Cryptography: Untwisting Mersenne Twister

Cách mã hóa sử dụng one-time pad (OTP), hay còn được gọi là Vernam-cipher hoặc perfect cipher là cách mã hóa sử dụng khóa ngẫu nhiên. Đây là cách mã hóa duy nhất, về lý thuyết, là bảo mật và không thể bẻ khóa được. Tuy nhiên, cuộc đời thường lắm trái ngang, thực tế lại chẳng được đẹp đẽ như lý thuyết. Trong bài viết này, tôi sẽ trình bày cách bẻ khóa một cách mã hóa như vậy.

Bài toán

Để minh họa cho việc bẻ khóa này, chúng ta đến với bài toán sau. Đây là đề bài trong cuộc thi CTF của công ty. Đề bài của bài toán này có thể xem ở đây (hy vọng nó chưa bị xóa). Trong trường hợp nó bị xóa rồi thì tôi đã backup file ở đây.

Có thể hiểu bài toán này đơn giản như sau: file flag là một file ảnh, được mã hóa bằng one-time pad. Đề bài chỉ cho chúng ta file đã mã hóa và công việc của chúng ta là tìm cách khôi phục file flag ban đầu. Chúng ta được cho mã nguồn đã biết được quá trình mã hóa như thế nào. Nhưng không có khóa, chúng ta phải làm thế nào đây, khi mà nó hoàn toàn được sinh ngẫu nhiên.

Cách mã hóa

Thực ra cách mã hóa rất đơn giản, file gốc được đọc theo từng khối 4 byte (32 bit) một, mỗi khối được coi như một số nguyên không dấu. Với mỗi khối như vậy, một khóa là một số nguyên không dấu 32bit được sinh ngẫu nhiên, và dữ liệu mã hóa là kết quả của phép XOR giữa hai số nguyên không dấu đó. Phép XOR có những tính chất sau:

A XOR B = B XOR A
A XOR B = C => A XOR C = B

Vì những tính chất trên, chúng ta có thể dễ dàng giải mã ngược lại bằng cách XOR file mã hóa với khóa. Tuy nhiên, chúng ta cần phải biết khóa, trong trường hợp này nó được sinh ngẫu nhiên. Nên làm sao chúng ta biết được đây.

Tôi nhớ Ada Lovelace, người được coi là lập trình viên đầu tiên, đã từng nói rằng: Máy tính rất ngu ngốc và chúng ta phải dạy nó mọi thứ. Sau bao nhiêu năm, máy tính đã thông minh hơn nhiều rồi, nhưng trong bài toán của chúng ta, nó vẫn đủ ngốc để chúng ta tìm cách bẻ khóa nó.

Để bẻ được khóa, chúng ta cần biết khóa được sinh ra như thế nào.

Mersenne Twister

Thực ra, với một cái máy tính không có gì là ngẫu nhiên cả. Việc sinh các số ngẫu nhiên thực ra cũng hoàn toàn là do con người dạy nó. Mà đã dạy được, thì có thể bẻ khóa được. Vì không thực sự là ngẫu nhiên, nên việc sinh số ngẫu nhiên của máy tính là giả ngẫu nhiên (pseudorandom), và các thuật toán sinh số ngẫu nhiên được gọi là pseudorandom number generator (pRNG). Trong số các thuật toán đã được phát minh thì Mersenne Twister là thuật toán được sử dụng rộng rãi nhất. Ngày nay nó vẫn được sử dụng, ví dụ Ruby có hàm rand, Python có hàm random, PHP có mt_rand chính là sử dụng thuật toán này.

Mã nguồn của phiên bản 19937 được đưa ra trong đề bài của chúng ta. Ở đây, tôi không đi sâu vào chi tiết thuật toán mà sẽ chỉ giới thiệu sơ lược. Trước khi sinh giá trị ngẫu nhiên, bộ khởi tạo cần được gọi trước. Chương trình sẽ có một state là một mảng 624 phần tử, mỗi lần sinh số ngẫu nhiên, 1 phần tử từ state sẽ được lấy ra và biến đổi (tampering) để cho ra một số. Sau khi state đã được lấy hết, state mới sẽ được tính toán dựa vào state hiện tại.

Với việc sinh số ngẫu nhiên như vậy, nếu chúng ta biết được bất cứ một state nào, thì các state tiếp theo, và cả các số “ngẫu nhiên” tiếp theo, chúng ta hoàn toàn có thể biết được. Tuy nhiên, đó là lý tưởng, khi thực hiện khó hơn rất nhiều, nhưng không phải là không thể. Và đề bài cũng đã cho chúng ta một gợi ý, đó là trước khi mã hóa, họ đã mã hóa một file khác trước. Và nhờ những thông tin này, chúng ta có thể tìm ra khóa cho file flag. Chúng ta sẽ tìm hiểu cách làm này trong phần tiếp theo.

Untwisting

Vì mỗi state có 624 số, và sẽ sinh ra 624 số ngẫu nhiên. Nếu chúng ta có được 624 số ngẫu nhiên sinh ra từ 1 state, liệu chúng ta có thể tìm ra được state đó không?

Trước hết, làm thế nào chúng ta lấy được 624 số từ 1 state. Rất đơn giản, gợi ý cho chúng ta đã có rồi. File gốc và file mã hóa đều có, chúng ta dễ dàng lấy ra khóa của nó bằng cách XOR hai file này với nhau. Và vì đây là một gợi ý nên nó đủ dài để chúng ta có thể lấy ra 624 số ngẫu nhiên của state đầu tiên. Việc bây giờ chúng ta cần làm là khôi phục lại state đó và tìm cách tính toán các state tiếp theo.

Như vậy kể cả khi chúng ta không biết các state được khởi tạo như thế nào, chúng ta vẫn có thể giả ngẫu nhiên để tìm ra khóa của flag được.

Tính toán state tiếp theo

Việc tính toán này không có chút nào. Nó hoàn toàn dựa vào tính toán dịch bit, XOR và AND. Ở đây tôi sẽ code bằng Python nên phép toán dịch bit sang phải sẽ hơi khác một chút. Ví dụ, Python khi dịch bit các số âm sẽ giữ nguyên dấu của chúng:

>>> -1 >> 3
-1

Nhưng Mersenne Twister làm việc với các số không dấu nên chúng ta cần một phép toán khác, thực ra nó cũng không khó lắm:

def rshift(value, shift):
    return (value % 0x100000000) >> shift

Và chúng ta có thể mô phỏng quá trình sinh state mới:

def next_state(mt):
    mag01 = [0x0, MATRIX_A]

    for kk in range(N - M):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        mt[kk] = mt[kk + M] ^ rshift(y, 1) ^ mag01[y & 0x1]
    for kk in range(N - M, N - 1):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        mt[kk] = mt[kk + (M - N)] ^ rshift(y, 1) ^ mag01[y & 0x1]
    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
    mt[N - 1] = mt[M - 1] ^ rshift(y, 1) ^ mag01[y & 0x1]
    return mt

Sinh số ngẫu nhiên từ state

Mỗi số ngẫu nhiên sẽ được sinh ra từ một phần tử của state bằng các phép toán khá phức tạp như sau:

def tampering(value):
    y = value ^ rshift(value, 11)
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 15) & 0xefc60000
    y ^= rshift(y, 18)
    return y

Khôi phục state

Bây giờ là công việc khó khăn nhất, cũng là chìa khóa để giải bài toán này. Tìm state từ số ngẫu nhiên đã biết. Thông thường, công việc có hai chiều như thế này thì một chiều lúc nào cũng dễ, chiều còn lại sẽ có hơn nhiều. Có state lấy ra số ngẫu nhiên thì dễ, chứ có số rồi tìm ra state thật là khó như lên trời vậy. Thực ra, cách làm ngu si nhất ở đây là brute force. Mỗi số trong state là 32 bit nên chỉ có 2 ^ 32 = 4294967296 số khác nhau thôi, nên nếu không có cách nào khác thì đành thử hết tất cả các trường hợp vậy.

Tuy nhiên, chúng ta có cách làm khác. Ví dụ với phép toán cuối cùng:

y ^= rshift(y, 18)

Chúng ta sẽ nhìn kỹ hơn vào các bit:

101101110101111001 11111001110010                    y
000000000000000000 10110111010111100111111001110010  rshift(y, 18)
101101110101111001 01001110100101                    y ^ rshift(y, 18)

Ở ví dụ trên, tôi đã ngăn cách 18 ký tự đầu với phần còn lại. Chúng ta dễ dàng nhận ra rằng, 18 bit đầu tiên của y vẫn còn nguyên sau phép toán đó. Chúng ta có thể dễ dàng lấy ra 18 bit này. Và 18 bit này lại được dịch sang phần tiếp theo, và chúng ta có thể dễ dàng XOR nó với kết quả để lấy ra giá trị ban đầu. Một thuật toán tổng quát để dịch ngược quá trình này như sau:

def unshift_right(value, shift):
    i = 0
    result = 0
    while i * shift < 32:
        part_mask = rshift(-1 << (32 - shift), shift * i)
        part = value & part_mask
        value ^= part >> shift
        result |= part
        i += 1
    return result

Phương pháp tương tự cũng có thể được sử dụng với phép dịch bit sang trái trong phép tampering ở trên:

def unshift_left(value, shift, mask):
    i = 0
    result = 0
    while i * shift < 32:
        part_mask = rshift(-1, (32 - shift)) << (shift * i)
        part = value & part_mask
        value ^= (part << shift) & mask
        result |= part
        i += 1
    return result

Và cả quá trình khôi phục state sẽ như sau:

def untampering(value):
    x = unshift_right(value, 18)
    x = unshift_left(x, 15, 0xefc60000)
    x = unshift_left(x, 7, 0x9d2c5680)
    x = unshift_right(x, 11)
    return x

Công việc khó khăn nhất đã có lời giải, quay trở lại bài toán của chúng ta, chúng ta cần lấy ra state 624 số ban đầu sau khi được khởi tạo.

Tìm flag cho bài toán đưa ra

Quay lại bài CTF của chúng ta. Bây giờ, chúng ta cần lấy ra 624 số được sinh ngẫu nhiên đầu tiên.

firsts = []
with open('impossibru.png', 'rb') as fp, open('impossibru.enc', 'rb') as fc:
    fc.read(4)
    for _ in range(624):
        x = struct.unpack('I', fp.read(4))[0]
        y = struct.unpack('I', fc.read(4))[0]
        firsts.append(x ^ y)

Sau đó là khôi phục state từ các số này:

mt = [untampering(x) for x in firsts]

Bây giờ đã có state đầu tiên, công việc của chúng ta chỉ còn là sinh các số ngẫu nhiên cho 2 file gợi ý và flag nữa thôi, chúng ta chỉ cần lưu lại các số được sinh ra flag là đủ:

with open('impossibru.enc', 'rb') as fhint, open('flag.enc', 'rb') as fflag:
    hint_length_in_bytes = struct.unpack('I', fhint.read(4))[0]
    flag_length_in_bytes = struct.unpack('I', fflag.read(4))[0]
hint_length = (hint_length_in_bytes + 3) // 4
flag_length = (flag_length_in_bytes + 3) // 4

for _ in range(hint_length // N - 1):
    mt = next_state(mt)
mt = next_state(mt)
keys = [tampering(x) for x in mt[hint_length % N:]]
for _ in range(flag_length // N):
    mt = next_state(mt)
    keys += [tampering(x) for x in mt]

Với key thu được, chúng ta có thể ghi ra file rồi lợi dùng hàm decrypt đề bài cung cấp để giải mã. Tuy nhiên, ở đây đang tiện code Python nên chúng ta có thể tiếp tục:

ciphers = []
with open('flag.enc', 'rb') as f:
    f.read(4)
    buffer = f.read(4)
    while buffer != b'':
        buffer = b'\x00' * (4 - len(buffer)) + buffer
        ciphers.append(struct.unpack('I', buffer)[0])
        buffer = f.read(4)
with open('flag.jpg', 'wb') as f:
    for x, y in zip(ciphers, keys):
        f.write(struct.pack('I', x ^ y))

Và cuối cùng là thành quả của chúng ta:

Kết luận

Thực sự việc sinh số ngẫu nhiên là có thể đoán trước được, và kể cả mã hóa one-time pad cũng không thực sự là an toàn. Tuy nhiên, việc này hoàn toàn là do sự bất cẩn của lập trình viên chứ bản thân thuật toán không có vấn đề gì. Trong bài toán của chúng ta, vì đây là một bài CTF nên có gợi ý chứ bình thường, không dễ dàng gì chúng ta có thể lấy ra được các số ngẫu nhiên để khôi phục state. Vì vậy, cũng không nên quá lo lắng về khả năng bị giải mã của cách mã hóa này.

P.S. Mời các bạn thử sức với một bài CTF tương tự.