Bài giảng Mật mã ứng dụng: Mã xác thực thông điệp

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

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

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

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

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

Toàn vẹn thông điệp: MAC (Message Authentication Code)

thông điệp m

tag

Alice

Bob

k k

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’

Toàn vẹn thông điệp cần một khóa bí mật

thông điệp m

tag

Bob

Alice

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.

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 ti ← S(k, mi) của m1, m2,…,mq

(m, t) /

(m1, t1),

, (mq, cq)

2 {

· · ·

}

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

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

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

m2,

, mq

· · ·

MAC như sau:

t2,

, tq

2 S(k, m1)

· · ·

(m, t)

Thử thách k ← K Kẻ tấn công

(m1, t1),

, (mq, tq)

2 {

· · ·

}

n∏u V (k, m, t) = ’yes’ và (m, t) / ng˜Òc l§i

b = 1 b = 0

Đị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ể”

Câu hỏi

Xét I=(S,V) là một MAC.

= m1

Giả sử một kẻ tấn công có thể tìm được 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

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.

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 F1 File F2 File Fn

khóa k được sinh từ mật khẩu người dùng

tag=S(k, F1) tag=S(k, F2) tag=S(k, Fn)

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

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

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

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 ti ← S(k, mi) của m1, m2,…,mq

(m, t) /

(m1, t1),

, (mq, cq)

2 {

· · ·

}

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

Kẻ tấn công không thể tạo tag hợp lệ cho một thông điệp mới

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 ]

thông điệp m

tag

Alice

Bob

k k

Sinh tag: chấp nhận nếu

tag ← F(k, m) tag = F(k,m)

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 .

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

Tóm tắt chứng minh

Nếu f : X → Y là một hàm ngẫu nhiên thực sự.

m1, m2,

, mq

Vậy thì thuật toán A tấn công MAC phải thắng trong trò chơi sau:

· · ·

Thử thách

f (m1), f (m2),

, f (mq)

· · ·

f thuộc Funs[X,Y]

(m, t)

và

m1,

, mq

t = f (m)

Kẻ tấn công

m / 2

· · ·

A thắng nế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?

• CBC-MAC (Ngân hàng - ANSI X9.9, X9.19, FIPS 186-3)

• HMAC (Giao thức cho Internet: SSL, IPSec, SSH,…)

Trả lời: Có hai cách xây dựng được dùng trong thực tế.

Cả hai cách này đều chuyển từ một PRF nhỏ thành PRF-lớn.

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).

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

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

MAC và PRF

Nhắc lại: ・PRF an toàn F (cid:15482) MAC an toàn, khi |Y| lớn. ・Cách xây dựng: S(k, m) = F(k, m)

Mục đích của chúng ta: ・Từ PRF cho thông điệp ngắn (Ví dụ AES), tìm cách xây dựng PRF cho

thông điệp dài tùy ý.

Xây dựng 1: ECBC-MAC (CBC-MAC được mã hóa)

m[0]

m[1]

m[3]

m[4]

⊕

raw CBC

F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅)

tag F(k1,⋅)

Xét F: K x X ⟶ X là PRF.

FEC BC : K 2

X 

⇥

Ta định nghĩa PRF:

Xây dựng 2: NMAC (nested MAC)

m[0]

m[1]

m[3]

m[4]

cascade

t k

>

F F F F t ll fpad

>

tag

F k1

Xét F: K x X ⟶ K là PRF.

FNMAC : K 2

X 

⇥

Ta định nghĩa PRF:

Tại sao trong bước cuối của ECBC-MAC và NMAC phải mã hóa?

NMAC. Giả sử ta định nghĩa MAC I = (S, V) với

S(k, m) = cascade(k,m)

1. MAC này là an toàn.

2. MAC này có thể bị giả mạo mà không cần truy vấn bất kỳ thông điệp

nào.

3. MAC này có thể bị giả mạo bằng cách truy vấn một thông điệp.

4. MAC này có thể bị giả mạo chỉ bằng truy vấn hai thông điệp.

Tại sao trong bước cuối của ECBC-MAC phải mã hóa?

Giả sử ta định nghĩa MAC IRAW = (S, V) với

S(k, m) = rawCBC(k, m)

Vậy thì IRAW có thể bị phá dễ dàng dùng tấn công chọn 1 thông điệp.

• Chọn một thông điệp chỉ một khối m ∈ X.

• Truy vấn để lấy tag cho m. Anh ta được t = F(k, m).

• Output t như một MAC giả cho thông điệp gồm 2 khối (m, t⊕m).

Kẻ tấn công thực hiện:

Thật vậy,

rawCBC(k, (m, t⊕m) ) = F(k, F(k, m) ⊕ (t⊕m) ) = F(k, t⊕(t⊕m) ) = t

Phân tích ECBC-MAC và NMAC

Định lý. Với mọi L > 0, với mọi thuật toán “hiệu quả” với q-truy vấn A

tấn công FECBC hoặc FNMAC, có tồn tại một thuật toán “hiệu quả” B thỏa

mãn:

AdvMAC[A, FECBC] ≤ AdvPRF[B, F] + 2 q2 / |X|

AdvMAC[A, FNMAC] ≤ qL AdvPRF[B, F] + 2 q2 / |K|

CBC-MAC: an toàn khi q << |X|1/2

NMAC: an toàn khi q << |K|1/2 (264 cho AES-128)

Ví dụ

Từ bất đẳng thức

AdvMAC[A,FECBC] ≤ AdvPRF[B, F] + 2q2 / |X|

・với q là số thông điệp được MAC với khóa k.

Giả sử ta muốn

⇐ q2 / |X| < 1/232

AdvMAC[A, FECBC] ≤ 1/232

・AES: |X| = 2128 vậy thì q < 248

– Vậy sau 248 thông điệp, chúng ta phải đổi khóa.

・3DES: |X| = 264 vậy thì q < 216

– Vậy sau 216 thông điệp, chúng ta phải đổi khóa.

Chặn trên cho tính an toàn là chặt: một cách tấn công

・Sau khi ký

|X|1/2 thông điệp với ECBC-MAC hoặc

|K|1/2 thông điệp với NMAC

thì MAC không còn an toàn.

・Giả sử khung PRF F là một PRP (ví dụ, AES)

– Vậy thì cả hai PRF (ECBC và NMAC) có tính chất mở rộng sau:

∀x, y, w: FBIG(k, x) = FBIG(k, y) (cid:15482) FBIG(k, xllw) = FBIG(k, yllw)

– Tính chất này cho ta một cách tấn công MAC.

Tính chất mở rộng của ECBC-MAC

m[0]

m[1]

m[3]

m[4]

⊕

raw CBC

F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅)

tag F(k1,⋅)

∀x, y, w: FECBC(k, x) = FECBC(k, y) (cid:15482) FECBC(k, xllw) = FECBC(k, yllw)

Tính chất mở rộng của NMAC (nested MAC)

m[0]

m[1]

m[3]

m[4]

cascade

t k

>

F F F F t ll fpad

>

tag

F k1

∀x, y, w: FNMAC(k, x) = FNMAC(k, y) (cid:15482) FNMAC(k, xllw) = FNMAC(k, yllw)

Tấn công MAC có tính chất mở rộng

Cho PRF FBIG: K × X ⟶ Y be có tính chất mở rộng:

∀x, y, w: FBIG(k, x) = FBIG(k, y) (cid:15482) FBIG(k, xllw) = FBIG(k, yllw)

MAC xây dựng từ PRF trên có thể bị tấn công theo thuật toán sau:

Bước 1: gửi |Y|1/2 truy vấn ngẫu nhiên cho các thông điệp trong X.

đạt được ( mi, ti ) for i = 1 ,…, |Y|1/2

Bước 2: tìm một xung đột tu = tv for u≠v (với xác suất cao là tìm

được theo nghịch lý ngày sinh)

Bước 3: chọn một w và truy vấn để lấy t := FBIG(k, mullw)

Bước 4: đưa ra cặp giả mạo (mvllw, t).

Thật vậy t := FBIG(k, mvllw).

Sơ đồ an toàn hơn: Xây dựng ngẫu nhiên RCBC

2 blocks

>

rawCBC t

t a g

rawCBC

rand. r trong X

・PRF: F: K × X ⟶ X ・Kết quả: MAC với tag trong X2 ・Tính an toàn:

AdvMAC[A, IRCBC] ≤ AdvPRF[B, F] ⋅(1 + 2q2/|X|)

・Ví dụ: Với 3DES, ta có thể ký q=232 thông điệp với cùng một khóa.

So sánh

ECBC-MAC thường dùng là MAC dựa trên AES ・Mode mã hóa CCM (dùng trong 802.11i) ・Chuẩn NIST gọi là CMAC

NMAC thường không dùng với AES hoặc 3DES ・Lý do chính: phải đổi khóa AES trên mọi block (cid:15482) phải tính lại AES key

expansion.

・Nhưng NMAC là cơ sở cho MAC được dùng phổ biên là HMAC.

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

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

Nhắc lại: ECBC-MAC

m[0]

m[1]

m[3]

m[4]

⊕

raw CBC

F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅)

tag F(k1,⋅)

Xét F: K x X ⟶ X là PRF.

FEC BC : K 2

X 

⇥

Ta định nghĩa PRF:

Nếu kích thước thông điệp không là bội của block-size thì sao?

m[0]

m[3]

???

m[1]

m[4]

⊕

tag

F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅)

F(k1,⋅)

CBC MAC padding

m[0]

m[1]

m[0]

0000

m[1]

Ý tưởng ngây thơ: pad m với dãy 0

Câu hỏi. MAC thu được có an toàn?

1. Có, MAC này an toàn.

2. Còn phụ thuộc vào thiết kế chi tiết của MAC.

3. Không, nếu lấy được tag của m, kẻ tấn công cũng lấy được tag của

mll0.

CBC MAC padding

Để an toàn, padding phải khả nghịch, tức là:

m0 ≠ m1 (cid:15482) pad(m0) ≠ pad(m1)

m[0]

100

m[0]

m[1]

m’[0]

m’[1]

1000…000

m’[1]

m’[0]

ISO. pad với “1000…00”. Thêm block giả nếu cần. ・Số ‘1’ chỉ ra vị trí bắt đầu của pad.

CMAC (Chuẩn NIST)

Là một biến thể của ECBC-MAC: với key = (k, k1,k2) ・Không cần bước mã hóa cuối (tấn công mở rộng bị chặn bằng cách xor

với khóa cuối)

・Không cần block giả (nhập nhằng được loại bỏ bằng cách sử dụng khóa

m[w]

m[0]

m[1]

m[0]

m[1]

100

k1 hoặc k2)

⊕

⋯ ⋯

k1 k2

tag

F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅) F(k,⋅)

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

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

Vấn đề

・Cả ECBC và NMAC là tuần tự. ・Liệu chúng ta có thể xây dựng một MAC song song từ một PRF nhỏ?

Xây dựng 3: PMAC - MAC song song

m[0]

m[1]

m[2]

m[3]

P(k,0)

P(k,2)

P(k,1)

P(k,3)

⊕

F(k1,⋅) F(k1,⋅) F(k1,⋅)

⊕

Padding tương tự CMAC

tag

key = (k, k1)

F(k1,⋅)

P(k, i): một hàm dễ tính toán

Xét PRF F: K × X ⟶ X Ta định nghĩa PRF mới FPMAC : K2 × X≤L ⟶ X

PMAC: Phân tích

Định lý. Với mọi L > 0, nếu F là một PRF an toàn trên (K,X,X) thì FPMAC

là một PRF an toàn trên (K, X≤L, X).

Cụ thể, với mọi thuật toán hiệu quả A dùng q-truy vấn tấn công FPMAC,

có tồn tại thuật toán hiệu quả B thỏa mãn:

AdvMAC[A, FPMAC] ≤ AdvPRF[B, F] + 2 q2L2 / |X|.

・PMAC an toàn khi qL << X1/2

PMAC cho phép cập nhật hiệu quả

m[0]

m[1]

m[2]

m[3]

P(k,0)

P(k,2)

P(k,1)

P(k,3)

⊕

tag

F(k1,⋅) F(k1,⋅) F(k1,⋅)

F(k1,⋅)

Câu hỏi. Giả sử F là một PRP. Khi m[1] thay đổi thành m’[1], liệu chúng ta có thể cập nhật nhanh tag?

1. Không, ta không thể 2. Tính tag ⨁ F(k1, m[1] ⨁ P(k,1)) ⨁ F(k1, m’[1] ⨁ P(k,1)) 3. Tính F-1(k1,tag) ⨁ F(k1, m[1] ⨁ P(k,1)) ⨁ F(k1, m’[1] ⨁ P(k,1)) 4. Tính F-1(k1,tag) ⨁ F(k1, m’[1] ⨁ P(k,1)) sau đó tính F(k1, .)

MAC với khóa dùng một lần

Xét MAC I = (S, V) và một kẻ tấn công A, ta định nghĩa một trò chơi MAC

như sau:

2 S(k, m1)

(m, t)

Thử thách k ← K Kẻ tấn công

= (m1, t1)

b = 1 n∏u V (k, m, t) = ’yes’ và (m, t) b = 0 ng˜Òc l§i

Định nghĩa. I=(S,V) là một MAC an toàn nếu với mọi thuật toán hiệu

quả A :

Adv1MAC[A, I] = Pr[Thử thách output 1] là “không đáng kể”.

Ví dụ: MAC với khóa dùng một lần

Mục tiêu. ・an toàn chống lại mọi kẻ tấn công và nhanh hơn MAC dựa trên PRP

Xây dựng: ・Xét q là một số nguyên tố lớn (ví dụ, q = 2128 + 51)

– key = (a,b) ∈ {1,…,q}2 (hai số nguyên ngẫu nhiên thuộc [1,q] )

– msg = ( m[1], …, m[L] ) với mỗi khối là một số nguyên 128 bit.

S( key, msg ) = Pmsg(a) + b (mod q)

với Pmsg(x) = xL+1 + m[L]⋅xL + … + m[1]⋅x là một đa thức bậc L+1

Ta sẽ chứng minh: ・cho S( key, msg1 ) kẻ tấn công không có thông tin gì về S( key, msg2 )

Tính an toàn của One-time MAC

Định lý. MAC xây dựng như trong slide trước thỏa mãn (L=msg-len)

∀m1≠m2, t1, t2:

Pra,b[ S( (a,b), m1) = t1 | S( (a,b), m2) = t2] ≤ L/q

Chứng minh. ∀m1≠m2, t1, t2:

2(a)+b = t2 ] = 1/q

(1) Pra,b[ S( (a,b), m2) = t2] = Pra,b[ Pm

(2) Pra,b[ S( (a,b), m1) = t1 và S( (a,b), m2) = t2] =

Pra,b[ Pm1(a) - Pm2(a)=t1-t2 và Pm2(a)+b=t2 ] ≤ L/q2 ∎

One-time MAC (cid:15482) Many-time MAC

• Xét (S,V) là một one-time MAC an toàn trên (KI,M, {0,1}n ) . • Xét F: KF × {0,1}n ⟶ {0,1}n là một PRF an toàn.

Carter-Wegman MAC: CW( (k1,k2), m) = (r, F(k1,r) ⨁ S(k2,m) ) với số ngẫu nhiên r ⟵ {0,1}n .

Định lý. Nếu (S,V) là một one-time MAC an toàn và F là một PRF an

toàn, vậy thì CW là một MAC an toàn với output là tag thuộc {0,1}2n .

Câu hỏi

CW( (k1,k2), m) = (r, F(k1,r) ⨁ S(k2,m) )

Làm thế nào để kiểm tra tag (r, t) cho thông điệp m? Nhắc lại rằng V(k2, m, .)

là thuật toán kiểm tra cho one time MAC.

1. Chạy V( k2, m, F(k1, t) ⨁r) )

2. Chạy V( k2, m, r )

3. Chạy V( k2, m, t )

4. Chạy V( k2, m, F(k1, r) ⨁ t) )

Xây dựng 4: HMAC (Hash-MAC)

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

… nhưng, trước hết ta cần xem xét khái niệm hàm băm mật mã.

Tài liệu đọc thêm và trình bày

・J. Black, P. Rogaway: CBC MACs for Arbitrary-Length Messages: The

Three-Key Constructions. J. Cryptology 18(2): 111-131 (2005)

・K. Pietrzak: A Tight Bound for EMAC. ICALP (2) 2006: 168-179 ・J. Black, P. Rogaway: A Block-Cipher Mode of Operation for

Parallelizable Message Authentication. EUROCRYPT 2002: 384-397

・M. Bellare: New Proofs for NMAC and HMAC: Security Without Collision-

Resistance. CRYPTO 2006: 602-619

・Y. Dodis, K. Pietrzak, P. Puniya: A New Mode of Operation for Block

Ciphers and Length-Preserving MACs. EUROCRYPT 2008: 198-219

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