[Cryptography] hash size

[Viktor Dukhovni]

> 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...

-- 
	Viktor.