Two Proven Countermeasures to Oracle Attacks on EdDSA

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

IV. COUNTERMEASURES

Fortunately, due to the nature of the oracle attack, the majority of applications with dependencies on the libraries listed in Table II probably are safe due to not publicly exposing affected signing functions. That said, due to the nature of these libraries, a user can inadvertently expose the attack surface when building their application, as was the case with Monero in 2017 [19]. Therefore, it is recommended that the implementer of the EdDSA standard follow one of two methods to prevent this attack: Correctly storing the public key along with the secret key or re-deriving the public key from the secret key each time the signing function is invoked.

The double public key signing function oracle attack occurs primarily due to insecure APIs around the signing function of the deterministic signature scheme. For example, the Ed25519 signing function taken from the OpenGNB library shown in Listing 1 has two separate arguments for the public and private keys. If an application using this library exposes this API publicly or mishandles the management of the keys, it could expose itself to the attack. The solution to this is to redesign the API to ensure that the secret and public keys pair are always tied together. It is common practice in many libraries to only accept a secret key in the signing function. For example, the Ed25519 signing function taken from the Libsodium library shown in Listing 2 accepts only the signature, message, and secret key as an argument. However, the public key is still required by the signing algorithm. There are two solutions to this.

A. Correct Key Storage

The simplest solution is to ensure the public and private keys are stored together and accept them as a single argument to the signing function. This is also slightly more efficient computationally than the other option. Both the public and private keys for EdDSA are 32 or 57-byte for Ed25519 and Ed448, respectively. The solution found in the majority of libraries is to generate the public-private keypair and store the secret key as a 64-byte string. The first 32 bytes are the private key, with the remaining 32 bytes being the public key. The main downside of this is the private key is now 64 or 114 bytes for Ed25519 and Ed448. However, this increased storage space should be acceptable in all but the most extreme cases. [ht]

In Listing 3, an example of safe key generation and storage is given based on the Libsodium Ed25519 implementation. In this example, the seed byte array is stored as the first 32 bytes of the private key sk. This means that the users of the library can retrieve the initial random seed used to generate the public and private key pair. When invoking the signing function, the secret key would be derived by taking the first 32 bytes and hashing them with the SHA-512 hash function, and the public key would be the remaining 32 bytes.

B. Public Key Re-derivation

The other option is to receive the public key on every invoke of the signing function. Obviously, this consumes significantly more CPU cycles in the long term than storing the public key alongside the private key, as suggested in Section IV-A. However, the additional space requirements are no longer necessary, which may be more suitable for use cases with extreme memory restrictions. This solution is far less common to see in software implementations of EdDSA.

In Listing 4, an example of an Ed25519 signature function with key re-derivation is given. In this example, the secret key sk given is expected to be a 32-byte seed array much like that from Listing 3. The secret key is then regenerated using the SHA-512 hash function, which is passed to the public key generation function, which performs the point multiplication. The rest of the Ed25519 signing function would then be implemented as per the standard.

V. CONCLUSION

In this work, an attack against the EdDSA standard is presented. Due to the deterministic nature of EdDSA signatures, an adversary with access to the signing function that accepts arbitrary public keys can recover the secret signing value by submitting as little as two different public keys. The adversary can sign arbitrary messages using this signing value, breaking the unforgeability security notion of digital signature schemes. The attack can occur primarily from software implementation APIs presenting an adversary’s opportunity to submit multiple public keys to the signing function, creating different signatures for the same message and private key. This attack presents a real threat if applications expose these APIs publicly or fail to manage public-private key pairs correctly. A list of libraries that implement the Ed25519 standard and are vulnerable to this attack is given. Additionally, two countermeasures are proposed to prevent the attack.

REFERENCES

[1] N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, pp. 203–209, 1987.

[2] V. S. Miller, “Use of elliptic curves in cryptography,” in Advances in Cryptology — CRYPTO ’85 Proceedings, H. C. Williams, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1986, pp. 417–426.

[3] D. W. Kravitz, “Digital signature algorithm,” May 1993, U.S. Patent US5231668A.

[4] D. Johnson, A. Menezes, and S. Vanstone, “The elliptic curve digital signature algorithm (ecdsa),” International Journal of Information Security, vol. 1, no. 1, pp. 36–63, Aug 2001. [Online]. Available: https://doi.org/10.1007/s102070100002

[5] P. Q. Nguyen and I. E. Shparlinski, “The insecurity of the elliptic curve digital signature algorithm with partially known nonces,” Designs, Codes and Cryptography, vol. 30, no. 2, pp. 201–217, Sep 2003. [Online]. Available: https://doi.org/10.1023/A:1025436905711

[6] M. Brengel and C. Rossow, “Identifying key leakage of bitcoin users,” in Research in Attacks, Intrusions, and Defenses, M. Bailey, T. Holz, M. Stamatogiannakis, and S. Ioannidis, Eds. Cham: Springer International Publishing, 2018, pp. 623–643.

[7] A. K. Lenstra, H. W. Lenstra, and L. Lov´asz, “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol. 261, no. 4, pp. 515–534, Dec 1982. [Online]. Available: https://doi.org/10.1007/BF01457454

[8] D. Poulakis, “Some lattice attacks on dsa and ecdsa,” Applicable Algebra in Engineering, Communication and Computing, vol. 22, no. 5, pp. 347–358, Dec 2011. [Online]. Available: https://doi.org/10.1007/s00200-011-0154-4

[9] J. Breitner and N. Heninger, “Biased nonce sense: Lattice attacks against weak ecdsa signatures in cryptocurrencies,” in Financial Cryptography and Data Security, I. Goldberg and T. Moore, Eds. Cham: Springer International Publishing, 2019, pp. 3–20.

[10] D. J. Bernstein, “Curve25519: New diffie-hellman speed records,” in Public Key Cryptography - PKC 2006, M. Yung, Y. Dodis, A. Kiayias, and T. Malkin, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 207–228.

[11] D. J. Bernstein, N. Duif, T. Lange, P. Schwabe, and B.-Y. Yang, “High-speed high-security signatures,” Journal of Cryptographic Engineering, vol. 2, no. 2, pp. 77–89, Sep 2012. [Online]. Available: https://doi.org/10.1007/s13389-012-0027-1

[12] C. P. Schnorr, “Efficient identification and signatures for smart cards,” in Advances in Cryptology — CRYPTO’ 89 Proceedings, G. Brassard, Ed. New York, NY: Springer New York, 1990, pp. 239–252.

[13] D. J. Bernstein, S. Josefsson, T. Lange, P. Schwabe, and B.-Y. Yang, “Eddsa for more curves,” Cryptology ePrint Archive, Paper 2015/677, 2015. [Online]. Available: https://eprint.iacr.org/2015/677

[14] S. Josefsson and I. Liusvaara, “Edwards-curve digital signature algorithm (EdDSA),” Tech. Rep., jan 2017.

[15] D. Moody, “Digital signature standard (DSS),” Tech. Rep., 2023.

[16] D. J. Bernstein, S. Josefsson, T. Lange, P. Schwabe, and B.-Y. Yang, “Eddsa for more curves,” Cryptology ePrint Archive, Paper 2015/677, 2015. [Online]. Available: https://eprint.iacr.org/2015/677

[17] J. Brendel, C. Cremers, D. Jackson, and M. Zhao, “The provable security of ed25519: Theory and practice,” in 2021 IEEE Symposium on Security and Privacy (SP), 2021, pp. 1659–1676.

[18] K. Chalkias, F. Garillot, and V. Nikolaenko, “Taming the many eddsas,” in Security Standardisation Research, T. van der Merwe, C. Mitchell, and M. Mehrnezhad, Eds. Cham: Springer International Publishing, 2020, pp. 67–90.

[19] luigi1111 and Riccardo ”fluffypony” Spagni, “Disclosure of a major bug in cryptonote based currencies,” May 2017. [Online]. Available: https://www.getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-

[20] N. Samwel, L. Batina, G. Bertoni, J. Daemen, and R. Susella, “Breaking ed25519 in wolfssl,” in Topics in Cryptology – CT-RSA 2018, N. P. Smart, Ed. Cham: Springer International Publishing, 2018, pp. 1–20.

[21] L. Weissbart, S. Picek, and L. Batina, “One trace is all it takes: Machine learning-based side-channel attack on eddsa,” in Security, Privacy, and Applied Cryptography Engineering, S. Bhasin, A. Mendelson, and M. Nandi, Eds. Cham: Springer International Publishing, 2019, pp. 86–105.

[22] Y. Romailler and S. Pelissier, “Practical fault attack against the ed25519 and eddsa signature schemes,” in 2017 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), 2017, pp. 17–24.

[23] D. Poddebniak, J. Somorovsky, S. Schinzel, M. Lochter, and P. R ¨osler, “Attacking deterministic signature schemes using fault attacks,” in 2018 IEEE European Symposium on Security and Privacy (EuroS&P), 2018, pp. 338–352. [

24] W. Cao, H. Shi, H. Chen, J. Chen, L. Fan, and W. Wu, “Lattice-based fault attacks on deterministic signature schemes of ecdsa and eddsa,” in Topics in Cryptology – CT-RSA 2022, S. D. Galbraith, Ed. Cham: Springer International Publishing, 2022, pp. 169–195.

[25] A. Langley, M. Hamburg, and S. Turner, “Elliptic curves for security,” Tech. Rep., jan 2016.

[26] IANIX, “Things that use Ed25519,” Jun. 2023. [Online]. Available: https://ianix.com/pub/ed25519-deployment.html