nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Taming the Many EdDSAs

verfasst von : Konstantinos Chalkias, François Garillot, Valeria Nikolaenko

Erschienen in: Security Standardisation Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper analyses security of concrete instantiations of EdDSA by identifying exploitable inconsistencies between standardization recommendations and Ed25519 implementations. We mainly focus on current ambiguity regarding signature verification equations, binding and malleability guarantees, and incompatibilities between randomized batch and single verification. We give a formulation of Ed25519 signature scheme that achieves the highest level of security, explaining how each step of the algorithm links with the formal security properties. We develop optimizations to allow for more efficient secure implementations. Finally, we designed a set of edge-case test-vectors and run them by some of the most popular Ed25519 libraries. The results allowed to understand the security level of those implementations and showed that most libraries do not comply with the latest standardization recommendations. The methodology allows to test compatibility of different Ed25519 implementations which is of practical importance for consensus-driven applications.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Systematic Appraisal of Side Channel Evaluation Strategies

Nächstes Kapitel SoK: Comparison of the Security of Real World RSA Hash-and-Sign Signatures

Nur mit Berechtigung zugänglich

Cofactored means interpreting the verification equation modulo 8, which is a cofactor of the Curve25519. Any signature accepted by a “cofactorless” equation will be accepted by a “cofactored” equation, though the converse is false.

Note that a malicious signer can always bypass the correct signing execution by picking a random R and thus output two different signatures for the same message. Thus, EdDSA cannot guarantee the signature-uniqueness property.

The least significant three bits of the scalar are unset to allow using the same secret key in the DH-key agreement, where the EC point of another party is raised to the secret key. Raising to the exponent divisible by 8 there erases the small-subgroup component and defends against attacks that exploit the non-trivial co-factor of 8. The most significant bit is unset to make sure that the number is indeed the multiple of 8 and was not wrapped around the modulus. The second most significant bit is being set to prevent variable-time implementation of multiplication that first looks for the first most significant bit that is set. Note however that the secret key has 251 pseudo-random bits and is not uniformly random mod a 253-bits prime L, though this loss of a few bits of random bits is deemed acceptable.

The incompatibility in semantics between batch verification and cofactorless single verification was known in the form of cryptography community folklore [29], but not laid out precisely.

For much of the same reasons, cofactorless verification is incompatible with a method for fast (single) signature verification initially suggested by Antipa et al. [1] and recently made practical by Pornin [32], yielding speedups of about 15% on single signature verification. In essence, this method relies on mutualizing point doublings involved in checking a linear combination of the verification equation using a carefully-chosen scalar. As this check’s outcome should not depend on the ability of the scalar to clear small components in the equation, which is only achievable if the verification equation is cofactored.

Pull request to Libra: github.com/libra/libra/pull/907, merged Sep 11, 2019.

Pull request to Dalek: github.com/dalek-cryptography/ed25519-dalek/pull/99, merged Dec 5, 2019.

Antipa, A., Brown, D., Gallant, R., Lambert, R., Struik, R., Vanstone, S.: Accelerated Verification of ECDSA Signatures. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 307–318. Springer, Heidelberg (2006). https://doi.org/10.1007/11693383_21CrossRef

Aranha, D.F., Orlandi, C., Takahashi, A., Zaverucha, G.: Security of hedged Fiat–Shamir signatures under fault attacks. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part I. LNCS, vol. 12105, pp. 644–674. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_23CrossRef

Barry, N., Losa, G., Mazieres, D., McCaleb, J., Polu, S.: The Stellar Consensus Protocol (SCP). IETF, draft-mazieres-dinrg-scp-05 (2018)

Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_26CrossRef

Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.-Y.: High-speed high-security signatures. J Crypt. Eng. 2, 77–89 (2012) CrossRef

Bleichenbacher, D., Duong, T., Kasper, E., Nguyen, Q.: Project Wycheproof. https://github.com/google/wycheproof

Boneh, D., Shen, E., Waters, B.: Strongly unforgeable signatures based on computational Diffie-Hellman. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 229–240. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_15CrossRef

Brendel, J., Cremers, C., Jackson, D., Zhao, M.: The provable security of ed25519: theory and practice. IACR ePrint 2020, 823 (2020)

de Valence, H.: Zcash-flavored ed25519 for use in zebra. https://github.com/ZcashFoundation/ed25519-zebra, version 2.1.1

10.

de Valence, H.: Zip 125: Explicitly defining and modifying ed25519 validation rules (2020). https://github.com/zcash/zips/blob/master/zip-0215.rst

11.

Decker, C., Wattenhofer, R.: Bitcoin transaction malleability and MtGox. In: Kutyłowski, M., Vaidya, J. (eds.) ESORICS 2014, Part II. LNCS, vol. 8713, pp. 313–326. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11212-1_18CrossRef

12.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12CrossRef

13.

Fleischhacker, N., Jager, T., Schröder, D.: On tight security proofs for Schnorr signatures. J. Cryptol. 32(2), 566–599 (2019)MathSciNetCrossRef

14.

Goodman, L.M.: Tezos – a self-amending crypto-ledger. Technical report (2014)

15.

Novi Research Group. Ed25519-speccheck. https://github.com/novifinancial/ed25519-speccheck, commit 82d9301

16.

Hearn, M.: Corda: A distributed ledger. Corda Technical White Paper (2016)

17.

Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your Ps and Qs: Detection of widespread weak keys in network devices. In: USENIX Security Symposium (2012)

18.

IANIX: Things that use Ed25519. https://ianix.com/pub/ed25519-deployment.html

19.

de Valenc, H., Lovecruft, I.A.: ed25519-dalek: Fast and efficient rust implementation of ed25519 key generation, signing, and verification in rust. https://github.com/dalek-cryptography/ed25519-dalek, version 1.0.0-pre.4

20.

Josefsson, S., Liusvaara, I.: RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA), January 2017

21.

Langley, A., Hamburg, M., Turner, S.: RFC 7748: Elliptic Curves for Security, January 2016

22.

Libra blockchain. https://github.com/libra/libra

23.

LibSodium. https://github.com/jedisct1/libsodium, version 1.0.18

24.

Lim, C.H., Lee, P.J.: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 249–263. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052240CrossRef

25.

Lombrozo, E., Lau, J., Wuille, P.: Segregated Witness. Bitcoin Improvement Proposal 141. Created, 21 December 2015

26.

R. luigi1111, "fluffypony" Spagni. Disclosure of a major bug in CryptoNote based currencies (2017)

27.

Neven, G., Smart, N.P., Warinschi, B.: Hash function requirements for Schnorr signatures. J. Math. Cryptol. 3(1), 69–87 (2009)MathSciNetCrossRef

28.

Paillier, P., Vergnaud, D.: Discrete-log-based signatures may not be equivalent to discrete log. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_1CrossRef

29.

Perrin, T.: Xed25519. email to the Modern Cryptography mailing list (2016)

30.

Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_33CrossRef

31.

Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000). https://doi.org/10.1007/s001450010003CrossRefMATH

32.

Pornin, T.: Optimized lattice basis reduction in dimension 2, and fast schnorr and EdDSA signature verification. IACR ePrint 2020/454 (2020)

33.

Ref10: the ed25519 software from supercop benchmarking tool. https://bench.cr.yp.to/supercop.html. Accessed 24 Aug 2020

34.

Regenscheid, A.: NIST FIPS 186–5 (Draft), Digital Signature Standard (2019)

35.

Samwel, N., Batina, L.: Practical fault injection on deterministic signatures: the case of EdDSA. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2018. LNCS, vol. 10831, pp. 306–321. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89339-6_17CrossRef

36.

Samwel, N., Batina, L., Bertoni, G., Daemen, J., Susella, R.: Breaking Ed25519 in WolfSSL. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 1–20. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76953-0_1CrossRefMATH

37.

Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 688–689. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_68CrossRef

38.

Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161–174 (1991). https://doi.org/10.1007/BF00196725CrossRefMATH

39.

Seurin, Y.: On the exact security of Schnorr-type signatures in the random oracle model. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 554–571. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_33CrossRefMATH

40.

Weissbart, L., Picek, S., Batina, L.: One trace is all it takes: Machine learning-based side-channel attack on EdDSA. IACR ePrint 2019/358 (2019)

41.

Wuille, P.: Dealing with malleability. Bitcoin Improvement Proposal 62, (2015)

42.

Wuille, P.: Strict DER signatures. Bitcoin Improvement Proposal 66 (2015)

43.

Zhou, J., Gollmann, D.: Observations on non-repudiation. In: Kim, K., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 133–144. Springer, Heidelberg (1996). https://doi.org/10.1007/BFb0034842CrossRef

Titel: Taming the Many EdDSAs
verfasst von: Konstantinos Chalkias
François Garillot
Valeria Nikolaenko
Verlag: Springer International Publishing
Buch: Security Standardisation Research
Print ISBN: 978-3-030-64356-0

Electronic ISBN: 978-3-030-64357-7

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-64357-7_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner