Paper 2022/914

The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications

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 could recover a client's private RSA key after 512 client login attempts. We show how to exploit additional information revealed by MEGA's protocol vulnerabilities to give an attack that requires only six client logins to recover the secret key. Our optimized attack combines several cryptanalytic techniques. In particular, we formulate and give a solution to a variant of the hidden number problem with small unknown multipliers, which may be of independent interest. We show that our lattice construction for this problem can be used to give improved results for the implicit factorization problem of May and Ritzenhofen.

Note: This revision contains extended analysis for the problem of recovering unknown multipliers and applies this analysis to the problem of implicit factoring.

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-11-03: revised
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 = {The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications},
      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.