Tuy nhiên, câu trả lời không hề dễ dàng, một điểm khởi đầu tốt là Bài báo của Florent Chabaud và Antoine Joux về SHA-0 và SHA-1
Giới thiệu đơn giản
Trong MD4, SHA-0, SHA-1 và SHA-2 có chức năng nén. $$C:\{0,1\}^\ell \to :\{0,1\}^n$$ ở đâu $n$ là kích thước đầu ra và $\ell$ là chiều dài khối để xử lý.
chức năng nén $C$ có thể được xem như một mật mã khối trong đó khóa là thông báo, điều này có ý nghĩa vì phần duy nhất là đầu vào.Và, SHACAL được gọi là mật mã khối của SHA-1 và SHACAL-2 tương tự cho SHA-2.
Bây giờ, chúng tôi có một mật mã khối và chúng tôi có đầu vào ( các giá trị ban đầu $H_i$s và giá trị đầu ra ( hàm băm - thông báo). Chúng ta cần tìm chìa khóa. Nếu chúng tôi có thể tìm thấy khóa, chúng tôi có các cuộc tấn công và va chạm trước hình ảnh. Điều này có thể khiến người ta nghĩ rằng chúng ta đang tấn công như trong các cuộc tấn công khác biệt, không chính xác, nhưng theo cách tương tự.
Các tác giả lần đầu tiên bắt đầu với SHA-1 yếu (SHI1) trong đó việc mở rộng đầu vào không được xem xét và THÊM được chuyển đổi thành X-hoặc để không có phần phi tuyến tính. Với nhiễu loạn bit đơn lẻ và hiệu chỉnh trên đầu vào, họ đã tìm thấy các va chạm với mặt nạ.
Sau này, ADD chuyển đổi duy nhất thành X-or (SHI2) để kéo dài cuộc tấn công. Họ tìm thấy một mặt nạ phân biệt $\mathcal{M}$ có thể được áp dụng cho văn bản gốc (đầu vào) để tìm xung đột.
lookRandomCollision(h, khối):
m = ramdom_message(1 khối).
h = Hash(m)
m' = mặt nạ (m)
h' = Băm(m')
Nếu h=h':
trở lại (m)
khác:
trả lại -1
trong khi (1):
giao diện thành côngRandomCollision(SHA-1, 512)
nếu bí mật != -1:
print("Cặp va chạm là - ", m, mask(m))
Thành công của cuộc tấn công là xác suất thành công của mặt nạ $\mathcal{M}$ để giới thiệu va chạm. Nếu xác suất thành công của mặt nạ là $1/t$ sau đó xung quanh $c\cdot t$ cặp ngẫu nhiên một sẽ tìm thấy sự va chạm.
Sau đó, họ xem xét SHA-0 và SHA-1 thực để tìm mặt nạ như vậy. Họ tìm một cái cho SHA-0 với $2^{61}$-thời gian phức tạp. Mặt nạ họ tìm thấy cho SHA-1 không có độ phức tạp tốt hơn so với va chạm chung, tức là nó có độ phức tạp $> 2^{80}$.
Bài viết được viết tốt từ việc hiểu cuộc tấn công từ chức năng nén cấp thấp (không có phần phi tuyến tính) đến chức năng cấp cao hơn bao gồm phi tuyến tính.
Và, với khả năng cao, NSA đã nhận thức được điều này nên họ đã sửa đổi phần mở rộng đầu vào của SHA-0 trên SHA-1 bằng cách giới thiệu phép quay.
Tại sao nó nguy hiểm
Xem xét trường hợp SHA-1 bị hỏng, chúng ta có (các) khối Tiền tố $P$ và (các) khối Hậu tố $S$ và chúng tôi đang tìm kiếm một vụ va chạm
$$Hash(P\mathbin\| m \mathbin\|S) = Hash(P\mathbin\| m' \mathbin\|S)$$
Nếu chúng ta có thể tìm thấy một mặt nạ vi sai tốt $\mathcal{M}$ với xác suất tốt thì chúng ta có thể thực hiện cuộc tấn công vào khối $m$. Nếu một phần của tệp là một phần của sự dư thừa như trong các tệp PDF, thì người ta có thể tạo hai tệp PDF khác nhau có cùng giá trị băm. Tất nhiên, một mối nguy hiểm thực sự đòi hỏi nhiều hơn thế. Sự thay đổi trong $m'$ có lợi cho người ký. Điều này cũng có thể thực hiện được.
