Birthday attack là một kiểu tấn công mật mã thuộc một loại tấn công brute force. Nó khai thác toán học đằng sau vấn đề birthday trong lý thuyết xác suất. Sự thành công của cuộc tấn công này phần lớn phụ thuộc vào khả năng xảy ra va chạm cao hơn được tìm thấy giữa các lần tấn công ngẫu nhiên và một mức độ hoán vị cố định, như được mô tả trong bài toán nghịch lý birthday.
Các bài viết liên quan:
Bài toán nghịch lý birthday
Chúng ta hãy xem xét ví dụ về một lớp học có 30 học sinh và một giáo viên. Giáo viên mong muốn tìm được các cặp học sinh có birthday giống nhau. Do đó, giáo viên yêu cầu birthday của mọi người để tìm những cặp như vậy. Về mặt trực quan, giá trị này có vẻ nhỏ. Ví dụ, nếu giáo viên ấn định một ngày cụ thể là ngày 10 tháng 10, thì xác suất để ít nhất một học sinh sinh vào ngày đó là 1 – (364/365) 30 là khoảng 7,9%. Tuy nhiên, xác suất để ít nhất một học sinh có cùng birthday với bất kỳ học sinh nào khác là khoảng 70% theo công thức sau:
Nguồn gốc của thuật ngữ trên:
Giả định:
- Giả sử một năm không nhuận (do đó có 365 ngày).
- Giả sử rằng một người có khả năng sinh ra như nhau vào bất kỳ ngày nào trong năm.
Chúng ta hãy xem xét n = 2.
P (Hai người có cùng birthday) = 1 – P (Hai người có birthday khác nhau)
= 1 – (365/365) * (364/365)
= 1 – 1 * (364/365)
= 1 – 364/365
= 1/365.
Vậy đối với n người, xác suất để tất cả họ có ngày birthday khác nhau là:
P (N người có birthday khác nhau) = (365/365) * (365-1 / 365) * (365-2 / 365) *…. (365-n + 1) / 365.
= 365! / ((365-n)! * 365n)
Hàm băm
Hàm băm H là một phép biến đổi nhận đầu vào có kích thước thay đổi m và trả về một chuỗi có kích thước cố định được gọi là giá trị băm (h = H (m)). Các hàm băm được chọn trong mật mã phải đáp ứng các yêu cầu sau:
- Đầu vào có độ dài thay đổi,
- Đầu ra có độ dài cố định,
- H (x) tương đối dễ tính cho bất kỳ x nào cho trước,
- H (x) là một chiều,
- H (x) là không va chạm.
Hàm băm H được cho là một chiều nếu nó khó đảo ngược, trong đó “khó đảo ngược” có nghĩa là đã cho một giá trị băm h, về mặt tính toán không khả thi để tìm một số đầu vào x sao cho H (x) = h.
Nếu, cho trước một thông báo x, về mặt tính toán không thể tìm thấy một thông báo y không bằng x sao cho H (x) = H (y) thì H được cho là một hàm băm không có va chạm yếu.
Một hàm băm không có va chạm mạnh H là một hàm mà về mặt tính toán không khả thi để tìm hai thông báo x và y bất kỳ sao cho H (x) = H (y).
Cho H: M => {0, 1} n là một hàm băm (| M | >> 2n)
Sau đây là một thuật toán chung để tìm xung đột trong thời gian băm O (2n / 2).
Thuật toán:
- Chọn 2^(n / 2) message ngẫu nhiên trong M: m1, m2,…., Mn / 2
- Với i = 1, 2,…, 2^(n / 2) tính ti = H (mi) => {0, 1} n
- Tìm một va chạm (ti = tj). Nếu không tìm thấy, hãy quay lại bước 1
Chúng tôi xem xét thử nghiệm sau đây. Từ tập các giá trị H, chúng ta chọn ngẫu nhiên đồng nhất n giá trị, do đó cho phép lặp lại. Gọi p (n; H) là xác suất để trong quá trình thử nghiệm này, ít nhất một giá trị được chọn nhiều hơn một lần. Xác suất này có thể được tính gần đúng như sau:
Tính nhạy cảm của chữ ký số
Chữ ký điện tử có thể dễ bị tấn công birthday. Một thông điệp m thường được ký bởi phép tính đầu tiên H (m), trong đó H là một hàm băm mật mã, và sau đó sử dụng một số khóa bí mật để ký H (m). Giả sử Alice muốn lừa Bob ký một hợp đồng gian dối. Alice chuẩn bị một hợp đồng công bằng m và gian lận một m ‘. Sau đó, cô ấy tìm một số vị trí mà m có thể thay đổi mà không làm thay đổi ý nghĩa, chẳng hạn như chèn dấu phẩy, dòng trống, một so với hai dấu cách sau một câu, thay thế các từ đồng nghĩa, v.v. Bằng cách kết hợp những thay đổi này, cô ấy có thể tạo ra một số lượng lớn các biến thể trên m đó là tất cả các hợp đồng công bằng.
Tương tự, Alice cũng có thể thực hiện một số thay đổi này đối với m ’để làm cho nó, thậm chí nhiều hơn, gần hơn với m, đó là H (m) = H (m’). Do đó, Alice hiện có thể trình phiên bản m hợp lý cho Bob để ký. Sau khi Bob đã ký, Alice lấy chữ ký và đính kèm vào đó là hợp đồng gian dối. Chữ ký này chứng tỏ Bob đã ký vào hợp đồng gian dối.
Để tránh một cuộc tấn công như vậy, đầu ra của hàm băm phải là một chuỗi bit rất dài để cuộc birthday attack bây giờ trở nên không khả thi về mặt tính toán.
