Breaking The Unbreakable: Meet Malleable Encryption Goes Awry

As an academic, I spend a good amount of time reading papers and I love solving cryptography puzzles. So when a paper drops that cracks the…

Breaking The Unbreakable: Meet Malleable Encryption Goes Awry

As an academic, I spend a good amount of time reading papers and I love solving cryptography puzzles. So when a paper drops that cracks the encryption on a Cloud-based platform, it’s a dream to read and discover new ways to crack cryptography, and how old ways can still be applied. I appreciate it is not good for the systems involved, but it does highlight how poor some of our designs around encryption can be.

The paper is written by researchers at ETH Zurich [paper][Web]:

The analysis relates to MEGA, and which is a massive cloud infrastructure which uses User-Controlled end-to-end Encryption (UCE), with over 250 million registered users and 1000 PB of stored data. Overall, the paper does not have just one attack, but five:

  • RSA Key Recovery: This recovers a user’s private key using 512 attempted logins.
  • Plaintext Recovery: This recovers all the related encryption key material, and which can be used to decrypt all of the communications and files related to a user.
  • Framing: This can create files within a user’s storage area, and which cannot be differentiated from the ones that have been uploaded in a genuine way.
  • Integrity: This is similar in scope to the framing attack, but less sophisticated.
  • GaP-Bleichenbacher: This crack RSA encryption using a modified Bleichenbacher method.

In a series of articles I will explain each of the methods, so let’s start with RSA key recovery.

RSA Key Recovery

The key generation method is outlined in Figure 1. It involves an initial password, and which derives an authentication key (used to authenticate the user) and an encryption key (which is used to encrypt a master key, and which is used to encrypt all the other related user content). The keys are an RSA key pair (for data sharing), Curve25519 key pair (for messages), and an Ed25519 key pair (for signing keys). Every file or folder is then encrypted with a node key, and where all of the keys are encrypted with AES ECB with a master key and stored on MEGA’s servers. A password can then be used to regenerate all of the keys.

Figure 1: Key generation [here]

RSA key are used for data sharing node keys — the keys which encrypt files — with other users, along with sharing session IDs. If Alice wants to share a file with Bob, she will encrypt the file with Bob’s public key (B_pk), and for Bob to decrypt it with his private key (B_sk). But, Bob’s private key is stored on MEGA’s servers, and where the researchers were able to recover the private key by discovering one of the prime number (p) factors used in the RSA modulus (N). It was found that it need 512 requests to discover the prime number used. Once this is discovered it is fairly easy to discover the other prime number involved and then from this to discover the decryption key. With N (which is public) and the discovered prime number (p), we can discover the other prime number (q) with:

Next, we can derive PHI with:

And then the decryption exponent with:

And finally, decrypt the ciphertext (c) with:

Conclusions

The paper is a feast of cryptographic discovery, so watch this space for more on the other methods.