Bài giảng An toàn an ninh thông tin - Chương 3: Xác thực thông điệp

BÀI 3.

XÁC THỰC THÔNG ĐIỆP

Bùi Trọng Tùng,

Viện Công nghệ thông tin và Truyền thông,

Đại học Bách khoa Hà Nội

1

Nội dung

• Các vấn đề xác thực thông điệp

• Mã xác thực thông điệp (MAC)

• Hàm băm và hàm băm mật HMAC

2

1

2

1. ĐẶT VẤN ĐỀ

3

1. Đặt vấn đề

M

Kênh truyền

Alice

Bob

Thay đổi nội dung

M thành M’

M’

Mallory

Hoặc, bản tin M’’

giả danh Alice

M’’

4

2

4

Xác thực thông điệp

• Bản tin phải được xác minh:

Nội dung toàn vẹn: bản tin không bị sửa đổi

Bao hàm cả trường hợp Bob cố tình sửa đổi

Nguồn gốc tin cậy:

Bao hàm cả trường hợp Alice phủ nhận bản tin

Bao hàm cả trường hợp Bob tự tạo thông báo và “vu khống”

Alice tạo ra thông báo này

Đúng thời điểm

Các dạng tấn công điển hình vào tính xác thực: Thay

thế (Substitution), Giả danh (Masquerade), tấn công

phát lại (Replay attack), Phủ nhận (Repudiation)

5

2. MÃ XÁC THỰC THÔNG ĐIỆP (MAC)

6

3

6

MessageAuthentication Code

• Hai bên đã trao đổi một cách an toàn khóa mật k

• Hàm MAC = (S, V) là một cặp thuật toán

• Sinh mã: t = S(k, m)

Đầu ra: kích thước cố định, không phụ thuộc kích thước

của M

• Xác minh: V(k, m, t)

Nếu t = S(k, m) thì V = true

Ngược lại V = false

M

t

Alice

S

V

Bob

K

7

MAC – Ví dụ 1

Khách hàng chuyển

khoản

1. Chia sẻ khóa k

2. Xác thực thông tin CK:

t = S(k,SoTK||money)

V (k, m t) = True

Ngân hàng

M

t

V

V (k, m’, t’) = False

M’ t'

Kẻ tấn công

Mã MAC cho phép

phát hiện thông tin bị

sửa đổi

t’ = S(?,SoTK’||money)

Thay đổi số tài

khoản nhận tiền

8

4

8

MAC – Ví dụ 2: Phần mềm Tripwire

• Khi cài đặt, tính giá trị MAC của các file cần bảo vệ

file

F

F’

t = S(k,F₁)

t = S(k, F₁)

V(k, F’, t) = False

• Khi máy tính khởi động, các file được kiểm tra mã MAC

 Cho phép phát hiện các file bị sửa đổi (ví dụ do nhiễm

virus)

9

An toàn của MAC

Thử thách

1. Sinh khóa k

Tấn công

m₁,...,m_q

t₁,...,t_q

2. Chọn m₁, ..., m_q

3. Tính t_i= S(k, m_i)

4. Chọn m và sinh t sao cho

(m,t)  {(m₁,t₁),...,(m_q,t_q)}

m, t

5. b = V(k, m, t)

b = {true,false}

• MAC là an toàn nếu với mọi thuật toán tấn công hiệu quả

thì xác suất P(b = true) ≤ ε

kẻ tấn công không thể tạo giá trị t hợp lệ nếu không có

khóa k

10

5

10

An toàn của MAC

MAC còn an toàn không nếu một trong các trường hợp

sau:

(1) Kẻ tấn công tìm được m* sao cho S(?, m*) = t với t

chọn trước

(2) Kẻ tấn công tìm được m* sao cho S(?, m*) = S(?, m)

với m chọn trước

(3) Kẻ tấn công tìm được m và m* sao cho S(?, m*) = S(?,

m)

(4) Giá trị t có kích thước 10 bit

11

Độ an toàn của MAC

• Giả sử m₁và m₂là hai bản tin có mã MAC giống nhau:

S(k, m₁) = S(k, m₂)

S(k, m₁||W) = S(k, m₂||W) với W bất kỳ

• Kịch bản tấn công:

1. Kẻ tấn công tính toán t_x= S(k, m_x) với x = 1, …, N

2. Tìm cặp bản tin (m_i, m_j) có t_i= t_j. Nếu không tìm thấy

thực hiện lại bước 1

3. Chọn bản tin W và tính t = S(k, m_i||W)

4. Thay m_i|| W bằng m_j|| W có lợi cho kẻ tấn công

12

6

12

Ví dụ tấn công vào tính đụng độ

(1) Kẻ tấn công(Mr. Tung) chọn được 2 bản tin có mã MAC

giống nhau:

m1: ‘I will pay 1’

m2: ‘I will pay 2’

Chọn W = ‘000$ to Mr.Tung’

m1 || W = ‘I will pay 1000$ to Mr.Tung’

m2 || W = ‘I will pay 2000$ to Mr.Tung’

(2) Đánh lừa người dùng gửi bản tin ‘I will pay 1000$ to

Mr.Tung’ || S(k, ‘I will pay 1000$ to Mr.Tung’) cho ngân

hàng

(3) Thay thế bằng ‘I will pay 2000$ to Mr.Tung’ || S(k, ‘I will

pay 1000$ to Mr.Tung’)  Ngân hàng chấp nhận

13

Xây dựng MAC: CBC-MAC

m[0]

m[1]

m[2]

m[3]



rawCBC

Tại sao?

k₁

Mã

hóa

k₁

Mã

hóa

Mã

hóa

k₁

Mã

hóa

tag

k = (k₁, k₂)

Mã

k₂

hóa

t

14

7

14

rawCBC-Tấn công chọn trước bản rõ

m

tm



rawCBC

m

rawCBC

S(k,)

t

Vấn đề: S(k, m || tm ) = S(k, S(k,m)(tm) ) =

S(k, t(tm) ) =

S(k,m) = t

15

An toàn của CBC-MAC

• Khóa được dùng nhiều lần  giảm độ an toàn

• Nếu gọi:

q: số bản tin được tính MAC cùng với khóa không đổi

|X|: Số lượng giá trị có thể của t

• Xác suất tấn công thành công ≤ 2*q²/ |X|

• Để xác suất tấn công là không đáng kể (≤ 2^-80) thì sau

bao nhiêu lần tính MAC phải đổi khóa?

8

16

Tấn công phát lại (Replay attack)

• Kẻ tấn công phát lại bản tin M đã được chứng

thực trong phiên truyền thông trước đó

• Thiết kế MAC không chống tấn công phát lại

 cần thêm các yếu tố chống tấn công phát lại

trong các giao thức truyền thông sử dụng MAC

• Một số kỹ thuật chống tấn công phát lại:

Giá trị dùng 1 lần(nonce): S(k, m || nonce)

Tem thời gian: S(k, m || timestamp)

17

Tấn công phát lại

Khách hàng chuyển

khoản

1. K = KeyGen(l)

Publish

Ngân hàng

V

2. Xác thực thông tin CK:

t = S(k, SoTK||money)

Kẻ tấn công

t = S(k, SoTK||money)

Sao chép và và phát lại

các yêu cầu chuyển khoản

18

9

18

Xây dựng MAC: CBC-MAC

Kích thước thông điệp không chia

hết cho kích thước một khối?

m[0]

m[1]

m[2]

m[3] padding



k₁

Mã

hóa

tag

k = (k₁, k₂)

Mã

k₂

hóa

t

19

Padding cho CBC-MAC

• Ý tưởng 1: Thêm vào các bit 0

m[0]

m[1]

m[0]

m[1] 00…0

• Không an toàn. Ví dụ:

$100

$10

00

000

Same Tag

10

20

Padding cho CBC-MAC

• Yêu cầu: M_i≠ M_jthì pad(M_i) ≠ pad(M_j)

• Chuẩn ISO/IEC 9797-1:

Sử dụng chuỗi padding bắt đầu bởi bit 1

Nếu kích thước thông điệp là bội số kích thước của khối, luôn thêm

1 khối padding

m[0]

m[1]

m[0]

m[1] 1000

m[1]

1000000000

21

Tấn công CCA– Nhắc lại

Thử thách

Tấn công

Sinh khóa k

c_i, m_j

Sinh c_i, m_j

m_i= D(k, c_i)

c_j= E(k, m_j)

m_i, c_j

Sinh m₀, m₁

m₀, m₁

Chọn b ∈ {0, 1}

c* = E(k, m_b)

c*

Sinh c’_i, m’_j(c’_i≠ c*)

c’_i, m’_j

m’_i, c’_j

m’_i= D(k, c’_i)

c’_j= E(k, m’_j)

Đoán b’ ∈ {0, 1}

• Hệ mật chống lại được tấn công CCA (độ an toàn IND-CCA)

nếu với mọi thuật toán tấn công hiệu quả thì P(b’ = b) ≤ ½ + ε

22

11

22

Mật mã có xác thực

• Các sơ đồ mật mã đã xem xét không chống lại được tấn

công CCA(chosen-cipher attack)

• Cách thức chung: kẻ tấn công sửa bản mã c* thành c’_ivà yêu cầu

giải mã

• Giải pháp: Mật mã có xác thực (E, D)

Từ chối giải mã các bản

mã không hợp lệ

Hàm mã hóa E: K x M x N  C

^{Hàm giải mã D: K x C x N }M ∪ {⊥}

• Trong đó N là một dấu hiệu sử dụng để xác thực

• Giải pháp: Kết hợp mật mã và mã MAC

• Khóa mã hóa và khóa xác thực phải khác nhau

23

Một số sơ đồ sử dụng mã MAC

k₁

k₂

m

’

E

||

S

m

t

D

So

sánh

m

t

t’

k₂

S

V(k₁, m’,t’)

a) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng(SSL)

k₁

K₂

K₁

K₂

D

S

So

sánh

||

E

M

t

t’

S

K₁

b) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng (SSH)

24

12

24

Một số sơ đồ sử dụng mã MAC(tiếp)

K₁

K₂

S

True

M

So

sánh

||

E

M

D

t

t’

S

K₁

c) Xác thực bằng MAC, bảo mật bằng mật mã khóa đối xứng(IPSec)

• Một số chuẩn:

GCM: Mã hóa ở chế độ CTR sau đó tính CW-MAC

CCM: Tính CBC-MAC sau đó mã hóa ở chế độ CTR (802.11i)

EAX: Mã hóa ở chế độ CTR sau đó tính CMAC

25

Nhận xét

Sơ đồ a

Sơ đồ b

Sơ đồ c

• Xác thực toàn vẹn

bản rõ

• Xác thực toàn

vẹn bản rõ

• Xác thực toàn

vẹn bản rõ

• Không xác thực

toàn vẹn bản

mật(không phát

hiện tấn công thay

thế bản mật)

• Không xác thực

toàn vẹn bản

không phát hiện

bản mật bị thay

thế)

• Xác thực toàn

vẹn bản mật(có

thể phát hiện bản

mật bị thay thế)

• MAC không chứa

thông tin bản rõ

• Không có thông tin

về bản rõ từ MAC

• MAC chứa thông

tin bản rõ

• Luôn đảm bảo an

toàn CCA

• Chỉ đảm bảo an

toàn CCA khi mã ở

chế độ rand-CBC

hoặc rand-CTR

• Có thể giảm sự

an toàn mã mật

13

26

3.HÀM BĂM

27

Khái niệm

• Hàm băm H: thực hiện phép biến đổi:

 Đầu vào: bản tin có kích thước bất kỳ

 Đầu ra: giá trị digest h = H(m)có kích thước n bit cố định (thường

nhỏ hơn rất nhiều so với kích thước bản tin đầu vào)

• Chỉ thay đổi 1 bit đầu vào, làm thay đổi hoàn toàn giá trị

đầu ra

• Ví dụ:

Đầu vào: “The quick brown fox jumps over the lazy dog”

Mã băm: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12

Đầu vào: “The quick brown fox jumps over the lazy cog”

Đầu ra: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3

28

14

28

Một hàm băm đơn giản

m

m₁₂ m







₁







_1n

11

• Chia thông điệp thành

các khối có kích thước n-

bit









m₂

...

m₂₁m₂₂ m_2n

m 









 Padding nếu cần

m_l

m_l1m_l2 m_ln

   

   

• Thực hiện XOR tất cả

các khối  mã băm có

kích thước n bit

• Tất nhiên, hàm băm này

không đủ an toàn để sử

dụng trong bài toán xác

thực thông điệp



c₁c₂... c_n



=H(m)

29

Yêu cầu đối với hàm băm

1. Có thể áp dụng với thông điệp m với độ dài bất kỳ

2. Tạo ra giá trị băm h có độ dài cố định

3. H(m) dễ dàng tính được với bất kỳ m nào

4. Từ h rất khó tìm được m sao cho h = H(m): tính một

chiều

5. Biết trước m₁rất khó tìm được m₂sao cho H(m₁) =

H(m₂)  tính chống đụng độ yếu

6. Rất khó tìm được cặp (m₁, m₂) sao cho H(m₁)=H(m₂) 

tính chống đụng độ mạnh

30

15

30

Một số hàm băm phổ biến

• MD5

 Kích thước digest: 128 bit

 Công bố thuật toán tấn công đụng độ (collision attack)

vào 1995

 Năm 2005 tấn công thành công

• SHA-1

Kích thước digest: 160 bit

Công bố tấn công thành công vào năm 2015

Hết hạn vào năm 2030

• SHA-2: 224/256/384/512 bit

• SHA-3: 224/256/384/512 bit

31

MD5

• Bước 1: Padding dữ liệu sao cho bản tin đầu vào có độ

dài L sao cho L mod 512 = 448

• Bước 2: Biểu diễn độ dài của dữ liệu ban đầu dưới dạng

64 bit. Thêm giá trị độ dài này vào khối dữ liệu.

• Coi khối dữ liệu là một chuỗi các khối 512 bit: Y₀, Y₁, …, Y_K-1

• Hoặc là một chuỗi các khối 32 bit : m₀, m₁, …,m_N

• Bước 3: Khởi tạo các giá trị hằng số A, B, C, D

A = 0x67 45 23 01

B = 0xEF CD AB 89

C = 0x98 BA DC FE

D = 0x10 32 54 76

16

32

MD5

• Bước 4: Thực hiện vòng lặp

xử lý các khối 512 bit

Xử lý khối dữ liệu 512 bit thứ q:

thực hiện 4 vòng lặp. Mỗi vòng

lặp áp dụng hàm nén với T[1..64]

là mảng hằng số xác định trước

Cộng modulo 2³²mỗi khối với giá

trị CV_qđể có CV_q+1

• Bước 5: Kết quả xử lý khối

512 bit cuối cùng là giá trị

băm của thông điệp

33

Hàm nén trong MD5

• Đầu vào:

• CV: Khối 128 bit

M_i: khối dữ liệu 32-bit

T_i: Hằng số

Cộng modulo 2³²

M_i

T_i

•

• <<<s: dịch trái s bit

• ˄: AND, v: OR, ¬: NOT

F1 = (B˄C)˅(¬B ˄ D)

F2 = (B ˄ D) ˅(C ˄ ¬D)

F3 = B  C  D

F4=C  (B ˅ ¬D)

• Thực hiện vòng lặp 16 bước

17

34

SHA-1

• Bước 1: Padding dữ liệu sao cho bản tin đầu vào có độ

dài L sao cho L mod 512 = 448

• Bước 2: Biểu diễn độ dài của dữ liệu ban đầu dưới dạng

64 bit. Thêm giá trị độ dài này vào khối dữ liệu.

• Coi khối dữ liệu là một chuỗi các khối 512 bit: Y₀, Y₁, …, Y_K-1

• Hoặc là một chuỗi các khối 32 bit : m₀, m₁, …,m_N

• Bước 3: Khởi tạo các giá trị hằng số A, B, C, D, E

A = 0x67 45 23 01

B = 0xEF CD AB 89

C = 0x98 BA DC FE

D = 0x10 32 54 76

E = 0xC3 D2 E1 F0

35

SHA-1

• Bước 4: Thực hiện vòng lặp

xử lý các khối 512 bit

Xử lý khối dữ liệu 512 bit thứ q:

thực hiện 4 vòng lặp. Mỗi vòng

lặp áp dụng hàm nén với K là

hằng số xác định trước

Cộng modulo 2³²mỗi khối với giá

trị CV_qđể có CV_q+1

• Bước 5: Kết quả xử lý khối

512 bit cuối cùng là giá trị

băm của thông điệp

18

36

Hàm nén trong SHA-1

• Đầu vào:

• CV: Khối 160 bit

• W_t: Khối dữ liệu mở rộng 32 bit

• K_t: Hằng số

•

Cộng modulo 2³²

• <<<5(30): dịch trái 5(30) bit

• ˄: AND, v: OR, ¬: NOT

F1 = (B˄C)˅(¬B ˄ D)

F2 = B  C  D

F3 = (B ˄ C) ˅ (B ˄ D) ˅ (C ˄ D)

F4 = B  C  D

• Thực hiện vòng lặp 20 bước

37

Sử dụng mã băm

• Xác thực toàn vẹn bản tin: chỉ phát hiện được lỗi ngẫu

nhiên trong quá trình truyền

m

h

m’

h’

H

m

||

So sánh

H

Tấn công:

Thay m bằng m’

Tính lại h’ = H(m’)

Bản tin

toàn vẹn?

Bên nhận

Bên gửi

38

19

38

HMAC

• Hashed MAC: xây dựng MAC dựa trên hàm băm

k ⨁ ipad

m[0]

m[1]

m[2] || PB

IV

(fixed)

h

h₀

h₁

h₂

h₃

h₄

tag

k⨁opad

h

IV

PB: Padding Block

39

HMAC và MAC

• HMAC có tính chống đụng độ chắc chắn hơn do

sử dụng hàm băm

• Tốc độ tính toán của HMAC nhanh hơn

• Kích thước giá trị tag được tạo bởi HMAC lớn

hơn  an toàn hơn trước các tấn công

40

20

40

Bài giảng An toàn an ninh thông tin - Chương 3: Xác thực thông điệp - Bùi Trọng Tùng