Thành phần của các hàm băm mật mã

Tôi đã vấp phải nhiều ý kiến, vì vậy tôi tự hỏi về chúng.

Để cho $H(x)$ và $F(x)$ là các hàm băm.

• Là $H(F(x))$ hoặc $F(H(x))$ An toàn hơn $H(x)$ hoặc $F(x)$
• Là $H(F(x))$ hoặc $F(H(x))$ an toàn khi $H(x)$ hoặc $F(x)$ trở nên dễ bị tổn thương
• Là $H(H(x))$ An toàn hơn $H(x)$

Lý lịch

Thực hiện nghiên cứu của riêng tôi, tôi đã tìm thấy những tuyên bố gợi ý rằng việc kết hợp h và F là một thực tế phổ biến để giữ an toàn khi một trong số chúng trở nên không an toàn, nhưng có nhiều ý kiến ​​trái chiều về việc liệu sự kết hợp đó có an toàn như TỐI ĐA(H, F) hoặc TỐI THIỂU(H, F) về mặt an toàn, hầu như không ai đề xuất hơn mức an toàn sẽ cao hơn hoặc thấp hơn mức này.

Tôi cũng phát hiện ra rằng một số thuật toán liên quan đến việc sử dụng mật khẩu SHA256d, về cơ bản là SHA256(SHA256(x))và về lý thuyết, việc sử dụng nhiều vòng hơn sẽ tăng độ an toàn của hàm băm, điều này không còn xa với việc kết hợp hàm băm với chính nó.

Tôi cũng có một số suy nghĩ cá nhân về điều này, bắt nguồn từ toán học ở trường. Tôi thấy rõ ràng rằng nếu f:A -> B và rất nhiều |A| > |B| và g:B -> C và rất nhiều |B| > |C| sau đó g(f(x)) nên có nhiều va chạm hơn f hoặc g. Nhưng cũng có một thực tế là chúng ta kết hợp 2 hàm phức tạp nên hơi khó "phá" hơn.

Vì vậy, trực giác của riêng tôi là g(f(x)) có nhiều va chạm hơn, nhưng khó tìm ra phương pháp tìm va chạm có mục đích và trong trường hợp các chức năng như SHA hoặc BLACK sự gia tăng va chạm không phải là một vấn đề, nhưng lợi ích bảo mật là xứng đáng.

Thành phần không phải là cách tốt nhất để kết hợp các hàm băm, nhưng rủi ro là câu hỏi về thuộc tính bảo mật nào bạn yêu cầu.

Đối với khả năng chống va chạm, tìm va chạm trên $H(F(X))$ không khó hơn việc tìm ra một va chạm của $F(X)$ và vì vậy nếu $F$ là va chạm bị tổn hại, sau đó như vậy là $H(F(X))$. Để thấy điều này, hãy $m_1$ và $m_2$ là hai đầu vào riêng biệt sao cho $F(m_1)=F(m_2)$ sau đó bởi vì $H$ là một chức năng chúng ta có $H(F(m_1))=H(F(m_2))$. trong trường hợp cụ thể $F=H$, $H(H(X))$ không có khả năng chống va chạm hơn $H(X)$.

Tương tự, nếu $H(X)$ là va chạm bị tổn hại và $F(X)$ bị xâm phạm trước hình ảnh (bị xâm phạm cực kỳ nghiêm trọng để hình ảnh trước mất ít thời gian hơn so với công việc sinh nhật), chúng tôi có thể thỏa hiệp do va chạm $H(F(X))$ bằng cách tìm một va chạm trên $H$ và sau đó tìm hình ảnh trước cho cả hai thông điệp xung đột.

Lưu ý sự khác biệt trong các chức năng bên trong và bên ngoài. Chúng tôi hiện có thể tìm thấy tin nhắn $m_1$ và $m_2$ như vậy mà $\mathrm{SHA3}(\mathrm{SHA1}(m_1))=\mathrm{SHA3}(\mathrm{SHA1}(m_2))$, nhưng chúng tôi không thể tìm thấy $m_3$ và $m_4$ như vậy mà $\mathrm{SHA1}(\mathrm{SHA3}(m_3))=\mathrm{SHA1}(\mathrm{SHA3}(m_4))$.

Tương tự như vậy đối với khả năng chống tiền hình ảnh thứ hai nếu chức năng bên trong bị ảnh hưởng trước hình ảnh thứ hai, thì bố cục cũng vậy.

Đối với khả năng chống lại hình ảnh trước đầy đủ, chắc chắn chúng tôi có thể tìm thấy hình ảnh trước đầy đủ cho bố cục nếu chúng tôi có thể tìm thấy hình ảnh trước đầy đủ cho cả hai $H$ và $F$. Thỏa hiệp trước hình ảnh của một hàm băm duy nhất là không đủ: hãy xem xét một hàm băm tuyến tính $L(X)$ đó là hình ảnh trước bị hỏng tầm thường. Đối với một mục tiêu $Y$, chúng ta không thể tìm thấy $X$ như vậy mà $\mathrm{SHA3}(L(X))=Y$ cũng không $L(\mathrm{SHA3}(X))=Y$.

Bảo mật mục tiêu của các hàm băm mật mã như SHAx, BLAKE, v.v. là khả năng chống va chạm. Chi phí tấn công va chạm chung cổ điển là $\mathcal{O}(2^{n/2})$-thời gian do cuộc tấn công sinh nhật.

Bây giờ, hãy xem xét các thành phần băm của bạn một cách chi tiết;

• Là $H(F(x))$ hoặc $F(H(x))$ An toàn hơn $H(x)$ hoặc $F(x)$

• Cuộc tấn công mở rộng chiều dài;

Băm kép được đề xuất bởi Bruce Schneier để giảm thiểu tấn công mở rộng chiều dài của các hàm băm dựa trên MD. Tấn công mở rộng chiều dài được thực hiện đối với bí mật tiền tố $H(bí mật||thông điệp)$. Băm đôi được thiết kế như $H(H(x))$ và Bitcoin sử dụng SHA256d để khai thác chậm. Tuy nhiên, trường hợp của bạn thì khác, cuộc tấn công này chỉ hoạt động nếu bạn muốn sử dụng hàm băm này để xây dựng MAC với cấu trúc bí mật tiền tố. Trong hàm băm kép, những kẻ tấn công không thể mở rộng hàm băm bên trong, vì vậy sẽ an toàn trước việc mở rộng độ dài ngay cả khi các hàm băm đơn lẻ không hoạt động. Tuy nhiên, việc sử dụng SHA3, SHA-512/256, BLAKE2, Shake tốn thời gian đã được bảo mật theo cách này ngay cả đối với máy tính lượng tử mã hóa có thể.

Bất kỳ hàm băm mật mã nào với cuộc tấn công mở rộng độ dài không phải là Oracle ngẫu nhiên. Do đó, SHA3 và BLAKE2 gần với các lời tiên tri ngẫu nhiên hơn.

• **

• va chạm

Sức cản**

Nếu băm nội bộ $H$ hoặc $F$ không chống va chạm thì các giá trị băm kết hợp $H(F(x))$ hoặc $F(H(x))$ sẽ không có khả năng chống va chạm. Được cho $x,y$ với $x\neq y$, nếu $H(x)=H(y)$ sau đó $F((H(x))=F(H(y))$ là va chạm đối với thành phần, và tương tự đối với $H(F(\cdot))$ trường hợp.

Nếu bạn muốn giảm thiểu cuộc tấn công va chạm của hàm băm nội bộ, câu trả lời đơn giản; không sử dụng nó.

• Điện trở hình ảnh trước

  Điện trở tiền ảnh thứ nhất và thứ hai có cùng một vấn đề, bỏ qua ở đây.

• Là $H(F(x))$ hoặc $F(H(x))$ an toàn khi $H(x)$ hoặc $F(x)$ trở nên dễ bị tổn thương

Khi nào $F(x)$ có một vụ va chạm sau đó $H(F(x))$ có một vụ va chạm nhỏ được trả lời trong phần đầu tiên.

Để cho $F(x)$ an toàn (không xung đột, không mở rộng độ dài, không hình ảnh trước) nhưng không $H(x)$ thì sao $H(F(x))$? Đây là một chút khó khăn, để sử dụng cuộc tấn công va chạm của $H$ chúng ta cần tìm hình ảnh trước của $F$ vì vậy điều này là an toàn hơn.

• Là $H(H(x))$ An toàn hơn $H(x)$

một chút có; $H(H(x))$ là an toàn chống lại cuộc tấn công mở rộng chiều dài. Nếu có sự va chạm của $H$, $H(x)=H(y)$ với $x \neq y$ sau đó nó là một vụ va chạm cho đôi $H(H(x)) = H(H(y))$, quá.

Tôi cũng phát hiện ra rằng một số thuật toán liên quan đến mật khẩu sử dụng SHA256d, về cơ bản là SHA256(SHA256(x)) và về lý thuyết, sử dụng nhiều vòng hơn sẽ tăng độ an toàn của hàm băm, điều này không quá xa so với việc tự kết hợp hàm băm với chính nó.

Bất cứ ai sử dụng SHA256d để băm mật khẩu đều không biết gì về chúng. Băm mật khẩu yêu cầu thời gian, bộ nhớ và tiêu thụ chuỗi để giảm thiểu các tìm kiếm lớn bằng CPU, GPU hoặc ASIC.

SHA256d được sử dụng trong Bitcoin để có khai thác chậm. Bất kỳ hệ thống mới nào được thiết kế để băm mật khẩu nên sử dụng ít nhất Scrypt hoặc Argon2 tốt hơn và các hệ thống cũ phải được di chuyển càng sớm càng tốt.

Để có kết quả chi tiết về học thuật trên bộ kết hợp băm, hãy bắt đầu đọc từ

• Các cuộc tấn công chung vào Hash Combiner, Boa et. al. 2020

Và, thậm chí chúng có thể tạo ra nhiều va chạm;

• Đa va chạm trong các hàm băm lặp lại. Ứng dụng cho các công trình Cascaded, Joux, 2004