Tấn công Ngày sinh là một loại tấn công mật mã dựa trên sự khai thác vấn đề Ngày sinh(Birthday problem)- một hiện tượng xác suất tạo ra nghịch lý đối với cảm giác của con người, do vậy còn được gọi là “Nghịch lý Ngày sinh”(Birthday paradox).
Bài này phân tích và chứng minh hiện tượng nghịch lý trên cùng với mối liên hệ ứng dụng mật mã trong tấn công/phòng vệ tấn công. Cuối bài là một chương trình với mã nguồn thực thi, kèm theo các giải thích cần thiết. Kiến thức trong bài phần lớn là những kiến thức phổ thông cho nên các bạn sẽ hiểu được dễ dàng, chỉ cần tốt nghiệp phổ thông trung học(bằng thật, học thật). Bạn sẽ gặp thuận lợi đối với một vài chi tiết khác nếu bạn có trình độ tin học căn bản. Về phần chương trình thì bạn cần biết sơ qua về ngôn ngữ C++; sử dụng một hệ điều hành kiểu Linux có trình biên dịch gcc.
Bài này cũng là cơ sở cho các khái niệm có thể gặp trong các bài sau có liên quan đến các vấn đề bí mật thông tin, các thuật toán mật mã, thuật toán mật mã không an toàn, tấn công tiền ảnh, tấn công tiền ảnh thứ hai, tấn công xung đột mạnh, chiến lược tìm kiếm, kỹ thuật mật mã khóa công khai, thực hành mã hóa và giải mã thông tin, thực hành ký kỹ thuật số, thực hành xác minh chữ ký kỹ thuật số, thực hành xác nhận các chứng chỉ CA-Certificates và loại bỏ các chứng chỉ không hợp lệ.
Nếu bạn đang ở trong một nhóm người ngẫu nhiên trong một căn phòng với số người lớn hơn con số 23, bạn có thể cá cược với ai đó rằng có ít nhất một cặp hai người nào đó có trùng ngày sinh, và phần thắng sẽ nghiêng về bạn. Một năm không kể năm nhuận là có 365 ngày vì thế có 365 ngày sinh khác nhau, một con số lớn hơn nhiều so với 23 làm cho chúng ta có cảm giác đây là điều nghịch lý. Nhưng lý thuyết xác suất thống kê đã chỉ ra rằng với 23 người ngẫu nhiên thì xác suất có ít nhất hai người có trùng ngày sinh là 50%.
Gọi xác suất cần tính là P(A). Chúng ta giải bài toán ngược lại, tìm xác suất P(A’) để 23 người ngẫu nhiên có ngày sinh hoàn toàn khác nhau.
Vì mỗi một người đều có thể có ngày sinh là một ngày trong 365 ngày của năm nên số khả năng về tình trạng ngày sinh của 23 người sẽ là chỉnh hợp lặp chập 23 của 365 phần tử
Số khả năng thuận lợi là số bộ 23 ngày sinh mà không có cặp hai ngày sinh nào trùng nhau, đây chính là chỉnh hợp(không lặp) chập 23 của 365 phần tử
Vậy xác suất P(A’), từ đó xác suất P(A) sẽ bằng
Công thức tổng quát cho n người, xác suất p(n) để có ít nhất hai người trong n người ngẫu nhiên trùng ngày sinh sẽ là
(*)
Để thử kết quả, bạn dùng một tiện ích tính toán. 365! là một số rất lớn, có đến 778 chữ số 0, một chương trình tính toán bình thường không tính được. Bạn chạy chương trình kcalc, vào menu Settings, chọn chế độ khoa học(Science Mode)
Với n=70 chúng ta sẽ được kết quả p(70) xấp xỉ 99.9%. Như vậy, với 70 người ngẫu nhiên, hầu như chắc chắn có ít nhất hai người có ngày sinh giống nhau.
Tính toán xấp xỉ
Công thức (*) là công thức tính toán chính xác. Khi áp dụng vào mật mã, số ngày 365 ngày trong năm sẽ được thay thế bằng kích thước không gian mật mã, là số chuỗi nhị phân khác nhau với một độ dài chuỗi nhất định. Ví dụ với chuỗi nhị phân dài 32 bits, con số này là 2³², hơn 4 tỷ. Tính toán con số lớn như vậy sử dụng trực tiếp công thức (*) là không khả thi thực hành. Cho nên cần phương pháp xấp xỉ. Từ công thức (*), xác suất để n người ngẫu nhiên có ngày sinh hoàn toàn khác nhau là
(**)
Khai triển Taylor áp dụng cho x tại lận cận điểm 0, |x| << 1
Với x=-1/365
Với x=-2/365
Lặp lại tương tự cho đến x=-(n-1)/365
Thay các giá trị gần đúng vế trái vào công thức (**)
Từ đó chúng ta có công thức tính gần đúng xác suất p(n). Áp dụng vấn đề Ngày sinh vào các hiện tượng tương tự, “số ngày” không phải là 365 mà là một biến d. Với cách đặt vấn đề sử dụng khai triển Taylor nói trên khi đặt các giá trị x, phương pháp gần đúng này chỉ đạt độ chính xác với các x gần điểm 0, hay trị tuyệt đối của x nhỏ hơn 1 rất nhiều. Nói cách khác, khi n << d thì có thể áp dụng công thức
Hàm xác suất(gần đúng) là một hàm theo “số người” n và “số ngày” d.
Để tính n theo p và d, chúng ta biến đổi công thức trên
(***)
Cùng ngày sinh như bạn(Same birthday as you)
Nếu bạn bước vào một phòng có ngẫu nhiên n người, xác suất q(n) để có một ai đó trong phòng có cùng ngày sinh với bạn là một dạng khác của vấn đề Ngày sinh- xác suất có ít nhất một ngày sinh trong n ngày sinh ngẫu nhiên trùng với một ngày sinh cho trước. Tổng số khả năng có thể xảy ra đối với n ngày sinh này vẫn là
Chúng ta lại làm bài toán ngược: tìm xác suất để không có ai trong n người này có ngày sinh như bạn. Về số khả năng thuận lợi, vì mỗi người đều có thể có ngày sinh trong năm trừ ngày sinh của bạn nên số khả năng thuận lợi của bộ n ngày sinh này là chỉnh hợp lặp chập n của (365-1) phần tử, bằng
Vậy
Với n=23 thì tính ra q(n) khoảng 6.1%, nhỏ hơn p(n) tương ứng là 50% rất nhiều. Lý do là trong 23 người này có thể có một hoặc nhiều cặp trùng ngày sinh nhưng họ lại khó trùng ngày sinh với bạn. Cũng vì lý do này mà để xác suất q(n) đạt 50% thì số người n phải là 253 > 365/2.
Tổng quát cho d “ngày”, xác suất là một hàm theo “số người” và “số ngày”
Bảng xác suất
| Số bits | Cỡ không gian băm (2Số bits) |
Xác suất xảy ra xung đột (p) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 10−18 | 10−15 | 10−12 | 10−9 | 10−6 | 0.1% | 1% | 25% | 50% | 75% | ||
| 16 | 65,536 | <2 | <2 | <2 | <2 | <2 | 11 | 36 | 190 | 300 | 430 |
| 32 | 4.3 × 109 | <2 | <2 | <2 | 3 | 93 | 2900 | 9300 | 50,000 | 77,000 | 110,000 |
| 64 | 1.8 × 1019 | 6 | 190 | 6100 | 190,000 | 6,100,000 | 1.9 × 108 | 6.1 × 108 | 3.3 × 109 | 5.1 × 109 | 7.2 × 109 |
| 128 | 3.4 × 1038 | 2.6 × 1010 | 8.2 × 1011 | 2.6 × 1013 | 8.2 × 1014 | 2.6 × 1016 | 8.3 × 1017 | 2.6 × 1018 | 1.4 × 1019 | 2.2 × 1019 | 3.1 × 1019 |
| 256 | 1.2 × 1077 | 4.8 × 1029 | 1.5 × 1031 | 4.8 × 1032 | 1.5 × 1034 | 4.8 × 1035 | 1.5 × 1037 | 4.8 × 1037 | 2.6 × 1038 | 4.0 × 1038 | 5.7 × 1038 |
| 384 | 3.9 × 10115 | 8.9 × 1048 | 2.8 × 1050 | 8.9 × 1051 | 2.8 × 1053 | 8.9 × 1054 | 2.8 × 1056 | 8.9 × 1056 | 4.8 × 1057 | 7.4 × 1057 | 1.0 × 1058 |
| 512 | 1.3 × 10154 | 1.6 × 1068 | 5.2 × 1069 | 1.6 × 1071 | 5.2 × 1072 | 1.6 × 1074 | 5.2 × 1075 | 1.6 × 1076 | 8.8 × 1076 | 1.4 × 1077 | 1.9 × 1077 |
Đây là bảng xác suất mật mã đưa ra các giá trị khung. Các ô màu trắng biểu thị số lượng giá trị băm( hashes) cần thiết để tấn công phá vỡ kháng xung đột mạnh với xác suất tương ứng theo cột và kích thước không gian băm theo hàng. “Kích thước không gian băm” ứng với “số ngày d”, “xác suất xung đột” ứng với “xác suất trùng ngày sinh”, và “số băm cần thiết” ứng với “số người n”.
Chương trình
Chương trình áp dụng công thức (***) để tính số băm cho các trường hợp xác suất nhỏ. Đối với các xác suất lớn xa điểm 0 thì công thức xấp xỉ sẽ gặp sai số, khi đó một hàm nội suy đa thức cho các giá trị khung trong bảng xác suất bên trên sẽ được sử dụng thay thế. Đó là hàm LookAyken.
-
birthday.cc
#include <cmath> #include <cstdlib> #include <iostream> /* This file is available at https://phamtyn.wordpress.com/mess */ #include "lookayken.h" double probabilityArr[]={0.1, 1, 25, 50, 75}; double bitLenArr[]={16,32,64,128,256,384,512}; double hashTable[5][7]={{11, 2900, 1.9*pow(10,8), 8.3*pow(10,17), 1.5*pow(10,37), 2.8*pow(10,56), 5.2*pow(10,75)}, {36, 9300, 6.1*pow(10,8), 2.6*pow(10,18), 4.8*pow(10,37), 8.9*pow(10,56), 1.6*pow(10,76)}, {190, 50000, 3.3*pow(10,9), 1.4*pow(10,19), 2.6*pow(10,38), 4.8*pow(10,57), 8.8*pow(10,76)}, {300, 77000, 5.1*pow(10,9), 2.2*pow(10,19), 4.0*pow(10,38), 7.4*pow(10,57), 1.4*pow(10,77)}, {430, 110000, 7.2*pow(10,9), 3.1*pow(10,19), 5.7*pow(10,38), 1.0*pow(10,58), 1.9*pow(10,77)}}; int main(int argc, char ** argv) { if (argc != 3) { std::cerr << "Usage: " << argv[0] << " probability-exponent/probability bits" << std::endl; return 1; } long probabilityExponent = strtol(argv[1], NULL, 10); long bits = strtol(argv[2], NULL, 10); double probability; if(probabilityExponent<0) { probability = pow(10, probabilityExponent); double outputs = pow(2, bits); std::cout << sqrt(2.0 * outputs * -log1p(-probability)) << std::endl; } else { switch(bits){ case 16: case 32: case 64: case 128: case 256: case 384: case 512: { probability = strtod(argv[1], NULL); int i; double hashRow[5]; for(i=0; i<5; i++) hashRow[i]=LookAyken(bits,bitLenArr,hashTable[i],7); double hashnum=LookAyken(probability, probabilityArr, hashRow, 5); std::cout << hashnum << std::endl; } break; default: std::cerr << "Usage: bits must be one of 16, 32, 64, 128, 256, 384, 512" << std::endl; break; } } return 0; }
- Biên dịch
Để tạo chương trình nhị phân, bạn làm như sau: tải về tệp tiêu đề “lookayken.h” trong tab “Mess” của site này, đặt nó vào thư mục hiện hành; sau đó tạo birthday.cc với nội dung trên. Biên dịch như sau:
g++ -o birthday birthday.cc
- Chạy chương trình
./birthday -15 128 8.24963e+11 ./birthday 1 32 9300 ./birthday 40 384 5.42285e+57 ./birthday 0.5 256 3.00578e+37 ./birthday 0.1 512 5.2e+75
Artificial Intelligence Kiosk 