Paper 2023/797

Entropy Suffices for Key Guessing

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$.