Paper 2022/914

Cryptanalyzing MEGA in Six Queries

Keegan Ryan, University of California, San Diego
Nadia Heninger, University of California, San Diego
Abstract

In recent work, Backendal, Haller, and Paterson identified several exploitable vulnerabilities in the cloud storage provider MEGA. They demonstrated an RSA key recovery attack in which a malicious server can recover the client’s RSA private key. Their attack uses binary search to recover the private RSA key after 1023 client logins, and optionally could be combined with lattice methods for factoring with partial knowledge to reduce the number of logins to 512 in theory, or 683 in the published proof of concept. In this note, we give an improved attack that requires only six client logins to recover the secret key. Our optimized attack combines several techniques, including a modification of the extended hidden number problem and the structure of RSA keys, to exploit additional information revealed by MEGA’s protocol vulnerabilities. MEGA has emphasized that users who had logged in more than 512 times could have been exposed; these improved attacks show that this bound was conservative, and that unpatched clients should be considered vulnerable under a much more realistic attack scenario.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Lattice Attacks RSA Coppersmith Hidden Number Problem ECB Mode
Contact author(s)
kryan @ eng ucsd edu
nadiah @ cs ucsd edu
History
2022-07-14: approved
2022-07-13: received
See all versions
Short URL
https://ia.cr/2022/914
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/914,
      author = {Keegan Ryan and Nadia Heninger},
      title = {Cryptanalyzing MEGA in Six Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2022/914},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/914}},
      url = {https://eprint.iacr.org/2022/914}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.