Paper 2023/329

Caveat Implementor! Key Recovery Attacks on MEGA

Martin R. Albrecht, King's College London
Miro Haller, ETH Zurich
Lenka Mareková, Royal Holloway University of London
Kenneth G. Paterson, ETH Zurich

MEGA is a large-scale cloud storage and communication platform that aims to provide end-to-end encryption for stored data. A recent analysis by Backendal, Haller and Paterson (IEEE S&P 2023) invalidated these security claims by presenting practical attacks against MEGA that could be mounted by the MEGA service provider. In response, the MEGA developers added lightweight sanity checks on the user RSA private keys used in MEGA, sufficient to prevent the previous attacks. We analyse these new sanity checks and show how they themselves can be exploited to mount novel attacks on MEGA that recover a target user's RSA private key with only slightly higher attack complexity than the original attacks. We identify the presence of an ECB encryption oracle under a target user's master key in the MEGA system; this oracle provides our adversary with the ability to partially overwrite a target user's RSA private key with chosen data, a powerful capability that we use in our attacks. We then present two distinct types of attack, each type exploiting different error conditions arising in the sanity checks and in subsequent cryptographic processing during MEGA's user authentication procedure. The first type appears to be novel and exploits the manner in which the MEGA code handles modular inversion when recomputing $u = q^{-1} \bmod p$. The second can be viewed as a small subgroup attack (van Oorschot and Wiener, EUROCRYPT 1996, Lim and Lee, CRYPTO 1998). We prototype the attacks and show that they work in practice. As a side contribution, we show how to improve the RSA key recovery attack of Backendal-Haller-Paterson against the unpatched version of MEGA to require only 2 logins instead of the original 512. We conclude by discussing wider lessons about secure implementation of cryptography that our work surfaces.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
CryptanalysisCloud storageKey recoveryKey overwriting attackSmall subgroup attackECB modeMEGA
Contact author(s)
martin albrecht @ kcl ac uk
miro haller @ ethz ch
lenka marekova 2018 @ rhul ac uk
kenny paterson @ inf ethz ch
2023-03-06: approved
2023-03-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R. Albrecht and Miro Haller and Lenka Mareková and Kenneth G. Paterson},
      title = {Caveat Implementor! Key Recovery Attacks on MEGA},
      howpublished = {Cryptology ePrint Archive, Paper 2023/329},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.