With the standardization of NIST post-quantum cryptographic (PQC) schemes, optimizing these PQC schemes across various platforms presents significant research value. While most existing software implementation efforts have concentrated on ARM platforms, research on PQC implementations utilizing various RISC-V instruction set architectures (ISAs) remains limited. In light of this gap, this paper proposes comprehensive and efficient optimizations of Keccak, Kyber, and Dilithium on...

Digital signature is a fundamental cryptographic primitive and is widely used in the real world. Unfortunately, the current digital signature standards like EC-DSA and RSA are not quantum-resistant. Among post-quantum cryptography (PQC), isogeny-based signatures preserve some advantages of elliptic curve cryptosystems, particularly offering small signature sizes. Currently, SQIsign and its variants are the most promising isogeny-based digital signature schemes. In this paper, we propose a...

This tutorial focuses on describing the fundamental mathematical concepts and design decisions used in the two ``main'' lattice schemes standardized by NIST and included in the CNSA 2.0 algorithmic suite. They are the KEM / encryption scheme CRYSTALS-Kyber (ML-KEM) and the signature scheme CRYSTALS-Dilithium (ML-DSA) . In addition, we will also give the main ideas behind other lattice-based KEMs like Frodo and NTRU.

This paper presents extensions to the OpenTitan hardware root of trust that aim at enabling high-performance lattice-based cryptography. We start by carefully optimizing ML-KEM and ML-DSA - the two primary algorithms selected by NIST for standardization - in software targeting the OTBN accelerator. Based on profiling results of these implementations, we propose tightly integrated extensions to OTBN, specifically an interface from OTBN to OpenTitan's Keccak accelerator (KMAC core) and...

$SPHINCS^+$, one of the Post-Quantum Cryptography Digital Signature Algorithms (PQC-DSA) selected by NIST in the third round, features very short public and private key lengths but faces significant performance challenges compared to other post-quantum cryptographic schemes, limiting its suitability for real-world applications. To address these challenges, we propose the GPU-based paRallel Accelerated $SPHINCS^+$ (GRASP), which leverages GPU technology to enhance the efficiency of...

$\mathrm{SPHINCS^{+}}$ is a post-quantum signature scheme that, at the time of writing, is being standardized as $\mathrm{SLH\text{-}DSA}$. It is the most conservative option for post-quantum signatures, but the original tight proofs of security were flawed—as reported by Kudinov, Kiktenko and Fedorov in 2020. In this work, we formally prove a tight security bound for $\mathrm{SPHINCS^{+}}$ using the EasyCrypt proof assistant, establishing greater confidence in the general security of the...

To introduce a post-quantum-secure encryption scheme specifically for use in flight-computers, we used avionics’ module-isolation methods to wrap a recent encryption standard (HPKE – Hybrid Public Key Encryption) within a software partition. This solution proposes an upgrade to HPKE, using quantum-resistant ciphers (Kyber/ML-KEM and Dilithium/ML-DSA) redundantly alongside well-established ciphers, to achieve post-quantum security. Because cryptographic technology can suddenly become...

Here is a potential way to create a SLH-DSA-like\cite{DraftFIPS205} key generation/signer that aspires to be resistant to DPA side channel attacks. We say that it is “SLH-DSA-like”, because it does not follow the FIPS 205 method of generating signatures (in particular, it does not have the same mapping from private key, messages, opt\_rand to signatures), however it does generate public keys and signatures that are compatible with the standard signature verification method, and with the...

Two recent proposals by Bernstein and Pornin emphasize the use of deterministic signatures in DSA and its elliptic curve-based variants. Deterministic signatures derive the required ephemeral key value in a deterministic manner from the message to be signed and the secret key instead of using random number generators. The goal is to prevent severe security issues, such as the straight-forward secret key recovery from low quality random numbers. Recent developments have raised skepticism...

We report on efficient and secure hardware implementation techniques for the FIPS 205 SLH-DSA Hash-Based Signature Standard. We demonstrate that very significant overall performance gains can be obtained from hardware that optimizes the padding formats and iterative hashing processes specific to SLH-DSA. A prototype implementation, SLotH, contains Keccak/SHAKE, SHA2-256, and SHA2-512 cores and supports all 12 parameter sets of SLH-DSA. SLotH also supports side-channel secure PRF computation...

CRYSTALS-Dilithium is a post-quantum secure digital signature algorithm currently being standardised by NIST. As a result, devices making use of CRYSTALS-Dilithium will soon become generally available and be deployed in various environments. It is thus important to assess the resistance of CRYSTALS-Dilithum implementations to physical attacks. In this paper, we present an attack on a CRYSTALS-Dilithium implementation in hedged mode in ARM Cortex-M4 using fault injection. Voltage glitching...

It has been shown that post-quantum key exchange and authentication with ML-KEM and ML-DSA, NIST’s postquantum algorithm picks, will have an impact on TLS 1.3 performance used in the Web or other applications. Studies so far have focused on the overhead of quantum-resistant algorithms on TLS time-to-first-byte (handshake time). Although these works have been important in quantifying the slowdown in connection establishment, they do not capture the full picture regarding real-world TLS 1.3...

While formal constructions for cryptographic schemes have steadily evolved and emerged over the past decades, the design and implementation of efficient and secure hardware instances is still a mostly manual, tedious, and intuition-driven process. With the increasing complexity of modern cryptography, e.g., Post-Quantum Cryptography (PQC) schemes, and consideration of physical implementation attacks, e.g., Side-Channel Analysis (SCA), the design space often grows exorbitantly without...

NIST has released the draft specification of SLH-DSA (also known as Sphincs+). When NIST released its original call for proposals for the Postquantum Process, they specified that signature systems would need to be usable at full security for $2^{64}$ signatures per private key. Hence, the parameter sets specified in SLH-DSA is tuned to have full security after that many signatures. However, it has been noted that in many cases, we don't have need for that many signatures, and that...

The threat posed by quantum computing has precipitated an urgent need for post-quantum cryptography. Recently, the post-quantum digital signature draft FIPS 204 has been published, delineating the details of the ML-DSA, which is derived from the CRYSTALS-Dilithium. Despite these advancements, server environments, especially those equipped with GPU devices necessitating high-throughput signing, remain entrenched in classical schemes. A conspicuous void exists in the realm of GPU...

The Hidden Number Problem (HNP) has been extensively used in the side-channel attacks against (EC)DSA and Diffie-Hellman. The lattice approach is a primary method of solving the HNP. In EUROCRYPT 2021, Albrecht and Heninger constructed a new lattice to solve the HNP, which converts the HNP to the SVP. After that, their approach became the state-of-the-art lattice method of solving the HNP. But Albrecht and Heninger's approach has a high failure rate for solving the HNP with one bit of nonce...

This draft presents work-in-progress concerning hybrid/composite signature schemes. More concretely, we give several tailored combinations of Fiat-Shamir based signature schemes (such as Dilithium) or Falcon with RSA or DSA. We observe that there are a number of signature hybridization goals, few of which are not achieved through parallel signing or concatenation approaches. These include proof composability (that the post-quantum hybrid signature security can easily be linked to the...

This is the second update of this report. In this update, we partially solve Open problem 2 and completely solve Open problem 3 from the previous version. By doing this we address one modification of the Panny's attack done by Nils Langius. In the first update we introduced conditions for choosing the parameters that render the attacks (both classical and quantum algorithms attacks) proposed by Lorenz Panny in March 2023 on the first variant, inapplicable. For the classical attack, we...

The elliptic curve family of schemes has the lowest computational latency, memory use, energy consumption, and bandwidth requirements, making it the most preferred public key method for adoption into network protocols. Being suitable for embedded devices and applicable for key exchange and authentication, ECC is assuming a prominent position in the field of IoT cryptography. The attractive properties of the relatively new curve Curve448 contribute to its inclusion in the TLS1.3 protocol and...

In this note, we explore parameter sets for SPHINCS+ which support a smaller number of signatures than $2^{64}$, but are otherwise compatible with the SLH-DSA specification. In practice, use cases for which a low number of signatures per key pair suffice are common, and as we will show this allows a significant reduction in signature size and verification speed for SPHINCS+. For this we carry out a larger search through the SPHINCS+ parameter space, comparing it with the current parameter...

Digital Signature Schemes such as DSA, ECDSA, and RSA are widely deployed to protect the integrity of security protocols such as TLS, SSH, and IPSec. In TLS, for instance, RSA and (EC)DSA are used to sign the state of the agreed upon protocol parameters during the handshake phase. Naturally, RSA and (EC)DSA implementations have become the target of numerous attacks, including powerful side-channel attacks. Hence, cryptographic libraries were patched repeatedly over the years. Here we...

This book chapter outlines techniques for breaking cryptography by taking advantage of implementation mistakes made in practice, with a focus on those that exploit the mathematical structure of the most widely used public-key primitives.

Lattice attacks are threats to (EC)DSA and have been used in cryptanalysis. In lattice attacks, a few bits of nonce leaks in multiple signatures are sufficient to recover the secret key. Currently, the BKZ algorithm is frequently used as a lattice reduction algorithm for lattice attacks, and there are many reports on the conditions for successful attacks. However, experimental attacks using the BKZ algorithm have only shown results for specific key lengths, and it is not clear how the...

The humble integers, $\mathbb{Z}$, are the backbone of many cryptosystems. When bridging the gap from theoretical systems to real-world implementations, programmers often look towards general purpose libraries to implement the arbitrary-precision arithmetic required. Alas, these libraries are often conceived without cryptography in mind, leaving applications potentially vulnerable to timing attacks. To address this, we present saferith, a library providing safer arbitrary-precision...

The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but...

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven...

In this paper, we improve the theoretical background of the attacks on the DSA schemes given in [1, 29], and we present some new more practical attacks.

Due to their use in crypto-currencies, threshold ECDSA signatures have received much attention in recent years. Though efficient solutions now exist both for the two party, and the full threshold scenario, there is still much room for improvement, be it in terms of protocol functionality, strengthening security or further optimising efficiency. In the past few months, a range of protocols have been published, allowing for a non interactive -- and hence extremely efficient -- signing...

Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short. We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for...

RSA key generation requires devices to generate large prime numbers. The naïve approach is to generate candidates at random, and then test each one for (probable) primality. However, it is faster to use a sieve method, where the candidates are chosen so as not to be divisible by a list of small prime numbers $\{p_i\}$. Sieve methods can be somewhat complex and time-consuming, at least by the standards of embedded and hardware implementations, and they can be tricky to defend against...

Side-channel attacks targeting cryptography may leak only partial or indirect information about the secret keys. There are a variety of techniques in the literature for recovering secret keys from partial information. In this tutorial, we survey several of the main families of partial key recovery algorithms for RSA, (EC)DSA, and (elliptic curve) Diffie-Hellman, the public-key cryptosystems in common use today. We categorize the known techniques by the structure of the information that is...

We present a sub-exponential forger by using a $k$-sum algorithm against the aggregate $\Gamma$-signature, which was proposed at AsiaCCS 2019 by Zhao. Our forger is a universal forger under a key-only attack and effective in the knowledge of secret key model. We also discuss the real impact of this attack in reality with Bitcoin applications. The discussions on the real impact of the attack also highlight the significant differences between the usage of individual signatures like EC-DSA...

We analyse whether the smartcards of the JavaCard platform correctly validate primality of domain parameters. The work is inspired by the paper Prime and prejudice: primality testing under adversarial conditions, where the authors analysed many open-source libraries and constructed pseudoprimes fooling the primality testing functions. However, in the case of smartcards, often there is no way to invoke the primality test directly, so we trigger it by replacing (EC)DSA and (EC)DH prime domain...

Following recent comments in a NIST document related to threshold cryptographic standards, we examine the case of thresholdizing the HashEdDSA signature scheme. This is a deterministic signature scheme based on Edwards elliptic curves. Unlike DSA, it has a Schnorr like signature equation, which is an advantage for threshold implementations, but it has the disadvantage of having the ephemeral secret obtained by hashing the secret key and the message. We show that one can obtain relatively...

Threshold Signatures allow n parties to share the power of issuing digital signatures so that any coalition of size at least (t+1) can sign, whereas groups of t or less players cannot. Over the last few years many schemes addressed the question of realizing efficient threshold variants for the specific case of EC-DSA signatures. In this paper we present new solutions to the problem that aim at reducing the overall bandwidth consumption. Our main contribution is a new variant of the Gennaro...

Quantum computers threaten to compromise public-key cryptography schemes such as DSA and ECDSA in polynomial time, which poses an imminent threat to secure signal processing. The cryptography community has responded with the development and standardization of post-quantum cryptography (PQC) algorithms, a class of public-key algorithms based on hard problems that no known quantum algorithms can solve in polynomial time. Ring learning with error (RLWE) lattice- based cryptographic (LBC)...

With the recent emergence of efficient zero-knowledge (ZK) proofs for general circuits, while efficient zero-knowledge proofs of algebraic statements have existed for decades, a natural challenge arose to combine algebraic and non-algebraic statements. Chase et al. (CRYPTO 2016) proposed an interactive ZK proof system for this cross-domain problem. As a use case they show that their system can be used to prove knowledge of a RSA/DSA signature on a message m with respect to a publicly known...

We introduce the notion of two-factor signatures (2FS), a generalization of a two-out-of-two threshold signature scheme in which one of the parties is a hardware token which can store a high-entropy secret, and the other party is a human who knows a low-entropy password. The security (unforgeability) property of 2FS requires that an external adversary corrupting either party (the token or the computer the human is using) cannot forge a signature. This primitive is useful in contexts like...

Algorithm substitution attack (ASA) on signatures should be treated seriously as the authentication services of numerous systems and applications rely on signature schemes and compromising them has a significant impact on the security of users. We present a somewhat alarming result in this regard: a highly efficient ASA on the Digital Signature Algorithm (DSA) and its implementation. Compared with the generic ASAs on signature schemes proposed in the literature, our attack provides fast...

The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the...

We discuss how to recover a secret bitstring given partial information obtained during a computation over that string, assuming the computation is a deterministic algorithm processing the secret bits sequentially. That abstract situation models certain types of side-channel attacks against discrete logarithm and RSA-based cryptosystems, where the adversary obtains information not on the secret exponent directly, but instead on the group or ring element that varies at each step of the...

Post Quantum Lattice-Based Cryptography (LBC) schemes are increasingly gaining attention in traditional and emerging security problems, such as encryption, digital signature, key exchange, homomorphic encryption etc, to address security needs of both short and long-lived devices — due to their foundational properties and ease of implementation. However, LBC schemes induce higher computational demand compared to classic schemes (e.g., DSA, ECDSA) for equivalent security guarantees, making...

Tight security is increasingly gaining importance in real-world cryptography, as it allows to choose cryptographic parameters in a way that is supported by a security proof, without the need to sacrifice efficiency by compensating the security loss of a reduction with larger parameters. However, for many important cryptographic primitives, including digital signatures and authenticated key exchange (AKE), we are still lacking constructions that are suitable for real-world deployment. We...

Aggregate signature (AS) allows non-interactively condensing multiple individual signatures into a compact one. Besides the faster verification, it is useful to reduce storage and bandwidth, and is especially attractive for blockchain and cryptocurrency. In this work, we first demonstrate the subtlety of achieving AS from general groups, by a concrete attack that actually works against the natural implementations of AS based on almost all the variants of DSA and Schnorr’s. Then, we show that...

In this paper, we optimize Bleichenbacher's statistical attack technique against (EC)DSA and other Schnorr-like signature schemes with biased or partially exposed nonces. Previous approaches to Bleichenbacher's attack suffered from very large memory consumption during the so-called "range reduction" phase. Using a carefully analyzed and highly parallelizable approach to this range reduction based on the Schroeppel-Shamir algorithm for knapsacks, we manage to overcome the memory barrier of...

This work introduces the concept of flexible signatures. In a flexible signature scheme, the verification algorithm quantifies the validity of a signature based on the number of computations performed such that the signature's validation (or confidence) level in $[0,1]$ improves as the algorithm performs more computations. Importantly, the definition of flexible signatures does not assume the resource restriction to be known in advance until the verification process is hard stopped by a...

Modular exponentiation represents a signicant workload for public key cryptosystems. Examples include not only the classical RSA, DSA, and DH algorithms, but also the partially homomorphic Paillier encryption. As a result, efficient software implementations of modular exponentiation are an important target for optimization. This paper studies methods for using Intel's forthcoming AVX512 Integer Fused Multiply Accumulate (AVX512IFMA) instructions in order to speed up modular (Montgomery)...

Double-authentication-preventing signatures (DAPS) are signatures designed with the aim that signing two messages with an identical first part (called address) but different second parts (called payload) allows to publicly extract the secret signing key from two such signatures. A prime application for DAPS is disincentivizing and/or penalizing the creation of two signatures on different payloads within the same address, such as penalizing double spending of transactions in Bitcoin by the...

The American signature standards DSA and ECDSA, as well as their Russian and Chinese counterparts GOST 34.10 and SM2, are of utmost importance in the current security landscape. The mentioned schemes are all rooted in the Elgamal signature scheme and use a hash function and a cyclic group as building blocks. Unfortunately, authoritative security guarantees for the schemes are still due: All existing positive results on their security use aggressive idealization approaches, like the generic...

ECDSA is a standard digital signature schemes that is widely used in TLS, Bitcoin and elsewhere. Unlike other schemes like RSA, Schnorr signatures and more, it is particularly hard to construct efficient threshold signature protocols for ECDSA (and DSA). As a result, the best-known protocols today for secure distributed ECDSA require running heavy zero-knowledge proofs and computing many large-modulus exponentiations for every signing operation. In this paper, we consider the specific case...

This paper reports on the number field sieve computation of a 768-bit prime field discrete logarithm, describes the different parameter optimizations and resulting algorithmic changes compared to the factorization of a 768-bit RSA modulus, and briefly discusses the cryptologic relevance of the result.

Several recent standards, including NIST SP 800- 56A and RFC 5114, advocate the use of “DSA” parameters for Diffie-Hellman key exchange. While it is possible to use such parameters securely, additional validation checks are necessary to prevent well-known and potentially devastating attacks. In this paper, we observe that many Diffie-Hellman implementations do not properly validate key exchange inputs. Combined with other protocol properties and implementation choices, this can radically...

We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software. Our chosen prime $p$ looks random, and $p-1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. ...

TLS and SSH are two of the most commonly used protocols for securing Internet traffic. Many of the implementations of these protocols rely on the cryptographic primitives provided in the OpenSSL library. In this work we disclose a vulnerability in OpenSSL, affecting all versions and forks (e.g. LibreSSL and BoringSSL) since roughly October 2005, which renders the implementation of the DSA signature scheme vulnerable to cache-based side-channel attacks. Exploiting the software defect, we...

Practical anonymous credential systems are generally built around sigma-protocol ZK proofs. This requires that credentials be based on specially formed signatures. Here we ask whether we can instead use a standard (say, RSA, or (EC)DSA) signature that includes formatting and hashing messages, as a credential, and still provide privacy. Existing techniques do not provide efficient solutions for proving knowledge of such a signature: On the one hand, ZK proofs based on garbled circuits...

Discrete-logarithm authentication protocols are known to present two interesting features: The first is that the prover's commitment, $x=g^r$, claims most of the prover's computational effort. The second is that $x$ does not depend on the challenge and can hence be computed in advance. Provers exploit this feature by pre-loading (or pre-computing) ready to use commitment pairs $r_i,x_i$. The $r_i$ can be derived from a common seed but storing each $x_i$ still requires 160 to 256 bits when...

We prove that a system of linear congruences of a particular form has at most a unique solution below a certain bound which can be computed efficiently. Using this result we develop attacks against the DSA schemes which, under some assumptions, can provide the secret key in the case where one or several signed messages are available.

While threshold signature schemes have been presented before, there has never been an optimal threshold signature algorithm for DSA. Due to the properties of DSA, it is far more difficult to create a threshold scheme for it than for other signature algorithms. In this paper, we present a breakthrough scheme that provides a threshold DSA algorithm that is efficient and optimal. We also present a compelling application to use our scheme: securing Bitcoin wallets. Bitcoin thefts are on the...

Side-channel attacks utilize information leakage in the implementation of an otherwise secure cryptographic algorithm to extract secret information. For example, adversaries can extract the secret key used in a cryptographic algorithm by observing cache-timing data. Threshold cryptography enables the division of private keys into shares, distributed among several nodes; the knowledge of a subset of shares does not leak information about the private key, thereby defending against memory...

In the ordinary security model for signature schemes, we consider an adversary that may forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In RKA for signature schemes, the adversary can also manipulate the signing key and obtain...

In 2011, B.B.Brumley and N.Tuveri found a remote timing attack on OpenSSL’s ECDSA implementation for binary curves. We will study if the title of their paper was indeed relevant (Remote Timing Attacks are Still Practical). We improved on their lattice attack using the Embedding Strategy that reduces the Closest Vector Problem to the Shortest Vector Problem so as to avoid using Babai’s procedures to solve the CVP and rely on the better experimental results of LLL. We will detail (along with...

Advanced modern processors support Single Instruction Multiple Data (SIMD) instructions (e.g. Intel-AVX, ARM-NEON) and a massive body of research on vector-parallel implementations of modular arithmetic, which are crucial components for modern public-key cryptography ranging from RSA, ElGamal, DSA and ECC, have been conducted. In this paper, we introduce a novel Double Operand Scanning (DOS) method to speed-up multi-precision squaring with non-redundant representations on SIMD...

PGP-based encryption systems use a network of key servers to share public keys. These key server operate on an add only basis, thus the data gives us access to PGP public keys from over 20 years of PGP usage. Analyzing this data allows searching for cryptographic weaknesses in large scale. I created a parser script that puts the raw cryptographic data of the PGP keys into a database. Doing this allows large scale searches for well-known vulnerabilities. DSA signatures with a duplicate $k$...

Montgomery modular multiplication constitutes the "arithmetic foundation" of modern public-key cryptography with applications ranging from RSA, DSA and Diffie-Hellman over elliptic curve schemes to pairing-based cryptosystems. The increased prevalence of SIMD-type instructions in commodity processors (e.g. Intel SSE, ARM NEON) has initiated a massive body of research on vector-parallel implementations of Montgomery modular multiplication. In this paper, we introduce the Cascade Operand...

In this work we explore new techniques for building short signatures from obfuscation. Our goals are twofold. First, we would like to achieve short signatures with adaptive security proofs. Second, we would like to build signatures with fast signing, ideally significantly faster than comparable signatures that are not based on obfuscation. The goal here is to create an "imbalanced" scheme where signing is fast at the expense of slower verification. We develop new methods for achieving short...

Modular multiplication of large integers is a performance-critical arithmetic operation of many public-key cryptosystems such as RSA, DSA, Diffie-Hellman (DH) and their elliptic curve-based variants ECDSA and ECDH. The computational cost of modular multiplication and related operations (e.g. exponentiation) poses a practical challenge to the widespread deployment of public-key cryptography, especially on embedded devices equipped with 8-bit processors (smart cards, wireless sensor nodes,...

Recently, researchers have proposed many non-interactive deniable authentication (NIDA) protocols. Most of them claim that their protocols possess full deniability. However, after reviewing, we found that they either cannot achieve full deniability, or suffer KCI or SKCI attack; moreover, lack efficiency, because they are mainly based on DLP, factoring problem, or bilinear pairings. Due to this observation, and that ECC provides the security equivalence to RSA and DSA by using much smaller...

Public key exchange protocol is identified as an important application in the field of public-key cryptography. Most of the existing public key exchange schemes are Diffie-Hellman (DH)-type, whose security is based on DH problems over different groups. Note that there exists Shor's polynomial-time algorithm to solve these DH problems when a quantum computer is available, we are therefore motivated to seek for a non-DH-type and quantum resistant key exchange protocol. To this end, we turn our...

Public key cryptographic algorithms are typically based on group exponentiation algorithms where the exponent is private. A collision attack is typically where an adversary seeks to determine whether two operations in an exponentiation have the same input. In this paper we extend this to an adversary who seeks to determine whether the output of one operation is used as the input to another. We describe implementations of these attacks to a 192-bit scalar multiplication over an elliptic curve...

AES-128, the NIST P-256 elliptic curve, DSA-3072, RSA-3072, and various higher-level protocols are frequently conjectured to provide a security level of 2^128. Extensive cryptanalysis of these primitives appears to have stabilized sufficiently to support such conjectures. In the literature on provable concrete security it is standard to define 2^b security as the nonexistence of high-probability attack algorithms taking time \le 2^b. However, this paper provides overwhelming evidence for...

Hummingbird-2 is one recent design of lightweight block ciphers targeting constraint devices, which not only enables a compact hardware implementation and ultra-low power consumption but also meets the stringent response time as specified in ISO18000-6C. In this paper, we present the first cryptanalytic result on the full version of this cipher using two pairs of related keys, i.e., four keys. We discover that the differential sequences for the last invocation of the round function can be...

We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for...

Finding efficient countermeasures for cryptosystems against fault attacks is challenged by a constant discovery of flaws in designs. Even elements, such as public keys, that do not seem critical must be protected. From the attacks against RSA, we develop a new attack of DLP-based cryptosystems, built in addition on a lattice analysis to recover DSA public keys from partially known nonces. Based on a realistic fault model, our attack only requires 16 faulty signatures to recover a 160-bit DSA...

Power Analysis has been widely studied since Kocher et al. presented in 1998 the initial Simple and Differential Power Analysis (SPA and DPA). Correlation Power Analysis (CPA) is nowadays one of the most powerful techniques which requires, as classical DPA, many execu- tion curves for recovering secrets. We introduce in this paper a technique in which we apply correlation analysis using only one execution power curve during an exponentiation to recover the whole secret exponent manipulated...

Certificateless cryptography eliminates the need of certificates in the PKI and solves the inherent key escrow problem in the ID-based cryptography. Recently, Du and Wen proposed a short certi¯cateless signature scheme without MapToPoint hash function, and the signature size is short enough with only half of the DSA signature. In this paper, after the detailing the formal of certificateless signature scheme, we show that the Du and Wen's short certificateless signature scheme is insecure...

In this paper, using the LLL reduction method and computing the integral points of two classes of conics, we develop attacks on DSA and ECDSA in case where the secret and the ephemeral key and their modular inverse are quite small or quite large.

The one-up problem is defined for any group and a function from the group to integers. An instance of problem consists of two points in the group. A solution consists of another point satisfying an equation involving the group and the function. The one-up problem must be hard for the security of (EC)DSA. Heuristic arguments are given for the independence of the discrete log and one-up problems. DSA and ECDSA are conjectured to be secure if the discrete log and one-up problems are hard...

We consider the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements $g_2, ..., g_k$ are fixed while $g_1$ is variable between multi-exponentiations but may repeat, and where the exponents are bounded (e.g., in a finite group). We present a new technique that entails two different ways of computing such a result. The first way applies to the first occurrence of any $g_1$ where, besides obtaining the actual result, we create a cache...

We introduce a message attack against DSA and show that the security of DSA is indeed reduced to the following problem, i.e., find $\theta\in \mathbb{Z}_q^*$ such that\\ \centerline{$z=(\hat g^{\theta} \,\mbox{mod}\, p)\, \mbox{mod}\, q $}\\ where $\mbox{Ord}_p(\hat g)=q$ and $z\in \mathbb{Z}_q^*$ is randomly chosen by the adversary. Compared with the common key-only attack, i.e., find $x\in \mathbb{Z}_q^*$ such that\\ \centerline{$ y= g^x \,\mbox{mod}\, p$}\\ the message attack is more...

The Merkle signature scheme (MSS) is an interesting alternative for well established signature schemes such as RSA, DSA, and ECDSA. The security of MSS only relies on the existence of cryptographically secure hash functions. MSS has a good chance of being quantum computer resistant. In this paper, we propose CMSS, a variant of MSS, with reduced private key size, key pair generation time, and signature generation time. We demonstrate that CMSS is competitive in practice by presenting a highly...

Raising of the fixed element of prime order group to arbitrary degree is the main operation specified by digital signature algorithms DSA, ECDSA. Fast exponentiation algorithms are proposed. Algorithms use number system with algebraic integer base (-2)^(1/4), 2^(1/4). Prime group order r can be factored as r = pi*pi1 in Euclidean ring Z[Sqrt[-2]], Z[Sqrt[2]] by Pollard and Schnorr algorithm. Farther factorization of prime quadratic divisor as pi = rho*rho1 in the ring Z[(-2)^(1/4)],...

Secure, anonymous and unobservable communication is becoming increasingly important due to the gradual erosion of privacy in many aspects of everyday life. This prompts the need for various anonymity- and privacy-enhancing techniques, e.g., group signatures, anonymous e-cash and secret handshakes. In this paper, we investigate an interesting and practical cryptographic construct Oblivious Signature-Based Envelopes (OS-BEs) recently introduced in [15]. OSBEs are very useful in anonymous...

We introduce the notion of tamper-evidence for digital signature generation in order to defend against attacks aimed at covertly leaking secret information held by corrupted network nodes. This is achieved by letting observers (which need not be trusted) verify the absence of covert channels by means of techniques we introduce herein. We call our signature schemes tamper-evident since any deviation from the protocol is immediately detectable. We demonstrate our technique for RSA-PSS and DSA...

We present an attack on DSA smart-cards which combines physical fault injection and lattice reduction techniques. This seems to be the first (publicly reported) physical experiment allowing to concretely pull-out DSA keys out of smart-cards. We employ a particular type of fault attack known as a glitch attack, which will be used to actively modify the DSA nonce k used for generating the signature: k will be tampered with so that a number of its least significant bytes will flip to zero. Then...

We deal with a divisor class halving algorithm on hyperelliptic curve cryptosystems (HECC), which can be used for scalar multiplication, instead of a doubling algorithm. It is not obvious how to construct a halving algorithm, due to the complicated addition formula of hyperelliptic curves. In this paper, we propose the first halving algorithm used for HECC of genus 2, which is as efficient as the previously known doubling algorithm. From the explicit formula of the doubling algorithm, we...

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC). However, it is expected that HECC still can be improved due to their mathematically rich structure. We consider here the application of degenerate divisors of HECC to scalar multiplication. We investigate the operations of the degenerate divisors in the Harley algorithm and the Cantor algorithm of genus 2. The timings of these...

Many variants of the ElGamal signature scheme have been proposed. The most famous is the DSA standard. If computing discrete logarithms is hard, then some of these schemes have been proven secure in an idealized model, either the random oracle or the generic group. We propose a generic but simple presentation of signature schemes with security based on the discrete logarithm. We show how they can be proven secure in idealized model, under which conditions. We conclude that none of the...

In this paper we present the first lattice attack on an authenticated key agreement protocol, which does not use a digital signature algorithm to produce the authentication. We present a two stage attack on MQV in which one party may recover the other party's static private key from partial knowledge of the nonces from several runs of the protocol. The first stage reduces the attack to a hidden number problem which is partially solved by considering a closest vector problem and using Babai's...

A new kind of attack on the non-repudiation property of digital signature schemes is presented. We introduce a notion of key-collisions, which may allow an attacker to claim that the message (presented to a judge) has been signed by someone else. We show how to compute key-collisions for the DSA and ECDSA signature schemes effectively. The main idea of these attacks has been inspired by the well-known notion of message-collisions, where an attacker claims that the signature presented at the...

The article describes an attack on OpenPGP format, which leads to disclosure of the private signature keys of the DSA and RSA algorithms. The OpenPGP format is used in a number of applications including PGP, GNU Privacy Guard and other programs specified on the list of products compatible with OpenPGP, which is available at http://www.pgpi.org/products. Therefore all these applications must undergo the same revision as the actual program PGP. The success of the attack was practically...

Proved here is the sufficiency of certain conditions to ensure the Elliptic Curve Digital Signature Algorithm (ECDSA) existentially unforgeable by adaptive chosen-message attacks. The sufficient conditions include (i) a uniformity property and collision-resistance for the underlying hash function, (ii) pseudo-randomness in the private key space for the ephemeral private key generator, (iii) generic treatment of the underlying group, and (iv) a further condition on how the ephemeral public...

In this paper we investigate the timed release of standard digital signatures, and demonstrate how to do it for RSA, Schnorr and DSA signatures. Such signatures, once released, cannot be distinguished from signatures of the same type obtained without a timed release, making it transparent to an observer of the end result. While previous work has allowed timed release of signatures, these have not been standard, but special-purpose signatures. Building on the recent work by Boneh and Naor...

This paper presents a new method called the robust software token for providing users with a stable and portable container in which a private key is stored and kept from adversaries, by simple software-only techniques. The proposed scheme is comparable with the related noble work such as a cryptographic camouflage scheme and a networked cryptographic device, but equipped with several advantages; (1) it uniquely supports both closed and open domains on public key infrastructures, (2) it...