Paper 2020/1491

Partitioning Oracle Attacks

Julia Len, Paul Grubbs, and Thomas Ristenpart

Abstract

In this paper we introduce partitioning oracles, a new class of decryption error oracles which, conceptually, take a ciphertext as input and output whether the decryption key belongs to some known subset of keys. We introduce the first partitioning oracles which arise when encryption schemes are not committing with respect to their keys. We detail novel adaptive chosen ciphertext attacks that exploit partitioning oracles to efficiently recover passwords and de-anonymize anonymous communications. The attacks utilize efficient key multi-collision algorithms --- a cryptanalytic goal that we define --- against widely used authenticated encryption with associated data (AEAD) schemes, including AES-GCM, XSalsa20/Poly1305, and ChaCha20/Poly1305. We build a practical partitioning oracle attack that quickly recovers passwords from Shadowsocks proxy servers. We also survey early implementations of the OPAQUE protocol for password-based key exchange, and show how many could be vulnerable to partitioning oracle attacks due to incorrectly using non-committing AEAD. Our results suggest that the community should standardize and make widely available committing AEAD to avoid such vulnerabilities.

Note: We updated our work to include a better discussion of prior work and incorporate miscellaneous feedback.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. MAJOR revision.USENIX Security 2021
Keywords
authenticated encryptioncommitting AEADrobustnesskey commitmentAES-GCMchosen ciphertext attack
Contact author(s)
jlen @ cs cornell edu
History
2020-12-11: revised
2020-11-29: received
See all versions
Short URL
https://ia.cr/2020/1491
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1491,
      author = {Julia Len and Paul Grubbs and Thomas Ristenpart},
      title = {Partitioning Oracle Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1491},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1491}},
      url = {https://eprint.iacr.org/2020/1491}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.