In the paper "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice" [here] it was discovered that many Web sites on the Internet used the same prime numbers for Diffie-Hellman Key Exchange. This allows for pre-computed keys to be generated for the values that Bob and Alice will use for their random numbers. In the following we will generated the shared key for values of 100 and 101 and for a G value of 3. Select a prime number:
Weak DH - Pre-computing DH |
Background
The following shows the basic method:
Within Diffie-Hellman key exchange, Bob generates an x value and calculates A:
\(A = G^x\mod p\)
Alice does the same and generates y, and the value of B:
\(B = G^y\mod p\)
Next Bob receives Alice's value (B) and raises it to x, and then computes the shared key:
\(Key = B^x\mod p\)
where x is Bob's random number, y is Alice's random number. The value of p is the prime number, and if it is a well-known prime number, the possible values of the keys can be pre-computed.
In the paper "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice" [here], we the authors defines a range of prime numbers which are used for TLS key exhange for Diffie-Hellman key exchange. If these are used, then an adversory can compile a list of keys for a range of random values (x and y), and then match these. In the following we use a prime number of 0x9fdb8b8a00454...7d08f70e6aa871033L:
Key: 0x9fdb8b8a004544f0045f1737d0ba2e0b274cdf1a9f588218fb435316a16e374171fd19d8d8f37c39bf863fd60e3e300680a3030c6e4c3757d08f70e6aa871033L x y Shared Key 100 100 141712882825921845644704769632745622601375629836052341385366535757747023401534528023731408699709878650488921680095879119479989665027456617305151270652192 100 101 529609334064784835402608286401745579115015095123148250690161577251605425522484976671903284992718508527810347558185302624211217331517851802658463838404699 101 100 529609334064784835402608286401745579115015095123148250690161577251605425522484976671903284992718508527810347558185302624211217331517851802658463838404699 101 101 914874672215774533837192665152716001408958112991636900393715396216020576719815419003509111900658636212968102556916266364035044219645999393564279754348622
Examples of weak keys are:
Apache: 0x9FDB8B8A004544F0045F1737D0BA2E0B274CDF1A9F588218FB435316A16E374171FD19D8D8F37C39BF863FD60E3E300680A3030C6E4C3757D08F70E6AA871033 mod_ssl: 0xD4BCD52406F69B35994B88DE5DB89682C8157F62D8F33633EE5772F11F05AB22D6B5145B9F241E5ACC31FF090A4BC71148976F76795094E71E7903529F5A824B 0xFCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17
The code is:
import sys g=3 p1=0x9FDB8B8A004544F0045F1737D0BA2E0B274CDF1A9F588218FB435316A16E374171FD19D8D8F37C39BF863FD60E3E300680A3030C6E4C3757D08F70E6AA871033 p2=0xD4BCD52406F69B35994B88DE5DB89682C8157F62D8F33633EE5772F11F05AB22D6B5145B9F241E5ACC31FF090A4BC71148976F76795094E71E7903529F5A824B p3=0xFCA682CE8E12CABA26EFCCF7110E526DB078B05EDECBCD1EB4A208F3AE1617AE01F35B91A47E6DF63413C5E12ED0899BCD132ACD50D99151BDC43EE737592E17 p4=0x678471B27A9CF44EE91A49C5147DB1A9AAF244F05A434D6486931D2D14271B9E35030B71FD73DA179069B32E2935630E1C2062354D0DA20A6C416E50BE794CA4 val=1 p=p1 if (len(sys.argv)>1): val=int(sys.argv[1]) if (val==1): p=p1 if (val==2): p=p2 if (val==3): p=p3 if (val==4): p=p4 print ("Key:",hex(p)) print () print ("x\ty\t\tShared Key") for a in range (100,102): for b in range (100,102): A=(g**a) % p B=(g**b) % p Key1= (B**a) % p print (a,"\t",b,"\t",Key1)