CryptoDB
The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: |
|
---|---|
Download: | |
Presentation: | Slides |
Conference: | PKC 2023 |
Award: | Best paper award |
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. |
BibTeX
@inproceedings{pkc-2023-32764, title={The Hidden Number Problem with Small Unknown Multipliers: Cryptanalyzing MEGA in Six Queries and Other Applications}, publisher={Springer-Verlag}, doi={10.1007/978-3-031-31368-4_6}, author={Nadia Heninger and Keegan Ryan}, year=2023 }