Bài giảng An ninh mạng - Chương 2: Mã hóa - Trần Trung Dũng

Nội dung text: Bài giảng An ninh mạng - Chương 2: Mã hóa - Trần Trung Dũng

1. Mã hóa
2. Mục tiêu • Từ điển trong mã hóa • Lịch sử mã hóa
3. Từ điển • plaintext: nội dung cần được mã hóa • ciphertext: đã mã hóa • enciphering và encryption: quá trình mã hóa, chuyển từ plaintext sang ciphertext • secret key: khóa dùng để mã hóa. Chú ý là khóa này cũng dùng để giải mã. Vì vậy được gọi là mã hóa đối xứng (symmetric key cryptography). • deciphering hoặc decryption: giải mã • cryptography: tất cả các lược đồ mã hóa và giải mã ngày nay • block cipher: mã hóa một khối dữ liệu, cho ra một khối đã được mã hóa • stream cipher: mã hóa liên tục dòng dữ liệu, thường là mỗi byte một lần
4. Kĩ thuật mã hóa cổ điển • Chia làm hai kĩ thuật chính: thay thế, đảo vị trí: – Thay thế: nghĩa là thay 1 kí tự plaintext thành một kí tự ciphertext – Đảo vị trí: thay đổi thứ tự xuất hiện của các kí tự
5. Caesar Cipher • Được xem là kĩ thuật mã hóa đầu tiên sử dụng phương pháp thay thế • Ví dụ: plaintext: are you ready ciphertext: DUH BRX UHDGB • Nếu khóa bí mật là k thì mã hóa kí tự ’p’ sẽ là C = E( k, p ) = (p + k) mod 26 • Giải mã p = D( k, C ) = (C - k) mod 26 E: encryption (mã hóa) D: decryption (giải mã)
6. Monoalphabetic Ciphers • Thay thế ngẫu nhiên một trật tự nào đó của 26 kí tự trong bảng alphabet • Ví dụ: plaintext letters: a b c d e f substitution letters: t h i j a b • Khóa bây giờ là một thứ tự ngẫu nhiên nào đó trong bảng alphabet • Như vậy sẽ có 26! > 4. 1026 • Không gian khóa lớn chống tấn công brute-force
7. Statistical Attack • Nếu chúng ta biết tỉ lệ xuất hiện của ngôn ngữ tự nhiên thì sử dụng statistical attack rất dễ dàng. • Nếu plaintext là tiếng Anh
8. Statistics của nhóm 2, 3 kí tự • Dựa vào đặc trưng của tỉ lệ xuất hiện cặp 2 kí tự hoặc bộ 3 kí tự liên tiếp để giải mã
9. Mã hóa nhiều kí tự • Nếu mỗi lần chỉ mã hóa một kí tự thì sẽ để lại cấu trúc của của plaintext trong ciphertext • Để phá cấu trúc này thì người ta đề nghị mã hóa một lần nhiều kí tự • Phương pháp tốt nhất được đề xuất là Playfair Cipher
10. Tạo ma trận trong Playfair cipher • Trong playfair cipher, chọn một khóa. Sau đó nhập khóa này và các kí tự còn lại từ trái qua phải, trên xuống dưới trong ma trận 5x5. • Ví dụ như khóa là : smythework S M Y T H E W O R K A B C D F G I/J L N P Q U V X Z
11. Luật mã hóa 1. Hai kí tự trên cũng dòng sẽ được thay thế bởi hai kí tự bên phải của nó (xoay vòng). Ví dụ bf thì thay bằng CA 2. Hai kí tự trên cùng cột thì được thay thế bởi hai kí tự ngay dưới nó. Ví dụ ol thay bằng CV 3. Còn lại, mỗi kí tự được thay thế bằng kí tự cùng dòng nhưng ở cột của kí tự còn lại. Ví dụ gf. g ở dòng 4 cột 1, f ở dòng 3 cột 5. Nên thay g bằng kí tự dòng 4 và cột 5. đó là P. Và ??? thay cho f
12. Vấn đề kí tự trùng lắp trong khóa và việc lặp lại kí tự trong plaintext 1. Bạn phải loại bỏ bất cứ sự trùng lắp trong khóa 2. Trước khi áp dụng phương pháp thay thế, phải chèn kí tự đặc biệt xen giữa hai từ trùng lắp liên tiếp Ví dụ: carry carxry, nếu chọn x là kí tự đặc biệt
13. Tính bảo mật của Playfair cipher • Playfair được cho là không thể phá mã trong nhiều thập niên • Được quân đội Anh sử dụng trong thế chiến 1, quân đội Mĩ và đồng minh sử dụng trong thế chiến 2. • Nhưng sau đó phát hiện ra nó rất dễ bẻ khóa. • Dựa vào mật độ xuất hiện của các kí tự. • Dựa vào tính chất: nếu AB XY thì BA YX. • Tìm những từ có bắt đầu và kết thúc là các cặp đảo nghịch nhau: receiver, departed, repairer, redder, denuded,
14. Mã hóa nhiều kí tự: The Hill Cipher • Sử dụng cách tiếp cận hoàn toàn khác • Mỗi kí tự được gán với 1 con số. Ví dụ gán từ 0 25 cho a z • Khóa, gọi là K, gồm một ma trận số nguyên 3x3 k11 k12 k13 k k k K = 21 22 23 k31 k32 k33
15. Mã hóa nhiều kí tự: The Hill Cipher • Mã hóa 3 từ cùng một lúc, giả sử đó là các số p1,p2,p3 c1 = ( k11p1 + k12p2 + k13p3 ) mod 26 c2 = ( k21p1 + k22p2 + k23p3 ) mod 26 c3 = ( k31p1 + k32p2 + k33p3 ) mod 26 • Viết gọn lại C [K]P mod 26 • Giải mã P [K 1]C mod 26
16. Tính bảo mật của Hill cipher • Phương pháp này cực kì an toàn chống lại tấn công trực tiếp vào nội dung đã mã hóa (cipher). Bởi vì không gian số nguyên rất lớn • Nhưng nó không có ý nghĩa bảo mật nếu như plaintext và ciphertext được biết. • Vì giải hệ phương trình c1 = ( k11p1 + k12p2 + k13p3 ) mod 26 c2 = ( k21p1 + k22p2 + k23p3 ) mod 26 c3 = ( k31p1 + k32p2 + k33p3 ) mod 26 dễ dàng nếu biết đc ci và pi
17. Polyalphabetic Ciphers: The Vigenere Cipher • Trong monoalphabetic cipher: một luật thay thế duy nhất được áp dụng cho mỗi lần thay thế • Mỗi kí tự trong khóa đại diện một giá trị shift trong Caesar cipher key: abracadabraabracadabraabracadabraab plaintext: canyoumeetmeatmidnightihavethegoods ciphertext: CBEYQUPEFKMEBK • Cụm từ “abracadabra” là key • Tra dòng là key, cột là plaintext để tìm ra ciphertext. Xem hình slide kế tiếp
18. Mức độ bảo mật của Vigenere Cipher • Vì một kí tự có thể cho ra nhiều kết quả khác nhau sau khi mã hóa nên tỉ lệ phân phối tự nhiên của các kí tự bị phá hủy • Nhưng thực tế với key dài 9 kí tự, thì theo mật độ phân bố như hình trên, vẫn không thay đổi đc nhiều. • Khi dùng khóa dài hơn thì tất nhiên sẽ phá sự phân bố tự nhiên, xem hình ví dụ khi chuỗi khóa dài bằng plaintext. • Để phá khóa Vigenere cipher thì trước tiên phải xác định chiều dài khóa. • Nếu chiều dài khóa là N thì plaintext ở các vị trí 1, N, 2N, 3N, sẽ được mã hóa giống nhau.
19. Kỹ thuật thay đổi vị trí • Bên trên chỉ mới trình bày về kĩ thuật thay thế • Về cơ bản kĩ thuật thay đổi vị trí: plaintext được viết theo từng dòng của ma trận. • Ciphertext được tạo bằng cách đọc theo từng cột • key: 4 1 3 6 2 5 • plaintext: m e e t m e a t m i d n i g h t f o r t h e g o d i e s x y • ciphertext: ETGTIMDFGXEMHHEMAIRDENOOYTITES
20. Block cipher (mã hóa khối) + DES • Khái niệm block cipher • Tính không khả thi của block cipher lý tưởng • Cấu trúc Feistel Cipher • DES, Data Encryption Standard
21. Block cipher lý tưởng • Trong mã hóa theo block (vẫn trong nhóm mã hóa cổ điển). Mỗi nhóm N bit của plaintext được thay thế bằng nhóm N bit của ciphertext. • Thông thường sử dụng nhóm 64 bit • Một block cipher lý tưởng là mối quan hệ giữa input và output là hoàn toàn ngẫu nhiên. Nhưng vẫn có thể giải mã đc. Vì vậy phải là hàm one-to-one, nghĩa là mỗi input block được ánh xạ đến một output block duy nhất. • Xem ví dụ ở slide kế tiếp
22. Kích thước khóa • 64-bit block 264 số nguyên input. Mỗi input phải có 1 output tương ứng duy nhất vì vậy khóa phải dài: 2X 264 ~ 1021 • Kích thước khóa của block cipher lý tưởng quá lớn làm cho nó không có tính khả thi. • Thử hình dung việc lưu trữ, xử lý, truyền khóa.
23. Cấu trúc Feistel cho Block Ciphers • Được đặt tên của nhà mã hóa Horst Feistel của IBM và được ứng dụng đầu tiên trong Lucifer cipher • Mã hóa theo cấu trúc Feistel sử dụng chung thuật toán cho việc giải mã và mã hóa • Cấu trúc Feistel bao gồm nhiều vòng xử lý plaintext, mỗi vòng sẽ sử dụng kĩ thuật thay thế trước rồi kĩ thuật thay đổi vị trí. • Input block tại mỗi vòng được chia làm hai nữa: L và R • Trong mỗi vòng, R không thay đổi, L sẽ thông qua một xử lý tùy thuộc vào R và khóa. • Sau đó hoán chuyển L và R. Nghĩa là R vòng trước là L của vòng hiện tại
24. Mô tả theo toán học • Li, Ri nữa trái và nữa phải của chuỗi input ở vòng thứ i • Li = Ri-1 • Ri = Li-1 XOR F(Ri-1, Ki) • F: hàm Feistel
25. Giải mã • Là quá trình tương tự được thực hiện ngược lại • [A ⊕ B] ⊕ C = A ⊕ [B ⊕ C ] • A ⊕ A = 0 • A ⊕ 0 = A
26. DES: The Data Encryption Standard • National Institute of Standards and Technology (NIST) chấp nhận năm 1977 • DES sử dụng cấu trúc Feistel cipher với 16 vòng xử lý • DES sử dụng khóa 56 bit (8 bytes, mỗi byte dùng 1 bit làm parity check) • DES bị Electronics Frontiers Organization phá khóa 1999 • Vì vậy NIST đề nghị các tổ chức sử dụng Triple-DES • Triple-DES tiếp tục được sử dụng rộng rãi trong các ứng dụng thương mại • Từ sự sụp đổ của DES AES (advanced encryption standard)
27. • Hàm F và việc tạo round key (khóa ở mỗi vòng) xác định phương pháp mã hóa DES. • Round key được phát sinh từ khóa chính thông qua một chuỗi phép hoán vị. Mỗi round key dài 48 bit
28. Xử lý ở mỗi vòng trong DEA • DEA là thuật toán cài đặt DES • 32 bit bên phải của 64 bit data được nhân rộng lên thành 48 bit. Bước này gọi là E-step (expansion permutation) • Chi tiết E-step: – Chia 32 bit thành 8 nhóm, mỗi nhóm 4 bit – Mỗi nhóm thêm 1 bit bên trái và 1 bit bên phải mỗi nhóm 6 bit • Khóa 56 bit được chia làm 2 nữa. Mỗi nữa được dịch (shift) rồi kết hợp với khóa 56 bit để tạo 48-bit round key. • 48 bit output của E-step được XOR với 48 bit round key. • Output được chia thành 8 nhóm 6-bit
29. • Mỗi nhóm 6bit sẽ được thay thế bằng nhóm 4 bit. Quá trình thay thế này chứa trong S-box, xem hình 4 • Sau quá trình thay thế chúng ta có 32 bit • 32 bit này được hoán vị bằng quá trình bên trong P-box, hình 4 • Kết quả này được XOR với 32 bit nữa trái ban đầu để tạo đầu ra bên phải cho vòng kế tiếp. • Mục tiêu của S-box là tạo diffusion (khuếch tán). Diffusion nghĩa là mỗi bit của plaintext phải ảnh hưởng càng nhiều bit của ciphertext càng tốt • Mục tiêu của P-box là tạo confusion. Confusion ở đây có nghĩa là mối quan hệ giữa khóa và ciphertext càng phức tạp càng tốt. • Diffusion và confusion là hai yếu tố cốt lõi của mã hóa theo block.
30. Hình 4
31. S-box • Như trong hình 5, mỗi input 48-bit được chia thành 8 nhóm, mỗi nhóm 6 bit. Mỗi nhóm này được xử lý qua 1 S-box cho ra 1 nhóm 4- bit. Vậy 8 S-box sẽ cho output 32bit. • Mỗi một S-box trong 8 S-box sẽ chứa bảng 4x16. Bit đầu tiên và cuối cùng của nhóm 6 bit được giải mã để tìm ra dòng. 4 bit ở giữa đại diện cho cột.
32. Hình 5
33. Bảng S-box số 1
34. P-Box • Mục tiêu của P-Box là hoán vị. Ở hình trên thì bit thứ 16 của input sẽ là bit số 1 của output. • Bit thứ 7 của input sẽ là bit thứ 2 của output. • Và tiếp theo như bảng mô tả • Chú ý chỉ số bắt đầu là 1.
35. Phát sinh round key • Khóa khởi đầu là 56bit, (8 byte, bit cuối là parity bit) • Đầu tiên 56bit khóa được thông qua hoán vị 1 (Permuation Choice 1) • Bắt đầu mỗi vòng, khóa 56 bit được chia thành 2 nữa, mỗi nữa 28 bit. Shift vòng mỗi nữa 1 hoặc 2 bit • Để tạo round key, ghép 2 nữa lại và áp dụng hoán vị 2 (permuation choice 2) để cho ra output 48 bit.
36. Hoán vị đầu tiên của khóa
37. Tạo 48 bit round key từ 56 bit
38. Tại sao DES tốt • Bước thay thế tạo diffusion mạnh. Nếu thay đổi 1 bit trong phần dữ liệu input thì sẽ tạo thay đổi khoảng 34 bit trong phần ciphertext • Việc tạo roundkey giúp cho confusion mạnh. Nếu thay đổi 1 bit trong khóa thì sẽ thay đổi khoảng 35 bit trong ciphertext. • Khóa 56 bit nghĩa là không gian khóa 256 ~ 7.2x1026. • Nếu muốn thử sai ½ số khóa, giả thiết 1 khóa tốn 1ms thì cần 1142 năm mới tìm ra được khóa • Tuy nhiên nếu xử lý song song 1 triệu khóa mỗi lần thì chỉ cần tốn 10h (EFF tốn 3 ngày để phá khóa)
39. Ôn tập • DES, bước hoán vị và mở rông từ 32bit lên 48 bit có cải tiến được tính diffusion không? • DES bị phá khóa 1999. Bạn nghĩ vì sao? • DES bị phá khóa. Vậy nó có còn quan trọng không?