On cofactored verification of EdDSA signatures

• Autorzy: Cinal Adrian , Sobolewski Oliwer

Identyfikatory

DOI

10.24425/ijet.2025.153592

• Języki publikacji: EN

Abstrakty

EN

EdDSA is a Schnorr signature scheme instantiated on top of Edwards curves, which admit fast, constant-time arithmetic, but suffer from the presence of a non-trivial cofactor, where the order of the group of points is a large prime times a small integer (4 or 8). Current standards permit for points present in the signature (commitment and/or public key) to have a component in the small-order subgroup of the group of points. This is done by sanctioning two variants of the signature verification equation and specifying precedence of one over the other. This last point, however, seems to be widely misunderstood and the two variants are given equal footing, allowing different “compliant” implementations to use different verification algorithms. This in turn lets malicious actors create signatures which are accepted by some parties, but rejected by others, threatening, e.g., consensus in a blockchain network setting. We add to the discussion on practical consequences of such discrepancies by formulating the consensus problem in the context of load-shedding attacks. We argue that the standards are in fact very specific about the set of valid signatures, despite lacking in explicitness and emphasis. We further show that two mainstream cryptographic libraries, namely, OpenSSL and CIRCL, accidentally (and in a manner not immediately apparent when inspecting the code) use the correct variant of the verification equation for one parameter set of EdDSA, but incorrect for another. In OpenSSL, this is traced back to careless copying of refcode. We conclude by proposing remedies to the chaotic status quo described.

Słowa kluczowe

EN

cryptographic standards; cryptographic implementations; consensus; cofactor

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 2
• Strony: 453--461
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Cinal Adrian

• NASK National Research Institute, Warsaw, Poland

autor

Sobolewski Oliwer

• NASK National Research Institute, Warsaw, Poland

Bibliografia

• [1] “Digital signature standard,” National Institute of Standards and Technology, Federal Information Processing Standards Publication 186-5, 2023. [Online]. Available: {https://csrc.nist.gov/pubs/fips/186-5/final}
• [2] S. Josefsson and I. Liusvaara, “Edwards-curve digital signature algorithm (EdDSA),” Internet Research Task Force, Informational 8032, 2017. [Online]. Available: {https://www.rfc-editor.org/rfc/rfc8032.txt}
• [3] Koe, K. M. Alonso, and S. Noether, “Zero to Monero: Second edition,” 2020. [Online]. Available: https://www.getmonero.org/library/ Zero-to-Monero-2-0-0.pdf
• [4] T. Pornin, “Point-halving and subgroup membership in twisted Edwards curves,” Cryptology ePrint Archive, Paper 2022/1164, 2022, https://eprint.iacr.org/2022/1164. [Online]. Available: https://eprint.iacr.org/2022/1164
• [5] “ZIP 215: Explicitly defining and modifying Ed25519 validation rules,” https://zips.z.cash/zip-0215.
• [6] K. Chalkias, F. Garillot, and V. Nikolaenko, “Taming the many Ed-DSAs,” Cryptology ePrint Archive, Paper 2020/1244, 2020.
• [7] M. Hamburg, “Decaf: Eliminating cofactors through point compression,” Cryptology ePrint Archive, Paper 2015/673, 2015. [Online]. Available: https://eprint.iacr.org/2015/673
• [8] ——, “Twisting Edwards curves with isogenies,” Cryptology ePrint Archive, Paper 2014/027, 2014. [Online]. Available: https://eprint.iacr.org/2014/027
• [9] H. M. Edwards, “A normal form for elliptic curves,” Bulletin of the American Mathematical Society, vol. 44, no. 3, pp. 393-422, 2007. [Online]. Available: https://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf
• [10] D. J. Bernstein and T. Lange, “Faster addition and doubling on elliptic curves,” in Advances in Cryptology - ASIACRYPT 2007, ser. Lecture Notes in Computer Science, vol. 4833. Springer, 2007, pp. 29-50.
• [11] D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters, “Twisted Edwards curves,” Cryptology ePrint Archive, Paper 2008/013, 2008.
• [12] H. Hisil, K. K.-H. Wong, G. Carter, and E. Dawson, “Twisted Edwards curves revisited,” in Advances in Cryptology - ASIACRYPT 2008, ser. Lecture Notes in Computer Science, vol. 5350. Springer, 2008, pp. 326-343.
• [13] 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, 2012.
• [14] J. R. Douceur, “The Sybil attack,” in International Workshop on Peer-to-Peer Systems, 2002. [Online]. Available: https://api.semanticscholar.org/CorpusID:5310675
• [15] M. Hamburg, “Ed448-Goldilocks, a new elliptic curve,” Cryptology ePrint Archive, Paper 2015/625, 2015. [Online]. Available: https://eprint.iacr.org/2015/625
• [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] P. R. Tiwari and M. Green, “Subverting cryptographic hardware used in blockchain consensus,” in Financial Crypto 2024. International Financial Cryptography Association, 2024.
• [18] I. Eyal and E. G. Sirer, “Majority is not enough: Bitcoin mining is vulnerable,” in Financial Crypto 2014. International Financial Cryptography Association, 2014.
• [19] L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem,” ACM Trans. Program. Lang. Syst., vol. 4, no. 3, p. 382-401, Jul. 1982. [Online]. Available: https://doi.org/10.1145/357172.357176
• [20] M. Pease, R. Shostak, and L. Lamport, “Reaching agreement in the presence of faults,” J. ACM, vol. 27, no. 2, p. 228-234, Apr. 1980. [Online]. Available: https://doi.org/10.1145/322186.322188
• [21] M. J. Fischer, N. A. Lynch, and M. Merritt, “Easy impossibility proofs for distributed consensus problems,” in Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, ser. PODC ’85. New York, NY, USA: Association for Computing Machinery, 1985, p. 59-70. [Online]. Available: https://doi.org/10.1145/323596.323602
• [22] D. Dolev and H. R. Strong, “Authenticated algorithms for byzantine agreement,” SIAM Journal on Computing, vol. 12, no. 4, pp. 656-666, 1983. [Online]. Available: https://doi.org/10.1137/0212045
• [23] F. Sheer Hardwick, A. Gioulis, R. Naeem Akram, and K. Markantonakis, “E-voting with blockchain: An e-voting protocol with decentralisation and voter privacy,” in 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CP-SCom) and IEEE Smart Data (SmartData), 2018, pp. 1561-1567.
• [24] Y.-X. Kho, S.-H. Heng, and J.-J. Chin, “A review of cryptographic electronic voting,” Symmetry, vol. 14, no. 5, 2022. [Online]. Available: https://www.mdpi.com/2073-8994/14/5/858
• [25] A. Antipa, D. Brown, R. Gallant, R. Lambert, R. Struik, and S. Vanstone, “Accelerated verification of ECDSA signatures,” in Selected Areas in Cryptography. Springer, 2005, pp. 307-318.
• [26] T. Pornin, “Optimized lattice basis reduction in dimension 2, and fast Schnorr and EdDSA signature verification,” Cryptology ePrint Archive, Paper 2020/454, 2020.
• [27] “Digital signature standard (initial public draft),” National Institute of Standards and Technology, Federal Information Processing Standards Publication 186-5, 2019. [Online]. Available: {https://csrc.nist.gov/pubs/fips/186-5/ipd}
• [28] “Public comments received on draft FIPS 186-5: Digital signature standards (DSS),” National Institute of Standards and Technology, Tech. Rep., 2021. [Online]. Available: {https://csrc.nist.gov/files/pubs/fips/186-5/ipd/docs/fips-186-5-draft-comments-received.pdf}
• [29] “ISO/IEC 9834-1:2012 - information technology — procedures for the operation of object identifier registration authorities — part 1: General procedures and top arcs of the international object identifier tree,” International Organization for Standardization, Standard, 2012.
• [30] 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.

Uwagi

1. Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).

2. This is not technically accurate, since RFC 8032 is an Informational RFC, not a standards-track document. We choose to treat it as such, however, since it is viewed as authoritative by software engineers providing the actual implementations, and it is the implementations, and the errors made therein, that we are most concerned with in this paper.