Công cụ dành cho nhà phát triển · Máy tính hàm băm SHA
Hiệu ứng tuyết lở: Tại sao một ký tự bị thay đổi lại viết lại hàm băm SHA
· Cách thức hoạt động
sha-256 mật mã bảo vệ xác nhận
Thay đổi một chữ cái và khoảng một nửa số bit đầu ra bị lật. Bài đăng này giải thích đặc tính tuyết lở, tại sao nó lại cần thiết cho việc phát hiện giả mạo và cách các vòng của SHA-2 đạt được đặc tính đó.
Mong đợi hàm băm thay đổi một chút - trực giác mà hầu hết mọi người mang lại và lý do thiết kế cố tình phá vỡ nó
Hầu hết mọi người mong đợi rằng những đầu vào giống nhau sẽ tạo ra những đầu ra giống nhau. Thay đổi một ký tự trong một tệp và thông báo sẽ thay đổi một chút. Thay vào đó, băm mật mã được thiết kế để làm điều ngược lại: một thay đổi một bit ở đầu vào sẽ làm đảo lộn gần một nửa số bit đầu ra, điều này không thể đoán trước được. Đặc tính này được gọi là hiệu ứng tuyết lở và nó là có chủ ý. Thiết kế phục vụ một mục đích cụ thể: phát hiện giả mạo.
Hiệu ứng tuyết lở là lý do tại sao "gần như khớp" không phải là một khái niệm trong thế giới băm. Hàm băm khớp chính xác hoặc không. Không có "đủ gần". Thuộc tính này làm cho việc băm trở nên hữu ích cho việc kiểm tra tính toàn vẹn và đánh địa chỉ nội dung, đồng thời làm cho các thuật toán băm yếu không thể sử dụng được cho mục đích bảo mật.
Avalanche có nghĩa là khuếch tán đầu ra rộng rãi; bài viết này không đưa ra tuyên bố về xác suất chính xác không có nguồn gốc
Về mặt chính thức, hiệu ứng tuyết lở có nghĩa là đối với hai đầu vào khác nhau một bit, các bản tóm tắt đầu ra sẽ khác nhau ở khoảng 50% số bit của chúng. Đối với SHA-256 (256 bits đầu ra), việc thay đổi một bit đầu vào sẽ lật khoảng 128 bit đầu ra. Hiệu quả không chính xác; nó là một thuộc tính thống kê. Nhưng nó rất mạnh: trong thực tế, từng bit đầu vào được trộn lẫn kỹ lưỡng với từng bit đầu ra.
Tại sao khoảng một nửa? Bởi vì một đầu ra thực sự ngẫu nhiên sẽ khác với một đầu ra ngẫu nhiên khác ở mức trung bình chính xác bằng một nửa số bit của nó (theo nguyên tắc chuồng chim và thống kê cơ bản). Hàm băm tốt gần đúng với tính ngẫu nhiên; nó tạo ra đầu ra dường như không có khuôn mẫu rõ ràng. Trung bình một nửa số bit bị lật là dấu hiệu của tính ngẫu nhiên. Nếu hàm băm chỉ lật 10% số bit thì kẻ tấn công có thể tìm thấy các mẫu và khai thác chúng.
Tại sao cần có tính năng phát hiện giả mạo - những chỉnh sửa nhỏ đối với tài liệu không được tạo ra hàm băm gần giống hệt nhau mà có thể chấp nhận được nếu xem nhanh
Phát hiện giả mạo dựa vào tuyết lở. Nếu bạn tải xuống một tệp và tính toán SHA-256 của nó, thì kết quả mong đợi là ba7816... (làm ví dụ). Kẻ tấn công sửa đổi tệp bằng cách thay đổi một byte. Thông báo mới thay đổi từ ba7816... thành một cái gì đó như 3d4e92... (hoàn toàn khác). Khi bạn xác minh tệp dựa trên thông báo dự kiến, sự không khớp sẽ xảy ra ngay lập tức và toàn bộ. Không có chỗ cho sự hiểu sai: tệp đã bị giả mạo.
Nếu không có tuyết lở, kẻ tấn công có thể thay đổi một byte và thông báo có thể chỉ dịch chuyển một chút, thành ba7817... (khác một chữ số hex). Một so sánh thông thường có thể bỏ lỡ sự khác biệt. Kẻ tấn công thậm chí có thể tìm kiếm các đầu vào tạo ra thông báo bắt đầu bằng ba78, khẳng định tệp này là xác thực. Avalanche khiến việc này trở nên cực kỳ tốn kém: để tìm ra ngay cả hai đầu vào trong đó các bản tóm tắt bắt đầu bằng bốn chữ số hex giống nhau đòi hỏi nhiều công việc hơn mức thiết kế cho phép.
Các vòng thay đổi như thế nào — các phép quay, phép cộng và các hàm phi tuyến tính mang ảnh hưởng của một bit trên toàn bộ trạng thái
Các vòng trong SHA-256 (và các vòng trong SHA-512) được thiết kế để truyền bá các thay đổi. Mỗi vòng trộn dữ liệu bằng cách sử dụng các hàm phi tuyến tính (chọn, đa số) và phép quay. Một sự thay đổi một bit ở đầu vào sẽ được đưa vào lịch trình tin nhắn và truyền qua các vòng. Xoay chuyển vị trí bit. Các hàm phi tuyến tính ẩn ảnh hưởng của bit: việc thay đổi bit điều khiển trong thao tác chọn có thể lật bất kỳ bit đầu ra nào, tùy thuộc vào dữ liệu được chọn.
Các hằng số băm ban đầu, hằng số lịch trình tin nhắn, số vòng quay và số vòng đều được chọn để tối đa hóa hiệu ứng tuyết lở. Những con số này không phải là tùy ý; chúng đến từ đặc tả SHA-2 và đã được phân tích mật mã rộng rãi. Bất kỳ thay đổi nào đối với hằng số hoặc số vòng sẽ tạo ra một thuật toán khác (có thể là thuật toán yếu hơn).
Ví dụ đã hoạt động - băm hai đầu vào khác nhau một ký tự và so sánh các bản tóm tắt từng chút một
Việc kiểm tra tuyết lở rất đơn giản. Băm abc đầu vào và lưu ý thông báo. Sau đó băm abc theo sau là khoảng trắng hoặc thay thế một ký tự bằng ký tự khác: abd. So sánh kết quả đầu ra hex. Đối với SHA-256, khoảng một nửa chữ số thập lục phân 64 sẽ khác nhau. Đếm chúng. Vectơ thử nghiệm từ bài đăng ToolAcre: abc tạo ra ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. Một chuỗi trống tạo ra e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. Những thông báo đó không có chữ số hex chung.
Hãy thử tính năng này trên máy tính ToolAcre với bất kỳ dữ liệu đầu vào nào. Băm một câu. Sau đó thay đổi một chữ cái và băm lại. Đếm các chữ số hex khác nhau. Bạn sẽ thấy rằng khoảng một nửa (32 trong số 64, trong hầu hết các trường hợp) là khác nhau. Đây chính là hiệu ứng tuyết lở đang diễn ra. Đó là đặc tính của thiết kế thuật toán chứ không phải ngẫu nhiên.
Avalanche không cung cấp tìm kiếm tương tự hoặc tự định lượng khả năng chống va chạm
Avalanche không tạo tìm kiếm tương tự hoặc kết hợp gần đúng. Nếu bạn có một bản tóm tắt ba7816... và bạn muốn tìm một bản tóm tắt tương tự, bạn không có đường tắt. Bạn phải đoán hoặc bắt buộc các dữ liệu đầu vào của ứng viên, băm từng dữ liệu và kiểm tra xem có khớp chính xác không. Hiệu ứng tuyết lở khiến mọi dự đoán đều có khả năng tạo ra kết quả tương tự hoặc hoàn toàn khác nhau như nhau. Một số thuật toán băm (được gọi là băm nhạy cảm cục bộ) được thiết kế để duy trì sự tương đồng; chúng rất hữu ích cho việc phát hiện và phân cụm gần như trùng lặp, nhưng chúng không phải là hàm băm mật mã.
Avalanche cũng không bảo vệ khỏi việc tìm kiếm va chạm được xác định. Một nhà giải mã vẫn có thể tìm kiếm hai đầu vào khác nhau tạo ra cùng một bản tóm tắt, nhưng không gian tìm kiếm là rất lớn. Tìm kiếm va chạm được xác định là một câu hỏi khác với việc phổ biến hình ảnh. Bài viết này không trích dẫn một con số giới hạn ngày sinh nhật hoặc dòng thời gian phần cứng vì nó không đưa ra con số nào ở đây. Ranh giới có thể bảo vệ được là chỉ riêng trận tuyết lở không chứng minh cũng như định lượng khả năng chống va chạm.
Bài học rút ra: không suýt bỏ sót — hãy thử thử nghiệm một ký tự trong máy tính hàm băm ToolAcre SHA và xem toàn bộ sự thay đổi trong thông báo
Công cụ tính hàm băm ToolAcre SHA chạy thuật toán SHA thông qua việc triển khai Web Crypto của trình duyệt. Bạn có thể sử dụng nó để tự mình xác minh trận tuyết lở. Mọi độ chính xác trong thuật toán đều được đưa vào đầu ra và việc triển khai Web Crypto đều được nhà cung cấp trình duyệt kiểm tra và duy trì. Bạn đang thấy thuật toán thực chạy trên đầu vào thực. Thuộc tính phản trực giác mà một thay đổi ký tự sẽ viết lại toàn bộ bản tóm tắt không phải là một sai sót; đó là tính năng giúp cho việc băm hoạt động.
Khi bạn sử dụng hàm băm để kiểm tra tính toàn vẹn, bạn đang dựa vào tuyết lở. Khi bạn sử dụng nó để đánh địa chỉ nội dung (như thông báo hình ảnh vùng chứa), bạn phụ thuộc vào đặc tính mà những thay đổi nhỏ sẽ tạo ra các thông báo rất khác nhau. Khi bạn sử dụng nó trong chữ ký số (trong đó chữ ký được tính dựa trên hàm băm của tin nhắn), hiệu ứng tuyết lở đảm bảo rằng việc giả mạo tin nhắn sẽ tạo ra thay đổi có thể phát hiện được. Thuộc tính là nền tảng của bảo mật dựa trên hàm băm.