Security dangers of the NIST curves
Daniel J. Bernstein, Tanja Langehttp://xkcd.com/927

http://xkcd.com/927
But our goal today isn’t unification; it’s security.
“We come to bury the standard, not to praise it.”Why do people choose standardized curves?

Why do people choose standardized curves?
I “Because they told me to”
I “Need to ensure interoperability”
I “The standards committee chose these curves for efficiency”
I “The standards committee chose these curves for security”
I “Obviously these curves have received much more

cryptanalysis: standard makes a worthwhile target for attack”(as in symmetric crypto)

Contrary example, Apple, “iOS Security”, October 2012:
I Automatic encryption for files stored on flash on iPhones,iPads (starting with iOS 4 in 2010)
I Why use public-key crypto? Clear answer from Apple: “Somefiles may need to be written while the device is locked. A
good example of this is a mail attachment downloading in thebackground.”
I Uses ECC but not a standard NIST curve: “This behavior isachieved by using asymmetric elliptic curve cryptography(ECDH over Curve25519).”
I Same for iCloud Backup: “All the class keys in this keybag areasymmetric (using Curve25519, like the Protected UnlessOpen Data Protection class), so iCloud backups can be
performed in the background.”Is ECC cryptanalysis actually curve-specific?
I Reality: researchers try to solve the generic ECDLPI Algorithm to find n given

curve E , point P on E , point nP on E
I Maybe algorithm performance varies with E
I Extreme example: MOV attack works only forpairing-friendly curves
I Standards react by prohibiting

the entire class of attacked curves
I and maybe even curves that smell similar(e.g., small-discriminant CM)

I Important example: IEEE P1363 standard
I Surveys all ECDLP attack techniques known in 1999
I Prohibits all curves breakable by these techniques
I Specifies method of generating random non-prohibitedcurve
I Jerry Solinas at NSA used this to generate the NIST
curves
I Were any more curves broken 1999–2013?
I For non-prime-field ECC, yes, some advances
I already known in 1998 to be worrisome (Frey)
I 2006 Curve25519 paper: prime fields “have thevirtue of minimizing the number of security concerns
for elliptic-curve cryptography”
I Using more computer power, yes
I New speedups in rho algorithm, but same basicbottlenecks
I Overall security picture unchanged for prime-field ECC

I Important example: IEEE P1363 standard
I Surveys all ECDLP attack techniques known in 1999
I Prohibits all curves breakable by these techniques
I Specifies method of generating random non-prohibitedcurve
I Jerry Solinas at NSA used this to generate the NIST
curves (or so he says)
I Were any more curves broken 1999–2013?
I For non-prime-field ECC, yes, some advances
I already known in 1998 to be worrisome (Frey)
I 2006 Curve25519 paper: prime fields “have thevirtue of minimizing the number of security concerns
for elliptic-curve cryptography”
I Using more computer power, yes
I New speedups in rho algorithm, but same basicbottlenecks
I Overall security picture unchanged for prime-field ECC

I Why don’t we give each user a separate curve?
I Changing curves is much cheaper than changing ciphers
I Would be an easy defense against curve-specificcryptanalysis
I but that’s not how ECC cryptanalysis actually works
I Really does defend against batch attacks
I but a bigger field would provide more security atlower cost
I Summary: not actually justified by rational cost-benefit
analysis

We’re writing a document “Security dangers of the NIST curves”
I Focus on the prime-field NIST curves
I DLP news relevant to these curves? NoI DLP on these curves seems really hard
I So what’s the problem?
I Answer: If you implement the NIST curves, chances are you’re

doing it wrong
I Your code produces incorrect results for some rare curve
pointsI Your code leaks secret data when the input isn’t a curve
point
I Your code leaks secret data through branch timing
I Your code leaks secret data through cache timing
I Even more trouble in smart cards: power, EM, etc.
I Theoretically possible to do it right, but very hard
I Can anyone show us software for the NIST curves doneright?

I These problems are exploitable by attackers
I These attacks are against real protocols, not against DLPI DLP is non-interactive; real protocols handle

attacker-controlled input
I DLP reveals only nP; real protocols also reveal timing
I DLP always computes nP correctly; real protocols have

failure cases
I Attacker takes advantage of these gaps
I Many papers claim that ECC is provably secure if DLP isI In fact, ECC is much less secure than DLPI Non-interactivity etc. are oversimplifications
I Important for cryptanalysts to study the actual systems
I Important for cryptographers to build better systems

Critical issue: implementation.
How do ECC standards get implemented?

Critical issue: implementation.
How do ECC standards get implemented?
I Use OpenSSL library (includes, e.g., P-256)
I Use Certicom tools
I Use NaCl library (includes Curve25519)
I Have grad student write it up
I Comes with the smart card or coprocessor
I In house by the hardware designer

How has the implementation been checked/reviewed/verified?

How has the implementation been checked/reviewed/verified?
I Smart cards:
I FIPS or CC evaluation after testing in lab
I Tests include side-channel attacks
I Software:
I OpenSSL is worthwhile target for security researchers
I Continuing string of papers on cryptographic failuresin OpenSSL
I Including ECC failures
I Many known failures are still not fixed
I Why? Implementation difficulty, especially forconstant time
I See ECC 2012 talk by Brumley
I NaCl is also worthwhile target
I Benefit is increasing: wider and wider deployment
I Cost is low: NaCl emphasizes simplicity, verifiability
I Already some successful formal verification
I correctness of part of the code
I SCA resistance for part of the code

Review of basic ECC setup:
I Have group G of points on an elliptic curve
I BSGS/rho attacks work in time O(√#G )I Typical cryptosystem works in subgroup of prime order `I Combine BSGS/rho with Pohlig–Hellman: time O(√`)

I We avoid curves where there are better attacks
I Side note: maybe this is excessively paranoid
I e.g. can use curves with endomorphisms (Koblitz,GLV, GLS, etc.)
I some security loss from endomorphisms, but seems
controllable
I pairing-based crypto needs these curves
I But we’ll stick to maximum-security curves for ECC

I How big is `?
I #G is very close to p if G is E (Fp )I gap is at most 2√

p+1
I ` is a prime divisor of #G ; ratio #G /` is “cofactor”
I In other words:
I security forces large `I which forces large #G ; exact size depends on cofactor
I which forces large p
I Efficiency depends on p

Review of the (prime-field) NIST curves:
I Presented by NIST in 1999
I Curve names: P-192, P-224, P-256, P-384, P-521
I Curve is defined over Fp where p has 192 bits, 224 bits,etc.
I Primes are pseudo-Mersenne primes:
I e.g. P-224 prime is 2224 − 296 + 1
I e.g. P-256 prime is 2256 − 2224 + 2192 + 296 − 1
I Why? Efficiency
I NSA’s Jerry Solinas chose these curves and wrote

papers about the speed of these primes

I Curve shape specifically y 2 = x 3 − 3x + b
I About 50% of all curves
I Absolutely nothing worrisome from an ECDLP

perspective
I “For reasons of efficiency”
I cites IEEE P1363 standard
I P1363 cites 1987 paper by Chudnovsky brothersI P1363 claims that its choices “provide the fastest

arithmetic on elliptic curves”
I Cofactor choice:I NIST takes cofactor “as small as possible” for “efficiencyreasons”
I All cofactors for NIST curves are 1, 2, or 4
I All cofactors for prime-field NIST curves are 1

I Protection against back doors (copied from P1363):
I NIST publishes s where b is (basically) SHA-1(s)I Situation where this provides protection:
I NSA knows a rare ECC weakness: a few weak curves
y 2 = x 3 − 3x + b
I NSA doesn’t know how to invert SHA-1
I But what if NSA knows a weakness in many curvechoices?
I e.g., 1/1000000000 of all curves
I NSA searches many choices of s until finding a weakcurveWhy did NIST choose these curves?

Why did NIST choose these curves?
I Most people we have asked: “security”
I Actual NIST design document: “efficiency”
I There are some minimal security requirements
I Enough to make ECDLP hard
I Not enough to make ECC secure
I Amusing side notes regarding efficiency:
I addition formulas presented in standard are suboptimal,

even for exactly these curves
I NIST’s prime choices are suboptimal
I cofactor 4 is much more efficient than cofactor 1

What goes wrong with the NIST curves? (part 1)
I Simplest scalar-multiplication inner loop: P ← P + P;

P ← P + Q if current exponent bit is set
I Huge timing channel, but that’s not the only problem
I Simplest way to implement “+”: use the addition formulas
I But this doesn’t work for doublings; all tests failI So implementor checks book, implements dbl(P)I New inner loop: P ← dbl(P); P ← P + Q if current

exponent bit is set
I This passes all tests but still has failure cases
I e.g., what if P = Q? what if P = −Q?
I Maybe implementor instead has “+” check for P = Q
I less likely: this is slower and more complicated code
I doesn’t catch all the failure cases
I Attacker triggers the failure cases
I Fancy example: Izu–Takagi “exceptional procedureattack”

Alternative: Montgomery curves y 2 = x 3 + ax 2 + xI Use Montgomery ladder for scalar multiplicationI per bit 1 doubling + 1 differential addition
I differential addition: compute P + Q given P, Q, P − Q
I automatic uniform pattern independent of n; goodagainst timing and simple side-channel attacks
I Represent a point as its x-coordinate
I very fast doubling, very fast differential addition
I faster scalar multiplication than y 2 = x 3 − 3x + b
I for Montgomery curves that have unique point of order 2:
I infinity and 0 behave the same way
I the formulas always work (2006 Bernstein)

I Is security the same?
I Cannot be very different
I Every curve is a Montgomery curve over a small

extension field
I Almost half of all curves are Montgomery curves over thesame field
I Any serious attack on Montgomery curves would behuge ECC news
I Cofactor for Montgomery curves is a multiple of 4
I Requires slightly larger primes
I Limitation: only for single-scalar multiplication
I signature verification needs double-scalar multiplication
I but no problem for DH, El Gamal, etc.

Does this work for the NIST curves?
I Not easily; NIST cofactor 1 is incompatible with Montgomery
I Can still try to imitate part of the Montgomery approach
I Double and always add
I Slow, more complicated than standard approach
I More smart-card trouble: extra vulnerability to fault

attacks
I Can stop timing attacks but does nothing to fix failurecases
I LadderI Representing point as (x, y ): very slow
I Just x: not as slow (Brier–Joye) but still complicated
I Maybe fixes failure cases; analysis has never been done

What goes wrong with the NIST curves? (part 2)
I What if input point P is not on E but on a different curve?
I Simplest implementation doesn’t check. What happens?
I Typical ECDH answer: successfully obtain nP on that othercurve; use nP as shared secret to encrypt data
I Attacker chooses P so that, e.g., 1009P = 0; checks

encryption, quickly figures out n mod 1009
I Attacker figures out n by CRT
I Attack is not as easy if P is represented as just x
I Only two possible curves: E and its “nontrivial quadratictwist”
I 2001 Bernstein: stop attack by choosing twist to besecure
I Might happen by accident, but random curves are usuallyless secure
I NIST P-256 has a somewhat weaker twist (security 2121 )I NIST P-224 has a much weaker twist (security 259 )Summary so far:
I Choose Montgomery curves (with unique point of order 2)
I Represent points as x-coordinates
I In particular choose twist-secure curves
I Simple implementation is fine
I Main limitation: how to handle signatures?

Alternative: Edwards curves x 2 + y 2 = 1 + dx 2 y 2
I Focus on complete Edwards curves: non-square d
I about 25% of all elliptic curves
I includes Curve25519; does not include the NIST curves
I Simplest addition law is complete
I x3 = (x1 y2 + x2 y1 )/(1 + dx1 x2 y1 y2 )I y3 = (y1 y2 − x1 x2 )/(1 − dx1 x2 y1 y2 )I no exceptions: works for doubling, P + (−P), etc.
I easy to implement; It Just WorksTM
I can implement separate doubling but don’t have toI also very fast (see http://hyperelliptic.org/EFD)
I Guarantees Montgomery compatibility
I easy secure single-scalar multiplication
I Also good for other ECC protocols
I simplest signature-verification implementation is fineFinal summary:
I ECDLP security does not guarantee ECC security
I Add extra requirements on curve choices
I Recognize the importance of friendliness to implementors
I NIST curves cause real trouble
I Require Montgomery compatibility (NIST curves flunk)
I Require Edwards compatibility (NIST curves flunk)
I Require completeness (NIST curves flunk)
I Require twist security (NIST curves are weak)
I Easy to generate curves meeting all these requirements:

Curve25519, Curve1174, etc.