Padding Oracle Attack (lược dịch + phân tích)

wind@k viết bài này với mong muốn chia sẻ thông tin cho các bạn có khó khăn trong việc tìm hiểu kỹ thuật này (do tiếng Anh hay lí do gì khác) đồng thời cũng là để học hỏi tự mình hiểu thêm vấn đề. Nói chung đây không phải là một kỹ thuật khó như nhiều bạn nghĩ, quan trọng là động não và lúc nào cũng suy nghĩ !!!

Phần 1: Căn bản về kỹ thuật mã hoá (cryptography)
Mã hoá nôm na là một số phép biến đổi trên dữ liệu nhằm làm cho dữ liệu đó biến dạng và không đọc được bởi những người không được phép đọc (người không có key để giải mã). Mã hoá có thể phân 2 loại :
- symmetric (đối xứng) : D(E(P,k),k) = P.
Ví dụ: thuật toán mã hoá DES, AES, Caesar http://en.wikipedia.org/wiki/Caesar_cipher):
Code:

E( P , k ) = C sao cho C[i] = (P[i] + k) % 26;
D(C, k) = P sao cho P[i] = (C[i] - k)%26;

- asymmetric/ public-key : D( E(P,d), e) = P.
Ví dụ: RSA - http://en.wikipedia.org/wiki/RSA
( E = hàm mã hoá, D = hàm giải mã
P = dữ liệu chưa mã hoá (plain text), C= dữ liệu đã mã hoá(cypher text)
k = key, d = public key, e = private key
d!=e )

Trong thực tế hàm mã hoá và giải mã thường lấy input là một block <=> 1 khối dữ liệu có độ dài nhất định ( 4-bytes, 8-bytes, 16-bytes v.v..). Vì vậy với 1 đoạn dữ liệu có độ dài lớn, người ta thường chia nó thành các đoạn nhỏ (trùng với độ dài input của thuật toán mã hoá) và mã hoá lần lượt.

Kỹ thuật mã hoá lần lượt từng block riêng lẻ rồi nối lại gọi là Electronic Codebook (ECB). Kỹ thuật này không an toàn vì nếu 2 đoạn input giống nhau sẽ cho ra 2 đoạn output giống nhau làm lộ pattern/hình dạng của dữ liệu. (Xem thêm ở http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Electronic_codebook_.28ECB.29)

Một kỹ thuật khác tăng cường tính bảo mật đó là Cypher Block Chaining (CBC). Sử dụng đoạn mã hoá của block trước, trong quá trình mã hoá. Cụ thể:
Code:

C[i] = E( P xor C[i-1], k )
C[0] = IV ( initial vector <=> 1 giá trị bất kì nào đó )
giải mã như sau:
P[i] = D( C[i], k ) xor C[i-1]





Vì đoạn dữ liệu được tách ra trong quá trình mã hoá, sẽ sảy ra trường hợp block cuối cùng sẽ ngắn hơn kích thước (size) cần, trong trường hợp này người ta sẽ thêm vào sau một số kí tự, kỹ thuật này gọi là PADDING. Cách thức padding là thêm vào sau N kí tự N, với N là phần khác nhau giữa size hiện tại của block và size tiêu chuẩn.

Ví dụ block size cần là 8 bytes, block cuối chỉ có 3 bytes : "AAA" => thêm vào thành "AAA\x05\x05\x05\x05\x05"




Phần 2: Padding Oracle Attack:
Như ở phần trước mình đã trình bày kỹ thuật CBC và Padding, đây là 2 mấu chốt quan trọng trong padding oracle attack.

Tưởng tượng trường hợp A connect đến server B và gửi 1 encrypted message với key thoả thuận từ trước và sử dụng CBC, trên B sẽ có 1 ứng dụng (app) làm những nhiệm vụ sau
1) nhận cypher text
2) decrypt cypher text => plain text
3) kiểm tra định dạng plain text, nếu padding không đúng => return ER_PADDING
4) đọc dữ liệu trong plain text => return SOMTHING_ELSE

Giả sử attacker bằng 1 cách nào đó có được đoạn encrypted msg (C) này, kỹ thuật Padding oracle có thể decrypt đoạn C mà không cần key cũng như thông tin về thuật toán mã hoá

Mấu chốt của PO là ở bước (3). Attacker sẽ gửi 1 đoạn encrypt message đến B và chờ return message, nếu return là SOMETHING_ELSE thay vì ER_PADDING thì attacker sẽ giải mã được ít nhất 1 byte của đoạn C. Cụ thể, thuật toán giải mã những byte cuối cùng của C trình bày trong paper của Serge Vaudenay như sau :

Code:

// b = block size; ^: phép xor; y = block cuối của cypher text ;
// O( S ) = 1 nếu nhận được SOMETHING_ELSE

1) chọn một vài random byte r[1] , . . . , r[b] and take i = 0
2) r = r[1]| . . . r[b−1]|(r[b] ^ i)
3) if O(r|y) = 0 then i++, trở lại bước 2
4) r[b] = r[b] ^ i
5) for n = b down to 2 do
(a) chọn r = r[1]| . . . |r[b−n]| (r[b−n+1] ^ 1)r[b−n+2] . . . r[b]
(b) if O(r|y) = 0 then stop and output (r[b−n+1] ^ n) . . . (r[b] ^ n)
6.) output rb ^ 1


Tư tưởng chủ đạo của thuật toán trên như sau:
- Ở bước 1 và 2, tác giả chọn ngẫu nhiên một đoạn dữ liệu có kích cỡ = 1 block size, và gọi nó là R
- Y là block cuối cùng của cypher text
- Khi Attacker gửi message gồm ( R | Y ) tức 2 block đến server, app sẽ giải mã ra P[0..1] như sau:
P[1] = D( Y, key ) xor R
P[0] = D( R, key ) xor IV

- Khi đó server sẽ kiểm tra định dạng của P[1], nếu những byte cuối cùng không có định dạng của 1 padding (xem phần 1) thì server sẽ trả ra ER_PADDING, nghĩa là O(R|Y) =0


còn ngược lại những byte cuối của P[1] sẽ có dạng ____1, ___22, __333, __444 v.v...



Giả sử nó là ____1 thì :
Code:

____1 = D(Y, key) xor R
==> D(Y,key) = _____1 xor R
==> D(Y, key)[b] = R[b] xor 1
==> P[last][b] = R[b] xor 1 xor C[last-1]
==> giải mã được byte cuối cùng không cần key.

(đối với 22,333,444 thì sao ??)

- Vấn đề còn lại là làm sao biết được nó ở dạng ___1,___22 hay __333 dù trong đa số trường hợp mà wind@k test thì toàn là ra ___1 vì mình chọn R ngẫu nhiên. Dù vậy thuật toán của tác giả có thể giúp ta biết được điều đó bằng việc detect ở bước (5). ( mọi người thử động não lí giải nhé )

Sau khi có được một vài byte ở cuối, nhiệm vụ còn lại là lấy được toàn bộ phần còn lại của block, thuật toán sau của tác giả làm điều đấy:

Code:

// Giải sử tìm được D( y[j..b] , key ), gọi nó là a[j]..a[b], y là block cần giải mã

1) chọn r[k] = a[k] ^ (b − j + 2) for k = j, . . . , b
2) chọn r[1] , . . . , r[j−1] at random and take i = 0
3) r = r[1] . . . r[j−2] (r[j−1] ^ i) r [j] . . . r[b]
4) if O(r|y) = 0 then i++ ; trở lại bước 3
5) output r[j−1] ^ i ^ (b − j + 2)


Tư tưởng tương đối giống thuật toán 1, chỉ có bước (1) là quan trọng. Ngoài ra nó không chỉ có thể giải mã last block như trên mà còn có thể lấy tư tưởng để giải được tất cả, ngoại trừ block đầu tiên!!!!

(Tại sao lại thế mọi người cũng thử tự lý giải nhé ?)

Khi nào có thời gian mình sẽ dịch và giải thích bài về CBC-R của anh mrro, giải thích nốt những phần còn lại ( dĩ nhiên là chỉ khi mọi người hưởng ứng )

Thân
wd.


// Bài viết được tham khảo, lược dịch Wikipedia + "Security Flaws Induced by CBC Padding – Applications to SSL, IPSEC, WTLS ...Serge Vaudenay" và có thêm một số giải thích từ bản thân mình
(update picture from anh mrro 's link)