SESSION ID: CRYP-T10 Modeling Memory Faults in Signature and Authenticated Encryption Schemes Felix Günther joint work with Marc Fischlin (TU Darmstadt) Postdoctoral Researcher Department of Computer Science, ETH Zurich, Switzerland #RSAC Memory Faults #RSAC FreeImages.com/Chris Woods What About the Code? #RSAC FreeImages.com/Gabor Heja The Cryptographic Perspective Deterministic ECDSA Signature security (EUF-CMA) Signdet-ECDSA(sk, m) r ← Hash(sk, m) R ← f(rG) mod q s ← (H(m) + sk R)/r mod q return (R, s) 4 #RSAC #RSAC Models Matter Deterministic ECDSA (& co.) succumb to rowhammer-style faults [PSSLR @ IEEE EuroS&P 2018] (R0,s0): (R!,s!): sk = H(m) + sk R0 = Hash(sk, m)s0 H(m) + sk R! = Hash(sk, m)s! H(m) / ((R0-R!)s0 / (s0-s!) - R0) We know for long that faults can have devastating effects on crypto operations at software level [BDL @ Eurocrypt 1997] But how to assess fault resilience in provable-security manner? 5 #RSAC Prior Work Faults in circuits [IPSW06] Tailored provable-security models (e.g., for RSA) [CM09, BDFGTZ14, FGLTZ12] Related-key attack (RKA) security [BK04, GLMMR04] Hedged randomness in Fiat-Shamir-type signatures under faults [AOTZ19] 6 #RSAC A Generic Framework for Fault Resilience in Security Models #RSAC Modeling Fault Resilience m) Signdr(sk, m) <m> <m>) r ← Hash(sk, m) <m>; r)r) s ← Signr(sk, m; ! return s augmented code, indicating faultable memory variables callbacks to adversary: may change values of variable readings 8 #RSAC Generic Fault Types Flexible callbacks Forming a hierarchy Full faults adversary controls variable completely Differential faults adversary can flip w selected bits Random faults adversary can flip N random bits No fault (baseline) 9 #RSAC Fault Resilience for Signatures #RSAC Augmenting Signature Security frEUF-CMA: Fault-resilience unforgeability Essential question: Signdr(sk, m) Which message did the signer sign? r ← Hash(sk, <m>) = Which (m,s) is trivially learned? s ← Signr(sk, <m>; r) Answer: the message m (among all appearing in Sign) verifying with s return s If there‘s two such m → confusion → adversary declared successful 11 De-Randomized Signatures Are Not Fault-Resilient 1. #RSAC Query OSign on m – no faults – obtain signature s on m Signdr(sk, m) r ← Hash(sk, <m>) 2. Query OSign on m – first <m>: do nothing – second <m>: flip bit (to m‘) – obtain signature s on m‘ s ← Signr(sk, <m>; r) return s 3. 12 Create new forgery due to re-used randomness r for signatures on m and m‘ Combining Randomization & De-Randomization Combining security (provably) de-randomization for regular EUF-CMA security under bad randomness Signc(sk, m) r‘←${0,1}λ randomization for fault-resilient EUF-CMA security under differential faults on m, r, r‘ r ← Hash(sk, <m>, <r‘>) s ← Signr(sk, <m>; <r>) return s 13 #RSAC #RSAC Fault Resilience for Authenticated Encryption #RSAC A Similar Setting good randomness isn‘t always available nonce-based authenticated encryption (AE) to avoid randomness nonce-misuse resistance hedging against repeated nonces but what about faults? 15 SIV Mode of Operation: Synthetic IV [RS06] Nonce-misue resistance … … but vulnerable to faults 1. EncSIV((K1,K2), N, A, m) – no faults, obtain c1 = c or $ IV ← PRF(K1, <N>|<A>|<m>) c Query OEnc on (N=00..0,A,m) 2. ← Enc(K2, <m>; <IV>) Query OEnc on (N=10..0,A,m) – <N> callback: flip 1st bit – obtain c2 = c or different $ return (IV, c) 3. 16 Distinguish by checking if c1 = c2 #RSAC SIV$: Combining Randomization & De-Randomization #RSAC Combining security (provably) synthetic IV approach for nonce-misuse res. AE security under bad randomness EncSIV$((K1,K2), N, A, m) r ←${0,1}λ c ← Enc(K2, <r>|<m>; <IV>) IV ← PRF(K1, <N>|<A>|<m>|<r>) return (IV, c) 17 augmented randomness for fault-resilient nm-res. AE security under diff. faults on N, A, m, r, IV #RSAC Summary Introduced generic model for understanding fault resilience in computational security proofs Signatures – confirm fault attacks on de-randomized signatures – provable security of combined randomization + de-randomization XEdDSA Authenticated encryption – fault-attack treatment of SIV mode of operation – propose combined SIV$ mode achieving fault resilience 18 Applying the Generic Fault Resilience Model Select your favorite crypto primitive – fault resilience model is generic Revise security definitions towards fault-resilient var