[Ach] [cryptography] Diffie-Hellman Params Best Practice on Web Server?
L. Aaron Kaplan
kaplan at cert.at
Wed Dec 11 22:38:26 CET 2013
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>
More information about the Ach
mailing list