Cho một hàm băm $\mathcal H()$ và một giá trị băm $H$ đó là trong tên miền/phạm vi đầu ra của $\mathcal H()$, bạn có thể xác định nếu $H$ có thể được sản xuất bởi $\mathcal H()$ (tức là $H$ trong hình ảnh của $\mathcal H()$)?
Tôi sẽ cho rằng "mã miền/phạm vi đầu ra" được xác định mà không cần tham chiếu đến những gì hàm băm thực sự tạo ra (chứ không phải là tập hợp các đầu ra thực tế của hàm băm, điều này sẽ làm cho nó đạt được tất cả theo định nghĩa).
Nếu một hàm băm $\mathcal H$ là như vậy mà đối với một phần khá lớn của nhất định $H$ trong tên miền của nó, người ta có thể triển lãm đầu vào $M$ như vậy mà $H(M)=H$, thì chức năng đó sẽ không có khả năng chống tạo ảnh trước. Do đó, cuộc triển lãm đã nói phải không thể tính toán được đối với một ngẫu nhiên $H$.
Nếu chúng ta lập mô hình hàm băm như một hàm ngẫu nhiên $\{0,1\}^*\to\{0,1\}^n$, sau đó theo người thu phiếu giảm giá vấn đề, số lần băm dự kiến của các tin nhắn ngẫu nhiên để đạt được tất cả các giá trị là $E=2^n\,(n\,\ln(2)+\gamma)+1/2+o(1)$. Trong thực tế tiền điện tử $n\ge128$ do đó $\log_2(E)\khoảng n+\log_2(n)-0,53$. Do đó, trung bình chúng ta cần băm ít hơn tất cả các tin nhắn chính xác 33 byte để đạt được tất cả các giá trị cho hàm băm 256 bit lý tưởng, nhưng cần băm nhiều hơn tất cả các tin nhắn chính xác 65 byte để đạt được tất cả các giá trị cho hàm băm 512-bit lý tưởng. băm nhỏ. Tạo ra nhiều giá trị băm như vậy là không thể.
Đối với các hàm băm thông thường như SHA-1, SHA-256, SHA-512 và tôi tin rằng SHA-3, như đã nêu trong đó câu trả lời khác, chúng tôi không có bằng chứng toán học nào cho thấy có thể đạt được mọi giá trị đầu ra. Điều tốt nhất chúng ta có thể nói là nó có khả năng đúng (thậm chí giới hạn ở những thông điệp phù hợp với một khối duy nhất và thậm chí còn hơn thế nữa với nhiều khối hơn), nhưng sẽ rất ngạc nhiên nếu nó có thể được chứng minh hoặc bác bỏ.
Nhưng tôi nghĩ chúng ta có thể xây dựng một hàm băm mà có thể chứng minh được đạt đến tất cả không gian đầu ra của nó, nhưng ở một mức độ lớn các thuộc tính được mong đợi từ hàm băm mật mã. Đây là một hàm băm ứng cử viên của chuỗi bit tùy ý có thể đạt được toàn bộ $\{0,1\}^{512}$.
Tôi sẽ sử dụng 3072-bit thủ an toàn $p$, đó là như vậy mà $q=(p-1)/2$ cũng là số nguyên tố; và một máy phát điện $g$ của nhóm nhân $\mathbb Z_p^*$, đó là $g\in[2,p-2]$ với $g^q\equiv-1\pmod p$. chúng ta có thể sử dụng $p=2^{3072}-2^{3008}+2^{64}\,(\left\lfloor2^{2942}\,\pi\right\rfloor+1690314)-1$ sau đó Nhóm MODP 3072-bit, và $g=\left\lfloor 2^{3070}\,e\right\rfloor$.
Tính toán hàm băm $H(M)\in\{0,1\}^{512}$ tin nhắn đầu vào $M\in\{0,1\}^*$ như sau:
- Chuyển đổi chuỗi bit $M$ thành số nguyên $m$ theo quy ước big-endian và theo dõi độ dài bit $\ell$ của $M$.
- tính toán
$$\begin{align}
m_0&=m\bmod(p-1)\
h_0&=(g^{m_0}\bmod p)-1\
h_1&=\left\lfloor h_0/2^{1024}\right\rfloor\bmod2^{512}\
h_2&=\left\lfloor h_0/2^{1664}\right\rfloor\bmod2^{512}\
m_1&=\left\lfloor m/(p-1)\right\rfloor\
\end{align}$$
Lưu ý: hằng số 1024 và 1664 chọn vị trí của hai phân đoạn 512-bit không chồng lấp tùy ý trong biểu diễn nhị phân của $h_0$.
- Chuyển thành $h_1$ thành chuỗi bit $H_1\in\{0,1\}^{512}$, $h_2$ thành chuỗi bit $H_2\in\{0,1\}^{512}$, và $m_1$ thành chuỗi bit $M_1\in\{0,1\}^{\ell}$ theo quy ước big-endian.
- Tính toán và xuất $H=H_1\oplus H_2\oplus\operatorname{SHA3-512}(M_1)$.
Sự chuyển hóa giữa $m_0$ và $h_0$ là một dự đoán của $[0,p-2]$. Nếu làm theo chúng ta có thể chứng minh được một hình ảnh trước $M$ của bất kỳ $H\in\{0,1\}^{512}$ nếu chúng ta có thể giải DLP trong nhóm nhân $\mathbb Z_p^*$: chúng tôi sửa $M_1=0^{3072}$ (do đó $\ell=3072$ và $m_0=m$), $h_0=2^{640}\,h_1$ (do đó $H_2=0^{512}$), điều đó cho phép chúng ta tính toán $H_1=H\oplus\operatorname{SHA3-512}(M_1)$, sau đó $h_1$, sau đó $h_0=2^{640}\,h_1$. Chúng tôi giải quyết vấn đề DLP $(g^{m_0}\bmod p)=h_0+1$ để có được $m_0$, sau đó $m$, sau đó là 3072-bit $M$.
Lập luận của tôi rằng hàm băm có khả năng chống va chạm và chống tạo ảnh trước là $M\mapsto(M_1,m_0)$ là thuốc tiêm, $m_0\mapsto H_1\oplus H_2$ dường như khá khó để đảo ngược hoặc va chạm và XORing điều đó với hàm băm không liên quan tốt của $M_1$ ít hơn một nửa khả năng chống va chạm.
Có bất kỳ lợi ích bạn có thể nghĩ đến?
tôi không thấy bất kỳ kỹ thuật thực tế mang lại lợi ích cho hàm băm có thể đạt được một cách rõ ràng tất cả tên miền của nó, vì chúng tôi không thể phân biệt bằng thực nghiệm với hàm băm tiêu chuẩn tốt nếu không có thuộc tính này. Mặt khác, nó sẽ thỏa mãn về mặt trí tuệ. Vấn đề là, bất cứ điều gì tôi có thể nghĩ đến (như ứng cử viên ở trên) nếu cả hai đều chậm hơn và kém an toàn hơn ở độ rộng đầu ra nhất định so với hàm băm tiêu chuẩn và việc xem xét thực tế đó sẽ cân nhắc lợi ích vô hình của việc đảm bảo có thể đạt được tất cả các giá trị đầu ra.
Tôi không thấy bất kỳ lợi ích nào đối với hàm băm mà rõ ràng là không thể đạt được một số không gian đầu ra của nó và do đó, về mặt tính toán, không thể thể hiện giá trị đầu ra đó hoặc không thể biết liệu giá trị không gian đầu ra nhất định có thể truy cập được hay không.
Tôi có thể tưởng tượng các ứng dụng cho hàm băm có thể không đạt được một số đã biết các giá trị trong không gian đầu ra của chúng (ví dụ: một giá trị như vậy có thể được dành riêng làm chỉ báo của trường hợp đặc biệt). Mặt khác, chúng ta có thể dễ dàng xây dựng các giá trị băm như vậy từ các giá trị gốc tiêu chuẩn. Ví dụ: đối với hàm băm 256 bit không thể đạt được $0^{256}$, chúng ta có thể sử dụng (với các chuyển đổi thông thường giữa chuỗi bit và số nguyên) $M\mapsto(\operatorname{SHAKE128}(M,416)\bmod(2^{256}-1))+1$. Và trong thực tế, chúng tôi cũng có thể sử dụng bất kỳ hàm băm 256 bit tiêu chuẩn nào.
