Paper 2019/258

Tight Time-Memory Trade-offs for Symmetric Encryption

Joseph Jaeger and Stefano Tessaro

Abstract

Concrete security proofs give upper bounds on the attacker's advantage as a function of its time/query complexity. Cryptanalysis suggests however that other resource limitations - most notably, the attacker's memory - could make the achievable advantage smaller, and thus these proven bounds too pessimistic. Yet, handling memory limitations has eluded existing security proofs. This paper initiates the study of time-memory trade-offs for basic symmetric cryptography. We show that schemes like counter-mode encryption, which are affected by the Birthday Bound, become more secure (in terms of time complexity) as the attacker's memory is reduced. One key step of this work is a generalization of the Switching Lemma: For adversaries with $S$ bits of memory issuing $q$ distinct queries, we prove an $n$-to-$n$ bit random function indistinguishable from a permutation as long as $S \times q \ll 2^n$. This result assumes a combinatorial conjecture, which we discuss, and implies right away trade-offs for deterministic, stateful versions of CTR and OFB encryption. We also show an unconditional time-memory trade-off for the security of randomized CTR based on a secure PRF. Via the aforementioned conjecture, we extend the result to assuming a PRP instead, assuming only one-block messages are encrypted. Our results solely rely on standard PRF/PRP security of an underlying block cipher. We frame the core of our proofs within a general framework of indistinguishability for streaming algorithms which may be of independent interest.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Keywords
provable securitytime-memory trade-offs
Contact author(s)
jsjaeger @ eng ucsd edu
History
2019-03-06: received
Short URL
https://ia.cr/2019/258
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/258,
      author = {Joseph Jaeger and Stefano Tessaro},
      title = {Tight Time-Memory Trade-offs for Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/258},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/258}},
      url = {https://eprint.iacr.org/2019/258}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.