Paper 2023/797

Entropy Suffices for Guessing Most Keys

Abstract

Historically, most cryptosystems chose their keys uniformly at random. This is in contrast to modern (lattice-based) schemes, which typically sample their keys from more complex distributions $\mathcal{D}$, such as the discrete Gaussian or centered binomial distribution. It is well-known that any key drawn from the uniform distribution $\mathcal{U}$ can be guessed using at most $2^{\operatorname{H}(\mathcal{U})}$ key guesses, where $\operatorname{H}(\mathcal{U})$ denotes the entropy of the uniform distribution. However, for keys drawn from general distributions $\mathcal{D}$ only a lower bound of $\Omega(2^{\operatorname{H}(\mathcal{D})})$ key guesses is known. In fact, Massey (1994) even ruled out that the number of key guesses can be upper bounded by a function of the entropy alone. When analyzing the complexity of so-called hybrid lattice-attacks (which combine lattice reduction with key guessing) one therefore usually conservatively underestimates the complexity of key guessing by $2^{\operatorname{H}(\mathcal{D})}$. However, a tight complexity analysis is missing, and due to Massey's result considered impossible. In this work, we bypass Massey's impossibility result by focusing on the typical cryptographic setting, where keys are drawn from $n$-fold product distributions $\mathcal{D} = \chi^n$. It is well known that the optimal key guessing algorithm enumerates keys in $\chi^n$ in descending order of probability. In order to provide a refined analysis, we allow to abort enumeration after a certain amount of key guesses. As our main result, we prove that for any discrete probability distribution $\chi$ the key guessing algorithm that we abort after $2^{\operatorname{H}(\chi)n}$ keys has asymptotically success probability $\frac 1 2$, taken over the random key choice. The aborted algorithm allows for a quantum version with success probability $\frac 1 2$ within $2^{\operatorname{H}(\chi)n/2}$ key guesses. In other words, for any distribution $\chi$, we achieve a Grover-type square root speedup. Furthermore, we show that for the distributions used in Kyber and Falcon, the aborted algorithm outperforms the non-aborted algorithm by an exponential factor in the runtime. Hence, for a typical multi-key scenario, where a (large scale) adversary wants to attack as many keys with as few as possible resources, our results show that it greatly pays off to tackle only the likely keys.