Sợi hữu hạn của SHA512

Là những $y\in\{0,1\}^{512}$ với $\emptyset \neq s^{-1}(\{y\})$ và $s^{-1}(\{y\})$ là hữu hạn?

Đối với SHA-512 như được định nghĩa thực sự, thì đúng là có, vì kích thước đầu vào bị hạn chế đến $2^{128}-1$ chút. Điều đó làm cho $s^{-1}(\{y\})$ đúng cho bất kỳ $y\in\{0,1\}^{512}$. Và $y$ hàm băm của chuỗi bit rỗng đáp ứng điều kiện $\emptyset \neq s^{-1}(\{y\})$. Sau đây chúng tôi giả sử điều này $2^{128}-1$ giới hạn bit được loại bỏ.

Cá cược của tôi là mệnh đề bây giờ là sai, bởi lập luận sau đây (không phải là bằng chứng).

1. Có vẻ hợp lý khi SHA-512 đạt được mọi hàm băm 512 bit đối với một số thông báo tối đa 895 bit (thông báo liên kết khối lớn nhất yêu cầu một vòng). Lập luận: theo mô hình mật mã khối lý tưởng cho mật mã khối ở trung tâm của vòng SHA-512, mỗi hàm băm của thông báo đó là ngẫu nhiên và độc lập trong $\{0,1\}^{512}$. Bằng nhà sưu tập phiếu giảm giá bị ràng buộc, chúng tôi hy vọng sẽ nhận được tất cả các giá trị sau khoảng $2^{520.5}$ vẽ, và ước tính đuôi về cơ bản loại trừ (xác suất $<2^{-(2^{384})}$) chúng tôi sẽ không nhận được tất cả sau $2^{896}-1$ cố gắng. Điều đó thực tế chỉ có thể thất bại nếu mô hình của chúng tôi quá tệ.

2. Điều hợp lý hơn nữa là SHA-512 đạt được mọi hàm băm 512 bit cho một thông báo tối đa 1919 bit (thông báo được căn chỉnh khối lớn nhất yêu cầu hai vòng), bởi vì với hai vòng, số lượng đầu vào có thể đạt được trong các vòng đầu tiên $2^{1024}$, làm cho nó (theo đối số 1) có khả năng gần với $2^{512}$ các giá trị có thể đạt đến đầu vào trạng thái 512-bit của vòng thứ hai; và chúng tôi nhận được $2^{896}-1$ khối đầu vào tin nhắn như trong vòng đầu tiên. Do đó, chúng tôi thậm chí còn vượt xa giới hạn của bộ sưu tập phiếu giảm giá và quan trọng hơn là vì chúng tôi có thêm 512 bit đầu vào thay đổi nên có vẻ như mô hình của chúng tôi không thể tệ đến thế.

3. Lập luận này cho vòng thứ hai có thể được lặp lại cho bất kỳ số vòng lớn hơn nào, dẫn đến kết luận rằng mỗi giá trị trong $\{0,1\}^{512}$ có khả năng đạt được ở hầu hết các vòng.

4. Điều đáng ngạc nhiên hơn nữa là khi chúng ta đặt độ dài thông điệp theo modulo $2^{128}$ lấy tất cả các giá trị có thể, bất kỳ $2^{512}$ giá trị đạt được cho không có tin nhắn $2^{128}$ đến $2^{129-1}$ bit: chúng tôi có thêm gần 128 bit đầu vào có thể thay đổi.

5. Và sau đó, vì độ dài tin nhắn được phép tăng vô hạn, chúng tôi có khả năng đó, bất kỳ $y$ có vô hạn $s^{-1}(\{y\})$.

6. Các $\emptyset \neq s^{-1}(\{y\})$ một phần của đề xuất làm cho nó thậm chí ít có khả năng nắm giữ. Giả sử rằng 512-bit giá trị ban đầu của SHA-512 đạt được một lần nữa (nội bộ) sau $2^{119}$ vòng cho ít nhất một (giả sử $w$) sau đó $2^{(2^{129})}$ tin nhắn khác nhau bắt đầu từ $2^{129}$ bit, có khả năng theo phiên bản sửa đổi một chút của 3 ở trên (chúng tôi có toàn quyền đối với mọi $2^{119}$ khối đầu vào 1024-bit của $w$). Bây giờ nếu một số $y\in\{0,1\}^{512}$ Là $\operatorname{SHA-512}(x)$, sau đó nó cũng $\operatorname{SHA-512}(w\mathbin\|x)$ và tổng quát hơn $\operatorname{SHA-512}(w\mathbin\|\ldots\mathbin\|w\mathbin\|x)$ do đó bác bỏ một cách xây dựng đề xuất.