Traffic correlation attacks have illustrated challenges with protecting communication meta-data, yet short flows as in messaging applications like Signal have been protected by practical Mixnets such as Loopix from prior traffic correlation attacks. This paper introduces a novel traffic correlation attack against short-flow applications like Signal that are tunneled through practical Mixnets like Loopix. We propose the MixFlow model, an approach for analyzing the unlinkability of communications through Mix networks. As a prominent example, we do our analysis on Loopix. The MixFlow is a contrastive model that looks for semantic relationships between entry and exit flows, even if the traffic is tunneled through Mixnets that protect meta-data like Loopix via Poisson mixing delay and cover traffic. We use the MixFlow model to evaluate the resistance of Loopix Mix networks against an adversary that observes only the inflow and outflow of Mixnet and tries to correlate communication flows. Our experiments indicate that the MixFlow model is exceptionally proficient in connecting end-to-end flows, even when the Poison delay and cover traffic are increased. These findings challenge the conventional notion that adding Poisson mixing delay and cover traffic can obscure the metadata patterns and relationships between communicating parties. Despite the implementation of Poisson mixing countermeasures in Mixnets, MixFlow is still capable of effectively linking end-to-end flows, enabling the extraction of meta-information and correlation between inflows and outflows. Our findings have important implications for existing Poisson-mixing techniques and open up new opportunities for analyzing the anonymity and unlinkability of communication protocols.

In [15], Leonardi and Ruiz-Lopez propose an additively homomorphic public key encryption scheme whose security is expected to depend on the hardness of the $\textit{learning homomorphism with noise problem}$ (LHN). Choosing parameters for their primitive requires choosing three groups $G$, $H$, and $K$. In their paper, Leonardi and Ruiz-Lopez claim that, when $G$, $H$, and $K$ are abelian, then their public-key cryptosystem is not quantum secure. In this paper, we study security for finite abelian groups $G$, $H$, and $K$ in the classical case. Moreover, we study quantum attacks on instantiations with solvable groups.

In recent years, the automatic search has been widely used to search differential characteristics and linear approximations with high probability/correlation. Among these methods, the automatic search with the Boolean Satisfiability Problem (SAT, in short) gradually becomes a powerful cryptanalysis tool in symmetric ciphers. A key problem in the automatic search method is how to fully characterize a set $S \subseteq \{0,1\}^n$ with as few Conjunctive Normal Form (CNF, in short) clauses as possible, which is called a full CNF characterization (FCC, in short) problem. In this work, we establish a complete theory to solve a best solution of a FCC problem. Specifically, we start from plain sets, which can be characterized by exactly one clause. By exploring mergeable sets, we find a sufficient and necessary condition for characterizing a plain set. Based on the properties of plain sets, we further provide an algorithm for solving a FCC problem with $S$, which can generate all the minimal plain closures of $S$ and produce a best FCC theoretically. We also apply our algorithm to S-boxes used in block ciphers to characterize their differential distribution tables and linear approximation tables. All of our FCCs are the best-known results at present.

The signed difference is a powerful tool for analyzing the Addition, XOR, Rotation (ARX) cryptographic primitives. Currently, solving the accurate model for the signed difference propagation is infeasible. We propose an approximate MILP modeling method capturing the propagation rules of signed differences. Unlike the accurate signed difference model, the approximate model only focuses on active bits and ignores the possible bit conditions on inactive bits. To overcome the negative effect of a lower accuracy arising from ignoring bit conditions on inactive bits, we propose an additional tool for deducing all bit conditions automatically. Such a tool is based on a directed-graph capturing the whole computation process of ARX primitives by drawing links among intermediate words and operations. The digraph is also applicable in the MILP model construction process: it enables us to identify the parameters upper bounding the number of bit conditions so as to define the objective function; it is further used to connect the boomerang top and bottom signed differential paths by introducing proper constraints to avoid incompatible intersections. Benefiting from the approximate model and the directed-graph based tool, the solving time of the new MILP model is significantly reduced, enabling us to deduce signed differential paths efficiently and accurately. To show the utility of our method, we propose boomerang attacks on the keyed permutations of three ARX hash functions of BLAKE. For the first time we mount an attack on the full 7 rounds of BLAKE3, with the complexity as low as $2^{180}$. Our best attack on BLAKE2s can improve the previously best result by 0.5 rounds but with lower complexity. The attacks on BLAKE-256 cover the same 8 rounds with the previous best result but with complexity $2^{16}$ times lower. All our results are verified practically with round-reduced boomerang quartets.

RIPEMD-160 and SHA-256 are two hash functions used to generate the bitcoin address. In particular, RIPEMD-160 is an ISO/IEC standard and SHA-256 has been widely used in the world. Due to their complex designs, the progress to find (semi-free-start) collisions for the two hash functions is slow. Recently at EUROCRYPT 2023, Liu et al. presented the first collision attack on 36 steps of RIPEMD-160 and the first MILP-based method to find collision-generating signed differential characteristics. We continue this line of research and implement the MILP-based method with a SAT/SMT-based method. Furthermore, we observe that the collision attack on RIPEMD-160 can be improved to 40 steps with different message differences. We have practically found a colliding message pair for 40-step RIPEMD-160 in 16 hours with 115 threads. Moreover, we also report the first semi-free-start (SFS) colliding message pair for 39-step SHA-256, which can be found in about 3 hours with 120 threads. These results update the best (SFS) collision attacks on RIPEMD-160 and SHA-256. Especially, we have made some progress on SHA-256 since the last update on (SFS) collision attacks on it at EUROCRYPT 2013, where the first practical SFS collision attack on 38-step SHA-256 was found.

Whereas theoretical attacks on standardized crypto primitives rarely lead to actual practical attacks, the situation is different for side-channel attacks. Improvements in the performance of side-channel attacks are of utmost importance. In this paper, we propose a framework to be used in key-recovery side-channel attacks on CCA-secure post-quantum encryption schemes. The basic idea is to construct chosen ciphertext queries to a plaintext checking oracle that collects information on a set of secret variables in a single query. Then a large number of such queries is considered, each related to a different set of secret variables, and they are modeled as a low-density parity-check code (LDPC code). Secret variables are finally determined through efficient iterative decoding methods, such as belief propagation, using soft information. The utilization of LDPC codes offers efficient decoding, source compression, and error correction benefits. It has been demonstrated that this approach provides significant improvements compared to previous work by reducing the required number of queries, such as the number of traces in a power attack. The framework is demonstrated and implemented in two different cases. On one hand, we attack implementations of HQC in a timing attack, lowering the number of required traces considerably compared to attacks in previous work. On the other hand, we describe and implement a full attack on a masked implementation of Kyber using power analysis. Using the ChipWhisperer evaluation platform, our real-world attacks recover the long-term secret key of a first-order masked implementation of Kyber-768 with an average of only 12 power traces.

Recent advancements in low-cost cryptography have converged upon the use of nanoscale level structural variances as sources of entropy that is unique to each device. Consequently, such delay-based Physically Unclonable Functions or (PUFs) have gained traction for several cryptographic applications. In light of recent machine learning (ML) attacks on delay-based PUFs, the common trend among PUF designers is to either introduce non-linearity using XORs or input transformations applied on the challenges in order to harden the security of delay-based PUFs. Such approaches make machine learning modelling attacks hard by destroying the linear relationship between challenge-response pairs of a PUF. However, we propose to perceive PUFs, which are fundamentally viewed as Boolean functional mapping, as a set of delay parameters drawn from normal distribution. Using this newfound perception, we propose an alternative attack strategy in this paper. We show that instead of trying to learn the exact functional relationship between challenge-response pairs from a PUF, one can search through the search space of all PUFs to find alternative PUF delay parameter set that exhibits similar behaviour as the target PUF. The core intuition behind this strategy is that one can consider a PUF as a set of stages wherein, depending on the corresponding input challenge bit, one of the several signals within a PUF's stage win a race condition. To utilize this idea, we develop a novel Particle Swarm Optimization based framework inspired by the biomimicry of amoebic reproduction. The proposed algorithm avoids the pitfalls of textbook Genetic Algorithms and demonstrates complete break of existing delay-based PUFs which are based on arbiter chains. More specifically, we are able to model higher-rder $k$-XOR PUF variants which are resistant to all-known ML modelling techniques, including $k=13, 15$ and $20$, without the knowledge of reliability values. In addition to that, we also model PUFs that incorporate input transformation, like variants of IPUF and LP-PUF. Furthermore, we take forward this idea across different search spaces in order to learn a higher order PUF using a lower order (and simpler) PUF architecture. This allows us to explore a novel class of attacks, including modelling a $k$-XOR PUF using a $(k-1)$-XOR PUF as well as bypassing input transformations based PUF designs.

With the recent development of quantum computers, various studies on quantum artificial intelligence technology are being conducted. Quantum artificial intelligence can improve performance in terms of accuracy and memory usage compared to deep learning on classical computers. In this work, we proposed an attack technique that recovers keys by learning patterns in cryptographic algorithms by applying quantum artificial intelligence to cryptanalysis. Cryptanalysis was performed in the current practically usable quantum computer environment, and this is the world's first study to the best of our knowledge. As a result, we reduced 70 epochs and reduced the parameters by 19.6%. In addition, higher average BAP (Bit Accuracy Probability) was achieved despite using fewer epochs and parameters. For the same epoch, the method using a quantum neural network achieved a 2.8% higher BAP with fewer parameters. In our approach, quantum advantages in accuracy and memory usage were obtained with quantum neural networks. It is expected that the cryptanalysis proposed in this work will be better utilized if a larger-scale stable quantum computer is developed in the future.

The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity $2^{64.5}$. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.

Deep learning-based profiling side-channel analysis is widely adopted in academia and industry thanks to the ability to reveal secrets protected with countermeasures. To leverage its capability, the adversary needs to have access to a clone of an attack device to obtain the profiling measurements. Moreover, the adversary needs to know secret information to label these measurements. Non-profiling attacks avoid those constraints by not relying on secret information to label data but rather by trying all key guesses and taking the most successful one. Deep learning approaches also form the basis of several non-profiling attacks. Unfortunately, such approaches suffer from high computational complexity and low generality when applied in practice. This paper proposes a novel non-profiling deep learning-based side-channel analysis technique. Our approach relies on the fact that there is (commonly) a bijective relationship between known information, such as plaintext and ciphertext, and secret information. We use this fact to label the leakage measurement with the known information and then mount attacks. Our results show that we reach at least $3\times$ better attack performance with negligible computational effort than existing non-profiling methods. Moreover, our non-profiling approach rivals the performance of state-of-the-art deep learning-based profiling attacks.

Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m \geq n$, a collision of $f$ is a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be $\Theta(2^{m/3})$, and matching algorithms are known for any value of $m$. The situation becomes different when one is looking for multiple collision pairs. Here, for $2^k$ collisions, a query lower bound of $\Theta(2^{(2k+m)/3})$ was shown by Liu and Zhandry (EUROCRYPT 2019). A matching algorithm is known, but only for relatively small values of $m$, when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met. Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk. As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of $2^{0.2563d + o(d)}$ instead of the previous $2^{0.2570d + o(d)}$.

The Demirci-Sel{\c{c}}uk meet-in-the-middle (DS-MITM) attack is a sophisticated variant of differential attacks. Due to its sophistication, it is hard to efficiently find the best DS-MITM attacks on most ciphers \emph{except} for AES. Moreover, the current automatic tools only capture the most basic version of DS-MITM attacks, and the critical techniques developed for enhancing the attacks (e.g., differential enumeration and key-dependent-sieve) still rely on manual work. In this paper, we develop a full-fledged automatic framework integrating all known techniques (differential enumeration, key-dependent-sieve, and key bridging, etc) for the DS-MITM attack that can produce key-recovery attacks directly rather than only search for distinguishers. Moreover, we develop a new technique that is able to exploit partial key additions to generate more linear relations beneficial to the attacks. We apply the framework to the SKINNY family of block ciphers and significantly improved results are obtained. In particular, all known DS-MITM attacks on the respective versions of SKINNY are improved by at least 2 rounds, and the data, memory, or time complexities of some attacks are reduced even compared to previous best attacks penetrating less rounds.

Differential-linear (DL) cryptanalysis has undergone remarkable advancements since it was first proposed by Langford and Hellman \cite{langford1994differential} in 1994. At CRYPTO 2022, Niu et al. studied the (rotational) DL cryptanalysis of $n$-bit modulo additions with 2 inputs, i.e., $\boxplus_2$, and presented a technique for evaluating the (rotational) DL correlation of ARX ciphers. However, the problem of how to automatically search for good DL trails on ARX with solvers was left open, which is the focus of this work. In this paper, we solve this open problem through some techniques to reduce complexity and a transformation technique from matrix multiplication chain to Mixed Integer Quadratically-Constrained Programs (MIQCP). First, the computational complexity of the DL correlation of $\boxplus_2$ is reduced to approximately one-eighth of the state of art, which can be computed by a $2\times2$ matrix multiplication chain of the same length as before. Some methods to further reduce complexity in special cases have been studied. Additionally, we present how to compute the extended (rotational) DL correlations of $\boxplus_k$ for $k\ge 2$, where two output linear masks of the cipher pairs can be different. Second, to ensure that the existing solver Gurobi\footnote{The solver used in this paper is Gurobi, and some ready-made functions in Gurobi are also used, such as LOG\_2 and ABS. The source code is available at \url{https://}. } can compute DL correlations of $\boxplus_2$, we propose a method to transform an arbitrary matrix multiplication chain into a MIQCP, which forms the foundation of our automatic search of DL trails in ARX ciphers. Third, in ARX ciphers, we use a single DL trail under some explicit conditions to give a good estimate of the correlation, which avoids the exhaustion of intermediate differences. We then derive an automatic method for evaluating the DL correlations of ARX, which we apply to Alzette and some versions of SPECK. Experimentally verified results confirm the validity of our method, with the predicted correlations being close to the experimental ones. To the best of our knowledge, this method finds the best DL distinguishers for these ARX primitives currently. Furthermore, we presented the lowest time-complexity attacks against 12-14 rounds of SPECK32 to date.

This work is intended for researchers in the field of side-channel attacks, countermeasure analysis, and probing security. It reports on a formalization of simulatability in terms of linear algebra properties, which we think will provide a useful tool in the practitioner toolbox. The formalization allowed us to revisit some existing definitions (such as probe isolating non-interference) in a simpler way that corresponds to the propagation of erase morphisms. From a theoretical perspective, we shed light into probabilistic definitions of simulatability and matrix-based spectral approaches. This could mean, in practice, that potentially better tools can be built. Readers will find a different, and perhaps less contrived, definition of simulatability, which could enable new forms of reasoning. This work does not cover any practical implementation of the proposed tools, which is left for future work.

We propose an efficient technique called coefficient grouping to evaluate the algebraic degree of the FHE-friendly cipher Chaghri, which has been accepted for ACM CCS 2022. It is found that the algebraic degree increases linearly rather than exponentially. As a consequence, we can construct a 13-round distinguisher with time and data complexity of $2^{63}$ and mount a 13.5-round key-recovery attack. In particular, a higher-order differential attack on 8 rounds of Chaghri can be achieved with time and data complexity of $2^{38}$. Hence, it indicates that the full 8 rounds are far from being secure. Furthermore, we also demonstrate the application of our coefficient grouping technique to the design of secure cryptographic components. As a result, a countermeasure is found for Chaghri and it has little overhead compared with the original design. Since more and more symmetric primitives defined over a large finite field are emerging, we believe our new technique can have more applications in the future research.

Encrypting too much data using the same key is a bad practice from a security perspective. Hence, it is customary to perform re-keying after a given amount of data is transmitted. While in many cases, the re-keying is done using a fresh execution of some key exchange protocol (e.g., in IKE or TLS), there are scenarios where internal re-keying, i.e., without exchange of information, is performed, mostly due to performance reasons. Originally suggested by Abdalla and Bellare, there are several proposals on how to perform this internal re-keying mechanism. For example, Liliya et al. offered the CryptoPro Key Meshing (CPKM) to be used together with GOST 28147-89 (known as the GOST block cipher). Later, ISO and the IETF adopted the Advanced CryptoPro Key Meshing (ACKPM) in ISO 10116 and RFC 8645, respectively. In this paper, we study the security of ACPKM and CPKM. We show that the internal re-keying suffers from an entropy loss in successive repetitions of the re- keying mechanism. We show some attacks based on this issue. The most prominent one has time and data complexities of $O(2^{\kappa/2} )$ and success rate of $O(2^{−\kappa/4} )$ for a $\kappa$-bit key. Furthermore, we show that a malicious block cipher designer or a faulty implementation can exploit the ACPKM (or the original CPKM) mechanism to significantly hinder the security of a protocol employing ACPKM (or CPKM). Namely, we show that in such cases, the entropy of the re-keyed key can be greatly reduced.

The finite field isomorphism (FFI) problem was introduced in PKC'18, as an alternative to average-case lattice problems (like LWE, SIS, or NTRU). As an application, the same paper used the FFI problem to construct a fully homomorphic encryption scheme. In this work, we prove that the decision variant of the FFI problem can be solved in polynomial time for any field characteristics $q= \Omega(\beta n^2)$, where $q,\beta,n$ parametrize the FFI problem. Then we use our result from the FFI distinguisher to propose polynomial-time attacks on the semantic security of the fully homomorphic encryption scheme. Furthermore, for completeness, we also study the search variant of the FFI problem and show how to state it as a $q$-ary lattice problem, which was previously unknown. As a result, we can solve the search problem for some previously intractable parameters using a simple lattice reduction approach.

The Mixed Integer Linear Programming (MILP) is a common method of searching for impossible differentials (IDs). However, the optimality of the distinguisher should be confirmed by an exhaustive search of all input and output differences, which is clearly computationally infeasible due to the huge search space. In this paper, we propose a new technique that uses two-dimensional binary variables to model the input and output differences and characterize contradictions with constraints. In our model, the existence of IDs can be directly obtained by checking whether the model has a solution. In addition, our tool can also detect any contradictions between input and output differences by changing the position of the contradictions. Our method is confirmed by applying it to several block ciphers, and our results show that we can find 6-, 13-, and 12-round IDs for Midori-64, CRAFT, and SKINNY-64 within a few seconds, respectively. Moreover, by carefully analyzing the key schedule of Midori-64, we propose an equivalent key transform technique and construct a complete MILP model for an 11-round impossible differential attack (IDA) on Midori-64 to search for the minimum number of keys to be guessed. Based on our automatic technique, we present a new 11-round IDA on Midori-64, where 23 nibbles of keys need to be guessed, which reduces the time complexity compared to previous work. The time and data complexity of our attack are $2^{116.59}$ and $2^{60}$, respectively. To the best of our knowledge, this is the best IDA on Midori-64 at present.

Falcon is one of the three post-quantum signature schemes selected for standardization by NIST. Due to its low bandwidth and high efficiency, Falcon is seen as an attractive option for quantum-safe embedded systems. In this work, we study Falcon's side-channel resistance by analysing its Gaussian samplers. Our results are mainly twofold. The first result is an improved key recovery exploiting the leakage within the base sampler investigated by Guerreau et al. (CHES 2022). Instead of resorting to the fourth moment as in former parallelepiped-learning attacks, we work with the second order statistics covariance and use its spectral decomposition to recover the secret information. Our approach substantially reduces the requirement for measurements and computation resources: $220\,000$ traces is sufficient to recover the secret key of Falcon 512 within half an hour with a probability of $\approx 25\%$. As a comparison, even with $10^6$ traces, the former attack still needs about 1000 hours CPU time of lattice reduction for a full key recovery. In addition, our approach is robust to inaccurate leakage classification, which is another advantage over parallelepiped-learning attacks. Our second result is a practical power analysis targeting the integer Gaussian sampler of Falcon. The analysis relies on the leakage of random sign flip within the integer Gaussian sampling. This leakage was exposed in 2018 by Kim and Hong, but it is not considered in Falcon's implementation and unexploited for side channel analysis until now. We identify the leakage within the reference implementation of Falcon on an ARM Cortex-M4 STM32F407IGT6 microprocessor. We also show that this single bit of leakage is in effect enough for practical key recovery: with $170\,000$ traces one can fully recover the key of Falcon-512 within half an hour. Furthermore, combining the sign leakage and the aforementioned leakage, one can recover the key with only $45\,000$ signature measurements in a short time. As a by-product, we also extend our power analysis to Mitaka which is a recent variant of Falcon. The same leakages exist within the integer Gaussian samplers of Mitaka, and they can also be used to mount key recovery attacks. Nevertheless, the key recovery in Mitaka requires much more traces than it does in Falcon, due to their different lattice Gaussian samplers.

In this paper, we propose a rectangle-like method called \textit{rotational-XOR differential rectangle} attack to search for better distinguishers. It is a combination of the rotational-XOR cryptanalysis and differential cryptanalysis in the rectangle-based way. In particular, we put a rotational-XOR characteristic before a differential characteristic to construct a rectangle structure. By choosing some appropriate rotational-XOR and differential characteristics as well as considering multiple differentials, some longer distinguishers that have the probability greater than $2^{-2n}$ can be constructed effectively where $n$ is the block size of a block cipher. We apply this new method to some versions of \textsc{Simon} and \textsc{Simeck} block ciphers. As a result, we obtain rotational-XOR differential rectangle distinguishers up to 16, 16, 17, 16 and 21 rounds for \textsc{Simon}32/64, \textsc{Simon}48/72, \textsc{Simon}48/96, \textsc{Simeck}32 and \textsc{Simeck}48, respectively. Our distinguishers for \textsc{Simon}32/64 is longer than the best differential and rotational-XOR distinguishers. As for \textsc{Simon}48/96, the distinguisher is longer than the rotational-XOR distinguisher and as long as the best differential distinguisher. Also, our distinguisher for \textsc{Simeck}32 is longer than the best differential distinguisher (14 rounds) and has the full weak key space (i.e., $2^{64}$) whereas the 16-round rotational-XOR distinguisher has a weak key class of $2^{36}$. In addition, our distinguisher for \textsc{Simeck}48 has a better weak key class ($2^{72}$ weak keys) than the 21-round rotational-XOR distinguisher ($2^{60}$ weak keys). To the best of our knowledge, this is the first time to consider the combinational cryptanalysis based on rotational-XOR and differential cryptanalysis using the rectangle structure.

In Addition-Rotation-Xor (ARX) ciphers, the large domain size obstructs the application of the boomerang connectivity table. In this paper, we explore the problem of computing this table for a modular addition and the automatic search of boomerang characteristics for ARX ciphers. We provide dynamic programming algorithms to efficiently compute this table and its variants. These algorithms are the most efficient up to now. For the boomerang connectivity table, the execution time is $4^2(n − 1)$ simple operations while the previous algorithm costs $8^2(n − 1)$ simple operations, which generates a smaller model in the searching phase. After rewriting these algorithms with boolean expressions, we construct the corresponding Boolean Satisfiability Problem models. Two automatic search frameworks are also proposed based on these models. This is the first time bringing the SAT-aided automatic search techniques into finding boomerang attacks on ARX ciphers. Finally, under these frameworks, we find out the first verifiable 10-round boomerang trail for SPECK32/64 with probability $2^{-29.15}$ and a 12-round trail for SPECK48/72 with probability $2^{-44.15}$. These are the best distinguishers for them so far. We also perceive that the previous boomerang attacks on LEA are constructed with an incorrect computation of the boomerang connection probability. The result is then fixed by our frameworks.

In this paper, we present a fully automated tool for differential-linear attacks using Mixed-Integer Linear Programming (MILP) and Mixed-Integer Quadratic Constraint Programming (MIQCP) techniques, which is, to the best of our knowledge, the very first attempt to fully automate such attacks. We use this tool to improve the correlations of the best 9 and 10-round differential-linear distinguishers on Speck32/64, and reach 11 rounds for the first time. Furthermore, we improve the latest 14-round key-recovery attack against Speck32/64, using differential-linear distinguishers obtained with our MILP/MIQCP tool. The techniques we present are generic and can be applied to other ARX ciphers as well.

In this paper, we show that it is inaccurate to apply the hypothesis of independent round keys to search for differential characteristics of a block cipher with a simple key schedule. Therefore, the derived differential characteristics may be invalid. We develop a SAT-based algorithm to verify the validity of differential characteristics. Furthermore, we take the key schedule into account and thus put forward an algorithm to directly find the valid differential characteristics. All experiments are performed on Midori64 and we find some interesting results.

In this paper we present several analyses on ChaCha, a software stream cipher. First, we consider a divide-and-conquer approach on the secret key bits by partitioning them. The partitions are based on multiple input-output differentials to obtain a significantly improved attack on 6-round ChaCha256 with a complexity of 2^{99.48}. It is 2^{40} times faster than the currently best known attack. Note that, this is the first time an attack could be mounted on reduced round ChaCha with a complexity significantly less than 2^{k}{2}, where the secret key is of $k$ bits. Further, we note that all the attack complexities related to ChaCha are theoretically estimated in general and there are several questions in this regard as pointed out by Dey et al. in Eurocrypt 2022. In this regard, we propose a toy version of ChaCha, with a 32-bit secret key, on which the attacks can be implemented completely to verify whether the theoretical estimates are justified. This idea is implemented for our proposed attack on 6 rounds. Finally, we show that it is possible to estimate the success probabilities of these kinds of PNB-based differential attacks more accurately. Our methodology explains how different cryptanalytic results can be evaluated with better accuracy rather than claiming (Aumasson et al., 2008) that the success probability is significantly better than 50%.

Mitaka is a lattice-based signature proposed at Eurocrypt 2022. A key advertised feature of Mitaka is that it can be masked at high orders efficiently, making it attractive in scenarios where side-channel attacks are a concern. Mitaka comes with a claimed security proof in the t-probing model. We uncover a flaw in the security proof of Mitaka, and subsequently show that it is not secure in the t-probing model. For any number of shares d ≥ 4, probing t < d variables per execution allows an attacker to recover the private key efficiently with approximately 221 executions. Our analysis shows that even a constant number of probes suffices (t = 3), as long as the attacker has access to a number of executions that is linear in d/t.

In this paper, we examine the algebraic XSL attack on the Advanced Encryption Standard (AES). We begin with a brief introduction and we present an overview of AES, then, in Section 3, we present the algebraic attack on ciphers like AES, following with the XL and XSL algorithms in Section 4 and Section 5. Then, we present the XSL first and second attacks, also their aplicability on BES. We see how and if the algorithm has been improved since it firstly appeared. We conclude with Section 10.

The Mixed Integer Linear Programming (MILP) technique has been widely applied in the realm of symmetric-key cryptanalysis. In this paper, we propose a new bitwise breakdown MILP modeling strategy for describing the linear propagation rules of modular addition-based operations. We apply such new techniques to cryptanalysis of the SNOW stream cipher family and find new linear masks: we use the MILP model to find many linear mask candidates among which the best ones are identified with particular algebraic bias evaluation techniques. For SNOW 3G, the correlation of the linear mask we found is the highest on record: such results are highly likely to be optimal according to our analysis. For SNOW 2.0, we find new masks matching the correlation record and many new sub-optimal masks applicable to improving correlation attacks. For SNOW-V/Vi, by investigating both bitwise and truncated linear masks, we find all linear masks having the highest correlation, and prove the optimum of the corresponding truncated patterns under the ``fewest active S-box preferred'' strategy. By using the newly found linear masks, we give correlation attacks on the SNOW family with improved complexities. We emphasize that the newly proposed uniform MILP-aided framework can be potentially applied to analyze LFSR-FSM structures composed of modular addition and S-box as non-linear components.

Modern day smart phones are used for performing several sensitive operations, including online payments. Hence, the underlying cryptographic libraries are expected to adhere to proper security measures to ensure that there are no exploitable leakages. In particular, the implementations should be constant time to prevent subsequent timing based side channel analysis which can leak secret keys. Unfortunately, we unearth in this paper a glaring timing variation present in the Bouncy-Castle implementation of RSA like ciphers which is based on the BigInteger Java library to support large number theoretic computations. We follow up the investigation with a step-by-step procedure to exploit the timing variations to retrieve the complete secret of windowed RSA-2048 implementation. The entire analysis is possible with a single set of timing observation, implying that the timing observation can be done at the onset, followed by some post processing which does not need access to the phone. We have validated our analysis on Android Marshmallow 6.0, Nougat 7.0 and Oreo 8.0 versions. Interestingly, we note that for newer phones the timing measurement is more accurate leading to faster key retrievals.

Proposed by Thang and Binh (NICS, 2015 ), DBTRU is a variant of NTRU, where the integer polynomial ring is replaced by two binary truncated polynomial rings GF(2)[x]/(x^n + 1). DBTRU has significant advantages over NTRU in terms of security and performance. NTRU is a probabilistic public key cryptosystem having security related to some hard problems in lattices. In this paper we will present a polynomial-time linear algebra attack on the DBTRU cryptosystem which can break DBTRU for all recommended parameter choices and the plaintext can be obtained in less than one second using a single PC and this specific attack.

The lightweight block ciphers ULC and LICID are introduced by Sliman et al. (2021) and Omrani et al. (2019) respectively. These ciphers are based on substitution permutation network structure. ULC is designed using the ULM method to increase efficiency, memory usage, and security. On the other hand, LICID is specifically designed for image data. In the ULC paper, the authors have given a full-round differential characteristic with a probability of $2^{-80}$. In the LICID paper, the authors have presented an 8-round differential characteristic with a probability of $2^{-112.66}$. In this paper, we present the 15-round ULC and the 14-round LICID differential characteristics of probabilities $2^{-45}$ and $2^{-40}$ respectively using the MILP model.

We present an algebraic attack on a McEliece-like scheme based on BCH codes (BCH-McEliece), where the Goppa code is replaced by a suitably permuted BCH code. Our attack continues the line of work devising attacks against McEliece-like schemes with Goppa-like codes, with the goal of getting a better understanding of why Goppa codes are so intractable. Our starting point is the work of Faugère, Perret and Portzamparc (Asiacrypt 2014). We take their algebraic model and adapt and improve their attack algorithm so that it can handle BCH-McEliece. We implement the attack and exhibit a parameter range where our attack is practical while generic attacks suggest cryptographic security.

Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three strategies for developing SAT models for 8-bit S-boxes that are geared toward differential probabilities and linear correlations. While these approaches cannot guarantee a minimum model size, the time needed to obtain models is drastically reduced. The newly proposed SAT model for large S-boxes enables us to establish that the upper bound on the differential probability for 14 rounds of SKINNY-128 is 2^{-131}, thereby completing the unsuccessful work of Abdelkhalek et al. We also analyse the seven AES-based constructions C1 - C7 designed by Jean and Nikolic and compute the minimum number of active S-boxes necessary to cause an internal collision using the SAT method. For two constructions C3 and C5, the current lower bound on the number of active S-boxes is increased, resulting in a more precise security analysis for these two structures.

Because of the rapid growth of Internet of Things (IoT), embedded systems have become an interesting target for experienced attackers. ESP32~\cite{tech-ref-man} is a low-cost and low-power system on chip (SoC) series created by Espressif Systems. The firmware extraction of such embedded systems is a real threat to the manufacturer as it breaks its intellectual property and raises the risk of creating equivalent systems with less effort and resources. In 2019, LimitedResults~\cite{LimitedResultsPown} published power glitch attacks which resulted in dumping secure boot and flash encryption keys stored in the eFuses of ESP32. Therefore, Espressif patched this vulnerability and then advised its customers to use ESP32-V3, which is an updated SoC revision. This new version is hardened against fault injection attacks in hardware and software as announced by Espressif~\cite{ESPpatch}. In this paper, we present for the first time a deep hardware security evaluation for ESP32-V3. The main goal of this evaluation is to extract the firmware encryption key stored in the eFuses. This evaluation includes Fault Injection (FI) and Side-Channel (SC) attacks. First, we use Electromagnetic FI (EMFI) in order to show that ESP32-V3 doesn't resist EMFI. However, by experimental results, we show that this version contains a revised bootloader compared to ESP32-V1, which hardens dumping the eFuse keys by FI. Second, we perform a full SC analysis on the AES accelerator of ESP32-V3. We show that an attacker with a physical access to the device can extract all the keys of the hardware AES-256 after collecting 60K power measurements during the execution of the AES block. Third, we present another SC analysis for the firmware decryption mechanism, by targeting the decryption operation during the power up. Using this knowledge, we demonstrate that the full 256-bit AES firmware encryption key, which is stored in the eFuses, can be recovered by SC analysis using 300K power measurements. Finally, we apply practically the firmware encryption attack on Jade hardware wallet \cite{jade}.

Fully Homomorphic Encryption (FHE) promises to secure our data on the untrusted cloud, while allowing arbitrary computations. Recent research has shown two side channel attacks on the client side running a popular HE library. However, no side channel attacks have yet been reported on the server side in existing literature. The current paper shows that it is possible for adversaries to inject perturbations in the ciphertexts stored in the cloud to result in decryption errors. Most importantly, we highlight that when the client reports of such aberrations to the cloud service provider the complete secret key can be extracted in few attempts. Technically, this implies a break of the IND-CVA (Indistinguishability against Ciphertext Verification Attacks) security of the FHE schemes. The core idea of the attack is to extract the underlying error values for each homomorphically computed ciphertext and thereby construct an exact system of equations. As the security of the underlying Learning with Errors (LWE) collapse with the leakage of the errors, the adversary is capable of ascertaining the secret keys. We demonstrate this attack on two well-known FHE libraries, namely FHEW and TFHE. The objective of the server is to perform the attack in a stealthy manner, without raising any suspicion from the innocent client. Therefore in a practical scenario, the successful key retrieval from a client would require the server to perform the attack with as few queries as possible. Thus we craftily use timing information during homomorphic gate computations to optimise our attack and significantly reduce the required number of queries per ciphertext. More precisely, we need 8 and 23 queries to the client for each error recovery for FHEW and TFHE, respectively. We mount a full-key recovery attack 1 on TFHE (without and with bootstrapping) with key size of 630 bits and successfully faulted 739 and 930 ciphertexts to recover correct errors. This required a total of 19838 and 29200 client queries respectively. In case of FHEW with key size 500, we successfully faulted 766 ciphertexts to recover correct errors, which required 7565 client queries. The results serve as a stark reminder that FHE schemes need to be secured at the application level apart from being secure at the primitive level so that the security of participants against realistic attacks can be ensured.

This paper aims to provide a security analysis comparison between three popular instant messaging apps: Signal, WhatsApp and Telegram. The analysis will focus on the encryption protocols used by each app and the security features they offer. The paper will evaluate the strengths and weaknesses of each app, and provide a summary of their overall security posture. Additionally, this paper will discuss other considerations such as user base, data collection and usage policies, and other features which may impact the security of the apps. The results of this analysis will provide insights for individuals and organizations looking to choose a secure instant messaging app for their communication needs. In this paper we reviewed the main encryption standards and we compared the features, traffic analysis, protocols, performance and recent security breaches for WhatsApp, Signal and Telegram. The paper includes packet sniffing using Wireshark and Fiddler.

Over the recent years, the cryptanalysis community leveraged the potential of research on Deep Learning to enhance attacks. In particular, several studies have recently highlighted the benefits of Deep Learning based Side-Channel Attacks (DLSCA) to target real-world cryptographic implementations. While this new research area on applied cryptography provides impressive result to recover a secret key even when countermeasures are implemented (e.g. desynchronization, masking schemes), the lack of theoretical results make the construction of appropriate and powerful models a notoriously hard problem. This can be problematic during an evaluation process where a security bound is required. In this work, we propose the first solution that bridges DL and SCA in order to ease the use of DL techniques in an evaluation process. Based on theoretical results, we develop the first Machine Learning generative model, called Conditional Variational AutoEncoder based on Stochastic Attacks (cVAE-SA), designed from the well-known Stochastic Attacks, that have been introduced by Schindler et al. in $2005$. This model reduces the black-box property of DL and eases the architecture design for every real-world crypto-system as we define theoretical complexity bounds which only depend on the dimension of the (reduced) trace and the targeting variable over $\mathbb{F}_{2}^{n}$. We validate our theoretical proposition through simulations and public datasets on a wide range of use cases, including multi-task learning, curse of dimensionality and masking scheme.

SPHINCS+ is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context of SPHINCS+ and analyzes the current algorithms that aim to prevent fault-based forgeries. First, the paper adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures. Considering the adaptation, the paper then presents a thorough analysis of the attack. In particular, the analysis shows that, with high probability, the security guarantees of SPHINCS+ significantly drop when a single random bit flip occurs anywhere in the signing procedure and that the resulting faulty signature cannot be detected with the verification procedure. The paper shows both in theory and experimentally that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults, and that such countermeasures are circumvented with a tolerable number of queries in an active attack. Based on these results, the paper recommends real-world deployments of SPHINCS+ to implement redundancy checks.

Troika is a sponge-based hash function designed by Kölbl, Tischhauser, Bogdanov and Derbez in 2019. Its specificity is that it is defined over $\mathbb{F}_3$ in order to be used inside IOTA’s distributed ledger but could also serve in all settings requiring the generation of ternary randomness. To be used in practice, Troika needs to be proven secure against state-of-the-art cryptanalysis. However, there are today almost no analysis tools for ternary designs. In this article we take a step in this direction by analyzing the propagation of differential trails of Troika and by providing bounds on the weight of its trails. For this, we adapt a well-known framework for trail search designed for KECCAK and provide new advanced techniques to handle the search on $\mathbb{F}_3$. Our work demonstrates that providing analysis tools for non-binary designs is a highly non-trivial research direction that needs to be enhanced in order to better understand the real security offered by such non-conventional primitives.

The applicability of lattice reduction to a wide variety of cryptographic situations makes it an important part of the cryptanalyst's toolbox. Despite this, the construction of lattices and use of lattice reduction algorithms for cryptanalysis continue to be somewhat difficult to understand for beginners. This tutorial aims to be a gentle but detailed introduction to lattice-based cryptanalysis targeted towards the novice cryptanalyst with little to no background in lattices. We explain some popular attacks through a conceptual model that simplifies the various components of a lattice attack.

In this work, we evaluate the security of Merkle-Damgård (MD) hash functions and their combiners (XOR and concatenation combiners) in quantum settings. Two main quantum scenarios are considered, including the scenario where a substantial amount of cheap quantum random access memory (qRAM) is available and where qRAM is limited and expensive to access. We present generic quantum attacks on the MD hash functions and hash combiners, and carefully analyze the complexities under both quantum scenarios. The considered securities are fundamental requirements for hash functions, including the resistance against collision and (second-)preimage. The results are consistent with the conclusions in the classical setting, that is, the considered resistances of the MD hash functions and their combiners are far less than ideal, despite the significant differences in the expected security bounds between the classical and quantum settings. Particularly, the generic attacks can be improved significantly using quantum computers under both scenarios. These results serve as an indication that classical hash constructions require careful security re-evaluation before being deployed to the post-quantum cryptography schemes.

In ToSC'20, a new approach combining Mix-Integer Linear Programming (MILP) tool and Constraint Programming (CP) tool to search for boomerang distinguishers is proposed and later used for rebound attack in ASIACRYPT'21 and CRYPTO'22. In this work, we extend these techniques to mount collision attacks on SKINNY-128-256 MMO hashing mode in classical and quantum settings. The first results of 17-round (and 15-round) free-start collision attack on this variant of SKINNY hashing mode are presented. Moreover, one more round of the inbound phase is covered leading to the best existing classical free-start collision attack of 19-round on the SKINNY-128-384 MMO hashing.

We are applying Fermat’s factorization algorithm to sets of public RSA keys. Fermat’s factorization allows efficiently calculating the prime factors of a composite number if the difference between the two primes is small. Knowledge of the prime factors of an RSA public key allows efficiently calculating the private key. A flawed RSA key generation function that produces close primes can therefore be attacked with Fermat’s factorization. We discovered a small number of vulnerable devices that generate such flawed RSA keys in the wild. These affect devices from two printer vendors - Canon and Fuji Xerox. Both use an underlying cryptographic module by Rambus.

We present a quantum augmented variant of the dual lattice attack on the Learning with Errors (LWE) problem, using classical memory with quantum random access (QRACM). Applying our results to lattice parameters from the literature, we find that our algorithm outperforms previous algorithms, assuming unit cost access to a QRACM. On a technical level, we show how to obtain a quantum speedup on the search for Fast Fourier Transform (FFT) coefficients above a given threshold by leveraging the relative sparseness of the FFT and using quantum amplitude estimation. We also discuss the applicability of the Quantum Fourier Transform in this context. Furthermore, we give a more rigorous analysis of the classical and quantum expected complexity of guessing part of the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).

Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by Grover algorithm. Previous studies have reduced the number of qubits required for the quantum circuits of AES-128/-192/-256 from 984/1112/1336 to 270/334/398, which is close to the optimal value of 256/320/384. It becomes a challenging task to further optimize them. Aiming at this task, we find a method about how the quantum circuit of AES S-box can be designed with the help of automation tool LIGHTER-R. Particularly, the multiplicative inversion in F_2^8, which is the main part of S-box, is converted into the multiplicative inversion (and multiplication) in F_2^4, then the latter can be implemented by LIGHTER-R because its search space is small enough. By this method, we construct the quantum circuits of S-box for mapping |a>|0> to |a>|S(a)> and |a>|b> to |a>|b+S(a)> with 20 qubits instead of 22 in the previous studies. Besides, we introduce new techniques to reduce the number of qubits required by the S-box circuit for mapping |a> to |S(a)>from 22 in the previous studies to 16. Accordingly, we synthesize the quantum circuits of AES-128/-192/-256 with 264/328/392 qubits, which implies a new record.

This paper illustrates that masking the torsion point images does not guarantee Castryck-Decru attack does not apply. Our experiments over SIDH primes hint that any square root concerning the Weil pairing on the masked public key helps to recover Bob's private key via the Castryck-Decru attack.

Since 2016, NIST has been standardrizing Post-Quantum Cryptosystems, PQCs. Code-Based Cryptosystem, CBC, which is considered to be one of PQCs, uses the Syndrome Decoding Problem as the basis for its security. NIST's PQC standardization project is currently in its 4th round and some CBC encryption schemes remain there. In this paper, we consider the quantum security for these cryptosystems.

Physically Unclonable Functions~(PUFs) with large challenge space~(also called Strong PUFs) are promoted for usage in authentications and various other cryptographic and security applications. In order to qualify for these cryptographic applications, the Boolean functions realized by PUFs need to possess a high non-linearity~(NL). However, with a large challenge space~(usually $\geq 64$ bits), measuring NL by classical techniques like Walsh transformation is computationally infeasible. In this paper, we propose the usage of a heuristic-based measure called non-homomorphicity test which estimates the NL of Boolean functions with high accuracy in spite of not needing access to the entire challenge-response set. We also combine our analysis with a technique used in linear cryptanalysis, called Piling-up lemma, to measure the NL of popular PUF compositions. As a demonstration to justify the soundness of the metric, we perform extensive experimentation by first estimating the NL of constituent Arbiter/Bistable Ring PUFs using the non-homomorphicity test, and then applying them to quantify the same for their XOR compositions namely XOR Arbiter PUFs and XOR Bistable Ring PUF. Our findings show that the metric explains the impact of various parameter choices of these PUF compositions on the NL obtained and thus promises to be used as an important objective criterion for future efforts to evaluate PUF designs. While the framework is not representative of the machine learning robustness of PUFs, it can be a useful complementary tool to analyze the cryptanalytic strengths of PUF primitives.

In [BS22], the authors proposed a lattice based hash function that is useful for building zero-knowledge proofs with superior performance. In this short note we analysis the underlying lattice problem with the classic shortest vector problem, and show that 2 out of 15 proposed parameter sets for this hash function do not achieve the claimed security.

Wi-Fi is a wireless communication technology that has been around since the late nineties. Nowadays, it is the most adopted wireless short-range communication technology in various IoT (Internet of Things) applications and on many wireless AI (Artificial Intelligent) systems. Although Wi-Fi security has significantly improved throughout the past years, it is still having some limitations. Some vulnerabilities still exist allowing attackers to generate different types of attacks. These attacks can breach the authentication, confidentiality, and data integrity of Wi-Fi systems. At the same time, many vulnerabilities have been fixed or patched, and the attacks that were relying on those vulnerabilities would fail on modern Wi-Fi systems. Therefore, it is important for security engineers, in general, and for wireless intelligent system designers, in particular, to be aware of the existing vulnerabilities and feasible attacks on modern Wi-Fi systems and their respective countermeasures. That would help them to not have to look back and care about attacks that can no longer be generated on today’s Wi-Fi systems. In this light, we devote this paper to extensively review the attacks on Wi-Fi. We group the attacks into feasible and unfeasible. Also, for each attack, we discuss the possible countermeasures to mitigate it.

The Learning with Errors (LWE) problem is one of the most prominent problems in lattice-based cryptography. Many practical LWE-based schemes, including Fully Homomorphic encryption (FHE), use sparse ternary secret for the sake of efficiency. Several (hybrid) attacks have been proposed that benefit from such sparseness, thus researchers believe the security of the schemes with sparse ternary secrets is not well-understood yet. Recently, May [Crypto 2021] proposed an efficient meet-in-the-middle attack named Meet-LWE for LWE with ternary se- cret, which significantly improves Odlyzko’s algorithm. In this work, we generalize May’s Meet-LWE and then introduce a new hybrid attack which combines Meet-LWE with lattice dual attack. We implement our algorithm to FHE-type parameters of LWE problem and compare it with the previous hybrid dual attacks. The result shows that our attack outperforms other attacks in a large range of parameters. We note that our attack has no impact on the LWE-based schemes in the PQC Standardization held by NIST as their secrets are not sparse and/or ternary.

Fully Homomorphic Encryption (FHE) allows computations on encrypted data without the need for decryption. Therefore, in the world of cloud computing, FHE provides an essential means for users to garner different computational services from potentially untrusted servers while keeping sensitive data private. In such a context, the security and privacy guarantees of well-known FHE schemes become paramount. In a research article, we (Chaturvedi et al., ePrint 2022/1563) have shown that popular FHE schemes like TFHE and FHEW are vulnerable to CVO (Ciphertext Verification Oracle) attacks, which belong to the family of “reaction attacks” [6]. We show, for the first time, that feedback from the client (user) can be craftily used by the server to extract the error (noise) associated with each computed ciphertext. Once the errors for some m ciphertext (m > n, where n = key size) are retrieved, the original secret key can be trivially leaked using the standard Gaussian Elimination method. The results in the paper (Chaturvedi et al., ePrint 2022/1563) show that FHE schemes should be subjected to further security evaluations, specifically in the context of system-wide implementation, such that CVO-based attacks can be eliminated. Quite recently, Michael Walter published a document (ePrint 2022/1722), claiming that the timing channel we used in our work (Chaturvedi et al., ePrint 2022/1563) “are false”. In this document, we debunk this claim and explain how we use the timing channel to improve the CVO attack. We explain that the CVO-based attack technique we proposed in the paper (Chaturvedi et al., ePrint 2022/1563) is a result of careful selection of perturbation values and the first work in literature that showed reaction based attacks are possible in the context of present FHE schemes in a realistic cloud setting. We further argue that for an attacker, any additional information that can aid a particular attack shall be considered as leakage and must be dealt with due importance to stymie the attack.

The Simeck family of lightweight block ciphers was proposed by Yang et al. in 2015, which combines the design features of the NSA-designed block ciphers Simon and Speck. Linear cryptanalysis using super-rounds was proposed by Almukhlifi and Vora to increase the efficiency of implementing Matsui’s second algorithm and achieved good results on all variants of Simon. The improved linear attacks result from the observation that, after four rounds of encryption, one bit of the left half of the state of the cipher depends on only 17 key bits (19 key bits for the larger variants of the cipher). Furthermore, due to the similarity between the design of Simon and Simeck, we were able to follow the same attack model and present improved linear attacks against all variants of Simeck. In this paper, we present attacks on 19-rounds of Simeck 32/64, 28-rounds of Simeck 48/96, and 33-rounds of Simeck 64/128, often with the direct recovery of the full master key without repeating the attack over multiple rounds. We also verified the results of linear cryptanalysis on 8, 10, and 12 rounds for Simeck 32/64.

The recent work of Chaturvedi et al. (ePrint 2022/685) claims to observe leakage about secret information in a ciphertext of TFHE through a timing side-channel on the (untrusted) server. In (Chaturvedi et al., ePrint 2022/1563) this is combined with an active attack against TFHE and FHEW. The claims in (Chaturvedi et al., ePrint 2022/685) about the non-trivial leakage from a ciphertext would have far-reaching implications, since the server does not have any secret inputs. In particular, this would mean a weakening of LWE in general, since an adversary could always simulate a server on which there is side channel leakage. In this short note, we show that the claims made in the two aforementioned works with regards to the leakage through the timing side channel are false. We demonstrate that the active attack, a standard attack against IND-CPA secure LWE-based encryption, can be mounted just as efficiently without the "side channel information".

To enhance the security or the efficiency of the standard RSA cryptosystem, some variants have been proposed based on elliptic curves, Gaussian integers or Lucas sequences. A typical type of these variants which we called Type-A variants have the specified modified Euler's totient function $\psi(N)=(p^2-1)(q^2-1)$. But in 2018, based on cubic Pell equation, Murru and Saettone presented a new RSA-like cryptosystem, and it is another type of RSA variants which we called Type-B variants, since their scheme has $\psi(N)=(p^2+p+1)(q^2+q+1)$. For RSA-like cryptosystems, four key-related attacks have been widely analyzed, i.e., the small private key attack, the multiple private keys attack, the partial key exposure attack and the small prime difference attack. These attacks are well-studied on both standard RSA and Type-A variants. Recently, the small private key attack on Type-B variants has also been analyzed. In this paper, we make further cryptanalysis of Type-B variants, that is, we propose the first theoretical results of multiple private keys attack, partial key exposure attack as well as small prime difference attack on Type-B variants, and the validity of our attacks are verified by experiments. Our results show that for all three attacks, Type-B variants are less secure than standard RSA.

Shuffling is a well-known countermeasure against side-channel analysis. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel analysis more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the secret key was reported. In this paper, we present an attack that can recover the secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decapsulation algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k ∗ l chosen ciphertexts constructed using a new method based on error-correcting codes with length l, where k is the security level, we recover the long term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.

In [1], a novel cryptographic key exchange technique was proposed using the plactic monoid, based on the apparent difficulty of solving division problems in that monoid. Specifically, given elements c, b in the plactic monoid, the problem is to find q for which qb = c, given that such a q exists. In this paper, we introduce a metric on the plactic monoid and use it to give a probabilistic algorithm for solving that problem which is fast for parameter values in the range of interest.

{We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given $n$ integer outputs of a degree-$d$ integer monotonic polynomial whose coefficients and inputs are integers within known bounds and $n \gg d$, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the degree of the polynomial but polynomial in the size of the polynomial coefficients. We conduct experiments with real-world data as well as randomly chosen parameters and demonstrate the effectiveness of our algorithm over a wide range of parameters. Using only the polynomial evaluations at specific integer points, the apparent hardness of recovering the input data served as the basis of security of a recent protocol proposed by Kesarwani et al. for secure $k$-nearest neighbour computation on encrypted data that involved secure sorting. The protocol uses the outputs of randomly chosen monotonic integer polynomial to hide its inputs except to only reveal the ordering of input data. Using our integer polynomial recovery algorithm, we show that we can recover the polynomial and the inputs within a few seconds, thereby demonstrating an attack on the protocol of Kesarwani et al.

Differential cryptanalysis is a block cipher analysis technology that infers a key by using the difference characteristics. Input differences can be distinguished using a good difference characteristic, and this distinguishing task can lead to key recovery. Artificial neural networks are a good solution for distinguishing tasks. For this reason, recently, neural distinguishers have been actively studied. We propose a distinguisher based on a quantum-classical hybrid neural network by utilizing the recently developed quantum neural network. To our knowledge, we are the first attempt to apply quantum neural networks for neural distinguisher. The target ciphers are simplified ciphers (S-DES, S-AES, S-PRESENT-[4]), and a quantum neural distinguisher that classifies the input difference from random data was constructed using the Pennylane library. Finally, we obtained quantum advantages in this work: improved accuracy and reduced number of parameters. Therefore, our work can be used as a quantum neural distinguisher with high reliability for simplified ciphers.

Primal attack, BKW attack, and dual attack are three well-known attacks to LWE. To build efficient post-quantum cryptosystems in practice, the structured variants of LWE (i.e. MLWE/RLWE) are often used. Some efforts have been spent on addressing concerns about additional vulnerabilities introduced by algebraic structures and no effective attack method based on ideal lattices or module lattices has been proposed so far; these include refining primal attack and BKW attack to MLWE/RLWE. It is thus an interesting problem to consider how to enhance the dual attack against LWE with the rich algebraic structure of MLWE (including RLWE). In this paper, we present the first attempt to this problem by observing that each short vector found by BKZ generates another n − 1 vectors of the same length automatically and all of these short vectors can be used to distinguish. To this end, an interesting property which indicates the rotations are consistent with certain linear transformations is proved, and a new kind of intersection lattice is constructed with some tricks. Moreover, we notice that coefficient vectors of different rotations of the same polynomial are near-orthogonal in high-dimensional spaces. This is validated by extensive experiments and is treated as an extension to the assumption under the original dual attack against LWE. Taking Newhope512 as an example, we show that by our enhanced dual attack method, the required blocksize and time complexity (in both classical and quantum cases) all decrease. It is remarked that our improvement is not significant and its limitation is also touched on. Our results do not reveal a severe security problem for MLWE/RLWE compared to that of a general LWE, this is consistent with the findings by the previous work for using primal and BKW attacks to MLWE/RLWE.

We demonstrate that with some ideas from group theory we are very often able to recover the keywords for a quagmire cipher from its key table. This would be the last task for a cryptologist in analyzing such a cipher.

Indistinguishability Obfuscation $(i\mathcal{O})$ is a highly versatile primitive implying a myriad advanced cryptographic applications. Up until recently, the state of feasibility of $i\mathcal{O}$ was unclear, which changed with works (Jain-Lin-Sahai STOC 2021, Jain-Lin-Sahai Eurocrypt 2022) showing that $i\mathcal{O}$ can be finally based upon well-studied hardness assumptions. Unfortunately, one of these assumptions is broken in quantum polynomial time. Luckily, the line work of Brakerski et al. Eurocrypt 2020, Gay-Pass STOC 2021, Wichs-Wee Eurocrypt 2021, Brakerski et al. ePrint 2021, Devadas et al. TCC 2021 simultaneously created new pathways to construct $i\mathcal{O}$ with plausible post-quantum security from new assumptions, namely a new form of circular security of LWE in the presence of leakages. At the same time, effective cryptanalysis of this line of work has also begun to emerge (Hopkins et al. Crypto 2021). It is important to identify the simplest possible conjectures that yield post-quantum $i\mathcal{O}$ and can be understood through known cryptanalytic tools. In that spirit, and in light of the cryptanalysis of Hopkins et al., recently Devadas et al. gave an elegant construction of $i\mathcal{O}$ from a fully-specified and simple-to-state assumption along with a thorough initial cryptanalysis. Our work gives a polynomial-time distinguisher on their "final assumption" for their scheme. Our algorithm is extremely simple to describe: Solve a carefully designed linear system arising out of the assumption. The argument of correctness of our algorithm, however, is nontrivial. We also analyze the "T-sum" version of the same assumption described by Devadas et. al. and under a reasonable conjecture rule out the assumption for any value of $T$ that implies $i\mathcal{O}$.

RAGHAV is a 64-bit block cipher proposed by Bansod in 2021. It supports 80-, and 128-bit secret keys. The designer evaluated its security against typical attack, such as differential cryptanalysis, linear cryptanalysis, and so on. On the other hand, it has not been reported the security of RAGHAV against higher order differential attack, which is one of the algebraic attacks. In this paper, we applied higher order differential cryptanalysis to RAGHAV. As a results, we found a new full-round higher order characteristic of RAGHAV using 1-st order differential. Exploiting this characteristic, we also show that the full-round of RAGHAV is attackable by distinguishing attack with 2 chosen plaintexts.

ARIA is a block cipher proposed by Kwon et al. at ICISC 2003, and it is widely used as the national standard block cipher in the Republic of Korea. In this study, we identify some flaws in the quantum rebound attack on 7-round ARIA-DM proposed by Dou et al., and we reveal that the limit of this attack is up to 5-round. Our revised attack applies not only to ARIA-DM but also to ARIA-MMO and ARIA-MP among the PGV models, and it is valid for all key lengths of ARIA. Moreover, we present dedicated quantum rebound attacks on 7-round ARIA-Hirose and ARIA-MJH for the first time. These attacks are only valid for the 256-bit key length of ARIA because they are constructed using the degrees of freedom in the key schedule. All our attacks are faster than the generic quantum attack in the cost metric of time–space tradeoff.

Fruit is a small-state stream cipher designed for securing communications among resource-constrained devices. The design of Fruit was first known to the public in 2016. It was later improved as Fruit-80 in 2018 and becomes the latest and final version among all versions of the Fruit stream ciphers. In this paper, we analyze the Fruit-80 stream cipher. We found that Fruit-80 generates identical keystreams from certain two distinct pairs of key and IV. Such pair of key and IV pairs is known as a slid pair. Moreover, we discover that when two pairs of key and IV fulfill specific characteristics, they will generate identical keystreams. This shows that slid pairs do not always exist arbitrarily in Fruit-80. We define specific rules which are equivalent to the characteristics. Using the defined rules, we are able to automate the searching process using an MILP solver, which makes searching of the slid pairs trivial.

Continuous authentication has been proposed as a complementary security mechanism to password-based authentication for computer devices that are handled directly by humans, such as smart phones. Continuous authentication has some privacy issues as certain user features and actions are revealed to the authentication server, which is not assumed to be trusted. Wei et al. proposed in 2021 a privacy-preserving protocol for behavioral authentication that utilizes homomorphic encryption. The encryption prevents the server from obtaining sampled user features. In this paper, we show that the Wei et al. scheme is insecure regarding both an honest-but-curious server and an active eavesdropper. We present two attacks. The first attack enables the authentication server to obtain the secret user key, plaintext behavior template and plaintext authentication behavior data from encrypted data. The second attack enables an active eavesdropper to restore the plaintext authentication behavior data from the transmitted encrypted data.

TinyJAMBU is one of the finalists in the NIST lightweight standardization competition. This paper presents full round practical zero-sum distinguishers on the keyed permutation used in TinyJAMBU. We propose a full round zero-sum distinguisher on the 128- and 192-bit key variants and a reduced round zero-sum distinguisher for the 256-bit key variant in the known-key settings. Our best known-key distinguisher works with $2^{16}$ data/time complexity on the full 128-bit version and with $2^{23}$ data/time complexity on the full 192-bit version. For the 256-bit ver- sion, we can distinguish 1152 rounds (out of 1280 rounds) in the known- key settings. In addition, we present the best zero-sum distinguishers in the secret-key settings: with complexity $2^{23}$ we can distinguish 544 rounds in the forward direction or 576 rounds in the backward direction. For finding the zero-sum distinguisher, we bound the algebraic degree of the TinyJAMBU permutation using the monomial prediction technique proposed by Hu et al. at ASIACRYPT 2020. We model the monomial prediction rule on TinyJAMBU in MILP and find upper bounds on the degree by computing the parity of the number of solutions.

The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized cost of evaluating $f_{G,H}$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=|\mathcal{X}|$ times a quantum attacker running Grover's algorithm only requires $\mathcal{O}(\sqrt{m})$ blackbox calls to a quantum circuit $C_{G,H}$ evaluating the function $f_{G,H}$. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit $C_{G,H}$. We first observe that a legal black pebbling strategy for the graph $G$ does not necessarily imply the existence of a quantum circuit with comparable complexity --- in contrast to the classical setting where any efficient pebbling strategy for $G$ corresponds to an algorithm with comparable complexity for evaluating $f_{G,H}$. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. Specifically, (1) we show that a line graph of size $N$ has reversible space-time complexity at most $\mathcal{O}\left(N^{1+\frac{2}{\sqrt{\log N}}}\right)$. (2) We show that any $(e,d)$-reducible DAG has reversible space-time complexity at most $\mathcal{O}(Ne+dN2^d)$. In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most $\mathcal{O}(N^2 \log \log N/\sqrt{\log N})$ and $\mathcal{O}(N^2/\sqrt[3]{\log N})$, respectively. (3) We show that the reversible space-time complexity of DRSample is at most $\mathcal{O}(N^2 \log \log N/\log N)$. We also study the cumulative pebbling cost of reversible pebblings extending a (non-reversible) pebbling attack of Alwen and Blocki on depth-reducible graphs.

We present a key-recovery fault injection attack on the Classic McEliece Key Encapsulation Mechanism (KEM). The fault injections target the error-locator polynomial of the Goppa code and the validity checks in the decryption algorithm, making a chosen ciphertext attack possible. Faulty decryption outputs are used to generate a system of polynomial equations in the secret support elements of the Goppa code. After solving the equations, we can determine a suitable Goppa polynomial and form an alternative secret key. To demonstrate the feasibility of the attack on hardware, we simulate the fault injections on virtual prototypes of two RISC-V cores at register-transfer level.

Since the introduction of differential-neural cryptanalysis, as the machine learning assisted differential cryptanalysis proposed in [Goh19] is coined by now, a lot of followup works have been published, showing the applicability for a wide variety of ciphers. In this work, we set out to vet a multitude of differential-neural distinguishers presented so far, and additionally provide general insights. Firstly, we show for a selection of different ciphers how differential-neural distinguishers for those ciphers can be (automatically) optimized, also providing guidance to do so for other ciphers as well. Secondly, we explore a correlation between a differential-neural distinguisher's accuracy and a standard notion of difference between the two underlying distributions. Furthermore, we show that for a whole (practically relevant) class of ciphers, the differential-neural distinguisher can use differential features only. At last, we also rectify a common mistake in current literature, and show that, making use of an idea already presented in the foundational work[Goh19], the claimed improvements from using multiple ciphertext-pairs at once are at most marginal, if not non-existent.

In recent work, Backendal, Haller, and Paterson identified several exploitable vulnerabilities in the cloud storage provider MEGA. They demonstrated an RSA key recovery attack in which a malicious server could recover a client's private RSA key after 512 client login attempts. We show how to exploit additional information revealed by MEGA's protocol vulnerabilities to give an attack that requires only six client logins to recover the secret key. Our optimized attack combines several cryptanalytic techniques. In particular, we formulate and give a solution to a variant of the hidden number problem with small unknown multipliers, which may be of independent interest. We show that our lattice construction for this problem can be used to give improved results for the implicit factorization problem of May and Ritzenhofen.

Garbling schemes, invented in the 80's by Yao (FOCS'86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP'08), introducing a global offset $\Delta$ for all garbled wire values where XOR gates are computed locally without garbling them. To date, garbling sachems were not studied per their side-channel attacks (SCA) security characteristics, even though SCA pose a significant security threat to cryptographic devices. In this research we demonstrate that adversaries utilizing advanced SCA tools such as horizontal attacks, mixed with advanced hypothesis building and standard (vertical) SCA tools, can jeopardize garbling implementations. Our main observation is that garbling schemes utilizing a global secret $\Delta$ open a door to quite trivial side-channel attacks. We model our side-channel attacks on the garbler's device and discuss the asymmetric setting where various computations are not performed on the evaluator side. This enables dangerous leakage extraction on the garbler and renders our attack impossible on the evaluator's side. Theoretically, we first demonstrate on a simulated environment, that such attacks are quite devastating. Concretely, our attack is capable of extracting $\Delta$ when the circuit embeds only $8$ input non-linear gates with fifth/first-order attack Success-Rates of $0.65$/$0.7$. With as little as $3$ such gates, our attack reduces the first-order Guessing Entropy of $\Delta$ from $128$ to $\sim48$-bits. We further demonstrate our attack via an implementation and measurements data over an STM 32-bit processor software implementing circuit garbling, and discuss their limitations and mitigation tactics on logical, protocol and implementation layers.

Unsupervised side-channel attacks allow extracting secret keys manipulated by cryptographic primitives through leakages of their physical implementations. As opposed to supervised attacks, they do not require a preliminary profiling of the target, constituting a broader threat since they imply weaker assumptions on the adversary model. Their downside is their requirement for some a priori knowledge on the leakage model of the device. On one hand, stochastic attacks such as the Linear Regression Analysis (LRA) allow for a flexible a priori, but are mostly limited to a univariate treatment of the traces. On the other hand, model-based attacks require an explicit formulation of the leakage model but have recently been extended to multidimensional versions allowing to benefit from the potential of Deep Learning (DL) techniques. The EVIL Machine Attack (EMA), introduced in this paper, aims at taking the best of both worlds. Inspired by generative adversarial networks, its architecture is able to recover a representation of the leakage model, which is then turned into a key distinguisher allowing flexible a priori. In addition, state-of-the-art DL techniques require 256 network trainings to conduct the attack. EMA requires only one, scaling down the time complexity of such attacks by a considerable factor. Simulations and real experiments show that EMA is applicable in cases where the adversary has very low knowledge on the leakage model, while significantly reducing the required number of traces compared to a classical LRA. Eventually, a generalization of EMA, able to deal with masked implementation is introduced.

The security guarantees of most isogeny-based protocols rely on the computational hardness of finding an isogeny between two supersingular isogenous curves defined over a prime field $\mathbb{F}_q$ with $q$ a power of a large prime $p$. In most scenarios, the isogeny is known to be of degree $\ell^e$ for some small prime $\ell$. We call this problem the Supersingular Fixed-Degree Isogeny Path (SIPFD) problem. It is believed that the most general version of SIPFD is not solvable faster than in exponential time by classical as well as quantum attackers. In a classical setting, a meet-in-the-middle algorithm is the fastest known strategy for solving the SIPFD. However, due to its stringent memory requirements, it quickly becomes infeasible for moderately large SIPFD instances. In a practical setting, one has therefore to resort to time-memory trade-offs to instantiate attacks on the SIPFD. This is particularly true for GPU platforms, which are inherently more memory-constrained than CPU architectures. In such a setting, a van Oorschot-Wiener-based collision finding algorithm offers a better asymptotic scaling. Finding the best algorithmic choice for solving instances under a fixed prime size, memory budget and computational platform remains so far an open problem. To answer this question, we present a precise estimation of the costs of both strategies considering most recent algorithmic improvements. As a second main contribution, we substantiate our estimations via optimized software implementations of both algorithms. In this context, we provide the first optimized GPU implementation of the van Oorschot-Wiener approach for solving the SIPFD. Based on practical measurements we extrapolate the running times for solving different-sized instances. Finally, we give estimates of the costs of computing a degree-$2^{88}$ isogeny using our CUDA software library running on an NVIDIA A100 GPU server.

CRYSTALS-Kyber has been recently selected by the NIST as a new public-key encryption and key-establishment algorithm to be standardized. This makes it important to assess how well CRYSTALS-Kyber implementations withstand side-channel attacks. Software implementations of CRYSTALS-Kyber have been already analyzed and the discovered vulnerabilities were patched in the subsequently released versions. In this paper, we present a profiling side-channel attack on a hardware implementation of CRYSTALS-Kyber with the security parameter $k = 3$, Kyber768. Since hardware implementations carry out computation in parallel, they are typically more difficult to break than their software counterparts. We demonstrate a successful message (session key) recovery by deep learning-based power analysis. Our results indicate that currently available hardware implementations of CRYSTALS-Kyber need better protection against side-channel attacks.

Conventional bit-based division property (CBDP) and bit- based division property using three subsets (BDPT) introduced by Todo et al. at FSE 2016 are the most effective techniques for finding integral characteristics of symmetric ciphers. At ASIACRYPT 2019, Wang et al. proposed the idea of modeling the propagation of BDPT, and recently Liu et al. described a model set method that characterized the BDPT propagation. However, the linear layers of the block ciphers which are analyzed using the above two methods of BDPT propagation are restricted to simple bit permutation. Thus the feasibility of the MILP method of BDPT propagation to analyze ciphers with complex linear layers is not settled. In this paper, we focus on constructing an automatic search algorithm that can accurately characterize BDPT propagation for ciphers with complex linear layers. We first introduce BDPT propagation rule for the binary diffusion layer and model that propagation in MILP efficiently. The solutions to these inequalities are exact BDPT trails of the binary diffusion layer. Next, we propose a new algorithm that models Key-Xor operation in BDPT based on MILP technique. Based on these ideas, we construct an automatic search algorithm that accurately characterizes the BDPT propagation and we prove the correctness of our search algorithm. We demonstrate our model for the block ciphers with non-binary diffusion layers by decomposing the non-binary linear layer trivially by the COPY and XOR operations. Therefore, we apply our method to search integral distinguishers based on BDPT of SIMON, SIMON(102), PRINCE, MANTIS, PRIDE, and KLEIN block ciphers. For PRINCE and MANTIS, we find (2 + 2) and (3 + 3) round integral distinguishers respectively which are longest to date. We also improve the previous best integral distinguishers of PRIDE and KLEIN. For SIMON, SIMON(102), the integral distinguishers found by our method are consistent with the existing longest distinguishers.

ASCON is a family of cryptographic primitives for authenticated encryption and hashing introduced in 2015. It is selected as one of the ten finalists in the NIST Lightweight Cryptography competition. Since its introduction, ASCON has been extensively cryptanalyzed, and the results of these analyses can indicate the good resistance of this family of cryptographic primitives against known attacks, like differential and linear cryptanalysis. Proving upper bounds for the differential probability of differential trails and for the squared correlation of linear trails is a standard requirement to evaluate the security of cryptographic primitives. It can be done analytically for some primitives like AES. For other primitives, computer assistance is required to prove strong upper bounds for differential and linear trails. Computer-aided tools can be classified into two categories: tools based on general-purpose solvers and dedicated tools. General-purpose solvers such as SAT and MILP are widely used to prove these bounds, however they seem to have lower capabilities and thus yield less powerful bounds compared to dedicated tools. In this work, we present a dedicated tool for trail search in ASCON. We arrange 2-round trails in a tree and traverse this tree in an efficient way using a number of new techniques we introduce. Then we extend these trails to more rounds, where we also use the tree traversal technique to do it efficiently. This allows us to scan much larger spaces of trails faster than the previous methods using general-purpose solvers. As a result, we prove tight bounds for 3-rounds linear trails, and for both differential and linear trails, we improve the existing upper bounds for other number of rounds. In particular, for the first time, we prove bounds beyond $2^{-128}$ for 6 rounds and beyond $2^{-256}$ for 12 rounds of both differential and linear trails.

The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD). A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error. This algorithm was long forgotten because even the best variants of it performed poorly when compared to the simplest ISD algorithm. We revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decodings at code rates smaller than $0.3$. It gives for the first time after $60$ years, a better decoding algorithm for a significant range which does not belong to the ISD family.

Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message. DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines security from the point of view of the adversary while remaining undetected by users. ASAs have been considered against a number of primitives including digital signatures, symmetric encryption and pseudo-random generators. However, public-key encryption has presented a less fruitful target, as the sender's only secrets are plaintexts and ASA techniques generally do not provide sufficient bandwidth to leak these. In this work, we show that subversion attacks against deniable encryption schemes present an attractive opportunity for an adversary. We note that whilst the notion is widely accepted, there are as yet no practical deniable PKE schemes; we demonstrate the feasibility of ASAs targeting deniable encryption using a representative scheme as a proof of concept. We also provide a formal model and discuss how to mitigate ASAs targeting deniable PKE schemes. Our results strengthen the security model for deniable encryption and highlight the necessity of considering subversion in the design of practical schemes.

An emerging direction of investigating the resilience of post-quantum cryptosystems under side-channel attacks is to consider the situations where leaked information is combined with traditional attack methods in various forms. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This idea is further developed in this paper. An accurate characterization of the information from perfect hints and modular hints is obtained through the establishment of an interesting decomposition of $\mathbb{Z}^n$. It is observed that modular hints with modulus $p$ produce some orthogonal projection of the secret in $\mathbb{Z}_p$, which is exactly an extension of the case of perfect hints in $\mathbb{R}$. Based on these, a new attack framework is described when some modular hints with modulus $q$ are available. In this framework, an adversary first reduces the LWE instance using such hints, and then performs various attacks on the new instance. One of the key characters of our framework is that the dimension of the secret in the new instance always decreases under some moderate conditions. A comparison with the previous work shows that our approach is in some sense more essential and applicable to various kinds of attacks. The new way of integrating modular hints to primal attack improves the existing work. The first attempt of using modular hints in dual attack and BKW attack is also discussed in the paper and better analysis results are produced. Experiments have been carried out and shown that multiple modular hints with modulus $q$ can indeed significantly reduce their attack costs. For examples, with just 100 hints, the blocksize can be reduced by 101 and the time complexity can be reduced by a factor of $2^{30}$ in both primal attack and dual attack against a Newhope1024 instance. As for the BKW attack, if 90 hints are available, the number of queries to the LWE oracle can be decreased by a factor of $2^{60}$, as do the time complexity and memory complexity when attacking an instance of Regev cryptosystem $(384,147457,39.19)$.

Combining theoretical-based traditional attack method with practical-based side-channel attack method provides more accurate security estimations for post-quantum cryptosystems. In CRYPTO 2020, Dachman-Soled et al. integrated hints from side-channel information to the primal attack against LWE schemes. This paper develops a general Fourier analytic framework to work with the dual attack in the presence of hints. Distinguishers that depend on specific geometric properties related to hints are established. The Fourier transform of discretized multivariate conditional Gaussian distribution on $\mathbb{Z}_q^d$ is carefully computed and estimated, some geometric characteristics of the resulting distinguisher are explored and a new model of dual attack is proposed. In our framework, an adversary performs the BKZ algorithm directly in a projected lattice to find short projection components, and then recovers them by MLLL algorithm to make a distinction. This method relies on a reasonable assumption and is backed up by naturally formed mathematical arguments. The improvements and the assumption are validated by experiments. For examples, for a Kyber768 instance, with 200 hints, the blocksize can be reduced by at least 188 and the time complexity can be reduced by a factor of greater than $2^{55}$. After adding 300 hints to a FireSaber instance, even in the worst case, the blocksize drops from 819 to 542, and the cost drops from $2^{255.61}$ to $2^{174.72}$.

We demonstrate how to apply some ideas from group theory to quagmire ciphers. Techniques are shown for amplifying one's knowledge of the keys. This is useful when breaking a ciphertext with a crib. The basic idea is that only a small amount of information goes into building a key table for a quagmire cipher, so we should only need that much information to reconstruct it.

The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has become urgent and important to evaluate the security of LowMC in the Picnic setting. The best attacks on LowMC with full S-box layers used in Picnic3 were achieved with Dinur's algorithm. For LowMC with partial nonlinear layers, e.g. 10 S-boxes per round adopted in Picnic2, the best attacks on LowMC were published by Banik et al. with the meet-in-the-middle (MITM) method. In this paper, we improve the attacks on LowMC in a model where memory consumption is costly. First, a new attack on 3-round LowMC with full S-box layers with negligible memory complexity is found, which can outperform Bouillaguet et al.'s fast exhaustive search attack and can achieve better time-memory tradeoffs than Dinur's algorithm. Second, we extend the 3-round attack to 4 rounds to significantly reduce the memory complexity of Dinur's algorithm at the sacrifice of a small factor of time complexity. For LowMC instances with 1 S-box per round, our attacks are shown to be much faster than the MITM attacks. For LowMC instances with 10 S-boxes per round, we can reduce the memory complexity from 32GB ($2^{38}$ bits) to only 256KB ($2^{21}$ bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about $2^{3.2}\sim 2^{5}$ times higher than that of the MITM attacks. A notable feature of our new attacks (apart from the 4-round attack) is their simplicity. Specifically, only some basic linear algebra is required to understand them and they can be easily implemented.

We propose new time-memory trade-offs for the random subset sum problem defined on $(a_1,\ldots,a_n,t)$ over $\mathbb{Z}_{2^n}$. Our trade-offs yield significant running time improvements for every fixed memory limit $M\geq2^{0.091n}$. Furthermore, we interpolate to the running times of the fastest known algorithms when memory is not limited. Technically, our design introduces a pruning strategy to the construction by Becker-Coron-Joux (BCJ) that allows for an exponentially small success probability. We compensate for this reduced probability by multiple randomized executions. Our main improvement stems from the clever reuse of parts of the computation in subsequent executions to reduce the time complexity per iteration. As an application of our construction, we derive the first non-trivial time-memory trade-offs for Information Set Decoding (ISD) algorithms. Our new algorithms improve on previous (implicit) trade-offs asymptotically as well as practically. Moreover, our optimized implementation also improves on running time, due to reduced memory access costs. We demonstrate this by obtaining a new record computation in decoding quasi-cyclic codes (QC-3138). Using our newly obtained data points we then extrapolate the hardness of suggested parameter sets for the NIST PQC fourth round candidates McEliece, BIKE and HQC, lowering previous estimates by up to 6 bits and further increasing their reliability.

The code-based post-quantum algorithm Hamming Quasi-Cyclic (HQC) is a fourth round candidate in the NIST standardization project. Since their third round version the authors utilize a new combination of error correcting codes, namely a combination of a Reed-Muller and a Reed-Solomon code, which requires an adaption of published attacks. We identify that the power side-channel attack by Uneo et al. from CHES 2021 does not work in practice as they miss the fact that the implemented Reed-Muller decoder does not have a fixed decoding boundary. In this work we provide a novel attack strategy that again allows for a successful attack. Our attack does not rely on simulation to verify its success but is proven with high probability for the HQC parameter sets. In contrast to the timing side-channel attack by Guo et al. we are able to reduce the required attack queries by a factor of 12 and are able to eliminate the inherent uncertainty of their used timing oracle. We show practical attack results utilizing a power side-channel of the used Reed-Solomon decoder on an ARM Cortex-M4 microcontroller. In addition, we provide a discussion on how or whether our attack strategy is usable with the side-channel targets of mentioned related work. Finally, we use information set decoding to evaluate the remaining attack complexity for partially retrieved secret keys. This work again emphasizes the need for a side-channel secure implementation of all relevant building blocks of HQC.

We give algebraic relations among equations of three algebraic modelings for MinRank problem: support minors modeling, Kipnis–Shamir modeling and minors modeling.

This note describes an observation discovered during a failed cryptanalysis attempt. Let $P(x,y)$ be a bivariate polynomial with coefficients in $\mathbb{C}$. Form the $n\times n$ matrices $L(n)$ whose elements are defined by $P(i,j)$. Define the matrices $M(n)=L(n)-\mbox{ID}_n$. It appears that $\mu(n)=(-1)^n\det(M_n)$ is a polynomial in $n$ that we did not characterize. We provide a numerical example.

This note describes the implementation of the Castryck-Decru key recovery attack on SIDH using the computer algebra system, SageMath. We describe in detail alternate computation methods for the isogeny steps of the original attack ($(2,2)$-isogenies from a product of elliptic curves and from a Jacobian), using explicit formulas to compute values of these isogenies at given points, motivated by both performance considerations and working around SageMath limitations. A performance analysis is provided, with focus given to the various algorithmic and SageMath specific improvements made during development, which in total accumulated in approximately an eight-fold performance improvement compared with a naïve reimplementation of the proof of concept.

This paper presents an approach to uncover and analyze power side-channel leakages on a processor cycle level precision. By carefully designing and evaluating the measurement setup, accurate trace timing is enabled, which is used to overlay the trace with the corresponding assembly code. This methodology allows to expose the sources of leakage on a processor cycle scale, which allows for evaluating new implementations. It also exposes that the default ChipWhisperer configuration for STM32F4 targets used in prior work includes wait cycles that are rarely used in real-world applications, but affect power side-channel leakage. As an application for our setup, we target the widely used Sign-Flip function of Gaussian sampling code used in multiple Post-Quantum Key-Exchange Mechanisms and Signature schemes. We propose new implementations for the Sign-Flip function based on our analysis on the original implementation and further evaluate their leakage. Our findings allow the conclusion that unmasked cryptographic implementations of schemes based on Gaussian random numbers for STM32F4 cannot be secure against power side-channel, and that masking just the Gaussian sampler is not a viable option.

The Montgomery Ladder is widely used for implementing the scalar multiplication in elliptic curve cryptographic designs. This algorithm is efficient and provides a natural robustness against (simple) side-channel attacks. Previous works however showed that implementations of the Montgomery Ladder using Lopez-Dahab projective coordinates easily leak the value of the most significant bits of the secret scalar, which led to a full key recovery in an attack known as LadderLeak. In light of such leakage, we analyse further popular methods for implementing the Montgomery Ladder. We first consider open source software implementations of the X25519 protocol which implement the Montgomery Ladder based on the ladderstep algorithm from Düll et al. [15]. We confirm via power measurements that these implementations also easily leak the most significant scalar bits, even when implementing Z-coordinate ran- domisations. We thus propose simple modifications of the algorithm and its handling of the most significant bits and show the effectiveness of our modifications via experimental results. Particularly, our re-designs of the algorithm do not incurring significant efficiency penalties. As a second case study, we consider open source hardware implementations of the Montgomery Ladder based on the complete addition formulas for prime order elliptic curves, where we observe the exact same leakage. As we explain, the most significant bits in implementations of the complete addition formulas can be protected in an analogous way as we do for Curve25519 in our first case study.

In the Nostradamus attack, introduced by Kelsey and Kohno (Eurocrypt 2006), the adversary has to commit to a hash value y of an iterated hash function H such that, when later given a message prefix P, the adversary is able to find a suitable "suffix explanation" S with H(P||S)=y. Kelsey and Kohno show a herding attack with $2^{2n/3}$ evaluations of the compression function of H (with n bits output and state), locating the attack between preimage attacks and collision search in terms of complexity. Here we investigate the security of Nostradamus attacks for quantum adversaries. We present a quantum herding algorithm for the Nostradamus problem making approximately $\sqrt[3]{n}\cdot 2^{3n/7}$ compression function evaluations, significantly improving over the classical bound. We also prove that quantum herding attacks cannot do better than $2^{3n/7}$ evaluations for random compression functions, showing that our algorithm is (essentially) optimal. We also discuss a slightly less tight bound of roughly $2^{3n/7-s}$ for general Nostradamus attacks against random compression functions, where s is the maximal block length of the adversarially chosen suffix S.

Garbling is a cryptographic primitive which has many applications. It is mainly used for scenes of limited authority, such as multi-party computation (MPC), attribute-based encryption (ABE), functional encryption (FE), indistinguishability obfuscation (IO), etc. Garbling schemes before 2013 are of one-time garbling. Goldwasser et al and Agrawal presented a reusable garbling scheme, which made use of a symmetric encryption scheme and an FE scheme as the components. In this paper we discuss the validity and the efficiency of reusable garbling scheme. We present the following three notes on the scheme. (1) Reusable garbling scheme does not provide new applications, and it is still a one-time garbling scheme. (2) Even reusable garbling scheme is taken as a one-time garbling scheme, sometimes it is not usable. More detailedly, it can only be used for Basic Scene 2, and cannot be used for Basic Scene 1. For example, it cannot be used for MPC. (3) Even reusable garbling scheme is taken as a one-time garbling scheme used for Basic Scene 2, there is no evidence to show that its efficiency is better than a former one-time garbling scheme.

At Eurocrypt 2022, May et al. proposed a partial key exposure (PKE) attack on CRT-RSA that efficiently factors $N$ knowing only a $\frac{1}{3}$-fraction of either most significant bits (MSBs) or least significant bits (LSBs) of private exponents $d_p$ and $d_q$ for public exponent $e \approx N^{\frac{1}{12}}$. In practice, PKE attacks typically rely on the side-channel leakage of these exponents, while a side-channel resistant implementation of CRT-RSA often uses additively blinded exponents $d^{\prime}_p = d_p + r_p(p-1)$ and $d^{\prime}_q = d_q + r_q(q-1)$ with unknown random blinding factors $r_p$ and $r_q$, which makes PKE attacks more challenging. Motivated by the above, we extend the PKE attack of May et al. to CRT-RSA with additive exponent blinding. While admitting $r_pe\in(0,N^{\frac{1}{4}})$, our extended PKE works ideally when $r_pe \approx N^{\frac{1}{12}}$, in which case the entire private key can be recovered using only $\frac{1}{3}$ known MSBs or LSBs of the blinded CRT exponents $d^{\prime}_p$ and $d^{\prime}_q$. Our extended PKE follows their novel two-step approach to first compute the key-dependent constant $k^{\prime}$ ($ed^{\prime}_p = 1 + k^{\prime}(p-1)$, $ed^{\prime}_q = 1 + l^{\prime}(q-1)$), and then to factor $N$ by computing the root of a univariate polynomial modulo $k^{\prime}p$. We extend their approach as follows. For the MSB case, we propose two options for the first step of the attack, either by obtaining a single estimate $k^{\prime}l^{\prime}$ and calculating $k^{\prime}$ via factoring, or by obtaining multiple estimates $k^{\prime}l^{\prime}_1,\ldots,k^{\prime}l^{\prime}_z$ and calculating $k^{\prime}$ probabilistically via GCD. For the LSB case, we extend their approach by constructing a different univariate polynomial in the second step of the LSB attack. A formal analysis shows that our LSB attack runs in polynomial time under the standard Coppersmith-type assumption, while our MSB attack either runs in sub-exponential time with a reduced input size (the problem is reduced to factor a number of size $e^2r_pr_q\approx N^{\frac{1}{6}}$) or in probabilistic polynomial time under a novel heuristic assumption. Under the settings of the most common key sizes (1024-bit, 2048-bit, and 3072-bit) and blinding factor lengths (32-bit, 64-bit, and 128-bit), our experiments verify the validity of the Coppersmith-type assumption and our own assumption, as well as the feasibility of the factoring step. To the best of our knowledge, this is the first PKE on CRT-RSA with experimentally verified effectiveness against 128-bit unknown exponent blinding factors. We also demonstrate an application of the proposed PKE attack using real partial side-channel key leakage targeting a Montgomery Ladder exponentiation CRT implementation.

K-Cipher is an ultra-low latency block cipher with variable-length parameters designed by Intel Labs. In this work, we analyze the security of K-Cipher and propose a differential cryptanalysis attack with the complexity of $2^{29.7}$ for a variant of K-Cipher with state size $n=24$ bits state and block size $m=8$ bits. Our attack recovers the secret key and secret randomizer values with a total length of 240 bits in $\sim 30$ minutes on a standard desktop machine. We show that it is possible to extend the same attack for an arbitrary set of parameters.

In this article, we generalize the works of Pan et al. (Eurocrypt’21) and Porter et al. (ArXiv’21) and provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely, we show that the more automorphisms stabilize the ideal, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois fields, and we generalize it to any ideal (whose prime factors are not ramified) of any number field. We then provide a cryptographic application of this result by showing that particular instances of the partial Vandermonde knapsack problem, also known as partial Fourier recovery problem, can be solved classically in polynomial time. As a proof of concept, we implemented our attack and managed to solve those particular instances for concrete parameter settings proposed in the literature. For random instances, we can halve the lattice dimension with non-negligible probability.

TrCBC is a variant of CBC-MAC which appeared in Information Processing Letters, 112(7):302-307, 2012. The authors claimed TrCBC to be a secure message authentication code (MAC) with some interesting properties. If TrCBC is instantiated with a block cipher with block length n, then it requires ⌈λ/n⌉ block cipher calls for authenticating a λ-bit message and requires a single key, which is the block cipher key. The authors state that TrCBC can have tag lengths of size less than n/2. We show that with high probability, an adversary can forge TrCBC with tag length n/2 − 1 with just three queries. The attack that we show can be applied to forge a large class of messages. The authors proved TrCBC to be a pseudorandom function (PRF). A scrutiny of the claimed PRF bound shows that for some recommended values of tag lengths, the bound turns out to be quite large. Thus, the security theorem does not imply security of TrCBC for all recommended tag lengths.

Multiple recursive generators are an important class of pseudorandom number generators which are widely used in cryptography. The predictability of truncated sequences that predict the whole sequences by the truncated high-order bits of the sequences is not only a crucial aspect of evaluating the security of pseudorandom number generators but also serves an important role in the design of pseudorandom number generators. This paper improves the work of Sun et al on the predictability of truncated multiple recursive generators with unknown parameters. Given a few truncated digits of high-order bits output by a multiple recursive generator, we adopt the resultant, the Chinese Remainder Theorem and the idea of recovering $p$-adic coordinates of the coefficients layer by layer, and Kannan's embedding technique to recover the modulus, the coefficients and the initial state, respectively. Experimental results show that our new method is superior to that of the work of Sun et al, no matter in terms of the running time or the number of truncated digits required.

TinyJambu is one of the finalists in the NIST lightweight cryptography competition. It has undergone extensive analysis in the recent years as both the keyed permutation as well as the mode are new designs. In this paper we present a related-key forgery attackon the updated TinyJambu scheme with 256- and 192-bit keys. We introduce a high probability related-key differential attack were the differences are only introduced into the key state. Therefore, the characteristic is applicable to the TinyJambu mode and can be used to mount a forgery attack. The time and data complexity of the forgery are $2^{32}$ using $2^{10}$ related-keys for the 256-bit key version, and $2^{42}$ using $2^{12}$ related-keys for the 192-bit key version. For the 128-bit key we construct a related-key differential characteristic on the full keyed permutation of TinyJambu with a probability of $2^{-16}$. We extend the related-key differential characteristics on TinyJambu to practical time key recovery attacks that extract the full key from the keyed permutation with a time and data complexity of $2^{23}$, $2^{20}$, and $2^{18}$ for respectively the 128-, 192-, and 256-bit key variants. All characteristics are experimentally verified and we provide key nonce pairs that produce the same tag to show the feasibility of the forgery attack.

We present an attack on SIDH which does not require any endomorphism information on the starting curve. Our attack has subexponential complexity thus significantly reducing the security of SIDH and SIKE; our analysis and preliminary implementation suggests that our algorithm will be feasible for the Microsoft challenge parameters $p = 2^{110}3^{67}-1$ on a regular computer. Our attack applies to any isogeny-based cryptosystem that publishes the images of points under the secret isogeny, for example Seta and B-SIDH. It does not apply to CSIDH, CSI-FiSh, or SQISign.

In this paper, we compute an algebraic decomposition of blackbox rings in the generic ring model. More precisely, we explicitly decompose a black-box ring as a direct product of a nilpotent black-box ring and local Artinian black-box rings, by computing all its primitive idempotents. The algorithm presented in this paper uses quantum subroutines for the computation of the p-power parts of a black-box ring and then classical algorithms for the computation of the corresponding primitive idempotents. As a by-product, we get that the reduction of a black-box ring is also a black-box ring. The first application of this decomposition is an extension of the work of Maurer and Raub [26] on representation problem in black-box finite fields to the case of reduced p-power black-box rings. Another important application is an IND-CCA1 attack for any ring homomorphic encryption scheme in the generic ring model. Moreover, when the plaintext space is a nite reduced black-box ring, we present a plaintext-recovery attack based on representation problem in black-box prime fields. In particular, if the ciphertext space has smooth characteristic, the plaintext-recovery attack is effectively computable in the generic ring model.

SPHINCS$^+$ is a stateless hash-based signature scheme that has been selected for standardization as part of the NIST post-quantum cryptography (PQC) standardization process. Its security proof relies on the distinct-function multi-target second-preimage resistance (DM-SPR) of the underlying keyed hash function. The SPHINCS$^+$ submission offered several instantiations of this keyed hash function, including one based on SHA-256. A recent observation by Sydney Antonov on the PQC mailing list demonstrated that the construction based on SHA-256 did not have DM-SPR at NIST category five, for several of the parameter sets submitted to NIST; however, it remained an open question whether this observation leads to a forgery attack. We answer this question in the affirmative by giving a complete forgery attack that reduces the concrete classical security of these parameter sets by approximately 40 bits of security. Our attack works by applying Antonov's technique to the {WOTS$^+$} public keys in {\SPHINCS}, leading to a new one-time key that can sign a very limited set of hash values. From that key, we construct a slightly altered version of the original hypertree with which we can sign arbitrary messages, yielding signatures that appear valid.