Hash length Extension Attacks

Hash length extension attack – tấn công mở rộng độ dài hash là một kỹ thuật tấn công vào kỹ thuật MAC (Message Authenticate Code). Đây là kỹ thuật tấn công khai thác lỗ hổng của các thuật toán mã hoá một chiều (hash). Sử dụng cách tấn công này, những kẻ tấn công có thể xâm nhập vào hệ thống mà chỉ cần dựa vào những thông tin public của hệ thống.

TL;DR

Cho một hash được tạo thành từ 1 string ghép với phần prefix không biết trước, kẻ tấn công có thể viết thêm vào đoạn string đó và tạo ra một hash mới mà không cần biết đoạn prefix đó.

Bối cảnh

Khi bạn viết một trang Web, có một số dữ liệu bạn cần lưu nó vào cookie của người dùng. Để đảm bảo lần tiếp theo truy cập trang, người dùng gửi lên đúng dữ liệu mà bạn đã set chứ không phải dữ liệu giả mạo, bạn set thêm vào cookie một signature. Signature đó được tính bằng signature = hash(salt||data). Cả data và signature đều được set vào cookie của người dùng. Dữ liệu salt bạn giữ bí mật trên server không cho người dùng biết. Khi người dùng gửi dữ liệu lên, bạn kiểm tra xem hash(salt||data) == signature hay không để thực hiện các xử lý tiếp theo. Nếu so sánh trên đúng, có nghĩa là người dùng đã gửi thông tin chính xác, nếu sai có nghĩa là người dùng đã gửi thông tin giả mạo. Cách làm này được cho là an toàn và bảo mật vì những lý do sau:

• Bạn giữ dữ liệu salt một cách bí mật trên server và người dùng không thể biết được.
• Các thuật toán hash, ví dụ MD5, SHA1, v.v… đều là one-way hash, tức là chúng chỉ mã hoá một chiều mà không thể giải mã. Và cho dù người dùng có biết được signature và data cũng không thể tìm cách crack để tìm ra salt được.
• Hiện nay có một số tool crack thuật toán MD5 kinh điển, nhưng chúng đều dựa trên cơ sở dữ liệu khủng chứ chưa có một cách crack nào. Tất cả các tool này đều có thể phòng chống bằng cách sử dụng salt dài.

Tuy nhiên, trong bài viết này, tôi sẽ giới thiệu một kỹ thuật có thể crack được kỹ thuật MAC như trên.

Trước hết, để hiểu cách tấn công này, bạn cần hiểu được thuật toán hash.

Cách thức mã hoá hash

Ở đây, tôi sẽ giới thiệu cách mã hoá sử dụng thuật toán SHA-1, các thuật toán khác tương tự như vậy.

SHA-1 xử lý dữ liệu thành từng khối 64 byte (512 bit). Với những dữ liệu có độ dài khác nhau, SHA-1 sẽ chèn thêm một số lượng các bit, phần lớn là bit 0 (ít nhất là 65 bit và nhiều nhất là 576 bit) để độ dài dữ liệu là bội số của 512. Số bit được thêm vào này gọi là padding. Các bit padding này chỉ phụ thuộc vào độ dài ban đầu của dữ liệu, nó hoàn toàn không phụ thuộc gì vào nội dung dữ liệu này.

Sau đó dữ liệu đã được thêm các bit padding này được chia thành các block 512 bit và được xử lý từng block một. SHA-1 có một hàm nén và một running state là một cụm 5 từ có độ dài 32 bit. Bạn hoàn toàn có thể tìm hiểu cách hoạt động của SHA-1 ở đây. Cách mã hoá này có thể tóm lược như sau:

Hàm nén nhận đầu vào là 2 giá trị có độ dài lần lượt là 160 và 512 bit, và trả về kết quả là chuỗi 160 bit. Quá trình xử lý giống như dưới đây:

• Running state được khởi tạo hoàn toàn giống nhau cho các dữ liệu khác nhau. Các giá trị này được đưa ra bởi đặc tả của SHA-1.
• Với mỗi block, hàm nén sẽ được thực thi với đầu vào là running state hiện tại, và một đầu vào khác là block cần xử lý. Đầu ra của hàm nén này sẽ là running state mới.
• Running state sau khi xử lý block cuối cùng chính là kết quả hash cần tính.

Nguyên lý tấn công mở rộng độ dài hash

Bây giờ tôi sẽ nói đến kỹ thuật tấn công. Giả sử tôi được đưa cho một giá trị hash h được tính từ giá trị của m. Tôi không biết m nhưng tôi biết độ dài của nó.

Bởi vì tôi biết độ dài của m, tôi có thể dễ dàng tính được các bit padding p được sử dụng. Sau đó, tôi cần một giá trị m' là giá trị mới bắt đầu bằng m||p và tôi sẽ chèn thêm dữ liệu giả mạo của mình, m' = m||p||z, với z là giá trị tôi cần thêm vào. Bây giờ tôi cần tính giá trị hash SHA-1 h' với đầu vào mới là m' mặc dù tôi không hề biết nội dung đầy đủ của nó. (Do tôi không hề biết biết m).

Khi SHA-1 tính giá trị hash cho m', đầu tiên nó cũng là một việc là chèn thêm các bit padding vào, các bit này hoàn toàn phụ thuộc vào độ dài của m' (mà độ dài này tôi đã biết rồi). Bây giờ, kết quả sau khi chèn sẽ là m||p||z||p'. Sau đó các block 512 bit sẽ được xử lý từng block một.

Vì không biết đầy đủ nội dung, tôi không thể làm được việc này. Tôi không thể tự tính hash cho m'. Nhưng tôi biết nó được tính như thế nào.

Độ dài của m||p chắc chắn là bội của 512 (đương nhiên, độ dài này tôi hoàn toàn biết được). Tôi không biết nó được xử lý như thế nào, nhưng tôi biết sau khi xử lý hết các block của m||p kết quả thu được chính là hash của nó, h.

Sau đó, sử dụng giá trị này, tôi tiếp tục tính SHA-1 cho m'. Với running state hiện tại chính là h, tôi chỉ cần tiếp tục quá trình xử lý từng block 512 bit một với chuỗi z||p'.

Đây chính là mấu chốt của vấn đề, tôi có thể tính SHA-1 của m' từ SHA-1 của m mà hoàn toàn không biết nội dung của nó. Tuy nhiên, có một yêu cầu tiên quyết đó là tôi phải biết độ dài của nó.

Ở trên là tôi ví dụ với thuật toán SHA-1, các thuật toán khác hoàn toàn tương tự. Tất cả các thuật toán sử dụng hàm hash Merkle-Damgård như MD5, SHA-256, SHA-512 đều có thể bị tấn công bằng cách này.

Cách thức tấn công đối với MAC

Vậy một kẻ tấn công làm thế nào với trường hợp một trang Web sử dụng kỹ thuật MAC mà tôi nói trên? Rất đơn giản, khi truy cập trang Web, kẻ tấn công được set cookie là data và signature. Hắn không biết salt được lưu trên server nhưng nếu hắn biết được độ dài của nó. Có nghĩa là hắn hoàn toàn biết được độ dài của satl||data được dùng để tính hash. Với độ dài trên và signature chính là hash của nó, hắn ta có thể chèn thêm dữ liệu giả mạo vào cookie và tính signature mới. Ví dụ, hắn chèn cookie data = data||padding||fake và tính signature mới cho dữ liệu giả mạo này. Khi server kiểm tra, signature hoàn toàn trùng khớp với dữ liệu giả. Vậy là kẻ tấn công đã thành công.

Phòng chống

Vì kỹ thuật tấn công trên, với chúng ta là những người phát triển Web, chúng ta cần một số biện pháp phòng chống

• Không sử dụng MAC, đừng tin tưởng vào những gì người dùng gửi lên. Hãy tìm cách khác để xử lý dữ liệu của người dùng.
• Nếu bắt buộc phải sử dụng thì có một biện pháp phòng chống nổi tiếng nhất là sử dụng HMAC thay cho MAC. HMAC được cho là có thể chống được tấn công mở rộng độ dài hash
• Một vài thuật toán mã hoá không xử dụng hàm hash Merkle-Damgård như MD-2, SHA-224, SHA-338 không bị tấn công bởi cách này, bạn có thể dùng chúng.

Thực hành

Mặc dù lý thuyết như trên, có vẻ rất đơn giản. Nhưng khi thực hành lại không đơn giản chút nào. Vì tôi không có khả năng tính toán thành thạo với dữ liệu kiểu bit nên tôi mất khá nhiều thời gian để thực hiện.

Tôi sẽ giải thích từng bước. Đầu tiên, tôi giả sử dữ liệu ban đầu là secret và sử dụng thuật toán SHA-1.

>>> import hashlib
>>> m = hashlib.sha1()
>>> m.update(b"secret")
>>> m.digest()
b'\xe5\xe9\xfa\x1b\xa3\x1e\xcd\x1a\xe8Ou\xca\xaaGO:f?\x05\xf4'
>>> m.hexdigest()
'e5e9fa1ba31ecd1ae84f75caaa474f3a663f05f4'

Vậy là SHA-1 của secret viết dưới dạng hexa là e5e9fa1ba31ecd1ae84f75caaa474f3a663f05f4. Bây giờ, tôi sẽ tìm cách viết thêm vào sau secret một padding và một đoạn string nữa, ví dụ append. Và tôi sẽ tính SHA-1 cho chuỗi mới này theo lý thuyết ở trên mà không cần dùng đến nội dung của secret, tôi chỉ cần biết độ dài của nó là 6. Bạn sẽ thấy rằng SHA-1 mà tôi tính được hoàn toàn giống với SHA-1 được tính một cách bình thường.

Padding của secret và append

Đặc tả của SHA-1 đã rất rõ ràng, tôi không đi sâu vào chi tiết nữa. Như đã nói ở trên, padding không phụ thuộc vào nội dung của đầu vào mà chỉ phụ thuộc vào độ dài của nó mà thôi.

Padding của secret như sau:

\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x000

Như vậy chuỗi mới sẽ là

secret\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x000append

Bây giờ, tôi cần tính padding của chuỗi mới này, đây là một chuỗi có 70 byte. Padding của nó sẽ là

\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x020

Hàm nén của SHA-1

Dưới đây là hàm nén của SHA-1, nó nhận đầu vào là running state hiện tại, là một chuỗi của 5 string có độ dài 32 bit (tổng là 160 bit), một đầu vào khác là block cần xử lý. Đầu ra của nó là running state mới, trong trường hợp vì chỉ có 1 block nên nó cũng là kết quả cuối cùng.

Đây là một cài đặt viết bằng Python, tuy hơi sơ sài nhưng nó chạy đúng ;)

def compress(block,
    state=(
        0x67452301,
        0xefcdab89,
        0x98badcfe,
        0x10325476,
        0xc3d2e1f0
    )):
    lrot = lambda x, n: (x << n) | (x >> (32 - n))
    w = []
    for j in range(len(block) // 32):
        w.append(int(block[j * 32: j * 32 + 32], 2))

    for i in range(16, 80):
        w.append(lrot(w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16], 1) & 0xffffffff)

    a, b, c, d, e = state

    for i in range(80):
        if i <= 19:
            f, k = d ^ (b & (c ^ d)), 0x5a827999
        elif 20 <= i <= 39:
            f, k = b ^ c ^ d, 0x6ed9eba1
        elif 40 <= i <= 59:
            f, k = (b & c) | (d & (b | c)), 0x8f1bbcdc
        elif 60 <= i <= 79:
            f, k = b ^ c ^ d, 0xca62c1d6

        temp = lrot(a, 5) + f + e + k + w[i] & 0xffffffff
        a, b, c, d, e = temp, a, lrot(b, 30), c, d
    h0 = (state[0] + a) & 0xffffffff
    h1 = (state[1] + b) & 0xffffffff
    h2 = (state[2] + c) & 0xffffffff
    h3 = (state[3] + d) & 0xffffffff
    h4 = (state[4] + e) & 0xffffffff
    return (h0, h1, h2, h3, h4)

Các giá trị 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0 chính là running state được khởi tạo. Tuy nhiên bạn không cần quan tâm đến nó. Ở đây chúng ta cần quan tâm đến SHA-1 của secret cũng chính là running state hiện tại.

Tính SHA-1 cho chuỗi mới

Tôi cần tính SHA-1 cho chuỗi mới với lý thuyết ở trên. Hiện nay tôi đang có running state là e5e9fa1ba31ecd1ae84f75caaa474f3a663f05f4 tôi sẽ sử dụng giá trị này với hàm compress ở trên và block cần tính sẽ là

append\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x020

Quá trình tính như sau:

>>> a = 0xe5e9fa1b
>>> b = 0xa31ecd1a
>>> c = 0xe84f75ca
>>> d = 0xaa474f3a
>>> e = 0x663f05f4
>>> msg = "append\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x020"
>>> block = "".join(format(ord(x), '08b') for x in msg)
>>> r = compress(block, (a, b, c, d, e))
>>> "".join(["%08x" % a for a in r])
'84cf06ff6b78bfe100edd0463ca56a816fd632eb'

84cf06ff6b78bfe100edd0463ca56a816fd632eb chính là SHA-1 hash của chuỗi mới. Tôi đã tính nó hoàn toàn dựa trên lý thuyết về tấn công mở rộng hash mà không cần sử dụng chuỗi secret ban đầu.

Kiểm tra lại với cách tính SHA-1 thông thường.

Chuỗi cần tính như sau:

secret\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x000append

>>> import hashlib
>>> m = hashlib.sha1()
>>> msg = b"secret\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x000append"
>>> m.update(msg)
>>> m.hexdigest()
'84cf06ff6b78bfe100edd0463ca56a816fd632eb'

Như vậy tôi đã thành công khi điền thêm vào chuỗi ban đầu đoạn padding và chuỗi append để tạo thành chuỗi mới. Và tôi đã tính được SHA-1 của chuỗi mới mà không cần biết chuỗi ban đầu. Tôi chỉ biết độ dài của nó là đủ.

Nếu một trang Web set cookie cho tôi như sau:

data = ""
signature = "e5e9fa1ba31ecd1ae84f75caaa474f3a663f05f4"

Tôi có thể đặt lại cookie như sau:

data = \x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x000append
signature = 84cf06ff6b78bfe100edd0463ca56a816fd632eb

Như vậy nếu server có kiểm tra signature thì dữ liệu của tôi cũng hoàn toàn hợp lệ, vì signature của tôi trùng khớp với những gì server sẽ tính. Vậy là tôi đã crack thành công và gửi lên server dữ liệu giả mạo hoàn toàn do tôi tạo ra.