# Key Recovery Attacks on MEGA

# I. Tổng quan

MEGA là nền tảng truyền thông và lưu trữ đám mây với hơn 265 triệu tài khoản người dùng và hơn 10 triệu người dùng hàng ngày, tự quảng cáo là được thiết kế an toàn và riêng tư. Nền tảng này khác biệt với các nhà cung cấp dịch vụ lớn khác bằng cách cung cấp mã hóa đầu cuối cho dữ liệu được lưu trữ. Trên MEGA, các tệp người dùng phải được giữ bí mật ngay cả khi nhà cung cấp dịch vụ lưu trữ độc hại hoặc đã bị xâm phạm do vi phạm, ngụ ý tính bảo mật trong mô hình mối đe dọa mạnh. Tính bảo mật của MEGA trong cài đặt này gần đây đã được phân tích chi tiết, trong đó mô tả 5 cuộc tấn công vào giao thức mật mã được MEGA sử dụng để xác thực người dùng và mã hóa dữ liệu người dùng. Hai cuộc tấn công đầu tiên trong số này đã phá vỡ hoàn toàn tính bảo mật của tệp người dùng. Ngay sau đó, đã cải thiện đáng kể cuộc tấn công đầu tiên trong, giảm yêu cầu ít nhất 512 lần đăng nhập của người dùng xuống chỉ còn 6.

Trọng tâm của chúng là các cuộc tấn công trong khai thác việc thiếu cả khả năng phân tách khóa và bảo vệ tính toàn vẹn đối với các khóa được lưu trữ trong thiết kế MEGA: một khóa chính của người dùng được sử dụng để mã hóa cả khóa riêng RSA của người dùng (được sử dụng trong quá trình xác thực người dùng) và chính các khóa mã hóa tệp của người dùng; trong khi đó AES ở chế độ ECB được sử dụng để mã hóa. Điều này cho phép làm hỏng khóa riêng RSA theo một số cách nhất định, làm rò rỉ thông tin hữu ích trong giao thức xác thực, cũng như “cắt và dán” các khối AES-ECB từ khóa mã hóa tệp vào khóa riêng RSA.

# II. Hệ thống phân cấp khóa


Nguồn gốc của hệ thống phân cấp khóa của máy khách MEGA là mật khẩu do người dùng chọn. Từ mật khẩu này, máy khách MEGA lấy được khóa xác thực và khóa mã hóa. Khóa xác thực được sử dụng để xác định người dùng MEGA. Khóa mã hóa mã hóa khóa chính được tạo ngẫu nhiên, từ đó mã hóa tài liệu khóa khác của người dùng.

Đối với mọi tài khoản, các phần tử khóa này bao gồm một bộ khóa bất đối xứng bao gồm cặp khóa RSA (để chia sẻ dữ liệu với người dùng khác), cặp khóa Curve25519 (để trao đổi khóa trò chuyện cho chức năng trò chuyện của MEGA) và cặp khóa Ed25519 (dành cho việc ký các khóa khác). Hơn nữa, đối với mỗi tệp hoặc thư mục được người dùng tải lên, một khóa mã hóa đối xứng mới gọi là khóa nút sẽ được tạo. Các khóa bất đối xứng riêng tư và các khóa nút được máy khách mã hóa bằng khóa chính bằng AES-ECB và được lưu trữ trên các máy chủ của MEGA để hỗ trợ truy cập từ nhiều thiết bị. Người dùng trên thiết bị mới có thể nhập mật khẩu của họ, xác thực với MEGA, tìm nạp các phần tử khóa được mã hóa và giải mã nó bằng khóa mã hóa lấy từ mật khẩu.

# III. **RSA Key Recovery Attack**

## 1. Bối cảnh

Khi người dùng MEGA cố gắng đăng nhập lần đầu tiên trên một máy khách mới, máy khách này chỉ sở hữu khóa bí mật AES lấy từ mật khẩu của người dùng.

Để hoạt động bình thường, máy khách cần có bản sao khóa riêng RSA của người dùng.

Máy chủ sở hữu khóa chung RSA của người dùng và một bản sao khóa riêng RSA của người dùng được mã hóa bằng khóa AES trong mô hình ECB, vì vậy về mặt lý thuyết, khóa riêng được ẩn khỏi máy chủ, nhưng máy khách có thể lấy khóa RSA riêng bằng cách giải mã khóa được mã hóa. Khóa riêng từ máy chủ bằng khóa bí mật AES có nguồn gốc từ mật khẩu. Mục tiêu của máy chủ độc hại là khôi phục khóa PrivateRSA của người dùng.

Trong quá trình đăng nhập, máy chủ tạo một mã nhận dạng phiên (SID) dài 43 byte, được mã hóa bằng khóa chung RSA và gửi đến máy khách cùng với khóa riêng được gói. Máy khách sử dụng khóa AES để giải mã khóa riêng RSA đã bị mã hóa, sau đó sử dụng các tham số nhận được để giải mã văn bản mã hóa RSA và truy xuất SID. Sau đó, máy khách sẽ gửi SID được truy xuất đến máy chủ.

Máy chủ độc hại muốn sử dụng giá trị SID được gửi từ máy khách để suy ra thông tin về các tham số trong khóa riêng tư chưa được gói.

Chúng ta biểu thị khóa công khai RSA bằng $(N,e)$, trong đó các thừa số của modulus $N$ là $p$ và $q$. Số mũ RSA công khai là $e$ và số mũ riêng tư là $d$. Máy khách MEGA sử dụng RSA-CRT để giải mã, vì vậy qui ước $u = q^{−1} \ mod \ p$ là hệ số được sử dụng trong quá trình hoạt động của CRT.

Khóa riêng được mã hóa có dạng:

$$
l(q) \ ‖ \ q \ ‖ \ l(p) \ ‖ \ p \ ‖ \ l(d) \ ‖ \ d \ ‖ \ l(u) \ ‖ \ u \ ‖ \ P
$$

$l$ là độ dài bit của các giá trị dưới dạng số nguyên 2 byte, tất cả các số nguyên được lưu trữ ở định dạng big-endian và $P$ là giá trị padding 8 byte mà attacker không xác định. Cần phải lưu ý rằng $q$ có độ dài $1024$ bit, vì vậy $l(q)$ là `0x0400` và vì các giá trị bí mật có kích thước có thể dự đoán được nên chúng xuất hiện ở các tập hợp có thể dự đoán được trong bản rõ. Điểm tiếp theo cần lưu ý là khóa riêng tư mã hóa toàn bộ $d$ và không bao $dp$ hay $dq$ thường được lưu trữ để sử dụng trong quá trình giải mã RSA-CRT. Cuối cùng, do các trường độ dài nên giá trị $u$ 1024-bit trải dài 9 khối văn bản gốc AES và giá trị cuối cùng trong số đó chứa các trường độ dài và trường đệm tương ứng.

Khóa riêng được mã hóa có độ dài là 656 byte hoặc 41 khối AES. Khóa riêng tư được mã hóa bằng AES trong ECB mode, có nghĩa là từng khối bản rõ 16 byte được mã hóa độc lập. Như sau:

$$
ct1 \ ‖ \ ct2 ‖ \ ···‖ \ ct41 \ = E_{AES} \ (pt1) \ ‖ E_{AES} \ (pt2) \ ‖ \ ··· \ ‖ \ E_{AES} \ (pt41)
$$

Việc giải mã khóa riêng được mã hóa cũng xử lý các khối 16 byte một cách độc lập, tạo điều kiện cho các cuộc tấn công malleability trong đó máy chủ độc hại thay đổi các khối văn bản mã hóa riêng lẻ dẫn đến việc thay đổi các khối văn bản gốc tương ứng trong bản mã của khóa riêng.

Khi máy chủ trung thực xây dựng bản rõ RSA với SID 43 byte, SID sẽ được đặt theo byte 3-45 của bản rõ RSA 256 byte m. Trước khi vá lỗi, máy khách trích xuất các byte này từ đầu ra giải mã RSA mà không kiểm tra tính hợp lệ của phần còn lại của đầu ra giải mã. Tuy nhiên, có một phương pháp đặc biệt trong hàm trích xuất của máy khách để kiểm tra xem byte 2 có khác 0 hay không và nếu đúng như vậy thì nó sẽ trích xuất các byte 2-44. Chi tiết này không gây hậu quả gì cho cuộc tấn công trích xuất khóa RSA, nhưng nó là một khía cạnh cần thiết trong cuộc tấn công.

Nếu chúng ta giả sử các byte đầu ra của hàm giải mã RSA được phân phối đồng đều thì khách hàng có xác suất 255/256 trả về SID ←m[2 : 44]. Ta sẽ giả định rằng tất cả SID được máy khách trả về đều bao gồm các byte này và sẽ xem lại nó trong phần sau.

Các máy khách MEGA sử dụng công thức Garner để thực hiện giải mã RSA-CRT, quá trình giải mã một bản mã RSA $c$ để gửi tin nhắn $m$. Các phương trình này cũng như bước trích xuất SID được trình bày chi tiết dưới đây.

$$
m_p ←c^{d \ mod \ (p−1)} \ mod \ p
$$

$$
m_q ←c^{d \ mod \ (q−1)} \ mod \ q
$$

$$
m ←((m_p −m_q)\ u \ mod \ p \ ) \ q + m_q
$$

$$
SID ←m[2 : 44]
$$

## 2. Original MEGA Attack of Backendal, Haller, and Paterson

Trong cuộc tấn công này, attacker thay đổi văn bản mã hóa của block $ct_{40}$, đây là khối văn bản mã hóa cuối cùng chỉ tương ứng với các byte của $u$ và không có trường độ dài hoặc byte đệm. Kẻ tấn công gửi `wrapped key` đã bị thay đổi này và bản mã RSA $q^{e}_{guess} \ mod \ N$ cho máy khách. Máy khách giải mã và giải mã khóa bọc để lấy khóa riêng (q,p,d,u′,P) trong đó $u′ ≠ u$ không phải là giá trị chính xác của $q^{−1} \ mod \ p$ để sử dụng trong quá trình giải mã RSA-CRT

Nếu $q_{guess} \ < \ q$, thì $m_p ≡ m_q \ (mod \ p)$,

do đó $(m_p − m_q) \ u = 0$ và $m = m_q < q$.

Do đó tất cả các byte SID đều bằng 0.

Nếu $q_{guess} >= q$ thì $m_p ≠ m_q \ (mod \ p)$, do đó $h ≠ 0$ và $m > q$.

Do đó, các byte SID khác 0 với xác suất cao. Do đó, attacker sử dụng SID bằng 0 hay khác 0 làm tiên đoán cho việc $q_{guess}$ được chọn nhỏ hơn hay lớn hơn $q$. Thực hiện tìm kiếm nhị phân trên giá trị của $q$ cho đến khi biết đủ nhiều bit quan trọng nhất của $q$.

Khi đã biết đủ most significant bits của q, attacker sau đó sử dụng kỹ thuật phân tích mật mã của $Coppersmith$ ([https://hackmd.io/@nomorecaffeine/By_SVppIh](https://hackmd.io/@nomorecaffeine/By_SVppIh)) để khôi phục các least significant bit của $q$, và do đó thu được hệ số hóa đầy đủ của N. Theo tiệm cận, cuộc tấn công này phục hồi phân tích N theo thời gian đa thức khi kẻ tấn công biết một nửa số bit có ý nghĩa nhất của $q$. Trong ngữ cảnh của MEGA, đó là 512 bit, yêu cầu 512 lần đăng nhập để có được. Trong thực tế, cuộc tấn công này có thể cực kỳ chậm ở giới hạn tiệm cận và việc triển khai phương pháp của $Coppersmith$ thường sử dụng hầu hết most significant bits bổ sung, giúp việc triển khai nhanh hơn và dễ hiểu hơn. Nhóm chuyên gia về khái niệm được liên kết với cuộc tấn công ban đầu sử dụng 683 most significant bits và do đó yêu cầu 683 lần đăng nhập.

### Coppersmith method

Gỉa sử ta đã thu được 683 most significant bits của q gọi là $a$. Phương trình của ta sẽ như sau:

$$
f(x) = a + x \ mod \ q
$$

tồn tại $r$ sao cho $a + r = q$ khi đó $r$ là các bit thấp bị thiếu của $q$.

Ta sẽ sử dụng lattice sau để recover smallroot của f(x)

Lattice:
                   |X^2  X*a  0 |
               M = |  0    X  a |
                   |  0    0  n |

## 3. Mô phỏng cuộc tấn công

Bản tấn công này sẽ chỉ chú trọng vào việc khai thác thuật toán RSA-CRT nên sẽ không bao gồm quá trình mã hóa và giải mã bộ khóa và các bước cần thiết khác.

Hàm `rsa_decrypt` như sau:

def rsa_decrypt(c, sk, do_unpad=True):
    """
    Compute c^d mod n (RSA decryption)
    :param c: ciphertext in bytes
    :param sk: RSA private key, format: (n, e, d, p, q, dp, dq, u)
    :param do_unpad: do unpad the plaintext
    :param do_ct_len_encode: if True, length decode the ciphertext
    """
    c = bytes_to_long(c)
    n, e, d, p, q, u = sk

    dp = d % (p-1)
    dq = d % (q-1)
    # Decrypt using CRT and Garner's formula
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)

    # Garner's formula for CRT
    t = (mp - mq) % p
    h = (u * t) % p
    m = (h * q + mq) % n

    if do_unpad:
        m_pad = long_to_bytes(m, 2048//8)
        if m_pad[1] != 0:
            m_pad = b"\x00" + m_pad
        m = m_pad[2:]
    return m[:23]

set up các tham số

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
d = inverse(e, (p-1)*(q-1))
u = inverse(q, p)

Các bước thực hiện

Gọi x là số bit của N.

1. Garble $u$
2. Thực hiện tìm kiếm nhị phân cho số nguyên tố q nếu q < p (tương ứng q > p) của N
1. Bắt đầu với bounds `(low, up) = (2^(x-1), sqrt(N)) (resp. (sqrt(N),`
2. Test `m = (low + up)//2`
3. Nếu oracle trả về 0 thì `m < q`, vì `m' = m < q < 2^1024` có nghĩa là SID được trả về toàn các byte 0 → bounds được sửa thành `(m, up)`
4. Mặt khác (tức là khi SID có byte khác 0), chúng ta có `m >= q` và cập nhật bounds thành `(low, m)`
3. Sau khi khôi phục được 683 most significant bits, ta sẽ dùng coppersmith để khôi phục phần còn lại.

#Garble u
u_garbled = (u ^ (randbelow(1 << 128) << 128))

#Start with bounds (low, up) = (2^(x-1), sqrt(N)) (resp. (sqrt(N),2^x-1))
low = 1 << (int(n).bit_length()//2 - 1)
up = (1 << ((int(n).bit_length() + 1)//2)) - 1

from tqdm import tqdm

#Perform a binary search for the prime q if q < p (resp. q > p) of N
for i in tqdm(range(683)):
    # print('Running binary search, recovered bits: ', i)
    sid = (low + up) >> 1
    r = bytes_to_long(rsa_decrypt(long_to_bytes(pow(sid, e, n)), sk))
    if r == 0:
        low = sid
    else:
        up = sid

Lattice attack

remaining_bits = n.bit_length() // 6
import sage.all as sage

for a in [up, low]:
    # remove lower bits
    a >>= remaining_bits
    a <<= remaining_bits

    # Use the following lattice to recover the small root r of
    # f(x) = x + a mod q, which exists since a + r = q when r is set
    # to the missing lower bits of q.
    # Lattice:
    #       |X^2  X*a  0 |
    #   M = |  0    X  a |
    #       |  0    0  n |
    R = (1 << remaining_bits)
    M = sage.matrix([[R**2, R*a, 0], [0, R, a], [0, 0, n]])
    B = M.LLL()
    PR = sage.PolynomialRing(sage.ZZ, 'x')
    x = PR.gen()
    v2 = B[0][0] / R**2
    v1 = B[0][1] / R
    v0 = B[0][2]
    Q = v2 * x**2 + v1 * x + v0

    roots = Q.roots()
    if len(roots) == 0:
        continue

    for root, _ in roots:
        q = a + int(root)
        if q != 0 and n % q == 0 and 1 < q < n:
            print("found q = ", q)
    break

Full script:

from Crypto.Util.number import *

def rsa_decrypt(c, sk, do_unpad=True):
    """
    Compute c^d mod n (RSA decryption)
    :param c: ciphertext in bytes
    :param sk: RSA private key, format: (n, e, d, p, q, dp, dq, u)
    :param do_unpad: do unpad the plaintext
    :param do_ct_len_encode: if True, length decode the ciphertext
    """
    c = bytes_to_long(c)
    n, e, d, p, q, u = sk

    dp = d % (p-1)
    dq = d % (q-1)
    # Decrypt using CRT and Garner's formula
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)

    # Garner's formula for CRT
    t = (mp - mq) % p
    h = (u * t) % p
    m = (h * q + mq) % n

    if do_unpad:
        m_pad = long_to_bytes(m, 2048//8)
        if m_pad[1] != 0:
            m_pad = b"\x00" + m_pad
        m = m_pad[2:]
    return m[:23]

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
d = inverse(e, (p-1)*(q-1))
u = inverse(q, p)

from secrets import randbelow

#Garble u
u_garbled = (u ^ (randbelow(1 << 128) << 128))

#Start with bounds (low, up) = (2^(x-1), sqrt(N)) (resp. (sqrt(N),2^x-1))
low = 1 << (n.bit_length()//2 - 1)
up = (1 << ((n.bit_length() + 1)//2)) - 1

sk = n, e, d, p, q, u_garbled

from tqdm import tqdm

for i in tqdm(range(683)):
    # print('Running binary search, recovered bits: ', i)
    sid = (low + up) >> 1
    r = bytes_to_long(rsa_decrypt(long_to_bytes(pow(sid, e, n)), sk))
    if r == 0:
        low = sid
    else:
        up = sid

remaining_bits = n.bit_length() // 6
import sage.all as sage

for a in [up, low]:
    # remove lower bits
    a >>= remaining_bits
    a <<= remaining_bits

    # Use the following lattice to recover the small root r of
    # f(x) = x + a mod q, which exists since a + r = q when r is set
    # to the missing lower bits of q.
    # Lattice:
    #       |X^2  X*a  0 |
    #   M = |  0    X  a |
    #       |  0    0  n |
    R = (1 << remaining_bits)
    M = sage.matrix([[R**2, R*a, 0], [0, R, a], [0, 0, n]])
    B = M.LLL()
    PR = sage.PolynomialRing(sage.ZZ, 'x')
    x = PR.gen()
    v2 = B[0][0] / R**2
    v1 = B[0][1] / R
    v0 = B[0][2]
    Q = v2 * x**2 + v1 * x + v0

    roots = Q.roots()
    if len(roots) == 0:
        continue

    for root, _ in roots:
        q = a + int(root)
        if q != 0 and n % q == 0 and 1 < q < n:
            print("found q = ", q)
    break

output

found q =  179079555967946513846412974502222132324799172859800570165634304241261674546988302684852534473029831509003128779050699947976179973392809728977871381206528831213664896355857852229074227320476110325945234150043533524209726446913554290220018590548521230046576031496976699766794825810205615662831693651912169459739

**References**

[MEGA: Malleable Encryption Goes Awry](https://mega-awry.io/)

[https://mega-awry.io/pdf/mega-malleable-encryption-goes-awry.pdf](https://mega-awry.io/pdf/mega-malleable-encryption-goes-awry.pdf)

[https://github.com/MEGA-Awry/attacks-poc](https://github.com/MEGA-Awry/attacks-poc)