Paper 2023/797
Entropy Suffices for Key Guessing
Abstract
Modern (latticebased) cryptosystems typically sample their secret keys componentwise 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 subkeys is of fundamental importance. Any length$n$ subkey 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$ subkey can be enumerated with $2^{\operatorname{H}(\chi)n}$ trials. However, for subkeys 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 componentwise 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 Grovertype 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 subkey 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 (nonaborted) key guessing by a run time factor exponential in $n$.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 cryptanalysiskeyguessingentropy
 Contact author(s)

timo glaser @ rub de
alex may @ rub de
julian nowakowski @ rub de  History
 20230606: approved
 20230531: received
 See all versions
 Short URL
 https://ia.cr/2023/797
 License

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