ECDSA: Sign

\[\begin{aligned} \textrm{Secret info} & : \textrm{private key } \textcolor{red}{d}; \textrm{nonce } \textcolor{red}{k}~(0 < d, k < n) \\ \textrm{Public info} & : \textrm{curve } E(\mathbb{F}_q); \textrm{base point } G \in E(\mathbb{F}_q), |G|=n; \\ & ~ \textrm{public key } [d]G; \textrm{hash function } h(\cdot) \\ \textrm{Message } & : m \\ \textrm{Signature } & : (r, s) \end{aligned} \]

\[\begin{aligned} r & = (\colorbox{blue}{[k] G})_x \mod n \\ s & = (h(m) + d r) k^{-1} \mod n \end{aligned} \]

ECDSA: Nonce Must Be Secured

\[\begin{aligned} r & = ([\textcolor{red}{k}] G)_x \mod n \\ s & = (h(m) + \textcolor{red}{d} r) \textcolor{red}{k}^{-1} \mod n \end{aligned} \] \[ \textrm{Knowledge of nonce } k \implies \textrm{Knowledge of private key } d \\ \]

\[ d = (s k - h(m)) r^{-1} \mod n \]

Elliptic Curve Scalar Multiplication: Double and add

                      # MSB to LSB
                      let bits = bit_repr(k)
                      let res = ponit_at_infinity
                     
                      for bit in bits:
                        res = res + res # double
                        if bit == 1:            
                          res = res + G # add
                        i = i - 1 # move right
                      return res
                    

Doubld And Add Leaks Information

Point addition and doubling take different CPU cycles

Double and Add Leaks Information

                      let bits = bit_repr(k)
                      let res = ponit_at_infinity
                     
                      for bit in bits:
                        res = res + res # double
                        if bit == 1:            
                          res = res + G # add
                        i = i - 1 # move right
                      return res
                    

Peter Montgomery (1947-2020)

Scalar Multiplication: Montgomery's Ladder

Speeding the Pollard and elliptic curve methods of factorization by Peter L. Montgomery, 1987. (Full paper)

Scalar Multiplication: Montgomery's Ladder

                      # MSB to LSB
                      let bits = bit_repr(k)
                      let R0 = ponit_at_infinity
                      let R1 = G

                      for bit in bits:
                        if bit == 0:
                          R1 = R0 + R1
                          R0 = R0 + R0
                        else:
                          R0 = R1 + R0
                          R1 = R1 + R1
                        i = i - 1 # move right
                      return R0
                    

The Devil Is In The Implementation

Leaking A Few Nonce Bits

Remote Timing Attack

• Collect certain amount of (message, signature) pairs
• Use timing leak to filter signatures with leading 0-bit runs than a fixed threshold
• Create a system of linear equations using filtered pairs
• Try solving the system to recover a single nonce using the LLL algorithm
• Use the nonce to recover private key

References:
Remote Timing Attacks Are Still Practical by Billy B. Brumley and Nicola Tuveri, 2011
Lattice Attacks on Digital Signature Schemes by Nick A. Howgrave-Graham and Nigel P. Smart, 2001

Mitigations

• Blinding: Brumley and Tuveri's fix in OpenSSL \[ \textrm{Compute equivalent } [\tilde{k}] G \textrm{, where} \] \[ \tilde{k} = \begin{cases} k + 2n & \text{if } \lceil\lg(k+n)\rceil = \lceil\lg n\rceil \\ k + n & \text{otherwise} \end{cases}\]
• RFC6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA): cf. Section 3.2

Leaking Secret Bits from Branching Conditions

Cache-Timing Attack: Flush+Reload

• Local attack exploiting a weakness in processor architecture (X86): shared cache lines between processes
• FLUSH+RELOAD method allows a spy process to figure out which branch is taken through cache-timing leaks
• Branching condition uniquely determines a bit in secret nonce

References:
Recovering OpenSSL ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack by Yuval Yarom and Naomi Benger, 2014
Cache Missing For Fun and Profit by Colin Percival, 2005

Mitigations

• Code-level: Prevent data flow from secrets to branching conditions.
  Yarom and Benger's fix in OpenSSL
• Processor architecture and OS level (and maybe app store level?): Restrict ability to flush specific memory lines from cache

Summary

1. The group law must be evaluated in the same order independent of the bits of the scalar
2. The number of loop iterations must be fixed
3. Memory operations must not depend on bits of the secret scalar

Food For Thought

• Does subzero leak? (cf. trezor-crypto/ecdsa.c)
• How much should we be worried?