Hãy tưởng tượng bạn có một tài liệu và đã tính mã băm SHA-1 nhưng hacker cũng có thể thay đổi hay tạo được văn bản giả mạo có giá trị băm giống với tài liệu gốc. Điều này làm tính toàn vẹn của văn bản và chữ ký số trở nên vô giá trị.
Hàm băm là gì?
Hàm băm là một cách mã hóa trong kỹ thuật mật mã nhằm sinh ra các giá trị băm (hash) tương ứng với mỗi khối dữ liệu (có thể là một chuỗi kí tự, một đối tượng trong lập trình hướng đối tượng, v.v...). Hàm băm là hàm "một cửa', hay “cửa sập” (trapdoor), nghĩa là hàm mà có thể tính toán dễ dàng một chiều và rất khó khăn theo chiều ngược lại.
Ảnh minh họa về hàm cửa sập (trapdoor function).
Ví dụ cho một biến số x và một hàm f(x). Việc từ x tính ra f(x) là dễ nhưng từ f(x) để tính ra x khó vô cùng. Trong hàm cửa sập tồn tại một thông tin bí mật k mà từ f(x) có thể tính ra x dễ dàng. Một ví dụ đơn giản, giả sử cho bạn một số 28 chữ số là 4951760154835678088235319297 và là tích của hai số nguyên tố (số mà chỉ chia hết cho 1 và chính nó). Tìm hai số đó? Cách làm là thử các số nguyên tố 2, 3,5,7,11,… xem số kia có chia hết không cho đến khi tìm ra. Việc này là rất tốn thời gian và công sức về mặt tính toán. Nhưng nếu được gợi ý một thừa số nguyên tố là 2147483647 (số nguyên tố Mersene thứ 8 do Euler tìm ra), thì bạn có thể dễ dàng tìm số nguyên tố còn lại là 2305843009213693951, cũng là một số nguyên tố Mersene thứ 9 có 19 chữ số.
Với các hàm băm cũng thế, giá trị băm của một dữ liệu bất kỳ dễ dàng tính toán được. Nhưng từ mã băm ấy, để khôi phục hay tìm được một dữ liệu có cùng một mã băm là rất khó khăn, tốn nhiều công sức tính toán và thời gian lâu dài.
Một hàm băm tốt phải thỏa mãn các điều kiện sau:
+ Tính toán nhanh.
+ Các khoá được phân bố đều trong bảng.
+ Ít xảy ra đụng độ.
+ Xử lý được các loại khóa có kiểu dữ liệu khác nhau.
Lưu ý rằng hàm băm ít xảy ra đụng độ chứ không phải không có đụng độ. Hàm băm thực tế không phải là một hàm đơn ánh (ánh xạ 1:1), như vậy tồn tại nhiều giá trị x có cùng một giá trị băm f(x), nghĩa là tồn tại những đụng độ.
Một đụng độ (collision) là gì?
Bình thường, khi ta tính toán một giá trị băm của hai khối dữ liệu (văn bản, chương trình, chứng thực website) thì sẽ có các giá trị băm khác nhau. Một đụng độ xảy ra khi hai khối dữ liệu có cùng một giá trị băm.
Hàm băm SHA-1 và đụng độ khi hai khối dữ liệu có cùng một giá trị băm (hình bên phải).
Từ năm 2005, MD5 và SHA-1 đã được chứng minh là khá yếu. Vào năm 2013, nhà nghiên cứu Marc Stevens đã xuất bản một bài báo chứng minh về lý thuyết đã tìm ra một đụng độ của SHA-1. Tuy nhiên để tìm bằng chứng các đụng độ thì cho đến mới đây, sau 2 năm nỗ lực tính toán, các nhà nghiên cứu Google mới có thể tìm ra được phương pháp tạo các đụng độ.
So với dùng phương pháp cổ điển (brute force), việc thử lần lượt các tổ hợp có thể có của mã 160 bit SHA-1 hầu như là bất khả với sức mạnh tính toán hiện nay, thì phương pháp "SHA-1 shattered" nhanh gấp 100.000 lần.
Nhờ vào công cuộc tính toán của Google, chúng ta không cần phải mất hàng ngàn năm thời gian máy tính để tạo ra hai văn bản có cùng một mã băm nữa.
Nguy hiểm từ đụng độ hàm băm
Tác giả đã thử thực hiện với thực hiện công cụ "SHA1 collider" (tại đây) và thực sự khi thử nghiệm với 2 file là A.PDF, B.PDF có cùng mã băm 891D6FE592B4CBB48717841F1AEBD1E4AF5F4FEA.
Và hãy tưởng tượng bạn có một tài liệu và đã tính mã băm SHA-1 hoặc dùng chữ ký điện tử trên mã băm đó nhưng hacker cũng có thể thay đổi hay tạo được văn bản giả mạo có giá trị băm (hash) giống với tài liệu gốc. Điều này làm tính toàn vẹn (integrity) của văn bản và chữ ký số trở nên vô giá trị.
Infographic về công bố đụng độ SHA-1 (nguồn Google Blog).
Theo ICTNews
Thêm bình luận