RSA & Chinese Remainder Theorem MEGA Exploits

There is a lot of data we are dealing with today. Most of us have multiple digital devices. Also, most of us are enrolled in multiple online platforms. Keeping our private data locally and synchronising it across devices is impractical. Many cloud providers offer solutions to store our private data encrypted in the cloud. They offer us storage and secure protocols that will help them achieve that goal. For this use case, the Cloud Provider shall not be able to decrypt our data by itself, i.e. only the user should be able to do that by downloading the data (file) and decrypting it locally with a secret key she and only she can derive.

All of the above holds only if there are secure protocols in place. Otherwise, the Cloud Provider is in position to derive our secret keys and decrypt our private data. Not acceptable, not acceptable at all!

This article is inspired by not that long published article and POC that demonstrates how MEGA, the leading cloud storage platform, adversary that has compromised MEGA's servers or Man-in-the-Middle proxy is in position to exploit the users and decrypt their files.

I like to write things down. The article depicts my understanding how these exploits work and it will put some light:

• How RSA works
• How RSA decryption with Chinese Remainder Theorem Works: RSA-CRT
• How MEGA was in position to derive the user's private RSA key
• How MEGA was in position to derive the secret key the user's file has been encrypted with
• What should we consider when implementing secure protocols in order to avoid these kind of exploits.

Chinese Remainder Theorem

Fermat's Little Theorem is the key of all derivations we will be dealing with. It states that if a and p are mutually prime and p is prime then:

a ^ (p-1) ≡ 1 (mod p)        

The Chinese Remainder Theorem provides solution to a set of congruences. Let's say we have a number x, mutually prime numbers n1, n2, ... , nk, any integers a1, a2, ... , ak and the following congruences:

x ≡ a1 (mod n1)

x ≡ a2 (mod n2)

. . . . .

x ≡ ak (mod nk)        

The theorem states that there is a solution x modulo N = n1 * n2 ... * nk that satisfies the congruences above. What is that solution? Let's solve it for a system of two congruences where:

• a1 = mp
• a2 = mq
• n1 = p
• n2 = q
• p > q

x ≡ mp (mod p)

x ≡ mq (mon q)

=> 

x = p * i + mp

p * i + mp ≡ mq (mod q)

p * i ≡ mq - mp (mod q) 

t ≡ (mq - mp) (mod q) 

t = (mq - mp) % q

# u * p ≡ 1 (mod q) # u is inverse of p mod q

u * p * i ≡ u * t (mod q)

i  ≡ u * t (mod q) 

h = (u * t) % q 

=>

i ≡ h (mod q)

i = q * j + h

x = p * (q * j + h) + mp

x = p * q * j + p * h + mp

x ≡ p * h + mp (mod p * q)        

What if mp = mq = m ?

x ≡ m (mod p)

x ≡ m (mod q)

x ≡ p * h + mp (mod p * q)

t = m - m  = 0 

h = u * 0 = 0

x ≡ p * 0 + m (mod p * q)

x ≡ m (mod p * q)        

In other words :

x ≡ m (mod p)

x ≡ m (mod q)

=>

x ≡ m (mod p * q)        

RSA

The RSA public and private keys are derived as:

# Pick 2 large prime numbers p and q

n = p * q

# pick e that is mutually prime with (p-1)*(q-1)

e = 65537 

# Calculate d

e * d ≡ 1 (mod (p-1) * (q-1)) 

# d >= 0 d and d < (p-1) * (q-1)        

The RSA public key is:

pk = (n , e)

The RSA private key is:

sk = d

A message m satisfying m < n can be encrypted with the RSA public key as:

c ≡ m ^ e  (mod n)

c = m ^ e % n        

The ciphertext c can be decrypted with the RSA private key as:

m' ≡ c ^ d (mod n)

m' = c ^ d % n        

Why this works, i.e. why m = m' (mod p * q) ? This congruence can be proven if we show that:

c ^ d ≡ m (mod p)

c ^ d ≡ m (mod q)        

So:

e * d ≡ 1 (mod (p-1) * (q-1))

e * d - 1 ≡ 0 (mod (p-1) * (q-1))

=>

e * d - 1 = k * (p -1) = l * (q-1)

e * d = k * (p -1) + 1

e * d = l * (k -1) + 1

# Let's prove the congruence for p

c ^ d  = (m ^ e) ^ d =  m ^ (e * d) =

= m ^ (k * (p - 1) + 1) = 

= m ^ (k * (p - 1)) * m = 

= (m ^ (p-1)) ^ k * m 

≡ 1 ^ k * m  (mod p) # By Fermat's Little Theorem

≡ m (mod p)

# The derivation for the congruence with q

c ^ d  = (m ^ e) ^ d =  m ^ (e * d) =

= m ^ (l * (q - 1) + 1) = 

= m ^ (l * (q - 1) + 1) * m = 

= (m ^ (q-1)) ^ l * m

≡ 1 ^ l * m  (mod q)

≡ m (mod q) # By Fermat's Little Theorem        

It follows by the Chinese Remainder Theorem solution derived above that:

c ^ d ≡ m (mod p)

c ^ d ≡ m (mod q)

=>

c ^ d ≡ m (mod p * q)

c ^ d ≡ m (mod n)

m' = c ^ d % n = m        

RSA - CRT

The RSA decryption is usually implemented by using the Chinese Remainder Theorem that will speed up the process a lot. For that purpose, the private key is usually stored as:

(p, q, d, u)

where u * p ≡ 1 (mod q).

Let's us derive the algorithm.

d ≡ dp (mod (p-1))

dp = d % (p - 1)

=> 

d = (p-1) * i + dp

# - - - - -

d ≡ dq (mod (q-1))

dq = d % (q - 1)

=> 

d = (q-1) * j + dq

# - - - - -

c ^ d ≡ c ^ ((p-1) * i + dp) (mod p)

c ^ d ≡ c ^ ((p-1) * i) * c ^ dp (mod p)

c ^ d ≡ (c ^ (p-1)) ^ i * c ^ dp (mod p)

c ^ d ≡ 1 ^ i * c ^ dp (mod p) # By Fermat's Little Theorem

c ^ d ≡ c ^ dp (mod p) ≡ mp (mod p)

mp = c ^ dp % p

# - - - - -

c ^ d ≡ c ^ ((q-1) * j + dq) (mod q)

c ^ d ≡ c ^ ((q-1) * j) * c ^ dq (mod q)

c ^ d ≡ (c ^ (q-1)) ^ j * c ^ dq (mod q)

c ^ d ≡ 1 ^ j * c ^ dq (mod q) # By Fermat's Little Theorem

c ^ d ≡ c ^ dq (mod q) ≡ mq (mod q)

mq = c ^ dq % q        

From the Chinese Remainder Theorem solution derivation above we have:

m' ≡ mp (mod p)

m' ≡ mq (mod q)

t = (mq - mp) % q

h = (u * t) % q 

m' ≡ p * h + mp (mod p * q)

# Note that:
# mp < p
# h < = q-1
# p * h <= p * (q-1)
# p * h + mp < p * (q - 1) + p = pq

=> 

m' = p * h + mp        

The concise RSA-CRT decryption algorithm is:

RSA - CRT

dp = d % (p-1)

dq = d % (q - 1)

mp = c ^ dp % p

mq = c ^ dq % q

t = (mq - mp) % q

h = u * t % q

m' = h * p + mp        

Now let's see how we can exploit the above RSA-CRT decryption for incorrectly implemented Cloud Provider protocols.

User Sign Up

The following toy outline does not match completely the MEGA protocol. I will use very simplified setup in order to show what the exploit is.

When the user signs up with the Cloud Provider she generates:

• ID_KEY: identification key
• ENC_KEY: Password derived encryption key (PBKDF2)
• MASTER_KEY: Random master key
• PK and SK: RSA public/private key

The user sends to the Cloud Provider:

• ID_KEY
• PK
• MASTER_KEY_ENC: MASTER_KEY encrypted with AES ECB and ENC_KEY as secret key
• SK_ENC: SK encrypted with AES ECB and MASTER_KEY as secret key

The format of SK is:

| len(p) | p | len(q) | q | len(d) | d | len(u) | u | padding

where:

• len(x) is 2 bytes length of x
• | means concatenation
• padding adds bytes up to 16 in order to match the AES encryption block size of 16 bytes (128 bits)

For 2048 RSA:

• len(p) = 128
• len(q) = 128
• len(d) = 256
• len(u) = 128
• len(padding) = 8

After the sign up, the user does not keep anything on her local device but the ID_KEY. She knows her password only.

User Login and RSA Secret Key Recovery

When the user wants to login she sends to the Cloud Provider her ID_KEY.

The Cloud Provider generates:

• SID: random session identifier
• SID_ENC: encrypts the generated SID with the user's PK

and sends to the user:

• SID_ENC
• MASTER_KEY_ENC
• SK_ENC

The user, based on the password she knows, regenerates the ENC_KEY. After that, from the received crypto material she obtains:

• MASTER_KEY: decrypted with the ENC_KEY
• SK: decrypted with the MASTER_KEY
• SID: Decrypted with the SK

The user returns the decrypted SID to the Cloud Provider that checks if the generated and returned SIDs match. If they match the user is logged on.

Now, how can the Cloud Provider abuse the login protocol and find the user's RSA private key SK?

What if the Cloud Provider injects SID = m < p?

What if m < p?
- - - - - - - - -
=> m = mp 

t = (mq - mp) % q

t = (mq - m) % q

t = 0 # because mq % q = m % q

h = u * t % q

h  = 0

m' = h * p + mp

m' = mp = m        

Note that m' (decrypted SID) does not depend on u (part of the private RSA key SK). The Cloud Provider can modify u and still the returned SID will match the generated one.

On the contrary, if m >= p, the modified u will influence decryption with not zero t and h that will produce SID that does not match the generated one on the server.

The Cloud Provider can use the following binary tree logic to derive the RSA private key SK:

N = bit_length(n)

low = 2 ^ (N/2 -1)

high = 2 ^ (N/2) -1

threshold = 1000000

# Note the structure of the SK
# | len(p) | p | len(q)| q | len(d) | d |  len(u) | u | padding
# The SK_ENC has the same structure because of AES ECB
# Modify SK_ENC

SK_ENC_MODIFIED = SK_ENC

#skip the padding and modify a bit of u

SK_ENC_MODIFIED[-16 - 1] ^= 1

while high - low > threshold:

    SID = (low + high) // 2

    SID_ENC = PK_ENCRYPT(SID)
    
    Send SID_ENC, MASTER_KEY_ENC and SK_ENC_MODIFIED to the user

    Receive SID_R from the user

    if SID == SID_R:
        # p > SID
        low = SID
    else:
        # p < SID
        high = SID

# At this point Cloud Provider can brute force the value of p

from p = low to high:
    
    if n % p == 0:
        
        break

q = n // q

n = q * p

e = 65537

d = inverse(e, (p - 1)*(q - 1))

u = inverse(p, q)

SK =(p, q, d, u)

# Cloud Provider recovers the user's RSA private key SK at this point        

You can apply these principles and the acquired knowledge on the Megalomaniac 1 CryptoHack challenge.

Plaintext Recovery

Before sending file to be stored in the Cloud, the user generates:

• NODE_KEY: random encryption bit
• NODE_KEY_ENC: encrypted NODE_KEY with AES ECB and MASTER_KEY as secret key
• FILE_ENC: encrypted file with AES ECB and NODE_KEY as secret key

The user sends to the Cloud Provider:

• NODE_KEY_ENC
• FILE_ENC

The Cloud Provider keeps NODE_KEY_ENC as encrypted file metadata attribute.

The user reverses the process when she wants to retrieve and decrypt the file.

Now, how can the Cloud Provider, after they have recovered the user's RSA private key SK, abuse the login protocol and find the NODE_KEY for particular encrypted file stored on the server?

What if the Cloud Provider generates SID = m = u * p ?

What if m = u * p ?

mp ≡ m ≡ u * p

mp ≡ 0 (mod p)

mp = 0

mq ≡ m ≡ u * p = inv(p) * p ≡ 1 mod q 

mq ≡ 1 mod q

mq = 1

t = (1 - 0) % q

t = 1

h = u * t % q

h = u % q

h = u # because u < q

m' = h * p + mp

m' = u * p

u = m' / p        

The decrypted message m' after division with p completely recovers u. How can the Cloud Provider use this construct?

The idea is to modify SK_ENC and replace some cipher text blocks that belong to u with the NODE_KEY_ENC.

We don't want to replace the most significant bytes of u and disturb its value considerably. Instead, we can take the original first len(padding) (8 bytes), concatenate the NODE_KEY_ENC (16 bytes) and finally concatenate the remaining SK_ENC suffix bytes. The user will decrypt these injected NODE_KEY_ENC bytes for us and return NODE_KEY as part of u'.

SK_ENC_MODIFIED = SK_ENC[:-len(u)] + NODE_KEY_ENC + SK_ENC[-len(u) + len(NODE_KEY_ENC:]

SID = u * p

SID_ENC = PK_ENCRYPT(SID)
    
Send SID_ENC, MASTER_KEY_ENC and SK_ENC_MODIFIED to the user

Receive SID_R from the user

u' = bytes_to_long(SID_R) // p

u'_bytes = long_to_bytes(u')

# u' with very high probability contains decrypted NODE_KEY at the replacement index

LEN_PADDING = 8 // for 2048 RSA keys

NODE_KEY = u'_bytes[LEN_PADDING: LEN_PADDING + len(NODE_KEY_ENC)
        

Once the Cloud Provider has the NODE_KEY, it can decrypt the associated encrypted file FILE_ENC.

You can apply these principles and the acquired knowledge on the Megalomaniac 3 CryptoHack challenge.

Corrected Protocol

A secure protocol shall include integrity verification. Before encrypting the content, we shall calculate the HASH of the content. After that we shall apply the encryption:

ENCRYPT(content || HASH(content))        

With this kind of encryption, SK_ENC can't be modified without detection on the client side. In addition, the client application can always check if u = inv(p) (mod q) before RSA-CRT decryption.

Marjan