-----------------------------------
How DH fails in practice
Nadia Heninger
EUROCRYPT? Also CRYPTO rump session
-----------------------------------
Amuse-bouche
Scanned internet for servers supporting DH.
Found many different primes (70,000 I think?), many of which are not Sophie-Germaine. This might be OK, because perhaps they are DSA-style groups (where large q | p-1), or if not, probably p-1 has a large factor.
However, if ord(g) has many small factors, it is not compatible with small exponent optimization. Rho/Pohlig-Helman/CRT breaks it. Broke 159 key exchanges with this fact.
---
Index calculus
Have some sieving algorithm which finds relations of the form
n = 2^a2 3^a3 ... x^ax, factor n, if it's B-smooth for some B then store relations.
Do sparse linear algebra mod q (hard)
Total runtime, optimized for B ~ L(1/2, sqrt(2)).
Improvement: number field sieve. Do this over Q(t)/f(t) for some polynomial t. Same idea, better bounds:
L(1/3, 1.923) precomputation
L(1/3, 1.232) calculation of log, no linear algebra
About 10x as hard as factoring (lg p = 512 bits) because linear algebra is mod q.
Precomputation is about 10 core years, sieving is about 10 core minutes.
(On a cluster, 2k-3k cores: 3h polynomial selection, 15 hours sieving, 120 hours linalg; 70 seconds descent on 36-core machine.)
---
Downgrade attacks
In TLS 1.2, the client's offered cipher suites are not signed, and because DH and export-DH have the same format. Therefore the handshake will pass client authentication except for the MAC.
When this attack was announced, 8.4% of Alexa top sites allowed DHE_EXPORT. 92% of them used the top 2 primes. Can attack this with MITM, especially if client is a machine and willing to wait 70 seconds.
---
LOGJAM attack
Estimate 768-bit discrete log as 36.5k core-years, 2 core-days descent.
Estimate 1024-bit discrete log as 45M core-years precomp, 30 core-days descent. NB: Don't need to do man in the middle, can just break connection directly.
Cost: about $8M+1 year of power with ASICs to sieve. Linear algebra: don't know, but probably hundreds of millions of dollars.
Snowden docs: various phrases suggest that NSA may be carrying out this attack. Slides suggest that it may be carried out against IKE in particular. ~64-66% of IKE traffic uses only 2 groups.
Mitigation: move to ECC, or >= 2048-bit primes, or ephemeral 1024-bit primes.
Browsers have stopped accepting 512-bit groups, will sunset 768- and 1024-bit groups soon.
---
-----------------
NFS-DL in F_{p^k}
Aurore Guillevic
ASIACRYPT 2015
-----------------
Focus: large precomputation, then relatively fast individual dlog in F(p^k).
This talk focuses on computation of the individual discrete logarithms.
In particular, pairings.
Pairings: usually source groups over eg p^n, p^2n target group is p^nk,
k between 1 and 12. Superlingular=2, MNT=3,4,6, BN=12, KSS=18 but group order ~p(3n/4).
Typically recommend 256*12 = 3072-bit field.
Small characteristic totally broken.
Theoretical attacks (Joux Pierrot '13, BGK 2015 tower NFS)
---
NFS: choose polynomials phi dividing f(x),g(x)
Collect relations
Do linear algebra
Precomputation finishes: have database of dlog(p) for |p| infinity.
From 2012, it's suggested [cite] that for fixed q this is also true, using Semaev
polynomials and Groebner-basis solvers.
Can use either Semaev polynomials or the "splitting trick", i.e. to write S_n as
n-2 copies of S_3 (i.e. Q = P1 + R, R = P2 + P3).
Use Groebner basis solver.
---
First fall degree: if you have polynomials g_i, then degree is smallest d where there
exist h_i where max(deg(g_i h_i)) = d, but 0 < deg sum g_i h_i < d
FF degree assumption: first fall degree is similar to regularity degree = max degree
you will see during groebner basis calculation, at least for ECDLP.
Kosters: I don't believe this assumption.
Why not? First of all, it would suggest for singular curves that subset-sum can
be solved in polynomial time.
Also, improved experiments in first fall vs regularity seem to provide counter evidence.
Corollary: Groebner basis + Semaev for discrete log are in doubt.
However, it seems to hold for hidden field equations. So what is the difference
between ECDLP and HFE?
---
Last fall degree: roughly the last time instead of first
--------------------------
Security of Genus 3 curves
Kim Laine
--------------------------
Jacobian variety is roughly {[P1]+[P2]+[P3]-3[P0]}, roughly triples of points.
Genus 3 curves have two flavors. Hyperelliptic is y^2 = P(x) of degree 7.
Non-hyperelliptic are the more general case. Index calculus on non-hyperelliptic
has comlpexity O~(q) over Fq, vs hyperelliptic with complexity O~(q^(4/3)).
---
Non-hyperelliptic curve (Diem): factor base is a subset of the curve,
where the Jacobian variety is roughly the formal sum of 3 points on the curve.
To find relations, intersect the curve with a line; the sum of the 4 points
on the line is zero.
Draw all lines between pairs of points. Probably the other two interesctions
with the curve are not in the factor base; draw an edge between those points to form
a graph. Transitively closing this graph produces relations among the factor
base elements.
Improvement over Diem: start with q^(1/4) points, and draw lines between them to get
q^(1/2) elements, then use those for factor base.
Implementation roughly 1.bleh * (lg q)^2 q, but requires too much memory to be
practical.
Time-memory tradeoffs. Possibly scales up to q ~ 2^60, giving 2^79 work instead of 2^90.
-----------------------------
Computing modular polynomials
Enea Milio
-----------------------------
I can't follow the math in this talk, so here's a rough outline.
Modular polynomials describe isogeny classes of elliptic curves, and can be computed
by interpolation. The computation is somewhat complicated and the polynomials have
many coefficients and digits, though there are ways to "compress" them with invariants.
This talk discusses a generalization of modular polynomials to surfaces of genus 2,
and how to compute them. In particular, Duport computed modular polynomials for p=2
but not for larger p, because they are too big. Using fancier invariants, Enea was
able to compute larger modular polynomials, up to maybe p=7 IIRC.
------------------------------------
Recovering short generators of
principal ideals in cyclotomic rings
Léo Ducas
------------------------------------
Some ring cryptosystems choose a short generator g in a ring R
Public key is a bad (eg canonical) basis for the ideal (g)
Cryptanalysis:
1) Given a basis, recover a generator
2) Given a generator, recover a short generator
1) Have now a sub-exponential classical algorithm (in theory), and progress
toward quantum poly-time algorithm.
2) Claimed to be easy. Equivalent to CVP in the "log-unit" lattice, or
in common crypto cases it is bounded-distance-decoding.
This talk: prove that 2 is easy at least in the case of cyclotomics.
Let Log map x in a number field K to [log(phi[x]) : embedding phi in C].
Its kernel is roots of unity, and the units map to a lattice. Since g, h
generate the same ideal iff h = ug for some unit u, and we want g to be small,
we want to find (roughly) the closest lattice point u to h.
---
Strategy: construct a basis B of the log-unit lattice R*. But this is known
based on the cyclotomic units log ((1-zeta^j)/(1-zeta)); while this may not
be a full basis, it is conjectured to be one for m=2^k and probably "close
enough" for other m.
Reduce this basis, solve CVP, small generator is found.
----------------------
Weaknesses in Ring-LWE
Katherine Stange
----------------------
LWE: given (a, + e) in Fq^n x Fq
Ring-LWE: Fq[x]/f; given samples (a,as+e) in Rq^2;
a uniform; s,e small according to error distributions
In particular, f is usually cyclotomic.
Protocol: Alice chooses secret s, sends as+e; Bob sends at+f; compute ast+small.
Question: is there a way to exploit the extra structure?
Minkowski embedding: natural map to C^n (or R^n because parts are complex conjugates)
Multiplication and addition are component-wise.
This gives reasonable choices of errors: ball around the origin in Minkowski or
in polynomial representation. Either one results in a distortion in the other case,
can be measured by largest radius of one ball when transformed to the other metric
(spectral norm).
Spectral norm is 1 for 2-power cyclotomics, close to 1 for non-2-power cyclotomics,
may be large for general number fields.
EHL attack: if f(1) = 0, then Rq -> Fq evaluating at 1 is a ring homomorphism.
Guess at s(1), get a,a(1)s(1)+e(1) -> e(1).
Same works if f(-1) = 0 or anything else small order.
This is a distinguishing attack; it does not compute s.
Seach problem is more relevant.
Actual weak example: x^1024 - (2^31 - 2) mod 2^31 - 1 takes 13 hours to break.
Search can be reduced to decision in a Galois field.
Key idea: if \q is a prime above (q), then there is a ring homomorphism Rq -> R/\q,
but the error distribution is not uniform over R/\q, which will induce a weakness.
This is because R/\q is much smaller than Rq, and so small enough to exhaust,
but big enough that breaking LWE in R/\q gives information about Rq.
Usually the error distribution will look uniform.
Have found attackable examples of residue degree 2.
Probably cyclotomics are not vulnerable to this family of attacks.
Questions: can you leverage this by switching rings or by changing polynomials?
Eg, add multiples of q to coefficients of the polynomials, which affects the
behavior over the integers.
----------------------
Verifying ECC software
Peter Schwabe
----------------------
Verifying specifically X25519, but same principle could be applied to other curves
and operations.
Want to show that software is correct, also that it is secure (eg, against timing
attacks). Can check this with valgrind/ctgrind. Easient way is to not initialize
your secret data. (Mike notes: could probably annotate real library with memcheck.h.)
What about correctness against eg carry bugs? Reduced radix can help, but serious
implementations have had possibly-exploitable bugs.
Approach 1: annotate qhasm code. Translate to SMT-solver boolector. Use boolector
to verify software. But multiplies tend to choke these tools. Had to do lots of
annotations, also a little bit of Coq work.
Approach 2: SAGE. Overload operators in C++ to trace multiply. Output to SAGE's
Groebner basis solver. Need to "cut" verification into chunks. Can verify all
muls in ladder.
-------------------------------------
Simple tricks for ECC implementations
Mike Hamburg
-------------------------------------
My talk. A collection of implementation techniques.
Example library APIs
Scalar multiplication:
Signed binary scalars
Fixed-base precomputed combs
Arithmetic:
Inverse square root trick
Algorithmic:
Encoding to an elliptic curve with Elligator 2
“Decaf”: use quotient groups instead of subgroups
---------------------------------------------------
Cryptography in GNUnet:
Protocols for a future internet for libre societies
Christian Grothoff
---------------------------------------------------
Goal: DNS-like system but resist censorship and spying.
However, intermediaries can see if a query is the same one they're making,
for cacheability.
www.gnu is your own server.
Alice learn's Bob's public key from his business card. Names it Bob, and can
query www.bob.gnu to get Bob's info.
Crypto. Derive a private key d = hash(label,Bob's public key) * (Bob's private key).
Then set a record (dG, sign_d(encrypt(above hash, result))). Query = hash of dG.
Anyone can compute the query from Bob's public key, and can verify the sig and read the
result. Revocation: a separate system with revocation certificates, but requires proof
of work to prevent DoS.
Zooko's triangle: hypothesis that a name system can be global, memorable or secure
but not all three ("secure" defined in a way that blockchains are not a full solution).
Hierarchical registration is global and memorable but not secure; pubkeys are not
memorable; petnames are not global.
---
Scalarproduct for GNUnet.
Use Paillier cryptosystem for additive homomorphism. (Or ElGamal with small elements,
and solve the DLP to retrieve the answer.)
Alice has input map mA : MA -> Z, bob mB : MB -> Z, compute sum mA(i)mB(i)
for i in intersection.
---
Taler: secure payments.
Mint issues coins, customer pays merchant, merchant deposits coins, auditor verifies.
Unlike traditional Chaum, can give change. Unlike Chaum, all payments must be online.
Unlike Chaum, taxable but anonymous payments are still allowed.
---
Trevor's TripleDH. Maybe use a deniable signature to prevent KCI even on a device with a bad RNG.
--------------------------------------
Hardware accelerators for ECC and HECC
A Tisserand
--------------------------------------
Fp, F2^m, 80-600 bits
Accelerate entire scalarmul operation.
Resist side channels, (in progress) fault injection.
Looks like an ASIP. Control logic implements up through even scalarmuls.
Register file does streaming loads/stores. Addresses are randomized (or will be?)
Dedicated key recoding unit. Computes NAF etc, addition chains, ...?
Talks AXI or whatever.
Anti-alignment design in eg Mastrovito multiplier. Non-constant time for this reason.
Hard to compare performance, since they are using FPGAs with no DSP units. "Maybe 30k
gates, who really knows"; heavily side channel protected; small options appear to take
~6.5M cycles for 256-bit ECC operation. Bigger but faster and better protected
(supposedly) than ultra-small units. Hard to compare vs CRI development work, especially
with very uncertain numbers and unknown curve (eg, special prime accel applies?); first
guess is that it's significantly slower but more flexible and includes a more capable
ASIP. Not sure whether RAM cost is counted. Not sure how expensive the countermeasures
are; random stall should be cheap.
Claim that in the spring, their platform will be available on the open internet.
------------------------------
Fault attacks against pairings
Juliane Krämer
------------------------------
Fault attack examples: RSA-CRT, invalid curve attacks
Pairing inversion problem: Given (an attack on the operation of) e(P,Q), find Q.
Rough assumption: have to invert both exponentiation and Miller loop.
Tate pairing is thus harder to break because it has a more complex final exponentiation.
Previous work: theoretical but not actually conducted.
---
This attack: eta pairing. (271+1)/2, F2^271, Final exponentiation (q^4-1)/#E(Fq).
Used two faults. One to disturb the Miller computation by dropping iterations,
one outright skips final exp. Both are instruction skip faults with clock glitching.
Used an automated setup to brute-force the parameter space for glitches (eg, how many
cycles to glitch for).
---
Countermeasures are the standard ones (checksums, canaries, random delays, etc) and also
blinding using the bilinearity of the pairing.