[Ach] [cryptography] Diffie-Hellman Params Best Practice on Web Server?

[L. Aaron Kaplan]

On Dec 11, 2013, at 4:48 PM, Pepi Zawodsky <pepi.zawodsky at maclemon.at> wrote:

> Food for thought…
> When everybody usese the same DH parameters it becomes worthwhile to brute force them, since if you manage to crack them, you get a lot of traffic you can access. More diversity makes that a broader target with less benefit to invest money/cycles/efforts into.
> 

What do you mean exactly by brute force them?
How would you achieve that?


Let's recap Diffie Hellman:


Let g be a primitive root modulo p (= prime) (== \exists{k} such that $ g^k = 1 (mod p) $ )
g,p are public

Alice secret key: x
Bob secret key: y

TOBOB   = g^x (mod p)
TOALICE = g^y(mod p)

@bob: commonkey =  TOBOB^y =  (g^x)^y (mod p) = g^(x*y) (mod p) = (g^y)^x (mod p) = TOALICE^x = commonkey @alice


So, how do you want to brute force for all values of x or y or x*y?
How much space does that take for p,g in the range of 1024 bits  and x in the same size?
Actually g might be even small (like 2 or so).

The only way you can do that is either you have a great way for finding logs in Z_p (Z == integer numbers)
Or you have some ingenious way of storing a table for all logs of g^x mod p (and then you look up the value) and precompute that. This could maybe be some kind of rainbow table or so (?) 

Let's estimate it like this:
We decide to store only  one bit for every possible value x in g^x (mod p)   (of course, one bit is not enough).

Since p is O(2^1024)  (if we assume that p is a 1024 bit number) that's still a very large table.
Actually that's

% bc -l
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
2^1024
17976931348623159077293051907890247336179769789423065727343008115773\
26758055009631327084773224075360211201138798713933576587897688144166\
22492847430639474124377767893424865485276302219601246094119453082952\
08500576883815068234246288147391311054082723716335051068458629823994\
7245938479716304835356329624224137216

That's a ten with 309 digits.
Yes, and since we decided to only store one bit per g^x (mod p), then the table gets divided in size by 8. 
:)

Maybe we will find a great to compress the table by a factor of one million. Well, then it is still a  number with 303 digits (take 6 digits way).


For a better explanation see also: http://www.mccurley.org/papers/dlog.pdf section 3.


Note: in case I did any mistakes in the calculations above, I am totally tired right now. Please feel free to blame me.



--- 
// L. Aaron Kaplan <kaplan at cert.at> - T: +43 1 5056416 78
// CERT Austria - http://www.cert.at/
// Eine Initiative der nic.at GmbH - http://www.nic.at/
// Firmenbuchnummer 172568b, LG Salzburg




-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 163 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.cert.at/pipermail/ach/attachments/20131211/5e277dab/attachment.sig>