Bài giảng Mật mã ứng dụng: Hàm băm kháng xung đột

Mật mã ứng dụng

Hàm băm kháng xung đột

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

Nhắc lại: Toàn vẹn thông điệp

MAC xây dựng dựa trên PRF: ・ECBC-MAC, CMAC : Thường dùng với AES (Ví dụ, 802.11i) ・NMAC: làm cơ sở cho HMAC ・PMAC: một MAC song song

MAC ngẫu nhiên: ・Carter-Wegman MAC: dựa trên one-time MAC nhanh

Tiếp theo: ・xây dựng MAC dựa trên tính kháng xung đột

Tính kháng xung đột

Định nghĩa. Xét hàm băm H: M →T với |M| >> |T|. Một xung đột cho H

là một cặp m0 , m1 ∈ M thỏa mãn :

H(m0) = H(m1) và m0 ≠ m1

Định nghĩa. Hàm H được gọi là kháng xung đột nếu với mọi thuật toán

“hiệu quả” (tường minh) A:

AdvCR[A,H] = Pr[ A output xung đột cho H ]

là “không đáng kể”.

Ví dụ: ・SHA-256: Output là 256 bit.

Xây dựng MAC từ hàm kháng xung đột

Xây dựng. Xét I = (S, V) là MAC cho thông điệp ngắn trên (K, M, T) (Ví dụ,

AES). Xét hàm băm H: Mbig → M.

Ta định nghĩa Ibig = (Sbig , Vbig ) trên (K, Mbig, T) như sau:

Sbig(k,m) = S(k,H(m)) ; Vbig(k, m, t) = V(k, H(m), t)

Định lý. Nếu I là một MAC an toàn và H hàm kháng xung đột, vậy thì

Ibig là MAC an toàn.

Ví dụ: ・S(k, m) = AES2-block-cbc(k, SHA-256(m)) là một MAC an toàn.

Xây dựng MAC từ hàm kháng xung đột

Sbig(k,m) = S(k,H(m)) ; Vbig(k, m, t) = V(k, H(m), t)

Tính kháng xung đột là cần:

・Nếu kẻ tấn công có thể tìm được m0 ≠ m1 sao cho H(m0) = H(m1), ・vậy thì MAC không còn an toàn trước tấn công chọn 1 bản rõ:

– bước 1: kẻ tấn công truy vấn t ⟵S(k, m0)

– bước 2: output (m1 , t) là cặp thông điệp/tag giả mạo

Bảo vệ sự toàn vẹn của file dùng hàm băm kháng xung đột

Không gian chung (chỉ đọc)

…

Gói phần mềm:

File F1 File F2 File Fn H(F1) H(F2) …

H(Fn)

Toàn vẹn: ・Khi người dùng download file, chị ta có thể kiểm tra nội dung có khớp

・H kháng xung đột (cid:15482) kẻ tấn công không thể sửa gói phần mềm mà

với mã băm

・Không cần khóa (mọi người đều có thể kiểm tra tính toàn vẹn), nhưng

không bị phát hiện

cần không gian lưu trữ công khai

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

Thuật toán tấn công hàm băm

・Xét hàm băm H: M → {0,1}n với |M| >> 2n ・Thuật toán sau cho phép tìm xung đột sau O(2n/2) lần băm.

n/2

Thuật toán:

1. Chọn 2n/2 thông điệp ngẫu nhiên trong M: m1, …, m2

(với xác suất chúng phân biệt là cao)

2. For i = 1, …, 2n/2 :

tính ti = H(mi) ∈ {0,1}n.

・Khả năng thành công của thuật toán này như thế nào?

3. Tìm xung đột (ti = tj). Nếu không thấy thì quay lại bước 1.

Nghịch lý ngày sinh nhật

Định lý. Xét các số nguyên r1, …, rn ∈ {1,…,B} có phân phối giống nhau.

Pr[ ∃i≠j: ri = rj ] ≥ ½

Khi n = 1.2 × B1/2 thì ta có

Pr[

= j : ri = r j] = 1

Chứng minh.

Pr[ B

= j : ri B 1

= r j] 2

= 1

n + 1 B

· · · n

Å 1

Å n

i/B

ã 1

= 1

ã Å i B

1 n

i=1 Y

i=1 i

ex ≥ 1 - x

P n2/(2B)

= 1 1

0.72

= 0.53

i=1 Å Y 1/B e e e

6 6 6

B = 106

# samples n

Thuật toán tấn công hàm băm H: M → {0,1}n

n/2

Thuật toán:

1. Chọn 2n/2 thông điệp ngẫu nhiên trong M: m1, …, m2

(xác suất chúng phân biệt nhau là cao)

2. For i = 1, …, 2n/2 :

tính ti = H(mi) ∈ {0,1}n.

・Kỳ vọng số vòng lặp cần thực hiện gần bằng 2

・Thời gian chạy: O(2n/2) và không gian O(2n/2)

3. Tìm xung đột (ti = tj). Nếu không thấy thì quay lại bước 1.

Một số hàm băm kháng xung đột Crypto++5.6.0 [Wei Dai]

hàm

mã băm (số bit)

tốc độ (MB/giây)

thời gian tấn công

SHA-1

160

153

280

2128

SHA-256

256

111

2256

SHA-512

512

2256

Whirlpool

512

AMD Opteron, 2.2 GHz (Linux)

* thuật toán tốt nhất tìm xung đột cho SHA-1 cần 251 lần tính mã băm.

Thuật toán lượng tử

Thuật toán cổ điển

Thuật toán lượng tử

O( |K| )

O( |K|1/2 )

Tấn công vét cạn hệ mã khối  E: K × X ⟶ X

O( |T|1/2 )

O( |T|1/3 )

Tìm xung đột cho hàm băm H: M ⟶ T

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

Nhắc lại: Hàm băm kháng xung đột

Định nghĩa. Xét hàm băm H: M →T với |M| >> |T|. Một xung đột cho H

là một cặp m0 , m1 ∈ M thỏa mãn :

H(m0) = H(m1) và m0 ≠ m1

Mục đích: ・Xây dựng hàm băm kháng xung đột

Bước đầu tiên: ・Cho một hàm băm kháng xung đột cho thông điệp kích thước nhỏ, ・hãy xây dựng hàm băm cho thông điệp kích thước lớn.

Xây dựng theo sơ đồ Merkle-Damgard

m[0]

m[1]

m[2]

m[3] ll PB

H(m) IV (fixed)

H1 H0 H2 H3 H4

Cho trước hàm nén h: T × X ⟶ T

・Hàm băm H: X≤L ⟶ T .

Xây dựng:

1000…0 ll msg len

64 bits

・Nếu không đủ không gian cho padding, vậy thì thêm block mới.

Padding:

Tính kháng xung đột cho sơ đồ MD

Định lý. Nếu h là kháng xung đột, vậy thì H xây dựng theo sơ đồ trước

cũng là kháng xung đột.

Chứng minh. ・xung đột cho H (cid:15482) xung đột cho h

Vấn đề

Làm thế nào xây dựng được hàm băm kháng xung đột cho thông điệp kích thước nhỏ?

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

Hàm nén từ mã khối

Xây dựng. Xét hệ mã khối E : K× {0,1}n ⟶ {0,1}n . Hàm nén Davies-Meyer

xây dựng bởi: mi

⨁

h(H, m) = E(m, H) ⨁ H

Định lý. Giả sử E là một hệ mã lý tưởng (tập gồm |K| hoán vị ngẫu nhiên).

Tìm một xung đột h(H, m) = h(H’, m’) mất O(2n/2) lần tính (E,D).

Hãy chọn đáp án đúng

• Giả sử ta định nghĩa

• Vậy thì hàm h(.,.) không kháng xung đột:

• để tìm xung đột (H,m) và (H’,m’) ta chọn ngẫu nhiên (H,m,m’)

• và xây dựng H’ như sau:

h(H, m) = E(m, H)

1. H’=D(m’, E(m,H))

2. H’=E(m’, D(m,H))

3. H’=E(m’, E(m, H))

4. H’=D(m’, D(m,H))

Các cách xây dựng khác

• Để đơn giản, ta xét E: {0,1}n × {0,1}n ⟶ {0,1}n

• Miyaguchi-Preneel: h(H, m) = E(m, H)⨁H⨁m (Whirlpool)

h(H, m) = E(H⨁m, m)⨁m

• Các biến thể khác là không an toàn, ví dụ

có 12 biến thể như vậy

h(H, m) = E(m, H)⨁m (Bài tập)

Case study: SHA-256

・Merkle-Damgard function ・Davies-Meyer compression function ・Block cipher: SHACAL-2

SHACAL-2

512-bit key

256-bit block

Hàm nén có thể chứng minh an toàn

• Chọn một số nguyên tố ngẫu nhiên p kích thước 2000-bit và các số ngẫu

• Với mỗi m, h ∈ {0,…,p-1} ta định nghĩa

nhiên 1 ≤ u, v ≤ p .

h(H, m) = uH ⋅ vm (mod p)

Sự kiện. Tìm xung đột cho h(.,.) là khó như giải bài toán “discrete- log” modun p.

Vấn đề: hàm nén này chậm.

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

Nhắc lại: Xây dựng theo sơ đồ Merkle-Damgard

m[0]

m[1]

m[2]

m[3] ll PB

H(m) IV (fixed)

H1 H0 H2 H3 H4

Định lý. h kháng xung đột (cid:15482) H kháng xung đột.

Câu hỏi: ・Liệu chúng ta có thể sử dụng H(.) trực tiếp để xây dựng MAC ?

MAC từ hàm băm theo sơ đồ Merkle-Damgard

・Xét H: X≤L ⟶ T là một hàm băm kháng xung đột theo sơ đồ

Xây dựng thử nghiệm:

・Ta xây dựng

Merkle-Damgard

・MAC này là không an toàn bởi vì:

S(k, m) = H( k || m)

1. Cho H( k ll m) có thể tính H( w ll k ll m ll PB) với mọi w.

2. Cho H( k ll m) có thể tính H( k ll m ll w ) với mọi w.

3. Cho H( k ll m) có thể tính H( k ll m ll PB ll w ) với mọi w.

4. Mọi người đều có thể tính H( k ll m ) với mọi m.

Phương pháp chuẩn: HMAC (Hash-MAC)

Được dùng rộng rã trên Internet

Hàm băm H ・Ví dụ: SHA-256 ; output là 256 bits

HMAC: S(k, m) = H( k ⊕ opad ll H( k ⊕ ipad ll m ) )

Ta xây dựng MAC từ hàm băm:

Hình mô tả HMAC

m[0]

m[1]

m[2] ll PB

k⨁ipad

IV (fixed)

k⨁opad

tag

IV (fixed)

Tương tự như NMAC PRF ・khác biệt chính: hai khóa k1 và k2 phụ thuộc nhau.

Tính chất của HMAC

・Xây dựng từ cài đặt của SHA-256

・HMAC được giả sử là một PRF an toàn

– Có thể chứng minh với một số giả sử PRF về h(.,.) – Chặn về an toàn tương tự như NMAC:

・Trong TLS: có hỗ trợ HMAC-SHA1-96

Khi q2/|T| là “không đáng kể”.

HÀM BĂM KHÁNG XUNG ĐỘT

‣ Giới thiệu

‣ Tấn công dùng nghịch lý ngày sinh

‣ Sơ đồ Merkle-Damgard

‣ Xây dựng hàm nén

‣ HMAC: MAC dựa trên SHA256

h t t p s : / / c l a s s . c o u r s e r a . o r g /

c r y p t o - p r e v i e w / c l a s s / i n d e x

‣ Timing Attack cho MAC

Chú ý: Timing Attacks vào hàm kiểm tra

Ví dụ. Keyczar crypto library (Python) [Đã đơn giản hóa]

def Verify(key, msg, sig_bytes):

return HMAC(key, msg) == sig_bytes

Vấn đề: ・Cài đặt của phép toán ‘==‘ so sánh tuần tự từng byte ・Sẽ trả lại false ngay khi gặp byte khác nhau đầu tiên.

Chú ý: Timing Attacks vào hàm kiểm tra

m , tag k

target   msg m

accept or reject

Timing attack: ・Để tính tag cho một thông điệp m ta thực hiện:

1. Truy vấn server để lấy một tag ngẫu nhiên

2. Lặp lại mọi khả năng của byte đầu tiên và gửi đến server, dừng khi

hàm verification chạy nhanh hơn so với thời gian thực hiện bước 1

3. Lặp lại với mọi byte trong tag cho đến khi tìm được tag.

Chống Timing Attack #1

Phương pháp ・Đảm bảo rằng phép toán so sánh sẽ luôn thực hiện với thời gian bằng

nhau trên mọi dữ liệu

return false if sig_bytes has wrong length result = 0 for x, y in zip( HMAC(key,msg) , sig_bytes): result |= ord(x) ^ ord(y) return result == 0

Vấn đề: ・Không đảm bảo được việc trình biên dịch không sửa lại đoạn mã trong

khi tối ưu

Chống Timing Attack #2

Phương pháp ・Đảm bảo rằng phép toán so sánh sẽ luôn thực hiện với thời gian bằng

nhau trên mọi dữ liệu

def Verify(key, msg, sig_bytes): mac = HMAC(key, msg) return HMAC(key, mac) == HMAC(key, sig_bytes)

Đảm bảo ・ Kẻ tấn công không biết giá trị nào đang được so sánh.

Bài giảng Mật mã ứng dụng: Hàm băm kháng xung đột - Đại học Bách khoa Hà Nội

Tags: