1. Kịch bản
Giả sử rằng chúng ta có một nguồn đang tạo ra một giá trị ngẫu nhiên mỗi phút. Vì vậy, chúng tôi có giá trị ngẫu nhiên $x_1$ Trong $1$phút thứ nhất, $x_2$ Trong $2$phút thứ 2, $\ldots$, $x_n$ bên trong $n$phút thứ, v.v.
Sự phân bố của các giá trị $x_1, x_2, \ldots$ không hoàn toàn là ngẫu nhiên đồng nhất mà tuân theo quy luật sau: với mọi $i \ge 1$, $x_i = (y_i, y_{i+1})$, ở đâu, $y_i$ là định danh duy nhất của $x_i$, và $y_{i+1}$ là định danh duy nhất của sắp tới $x_{i+1}$ rằng sẽ đến vào phút tiếp theo.
Nói cách khác, tại bất kỳ thời điểm nào $i$phút thứ, hiện tại $x_i$, Và kế tiếp $x_{i+}$ được biết đến, nhưng cái sau $x_{i+2}$ là hoàn toàn không xác định, hoặc ngẫu nhiên. Dưới đây là một ví dụ:
Phút 1: x_1 = (334234 , 234829129 )
Phút 2: x_2 = (234829129, 983220 )
Phút 3: x_3 = (983220 , 831231236347)
...
Phút thứ n: x_n = (643532754, 3534611 )
Một cách để băm những $n$ các giá trị, theo thứ tự, là băm từng giá trị khi nó đến, ví dụ: $h_1 = f(x_1)$, sau đó xâu chuỗi nó với cái mới đến tiếp theo, ví dụ: $h_2 = f(x_2 \parallel h_1)$.
Nói cách khác, hàm băm của danh sách đầu vào được sắp xếp theo thứ tự, trong $n$phút thứ được định nghĩa đệ quy là $h_n = f(x_n \parallel h_{n-1})$, với trường hợp cơ sở là $h_1 = f(x_1)$.
Ưu điểm của cách tiếp cận này là, đối với một số người đang chạy quy trình này ngay từ đầu, tại mỗi phút, cả thời gian chạy và không-thời gian đều ở trong $O(1)$, vì anh ấy có thể lưu vào bộ nhớ đệm hàm băm từ phút trước.
Nhược điểm của phương pháp này là, đối với người không tuân theo quy trình và muốn xác minh xem liệu $h_n$ thực sự là hàm băm của toàn bộ chuỗi, anh ta sẽ phải bắt đầu lại từ đầu với $h_1$, và lặp lại toàn bộ chuỗi cho đến khi $h_n$. Thực tế, quá trình xác minh này sẽ mất $O(n)$ không gian và $O(n)$ thời gian.
2. Lỗ sâu
Sẽ thật tuyệt nếu có thể, tại mọi thời điểm $n$ nhiều chuỗi băm, chúng ta có thể khám phá một hố sâu $w_n$ đó có các thuộc tính sau:
- Một khi $n$thứ băm, $h_n$, được tính toán hợp pháp $h_1$ bằng cách tuân theo đệ quy đầy đủ trước đó, chỉ sau đó lỗ sâu $w_n$ trở nên được khám phá. Mặt khác, việc tìm kiếm $w_n$ thực tế là không thể.
- Để cho $h'_n$ băm được tuyên bố là $h_n$, lỗ sâu đục có thể tắt quá trình xác minh như sau:
$$
w_n(h_1, h'_n) = \begin{cases}
1 & \text{if $h'_n = h_n$}\
0 & \text{khác}\
\end{trường hợp}
$$
- Thời gian chạy tiệm cận tồi tệ nhất cũng như không gian tiệm cận tồi tệ nhất cho máy tính $w_n(h_1, h'_n)$ không tệ hơn $O(\log n)$. Nếu nó có thể làm cho nó trong $O(1)$, điều đó thậm chí còn tốt hơn tất nhiên.
Ghi chú. Điều này khác với hình ảnh trước cuộc tấn công của các hàm băm. Sự khác biệt như sau:
Các cuộc tấn công tiền hình ảnh cho phép kẻ tấn công giả mạo một Bất kỳ đầu vào cung cấp một số hàm băm mục tiêu mong muốn.
lỗ sâu này $w_n$ không cho phép giả mạo bất kỳ đầu vào tùy ý nào mà thay vào đó tiết lộ một đường tắt ẩn chỉ hoạt động để liên kết một đầu vào cụ thể cho phép liên kết $h_n$ Quay lại $h_1$, và cách duy nhất để khám phá lỗ sâu như vậy là tính toán hợp pháp $h_n$ đầu tiên.
Có lẽ chúng ta có thể gọi một lỗ sâu như vậy là một cuộc tấn công tiền hình ảnh có điều kiện không có lợi cho kẻ thù.
3. Câu hỏi
Các lỗ sâu xác minh như vậy có được biết đến hay thậm chí có thể xảy ra không?
