Paper 2023/797

Entropy Suffices for Key Guessing

Timo Glaser, Ruhr University Bochum
Alexander May, Ruhr University Bochum
Julian Nowakowski, Ruhr University Bochum
Abstract

Modern (lattice-based) cryptosystems typically sample their secret keys component-wise and independently from a discrete probability distribution $\chi$. For instance, KYBER has secret key entries from the centered binomial distribution, DILITHIUM from the uniform distribution, and FALCON from the discrete Gaussian. As attacks may require guessing of a subset of the secret key coordinates, the complexity of enumerating such sub-keys is of fundamental importance. Any length-$n$ sub-key with entries sampled from $\chi$ has entropy $\operatorname{H}(\chi)n$, where $\operatorname{H}(\chi)$ denotes the entropy of $\chi$. If $\chi$ is the uniform distribution, then it is easy to see that any length-$n$ sub-key can be enumerated with $2^{\operatorname{H}(\chi)n}$ trials. However, for sub-keys sampled from general probability distributions, Massey (1994) ruled out that the number of key guesses can be upper bounded by a function of the entropy alone. In this work, we bypass Massey's impossibility result by focussing on the typical cryptographic setting, where key entries are sampled independently component-wise from some distribution $\chi$, i.e., we focus on $\chi^n$. We study the optimal key guessing algorithm that enumerates keys in $\chi^n$ in descending order of probability, but we abort at a certain probability. As our main result, we show that for any discrete probability distribution~$\chi$ our aborted key guessing algorithm tries at most $2^{\operatorname{H}(\chi)n}$ keys, and its success probability asymptotically converges to $\frac 1 2$. Our algorithm allows for a quantum version with at most $2^{\operatorname{H}(\chi) n/ 2}$ key guesses. In other words, for any distribution $\chi$, we achieve a Grover-type square root speedup, which we show to be optimal. For the underlying key distributions of KYBER and FALCON, we explicitly compute the expected number of key guesses and their success probabilities for our aborted key guessing for all sub-key lengths $n$ of practical interest. Our experiments strongly indicate that our aborted key guessing, while sacrificing only a factor of two in success probability, improves over the usual (non-aborted) key guessing by a run time factor exponential in $n$.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
cryptanalysiskey-guessingentropy
Contact author(s)
timo glaser @ rub de
alex may @ rub de
julian nowakowski @ rub de
History
2023-06-06: approved
2023-05-31: received
See all versions
Short URL
https://ia.cr/2023/797
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/797,
      author = {Timo Glaser and Alexander May and Julian Nowakowski},
      title = {Entropy Suffices for Key Guessing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/797},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/797}},
      url = {https://eprint.iacr.org/2023/797}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.