Bài giảng An ninh mạng - Chương 6: Hàm băm (Hash) - Trần Trung Dũng

Nội dung text: Bài giảng An ninh mạng - Chương 6: Hàm băm (Hash) - Trần Trung Dũng

1. Băm (Hash) Trần Trung Dũng
2. Chủ đề hôm nay • Hàm băm là gì? (hash function) • Các cách sử dụng hàm băm để xác thực • Tính một chiều, vấn đề đụng độ của hàm băm • Hàm băm đơn giản • Nghịch lý sinh nhật, tấn công sinh nhật • Họ hàm băm SHA
3. Hàm băm là gì? • Hàm băm nhận input là một chuỗi chiều dài không cố định, và output một chuỗi chiều dài cố định. • Output thường được gọi là: hash code, hash value, hoặc là message digest. • Hàm băm SHA-512 nhận input chiều dài <= 2128 bit và output MD (message digest) chiều dài 512 bit. SHA = secure hash algorithm.
4. • Message: "A hungry brown fox jumped over a lazy dog" • SHA1 hash code: a8e7038cf5042232ce4a2f582640f2aa5caf12d2 • Message: "A hungry brown fox jumped over a lazy dog" • SHA1 hash code: d617ba80a8bc883c1c3870af12a516c4a30f8fda • Chỉ một khác biệt nhỏ trong chuỗi input hash code khác nhau hoàn toàn khó bị tấn công
5. Các cách sử dụng băm Hình 1
6. Hình 1
7. Hình 1
8. Hình 2
9. Hình 2
10. Hình 2
11. Thế nào là một hàm băm an toàn! • Không khả thi để tìm được thông điệp tương ứng với 1 hash code. Đây là tính một chiều (one-way function) • Không khả thi để tìm được hai thông điệp cho ra chung một hash code. Chống đụng độ (strong collision resistance) • Một hàm hash mà tính đụng độ không tốt dễ bị tấn công sinh nhật
12. Góc nhìn xác suất • Message x hash code là h(x) • Xét k messages • Với k bằng bao nhiêu thì tồn tại ít nhất một message y: xác suất h(y) = h(x) là 0.5 • Để tìm k, chúng ta giả sử hash code ϵ {1, ,N} • Cho trước h(x), P(h(y) = h(x)) = 1/N. • P(h(y) != h(x)) = 1- 1/N. • Xác suất không có một message nào trong k messages có hash code trùng với h(x) là : (1-1/N)k.
13. • Vậy xác suất có ít nhất một trong k messages có hash code trùng với h(x) là: 1- (1- 1/N)k (*) • Nếu a 0 thì (1+a)n ≈ 1+an • (*) tương đương ≈ 1 – (1 – k/N) = k/N • Vậy, nếu có k messages ngẫu nhiên, thì xác suất tồn tại ít nhất một message trùng hash code với h(x) là k/N. • Để tồn tại ít nhất một message có hash code trùng với h(x) với xác suất là 0.5 là: k/N = 0.5 hay k = 0.5N. • Nếu hash code dài 64 bit thì chúng ta cần tạo 263 messages để tồn tại ít nhất một msg có hash code trùng với h(x) với xs là 0.5.
14. Xác suất để tồn tại một cặp message có cùng hash code? • Cho k messages 1. Xác suất tồn tại msg nào đó trong k messages có hash code bằng với một giá trị cụ thể h(x). 2. Xác suất tồn tại một cặp messages có cùng hash code. • Hai xác suất này bằng nhau hay khác nhau!
15. • Lớp của bạn có 20 học sinh, xác suất tồn tại một bạn cùng ngày sinh với bạn là bao nhiêu. ~ 19/365 • Xác suất để tồn tại ít nhất hai bạn nào đó trong lớp có sinh nhật cùng ngày 19 18/ 2 171 365 365 • Nếu có k msg và hash code ϵ {1, ,N} thì xác suất tồn tại hai msg cùng hash code là: N! 1 (N k)!N k
16. • Gọi M1 là số cách tạo ra k msg không có trùng hash code • M2 là tổng số cách tạo ra k msg, cho phép trùng hash code • M1/M2 là xác suất tạo ra k msg không bị trùng hash code • Có N là tổng số hash code chúng ta chọn k msg có hash code khác nhau . • Msg đầu tiên chọn tùy ý trong N, msg thứ 2 chọn tùy ý trong N-1, • M1 = N x (N-1) x x (N-k+1) = N!/(N-k)! • M2 = N x N x x N = Nk • Xác suất tồn tai hai msg cùng hash code: 1- M1/M2 N! 1 (N k)!N k
17. N! 1 (N k)!N k Áp dụng
18. k(k 1) 1 e 2N Xác suất để k msg tồn tại ít nhất một cặp msg có cùng hash code luôn lớn hơn biểu thức trên Để tìm k sao cho tồn tại ít nhất một cặp msg cùng hash code với xác suất 0.5 nghĩa là giải k từ đẳng thức k(k 1) 1 e 2N 0.5 k(k 1) e 2N 2
19. • Vì vậy k(k 1) ln 2 2N • Giả sử k lớn k(k-1) (2ln 2)N k 2 (2ln 2)N k (2ln 2)N 1.18 N N
20. • Nếu n-bit hash code thì N = 2n. • Vậy cần tạo 2n/2 msg thì sẽ tồn tại một cặp msg có cùng hash code với xác suất 0.5 • Với trường hợp 64-bit hash code thì chúng ta cần tạo 232 msg ngẫu nhiên để tồn tại một cặp msg có cùng giá trị hash code.
21. Tấn công “sinh nhật” • Ngữ cảnh: ông chủ A nhờ trợ lý “bất tín” B soạn một hợp đồng • B soạn một hợp đồng hợp pháp, sau đó tạo ra k bản hợp pháp khác. Bằng cách thêm khoảng trắng, dấu phẩy, trạng từ, kí hiệu k bản hợp đồng hợp pháp: {c1,c2, ,ck} • B soạn một hợp đồng giả. Và cũng tạo ra k bản giả. Kí hiệu {f1,f2, ,fk} • Chúng ta cần tìm xác suất để tồn tại một cặp (ci,fj) sao cho h(ci) = h(fi)
22. • Giả thiết tất cả các hợp đồng giả đều tạo hash code ngẫu nhiên. • Xác suất hash code h(c1) trùng với hash code h(f1) là 1/N. Xác suất h(c1) khác h(f1) là 1-1/N. k • Xác suất h(c1) khác tất cả {h(f1), h(f2), ,h(fk)} là (1-1/N) k 2 • Xác suất tất cả {h(ci)} khác tất cả {h(fi)}: 1 1 N • Đây là xác suất để không tồn tại một cặp {ci,fj} nào trùng hash code
23. • Nghĩa là xác suất có tồn tại 1 cặp {ci,fj} cùng hash code là k 2 1 1 1 (*) N 2 1 1 k 1 N N vì 1- e nên (*) 1 e N • k = ? để xác suất trên là 0.5 k 2 1 e N 0.5 k (ln 2)N 0.83 N N
24. Cấu trúc hàm băm • Hầu hết hàm băm dựa trên cấu trúc do Merkle đề xuất.
25. Họ hàm băm SHA • SHA : Secure Hash Algorithm • Hàm băm được sử dụng phổ biến nhất trong họ SHA là SHA-1 • SHA-1 được sử dụng trong SSL/TLS, PGP, SSH, S/MIME và IPSec.
26. • Message size: chiều dài tối đa của msg mà hàm băm có thể xử lý • Block size: số bit trong mỗi block (cấu trúc hàm băm Merkle) • Word size: đc sử dụng trong quá trình xử lý input block • Message Digest Size: kích thước của ouput hash code • Security: tổng số msg cần tạo ra cho đến khi tồn tại 2 msg có cùng hash code với xác suất 0.5
27. • SHA-2: đại diện cho SHA-256, SHA-384, SHA-512 • SHA-1: là hậu duệ của MD5 (từng đc sử dụng rộng rãi) • SHA-1: bị bẻ khóa năm 2005, nhóm tác giả chỉ ra chỉ cần 269 (<< 280) phép thử. • NIST rút lại bảng chứng nhận an toàn SHA-1 năm ngoái (2010)
28. SHA-512
29. • Mỗi block 1024-bit, Mi, sẽ được thông qua 80 vòng xử lý (hình trên) • 80 words 64-bit được dùng cho mỗi vòng đc tạo như sau. 16 words đầu lấy từ 1024 bit của Mi, sau đó
30. • Đồ án 3. lập trình thuật SHA-512 • Hạn cuối: 23:55pm 28-4-2011
31. Hàm băm tạo Message Authentication Codes • Hash code là một chữ kí của thông điệp gọi Message Authentication Code (MAC) • Gọi MAC = C(K,M) là hàm tạo ra MAC bằng khóa K • Sau đây là ví dụ hàm tạo MAC không an toàn • M = X1 || X2 || || Xm (||: kết nối 2 chuỗi) • ∆(M) = X1 ⊕ X2 ⊕ ・ ・ ・ ⊕ Xm • C(K, M) = E(K, ∆(M)). Ví dụ hàm E() là thuật toán DES. • Giả sử người tấn công biết {M, C(K,M)}
32. • Người tấn công tạo ra msg Y = Y1 || || Ym • Trong đó Y1, Ym-1 là tùy ý • Ym = Y1 ⊕ Y2 ⊕ ・ ・ ・ ⊕ Ym−1 ⊕ ∆(M) • Mgiả = {Y1||Y2|| ・ ・ ・ ||Ym} • gửi {Mgiả, C(K,M)} • Tại sao ở đầu nhận không phát hiện được nội dung X1, ,Xn đã bị thay thế ?
33. • Phương thức để tạo MAC hay sử dụng là HMAC. • Kích thước của MAC được tạo từ HMAC cũng bằng với kích thước của hash code được tạo từ SHA-1 • Thuật toán HMAC được mô tả trong hình bên dưới
34. • K+ là khóa K được chèn thêm 0 bên trái để đủ b-bit. • b là số bit mỗi block • ipad: chuỗi 001101100 được lặp lại b/8 lần • opad: chuỗi 01011100 được lặp lại b/8 lần
35. Chữkí số: Thuật toán ElGamal • Chữ kí số là để đảm bảo tính toàn vẹn của văn bản • Để tạo chữ kí cho một văn bản, chúng ta phải tạo cặp khóa: public key – private key. Các bước ElGamal như sau: • Chọn số nguyên tố lớn p, sau đó chọn a và PR nhỏ hơn p. Công bố p và a, giữ PR như là private key • Tính public key: PU = aPR mod p • PU cũng được công bố (cùng với a, p) • Thêm vào đó cần có 1 số ngẫu nhiên K nguyên tố cùng nhau với p, chỉ dùng một lần. Dù sử dụng 1 lần nhưng K phải giữ bí mật, ngược lại sẽ dễ đoán được private key PR.
36. • Gọi M là số nguyên đại diện cho tài liệu chúng ta muốn kí lên. • Chữ kí số cho M sẽ gồm hai phần sig1 và sig2. . sig1 = aK mod p . M = (PR x sig1 + K x sig2) mod (p-1) (giải tìm sig2) • Bên gửi sẽ gửi M và (sig1,sig2) làm chữ kí. • Bên nhận sẽ xác thực tính toàn vẹn của M bằng cách kiểm tra: PU x sig1sig2 mod p = aM mod p (1) • Chứng minh (1): bài tập về nhà
37. Bên lề • Tiến sĩ Taher ElGamal đóng vai trò chính trong việc phát triển giao thức SSL (Secure Socket Layer), khi ông còn là trưởng bộ phận nghiên cứu trong Nestcape Communications cuối 1990’s. SSL (cùng người em họ TLS – Transport Layer Security) là nền tảng bảo mật cho rất nhiều giao thức khác.