Policy-Discussion

[Philipp Gühring <pg AT futureware.at>]

Hi,

> You all  know that password attacks are not done brute force (brute force
> attacks on a long password can take years) , but by lookups in a table with
> precalculated hashes (rainbow table lookup, crack a password in
> milliseconds). What would stop a dedicated foreign agency to start
> generating rainbow tables for public/private key pairs? If well funded,
> they can build dedicated hardware for it, and once such a table is created
> they can simply do a lookup to find any private key based on the public key
> in milliseconds... I'm not a crypto specialist, so could someone give an
> indication of the number of valid public/private key pair with 1024bit key
> size? 

Given proper entropy was used properly to generate the keys (which both isn´t 
given in practice, but let´s assume it anyway), you get something like 2^1024 
possible keys, which is

17976931348623159077293051907890247336179769789423065727343008115773
26758055009631327084773224075360211201138798713933576587897688144166
22492847430639474124377767893424865485276302219601246094119453082952
08500576883815068234246288147391311054082723716335051068458629823994
7245938479716304835356329624224137216 possible keys. Let´s assume that a key 
usually costs a Kilobyte, and you succeed to need only 10 Bytes for each 
entry in your rainbow table, then you need

17976931348623159077293051907890247336179769789423065727343008115773
26758055009631327084773224075360211201138798713933576587897688144166
22492847430639474124377767893424865485276302219601246094119453082952
08500576883815068234246288147391311054082723716335051068458629823994
72459384797163048353563296242241372160 Bytes, which is about

17976931348623159077293051907890247336179769789423065727343008115773
26758055009631327084773224075360211201138798713933576587897688144166
22492847430639474124377767893424865485276302219601246094119453082952
08500576883815068234246288147391311054082723716335051068458629823994
72459384797163048353563296242241 Megabyte, which is about

17976931348623159077293051907890247336179769789423065727343008115773
26758055009631327084773224075360211201138798713933576587897688144166
22492847430639474124377767893424865485276302219601246094119453082952
08500576883815068234246288147391311054082723716335051068458629823994
72459384797163048353563296 Terabyte

> Am I missing something?

If you have a cheap source for that amount of storage, please let me know!

Best regards,
Philipp Gühring