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

1BÀ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 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 21. ĐẶT VẤN ĐỀ 3 1. Đặt vấn đề 4 Kênh truyền Alice Bob Mallory M M’ M’’ Thay đổi nội dung M thành M’ Hoặc, bản tin M’’ giả danh Alice 3 4 3Xá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 Tấn công thay thế • Chặn thông điệp, thay đổi nội dung và chuyển tiếp cho bên kia 6 Alice Bob“Tôi là Alice. Số tài khoản của tôi là 456. Hãy chuyển tiền cho tôi!” Kẻ tấn công “Tôi là Alice. Số tài khoản của tôi là 123. Hãy chuyển tiền cho tôi!” Kênh truyền 5 6 4Tấn công giả danh • Kẻ tấn công mạo danh một bên và chuyển các thông điệp cho bên kia. 7 Alice Bob “Tôi là Alice. Đây là số tài khoản của tôi. Hãy chuyển tiền cho tôi!” Kẻ tấn công “Tôi là Bob. Đây là số tài khoản của tôi. Hãy chuyển tiền cho tôi!” Tấn công phủ nhận gửi • Bên gửi phủ nhận việc đã gửi đi một thông tin 8 Alice Bob “Tôi là Alice. Hãy chuyển tiền của tôi vào tài khoản 123!” “Tôi là Bob. Tôi đã chuyển tiền của cô vào tài khoản 123.” “Không. Tôi chưa bao giờ yêu cầu chuyển tiền của tôi vào tài khoản 123!” 7 8 52. MÃ XÁC THỰC THÔNG ĐIỆP (MAC) 9 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 10 Alice BobS V M t K K 9 10 6MAC – Ví dụ 1 11 Khách hàng chuyển khoản 1. Chia sẻ khóa k 2. m = SoTK || money 3. t = S(k, m) Kẻ tấn công 1. Không biết k 2. Tạo m’ = SoTK’||money 3. Tạo t’ Thay đổi số tài khoản nhận tiền Mã MAC cho phép phát hiện thông tin bị sửa đổi Ngân hàngV m t m’ t' V (k, m’, t’) = False V (k, m t) = True MAC – Ví dụ 2: Phần mềm Tripwire 12 • Khi cài đặt, tính giá trị MAC của các file cần bảo vệ • 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) F t = S(k, F) file F’ t = S(k, F) file V(k, F’, t) = False 11 12 7An toàn của MAC • 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 13 Thử thách 1. Sinh khóa k 3. Tính ti = S(k, mi) 5. b = V(k, m, t) Tấn công 2. Chọn m1, ..., mq 4. Chọn m và sinh t sao cho (m,t)  {(m1,t1),...,(mq,tq)} m1,...,mq t1,...,tq m, t b = {true,false} An toàn của MAC • MAC còn an toàn không nếu tồn tại thuật toán hiệu quả cho một trong các tình huống sau: (1) Tìm được m* sao cho S(?, m*) = t với t chọn trước (2) Tìm được m* sao cho S(?, m*) = S(?, m) với m chọn trước (3) Tìm được m và m* sao cho S(?, m*) = S(?, m) • Hoặc giá trị t có kích thước 10 bit 14 13 14 8Độ 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 15 Ví dụ tấn công vào tính đụng độ (1) Kẻ tấn công(Mr. Tung) tìm đượ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 16 15 16 9Xây dựng MAC: CBC-MAC 17 Mã hóa Mã hóa Mã hóa m[0] m[1] m[2] m[3]   Mã hóa  tag k1 k1 k1 k1 Mã hóa k2 t k = (k1, k2) Tại sao? rawCBC rawCBC-Tấn công chọn trước bản rõ t S(k,) m Vấn đề: S(k, m || tm ) = S(k, S(k,m)(tm) ) = S(k, t(tm) ) = S(k,m) = t  S(k,) m tm  S(k,) m t  t rawCBC rawCBC rawCBC 17 18 10 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? 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) 20 19 20 11 Tấn công phát lại 21 Khách hàng chuyển khoản 1. K = KeyGen(l) 2. Xác thực thông tin CK: t = S(k, SoTK||money) Publish 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 Ngân hàngV Xây dựng MAC: CBC-MAC 22 Mã hóa Mã hóa Mã hóa m[0] m[1] m[2] m[3]   Mã hóa  tag k1 k1 k1 k1 Mã hóa k2 t k = (k1, k2) padding Kích thước thông điệp không chia hết cho kích thước một khối? 21 22 12 Padding cho CBC-MAC • Ý tưởng 1: Thêm vào các bit 0 • Không an toàn. Ví dụ: m[0] m[1] m[0] 000m[1] Same Tag $100 00 $10 000 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] 10000000 23 24 13 Tấn công CCA – Nhắc lại 25 Thử thách Sinh khóa k Chọn b ∈ {0, 1} c* = E(k, mb) Tấn công Sinh ci, mj Sinh m0, m1 Sinh c’i, m’j (c’i ≠ c*) Đoán b’ ∈ {0, 1} m0, m1 c* ci, mj c’i, m’j • 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) ≤ ½ + ε mi = D(k, ci) cj = E(k, mj) mi, cj m’i, c’j m’i = D(k, c’i) c’j = E(k, m’j) Mật mã có xác thực 26 • 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) Hàm mã hóa E: K x M x N  C 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 Từ chối giải mã các bản mã không hợp lệ 25 26 14 Một số sơ đồ sử dụng mã MAC 27 t m || m t’ m’ So sánht E D k1 k2 k2 k1 a) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng(SSL) t M So sánh E D K1 K1 b) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng (SSH) || t’ K2K2 S S S S V(k1, m’,t’) V(k1, m’,t’) Một số sơ đồ sử dụng mã MAC(tiếp) 28 t M So sánh E D K1 K1 c) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng(IPSec) || t’ K2K2 True • 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 S S M V(k1, c’, t’) 27 28 15 Nhận xét • Xác thực toàn vẹn bản rõ • Không xác thực toàn vẹn bản không phát hiện bản mật bị thay thế) • MAC chứa thông tin bản rõ • Có thể giảm sự an toàn mã mật • Xác thực toàn vẹn bản rõ • Không xác thực toàn vẹn bản mật(không phát hiện tấn công thay thế bản mật) • Không có thông tin về bản rõ từ MAC • Chỉ đảm bảo an toàn CCA khi mã ở chế độ rand-CBC hoặc rand-CTR • Xác thực toàn vẹn bản rõ • Xác thực toàn vẹn bản mật(có thể phát hiện bản mật bị thay thế) • MAC không chứa thông tin bản rõ • Luôn đảm bảo an toàn CCA Sơ đồ a Sơ đồ b Sơ đồ c 3.HÀM BĂM 30 29 30 16 Khái niệm 31 • 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 Một hàm băm đơn giản 32 • Chia thông điệp thành các khối có kích thước n- bit  Padding nếu cần • 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 không đủ an toàn để sử dụng trong bài toán xác thực thông điệp                           ln21 22221 11211 2 1 ... mmm mmm mmm m m m m ll n n l      nccc ...21   =H(m) 31 32 17 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 33 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 34 33 34 18 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 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 35 36 19 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ố • Cộng modulo 232 • <<<s: dịch trái s bit • ˄: 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 Mi Ti 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 37 38 20 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 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 39 40 21 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 41 m H || m h m’ h’ H So sánh Bản tin toàn vẹn? Bên gửi Bên nhận Tấn công: Thay m bằng m’ Tính lại h’ = H(m’) HMAC 42 • Hashed MAC: xây dựng MAC dựa trên hàm băm m[0] m[1] m[2] || PB h1 h2 h3 h4 h h h h IV k ⨁ ipad IV (fixed) h h k⨁opad tag PB: Padding Block 41 42 22 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 43 H(k||m) có an toàn? • Tấn công mở rộng kích thước (Length extension attack) • Có thể tính được H(k || m1 || m2) nếu biết H(k || m1) • Các hàm băm bị ảnh hưởng: MD5, SHA-1, SHA-2 44 43 44 23 4. TẤN CÔNG VÀO TÍNH ĐỤNG ĐỘ 45 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? 45 46 24 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 sinh: 365 x 364 x x (365-(n-1)) = Cn365 • 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) 47 Nghịch lý ngày sinh 48 47 48 25 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ử 49 49