Abstract The Fiat-Shamir transform is one of the most widely applied methods for secure signature construction. Fiat-Shamir starts with an interactive zero-knowledge identification protocol and transforms this via a hash function into a non-interactive signature. The protocol’s zero-knowledge property ensures that a signature does not leak information on its secret key $${\textbf{s}}$$ s , which is achieved by blinding $$\vec {s}$$ s → via proper randomness $${\textbf{y}}$$ y . Most prominent Fiat-Shamir examples are EC-DSA signatures and the new post-quantum standard ML-DSA (aka Dilithium). In practice, EC-DSA signatures have experienced fatal attacks via leakage of a few bits of the randomness $${\textbf{y}}$$ y per signature. Similar attacks now emerge for lattice-based signatures, such as ML-DSA. We build on, improve and generalize the pioneering leakage attack on ML-DSA by Liu, Zhou, Sun, Wang, Zhang, and Ming. Using a transformation to Integer LWE (ILWE), their attack can recover a 256-dimensional subkey of ML-DSA-44 from leakage in a single bit of $$\textbf{y}$$ y per signature, in any bit position $$j \ge 6$$ j ≥ 6 . However, the number of required signatures grows exponentially as $$4^j$$ 4 j . In this work, we show that not all leaky signatures carry information about the secret subkey. We introduce the notion of informative signature relations. This notion allows us to define a preprocessing step, called filter-and-shift that leads to ILWE instances that require a smaller sample amount. Unlike the standard ILWE transformation, filter-and-shift exploits the smallness of secret keys, and therefore might be of independent cryptanalytic interest. In comparison to Liu et al., for $$j=6$$ j = 6 we require only a quarter of the signatures and reduce the exponential growth to $$2^j$$ 2 j . In addition, we show that the secret subkey can be recovered even with a leak bit corrupted by a large amount of noise, in theory up to the maximum of $$50\%$$ 50 % . Experimentally, we still recover the secret with $$43\%$$ 43 % noise, where we need 170 times as many signatures as in the noise-free setting. The attack applies more generally to all Fiat-Shamir-type lattice-based signatures. For a signature scheme based on module LWE over an $$\ell $$ ℓ -dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a $$\frac{1}{\ell }$$ 1 ℓ -fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with $$\ell = 1$$ ℓ = 1 , the attack recovers the whole key.

Abstract We study the hardness of the Syndrome Decoding problem, the base of most code-based cryptographic schemes, such as Classic McEliece, in the presence of side-channel information. We use ChipWhisperer equipment to perform a template attack on Classic McEliece running on an ARM Cortex-M4, and accurately classify the Hamming weights of consecutive 32-bit blocks of the secret error vector $$\textbf{e}\in {{\mathbb {F}}}_2^n$$ e ∈ F 2 n . With these weights at hand, we optimize Information Set Decoding algorithms. Technically, we demonstrate how to speed up information set decoding via a dimension reduction, additional parity-check equations, and an improved information set search, all derived from the Hamming-weight information. Consequently, using our template attack, we can practically recover an error vector $$\textbf{e}\in {{\mathbb {F}}}_2^n$$ e ∈ F 2 n in dimension $$n=2197$$ n = 2197 in a matter of seconds. Without side-channel information, such an instance has a complexity of around 88 bit. We also estimate how our template attack affects the security of the proposed McEliece parameter sets. Roughly speaking, even an error-prone leak of our Hamming weight information leads for $$n=3488$$ n = 3488 to a security drop of 89 bits.

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$k$on input$x$the Legendre symbol$L_{k}(x)=(\frac{x+k}{p})$in some finite field$\mathbb{F}_{p}$. As standard notion, PRF security is analysed by giving an attacker oracle access to$L_{k}(\cdot)$. Khovratovich's collision-based algorithm recovers$k$using$L_{k}(\cdot)$in time$\sqrt{p}$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$m$Legendre keys$k_{1}, \ldots, k_{m}$in time$\sqrt{mp}$, i.e. with amortized cost$\sqrt{p/m}$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$p$only - and not on a key$k$. Namely, an attacker may compute e.g. in precomputation time$p^{\frac{2}{3}}$a hint of size$p^{\frac{1}{3}}$. On receiving access to$L_{k}(\cdot)$in an online phase, the attacker then uses the hint to recover the desired key$k$in time only$p^{\frac{1}{3}}$. 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$m$keys one may spend time$mp^{\frac{2}{3}}$in the precomputation phase for constructing a hint of size$m^{2}p^{\frac{1}{3}}$. In an online phase, one then finds all$m$keys in total time only$p^{\frac{1}{3}}$. 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.

Modern hardware systems are composed of a variety of third-party Intellectual Property (IP) cores to implement their overall functionality. Since hardware design is a globalized process involving various (untrusted) stakeholders, a secure management of the valuable IP between authors and users is inevitable to protect them from unauthorized access and modification. To this end, the widely adopted IEEE standard 1735-2014 was created to ensure confidentiality and integrity. In this paper, we outline structural weaknesses in IEEE 1735 that cannot be fixed with cryptographic solutions (given the contemporary hardware design process) and thus render the standard inherently insecure. We practically demonstrate the weaknesses by recovering the private keys of IEEE 1735 implementations from major Electronic Design Automation (EDA) tool vendors, namely Intel, Xilinx, Cadence, Siemens, Microsemi, and Lattice, while results on a seventh case study are withheld. As a consequence, we can decrypt, modify, and re-encrypt all allegedly protected IP cores designed for the respective tools, thus leading to an industry-wide break. As part of this analysis, we are the first to publicly disclose three RSA-based white-box schemes that are used in real-world products and present cryptanalytical attacks for all of them, finally resulting in key recovery.

The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable. We introduce a new technique that enables the first security proof for RSA-PKCS#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS#1 v1.5 signatures can be instantiated in practice such that our security proofs apply. In order to draw a more complete picture of the precise security of RSA PKCS#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.