đảo ngược hàm băm làm cho khả năng tăng theo cấp số nhân, nhưng có một số lượng đầu vào hữu hạn. Thế nào?

Khi cố gắng đảo ngược hàm băm, sẽ xảy ra mất mát, ví dụ:

a+b=c
đã cho c=5, thử quay lại a,b (bước trước)
(a,b)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)

nhưng, với bất kỳ cặp nào trong số (a, b), chúng tôi nhận được c=5 trong bước tiếp theo và mỗi cặp trong số này có cùng mức tăng trưởng theo cấp số nhân được áp dụng khi đảo ngược chúng. Do đó, có vẻ như mỗi bước bạn lùi lại sẽ làm tăng số lượng giá trị có thể dẫn đến c=5 theo cấp số nhân.

Ngoài ra, không có hai nhánh nào có thể kết hợp lại khi đảo ngược, vì điều đó sẽ yêu cầu một nhánh (a,b,c) tách thành hai nhánh có thể (a,b,c), điều này là ngẫu nhiên không mang tính quyết định và do đó không thể thực hiện được trong quá trình băm.

Vấn đề là, có một số lượng đầu vào hữu hạn và một số lượng hữu hạn các giá trị (a, b, c) có thể. Nó có vẻ giống như một nghịch lý và giải pháp duy nhất tôi có thể tìm thấy là một số con đường là ngõ cụt, ví dụ: ((a,b,c)!=có thể tạo từ bất kỳ (a,b,c) nào khác). Tuy nhiên, tôi không nghĩ rằng bất kỳ (a, b, c) nào như vậy tồn tại, vì vậy có lẽ tôi có giải pháp sai?

đảo ngược hàm băm làm cho khả năng tăng theo cấp số nhân, nhưng có một số lượng đầu vào hữu hạn. Thế nào?

Đó là những gì chúng tôi mong đợi (truyện ngắn); mỗi ẩn số làm tăng khả năng lên gấp 2, do đó bạn sẽ nhận được một cấp số nhân - bạn có thể nghĩ đến bảng chân lý để thấy điều đó. Có đầu vào hữu hạn cho SHA-256 do các quy tắc đệm, nghĩa là $2^{128}-1$. Đầu vào của bạn có thể không lớn, vẫn còn hữu hạn.

Đảo ngược thao tác băm SHA-256 bằng cách giải các phương trình ( chúng tôi gọi đây là tấn công đại số) gần như là không thể vì bạn phải giải một phép tính tượng trưng (SAT) và 3SAT là NP-Complete. Không có gì đảm bảo rằng mọi phiên bản SHA-256 đều có thể chữa được. Khi chúng tôi xem xét rằng cuộc tấn công đại số đã tuyên bố của AES (XSL) không nhanh hơn vũ phu. Tôi hy vọng rằng vòng 64 của SHA-256 sẽ khó phân tích mật mã hơn bằng các cuộc tấn công đại số. Điều này vẫn không có nghĩa là đối với một số giá trị băm, trường hợp này cũng sẽ khó xử lý.

Ngay cả đối với không gian đầu vào 64 bit, tôi cho rằng đại số khó hơn tìm kiếm không gian đầu vào 64 bit để tìm hình ảnh trước của đầu ra hàm băm đã cho.

Trong tính toán của bạn, bạn đang loại bỏ một số khả năng của các biến, đây là điều chúng tôi mong đợi, tuy nhiên, vòng 64 của mật mã khối bên trong SHA-256 có tên SHACAL2 sẽ không cho phép bạn thực hiện nó nhiều. Đây không phải là cách để tấn công SHA-256.

cuốn sách của Bard; Giải mã đại số là một điểm khởi đầu cho cuộc tấn công đại số. Và, hãy xem cách thông báo mới lạ của họ giúp phá vỡ mã hóa keeloq đơn giản trong khi SHA-256 phức tạp hơn nhiều để xem xét.

Tôi nghĩ rằng sự nhầm lẫn của bạn xuất phát từ việc nhìn vào một thao tác đơn lẻ thay vì toàn bộ hàm băm. Đúng là việc đảo ngược một thao tác chẳng hạn như phép cộng đưa vào một biến đầu vào khác cho mỗi lần lặp. Nhưng điều đó bỏ qua cách thức hoạt động như vậy được sử dụng trong hàm băm. Nếu bạn nhìn vào một chức năng như SHA-256, thì một hoạt động như phép cộng phù hợp với một mạng lưới các hoạt động khác được xác định rõ ràng để chuyển đổi đầu vào thành đầu ra. Mạng chấp nhận 512 bit đầu vào và tạo ra 256 bit đầu ra và định nghĩa là cố định, vì vậy thực sự không có chỗ để nói về "tăng trưởng theo cấp số nhân". Điều đúng là việc cố gắng giải quyết một tập hợp các đầu vào tạo ra đầu ra mong muốn được dự kiến ​​​​sẽ tốn công sức theo cấp số nhân là quy mô của vấn đề.