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

Mật mã ứng dụng

Hệ mã có xác thực

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

Nhắc lại

Bí mật: An toàn ngữ nghĩa chống lại tấn công CPA ・Mã hóa chỉ chống kẻ nghe trộm

Toàn vẹn: ・Không thể giả mạo dưới tấn công với thông điệp chọn sẵn ・CBC-MAC, HMAC, PMAC, CW-MAC

Tiếp theo: Mã hóa an toàn chống lại tấn công chủ động ・Đảm bảo cả bí mật và toàn vẹn

Ví dụ tấn công chủ động: TCP/IP

WWW  port = 80

pack

dest = 80 data

source machine

TCP/IP stack

Bob port = 25

Máy đích

Ví dụ tấn công chủ động: TCP/IP

WWW  port = 80

packet

TCP/IP stack

dest = 80 data

stuff

dest = 25

k

Bob port = 25

packets encrypted  using key k

Đọc thông tin của người khác

IV,

WWW  port = 80

dest = 80 data

Bob:

data

IV’,

k

dest = 25 data

k

Bob port = 25

Dễ làm với CBC với rand. IV

(chỉ thay đổi IV)

Sửa gói tin

IV’

dest = 80 data

dest = 25 data

・Giả sử gói tin được mã hóa bằng CBC mode với IV ngẫu nhiên. ・Vậy ta nên sửa IV’ như thế nào để

m[0] = D(k, c[0]) ⨁ IV = “dest=80…”

1. IV’ = IV ⨁ (…25…)

2. IV’ = IV ⨁ (…80…)

3. IV’ = IV ⨁ (…80…) ⨁ (…25…)

4. Không thể làm được

Một cách tấn công chỉ cần truy cập mạng

TCP/IP packet

Ứng dụng đầu cuối từ xa: ・Mỗi lần gõ phím được mã hóa với CTR mode

k

IP hdr TCP hdr

16 bit TCP checksum

1 byte keystroke

k

⨁ t ⨁ s

for all t, s send:

IP hdr TCP hdr

ACK if valid checksum, nothing otherwise

{ checksum(hdr, D) = t ⨁ checksum(hdr, D⨁s) } (cid:15482) can find D

Bài học

CPA an toàn: ・không đảm bảo giữ bí mật khỏi phương pháp tấn công chủ động

Chỉ nên dùng 2 mode: ・Nếu thông điệp chỉ cần toàn vẹn không cần bí mật:

(cid:15482) sử dụng MAC

・Nếu thông điệp cần cả toàn vẹn và bí mật

(cid:15482) sử dụng mã có xác thực

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

Mục đích

Định nghĩa. Một hệ mã xác thực (E,D) là một hệ mã với

Như thông thường: E: K × M × N ⟶ C

Bản mã bị loại

nhưng: D: K × C × N ⟶ M ∪ {⊥}

Tính an toàn: Hệ thống phải đảm bảo ・an toàn ngữ nghĩa chống CPA attack, và ・toàn vẹn thông điệp:

kẻ tấn công không thể tạo ra được bản mã hợp lệ mới

Toàn vẹn thông điệp

m2,

, mq

· · ·

Thử thách k ← K

Kẻ tấn công

c2,

, cq

2 E(k, m1)

· · ·

và c /

c1,

, cq

2 {

· · ·

}

n∏u D(k, c) ng˜Òc l§i

b = 1 b = 0

Định nghĩa. (E, D) là toàn vẹn thông điệp nếu với mọi thuật toán

“hiệu quả” A

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

Hệ mã có xác thực (Authenticated Encryption)

Định nghĩa. Hệ mã (E, D) là có xác thực nếu

1. an toàn ngữ nghĩa dưới CPA, và

2. có toàn vẹn thông điệp

Ví dụ: ・CBC với IV ngẫu nhiên không có xác thực vì ・D (k, .) không bao giờ output ra ⊥, vậy kẻ tấn công dễ dàng thắng

trong trò chơi toàn vẹn thông điệp

Hệ quả 1: tính xác thực

m1 , …, mq

Bob

Alice

ci = E(k, mi)

Kẻ tấn công không thể lừa Bob nghĩ rằng Alice đã gửi thông điệp cho mình

k

không thể tạo ra c ∉ { c1, …, cq }

(cid:15482) nếu D(k,c) ≠⊥ Bob biết thông điệp được gửi từ người biết khóa k (nhưng thông điệp có thể bị gửi lại nhiều lần)

Hệ quả 2

Hệ mã có xác thực (cid:15482) An toàn chống lại tấn công chọn bản mã (Security against chosen ciphertext attacks)

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

Ví dụ tấn công chọn bản mã (CCA)

Kẻ tấn công có bản mã c và anh ta muốn giải mã

・Thông thường, anh ta có thể lừa server giải mã một số bản mã

dest = 25 data

data

(không phải c)

・Thông thường, anh ta có thể học được một số thông tin về bản

TCP/IP packet

ACK

if valid checksum

rõ từ bản mã.

An toàn trước tấn công chọn bản mã

Khả năng của kẻ tấn công: Cả CPA và CCA

・Có thể lấy được mã hóa của mọi thông điệp anh ta chọn ・Có thể giải mã mọi bản mã anh ta chọn, khác với thử thách

(Mô hình chặt của thế giới thực)

Mục đích của kẻ tấn công: Phá an toàn ngữ nghĩa

An toàn trước tấn công chọn bản mã

for i = 1,…,q:

(1) truy vấn CPA

mi,0 , mi,1 ∈ M: |mi,0| = |mi,1|

Kẻ tấn công

Thử thách k ← K

ci ← E(k, mi,b)

(2) truy vấn CCA

ci ∈ C: ci ∉ {c1 , …, ci-1}

mi ← D(k, ci)

b’ ∈ {0,1}

・E=(E, D) là hệ mã trên (K, M, C)

An toàn trước tấn công chọn bản mã: Định nghĩa

Định nghĩa. E là CCA an toàn nếu với mọi thuật toán “hiệu quả” A:

AdvCCA[A,E] = | Pr[EXP(0) = 1] - Pr[EXP(1) = 1] |

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

m0 , m1: |m0| = |m1| = 1

Kẻ tấn công

Thử thách k ← K

c ← E(k, mb) = (IV, c[0])

c’ = (IV ⨁ 1, c[0])

D(k, c’) = mb ⨁ 1

Ví dụ: CBC với IV ngẫu nhiên là không CCA an toàn

Mã xác thực (cid:15482) CCA an toàn

Định lý. Xét (E,D) là hệ mã có xác thực. Vậy thì (E,D) là CCA an toàn.

Đặc biệt, với mọi thuật toán hiệu quả tấn công E dùng q-truy vấn, có

tồn tại B1, B2 thỏa mãn:

AdvCCA[A,E] ≤ 2q⋅AdvCI[B1,E] + AdvCPA[B2,E]

Chứng minh

Chal.

Adv.

Chal.

Adv.

CPA query: mi,0 , mi,1

ci=E(k,mi,0)

k←K

CCA query: ci

≈p

CCA query: ci

⊥

D(k,ci) ≈p

≈p

Chal.

Adv.

Chal.

Adv.

CPA query: mi,0 , mi,1

ci=E(k,mi,1)

≈p

k←K

CCA query: ci

D(k,ci)

⊥

Kết luận

Mã có xác thực: ・Đảm bảo bí mật chống lại kẻ tấn công chủ động, kẻ có thể giải

mã một vài bản mã.

Giới hạn: ・không chống được tấn công replay ・không chống được side channel (timing)

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

Một chút về lịch sử

Mã có xác thực (AE): được giới thiệu vào năm 2000 [KY’00, BN’00]

API mật mã trước đó: (ví dụ MS-CAPI) ・Cung cấp API mã hóa CPA-an toàn (Ví dụ CBC với IV ngẫu nhiên) ・Cung cấp API cho MAC (ví dụ HMAC)

Các dự án cố gắng kết hợp hai cơ chế này với nhau mà không định

nghĩa rõ ràng mục đích. ・Không phải mọi cách kết hợp đều cho phép AE…

Kết hợp MAC và ENC (CCA)

E(kE , mlltag)

Khóa mã hóa kE, khóa cho MAC = kI

・Option 1: (SSL)

S(kI, m)

msg m

tag

・Option 2: (IPsec)

E(kE, m)

S(kI, c) tag

msg m

always correct

E(kE , m)

S(kI, m)

・Option 3: (SSH)

msg m

tag

Định lý A.E

Xét (E,D) là CPA an toàn và (S,V) là một MAC an toàn. Vậy thì:

1. Encrypt-then-MAC: luôn cho A.E

2. MAC-then-encrypt: có thể không an toàn chống tấn công CCA

tuy nhiên, khi (E,D) là rand-CTR mode hoặc rand-CBC vậy thì

M-then-E cho phép A.E

với rand-CTR mode, chỉ cần one-time MAC là đủ.

Các chuẩn (ở mức cao)

・GCM: CTR mode encryption then CW-MAC

(được tăng tốc qua lệnh PCLMULQDQ của Intel)

・CCM: CBC-MAC then CTR mode encryption (802.11i) ・EAX : CTR mode encryption then CMAC

Tất cả đều có AEAD: (auth. enc. with associated data).

encrypted

associated data

encrypted data

authenticated

Tất cả đều dựa trên nonce.

Ví dụ API (OpenSSL)

int AES_GCM_Init(AES_GCM_CTX *ain, unsigned char *nonce, unsigned long noncelen, unsigned char *key, unsigned int klen )

int AES_GCM_EncryptUpdate(AES_GCM_CTX *a, unsigned char *aad, unsigned long aadlen, unsigned char *data, unsigned long datalen, unsigned char *out, unsigned long *outlen)

MAC an toàn — giải thích

Nhắc lại: ・MAC an toàn chỉ ra (m , t) ⇏ (m , t’ ) ・Tại sao? Giả sử ngược lại: (m , t) ⟶ (m , t’)

m0, m1

Chal.

Adv.

c ← E(k, mb) = (c0, t)

(c0, t)

k←K

c’ = (c0 , t’ ) ≠ c

(c0, t’)

D(k, c’) = mb

Vậy thì Encrypt-then-MAC có thể không toàn vẹn thông điệp!!

OCB: xây dựng trực tiếp từ PRG

checksum

m[1]

m[2]

m[3]

m[0]

P(N,k,1)

P(N,k,2)

P(N,k,0)

P(N,k,3)

P(N,k,0)

⊕

E(k,⋅)

auth

P(N,k,2)

P(N,k,3)

P(N,k,0)

P(N,k,1)

⊕

c[1]

c[2]

c[3]

c[4]

c[0]

Mã xác thực hiệu quả hơn: một phép toán E(.) cho mỗi block

Hiệu năng Crypto++5.6.0 [Wei Dai]

AMD Opteron, 2.2 GHz (Linux)

Hệ mã

Kích thước mã tốc độ (MB/giây)

AES/GCM lớn ** 108 AES/CTR 139

nhỏ hơn 61 AES/CBC 109 AES/CCM

nhỏ hơn 61 AES/CMAC 109 AES/EAX

129* HMAC/SHA1 147 AES/OCB

* theo kết quả của Ted Kravitz ** máy không phải Intel

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

HỆ MÃ CÓ XÁC THỰC

‣ Tấn công chủ động hệ mã CPA-an toàn

‣ Định nghĩa

‣ Tấn công chọn bản mã

‣ Xây dựng từ hệ mã và MAC

‣ Case study: TLS

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

‣ CBC pading attack

‣ Attacking non-atomic decryption

Nhắc lại

Mã có xác thực: ・CPA an toàn + toàn vẹn thông điệp ・chống lại tấn công chọn bản mã

Giới hạn: ・không an toàn khi cài đặt sai

Các mode mã hóa có xác thực: ・Chuẩn: GCM, CCM, EAX

Sơ đồ xây dựng tổng quát: ・encrypt-then-MAC

Giao thức TLS (mã hóa với CBC)

Giải mã: dec(kb⇾s , record, ctrb⇾s ) :

bước 1: giải mã CBC bản ghi dùng kenc

bước 2: kiểm tra định dạng pad: bỏ qua nếu sai

bước 3: kiểm tra tag trên [ ++ctrb⇾s ll header ll data]

type ll ver ll len

Hai kiểu lỗi:

data

• padding error • MAC error

tag

pad

bỏ qua nếu sai

Padding oracle

Giả sử kẻ tấn công có thể phân biệt được hai lỗi

(pad error, MAC error):

(cid:15482) Padding oracle:

type ll ver ll len

data

kẻ tấn công gửi các bản mã và lấy được thông tin về bản mã nếu byte cuối là valid pad

Đây là ví dụ đẹp cho tấn công chọn bản mã

tag

pad

Padding oracle qua timing OpenSSL

Credit: Brice Canvel

(fixed in OpenSSL 0.9.7a)

In older TLS 1.0: padding oracle due to different alert messages.

Dùng padding oracle (mã hóa với CBC )

c[0]

c[1]

c[2]

D(k,⋅)

⊕

m[2] ll pad

m[0]

m[1]

Kẻ tấn công có bản mã c = (c[0], c[1], c[2]) và anh ta muốn m[1]

Dùng padding oracle (mã hóa với CBC )

c[0]

c[1]

⨁ g ⨁ 0x01

D(k,⋅)

= last-byte ⨁ g ⨁ 0x01

⊕

m[0]

m[1]

if last-byte = g: valid pad otherwise: invalid pad

Bước 1: xét g là gợi ý cho byte cuối của m[1]

Dùng padding oracle (mã hóa với CBC )

Cách tấn công: ・Gửi ( IV, c’[0], c[1] ) tới padding oracle (cid:15482) kẻ tấn công biết liệu last-byte = g

・Lặp lại với g = 0,1, …, 255 để lấy được thông tin về byte cuối

của m[1]

・Dùng pad (02,02) để lấy thông tin về byte tiếp theo.

IMAP trên TLS

Vấn đề: ・TLS thương lượng lại khóa khi nhận được một bản ghi sai.

Chi tiết IMAP trên TLS: (giao thức để đọc mail) ・Mỗi năm phút client gửi thông báo login tới server: LOGIN “username” “password” ・Cùng một kiểu tấn công như vậy, bất kể khóa mới (cid:15482) lấy được password chỉ trong vài giờ.