How EdDSA Vulnerability Exposed Private Keys in Popular Libraries

Table of Links

Abstract and I. Introduction

II. Edwards-Curve Digital Signature Algorithm

III. Double Public Key Signing Function Oracle Attack

IV. Countermeasures

V. Conclusion and References

Abstract—EdDSA is a standardised elliptic curve digital signature scheme introduced to overcome some of the issues prevalent in the more established ECDSA standard. Due to the EdDSA standard specifying that the EdDSA signature be deterministic, if the signing function were to be used as a public key signing oracle for the attacker, the unforgeability notion of security of the scheme can be broken. This paper describes an attack against some of the most popular EdDSA implementations, which results in an adversary recovering the private key used during signing. With this recovered secret key, an adversary can sign arbitrary messages that would be seen as valid by the EdDSA verification function. A list of libraries with vulnerable APIs at the time of publication is provided. Furthermore, this paper provides two suggestions for securing EdDSA signing APIs against this vulnerability while it additionally discusses failed attempts to solve the issue.

I. INTRODUCTION

Since it was first proposed independently in the late ’80s by Koblitz [1] and Miller [2], Elliptic Curve Cryptography (ECC) has become the preferred choice for constructing classical public-key cryptosystems. The critical advantage of ECC is its capability to construct public key cryptosystems with a smaller key size than its discrete logarithm-based counterparts. For example, the Digital Signature Algorithm (DSA) proposed by the National Institute of Standards and Technology (NIST) for their Digital Signature Standard (DSS) (attributed to Kravitz [3]) has an ECC counterpart, the Elliptic Curve Digital Signature Algorithm (ECDSA) [4], which boasts greater efficiency and smaller key sizes while achieving similar levels of security. However, ECDSA is not without its share of common pitfalls that implementations can suffer from. For example, key recovery attacks are enabled by poorly generated random values [5] and nonce re-usage [6]. Latticebased attacks, such as those using the Lenstra-Lenstra-Lov´asz (LLL) method [7], have also been used to recover information about private keys from weak ECDSA signatures successfully [8], [9].

With the evident problems in ECDSA implementations and a loss of trust in NIST after the Snowden revelations, the cryptography community shifted towards a new cryptosystem based on Curve25519 proposed by Bernstein in 2006 [10]. In 2012, Bernstein et al. [11] proposed using the Edwards variant of Curve25519 to construct a deterministic Schnorr-like [12] digital signature scheme. This scheme became the Edwardscurve Digitial Signature Algorithm (EdDSA). One of the main advantages of EdDSA over other ECC signature schemes is how the scalar multiplication of points on the curve can be implemented without branching and lookups depending on a secret value [11]. Due to its many advantages over ECDSA [13], EdDSA quickly became widely implemented and was eventually standardised in both RFC 8032 [14] and NIST’s own FIPS 186-5 [15].

This paper discloses an undiscovered vulnerability related to the implementation of EdDSA. This vulnerability is severe enough that adversaries can easily exploit it to extract the private key during the EdDSA signing process. This attack requires that an adversary use the signing function as an oracle that expects arbitrary public keys as inputs. While the majority of applications that use EdDSA are unlikely to expose signing functions to end users publicly or may mitigate the issue before signing invocation, there are some applications in which private and public keys are managed in different ways, exposing the surface to attack by adversaries. The details of this attack are given later in the paper, along with ways to mitigate the attack easily.

The rest of this paper is organised as follows: In the remainder of this section, various work related to EdDSA and its vulnerabilities is outlined, and the contributions of this paper are specified. In Section II provides background information on the EdDSA algorithm required for the rest of the paper. Section III describes the double public key signing function oracle attack and gives a list of libraries with EdDSA implementations vulnerable to the attack. In Section IV, possible countermeasures against the described vulnerability are given and Section V concludes the paper.

A. Related Work

Since the proposal of Ed25519 by Bernstein et al. [11] in 2012 and the subsequent generalisation of the algorithm into EdDSA [13], there has been a significant amount of work detailing various formal security notions of EdDSA as well as attacks to both the algorithm itself and implementation of the algorithm. Due to the fact that its construction is heavily based on the Schnorr signature scheme [12], security of the schemes proposed by Bernstein et al. in [11] and [16] is based on similar assumptions. More recently, Brendel et al. [17] gave a comprehensive security analysis of Ed25519 based on its implementation as per the RFC 8032 standard [14], in which they found that certain implementations guarantee stronger security than others. Furthermore, work by Chalkias et al. [18] was done to formalise EdDSA implementations under the strictest notions of security.

There have also been some high-profile attacks against EdDSA. In 2017, an issue arose in an implementation of Ed25519 used by the Monero crypto-currency, which allowed users to get around double-spending prevent ions. This issue was mitigated by checking the order of the key using full scalar multiplication and arose due to the unique way in which Monero used Ed25519 [19]. Samwel et al. [20] demonstrated that differential power analysis could be used on Ed25519’s underlying hash function SHA-512. In particular, their work targeted the WolfSSL implementation and required 4000 EM traces to be successful. In an extension to this work, Weissbart et al. [21] used machine learning techniques to reduce this attack to a single EM trace.

Another type of attack against EdDSA is a fault attack. Romallier and Pelissier [22] demonstrated that a single fault in the EdDSA signing process could be used to recover enough private key material for an attacker to sign arbitrary messages. Poddebniak et al. [23] also studied fault attacks against deterministic digital signature schemes such as EdDSA, formalising requirements for protocols to be vulnerable to these types of attacks. Approaching the same problem slightly differently, Cao et al. [24] constructed lattice-based attacks to recover private key information from deterministic digital signature schemes vulnerable to fault attacks.

This work presents an attack on the standard rather than an attack on implementation-specific details found in EdDSA software or hardware. More specifically, the standards fail to specify the format of key input into the EdDSA signing function. Due to the algorithmic details, if an adversary was able to use the signing function as an Oracle expecting arbitrary public key inputs, then it is possible for them to recover the full private key trivially. To the best of the authors’ knowledge, this issue was unreported until now.

B. Contributions

The main contributions of this paper are as follows:

• A new attack against the EdDSA standards RFC 8032 [14] and FIPS 186-5 DSS [15] is presented. It is shown that unless necessary precautions are taken, an adversary can perform full private key recovery if given Oracle access to the EdDSA signing function

• A list of potentially unsafe EdDSA libraries is given. At the time of writing, there are 45 libraries impacted by this vulnerability. Misuse of these libraries can result in private key exposure. Currently, 8 of the 45 impacted libraries have implemented fixes to the issues after notification.

• Finally, two countermeasures against this type of attack are given. These countermeasures are simple changes to the vulnerable EdDSA software implementations found in many libraries. Both changes require only a small amount of additional overhead in the signing function.