Understanding the Security of (EC)DSA Signatures

How Provably Secure are (EC)DSA Signatures? Eike Kiltz, PKC 2021

History of Digital Signature Algorithm (DSA) 1982: the U.S government solicited proposals for a public key signature standard 1984: ElGamal Signatures [ElGamal84] 1990: Schnorr Signatures: various improvements [Schnorr90], U.S. Patent 4,995,082 1991: NIST proposes DSS=DSA. U.S. Patent 5,231,668 by David W. Kravitz (NSA). 1992: Panel discussion at EUROCRYPT 1992: trapdoor in DSS? [DLLMORS92] 1992: Public comments [RHAL92, ] 1992: NIST p blis s R spons o Comm n s on NIST P opos Digi al Signa S an a , CRYPTO 1992 [SK92] 1994: DSS standard FIPS 186. Includes 1024-bit moduli. First digital signature recognized by any government 1992: Vanstone proposes EC variant of DSA 1995: IEEE P1363 working proposes current form of ECDSA 1998: ISO 14888-3: ECDSA 1999: ANSI X9.62: ECDSA 2000: IEEE 1363-200: ECDSA 2000: FIPS 186-2 includes ECDSA: 15 elliptic curves, chosen by Jerry Solinas (NSA), including NIST P-256 2019: FIPS 186-5 (draft) forbids signing with DSA (verify still ok), includes EdDSA Collected from: [Bernstein14], Wikipedia, various

Who uses (EC)DSA in 2021?* kiltz@home % openssl version LibreSSL 2.8.3 kiltz@home % openssl s_client connect wikipedia.org:443 CONNECTED(00000005) [ ] SSL-Session: Protocol : TLSv1.2 Cipher : ECDHE-ECDSA-AES256-GCM-SHA384 [ ] SSL: 20% ECDSA, 80% RSA (https://notary.icsi.berkeley.edu/, July 2018) TLS: 25% ECDSA, 75% RSA (https://telemetry.mozilla.org/, May 2021) 99% support ecdsa_secp256r1_sha256 (https://tlsfingerprint.io/sig-algs, May 2021) Certificates: 7% ECDSA (https://censys.io/certificates, May 2021) Car2X communication (IEEE 1609-2): 100% ECDSA? Mainstream cryptocurrencies: 100% ECDSA Threshold signature schemes [C M20,CLST21, YCX21, ] Multi-party signing protocols [Lin ll17, ] Adaptor signatures DSA: ??? *thanks to Nadia Henniger, Dan Brown, Juraj Somorovsky, Robert Merget, Tim G neysu, Peter Schwabe

Generic DSA: GenDSA[?, H, f] [Brown02] 1. (?, ) = g o p o p im o p, <g>=? 2. H: {0,1}* p hash function (SHA) 3. f: ? p conversion function DSA: ? = subgroup of ?q, f(R) := R mod p ECDSA: ? = EC over ?, x-coordinate of R=(Rx,Ry) ? ? f(R) := Rx mod p Gen: x p; X = gx pk = X; sk = x Return (pk, sk) Sign(sk,m): p*; R = gr t = f(R); h = H(m) s = (h + x) / r mod p Return ? = (s,t) p p Ver(pk, m, ? ? = (s,t)): h = H(m) R = (gh Xt)1/s = (R ) Return 1 iff = + set containment checks for s, t, R' Special case of ElGamal signatures[ElGamal84] Deterministic ECDSA (RFC 6979): p r := H(sk,m) Country-specific variants Russian (EC)GOST (RFC 7091) Chinese SM2 (ISO/IEC 11889:2015) German (EC)GDSA (ISO/IEC 15946-2)

Security UF-CMA: s Strong UnForgeability against Chosen Message Attack pk mi (1 i q) ?i m*, ?* (m*, ?*) (mi,?i) m* mi UF-1CMA: UnForgeability against 1-per-message Chosen Message Attack Signing queries mi distinct Equivalent to UF-NMA for deterministic signing UF-NMA: UnForgeability against No Message Attack (aka Key Only Attack) No signing queries allowed

Provable Security P ovabl s i y = s i y o A impli s s i y o B (A B) Reduction A B Crypto can be secure in practice, without being provably secure Crypto can be insecure in practice, even being provably secure Talk will not cover SCA: ECDSA is very prone to SCA! Ev y na al impl m n a ion o ECDSA mak s avy s o s b an s an s a ay in i s [Bernstein14] Talk will no ov ba an omn ss (Playstation 3 Ha k 2010) o an omn ss l akag

(EC)DSA important but little security research #eprint papersHow Provably Secure are 12 10 6 (EC)DSA Signatures? 8 4 2 0 2012 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2013 2014 2015 2016 2017 2018 2019 2020 Provable security SCA SCA/cryptocurrencies Why? Conversion function f(R) := R mod q, f(R) := Rx mod qis ugly!

This talk: provable security of GenDSA[?, H, f] 1. Modeling H and f as random oracle [Brickell96, PV96, BPVY00] 2. Modeling group ? as generic group [Brown02] 3. Modeling H as random oracle [Brown05, FKP17, HK21] 4. Modeling f using bijective random oracle [FKP16] Other results related to (EC)DSA security Brown [Brown02, Brown05b, Brown08], Vaudenay [Vau96, Vau03], Howgrave Graham and Smart [HS01], Nguyen and Shparlinski [NS03], Leadbitter et al. [LPS04], Medwed and Oswald [MO09], Garc a et al. [GBY16], Genkin al. [ PP+16],

1. GenDSA[?, f, H] in Random Oracle Model (f = random oracle, H = random oracle) f: ? p conversion function H: {0,1}* p hash function Theorem [Brickell96, PV96, BPVY00] 1. f = programmable random oracle 2. H = programmable random oracle 3. ? = group with hard DLOG GenDSA[? ?, f, H] is UF-NMA secure Sign(sk=x,m): Zp; R = gr t = f(R) h = H(m) s = (h + tx) / r Return ? = (s,t) Proof based on Forking Lemma But: f not random oracle, invertible in ECDSA! [Brickell96]: variant DSA-I w pla by as n ion O va ian : DSA-II s s h=H(m,t) h=H(m,t) [PV96]

This talk: provable security of GenDSA 1. Modeling H and f as random oracle [Brickell96, PV96, BPVY00] 2. Modeling group ? as generic group [Brown02] 3. Modeling H as random oracle [Brown05, FKP17, HK21] 4. Modeling f using bijective random oracle [FKP16]

2. GenDSA[?, f, H] in Generic Group Model What does that mean for GenDSA?? Theorem [Brown02] 1. f = almost invertible, almost bijective 2. H = one-way, second-preimage resistant, zero-finder-resistant 3. ? = generic group GenDSA[? ?, f, H] is strongly UF-CMA f: ? p conversion function H: {0,1}* p hash function ? = group of prime order p Applicable to ECDSA only (f in DSA not almost invertible) But: ECDSA is malleable not strongly UF-CMA [SPMLS02] 1. ? elliptic curve: R=(Rx,Ry) ? R-1 = (Rx,-Ry) 2. f(R) = Rx (x-coordinate of EC) f(R) = f(R-1) 3. (s,t) signature on m Sign(sk=x,m): p; R = gr t = f(R) h = H(m) s = (h + tx) / r Return ? = (s,t) (-s,t) signature on m [SPMLS02]: W a go s w ong is a q a y o model. The proof is correct but the underlying model is flawed, sin i isallows p o ion o mall abl signa s

S o ps Generic Group Model [Shoup97] ?[?] = cryptographic experiment defined over group ? (e.g., DLOG[? ?]) GGM idea: adversary can only exploit group structure to solve ?[?] GGM implementation: access to ? restricted to random encoding 1. Chose random injective encoding ?: ? ?, where ? {0,1}* is set 2. ?[?] executed, each A ? substituted by ?(A) ? 3. A v sa y s a ss o ? only with oracles DLOG[? ?] in GGM: Pick random ?: ? ? Pi k x p ?(g), ?(gX) enc1, enc2 ? enc ? max: Q queries enc= ?(?-1(enc1) ?-1(enc2) ?) x Pr?[A v solv s DLO in M] Q2/p

GGM for non-algebraic functions [FKP16] f? Experiment ?[?,f?] involv s non-alg b ai n ion f?: ? p E.g. ECDSA: ? = EC, f?(R)=Rx How to model fGG: ? p in GGM? f?(R) only defined if R is point on EC over ?q f?(R) undefined for R ? ? p f? ?-1 f? ? encoding ? fGG = ?? ? 1. Use fGG = f? ?-1 (fGG(R) = f?(?-1(R)) ) ? fGG(R) reveals information on ?-1(R) ? Not useful in GGM! 2. Assume ? ? and define fGG(R):=f?(R) ? Considers implicitly ?[?,f] with f = f? ? Models f = f? ? as idealized object GGM proof can exploit entropy of fGG(R) E.g., for fGG(R) = Rx: fGG(R) fGG(R-1) E.g., f(R) := half_bits(R) acts like RO!

Summary: GenDSA in Generic Group Model Theorem [Brown02] 1. f = almost invertible, almost bijective 2. H = one-way, second-preimage resistant, zero-finder-resistant 3. ? = generic group: ? ?, fGG(R) := f?(R) GenDSA[? ?, f, H] is sUF-CMA secure My opinion: don t mix GGM with non-algebraic operations ECDSA proof: formally correct but meaningless Threshold ECDSA: similar problems [C M20,CLST21, ] Other crypto: similar problems [Smart01, NSW09, KP10, ] Us Ma s M! GGM vs ROM

This talk: provable security of GenDSA 1. Modeling H and f as random oracle [Brickell96, PV96, BPVY00] 2. Modeling group ? as generic group [Brown02] 3. Modeling H as random oracle [Brown05, FKP17, HK21] 4. Modeling f using bijective random oracle [FKP16]

3. GenDSA in Random Oracle Model [Brown02,FKP17] (f = arbitray, H = random oracle) UF-1CMA Deterministic GenDSA ? Semi- DLOG Th 1 Th 3 DLOG UF-NMA UF-CMA Semi-DLO [ ]: iv n pk, o g on m wi H(m)=1 Input: (g,X) Output: (s , ): t = f( (g Xt)s ) Ver(pk, m, ? ? = (s,t)): Return 1 iff t = f((gH(m)Xt)1/s) Theorem 1 Theorem 2 f = arbitrary H = programmable random oracle ? = group with hard Semi-DLOG GenDSA[? ?, f, H] is UF-NMA secure 1. 2. 3. f = arbitrary H = programmable random oracle GenDSA[?, f, H] = UF-NMA GenDSA[? ?, f, H] is UF-1CMA secure 1. 2. 3.

Proof UF-NMA UF-1CMA (Theorem 2) pk= gx pk= gx B/UF-NMAH UF-NMAH A/UF-1CMAH m ?m : simulate ?m without sk=x distinct m Forgery (m*, ?*) valid for UF-NMAH if H(m*) = H (m*) was no p og amm reduction loses #signing queries m m Program H vs. q y H H(m) H (m) (m*, ?*) (m*, ?*) : Simulate ? ?m without sk=x: Pick random am, bm Rm := gbm Xam = gbm + am x tm H(m) := bmtm / am sm = ( H(m) + tm x ) / rm = ( bm tm / am + tm x ) / (bm + am x) = tm / am ( bm + am x) / (bm + am x) = tm / am ?m = (sm, tm) Sign(sk=x, m): [ rm = bm + am x ] p; R = gr t = f(R) = f(Rm) RO p og amming s = (H(m) + t x) / r independent of x! valid signature on m ? = (s,t)

Can we prove UF-NMA UF-CMA? Theorem 3 [HK21] 1. f = non-programmable random oracle 2. H = programmable random oracle 3. G = group with hard DLOG Then there is no algebraic reduction UF-NMA UF-CMA UF-1CMA Det. GenDSA Th 3 UF-CMA UF-NMA Meta reduction g, gx g, gx g, gx m h=H(m) Reduction B B = algebraic m ?1 = (s1,t1) r1 = a1+x b1 = (h + x t1 ) / s1 extract x (whp) m r2 = a2+x b2 = (h + x t2 ) / s2 x ?2 = (s2,t2)

Summary: GenDSA in Random Oracle Model (f = arbitray, H = random oracle) [PV05]: no algebraic reduction DLOG UF-NMA in standard model UF-1CMA Det. GenDSA ? Th 1 Semi- DLOG Th 3 DLOG UF-NMA UF-CMA works for all conversion functions f has to exploit property of f Take away messages: Use Deterministic ECDSA (RFC 6979) if you can In some applications not possible (threshold signing, etc) Wanna break DSA/ECDSA? Two signatures on same message + special properties of f Results extend to ElGamal signa s (SM2, HOST, EC DSA, )

This talk: provable security of GenDSA 1. Modeling H and f as random oracle [Brickell96, PV96, BPVY00] 2. Modeling group ? as generic group [Brown02] 3. Modeling H as random oracle [Brown05, FKP17, HK21] 4. Modeling f using bijective random oracle [FKP16]

4. GenDSA in Bijective Random Oracle Model [FKP16] (f = modeled with Bijective Random Oracle) Problem with modeling conversion function f: ? p as RO in DSA-I: f is invertible : model f to be invertible & destroy algebraic structure f = ? ? ? ? ? ? ? {0,1}L [0, 2L-1] p Example ECDSA: ?: ? {0,1}L ?: {0,1}L [0, 2L-1] ?: [0, 2L-1] p x ?(R) = field_to_string(Rx) Bijective Random Oracle (BRO) ?(T) = string_to_integer(T) mod p ?(x) y BRO ? ?-1(y)

GenDSA in BRO (f = ???) [FKP16] Th 1 Th 2 DLOG UF-NMA UF-CMA ? ?-division-resistance for H: Given: random ?, ? Find: m, m : H(m) ?(?) = H(m ) ?(? ) (mod p) Theorem 1 1. Theorem 2 1. f = ? ? ? , ? = semi-injective, ? = programmable BRO 2. H = collision resistant 3. GenDSA[? ?, f, H] = UF-NMA GenDSA[? ?, f, H] is UF-CMA f = ? ? ?, ? = semi-injective*, ? = programmable BRO H = ?-division-resistant ? = group with hard DLOG GenDSA[?, f, H] is UF-NMA 2. 3. *semi-injective: ? either 2-1 or injective

Proof of DLOG UF-NMA (Th 1) pk= gx UF-NMA A/UF-NMA ? ?=?(?) forward queries ? backward queries ?=?-1(?) (m*, ?*=(s*,t*)) Forgery: ?* = ?(gr*) ?* = ?(?*) t* = ?(?*) DLOG ?* from forward query ?* = ?(?*) r* = (H(m*) + xt*)/s* t* = f(gr*)

Proof of DLOG UF-NMA pk= gx Simplified UF-NMA A ? ?* ? ?=?-1(?) (m*, ?*=(s*,t*)) Forgery: ?* = ?(gr*) ?* = ?(?*) t* = ?(?*) DLOG ?* from forward query ?(?*) UF-CMA Simplified UF-CMA: single ?* from experiment (loss: #queries to ?) r* = (H(m*) + xt*)/s* t* = f(gr*)

Proof of DLOG UF-NMA pk= gx pk= gx Rewinding A Simplified UF-NMA A ? ?* ?* (m , ? =(s , )) (m*, ?*=(s*,t*)) Forgery: ?* = ?(gr*) ?* = ?(?*) t* = ?(?*) DLOG ?* from forward query ?(?*) UF-CMA Simplified UF-CMA: single ?* from experiment (loss: #queries to ?) Forking Lemma: solve for x unless H not ?-division-resistant r* = (H(m*) + xt*)/s* t* = f(gr*) = (H(m ) + xt )/s = (g )

Summary: Bijective Random Oracle (BRO) Model (f = modeled with Bijective Random Oracle) Th 1 Th 2 DLOG UF-CMA UF-NMA Take away messages: Model f = ? ? ?, where ? = programmable BRO More realistic than f = RO, but possibly too strong abstraction of f Best known provable security guarantee for full UF-CMA security of (EC)DSA

Conclusions: How provably secure is GenDSA[?, f, H]? Security result 1. H, f = RO UF-CMA security from DLOG 2. ? = generic group UF-CMA security 3. H = RO UF-1CMA security from Semi-DLOG[f] 4. f = ? ? ?, ? = BRO UF-CMA security from DLOG Modelling Security Open problems Ad 2.: GGM with non-algebraic operations ? Ad 3.: hardness of Semi-DLOG[f] ? Ad 4.: more realistic modeling of f ? Tightness ?

Con l sions: Ra s .. EdDSA (RFC 8032, FIPS 186-5 draft) [BDLSY12] EdDSA (ECDSA wi v E 25519) EdDSA (Schnorr with curve Ed25519 + deterministic signing) EdDSA > ECDSA: simpli i y, i i n y, s i y, v sali y, S no s U.S. Patent 4,995,082 expired Used in TLS 1.3, SSH, WhatsApp/Signal, Tor, Zcash, n P , Op nBSD, BLS [BLS03] Full Domain Hash signature over Bilinear Maps Used in version 2 of Etherium, Algorand, Chia Even more versatile than EdDSA Post-Quantum security! Dilithium [DKLLSSS18] Or any other round-3 NIST PQC signature

Thank you RUHR-UNIVERSIT T BOCHUM Horst-G rtz-Institut f r IT-Sicherheit Exzellenzcluster CASA www.casa.rub.de ID 2/150 | Universit tsstr. 150 | 44780 Bochum | Germany www.casa.rub.de | www.hgi.rub.de www.hgi.rub.de

References A-F [Bernstein14] Bernstein: How to design an elliptic-curve signature system. https://blog.cr.yp.to/20140323-ecdsa.html [BDLSY12] Bernstein, Duif, Lange, Schwabe, Yang: High-speed high-security signatures. Journal of Cryptographic Engineering 2012 [Brickel96] Brickell: Invited lecture given at Crypto 1996 [BPVY00] Brickell, Pointcheval, Vaudenay, Yung: Design validations for discrete logarithm based signature schemes. PKC 2000. [Brown02] Brown: Generic groups, collision resistance, and ECDSA. Cryptology ePrint Archive, Report 2002/026. [Brown05] Brown: On the provable security of ECDSA. In: Advances in Elliptic Curve Cryptography, Cambridge University Press (2005) [Brown08] Brown: One-up problem for (EC)DSA. Cryptology ePrint Archive, Report 2008/286, 2008. [CGGM20] Canetti, Gennaro, Goldfeder, Makriyannisk: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts, CCS 2020 [CLST21] Castagnos, Catalano, Laguillaumie, Savasta, Tucker: Bandwidth-efficient threshold EC-DSA revisited: Online/Offline Extensions, Identifiable Aborts, Proactivity and Adaptive Security, eprint 2021/291 [DKLLSSS18] Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, Stehle: CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. CHES 2018. [DLLMORS92] Desmedt, Landrock, Lenstra, McCurley, Odlyzko, Rueppel, Smid: The EUROCRPY '92 Controversial Issue: Trapdoor Primes and Moduli (Panel) [DD12] Dolmatov, V., Degtyarev, A.: GOST R 34.10-2012: Digital Signature Algorithm. RFC 7091 [ElGamal84] ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms. CRYPTO 1984. [Fersch18] Fersch: The Provable Security of Elgamal-type Signature Schemes. PhD Thesis, 2018. [FKP16] Fersch, Kiltz, Poettering: On the Provable Security of (EC)DSA Signatures. CCS 2016. [FKP17] Fersch, Kiltz, Poettering: On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC 2017

References G-Z [ BY16] a a, B ml y, Ya om: Mak s DSA signing xpon n ia ions ally a ons an - im . ACM CCS 2016 [ PPTY16] nkin, Pa manov, Pipman, T om , Ya om. ECDSA k y x a ion om mobil vi s via nonin siv p ysi al si ann ls. CCS 2016 [HS01] Howg av - a am, Sma : La i a a ks on igi al signa s m s. D s. Co s C yp og ap y, 23(3):283 290, 2001 [ISO13] ISO/IEC 11889:2015: In o ma ion nology - T s Pla o m Mo l lib a y [Lin ll17] Lin ll: Fas S Two-Pa y ECDSA Signing, CRYPTO 2017 [LPS04] L a bi , Pag , Sma : A a king DSA n a p a bi s ass mp ion. CHES 2004, [MO09] M w an Oswal : T mpla a a ks on ECDSA. WISA 2009 [MLS02] Malon -L , Sma : Mo i i a ions o ECDSA. SAC 2002 [NS03] Ng y n, S pa linski: T ins i y o Ellip i C v Digi al Signa Algo i m wi pa ially known non s. D s. Co s C yp og ap y, 30(2):201 217, 2003 [PV05] Pailli , B gna : Dis -Log-Bas Signa s May No B Eq ival n o Dis Log. ASIACRYPT 2005 [PV96] Poin val, Va nay. On p ovabl s i y o igi al signa algo i ms. T ni al R po LIENS-96-17, LIENS 1996 [RHAL92] Riv s , H llman, An son, Lyons. R spons s o NIST s P oposal, Comm. o ACM 1992. p://p opl . sail.mi . / iv s /p bs/RHAL92.p [SB92] B ans a , Smi : R spons o Comm n s on NIST P opos Digi al Signa S an a , CRYPTO 1992 [S o p97] S o p: Low bo n s o is loga i ms an la p obl ms. EUROCRYPT 1997 [SPMLS02] S n, Poin val, Malon -L , Sma . Flaws in Applying P oo M o ologi s o Signa S m s. CRYPTO 2002 [Va 03] Va nay: T s i y o DSA an ECDSA. PKC 2003 [YCX21] Y n, C i, Xi : Compa Z o-Knowl g P oo s o T s ol ECDSA wi T s l ss S p, PKC 2021