Hash Collision là gì?
Hash Collision là khi hai đầu vào khác nhau tạo ra cùng một kết quả băm. Hãy tưởng tượng hai chìa khóa khác nhau mà lại mở cùng một ổ khoá số. Hiếm gặp, nhưng nếu xảy ra với thuật toán kém an toàn thì có thể gây rắc rối.
“Nếu tồn tại một collision thì mọi thứ bị phá vỡ.” Không hẳn vậy. Các thuật toán mạnh được thiết kế để khiến bất kỳ Hash Collision thực tế nào gần như không thể xảy ra, và hệ thống hiện đại có nhiều lớp bảo vệ nên một lỗi không làm sụp toàn bộ.
Cách Hash Collision hoạt động
Hãy coi một giá trị băm như nhãn nhỏ cho dữ liệu lớn. Đây là tóm tắt ngắn từ đầu vào đến trùng.
- Đầu vào: Bạn bắt đầu với bất kỳ thông điệp, tệp, hoặc giao dịch nào.
- Băm: Một hàm thuộc họ hàm băm mật mã chuyển đầu vào đó thành một chuỗi có độ dài cố định.
- Va chạm: Vì số lượng kết quả giới hạn trong khi đầu vào vô hạn, hai đầu vào khác nhau có thể cho cùng một kết quả.
- Tấn công: Mối đe doạ nghiêm trọng là khi ai đó cố ý tạo hai đầu vào khác nhau mà trùng, rồi thay một cái bằng cái kia.
- Bảo vệ: Thuật toán tốt làm cho việc tìm kiếm đó cực kỳ tốn kém, nên đoán ngẫu nhiên tiêu tốn nhiều thời gian và tiền bạc.
Đó là ý chính.
Tại sao Hash Collision quan trọng
Tại sao bạn nên quan tâm tới khía cạnh ít được chú ý này của toán học và mã?
- Lợi ích: Khả năng chống va chạm cao giữ nhãn dữ liệu của bạn độc nhất, giảm cơ hội cho các chiêu trò tinh vi.
- Góc nhìn: Va chạm đe doạ tính toàn vẹn cho những thứ như công nghệ blockchain, cập nhật phần mềm và kiểm tra tệp.
- Tính ứng dụng: Bạn sẽ gặp nó trong ví, sàn giao dịch, các chứng minh và công cụ kiểm toán tin tưởng vào sự bằng nhau của băm.
Khi có lựa chọn, chọn các phương án ghép lớp bảo vệ như băm hai lần, và dùng các thuật toán đã được đánh giá rộng rãi và có kết quả đầu ra dài.
Các đặc điểm chính của Hash Collision
Điều gì làm hiện tượng này đáng chú ý và nên ghi nhớ:
- Không thể tránh: Khi kết quả hữu hạn còn đầu vào vô hạn, theo nguyên lý hộp thỏ, một vài cặp sẽ trùng.
- Khó: Với các hàm băm hiện đại, việc có chủ ý tìm một va chạm được thiết kế để tiêu tốn tài nguyên tính toán cực lớn.
- Chữ ký: Nhiều chữ ký số ký lên một giá trị băm, nên khả năng chống va chạm bảo vệ người ký khỏi chiêu trò đổi nội dung.
Hash Collision được tính như thế nào?
Bạn có thể ước lượng độ khó bằng ý tưởng ngày sinh. Với một hàm băm k bit, số lần thử ngẫu nhiên cần để đạt khoảng 50% khả năng có va chạm xấp xỉ căn bậc hai của 2 mũ k, nhân với khoảng 1.1774.
n_fifty_percent ≈ 1.1774 * sqrt(2^k) Ví dụ: với k bằng 256, số lần thử cần thiết lớn đến mức không tưởng, vì vậy dò tìm bằng brute force để tạo va chạm không phải là dự án cuối tuần.
Các biến thể
Nhiều dạng xuất hiện trong nghiên cứu và tấn công:
- Va chạm: Bất kỳ hai đầu vào khác nhau cùng chia sẻ một giá trị băm.
- Va chạm thứ hai: Khi biết một đầu vào, tìm đầu vào khác có cùng giá trị băm.
- Tiền ảnh: Khi biết một giá trị băm, tìm bất kỳ đầu vào nào ánh xạ tới nó.
- Va chạm tiền tố chọn trước: Tạo hai thông điệp có phần đầu do người tấn công chọn khác nhau nhưng cuối cùng cho cùng một giá trị băm.
SHA 256 chưa có va chạm công khai và thực tiễn. Nếu ai đó tuyên bố tìm thấy một va chạm, hãy chờ phản biện mạnh mẽ và kết quả kiểm tra trước khi bạn hoảng loạn hay ăn mừng.
Ví dụ
Nếu kẻ tấn công có thể tạo hai giao dịch khác nhau cùng có cùng txid, họ có thể thử mưu mẹo chi tiêu kép bằng cách thay giao dịch song sinh sau khi bạn ký.
Sự thật thú vị
Va chạm MD5 đã được chứng minh từ vài thập kỷ trước, và dự án SHAttered tạo ra một va chạm công khai cho SHA 1 với hai PDF khác nhau, làm ngành phải loại bỏ nó.
Tổng kết
Tóm lại, Hash Collision là trường hợp hiếm khi hai đầu vào khác nhau chia sẻ cùng một dấu vân tay kỹ thuật số, và mật mã hiện đại nỗ lực để giữ điều đó chỉ là thông tin tham khảo chứ không phải vấn đề lớn.