[p2p-hackers] Homomorphic hashing and fountain codes - implementation question

[Hal Finney]

Nick Johnson writes:
> Should someone successfully break the 1024 bit hash, what would the 
> consequences be? Could they compute collisions for a single block (a 
> break that is meaningless, since using the per-publisher model the only 
> one setting blocks is the publisher, who can compute collisions with 
> ease anyway - a backup file-wide SHA-1 hash will act to prevent this), 
> could they conduct a preimage attack against a single block, or could 
> they create collisions and preimage attacks for any file published with 
> that K? Worse, could they compute collisions for every file published 
> using that p?

As I understand it, the hash on a block is computed by breaking it into
256 bit pieces t_i, and using pre-defined constants g_i, computing the
product over i of g_i^t_i.

If someone did the work to break discrete logs mod p, they could compute
the discrete logs of the g_i relative to each other, and take discrete
logs of hashes.  This would allow them to create a block that would match
the hash of any given block.  They could compute preimages for any hash,
and they could compute collisions for any file hash using that p.

The nature of the discrete log attack based on p is that it is expensive
to mount, but once you have done the work, you can easily find more
discrete logs of other values using that same modulus p.

However, on the other hand, these hypothetical machines are really
expensive, something like a billion dollars in today's money.  Some people
speculate that it might be down to a hundred million in a few years.

The main concern with 1024 bit moduli has been cryptographic, where
"they" could factor your key.  Since it's so easy to move to bigger
keys, many people are doing it, just to make sure that no government or
anyone else who has a billion dollars to spend could read their messages.
I guess everyone feels like they are special enough that their secrets
might be worth that much.

In your case, maybe this level of paranoia is unnecessary.  Nobody is
going to spend a billion dollars to break this.  You could think about
how much the opponents of this system would be willing to spend, look
at Moore's law over the time frame during which you would envision this
system being used, and estimate a desired security level from that.

There's also the point that if someone did have the money to build such
a machine, they would probably rather factor RSA moduli secretly than
publicly start messing with your hashes.  As soon as someone noticed
a matching hash it would give away the existence of the machine.
Then people would switch to a larger hash, making the machine useless.
All that money spent would be wasted after forging a single hash.
Using it to break encryption keys allows the machine to be kept secret,
making it far more valuable.

http://mathworld.wolfram.com/RSANumber.html has a nice chart showing
the progress over the years in factoring RSA moduli, which are within an
order of magnitude of difficulty of finding discrete logs.  The largest
RSA modulus factored is 576 bits, although looking at the chart I expect
640 will probably fall within a year or so.

One point is that you should try to design the system to allow the hash
size to be upgradeable if and when it became necessary.  Then, maybe you
could even get away with something a little smaller than 1024, with the
idea of upgrading in five years or so, when faster networks and cheaper
disk storage will make a larger hash more palatable.  This will also
let you recover from a surprise breakthrough.

Another point is that if you used a different p for every file, it
would require a billion dollars per file break rather than a billion to
break the whole system.  In that case I'd feel much safer about using a
smaller p, even maybe 768 bits if you accept that one or two files might
be cracked by say 2010.

Hal