Bài giảng An ninh mạng - Chương 3: Ứng dụng block cipher + stream cipher trong thực tế - Trần Trung Dũng

Nội dung text: Bài giảng An ninh mạng - Chương 3: Ứng dụng block cipher + stream cipher trong thực tế - Trần Trung Dũng

1. Ứng dụng block cipher + stream cipher trong thực tế TS. Trần Trung Dũng
2. Mục tiêu bài giảng • 2DES và nguy cơ tấn công meet-in-the-middle • 3DES với hai khóa và nguy hiểm tiềm tàng • 3DES với ba khóa • Các phương thức ứng dụng block cipher trong thực tế • Stream cipher và RC4 stream cipher • Vấn đề của giao thức WEP của mạng không dây gia đình
3. Sử dụng nhiều lần DES • Mã hóa DES không còn an toàn từ hơn mười năm trước (1999) • Mã hóa AES ra đời để thay thế, nhưng cộng đồng tài chính-thương mại vẫn chưa muốn thay thế. (Vì tốn kém đầu tư lại phần mềm + phần cứng) • Câu hỏi đặt ra: liệu mã hóa bằng cách sử dụng nhiều lần DES có an toàn hơn không? • Chúng tôi sẽ chỉ ra double DES không tăng thêm tính an toàn
4. Double DES • Cơ bản: mã hóa DES hai lần và sử dụng hai khóa khác nhau • Gọi P là 64-bit plaintext, E là quá trình mã hóa, K1 và K2 khóa 56-bit. C là ciphertext, thì C = E(K2, E(K1, P)) P = D(K1, D(K2, C)) • Với hai khóa nghĩa là sử dụng khóa với 112-bit. Như vậy có thể chống lại tấn công brute-force
5. Liệu double-DES có tương đồng với một single-DES nào đó không? • Nghĩa là có tồn tại khóa K3 nào đó thỏa: E(K2, E(K1, P)) = E(K3, P) nếu tồn tại K3 thì ý tưởng double-DES không dùng được! • Ơn trời, xác suất sử dụng hai khóa cho ra 1 kết quả trùng với sử dụng một khóa K3 nào đó là rất nhỏ.
6. • Xét 4-bit block. Mỗi khóa phải tạo ra 1 ánh xạ duy nhất giữa input plaintext và output ciphertext. (Nếu không thì không giải mã được) • Như vậy với 4-bit block input cho ra 4-bit output, • Mỗi 4 bit có thể biểu diễn 16 giá trị khác nhau, • chúng ta có thể tạo ra 16! ánh xạ khác nhau (=24!)
7. • Vậy 64-bit block thì sẽ có 264! cách ánh xạ (264 )!= 1034738000000000000000 20 1010 • Khóa 56bit có 256 khóa khác nhau • 256 < 1017 • Mỗi khóa tương ứng với 1 ánh xạ. Nên tổng số ánh xạ có thể được tạo từ 1 DES là rất nhỏ so với tổng số ánh xạ có thể từ plaintext ciphertext • Vì vậy xác suất mã hai lần DES với hai khóa sẽ trùng với mã một lần bằng một khóa khác là rất nhỏ
8. Điểm yếu của double-DES, tấn công meet-in-the-middle • Nhắc lại C = E(K2, E(K1, P)) P = D(K1, D(K2, C)) • Attacker biết được cặp (P, C) • Tồn tại X sao cho X = E(K1, P) = D(K2, C)
9. • Attacker tạo bảng chứa tất cả các giá trị có thể của X 56 khi biết trước P (thử hết 2 khóa). Kí hiệu bảng TE. • Attacket tạo một bảng khác chứa tất cả giá trị có thể của X’ bằng cách giải mã C bằng 256 khóa có thể. 56 Bảng này cũng chứa 2 phần tử. Gọi bảng này là TD. • Có bao nhiêu phần tử X trong TE giống với X’ trong TD. Lý tưởng, chỉ có duy nhất một X trong TE trùng với một X’ duy nhất trong TD. • Thực tế chúng ta sẽ thấy số lượng trùng rất lớn. Chúng ta gọi số này là false alarms.
10. • Input 64-bit block cho ra 264 giá trị output 64bit khác nhau • Khóa 112 bit 2112 khóa • 2112 khóa chỉ cho ra 264 output khác nhau nên 2112/264 = 248 48 112 • Trung bình, 2 cặp trong 2 cặp khóa (K1,K2) sẽ mã hóa 64- bit plaintext cho ra chung một 64-bit output ciphertext C. 56 56 • Vì vậy khi so sánh 2 phần tử trong TE với 2 phần tử trong 48 TD, chúng ta sẽ có (2 -1 ) false alarms
11. • Giả sử chúng ta có 1 cặp (P’,C’). Thì lần này chỉ cần thử với 248 cặp khóa báo trùng. • Vì tổng số ánh xạ có thể là 256 • Trong khi đó chỉ thử 248 ánh xạ, nên số cặp khóa sẽ cho ra cùng chung ciphertext C là 248/264 = 2-16. • Nghĩa là chắc chắn tìm được cặp khóa (K1, K2) của double-DES • Số tính toán phải làm (duyệt bảng 256 phần tử) cũng tương đương số tính toán để giải mã single-DES
12. Triple-DES dùng 2 khóa • Cách trực quan là C = E(K3, E (K2, E (K1, P))) nghĩa là sử dụng khóa168bit (3 khóa khác nhau) nhưng không được sử dụng nhiều trong các ứng dụng. Được sử dụng trong PGP và S/MIME • Cách khác của Triple-DES là sử dụng 2 khóa C = E(K1, D(K2, E (K1, P))) • Chú ý là bước đầu tiên là encryption, rồi đến decryption, rồi đến encryption.
13. • Giải pháp này được sử dụng vì sự tương thích ngược với với DES đã có • Chú ý rằng quá trình decryption cũng giống hệt encryption, nhưng sử dụng với khóa khác. Nên sau bước encyption rồi decryption thì vẫn là một chuỗi đã mã hóa. • Triple-DES sử dụng 2 khóa khá phổ biến để thay cho DES
14. Tấn công 3DES trên 2 khóa • Về lý thuyết, có thể sử dụng tấn công meet-in-the-middle mở rộng C = E(K1, D(K2, E (K1, P))) • Có thể viết lại A = E(K1, P) B = D(K2, A) C = E (K1, B) Chi tiết ý tưởng: bài tập về nhà
15. Sử dụng block ciphers • DES mã hóa các khối 64bit. Việc mã hóa này áp dụng ntn cho toàn văn bản? • Phương thức đơn giản nhất: Electronic Code Book (ECB) – Chia plaintext thành các blocks 64 bit – Mã hóa các block riêng biệt, sử dụng chung 1 khóa – Giải mã cũng vậy: sử dụng chung khóa cho các block.
16. Modes: Cipher Block Chain (CBC) • CBC: tránh sự lặp lại ở mức độ block • Block kế tiếp (plaintext) được XOR với block trước đó (ciphertext) rồi mới được mã hóa • Sử dụng chung khóa cho các block • Block đầu tiên: sử dụng vector khởi tạo (IV- Initialization Vector) • Sự lặp lại của plaintext sẽ bị mất dấu trong ciphertext
17. Modes: Cipher FeedBack (CFB) • Chia dữ liệu thành các block nhỏ (1 byte cho mỗi block). Giống stream cipher. • Vector khởi tạo (IV) có chiều dài bằng chiều dài khối thông thường. • Mã hóa IV bằng thuật toán mã hóa khối • Sau đó giữ lại 1 byte bên trái nhất, còn lại bỏ • XOR byte này với 1 byte trong plaintext 1 byte ciphertext
18. • Shift vector khởi tạo (IV) 1 byte về bên trái. • Lấy byte mới mã hóa xong gán vào bên phải IV, tạo ra 1 IV đầy đủ mới • Quay lại bước mã hóa IV bằng thuật toán mã hóa khối • Nhận xét: – Một byte bất kì đều bị ảnh hưởng bởi tất cả các byte trước đó
19. Modes: Output FeedBack (OFB) • Tương tự CFB, sử dụng giống stream cipher • Khác biệt duy nhất là lấy 1 byte từ kết quả mã hóa IV để thêm vào bên phải của IV ở bước kế tiếp • Xem hình trang kế • Trong CFB, nếu ttrong quá trình truyền mà byte đầu tiên bị lỗi vài bit, sẽ ảnh hưởng đến quá trình giải mã của cả văn bản
20. Modes: The Counter
21. The Counter • Mã hóa các khối riêng biệt mã hóa song song • Tiền xử lý: tạo sẳn các khóa dễ dàng nhanh. (khác CFB, OFB) • Cũng an toàn như các cách mã hóa trên
22. Stream cipher • Các slide trước có nhắc đến stream cipher. Bây giờ là chi tiết • Thông thường mã hóa stream sẽ mã hóa từng byte một • Khi có một byte mới từ plaintext thì cũng sẽ có 1 byte ngẫu nhiên tương ứng đến từ khóa. • Hai byte này được XOR với nhau để tạo ciphertext • Chuỗi các byte của khóa được phát ngẫu nhiên, tuy nhiên phải theo qui luật để ở đầu nhận có thể giải mã được • Khóa càng dài chuỗi byte ngẫu nhiên càng dài an toàn
23. • Ngày nay, khóa an toàn cần ít nhất 128 bit • Với hàm phát sinh byte ngẫu nhiên thích hợp thì stream cipher cũng an toàn như block cipher nếu cả hai sử dụng khóa cùng chiều dài. • Stream cipher phù hợp cho các ứng dụng truyền âm thanh, video, dữ liệu web thông dụng. • Block cipher thích hợp hơn cho việc truyền files
24. Thuật toán stream cipher: RC4 • Chìa khóa của stream cipher là bộ phát sinh chuỗi byte ngẫu nhiên • Nền tảng, RC4 sử dụng chuỗi 256 byte. Gọi là state vector, kí hiệu S • State vector được khởi tạo như sau: S[0] = 0x00 = 0 S[1] = 0x01 = 1 S[255] = 0xFF = 255
25. • State vector được khởi tạo thông qua vector tạm T chứa 256 phần tử số nguyên. • Gọi khóa là K, dài 128-bit. K sẽ chứa 16 số nguyên không âm giữa 0 – 255 • Vector T được khởi tạo như sau: T[i] = K[i mod keylen] 0 ≤ i ≤ 255 trong đó keylen là số byte trong khóa.
26. • Chúng ta sử dụng vector tạm T (256 phần tử) để tạo hóan vị đầu tiên của S. j = 0 for i = 0 to 255 j = (j + S[i] + T[i]) mod 256 SWAP S[i], S[j] Thuật toán này được gọi Key Scheduling Algorithm (KSA) • Vector tạm T không sử dụng lại nữa • Chú ý khóa K cũng chỉ được sử dụng ở bước khởi tạo của state vector S.
27. • Chú ý rằng, bước khởi tạo của S cũng chỉ là tạo ra một hoán vị nào đó giữa tập số nguyên từ 0-255, tùy theo khóa K, để cho ra state vector S mới. • Thủ tục sau phát sinh ra byte ngẫu nhiên, để XOR với 1 byte của plaintext i, j = 0 while ( true ) i = ( i + 1 ) mod 256 j = ( j + S[i] ) mod 256 SWAP S[i], S[j] t = ( S[i] + S[j] ) mod 256 k = S[t] output k
28. • Thủ tục trên trả về byte ngẫu nhiên lưu trong biến k. Byte này được XOR với byte plaintext để tạo byte mã hóa. • Chuỗi phát sinh từ thủ tục trên gọi là keystream • Về lý thuyết, với khóa 128 bit thì chu kz lặp lại của chuỗi byte ngẫu nhiên > 10100. • RC4 được sử dụng trong SSL/TLS (Secure Socket Layer / Transport Layer Security) chuẩn an toàn trong ứng dụng web. • RC4 cũng được sử dụng trong giao thức WEP (Wired Equivalent Privacy) và giao thức mới hơn Wifi Protected Access (WPA) là 1 phần trong chuẩn LAN không dây 802.11
29. Điểm mạnh và yếu của stream cipher RC4 • Đơn giản là điều đáng giá nhất • Các thao tác ở mức byte, quá trình mã hóa nhanh RC4 sử dụng rộng rãi. • Trong bài báo “Weaknesses in the Key Scheduling Algorithm of RC4 ” của Fluhrer, Mantin, và Shamir đã chỉ ra nhiều điểm yếu.
30. Vấn đề của WEP • Giao thức WEP mã hóa các gói tin riêng biệt nhau. • RC4 key cho mỗi gói tin là chuỗi kết hợp giữa 24-bit Initialization Vector (IV) và root key (mật mã bạn đã nhập để bảo vệ wireless router). • WEP tính CRC32 checksum của dữ liệu (Cyclic Redundancy Check). Trong WEP thì CRC32 được gọi Integrity Check Value (ICV) • Gói tin + ICV được mã hóa bằng RC4
31. • Vấn đề lớn nhất của WEP là root key không thay đổi khá lâu • IV chỉ có 24 bit • Suy ra số keystream phân biệt có thể tạo là 224. • số gói tin lớn sẽ bị lặp lại khóa • Nếu cùng keystream S sử dụng hai gói tin P1 và P2 thì XOR của 2 ciphertext độc lập với keystream S. C1 ⊕ C2 = (P1 ⊕ S) ⊕ (P2 ⊕ S) = P1 ⊕ P2
32. • 24 bit của IV được gửi dưới dạng plaintext, nên một frame 802.11 được mã hóa bằng WEP như sau:
33. • Bài báo “Breaking 104 bit WEP in less than 60 seconds,” của Tews, Weinmann, and Pyshkin chỉ ra cách 1 attacker có thể tìm ra các byte còn lại trong RC4 key. • Chú ý, WPA cũng sử dụng RC4 tuy nhiên WPA cải tiến tính an toàn bằng cách sử dụng 48-bit Initialization Vector. Thêm vào đó WPA băm IV trước khi kết hợp nó với root key.
34. Ôn tập • Ứng dụng Internet nào sử dụng 3DES với 3 khóa • Ứng dụng nào sử dụng RC4 • Tại sao WEP không an toàn. • Cải tiến nào của WPA giúp nó an toàn
35. Đồ Án • Đồ án 1: viết chương trình phá khóa WEP 104 bit dựa vào bài báo của Tews et al. (4 điểm). Hạn cuối 11:55pm 1-4-2011. • Đồ án 2: viết chương trình mã hóa và giải mã một file âm thanh theo chuẩn .wav sử dụng khóa (16 kí tự ASCII) được nhập từ bàn phím theo phương pháp keystream RC4. Sau đó nghe lại file âm thanh đã mã hóa và file giải mã để kiểm tra tính đúng đắn của thuật toán mã hóa và giải mã. (1.5 điểm). Hạn cuối 11:55pm 15-03-2011. Chú ý: Không được dùng các hàm thư viện có sẳn về mã hóa RC4 để mã hóa hoặc giải mã.