I. Nghịch lý ngày sinh nhật

1. Phát biểu

Mỗi người đều có ngày sinh duy nhất của mình, có thể nhận một trong $365$ giá trị (trong khuôn khổ bài viết này chúng ta bỏ qua năm nhuận) từ 1/1 tới 31/12. Chúng ta xem xét xác suất xảy ra hai người có trùng ngày sinh trong một nhóm người.

Nhớ lại nguyên lý Dirichlet: "Nếu nhốt $n$ con chim bồ câu vào $m$ chiếc lồng, khi $n>m$ thì luôn tồn tại một lồng chứa ít nhất hai con chim". Như vậy, nếu xét một nhóm gồm $366$ người thì chắc chắn có hai người trùng ngày sinh, hay xác suất bằng $1$.

Nhưng, nếu chúng ta giảm số người trong nhóm đi, thì giá trị xác suất này có giảm nhiều không? Thực tế thì nó giảm ... không đáng kể! Đó cũng chính là cái tên "nghịch lý ngày sinh nhật". Nghịch lý có nhiều cách phát biểu, chúng ta sẽ tiếp cận qua một hướng đơn giản: Nếu trong một lớp học có từ $23$ sinh viên trở lên, thì xác suất tồn tại hai người trùng ngày sinh lớn hơn $\frac{1}{2}$.

2. Chứng minh

Con số $23$ thực sự quá nhỏ so với $366$ ngày trong một năm nhỉ, nhưng xác suất lại thực sự đã vượt quá một nửa! Thật vậy, cùng chứng minh nghịch lý trên trong trường hợp tổng quát nhóm có $n$ người ($n\le 365$).

Gọi $p(n)$ là xác suất trong nhóm $n$ người có hai người trùng ngày sinh. Chúng ta sẽ thực hiện tính $\overline{p}(n)$ trước - xác suất $n$ người này không có bất kỳ hai người nào trùng ngày sinh. Lần lượt chọn ra từng người, bắt đầu từ người thứ hai:

Xác suất người thứ hai không trùng ngày sinh người thứ nhất là:

$$1-\frac{1}{365}$$

Xác suất người thứ ba không trùng ngày sinh hai người trước là:

$$1-\frac{2}{365}$$

...

Xác suất người thứ $n$ không trùng ngày sinh $n-1$ người trước là:

$$1-\frac{n-1}{365}$$

Dễ dàng tính được:

$$\overline{p}(n) = (1-\frac{1}{365})(1-\frac{2}{365})...(1-\frac{n-1}{365})$$

$$=\frac{365}{365}\times \frac{363}{365}\times ...\times \frac{365-n+1}{365}=\frac{365!}{365^n(365-n)!}$$

Suy ra xác suất tồn tại hai người trùng ngày sinh là:

$$p(n)=1-\frac{365!}{365^n(365-n)!}$$

Quan sát bảng sau với một số giá trị của $n$:

II. Ứng dụng nghịch lý ngày sinh nhật trong mật mã học

Bài toán ngày sinh nhật thường được ứng dụng qua "tấn công va chạm", ý tưởng là chứng minh hoặc tìm kiếm yếu tố giống nhau trong một tập ngẫu nhiên $n$ yếu tố. Từ xác suất tồn tại hai thành phần giống nhau đó có thể xem xét việc thực hiện tấn công vét cạn tìm ra hai thành phần đó có khả thi hay không. Hoặc dựa vào nghịch lý này nhằm chọn ra một tập hợp hữu hạn các phần tử (thường có số lượng nhỏ) trong cài đặt thuật toán tấn công.

1. Tấn công va chạm (Collision Attack)

Một trong những ứng dụng quan trọng nhất của nghịch lý ngày sinh nhật trong mật mã học là tấn công va chạm (collision attack). Đây là một kỹ thuật nhằm khai thác khả năng xảy ra va chạm trong các hệ thống mã hóa, đặc biệt là trong các hàm băm mật mã.

Hàm băm và va chạm

• Một hàm băm mật mã $H(x)$ ánh xạ dữ liệu $x$ (với kích thước bất kỳ) thành một giá trị băm $h$ (có kích thước cố định).
• Ví dụ: Hàm băm SHA-256 sẽ ánh xạ dữ liệu bất kỳ thành một chuỗi 256-bit.
• Một va chạm xảy ra khi hai giá trị khác nhau $x_1 \neq x_2$ nhưng $H(x_1) = H(x_2)$.

Do nghịch lý ngày sinh nhật, xác suất xảy ra va chạm với một hàm băm có kích thước $k$-bit không phải là $2^k$ mà là xấp xỉ $2^{k/2}$. Điều này khiến cho việc tìm va chạm trở nên khả thi hơn dự kiến nếu không gian đầu ra của hàm băm không đủ lớn.

Chi phí tấn công va chạm

• Nếu không gian đầu ra của hàm băm có kích thước $k$-bit, thì:
  • Với tấn công vét cạn (brute force), chi phí để tìm một giá trị cụ thể là $2^k$.
  • Với tấn công va chạm dựa trên nghịch lý ngày sinh nhật, chi phí chỉ là $2^{k/2}$, tức là giảm đáng kể.

Ví dụ thực tế

• MD5: MD5 là một hàm băm 128-bit. Do nghịch lý ngày sinh nhật, chi phí tìm va chạm chỉ khoảng $2^{64}$, thấp hơn rất nhiều so với mức an toàn. MD5 đã bị phá vỡ bởi các tấn công va chạm.
• SHA-1: SHA-1 có kích thước đầu ra 160-bit. Chi phí tấn công va chạm là $2^{80}$, và SHA-1 cũng không còn được xem là an toàn trong mật mã hiện đại.

2. Birthday Attack

Tấn công ngày sinh nhật là một ứng dụng cụ thể của nghịch lý ngày sinh nhật, được sử dụng để tìm va chạm trong các hàm băm.

Ý tưởng

Giả sử chúng ta muốn tìm hai giá trị $x_1$ và $x_2$ sao cho $H(x_1) = H(x_2)$. Với nghịch lý ngày sinh nhật:

• Nếu hàm băm có đầu ra $k$-bit, cần sinh ngẫu nhiên khoảng $2^{k/2}$ giá trị $x$ để có xác suất cao tìm được một cặp va chạm.

Quy trình thực hiện tấn công

1. Sinh ngẫu nhiên một tập hợp các giá trị $x_1, x_2, \dots, x_n$.
2. Tính giá trị băm $H(x_1), H(x_2), \dots, H(x_n)$.
3. Kiểm tra xem có cặp nào $H(x_i) = H(x_j)$ với $i \neq j$. Nếu có, thì đã tìm thấy va chạm.

Ứng dụng của Birthday Attack

• Tấn công chữ ký số: Nếu một hệ thống chữ ký số dựa trên hàm băm, một kẻ tấn công có thể tìm hai thông điệp khác nhau $M_1$ và $M_2$ sao cho $H(M_1) = H(M_2)$. Kẻ tấn công có thể ký thông điệp hợp lệ $M_1$ và sau đó thay thế bằng thông điệp $M_2$.
• Phá vỡ tính toàn vẹn: Nếu va chạm xảy ra, kẻ tấn công có thể thay đổi nội dung dữ liệu mà không bị phát hiện.

Ví dụ minh họa

• Một hàm băm có kích thước đầu ra là 64-bit:
  • Với không gian đầu ra $2^{64}$, cần khoảng $2^{32}$ giá trị để có xác suất cao tìm được va chạm.
• Với một lớp học có 23 sinh viên, xác suất hai sinh viên trùng ngày sinh lớn hơn 50%. Tương tự, với $2^{32}$ giá trị băm, xác suất va chạm cũng lớn hơn 50%.

3. Ứng dụng trong thực tế

• Chứng minh tính an toàn của hàm băm: Nghịch lý ngày sinh nhật là cơ sở để xác định kích thước đầu ra tối thiểu của hàm băm mật mã. Để chống lại tấn công va chạm, một hàm băm phải có đầu ra ít nhất là 256-bit.
• Phân tích hiệu quả mã hóa: Trong thiết kế giao thức mật mã, nghịch lý ngày sinh nhật giúp ước lượng khả năng xảy ra xung đột hoặc trùng lặp khi chọn khóa, nonce hoặc số ngẫu nhiên.
• Bảo mật giao thức: Trong giao thức TLS (Transport Layer Security), nghịch lý ngày sinh nhật được xem xét để giảm khả năng trùng lặp mã định danh (Session ID) hoặc số thứ tự gói tin.

4. Bài học từ nghịch lý ngày sinh nhật

• Kích thước đầu ra của hàm băm phải đủ lớn: Ví dụ, với hàm băm SHA-256 (256-bit), chi phí tấn công va chạm sẽ là $2^{128}$, đủ an toàn trong thực tế.
• Tránh trùng lặp giá trị: Các giao thức phải đảm bảo rằng các giá trị quan trọng như khóa, nonce, hoặc ID không được tái sử dụng hoặc trùng lặp trong khoảng thời gian dài.

III. Tổng kết

Nghịch lý ngày sinh nhật, với xác suất cao xảy ra trùng lặp trong một tập hợp lớn, là một công cụ quan trọng để phân tích và tấn công các hệ thống mật mã. Các ứng dụng của nó, từ tấn công va chạm đến thiết kế hàm băm và giao thức an toàn, đã chỉ ra rằng kích thước không gian đầu ra của các hàm băm hoặc khóa cần được lựa chọn cẩn thận để đảm bảo an toàn. Trong thời đại mật mã hiện đại, nghịch lý này tiếp tục đóng vai trò quan trọng trong việc đánh giá và nâng cao bảo mật hệ thống.

Tài liệu tham khảo

• https://www.geeksforgeeks.org/birthday-attack-in-cryptography/
• https://math.columbia.edu/~goldfeld/BirthdayAttack.pdf