Bài giảng Hàm băm mật mã môn Bảo mật thông tin | Đại học Bách Khoa Hà Nội

2023 ThS. Nguyễn Chí Hiếu 2023 1 Hàm băm mật mã 2023
An toàn bảo mật Hệ thống thông tin 2 2 1 2023 Nội dung
 Giới thiệu hàm băm mật mã
 Các tính chất của hàm băm mật mã  Hàm băm MD5 2023
An toàn bảo mật Hệ thống thông tin 3 3
Giới thiệu hàm băm mật mã
 Hàm băm (hash function) là hàm toán học biến đổi thông điệp
có chiều dài bất kỳ thành một thông điệp rút gọn/giá trị băm
(chuỗi 𝑛 bit) có chiều dài cố định. ℎ = 𝐻 (𝑀)
 ℎ : giá trị băm, 𝑀 : thông điệp (đầu vào của hàm băm),  𝐻 : hàm băm.
 Đầu ra của hàm băm được gọi là thông điệp rút gọn (message
digest) hay giá trị băm (hash value). 2023
An toàn bảo mật Hệ thống thông tin 4 4 2 2023
Giới thiệu hàm băm mật mã
 Hàm băm mật mã (cryptographic hash functions) là một
loại hàm băm được ứng dụng trong an toàn và bảo mật thông tin.
 Phải thỏa một số tính chất để kẻ tấn công không thể
tìm được thông điệp ban đầu, hoặc được dùng để kiểm tra dữ liệu toàn vẹn. 2023
An toàn bảo mật Hệ thống thông tin 5 5
Giới thiệu hàm băm mật mã Hàm băm Mã hóa Hàm 1 chiều Hàm 2 chiều
Băm bản rõ thành thông điệp có chiều dài Biến đổi bản rõ thành bản mã, và có thể cố định
biến đổi ngược lại bản rõ
Đảm bảo toàn vẹn dữ liệu Bảo mật dữ liệu 2023
An toàn bảo mật Hệ thống thông tin 6 6 3 2023
Giới thiệu hàm băm mật mã Thông điệp hay khối dữ liệu 𝑴
 Hàm băm mật mã là một hàm nén chiều dài bất kỳ
(hàm phi tuyến) mất thông tin.
 Chiều dài của giá trị băm phải đủ
lớn để chống lại một số loại tấn
công. Chiều dài thường là: 128, 256, 512, … bit Giá trị băm 𝒉 chiều dài cố định 2023
An toàn bảo mật Hệ thống thông tin 7 7
Các tính chất của hàm băm mật mã
 Hàm băm mật mã phải có những tính chất sau:
 Nén (compression): thông điệp đầu vào có chiều dài bất kỳ và
giá trị băm có chiều dài cố định.
 Tính hiệu quả (eficiency) khi cài đặt phần cứng và phần mềm.
 Tính một chiều (one-way).
 Tính chống đụng độ yếu (weak collision resistance).
 Tính chống đụng độ mạnh (strong collision resistance). 2023
An toàn bảo mật Hệ thống thông tin 8 8 4 2023 Tính một chiều  Cho ℎ ∈ 0,1
với 𝑛 > 0 là chiều dài của giá trị băm, rất khó tìm 𝒙 sao cho:  𝐻 (𝑥) = ℎ 𝑥 ℎ 𝐻: 0,1 ∗ → 0,1
 Chống tấn công tiền ảnh (pre-image resistance). 2023
An toàn bảo mật Hệ thống thông tin 9 9
Tính an toàn với “Đụng độ mạnh”
 Rất khó tìm 𝒙′ và 𝒙′ sao cho:
𝑥 = 𝑥 và 𝐻(𝑥) = 𝐻(𝑥 ) 𝑥 𝑥′ 𝐻: 0,1 ∗ → 0,1
 Chống đụng độ (collision resistance) 2023
An toàn bảo mật Hệ thống thông tin 10 10 5 2023
Tính an toàn với “Đụng độ yếu”
 Cho 𝑥 ∈ 0,1 ∗, rất khó tìm 𝒙 ≠ 𝒙′ sao cho: 𝐻(𝑥) = 𝐻(𝑥 ) 𝑥 𝑥′ 𝐻: 0,1 ∗ → 0,1
 Chống tấn công tiền ảnh thứ 2 (pre-image resistance). 2023
An toàn bảo mật Hệ thống thông tin 11 11
Sự liên quan giữa các tính chất
 An toàn với hiện tượng đụng độ “mạnh” thì an toàn
tính an toàn với hiện tượng đụng độ “yếu”.
 An toàn với hiện tượng đụng độ “yếu” không đảm bảo
an toàn với hiện tượng đụng độ “mạnh”. 2023
An toàn bảo mật Hệ thống thông tin 12 12 6 2023 Ứng dụng của hàm băm
 Chứng thực (authentication)
 Kiểm tra tính toàn vẹn (integrity) của dữ liệu
 Chống thoái thác/chối bỏ (non-repudiation)  … 2023
An toàn bảo mật Hệ thống thông tin 13 13 Ứng dụng của hàm băm
 Chứng thực (authentication) nhằm thực hiện chức năng
đăng nhập vào một hệ thống nào đó bằng mật khẩu đã
đăng ký và lưu trong cơ sở dữ liệu.
 Chống tấn công tiền ảnh 
 Chống tấn công tiền ảnh thứ 2   Chống đụng độ  2023
An toàn bảo mật Hệ thống thông tin 14 14 7 2023 Ứng dụng của hàm băm
An Il ustrated Guide to Cryptographic Hashes (unixwiz.net) 2023
An toàn bảo mật Hệ thống thông tin 15 15
Vấn đề chứng thực bằng mật khẩu
 Mật khẩu (password) là một dãy gồm các ký số và các
ký tự, được dùng để đăng nhập vào một hệ thống nào đó.
 Đây chính là yếu tố thường bị kẻ tấn công khai thác. 2023
An toàn bảo mật Hệ thống thông tin 16 16 8 2023
Vấn đề chứng thực bằng mật khẩu
 Bảo vệ mật khẩu bằng hàm băm
 Thường kết hợp thêm kỹ thuật “Rắc muối” (salting) 2023
An toàn bảo mật Hệ thống thông tin 17 17 Ứng dụng của hàm băm
 Kiểm tra tính toàn vẹn (integrity) của dữ liệu nhằm
phát hiện dữ liệu đã bị thay đổi bất hợp pháp.
 Chống tấn công tiền ảnh 
 Chống tấn công tiền ảnh thứ 2   Chống đụng độ  2023
An toàn bảo mật Hệ thống thông tin 18 18 9 2023 Ứng dụng của hàm băm
 Kiểm tra tính toàn vẹn (integrity) của dữ liệu
 Server: cung cấp giá trị băm tương ứng tập tin.
 Client: sau khi tải tập tin, tính lại giá trị băm và so sánh với
giá trị băm do server cung cấp 2023
An toàn bảo mật Hệ thống thông tin 19 19 Ứng dụng của hàm băm
https://en.wikipedia.org/wiki/MD5 2023
An toàn bảo mật Hệ thống thông tin 20 20 10 2023 Ứng dụng của hàm băm
 Chống thoái thác/chối bỏ (non-repudiation) dùng để
ngăn chặn hành vi thoái thác việc một tổ chức/cá nhân
đã giao dịch với các bên khác.
 Chống tấn công tiền ảnh 
 Chống tấn công tiền ảnh thứ 2   Chống đụng độ  2023
An toàn bảo mật Hệ thống thông tin 21 21 Ứng dụng của hàm băm
An Il ustrated Guide to Cryptographic Hashes (unixwiz.net) 2023
An toàn bảo mật Hệ thống thông tin 22 22 11 2023
Các tính chất của hàm băm
 An toàn với hiện tượng đụng độ “mạnh” thì an toàn
tính an toàn với hiện tượng đụng độ “yếu”.
 An toàn với hiện tượng đụng độ “yếu” không đảm bảo
an toàn với hiện tượng đụng độ “mạnh”. 2023
An toàn bảo mật Hệ thống thông tin 23 23 Cấu trúc của hàm băm
 1990: MD4 (message digest) được thiết kế bởi Ronald Rivest
 1991: MD5 được phát triển từ MD4
 1995: SHA-1 (secure hash algorithm 1)
 2001: SHA-2 (SHA-256, SHA-384, SHA-512 2023
An toàn bảo mật Hệ thống thông tin 24 24 12 2023 Cấu trúc của hàm băm
 Merkle-Damgard đã đưa ra cấu trúc hàm băm là một quá trình lặp như sau:
1280px-Merkle-damgard.svg.png (1280×343) (wikimedia.org) 2023
An toàn bảo mật Hệ thống thông tin 25 25 Cấu trúc của hàm băm
 Đầu vào là thông điệp 𝑀 kích thước bất kỳ, có thể thêm
một số bit để kích thước phù hợp với thuật toán
 Chia thông điệp 𝑀 thành 𝑛 khối 𝑀 có kích thước bằng
nhau, với 𝑖 = 1,2, … , 𝑛
 Khởi tạo một giá trị 𝐻 hay được gọi véc tơ khởi tạo 𝐼𝑉
 Lặp quá trình các khối 𝑀 bằng một hàm 𝑓(𝐻 , 𝑀 )
 Đầu ra là giá trị băm 𝐻 của thông điệp 𝑀 2023
An toàn bảo mật Hệ thống thông tin 26 26 13 2023 Cấu trúc của hàm băm
 Sự ảnh hưởng của hàm 𝑓 đến giá trị băm 𝐻
 Hàm 𝑓 chống lại đụng độ => Giá trị băm 𝐻 chống lại đụng độ 2023
An toàn bảo mật Hệ thống thông tin 27 27
An Il ustrated Guide to Cryptographic Hashes (unixwiz.net) 2023
An toàn bảo mật Hệ thống thông tin 28 28 14 2023 MD5
 MD5 được Ronald Rivest giới thiệu năm 1991, là
cải tiến của MD4 trước đó
 Đầu vào: thông điệp với độ dài bất kỳ.
 Đầu ra: giá trị băm 128 bit (16 byte).
 Thuật toán xử lý theo từng khối 512 bit (64 byte) 2023
An toàn bảo mật Hệ thống thông tin 29 29 2023
An toàn bảo mật Hệ thống thông tin 30 30 15 2023 MD5
 Bước 1: Tiền xử lý sao cho chiều dài thông điệp là bội số của 512. 
Thêm bit 1 vào cuối thông điệp ban đầu. 
Thêm 𝑘 bit 0 vào cuối thông điệp sao cho 𝐿 = 448 𝑚𝑜𝑑 512 .Trong
đó, 𝐿 là chiều dài thông điệp sau khi thêm bit 1 và 𝑘 bit 0. 
Thêm 64 bit vào cuối thông điệp (64 bit biểu diễn chiều dài của thông điệp ban đầu). 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 31 31 MD5
 Bước 2: Chia thông điệp thành 𝑁 khối 𝑀 với 1 ≤
𝑖 ≤ 𝑁. Mỗi khối 𝑀 gồm 512 bit. 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 32 32 16 2023 MD5
 Bước 3: Khởi tạo 𝐻 (véc tơ khởi tạo - 𝐼𝑉)  𝐻
gồm 128 bit được chia thành 4 từ 32 bit 𝐴, 𝐵, 𝐶, 𝐷
 Với 𝐴, 𝐵, 𝐶 , 𝐷 là các hằng số sau:  𝐴 = 0𝑥67452301
 𝐵 = 0𝑥𝐸𝐹𝐶𝐷𝐴𝐵89  𝐶 = 0𝑥98BADCFE  𝐷 = 0𝑥10325476 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 33 33 MD5
 Bước 4: Lặp i = 1 đến 𝑁
 Khối 𝑀 kết hợp với giá trị khởi tạo 𝐻 thông qua hàm
phi tuyến 𝐹 để tính giá trị 𝐻 . 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 34 34 17 2023 MD5  Bước 5: Xuất 𝐻
là giá trị băm của thông điệp. 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 35 35 Hàm của MD5
 Đầu vào: 𝑀 (512 bit) và 𝐻 (128 bit).  Đầu ra: 𝐻 (128 bit).
 Hàm nén (hàm phi tuyến) 𝐹
thực hiện qua 64 vòng lặp.
 Phép toán ⊞ là phép cộng modulo 2 . 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 36 36 18 2023
 Bước 1: Chia 𝑀 thành 16 từ 32 bit 𝑊 , 𝑊 , … , 𝑊  Bước 2: Chia 𝐻
thành 4 từ 32 bit 𝐴 ,𝐵 ,𝐶 ,𝐷 .
 Bước 3: Lặp 𝑗 = 0 → 63
 𝑡 = 𝐴 + 𝑓 𝐵 , 𝐶 , 𝐷 + 𝐾 + 𝑊 sj  𝐷 =𝐶  𝐶 =𝐵  𝐵
= 𝐵 + 𝑅𝑂𝑇𝐿 𝑡, 𝑠 , với 𝑅𝑂𝑇𝐿 𝑡, 𝑠 = 𝑡 ⋘ 𝑠  𝐴 =𝐷  Bước 4: Tính 𝐻
 𝐻 = 𝐴 + 𝐴 , 𝐵 + 𝐵 , 𝐶 + 𝐶 , 𝐷 + 𝐷 . 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 37 37
 Tính 𝑓 𝐵, 𝐶, 𝐷 và 𝑔 𝑗 theo quy ước sau:  0 ≤ 𝑗 ≤ 15
 𝑓 𝐵, 𝐶, 𝐷 = 𝐵 ∧ 𝐶 ∨ ¬𝐵 ∧ 𝐷 , 𝑔 𝑗 = 𝑗  16 ≤ 𝑗 ≤ 31
 𝑓 𝐵, 𝐶, 𝐷 = 𝐷 ∧ 𝐵 ∨ ¬𝐷 ∧ 𝐶 ,
𝑔 𝑗 = 5 × 𝑗 + 1 𝑚𝑜𝑑 16  32 ≤ 𝑗 ≤ 47
 𝑓 𝐵, 𝐶, 𝐷 = 𝐵⨁𝐶⨁𝐷,
𝑔 𝑗 = 3 × 𝑗 + 5 𝑚𝑜𝑑 16  48 ≤ 𝑗 ≤ 63
 𝑓 𝐵, 𝐶, 𝐷 = 𝐶⨁ 𝐵 ∨ ¬𝐷 ,
𝑔 𝑗 = 7 × 𝑗 𝑚𝑜𝑑 16 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 38 38 19 2023 Hàm của MD5 (tt)
 Hằng số 𝐾 tính theo công thức 𝐾 = 𝑠𝑖𝑛 𝑗 + 1 2 .
 Trong hàm 𝑅𝑂𝑇𝐿 𝑡, 𝑠 , số bit xoay vòng 𝑠 được quy định theo bảng sau 𝑠 𝒋 2014
Khoa Công Nghệ Thông Tin | Đại học Cửu Long 39 39 Hỏi & Đáp  Cám ơn đã theo dõi 2023
An toàn bảo mật Hệ thống thông tin 40 40 20