Bài giảng Mật mã ứng dụng: Mã xác thực thông điệp - Đại học Bách khoa Hà Nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

12
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Mật mã ứng dụng: Mã xác thực thông điệp" trình bày các nội dung chính sau đây: Toàn vẹn thông điệp; MAC dựa trên PRF; CBC-MAC và NMAC; MAC padding; PMAC và Carter-Wegman MAC;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Mật mã ứng dụng: Mã xác thực thông điệp - Đại học Bách khoa Hà Nội

Mật mã ứng dụng Mã xác thực thông điệp
MÃ XÁC THỰC THÔNG ĐIỆP ‣ Toàn vẹn thông điệp ‣ MAC dựa trên PRF ‣ CBC-MAC và NMAC ‣ MAC padding ‣ PMAC và Carter-Wegman MAC https://class.coursera.org/ crypto-preview/class/index
MÃ XÁC THỰC THÔNG ĐIỆP ‣ Toàn vẹn thông điệp ‣ MAC dựa trên PRF ‣ CBC-MAC và NMAC ‣ MAC padding ‣ PMAC và Carter-Wegman MAC https://class.coursera.org/ crypto-preview/class/index
Toàn vẹn thông điệp Mục đích ・Toàn vẹn, không cần bí mật Ví dụ ・Bảo vệ các file công khai trên đĩa ・Bảo vệ các banner quảng cáo trên trang web 4
Toàn vẹn thông điệp: MAC (Message Authentication Code) k k thông điệp m tag Alice Bob Sinh tag: Kiểm tra tag: ? tag ← S(k, m) V(k,m,tag) = ‘yes’ Định nghĩa. MAC I = (S, V) định nghĩa trên (K, M, T) là một cặp thuật toán: - S(k, m) output t thuộc T - V(k, m, t) output ‘yes’ hoặc ‘no’ 5
Toàn vẹn thông điệp cần một khóa bí mật thông điệp m tag Alice Bob Sinh tag: Kiểm tra tag: ? tag ← CRC(m) V(m,tag) = ‘yes’ ・Kẻ tấn công có thể dễ dàng thay đổi thông điệp và tính lại CRC (Cyclic redundancy check). ・CRC được thiết kế để phát hiện lỗi xảy ra ngẫu nhiên chứ không chống được lỗi có chủ đích. 6
MAC an toàn Khả năng của kẻ tấn công ・ kẻ tấn công có thể lấy được các tag t ← S(k, m ) của m , m ,…,m i i 1 2 q Mục đích của kẻ tấn công: Giả mạo thông điệp ・đưa ra được một cặp thông điệp/tag (m, t) hợp lệ mới (m, t) 2 {(m1 , t 1 ), · · · , (mq , cq )} / Có nghĩa rằng: ・kẻ tấn công không thể tạo ra một tag hợp lệ cho một thông điệp mới ・đưa ra (m, t) kẻ tấn công thậm chí không tạo được (m, t’) với t’≠ t 7
MAC an toàn Cho MAC I = (S, V) và một kẻ tấn công A. Ta định nghĩa một thử nghiệm MAC như sau: Thử thác m1 2 M m2 , · · · , mq Kẻ k←K tấn côn t1 S(k, m1 ) t2, · · · , tq (m, t) b ® b=1 n∏u V (k, m, t) = ’yes’ và (m, t) 2 {(m1 , t 1 ), · · · , (mq , t q )} / b=0 ng˜Òc l§i Định nghĩa. MAC I = (S, V) là MAC an toàn nếu với mọi thuật toán “hiệu quả “ A: AdvMAC[A,I] = Pr[Thử thách output =1] là “không đáng kể” 8 g h
Câu hỏi Xét I=(S,V) là một MAC. Giả sử một kẻ tấn công có thể tìm được m0 6= m1 sao cho S(k, m0 ) = S(k, m1 ) với 1/2 số khóa k trong K. Vậy MAC này có an toàn không? 1. Có, kẻ tấn công không thể sinh tag đúng cho m0 hoặc m1 2. Không, MAC này có thể bị phá dùng tấn công chọn thông điệp 3. Nó phụ thuộc vào thiết kế của MAC 9
Câu hỏi Xét MAC I=(S,V) và giả sử S(k,m) luôn output dãy 5 bit. MAC này có an toàn không? 1. Không, kẻ tấn công có thể gợi ý tag cho các thông điệp 2. Nó phụ thuộc vào thiết kế chi tiết của MAC 3. Có, kẻ tấn công không thể sinh tag hợp lệ cho bất kỳ thông điệp nào. 10
Ví dụ: Bảo vệ hệ thống files Giả sử tại thời điểm cài đặt hệ thống tính toán: File File File F1 F2 Fn … tag=S(k, F1) tag=S(k, F2) tag=S(k, Fn) khóa k được sinh từ mật khẩu người dùng Sau đó hệ thống bị nhiễm virus, và các file bị sửa đổi. Người dùng khởi động lại vào OS sạch và nhập mật khẩu ・Khi đó: MAC an toàn sẽ cho phép phát hiện các file bị sửa đổi 11
MÃ XÁC THỰC THÔNG ĐIỆP ‣ Toàn vẹn thông điệp ‣ MAC dựa trên PRF ‣ CBC-MAC và NMAC ‣ MAC padding ‣ PMAC và Carter-Wegman MAC https://class.coursera.org/ crypto-preview/class/index
Nhắc lại: MAC an toàn MAC: ・Thuật toán ký: t ← S(k, m) ・Thuật toán kiểm tra: V(k,m,t) = ‘yes’ hoặc ‘no’ Khả năng của kẻ tấn công ・ kẻ tấn công có thể lấy được các tag t ← S(k, m ) của m , m ,…,m i i 1 2 q Mục đích của kẻ tấn công: Giả mạo thông điệp ・đưa ra được một cặp thông điệp/tag (m, t) hợp lệ mới (m, t) 2 {(m1 , t 1 ), · · · , (mq , cq )} / Kẻ tấn công không thể tạo tag hợp lệ cho một thông điệp mới 13
MAC an toàn từ PRF an toàn Xét PRF F : K x X → Y ta định nghĩa MAC IF = (S, V) bởi ・S(k, m) := F(k, m) ・V(k, m, t) := [ ‘yes’ nếu t = F(k,m) ; ’no’ nếu ngược lại ] k k thông điệp m tag Alice Bob Sinh tag: chấp nhận nếu tag ← F(k, m) tag = F(k,m) 14
Câu hỏi Giả sử F : K x X → Y là một PRF an toàn với Y={0,1}10 . MAC IF có phải là hệ MAC an toàn ? 1. Có, MAC là an toàn vì PRF là an toàn. 2. Không, độ dài tag quá ngắn: người ta có thể gợi ý ngẫu nhiên tag cho thông điệp bất kỳ. 3. Phụ thuộc vào thiết kế chi tiết của hàm F . 15
Tính an toàn Định lý. Nếu F : K x X → Y là một PRF an toàn và 1/|Y| là “không đáng kể” (tức là |Y| lớn), vậy thì IF là một MAC an toàn. Cụ thể, với mọi thuật toán “hiệu quả” A tấn công MAC IF có tồn tại một thuật toán “hiệu quả” B tấn công PRF F thỏa mãn: AdvMAC[A,IF] ≤ AdvPRF[B,F] + 1/|Y| IF là an toàn khii |Y| lớn, ví dụ |Y| = 280 16
Tóm tắt chứng minh Nếu f : X → Y là một hàm ngẫu nhiên thực sự. Vậy thì thuật toán A tấn công MAC phải thắng trong trò chơi sa : Thử thác m1 , m2 , · · · , mq 2 X Kẻ tấn côn t1 f (m1 ), f (m2 ), · · · , f (mq ) f thuộc Funs[X,Y] (m, t) t = f (m) và m 2 m1 , · · · , mq / A thắng nếu 17 g h u
Ví dụ: AES là một MAC với thông điệp độ dài 16 byte. Câu hỏi: làm thế nào chuyển từ MAC nhỏ sang MAC lớn? Trả lời: Có hai cách xây dựng được dùng trong thực tế. • CBC-MAC (Ngân hàng - ANSI X9.9, X9.19, FIPS 186-3) • HMAC (Giao thức cho Internet: SSL, IPSec, SSH,…) Cả hai cách này đều chuyển từ một PRF nhỏ thành PRF-lớn. 18
Chặt bớt MAC dựa trên PRF Bổ đề dễ. Giả sử F : K x X → {0,1}n là một PRF an toàn. Vậy thì Ft (k, m) := F(k, m)[1…t] với mọi 1≤t≤n cũng là PRF an toàn. Hệ quả. Nếu (S, V) là một MAC dựa trên PRF an toàn với output là tag độ dài n-bit, vậy thì MAC bị cắt chỉ lấy w bit cũng là an toàn khi 1/2w là “không đáng kể” (Ví dụ, w ≥ 64). 19
MÃ XÁC THỰC THÔNG ĐIỆP ‣ Toàn vẹn thông điệp ‣ MAC dựa trên PRF ‣ CBC-MAC và NMAC ‣ MAC padding ‣ PMAC và Carter-Wegman MAC https://class.coursera.org/ crypto-preview/class/index