[Cryptography] hash size

Viktor Dukhovni cryptography at dukhovni.org
Thu Nov 1 13:58:55 EDT 2018

> On Oct 31, 2018, at 6:03 PM, jamesd at echeque.com wrote:
> Launching a birthday attack on a 128 bit hash would involve generating 2^64 hashes and sorting them.

Sorting them all is not required to detect collisions.

> This requires 3*2^67 bytes of disk.

Nor is that much storage.  A rainbow table could suffice.
Parallelizing the rainbow table computation at reasonable
communication cost is the tricky part.  The key/value
store can be sharded, but naively you still need O(2^64)
table queries during table construction, and to construct
the table in one year, one needs to move O(2^70) bits in
O(2^25) seconds, so the interconnect appears to need an
aggregate bandwidth of O(2^45) bps.  I don't know how to
make the construction phase practical.

Some clever people may have figured efficient ways to
build rainbow tables for a 2^64 keyspace without prohibitive
communications costs...


More information about the cryptography mailing list