Legendre PRF (Multiple) Key Attacks and the Power of Preprocessing
Alexander May and Floyd Zweydinger
Abstract
Due to its amazing speed and multiplicative properties the Legendre PRF recently finds widespread applications e.g. in Ethereum 2.0, multiparty computation and in the quantum-secure signature proposal LegRoast. However, its security is not yet extensively studied.
The Legendre PRF computes for a key on input the Legendre symbol in some finite field . As standard notion, PRF security is analysed by giving an attacker oracle access to . Khovratovich's collision-based algorithm recovers using in time with constant memory. It is a major open problem whether this birthday-bound complexity can be beaten.
We show a somewhat surprising wide-ranging analogy between the discrete logarithm problem and Legendre symbol computations. This analogy allows us to adapt various algorithmic ideas from the discrete logarithm setting.
More precisely, we present a small memory multiple-key attack on Legendre keys in time , i.e. with amortized cost per key. This multiple-key attack might be of interest in the Ethereum context, since recovering many keys simultaneously maximizes an attacker's profit.
Moreover, we show that the Legendre PRF admits precomputation attacks, where the precomputation depends on the public only -- and not on a key . Namely, an attacker may compute e.g. in precomputation time a hint of size . On receiving access to in an online phase, the attacker then uses the hint to recover the desired key in time only . Thus, the attacker's online complexity again beats the birthday-bound.
In addition, our precomputation attack can also be combined with our multiple-key attack. We explicitly give various tradeoffs between precomputation and online phase. E.g. for attacking keys one may spend time in the precomputation phase for constructing a hint of size . In an online phase, one then finds {\em all keys in total time} only .
Precomputation attacks might again be interesting in the Ethereum 2.0 context, where keys are frequently changed such that a heavy key-independent precomputation pays off.
@misc{cryptoeprint:2021/645,
author = {Alexander May and Floyd Zweydinger},
title = {Legendre {PRF} (Multiple) Key Attacks and the Power of Preprocessing},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/645},
year = {2021},
url = {https://eprint.iacr.org/2021/645}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.