Bài giảng An toàn hệ thống thông tin - Chương 3a: Hàm băm mật mã học (Crytographic hash functions)

07/01/2018

Chương 3a:

HÀM BĂM MẬT MÃ HỌC

(CRYTOGRAPHIC HASH FUNCTIONS)

GV: Nguyễn Thị Hạnh

Nội dung chính

1. Tổng quan về hàm băm (Hash Function)

2. Ứng dụng của hàm băm

3. Kiến trúc hàm băm

4. Hai hàm băm MD5 và SHA1

( Cryptography and Network Security: Principles

and Practices (3rd Ed.) – Chapter 11)

(Cryptography & Network Security. McGraw-Hill,

Inc., 2007., Chapter 12)

1

07/01/2018

Mục tiêu

˗ Giới thiệu ý tưởng tổng quát của hàm băm

mật mã học

° Định nghĩa hàm băm

° Tính chất hàm băm cần có

° Bài toán ngày sinh

˗ Nêu các ứng dụng của hàm băm

° Chứng thực thông điệp

° Chữ ký số

° Các ứng dụng khác

˗ Thảo luận cơ chế Merkle-Damgard như là kiến

trúc cơ bản của hàm băm

3

Mục tiêu

˗ Thảo luận vầ hàm băm MD5 và SHA1

° Sơ lược vầ MD5 và SHA1

° Sơ đồ tổng thể

° Cấu trúc hàm F tại mỗi bước

° Cấu trúc của một vòng trong F

° So sánh MD5 và SHA1

4

2

07/01/2018

1. Hàm băm (Hash Function)

˗ Hàm băm là các thuật toán không sử dụng

khóa để mã hóa, nó có nhiệm vụ băm thông

điệp được đưa vào theo một thuật toán h một

chiều nào đó, rồi đưa ra một bản băm – văn

bản đại diện – có kích thước cố định. Do đó

người nhận không biết được nội dung hay độ

dài ban đầu của thông điệp đã được băm

bằng hàm băm.

˗ Giá trị của hàm băm là duy nhất, và không

thể suy ngược lại được nội dung thông điệp

từ giá trị băm này.

5

1. Hàm băm (Hash Function)

˗ Input: M có kích

thước bất ky

̀

˗ Output – giá trị h có

kích thước cố định,

ngắn.

˗ H(x) – hàm một

chiều (“Khó để tính

nghịch đảo”)

6

3

07/01/2018

1. Hàm băm (Hash Function)

7

1. Hàm băm (Hash Function)

x₁

Thông điệp

x₂

y₁

Thông điệp

rút gọn

x₃

y₂

Không gian thông điệp

Không gian giá trị băm

8

‰Không gian giá trị Băm nhỏ hơn rất nhiều so

với Không gian thông điệp về mặt kích thước

‰chắc chắn sẽ tồn tại đụng độ (trùng), nghĩa

là có hai tin x và x” mà giá trị Băm của

chúng là giống nhau, tức là h(x) = h(x”)

4

07/01/2018

Tính chất hàm băm

1. Tính chống tiền ảnh (Preimage resistant – one-way

property):

Cho trước giá trị băm h việc tìm x sao cho H(x)=h là rất khó

2. Tính chống tiền ảnh thứ hai (Second preimage

resistant – weak collision resistant – Tính chống

trùng yếu):

Cho thông điệp đầu vào x, việc tìm một thông điệp x’ với

(x’≠ x) sao cho h(x’)=h(x) là rất khó

3. Tính chống trùng mạnh (Strong Collision resistant):

Không thể tính toán để tìm được hai thông điệp đầu vào

x₁≠ x₂sao cho chúng có cùng giá trị băm

(Nghịch lý ngày sinh – Birthday paradox)

9

Nghịch lý ngày sinh (birthday paradox)

Bài toán 1: Giả sử trong phòng có M sinh viên.

Vậy xác suất để có hai SV có cùng ngày sinh là

bao nhiêu phần trăm? (1 năm 365 ngày khác

nhau)

° Theo nguyên lý chuồng bồ câu Dirichlet: cần có

365+1 = 366 người để tìm thấy 2 người có cùng

ngày sinh với xác suất 100%. Vì vậy với 30 người

thì xác xuất này rất nhỏ. ‰ Rất nhỏ, đúng không

° Tính theo xác suất thống kê toán học thì

M(M-1) >=2 x 365 x log_e2 (*)

chỉ cần 23 người là đủ để xác suất hơn 50%. Vì vậy

bài toán này gọi là nghịch lý ngày sinh

10

5

07/01/2018

Nghịch lý ngày sinh (birthday paradox)

Điều này muốn nói lên rằng, trong nhiều trường

hợp xác suất để hai mẩu tin có cùng bản Hash là

không nhỏ như chúng ta nghĩ.

‰Tính chống trùng mạnh

11

Nghịch lý ngày sinh (birthday paradox)

Bài toán 2: Giả sử bạn đang ở trong một lớp học

với M sinh viên. Hỏi M tối thiểu là bao nhiêu để

tồn tại một bạn khác có cùng ngày sinh với bạn

với xác suất (XS) lớn hơn 50%?

° XS để 1 người khác ngày sinh với bạn là 364/365.

° ‰XS để M người đều khác ngày sinh với bạn là (364/365)^M.

° ‰XS để tồn tại ít nhất một người có cùng ngày sinh với bạn

là: 1-(364/365)^M

° Để XS này >50% Ï M>=253 người

‰Tính chống trùng yếu

12

6

07/01/2018

Nghịch lý ngày sinh (birthday paradox)

˗

13

Nghịch lý ngày sinh (birthday paradox)

˗ Để tìm ra hai thông điệp có cùng giá trị băm

(vét cạn) thì phải thử bao nhiêu thông điệp

khác nhau?

‰Phải thử khoảng 2^n/2thông điệp khác nhau

(xác suất > 50%)

˗ Ví dụ: Nếu n=128 thì phải thử 2⁶⁴thông điệp

(khá lớn), nghĩa là hàm hăm đạt được tính

chống trùng mạnh (tương được tấn công vét

cạn khóa của DES)

14

7

07/01/2018

2. Ứng dụng hàm băm

˗ Chứng thực thông điệp

(Message Authentication)

˗ Chữ ký số

(Digital Signatures)

˗ Các ứng dụng khác

(Other Applications)

15

2.1 Message Authentication

˗ Là một cơ chế/dịch vụ được dùng để kiểm

tra tính toàn vẹn của một thông điệp.

˗ Đảm bảo rằng dữ liệu nhận được là chính xác

như khi được gửi (không bị chỉnh sửa, chèn,

hoặc thay thế)

˗ Trong nhiều trường hợp, có một yêu cầu là cơ

chế chứng thực phải hỗ trợ nhận dạng người

gửi (sender) là hợp pháp.

˗ Hàm băm dạng này, giá trị băm (h) được gọi là

tóm tắt thông điệp hoặc cốt thông điệp

(message digest)

16

8

07/01/2018

2.1 Message Authentication

˗ Ví dụ cơ chế chứng thực đơn giản

17

2.1 Message Authentication

˗ Ví dụ cơ chế chứng thực đơn giản (tt)

18

9

07/01/2018

2.2 Digital Signatures

˗ Giá trị băm của thông điệp được mã hóa bằng

private key của user, bất kỳ ai biết public key

của user thì có thể thẩm tra thông điệp mà

được gắn kết với chữ ký số.

˗ Kẻ tấn công muốn hiệu chỉnh thông điệp thì sẽ

cần phải biết private key của user.

19

2.2 Digital Signatures

˗ Ví dụ:

20

10

07/01/2018

2.3 Other Applications

Dùng lưu trữ mật khẩu (băm password):

˗ Hàm băm được dùng để tạo one-way

password file, trong cơ chế này giá trị băm

của password được lưu, điều này tốt hơn là

lưu chính bản rõ password. ‰ password

không bị truy xuất bởi kẻ tấn công nơi chứa

password.

˗ Khi user nhập vào một password, thì giá trị

băm của password được so với giá trị băm

được lưu để kiểm tra.

21

2.3 Other Applications

Dùng nhận diện xâm hại (intrusion detection)

và nhận diện virus (virus detection).

˗ Tính, lưu và bảo mật giá trị băm H(F) của các

tập tin trong hệ thống (thể lưu trên CD-R)

˗ Kẻ xâm hại cần phải hiệu chỉnh F mà không

thay đổi H(F)

22

11

07/01/2018

2.3 Other Applications

˗ Dùng:

Xây dựng hàm ngẫu nhiên giả

(pseudorandom function - PRF)

hoặc

Phát sinh số ngẫu nhiên giả

(pseudorandom number generator - PRNG)

23

3. Kiến trúc hàm băm an toàn

˗ Cơ chế Merkle-Damgard

˗ Tác giả: Ralph Merkle, Ivan Damgård

˗ Hầu hết các hàm băm đều sử dụng cấu trúc này

˗ Ví dụ: SHA-1, MD5

24

12

07/01/2018

4. Hàm băm MD5, SHA1

˗ MD5 (Message Digest)

° Phát minh bởi Ron Rivest (RSA)

° Phát triển từ MD4, trước đó MD2 (không an toàn)

° Kích thước giá trị băm là 128-bit

° 1994 và 1998: một pp tấn công MD5 và một số

thông điệp có cùng giá trị băm MD5 được chỉ ra (vi

phạm tính chống trùng mạnh). Tuy nhiên MD5 vẫn

còn sử dụng phổ biến

25

4. Hàm băm MD5, SHA1

˗ SHA (Secure Hash Algorithm)

° Được phát triển bởi NIST 1993 (SHA-0)

° 1995: SHA-1 - Chính phủ Mỹ chọn làm chuẩn quốc

gia. Kích thước giá trị băm 160-bit

° Hiện nay còn có SHA-224, SHA-256, SHA-384,

SHA-512

26

13

07/01/2018

4.1 Hàm băm MD5 (128-bit, ≤2⁶⁴-bit)

˗ Sơ đồ tổng thể

H₀– 128-bit, chia thành 4 từ 32-bit, ký hiệu a,b,c,d – hằng số (thập lục phân)

a=01234567; b=89abcdef; c=fedbca98; d=76543210

27

4.1 Hàm băm MD5 (128-bit, ≤2⁶⁴-bit)

˗ Cấu trúc hàm F tại mỗi bưới lũy tiến

K_j: phần nguyên của 2³²abs(sin(i)) với i biểu diễn radian

M_iđược biến đổi qua hàm message schedule cho ra W₀, W₁, .., W₆₃

mỗi giá trị 32-bit

28

14

07/01/2018

4.1 Hàm băm MD5 (128-bit, ≤2⁶⁴-bit)

Cấu trúc của một vòng trong F

Ở đây: b‰c, c‰d, d‰a, b được

tính qua hàm

t=a+f(b,c,d)+W_i+K_i

b=b+ROTL(t,s)

Hàm f(x,y,z):

f(x,y,z)=(x y) (¬ x z) nếu vòng 0 – 15

f(x,y,z)=(z x) (¬ z y) nếu vòng 16 – 31

f(x,y,z)=x y x nếu vòng 32 – 48

f(x,y,z)=y (x ¬ z) nếu vòng 49 – 63

Hàm ROTL(t,s): t được dịch vòng

trái s-bit, với s là các hằng số cho

vòng thứ i

Phép + (hay ≥) là phép cộng

modulo 2³²

29

4.1 Hàm băm MD5 (128-bit, ≤2⁶⁴-bit)

˗ Hàm ROTL(t,s): t

được dịch vòng trái

s-bit, với s là các

hằng số cho vòng

thứ i

30

15

07/01/2018

4.2 Hàm băm SHA-1 (160-bit, 2⁶⁴-bit)

˗ Sơ đồ tổng thể của SHA1 cũng giống như MD5, kích

thước của giá trị băm tại mỗi bước là 160-bit.

H₀– 160-bit, chia thành 5 từ 32-bit, ký hiệu a,b,c,d,e – hằng số

a=67452301; b=efcdab89; c=98badcfe; d=10325476; e=c3d2e1f0

31

4.2 Hàm băm SHA-1 (160-bit, 2⁶⁴-bit)

˗ Cấu trúc hàm F cũng tương tự MD5, nhưng được

thực hiện 80 vòng

K_ilà hằng sô

́

K_i=5A827999 với 0≤i ≤19

K_i=6ED9EBA1 với 20≤i ≤39

K_i=8F1BBCDC với 40≤i ≤59

K_i=CA62C1D6 với 60≤i ≤79

Gia

́

trị M_i– biến đổi qua message

trị như sau:

M_ichia thành 16 block 32-bit

schedule cho ra 80 gia

́

-

ứng với W₀, W₁,…, W₁₅.

Các W_t(16≤t ≤79) được tính:

W_t=ROTL(W_t-3+W_t-8+W_t-14+W_t-

₁₆,1)

với phép cộng modulo 2³²

32

16

07/01/2018

4.2 Hàm băm SHA-1 (160-bit, 2⁶⁴-bit)

Cấu trúc của một vòng trong F

Ở đây: a‰b, c‰d, d‰e. Giá trị a và c

được tính:

a=ROTL(a,5)+f(b,c,d)+e+W_i+K_i

c=ROTL(b,30)

Hàm f(x,y,z):

f(x,y,z)=Cf(x,y,z)=(x y) (−|x z) nếu vòng 0 – 19

f(x,y,z)=Parity(x,y,z)= x y z nếu vòng 20 – 39

f(x,y,z)=Maj(x,y,z)=(x y) (y z) (z x) nếu vòng

40 – 59

f(x,y,z)=Party(x,y,z)= x y z nếu vòng 60 – 79

°

Hàm Maj: giải sử x_i, y_i, z_ilà bit thứ i của x,y,z

thì bit thứ i của hàm Maj là giá trị nào chiếm đa

số, 0 hoặc 1

°

Hàm Ch: bit thứ i của hàm Ch là phép chọn: if

x_ithen y_ielse x_i

33

So sánh giữa MD5 và SHA-1

˗ Khả năng chống lại tấn công brute-force:

° Để tạo ra thông điệp có giá trị băm cho trước, cần 2¹²⁸thao

tác với MD5 và 2¹⁶⁰với SHA-1

°

Để tìm 2 thông điệp có cùng giá trị băm, cần 2⁶⁴thao tác với

MD5 và 2⁸⁰với SHA-1

˗ Khả năng chống lại thám mã: cả 2 đều có cấu trúc tốt

˗ Tốc độ:

° Cả hai dựa trên phép toán 32 bit, thực hiện tốt trên các kiến

trúc 32 bit

° SHA-1 thực hiện nhiều hơn 16 bước và thao tác trên thanh

ghi 160 bit nên tốt độ thực hiện chậm hơn

˗ Tính đơn giản: cả hai đều được mô tả đơn giản và dễ

dàng cài đặt trên phần cứng và phần mềm

34

17

07/01/2018

Câu hỏi và bài tập

1. Về mặt lý thuyết, giá trị băm có thể trùng

không? Vậy tại sao nói giá trị băm có thể xem

là “dấu vân tay của thông điệp”

2. Tìm hiểu phương pháp sử dụng hàm băm

MD5 và SHA trong thư viện .NET, viết

chương trình mã hóa password lưu trữ và

kiểm tra password.

3. Trình bày kiến trúc cơ bản của hàm băm (cơ

chế Merkle-Damgard)

35

18

Bài giảng An toàn hệ thống thông tin - Chương 3a: Hàm băm mật mã học (Crytographic hash functions) - Nguyễn Thị Hạnh