Công cụ dành cho nhà phát triển · Máy tính hàm băm SHA
Merkle–Damgård Giải thích: Công trình đằng sau SHA-1 và SHA-2
· Lý lịch
sha-256 mật mã browser-apis
Hàm nén có kích thước cố định không thể tự băm dữ liệu đầu vào tùy ý. Merkle–Damgård xâu chuỗi nó từng khối một; bài đăng này giải thích cách xây dựng, ý tưởng chứng minh của nó và những điểm yếu mà nó mang lại.
Đầu vào tùy ý, đầu ra cố định - vấn đề mà mọi hàm băm phải giải quyết trước tiên
Hàm băm phải ánh xạ đầu vào tùy ý tới đầu ra cố định. Cả thông báo ba byte và thông báo ba megabyte đều phải tạo ra chính xác 256 bits đầu ra cho SHA-256. Hàm băm phải có tính xác định, do đó, cùng một đầu vào luôn tạo ra cùng một đầu ra. Đầu ra phải trông ngẫu nhiên; thay đổi một bit của đầu vào sẽ thay đổi khoảng một nửa số bit đầu ra.
Thoạt nhìn, đây là những yêu cầu trái ngược nhau, bởi vì một thuật toán nhanh duy nhất không thể xử lý các thông báo có độ dài tùy ý và tạo ra đầu ra có chiều rộng cố định thống nhất. Cấu trúc Merkle–Damgård giải quyết vấn đề này bằng cách sử dụng hàm nén có kích thước cố định nhiều lần, đưa đầu ra của mỗi ứng dụng vào đầu vào của ứng dụng tiếp theo. Công trình này được sử dụng bởi SHA-1 và tất cả SHA-2 (SHA-256, SHA-384 và SHA-512).
Hàm nén - một bộ trộn có kích thước cố định nhận một trạng thái và một khối rồi trả về trạng thái mới
Hàm nén là nguyên hàm mã hóa cốt lõi hỗ trợ hàm băm Merkle–Damgård. Nó có trạng thái có kích thước cố định, thường là 256 bits cho SHA-256 hoặc 512 bits cho SHA-512 và khối đầu vào có kích thước cố định, thường là 512 bits cho SHA-256 hoặc 1024 bits cho SHA-512. Hàm nén trộn chúng lại với nhau bằng cách sử dụng các thao tác bitwise, phép quay và tra cứu bảng, tạo ra trạng thái mới có cùng kích thước. Hàm này phải có khả năng chống va chạm: việc tìm hai cặp (trạng thái, khối) khác nhau tạo ra cùng một đầu ra phải khó khăn.
Bản thân hàm nén không phải là một hàm băm hoàn chỉnh—nó không xử lý độ dài đầu vào tùy ý và thậm chí nó không xử lý đầu vào đầu tiên không có trạng thái trước đó. Thay vào đó, nó là khối xây dựng mà một công trình lớn hơn được xây dựng xung quanh. Hàm nén là hoạt động mã hóa duy nhất chạy lặp đi lặp lại; mọi thứ khác là sổ sách kế toán kết nối chức năng này với hàm băm đầy đủ.
Chuỗi và vectơ khởi tạo - cách các khối kết nối với nhau từ trạng thái bắt đầu cố định
Vectơ khởi tạo là trạng thái bắt đầu cố định, được chọn cẩn thận để tránh sự đối xứng hoặc điểm yếu. Đối với SHA-256, IV là tám từ 32-bit được lấy từ phần phân số của căn bậc hai của tám số nguyên tố đầu tiên. Các giá trị này là tùy ý nhưng mang tính xác định, do đó mọi triển khai đều tạo ra kết quả như nhau. Khối thông báo đầu tiên được trộn với IV bằng chức năng nén, tạo ra trạng thái mới. Khối thông báo thứ hai được trộn lẫn với trạng thái đó, tạo ra một trạng thái mới khác, v.v. qua mỗi khối thông báo.
Chuỗi này là phần quan trọng: đầu ra của một khối phụ thuộc vào tất cả các khối trước đó, do đó việc thay đổi bất kỳ bit nào của bất kỳ khối nào trước đó sẽ thay đổi tất cả các khối tiếp theo. Vào thời điểm khối cuối cùng được xử lý, trạng thái sẽ chứa thông tin về từng bit của đầu vào. Đệm là thủ thuật tạo nên âm thanh cho công trình này. Một tin nhắn không phải lúc nào cũng chia đều thành các khối. Cấu trúc Merkle–Damgård sử dụng tính năng tăng cường MD: nối thêm một bit vào tin nhắn, sau đó thêm các số 0 cho đến khi còn lại gần như toàn bộ khối, sau đó nối thêm độ dài tin nhắn ban đầu.
Đệm với độ dài tin nhắn - tại sao việc tăng cường MD là yếu tố tạo nên âm thanh cho kết cấu
Lập luận bảo mật cho Merkle–Damgård nói rằng nếu hàm nén có khả năng chống va chạm thì toàn bộ hàm băm có khả năng chống va chạm. Bằng chứng là sự rút gọn: nếu bạn có thể tìm thấy xung đột trong hàm băm, bạn có thể trích xuất xung đột trong hàm nén, điều này mâu thuẫn với giả định rằng hàm nén khó có thể va chạm. Theo trực giác, bất kỳ xung đột nào trong hàm băm cuối cùng đều phải tạo ra xung đột trong một trong các lệnh gọi hàm nén, vì trạng thái được chuyển tiếp hoàn toàn.
Những điểm yếu của Merkle–Damgård được phát hiện theo thời gian, mặc dù kết cấu cơ bản vẫn ổn. Phần mở rộng độ dài là một: kẻ tấn công nhìn thấy bản tóm tắt của tin nhắn có thể mở rộng tin nhắn và tính toán phần tóm tắt hợp lệ cho tin nhắn dài hơn mà không cần biết gì về đầu vào. Các cuộc tấn công tiền ảnh thứ hai là một kiểu tấn công khác: đưa ra một tin nhắn, việc tìm một tin nhắn khác có cùng hàm băm sẽ dễ dàng hơn so với một số loại tin nhắn. Những điểm yếu này đã thúc đẩy việc thiết kế SHA-3, sử dụng một cách tiếp cận khác gọi là cấu trúc xốp.
Khoảng đệm mã hóa độ dài phân tách các tin nhắn được đệm; bằng chứng bảo mật đầy đủ là bằng chứng kho lưu trữ bên ngoài
Hàm nén cho SHA-256 có trạng thái 256-bit (tám từ 32-bit) và khối 512-bit. Thao tác này sử dụng vòng 64, mỗi vòng trộn trạng thái với một hằng số và một từ trong khối. Việc trộn sử dụng các phép toán theo bit: XOR, AND, NOT. Nó sử dụng phép quay và dịch chuyển để di chuyển các bit xung quanh mà không thay đổi bit nào được đặt. Nó sử dụng tra cứu bảng cung cấp khả năng trộn phi tuyến tính mà riêng XOR không thể đạt được.
SHA-512 sử dụng cấu trúc tương tự như SHA-256 nhưng với các hoạt động 64-bit thay vì các hoạt động 32-bit. Trạng thái là 512 bits (tám từ 64-bit) và kích thước khối là 1024 bits. Hàm nén có 80 vòng thay vì 64, đồng thời các hằng số và tra cứu bảng cũng khác nhau. Đối với SHA-384, trạng thái và chức năng nén giống như SHA-512, nhưng chỉ 384 bits đầu tiên của trạng thái cuối cùng được xuất ra. 128 bits cuối cùng bị loại bỏ. Việc cắt ngắn này là lý do tại sao SHA-384 không thể kéo dài độ dài.
Phần mở rộng chiều dài là chỉ giới xây dựng đã được xác minh; xác nhận quyền sở hữu nhiều va chạm và SHA-3 động lực bị bỏ qua
Tính bảo mật của hàm băm Merkle–Damgård phụ thuộc vào một số thuộc tính được nắm giữ. Chức năng nén phải có khả năng chống va chạm nên việc tấn công trực tiếp vào nó là không khả thi. Sơ đồ đệm phải đảm bảo rằng các thông báo khác nhau tạo ra các dạng đệm khác nhau, vì vậy mọi xung đột trong hàm băm phải liên quan đến xung đột hàm nén. Kích thước khối và kích thước trạng thái phải đủ lớn để không thể sử dụng vũ lực. Trạng thái rộng hơn sẽ mở rộng không gian tìm kiếm chung, nhưng bài viết này không đính kèm số lượng hoạt động hoặc ngày khả thi mà không có dẫn xuất nội tuyến và nguồn được xem xét.
Nếu kẻ tấn công tìm thấy điểm yếu trong chức năng nén hoặc nếu máy tính lượng tử trở nên thiết thực và có thể tìm kiếm một không gian không có cấu trúc trong thời gian sqrt(2^n) thay vì 2^n thời gian, thì giới hạn bảo mật sẽ bị xói mòn. Điểm yếu thúc đẩy SHA-3 không phải là sự gián đoạn trong chức năng nén mà là vấn đề mở rộng độ dài và các lỗ hổng cấu trúc khác. Cấu trúc bọt biển tránh được những điều này bằng cách không bao giờ xuất bản trạng thái bên trong đầy đủ của nó.
Nội dung này không đề cập đến — các hàm vòng cụ thể của SHA-256, được đề cập trong một bài đăng riêng
Cách cấu trúc Merkle–Damgård xử lý mọi kích thước đầu vào là hệ quả thực tế của thiết kế của nó. Chia tin nhắn thành các khối 512-bit, đệm khối cuối cùng, xử lý mọi khối thông qua chức năng nén theo trình tự và xuất ra trạng thái cuối cùng. Đối với đầu vào một byte, phần đệm tạo ra khối 512-bit (một byte thông báo, một bit phần đệm, 447 bits số 0 và 64 bits cho độ dài). Số lần nén là số khối 512-bit, tỷ lệ thuận với độ dài tin nhắn.
Mọi thông báo mà máy tính băm ToolAcre SHA tạo ra đều xuất phát từ cấu trúc này. Thông báo 64 ký tự SHA-256 là trạng thái 256-bit cuối cùng được in ở dạng thập lục phân. Thông báo 128 ký tự SHA-512 là trạng thái 512-bit cuối cùng được in ở dạng thập lục phân. Thông báo 96 ký tự SHA-384 là 384 bits đầu tiên của trạng thái bit 512 cuối cùng. Phần đệm phía sau đảm bảo rằng mọi thông báo có thể tạo ra chính xác số khối và độ rộng thông báo phù hợp. Đây là cấu trúc Merkle–Damgård tiêu chuẩn chạy trên trình duyệt.
Bài học rút ra: bộ khung giống nhau đằng sau bốn thuật toán — mọi bản tóm tắt mà máy tính băm ToolAcre SHA tạo ra đều xuất phát từ cấu trúc này
Việc hiểu cấu trúc rất hữu ích để biết lý do tại sao các bản tóm tắt luôn có cùng chiều rộng và tại sao việc thay đổi một bit của đầu vào lại thay đổi toàn bộ bản tóm tắt. Thuộc tính chuỗi có nghĩa là mỗi bit của đầu vào ảnh hưởng đến mọi bit của đầu ra thông qua một loạt các thao tác trộn. Một thay đổi một bit sớm trong thông báo sẽ lan truyền qua tất cả các lần nén tiếp theo, do đó, bản tóm tắt cuối cùng sẽ hoàn toàn khác. Thuộc tính này được gọi là hiệu ứng tuyết lở và là dấu hiệu đặc trưng của hàm băm âm thanh.
Cấu trúc Merkle–Damgård đã được sử dụng trong nhiều thập kỷ và tạo thành nền tảng của các hàm băm được triển khai rộng rãi nhất. SHA-1 và SHA-2 được xây dựng dựa trên cấu trúc này và nhiều hệ thống được triển khai dựa vào kết quả đầu ra của chúng. Việc xây dựng được thiết lập chứ không phải thử nghiệm, nhưng lịch sử đó không làm cho mọi hoạt động sử dụng đều an toàn; phần mở rộng độ dài là một ranh giới được ghi lại. Hiểu cấu trúc này giúp các nhà phát triển hiểu lý do tại sao một số thuộc tính bảo mật nhất định được giữ nguyên và tại sao các vectơ tấn công nhất định tồn tại.