Bài giảng An toàn an ninh thông tin - Chương 2: Các hệ mật mã - Bùi Trọng Tùng

aXhine has risen YraEatiXaSST as a rXXsKSt oR 
 this reXent YeNeXoFEent in teXhnoSoAT EanT oR the 
 XiFher sTsteEsthat Pere onXe XonsiYXreYseKre 
 arenoP WreaMaWSe
 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 n h o r s t i a e
 reason Ror this has Ween reason for this has been
 this reXent this recent
 R f, W b, X c
 44
 22
44
 Ví dụ: Phá mã dịch vòng (tiếp)
 YKrinA the Sast ten Tears the art of secKrinA aSS 
 forEs of Yata incSKYinA YiAitaS sFeech has 
 iEFroNeY EanifoSY the FriEarT reason for this has 
 been the aYNent of EicroeSectronics the coEFSeQitT 
 of the fKnctions that can noP be FerforEeY bT the 
 Eachine has risen YraEaticaSST as a rccsKSt of 
 this recent YeNecoFEent in technoSoAT EanT of the 
 ciFher sTsteEsthat Pere once consiYcreYseKre 
 arenoP breaMabSe
 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 n h o r s t i f a b c e
 of the fKnctions of the functions
 of the ciFher of the cipher
 K u, F p
 45
45
 2.3. MẬT MÃ HIỆN ĐẠI
 46
 23
46
 Mật mã one-time-pad (OTP)
 •Vernam (1917)
 Key: 0 1 0 1 1 1 0 0 1 0
 
 Plaintext: 1 1 0 0 0 1 1 0 0 0
 Ciphertext: 1 0 0 1 1 0 1 0 1 0
 • Kích thước của khóa bằng kích thước của bản rõ
 • Khóa chỉ dùng 1 lần
 • Shannon : mật mã OTP là hệ mật hoàn hảo.
 47
47
 Mật mã OTP
 • Nếu khóa được dùng nhiều hơn 1 lần mật mã two-
 time-pad không còn an toàn (Tại sao?)
 c1  m1  k
 c2  m2  k
 Nếu kẻ tấn công có được bản mã:
 c1  c2 m1  m2 
 Nếu kích thước bản tin đủ dài
 m1  m2 m1 , m2
 48
 24
48
 Tấn công vào tính toàn vẹn của OTP
 enc ( ⊕k )
 m⊕k
 m ⊕
 p
 dec ( ⊕k )
 m⊕p (m⊕k)⊕p
 enc ( ⊕k )
 From: Bob
 From: Bob ⊕
 ⋯
 dec ( ⊕k )
 From: Eve From: Eve
 49
49
 Mật mã dòng (Stream Cipher)
 • Xử lý văn bản rõ theo dòng byte, thời gian thực
 RC4 (900 Mbps), SEAL (2400 Mbps), RC5(450 Mbps)
 • Phù hợp với các hệ thống truyền dữ liệu thời gian 
 thực trên môi trường mạng máy tính
 • An toàn nếu khóa chỉ dùng 1 lần (one-time-pad)
 • Trên thực tế, sử dụng hàm sinh khóa giả ngẫu nhiên
 (PRG - Pseudo Random Generator)
 k
 G: K {0, 1}n (len(K) << n)
 Hàm PRG phải có tính không thể tiên đoán: G(k)
 Với mọi thuật toán hiệu quả, nếu đã ⊕
 m
 biết i bit đầu tiên thì xác suất đoán 
 đúng bit thứ i + 1 là ≤ ½ + ε c
 50
 25
50
 Mã RC4 (Rivest Cipher 4)
 • Rivest Cipher 4: ra đời năm 1987
 • Kích thước khóa: 40 đến 128 bit
 • Hoạt động: gồm 2 thuật toán chính
 Key-scheduling algorithm (KSA): mở rộng khóa mã hóa thành 1 giá 
 trị S có kích thước 256 byte
 Pseudo-random generation algorithm (PRGA): lựa chọn 1 byte K từ 
 S để XOR 1 byte thông điệp
 • Hiện không còn an toàn
 51
51
 Mã eStream
 • Phương pháp mật mã dòng mới nhất được thiết kế để 
 thay thế cho các phương pháp mã dòng cũ
 • Hiện đang được phát triển, chưa công bố thành tiêu 
 chuẩn
 • Hàm sinh khóa giả ngẫu nhiên:
 PRG: {0,1}s × R ⟶ {0,1}n
 R: giá trị chỉ dùng 1 lần, không lặp lại
 • Mã hóa: E(k, m ; r) = m ⊕ PRG(k ; r)
 • Ví dụ: Salsa20 có s = 128 hoặc 256 bit, R có kích thước 
 64 bit
 52
 26
52
 Mật mã khối (Block Cipher)
 • Chia văn bản gốc thành các khối có kích thước như nhau
 • Xử lý mã hóa và giải mã từng khối
 • Nguyên lý chung: sử dụng các hàm lặp R(ki, ∙)
 key k
 key expansion
 key k1 key k2 key k3 key kn
 m1 m2 m3
 mm R(k1, ∙) R(k2, ∙) R(k3, ∙) R(kn, ∙) c
 53
53
 Mật mã DES - Data Encryption Standard
 • Kích thước khóa: 56 bit
 • Kích thước khối dữ liệu: 64 bit
 • Giải mã giống mã hóa nhưng đảo ngược thứ tự dùng khóa
 • Không còn an toàn để sử dụng
 56 bits
 key k
 48 bits key expansion
 m key k1 key k2 • • • key k16 c
 64 b 64 bits
 R0 R1 R2 R15 R16
 -1
 its IP f1 f2 • • • f16 IP
 L0 L1 L2 L15 L16
 Initial ⊕ ⊕ ⊕ Reverse 
 Permutation Initial 
 Permutation
 Mạng Fiestel có 16 vòng lặp 54
 27
54
 Cải tiến DES
 • DES trở nên không an toàn do kích thước khóa ngắn
 • 2DES: Sử dụng 2 khóa DES (k1,k2) = 112 bit
 E(k1,.) E(k2,.)
 Tuy nhiên, 2DES không an toàn hơn đáng kể so với DES vì 
 có thể bị tấn công meet-in-the-middle
 • 3DES:
 Sử dụng 2 khóa DES: E(k1,.) D(k2,.) E(k1,.)
 Sử dụng 3 khóa DES: E(k1,.) D(k2,.) E(k3,.)
 Sử dụng 3 khóa không an toàn hơn so với sử dụng 2 khóa
 55
55
 Mật mã AES – Advanced Encryption Standard
 • Kích thước khóa: 128, 192, 256 bit
 • Kích thước khối: 128 bit
 • Số vòng lặp: 10, 12, 14 theo kích thước khóa
 10 rounds
 4
 (1) ByteSub (1) ByteSub (1) ByteSub
 (2) ShiftRow (2) ShiftRow
 4 ⨁
 ⨁
 input (2) ShiftRow ⨁
 ⨁ ⋯
 (3) MixColumn (3) MixColumn
 invertible
 k0 k1 k2 k9
 ⨁
 key k10
 16 bytes key expansion: 16 bytes ⟶176 bytes 4 output
 4
 56
 28
56
 AES – Hàm lặp (Tham khảo)
 • ByteSub:
 • ShiftRows: 
 • MixColumns:
 57
57
 Các chế độ mã khối
 • Electronic Code Book (ECB): Mã từ điển
 Plain text: m1 m2
 Cipher text: c1 c2
 • Hạn chế: ECB không chống lại được tấn công KPA
 ECB
 58
 29
58
 Chế độ CBC - Cipher Block Chaining
 • Chế độ mã móc xích
 IV m[0] m[1] m[2] m[3]
    
 KS Mã KS Mã KS Mã KS Mã
 hóa hóa hóa hóa
 IV c[0] c[1] c[2] c[3]
 CBC chống lại được tấn công CPA nếu IV (Initial Vector) ngẫu nhiên
 59
59
 Tấn công CPA khi đoán được IV
 • Giả sử kẻ tấn công đoán được giá trị IV*
 Thử thách Tấn công
 Sinh khóa k
 m = 0 Sinh m
 c = [IV, E(k, IV)] c
 Sinh m0 = IV*  IV
 m0, m1 m1 ≠ m0
 Chọn b ∈ {0, 1}
 b = 0 c* = [IV*, E(k, IV)]
 b = 1 c* = [IV*, E(k, m  IV*)] 
 1 c*
 Nếu c*[1] = c[1] b’ = 0
 Ngược lại b’ = 1
 60
 30
60
 CBC – Giải mã
 IV c[0] c[1] c[2] c[3]
 KS Giải KS Giải Giải Giải
 KS KS
 mã mã mã mã
    
 IV m[0] m[1] m[2] m[3]
 61
61
 CBC – So sánh với ECB
 Ảnh gốc Mã hóa ở chế độ Mã hóa ở chế độ 
 ECB CBC
 62
 31
62
 CBC Padding
 • Khi kích thước bản tin gốc không chia hết cho một khối:
 r = Len(message) mod Len(block)
 Phần đệm có kích thước Len(block) – r
 • Khi kích thước bản tin gốc chia hết cho 1 khối: thêm phần 
 đệm có kích thước là 1 khối
 • Giá trị phần đệm khác nhau với mỗi chuẩn
 Không dùng chuỗi bit 0 để làm phần đệm
 • Chuẩn PKCS#7: Nếu cần đệm n byte thì dùng phần đệm 
 là chuỗi byte có giá trị mỗi byte là n
 Khối cuối n n  n
 Phần đệm: n byte
 63
63
 Chế độ CTR – Counter Mode
 • Initial Vector: 2 phương pháp sử dụng
 Giá trị ngẫu nhiên n bits
 Sử dụng giá trị dùng 1 lần (nonce) nonce counter
 n/2 bits n/2 bits
 • Mã hóa
 msg
 IV m[0] m[1]  m[L]
 
 E(k,IV) E(k,IV+1)  E(k,IV+L)
 IV c[0] c[1]  c[L]
 ciphertext
 Nếu IV lặp lại, chế độ CTR không an toàn
 64
 32
64
 Độ an toàn của các chế độ mã
 • Khóa được dùng nhiều lần giảm độ an toàn
 • Nếu gọi:
 q: số bản tin được mã hóa cùng với khóa không đổi
 L: số khối dữ liệu có trong bản tin dài nhất
 |X|: Số lượng giá trị có thể của 1 khối dữ liệu
 • Chế độ CBC an toàn trước tấn công CPA khi q2*L2 << |X|
 • Chế độ CTR an toàn trước tấn công CPA khi q2*L << |X|
 • Để xác suất tấn công là không đáng kể (≤ 2-80) thì sau 
 bao nhiêu khối phải đổi khóa?
 • Tất cả các chế độ mã đã đề cập không an toàn trước tấn 
 công CCA
 65
65
 Tấn công vào mật mã khối
 • Tấn công vét cạn (Exhaustive Search): Kẻ tấn công thử 
 mọi giá trị khóa k khi có được một vài cặp (mi, ci)
 DES: Với 2 cặp, xác suất tìm được đúng khóa k là ~ 1 – 1/271 với 
 thời gian vét cạn 256 giá trị
 AES-128: Với 2 cặp, xác suất tìm được đúng khóa k là ~ 1 – 1/2128 
 với thời gian vét cạn 2128 giá trị
 Sử dụng tính toán lượng tử: thời gian vét cạn còn T1/2 sử dụng 
 AES-256
 1976 DES adopted as federal standard
 1997 Distributed search 3 months
 1998 EFF deep crack 3 days $250,000
 1999 Distributed search 22 hours
 2006 COPACOBANA (120 FPGAs) 7 days $10,000
 66
 33
66
 Tấn công vào mật mã khối
 • Tấn công vét cạn (Exhaustive Search): Kẻ tấn công thử 
 mọi giá trị khóa k khi có được một vài cặp (mi, ci)
 DES: Với 2 cặp, xác suất tìm được đúng khóa k là ~ 1 – 1/271 với 
 thời gian vét cạn 256 giá trị
 AES-128: Với 2 cặp, xác suất tìm được đúng khóa k là ~ 1 – 1/2128 
 với thời gian vét cạn 2128 giá trị
 Sử dụng tính toán lượng tử: thời gian vét cạn còn T1/2 sử dụng 
 AES-256
 • Tấn công tuyến tính (Linear Attack): Kẻ tấn công tính toán 
 khóa k khi có rất nhiều cặp (mi, ci)
 DES: Với 242 cặp có thể tìm thấy khóa K trong thời gian 243
 AES-256: Với 299 cặp có thể tìm thấy khóa K trong thời gian 299
 67
67
 Tấn công vào mật mã khối
 • Tấn công kênh bên (side-channel attack): phán đoán giá 
 trị các bit khóa bằng cách ước lượng thời gian, lượng 
 điện năng tiêu thụ, bức xạ điện từ khi mã hóa, giải mã
 Ví dụ: phương pháp tấn công DES của Kocher và Jaffe năm 1998
 • Tấn công dựa vào lỗi (Fault attacks): lỗi xảy ra ở vòng lặp 
 cuối cùng sẽ làm lộ thông tin về khóa
 68
 34
68
 2.4. Những hạn chế của mật mã khóa đối xứng
 • Cần kênh mật để chia sẻ khóa bí mật giữa các bên
 Làm sao để chia sẻ một cách an toàn cho lần đầu tiên
 • Quá trình trao đổi khóa đòi hỏi cả 2 bên đều online
 • Số lượng khóa lớn: n(n-1)/2
 • Không dễ dàng để xác thực đối với thông tin quảng 
 bá (Chúng ta sẽ quay trở lại vấn đề này trong những 
 bài sau)
 • Giải pháp sử dụng bên thứ 3 tin cậy (trusted 3rd
 party) có giải quyết được vấn đề?
 69
69
 3. Hệ mật mã khóa bất đối xứng
 • Asymmetric key cryptography, Public key cryptography
 • Tháng 11/1976, Diffie và Hellman giới thiệu ý tưởng về 
 một kịch bản chia sẻ khóa bí mật (của hệ mật mã khóa 
 đối xứng) mới mà không truyền trực tiếp giá trị của khóa.
 • Độ an toàn dựa trên độ khó khi giải một số bài toán:
  Phân tích một số thành thừa số nguyên tố
  Tính logarit rời rạc
 • Các thuật toán dựa trên các hàm toán học
 • Một số hệ mật mã khóa công khai: RSA, El-Gamal, Eliptic 
 Curve Cipher (ECC)
 • Nếu hệ mật mã khóa BĐX an toàn trước tấn công KPA thì 
 cũng an toàn trước tấn công CPA
 70
 35
70
 Sơ đồ nguyên lý
 • Hệ mật mã gồm:
 Bản rõ (plaintext-m): thông tin không được che dấu
 Bản mật (ciphertext-c): thông tin được che dấu
 • Khóa: Bên nhận có 1 cặp khóa:
 Khóa công khai kUB : công bố cho tất cả biết (trong đó có cả kẻ tấn 
 công)
 Khóa cá nhân kRB : bên nhận giữ bí mật, không chia sẻ
 • Mã hóa (encrypt-E): c = E(kUB, m)
 Là hàm ngẫu nhiên
 • Giải mã (decrypt): m = D(kRB, c)
 Là hàm xác định
 • Tính đúng đắn: D(kRB, E(kUB, m)) = m
 71
71
 Sơ đồ nguyên lý (tiếp)
 Khóa mã hóa và
 giải mã khác nhau
 kUB kRB
 m m
 Mã hóa Giải mã
 Người
 Người 
 Gửi (A) c
 c nhận (B)
 Kênh truyền
 Làm thế nào để B m*
 Kẻ tấn 
 gửi tin một cách bí Thám mã
 mật cho A? công
 k*
 RB 72
 36
72
 Một ví dụ - Hệ mật RSA
 • Sinh khóa:
 Chọn p,q là hai số nguyên tố
 Tính n = p q , (n) = (p-1) (q-1)
 Chọn e sao cho UCLN((n), e) = 1 ;1< e < (n)
 Tính d sao cho (e d) mod (n) =1; 1 < d < (n)
 Khóa công khai : kU = (e,n)
 Khóa riêng : kR = (d,n)
 • Mã hóa : c = me mod n
 • Giải mã: m = cd mod n
 73
73
 Một ví dụ - Hệ mật RSA
 • Sinh khóa:
  Chọn p = 5, q = 11
 Tính n = p × q = 55, (n) =(p-1)×(q-1) = 40
 Chọn e sao cho UCLN((n), e) = 1 và 1 < e < (n)
 VD: e = 7
  Tính d sao cho (e × d) mod (n) = 1, 1 < d < (n)
 d = 23
 Cặp khóa : kU = (7,55), kR = (23,55)
 • Mã hóa: m = 6 c = me mod n = 67 mod 55 = 41
 • Giải mã: c = 41 m = cd mod n = 4123 mod 55 = 6
 Nếu kẻ tấn công có kU, làm thế nào để tính kR?
 74
 37
74
 Những vấn đề của mật mã RSA
 • Bản tin gốc m từ tập β có kích thước nhỏ kẻ 
 tấn công có thể thực hiện kiểm tra vét cạn để xác 
 định bản tin gốc.
 β ≤ ||N||1/e với e đủ nhỏ
 • Giá trị e nhỏ cho phép kẻ tấn công xác định được 
 các bản tin gốc nếu chúng có liên quan với nhau
 • Giá trị e nhỏ cho phép kẻ tấn công đoán nhận 
 được bản tin gốc nếu bản tin đó được mã hóa và 
 gửi tới nhiều đích
 75
75
 RSA-OEAP (Chuẩn PKCS#1 v2.0)
 • Nếu bản tin m được mã 2 lần với cùng khóa k thì nội 
 dung bản mã không thay đổi không chống được tấn 
 công CPA không an toàn
 • RSA-OEAP: sử dụng thêm khối đệm(padding) và giá trị 
 ngẫu nhiên trong quá trình mã hóa
 • Chống lại được tấn công CCA
 • Xử lý bản m trước khi mã hóa:
 r: giá trị ngẫu nhiên
 G, H: hàm băm
 • Mã hóa:
 X = (m || padding) XOR G(r)
 Y = H(X) XOR r
 Mã hóa (X||Y)
 || : Phép nối 76
 38
76
 Độ an toàn của RSA
 77
77
 Tấn công vào RSA
 • Tấn công kênh bên: quan sát quá trình x = C
 giải mã for j = 1 to n
 x = mod(x2, N)
 Phân tích thời gian [Kocher et al. 1997]: quá if dj == 1 then
 trình giải mã có thể lộ thông tin về khóa riêng x = mod(xC, N)
 Phân tích mức độ tiêu thụ năng lượng [Kocher end if
 et al. 1999] return x
 Phân tích tiếng ồn phát ra từ CPU [Daniel 
 Genkin et al. 2013]
 • Tấn công dựa vào lỗi tính toán
 • Tấn công do sinh khóa không ngẫu nhiên:
 Giả sử quá trình sinh khóa sử dụng p1 = p2 
 nhưng q1 ≠ q2 UCLN(N1, N2) = p
 Thực tế: 0.4% số lần sinh khóa ra trong giao 
 thức HTTPS gặp lỗi trên
 78
 39
78
 3.3. Kết hợp mật mã khóa công khai và 
 mật mã khóa đối xứng
 • Ưu điểm của mật mã khóa công khai:
  Không cần chia sẻ khóa mã hóa kUB một cách bí mật
  Khóa giải mã kRB chỉ có B biết:
 An toàn hơn
 Có thể sử dụng kRB để xác thực nguồn gốc thông tin (Chúng ta 
 sẽ quay lại vấn đề này trong bài sau)
  Số lượng khóa để mã mật tỉ lệ tuyến tính với số phần 
 tử (n phần tử n cặp khóa)
 • Nhưng...
 79
79
 3.3. Kết hợp mật mã khóa công khai và 
 mật mã khóa đối xứng
 • Hạn chế của mật mã khóa công khai so với mật mã khóa 
 đối xứng:
  Kém hiệu quả hơn: khóa có kích thước lớn hơn, chi phí tính toán 
 cao hơn
 Có thể bị tấn công toán học
 Kết hợp 2 hệ mật mã
 80
 40
80
 Sơ đồ “lai”
 • Phía gửi
 Thông điệp 
 (bản rõ) kUB
 Mã hóa Thông điệp Bản mã
 KĐX được mã hóa
 Mã hóa Khóa được 
 kS KCK mã hóa
 Nguồn khóa
 bí mật Tự suy luận cách thức xử lý của 
 phía nhận như là một bài tập!
 81
81
 Những sai lầm khi sử dụng mật mã
 • Lỗ hổng trên HĐH Android được phát hiện vào năm 2013 
 cho thấy quá trình sinh khóa không đủ ngẫu nhiên
 Các ứng dụng sử dụng cơ chế mã hóa bị ảnh hưởng, trong đó có 
 các ứng dụng sử dụng Bitcoin để thanh toán
 • Lỗ hổng trên Chromebooks: sinh giá trị ngẫu nhiên chỉ có 
 32 bit thay vì 256 bit
 • Coi mật mã là giải pháp vạn năng (những bài sau chúng 
 ta sẽ phân tích kỹ hơn)
 • Sửa đổi/Thêm một vài yếu tố bí mật vào giải thuật, hệ mật 
 mã sẽ an toàn hơn
 • Sử dụng các hàm ngẫu nhiên của ngôn ngữ lập trình
 82
 41
82
 Những sai lầm khi sử dụng mật mã
 • Không thay đổi giá trị IV(Initial Vector)
 • Sử dụng chế độ mã từ điển (ECB)
 • Case study: Lỗi sử dụng mật mã trong các ứng dụng 
 Android (2013)
 Phân tích 11.748 ứng dụng
 83
83
 Một số lưu ý khác
 • Chỉ sử dụng thuật toán chuẩn và các thư viện lập 
 trình được phê chuẩn: OpenSSL, Bouncy Castle, 
 Libgcrypt, RSA BSAFE, wolfCrypt
 • Nếu có thể, sử dụng các thuật toán mạnh nhất
 • Nếu phải sinh khóa từ một giá trị cho trước, sử 
 dụng hàm PBKDF2()
 • Sử dụng mật mã theo tiêu chuẩn. Ví dụ: PKCS, 
 FIPS
 84
 42
84