Bài giảng An toàn an ninh thông tin - Chương 3: Xác thực thông điệp - Bùi Trọng Tùng

 BÀI 3.
 XÁC THỰC THÔNG ĐIỆP
 Bùi Trọng Tùng,
 Viện Công nghệ thông tin và Truyền thông,
 Đại học Bách khoa Hà Nội
 1
1
 Nội dung
 • Các vấn đề xác thực thông điệp
 • Mã xác thực thông điệp (MAC)
 • Hàm băm và hàm băm mật HMAC
 2
 1
2
 1. ĐẶT VẤN ĐỀ
 3
3
 1. Đặt vấn đề
 M
 Kênh truyền
 Alice Bob
 M’ Thay đổi nội dung 
 M thành M’
 Mallory Hoặc, bản tin M’’ 
 M’’ giả danh Alice 
 4
 2
4
 Xác thực thông điệp
 • Bản tin phải được xác minh:
 Nội dung toàn vẹn: bản tin không bị sửa đổi
 Bao hàm cả trường hợp Bob cố tình sửa đổi
 Nguồn gốc tin cậy:
 Bao hàm cả trường hợp Alice phủ nhận bản tin
 Bao hàm cả trường hợp Bob tự tạo thông báo và “vu khống” 
 Alice tạo ra thông báo này
 Đúng thời điểm
 Các dạng tấn công điển hình vào tính xác thực: Thay
 thế (Substitution), Giả danh (Masquerade), tấn công
 phát lại (Replay attack), Phủ nhận (Repudiation)
 5
5
 2. MÃ XÁC THỰC THÔNG ĐIỆP (MAC)
 6
 3
6
 Message Authentication Code
 • Hai bên đã trao đổi một cách an toàn khóa mật k
 • Hàm MAC = (S, V) là một cặp thuật toán
 • Sinh mã: t = S(k, m)
 Đầu ra: kích thước cố định, không phụ thuộc kích thước
 của M
 • Xác minh: V(k, m, t)
 Nếu t = S(k, m) thì V = true
 Ngược lại V = false
 M t
 Alice S V Bob
 K K
 7
7
 MAC – Ví dụ 1
 Khách hàng chuyển 
 V (k, m t) = True 
 khoản
 1. Chia sẻ khóa k M t
 2. Xác thực thông tin CK: V Ngân hàng
 t = S(k,SoTK||money)
 M’ t' V (k, m’, t’) = False 
 Kẻ tấn công Mã MAC cho phép 
 phát hiện thông tin bị 
 t’ = S(?,SoTK’||money) sửa đổi
 Thay đổi số tài 
 khoản nhận tiền
 8
 4
8
 MAC – Ví dụ 2: Phần mềm Tripwire
 • Khi cài đặt, tính giá trị MAC của các file cần bảo vệ
 file file
 F F’
 t = S(k,F )
 1 t = S(k, F1) V(k, F’, t) = False 
 • Khi máy tính khởi động, các file được kiểm tra mã MAC
 Cho phép phát hiện các file bị sửa đổi (ví dụ do nhiễm 
 virus)
 9
9
 An toàn của MAC
 Thử thách Tấn công
 1. Sinh khóa k
 m ,...,m
 1 q 2. Chọn m1, ..., mq
 3. Tính ti = S(k, mi)
 t1,...,tq
 4. Chọn m và sinh t sao cho
 (m,t) {(m ,t ),...,(m t )}
 m, t 1 1 q, q
 5. b = V(k, m, t) 
 b = {true,false}
 • MAC là an toàn nếu với mọi thuật toán tấn công hiệu quả 
 thì xác suất P(b = true) ≤ ε
 kẻ tấn công không thể tạo giá trị t hợp lệ nếu không có 
 khóa k
 10
 5
10
 An toàn của MAC
 MAC còn an toàn không nếu một trong các trường hợp 
 sau:
 (1) Kẻ tấn công tìm được m* sao cho S(?, m*) = t với t 
 chọn trước
 (2) Kẻ tấn công tìm được m* sao cho S(?, m*) = S(?, m) 
 với m chọn trước
 (3) Kẻ tấn công tìm được m và m* sao cho S(?, m*) = S(?, 
 m)
 (4) Giá trị t có kích thước 10 bit
 11
11
 Độ an toàn của MAC
 • Giả sử m1 và m2 là hai bản tin có mã MAC giống nhau:
 S(k, m1) = S(k, m2)
 S(k, m1||W) = S(k, m2||W) với W bất kỳ
 • Kịch bản tấn công:
 1. Kẻ tấn công tính toán tx = S(k, mx) với x = 1, , N
 2. Tìm cặp bản tin (mi, mj) có ti = tj. Nếu không tìm thấy 
 thực hiện lại bước 1
 3. Chọn bản tin W và tính t = S(k, mi ||W)
 4. Thay mi || W bằng mj || W có lợi cho kẻ tấn công
 12
 6
12
 Ví dụ tấn công vào tính đụng độ
 (1) Kẻ tấn công(Mr. Tung) chọn được 2 bản tin có mã MAC 
 giống nhau:
 m1: ‘I will pay 1’
 m2: ‘I will pay 2’
 Chọn W = ‘000$ to Mr.Tung’
 m1 || W = ‘I will pay 1000$ to Mr.Tung’
 m2 || W = ‘I will pay 2000$ to Mr.Tung’
 (2) Đánh lừa người dùng gửi bản tin ‘I will pay 1000$ to 
 Mr.Tung’ || S(k, ‘I will pay 1000$ to Mr.Tung’) cho ngân 
 hàng
 (3) Thay thế bằng ‘I will pay 2000$ to Mr.Tung’ || S(k, ‘I will 
 pay 1000$ to Mr.Tung’) Ngân hàng chấp nhận
 13
13
 Xây dựng MAC: CBC-MAC
 m[0] m[1] m[2] m[3]
     rawCBC
 k1 Mã k1 Mã k1 Mã k1 Mã
 hóa hóa hóa hóa
 Tại sao?
 tag
 k = (k1, k2) k Mã
 2 hóa
 t
 14
 7
14
 rawCBC-Tấn công chọn trước bản rõ
 m m tm
   
 rawCBC rawCBC m rawCBC
 S(k,) S(k,) S(k,)
 t
 t t
 Vấn đề: S(k, m || tm ) = S(k, S(k,m)(tm) ) =
 S(k, t(tm) ) =
 S(k,m) = t
15
 An toàn của CBC-MAC
 • Khóa được dùng nhiều lần giảm độ an toàn
 • Nếu gọi:
 q: số bản tin được tính MAC cùng với khóa không đổi
 |X|: Số lượng giá trị có thể của t
 • Xác suất tấn công thành công ≤ 2*q2 / |X|
 • Để xác suất tấn công là không đáng kể (≤ 2-80) thì sau 
 bao nhiêu lần tính MAC phải đổi khóa?
 8
16
 Tấn công phát lại (Replay attack)
 • Kẻ tấn công phát lại bản tin M đã được chứng 
 thực trong phiên truyền thông trước đó
 • Thiết kế MAC không chống tấn công phát lại
 cần thêm các yếu tố chống tấn công phát lại 
 trong các giao thức truyền thông sử dụng MAC
 • Một số kỹ thuật chống tấn công phát lại:
 Giá trị dùng 1 lần(nonce): S(k, m || nonce)
 Tem thời gian: S(k, m || timestamp)
 17
17
 Tấn công phát lại
 Khách hàng chuyển 
 khoản
 1. K = KeyGen(l) Publish
 2. Xác thực thông tin CK: V Ngân hàng
 t = S(k, SoTK||money)
 Kẻ tấn công
 t = S(k, SoTK||money)
 Sao chép và và phát lại 
 các yêu cầu chuyển khoản
 18
 9
18
 Xây dựng MAC: CBC-MAC
 Kích thước thông điệp không chia 
 hết cho kích thước một khối?
 m[0] m[1] m[2] m[3] padding
    
 k1 Mã k1 Mã k1 Mã k1 Mã
 hóa hóa hóa hóa
 tag
 k = (k1, k2) k Mã
 2 hóa
 t
 19
19
 Padding cho CBC-MAC
 • Ý tưởng 1: Thêm vào các bit 0
 m[0] m[1] m[0] m[1] 000
 • Không an toàn. Ví dụ:
 $100 00
 $10 000
 Same Tag
 10
20
 Padding cho CBC-MAC
 • Yêu cầu: Mi ≠ Mj thì pad(Mi) ≠ pad(Mj)
 • Chuẩn ISO/IEC 9797-1:
 Sử dụng chuỗi padding bắt đầu bởi bit 1
 Nếu kích thước thông điệp là bội số kích thước của khối, luôn thêm
 1 khối padding
 m[0] m[1] m[0] m[1] 1000
 m[0] m[1] m[0] m[1] 1000000000
21
 Tấn công CCA – Nhắc lại
 Thử thách Tấn công
 Sinh khóa k
 ci, mj Sinh ci, mj
 m = D(k, c )
 i i m , c
 cj = E(k, mj) i j
 Sinh m0, m1
 m0, m1
 Chọn b ∈ {0, 1}
 c* = E(k, mb) c*
 Sinh c’i, m’j (c’i ≠ c*)
 c’i, m’j
 m’ = D(k, c’ )
 i i m’ , c’
 c’j = E(k, m’j) i j Đoán b’ ∈ {0, 1}
 • Hệ mật chống lại được tấn công CCA (độ an toàn IND-CCA) 
 nếu với mọi thuật toán tấn công hiệu quả thì P(b’ = b) ≤ ½ + ε
 22
 11
22
 Mật mã có xác thực
 • Các sơ đồ mật mã đã xem xét không chống lại được tấn 
 công CCA(chosen-cipher attack)
 • Cách thức chung: kẻ tấn công sửa bản mã c* thành c’i và yêu cầu 
 giải mã
 • Giải pháp: Mật mã có xác thực (E, D) Từ chối giải mã các bản 
 Hàm mã hóa E: K x M x N C mã không hợp lệ
 Hàm giải mã D: K x C x N M ∪ {⊥}
 • Trong đó N là một dấu hiệu sử dụng để xác thực
 • Giải pháp: Kết hợp mật mã và mã MAC
 • Khóa mã hóa và khóa xác thực phải khác nhau
 23
23
 Một số sơ đồ sử dụng mã MAC
 k
 k2 1
 m
 || m E S
 m D ’ So
 t t sánh
 t’
 S k2
 V(k1, m’,t’)
 k1
 a) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng(SSL)
 K K
 K2 2 1
 D S
 M E || So
 sánh
 t t’
 S
 K1
 b) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng (SSH) 24
 12
24
 Một số sơ đồ sử dụng mã MAC(tiếp)
 K1
 K2 K2
 S So True M
 M E || D
 sánh
 t t’
 S
 K1
 c) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng(IPSec)
 • Một số chuẩn:
 GCM: Mã hóa ở chế độ CTR sau đó tính CW-MAC
 CCM: Tính CBC-MAC sau đó mã hóa ở chế độ CTR (802.11i)
 EAX: Mã hóa ở chế độ CTR sau đó tính CMAC
 25
25
 Nhận xét
 Sơ đồ a Sơ đồ b Sơ đồ c
 • Xác thực toàn vẹn • Xác thực toàn • Xác thực toàn 
 bản rõ vẹn bản rõ vẹn bản rõ
 • Không xác thực • Không xác thực • Xác thực toàn 
 toàn vẹn bản toàn vẹn bản vẹn bản mật(có 
 mật(không phát không phát hiện thể phát hiện bản 
 hiện tấn công thay 
 bản mật bị thay mật bị thay thế)
 thế bản mật)
 thế)
 • Không có thông tin • MAC không chứa 
 về bản rõ từ MAC • MAC chứa thông thông tin bản rõ
 • Chỉ đảm bảo an tin bản rõ • Luôn đảm bảo an 
 toàn CCA khi mã ở • Có thể giảm sự toàn CCA
 chế độ rand-CBC an toàn mã mật
 hoặc rand-CTR
 13
26
 3.HÀM BĂM
 27
27
 Khái niệm
 • Hàm băm H: thực hiện phép biến đổi:
  Đầu vào: bản tin có kích thước bất kỳ
  Đầu ra: giá trị digest h = H(m)có kích thước n bit cố định (thường 
 nhỏ hơn rất nhiều so với kích thước bản tin đầu vào)
 • Chỉ thay đổi 1 bit đầu vào, làm thay đổi hoàn toàn giá trị 
 đầu ra
 • Ví dụ:
 Đầu vào: “The quick brown fox jumps over the lazy dog”
 Mã băm: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
 Đầu vào: “The quick brown fox jumps over the lazy cog”
 Đầu ra: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
 28
 14
28
 Một hàm băm đơn giản
 m m m  m 
 • Chia thông điệp thành 1 11 12 1n
 m m m  m 
 các khối có kích thước n- m 2 21 22 2n 
 bit ...     
  Padding nếu cần 
 ml ml1 ml2  mln 
 • Thực hiện XOR tất cả    
 các khối mã băm có 
 kích thước n bit    
 • Tất nhiên, hàm băm này 
 c1 c2 ... cn =H(m)
 không đủ an toàn để sử 
 dụng trong bài toán xác 
 thực thông điệp
 29
29
 Yêu cầu đối với hàm băm
 1. Có thể áp dụng với thông điệp m với độ dài bất kỳ
 2. Tạo ra giá trị băm h có độ dài cố định
 3. H(m) dễ dàng tính được với bất kỳ m nào
 4. Từ h rất khó tìm được m sao cho h = H(m): tính một 
 chiều
 5. Biết trước m1 rất khó tìm được m2 sao cho H(m1) = 
 H(m2) tính chống đụng độ yếu
 6. Rất khó tìm được cặp (m1, m2) sao cho H(m1)=H(m2) 
 tính chống đụng độ mạnh
 30
 15
30
 Một số hàm băm phổ biến
 • MD5
  Kích thước digest: 128 bit
  Công bố thuật toán tấn công đụng độ (collision attack) 
 vào 1995
  Năm 2005 tấn công thành công
 • SHA-1
 Kích thước digest: 160 bit
 Công bố tấn công thành công vào năm 2015
 Hết hạn vào năm 2030
 • SHA-2: 224/256/384/512 bit
 • SHA-3: 224/256/384/512 bit
 31
31
 MD5
 • Bước 1: Padding dữ liệu sao cho bản tin đầu vào có độ 
 dài L sao cho L mod 512 = 448
 • Bước 2: Biểu diễn độ dài của dữ liệu ban đầu dưới dạng 
 64 bit. Thêm giá trị độ dài này vào khối dữ liệu.
 • Coi khối dữ liệu là một chuỗi các khối 512 bit: Y0, Y1, , YK-1
 • Hoặc là một chuỗi các khối 32 bit : m0, m1, ,mN
 • Bước 3: Khởi tạo các giá trị hằng số A, B, C, D
 A = 0x67 45 23 01
 B = 0xEF CD AB 89
 C = 0x98 BA DC FE
 D = 0x10 32 54 76
 16
32
 MD5
 • Bước 4: Thực hiện vòng lặp 
 xử lý các khối 512 bit
 Xử lý khối dữ liệu 512 bit thứ q: 
 thực hiện 4 vòng lặp. Mỗi vòng 
 lặp áp dụng hàm nén với T[1..64] 
 là mảng hằng số xác định trước
 Cộng modulo 232 mỗi khối với giá 
 trị CVq để có CVq+1
 • Bước 5: Kết quả xử lý khối 
 512 bit cuối cùng là giá trị 
 băm của thông điệp
33
 Hàm nén trong MD5
 • Đầu vào:
 • CV: Khối 128 bit
 Mi: khối dữ liệu 32-bit
 Ti: Hằng số
 32
 • Cộng modulo 2 Mi
 • <<<s: dịch trái s bit
 Ti
 • ˄: AND, v: OR, ¬: NOT 
 F1 = (B˄C)˅(¬B ˄ D)
 F2 = (B ˄ D) ˅(C ˄ ¬D)
 F3 = B  C  D
 F4=C  (B ˅ ¬D)
 • Thực hiện vòng lặp 16 bước
 17
34
 SHA-1
 • Bước 1: Padding dữ liệu sao cho bản tin đầu vào có độ 
 dài L sao cho L mod 512 = 448
 • Bước 2: Biểu diễn độ dài của dữ liệu ban đầu dưới dạng 
 64 bit. Thêm giá trị độ dài này vào khối dữ liệu.
 • Coi khối dữ liệu là một chuỗi các khối 512 bit: Y0, Y1, , YK-1
 • Hoặc là một chuỗi các khối 32 bit : m0, m1, ,mN
 • Bước 3: Khởi tạo các giá trị hằng số A, B, C, D, E
 A = 0x67 45 23 01
 B = 0xEF CD AB 89
 C = 0x98 BA DC FE
 D = 0x10 32 54 76
 E = 0xC3 D2 E1 F0
35
 SHA-1
 • Bước 4: Thực hiện vòng lặp 
 xử lý các khối 512 bit
 Xử lý khối dữ liệu 512 bit thứ q: 
 thực hiện 4 vòng lặp. Mỗi vòng 
 lặp áp dụng hàm nén với K là 
 hằng số xác định trước
 Cộng modulo 232 mỗi khối với giá 
 trị CVq để có CVq+1
 • Bước 5: Kết quả xử lý khối 
 512 bit cuối cùng là giá trị 
 băm của thông điệp
 18
36
 Hàm nén trong SHA-1
 • Đầu vào:
 • CV: Khối 160 bit
 • Wt: Khối dữ liệu mở rộng 32 bit
 • Kt: Hằng số
 • Cộng modulo 232
 • <<<5(30): dịch trái 5(30) bit
 • ˄: AND, v: OR, ¬: NOT 
 F1 = (B˄C)˅(¬B ˄ D)
 F2 = B  C  D
 F3 = (B ˄ C) ˅ (B ˄ D) ˅ (C ˄ D)
 F4 = B  C  D
 • Thực hiện vòng lặp 20 bước
37
 Sử dụng mã băm
 • Xác thực toàn vẹn bản tin: chỉ phát hiện được lỗi ngẫu 
 nhiên trong quá trình truyền
 m || m m’ H
 So sánh
 h
 h’
 H
 Tấn công:
 Bản tin 
 Thay m bằng m’
 toàn vẹn?
 Tính lại h’ = H(m’)
 Bên gửi Bên nhận
 38
 19
38
 HMAC
 • Hashed MAC: xây dựng MAC dựa trên hàm băm
 k ⨁ ipad m[0] m[1] m[2] || PB
 IV
 (fixed)
 h h h h
 h0 h1 h2 h3 h4
 tag
 k⨁opad h
 h
 IV
 PB: Padding Block
 39
39
 HMAC và MAC
 • HMAC có tính chống đụng độ chắc chắn hơn do 
 sử dụng hàm băm
 • Tốc độ tính toán của HMAC nhanh hơn
 • Kích thước giá trị tag được tạo bởi HMAC lớn 
 hơn an toàn hơn trước các tấn công
 40
 20
40
 H(k||m) có an toàn?
 41
41
 4. TẤN CÔNG VÀO TÍNH ĐỤNG ĐỘ
 42
 21
42
 Tấn công vét cạn
 • Đụng độ trong MAC: tồn tại m1 ≠ m2 mà S(k, m1) 
 = S(k, m2)
 • Đụng độ trong hàm băm: tồn tại m1 ≠ m2 mà 
 H(m1) = H(m2)
 • Nhắc lại: sự tồn tại các bản tin đụng độ dẫn đến 
 các nguy cơ tấn công vào sơ đồ xác thực
 • Tìm ra bản tin đụng độ: có thể thực hiện vét cạn 
 số bản tin cần tính tối thiểu là bao nhiêu sẽ 
 chắc chắn thành công?
43
 Nghịch lý ngày sinh (Birthday paradox)
 • Bài toán: Khi chọn n người bất kỳ, xác suất để có tối thiểu 
 2 người có trùng ngày sinh là bao nhiêu?
 • Số cách chọn ra n người bất kỳ: 365n
 • Số cách chọn ra n người không có cặp nào trùng ngày 
 n
 sinh: 365 x 364 x  x (365-(n-1)) = C 365
 • Xác suất để chọn ra n người không có cặp nào trùng 
 ngày sinh
 365 × 364 × ⋯ × (365 − ( − 1))
  =
 365
 • Xác suất cần tính: P = 1 – Q
 • n = ? để P > 0.5 (cứ 2 lần chọn thì có 1 lần thỏa mãn) 
 44
 22
44
 Nghịch lý ngày sinh
 45
45
 Tấn công dựa trên nghịch lý ngày sinh 
 (Birthday paradox attack)
 • Kiểm tra 2n/2 bản tin có xác suất tìm ra các bản tin 
 đụng độ là ~ 0.5
 • Cách thức tấn công:
 Bước 1: Chọn ra 2n/2 bản tin ngẫu nhiên
 Bước 2: Tính mã băm/MAC cho các bản tin
 Bước 3: Kiểm tra sự tồn tại của các bản tin 
 đụng độ. Nếu không có, quay lại bước 1.
 Kỳ vọng: thành công sau 2 lần thử
 46
 23
46