LogJam Attack Explained
To understand DH key exchange, let’s first undestand mathematic behind it.
Group: They are algebraic structure which obey following laws.
•Closure property: Take any two elements from set and perform binary operation, result should also be in same set , like + on Integer(Z).
•Associative property: a+(b+c) = (a+b)+c , this is true for (Z,+).
•Identity Element: there exists an element in e such that a + e = a , in case of Z this will be 0 and 0 exists in Z.
•Inverse there exists an element in set such that a + a-1 = e (Identity element) , in set Z if we take 2 , its inverse would be -2 since 2 + (-2) = 0.
•Abelian Group : Commutative law also hold i.e. a+b = b+a.
Multiplicative Group modulo p
•multiplicative group modulo p, (Zₚ , *) for example (Z₇, *) = [1,2, 3, 4, 5, 6]
•2 * 4 mod 7 = 1
•2 *(3*4) mod 7 = (2*3)*4 mod 7
•2 *1 mod 7 = 2 ∴ 1 is identity element
•2 * 4 mod 7 = 1 , 4 is inverse of 2
•2*4 mod 7 = 4*2 mod 7
•Hence (Z₇, *) is a group under binary operation of *.
•(Z10, *) =? [1,3,7,9] Why because for 2,4,etc you can not find inverse for every element. It appears for prime p , group laws hold true.
Cyclic Group: Using at least one element of group we can generate all other element of group. lets see an example of G =(Z₇, *), if we chose g=3 and try to generate other element by applying group operator which is * mod 7
As noticed all other elements can be generated using g=3 , however if we chose g=2 , we cannot generate all elements of group.
This g is called generator a.k.a primitive roots.
How to find all generator of a group.
•Total Number of generator = φ (φ (p)) [φ i.e. phi stands for Euler’s Totient ]
•Example p=19 φ (19) = 18, φ (18) = 2.3.3 (prime factors)= 18 . (1–1/2)(1–1/3)=6 [ only distinct primes]
•What are those 6 generator?
•Determine all the prime factors of s: p1,…,pk
•Choose any a and test if a(p-1)/p1 = 1 mod p ?
•a= 2 p = 19 {p1=2, p2=3}
•2(19–1)/2 = 29≢ 1 mod 19
•2(19–1)/3 = 26≢ 1 mod 19 ∴2 is generator
•All others : a.k.a gcd(p−1,k) = 1; k=[1, 5, 7, 11, 13, 17]
•Generator = [2, 13, 14, 15, 3, 10]
Discrete Logarithm
What is a logarithm: Suppose we can given 100 = 10ˣ , in order to solve for x ; x = log₁₀ 100 , this is logarithm.
Discrete logarithm is of form h = gˣ mod p; where p is a large prime, g is generator of Cyclic Group G.
Discrete Logarithm Problem states that given (h, g, p ) it is tough to solve for x.So far we don’t have an efficient algorithm to solve for x for a carefully chosen group.
DH Key Exchange
- Alice and Bob agreed on parameter (g , p).
- Alice chose a secret a and send to Bob gᵃ mod p. Anyone can see this value as well.
- Bob also chose a secret b and send to Alice gᵇ mod p.
- Alice have [a ,gᵇ mod p] while Bob has [b, gᵃ mod p] and they have a shared secret gᵃᵇ mod p.
DH Key Exchange in TLS
DH key exchange shown above is prone to an active man-in-the-middle attack. During TLS session establishment, server value .e.g. gᵃ mod p is signed by Server’s private Key. Client can verify before trusting this value. This value is typically sent in ServerkeyExchange
p is prime modulo being used.
g is chosen generator.
PubKey is value of gᵃ mod p. Note that a is unknown.
Signature is PubKey signed using Signature algorithm like RSA/EC.
Logjam Attack
TLS session starts with Client connecting to a server and publish a list of cipher suites it supports in order of strongest being the first.
Server selects the common strongest one and they go on to compute common shared secret as explained above and further deriving session keys.
A Man-in-the-Middle(MiTM) can downgrade the connection to export grade cipher suites which uses 512 bit prime number p. As explained in FREAK attack, browser as well as server both support export grade cipher suites. As advancement in computing this 512 bit can be broken using General Number Field Sieve(GNFS) algorithm and hence a Man-in-the Middle also knows shared secret. MiTM also have to compute Finished message using the computed shared secret and with it’s own ClientHello and then server.
Few things to note out that server typically compute gᵇ mod p and reuse this value for entire lifetime. openssl has a switch ` SSL_OP_SINGLE_DH_USE` to make sure a fresh b value is always chosen.
Full Technical paper: https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf
CVE-ID: https://nvd.nist.gov/vuln/detail/CVE-2015-4000
Mitigation:
Disable export grade DH key exchange, use perfect forward secrecy.