https://eprint.iacr.org/2022/914

What a lovely hat

Is it made out of tin foil?

IACR Logo
Cryptology ePrint Archive

  * Papers
        Updates from the last:
      + 7 days
      + 31 days
      + 6 months
      + 365 days
      + -------------------------------------------------------------
      + Listing by year
      + All papers
      + Compact view
      + -------------------------------------------------------------
      + How to cite
      + -------------------------------------------------------------
      + Harvesting metadata
  * Submissions
      + Submit a paper
      + Revise or withdraw a paper
      + Acceptance and publishing conditions
  * About
      + Goals and history
      + News
      + Statistics
      + Contact

Search Button
[                    ] Search
Advanced search

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)
    [file-pdf]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 [copy-outli]Copy to clipboard

@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}
}

IACR Logo
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.