Should feeds be IDed with the public key to protect against hash-collision attacks?

[pfrazee]

This relates to #8, but regards internal architecture.

Currently, the feeds are identified with Blake2 hashes of their public keys. This means an effective collision-attack could create unpredictable behaviors.

How much of an efficiency impact would we take if we used public keys as the IDs? Based on the hex-strings I've been staring at, the hash (32 bytes) looks like it's half as large as the ECC public key (64 bytes). If that's right, then I think we should consider accepting the drop in efficiency for a simpler security design.

[dominictarr]

The chance of a collision is astronomically small. Even sha1, which has been shown to be weaker than we thought, still has no known collisions.

Of course, crypto doesn't make it impossible that no one could guess your key, or create a ew key with the same hash, but it makes it so incredibly unlikely that you should be much more worried about being killed by a meteor, etc...

So the answer is yes, but don't worry about it. And that we are also relying on difficult-to-guessness of generating the public key - since a private key is just a long random number (it's also 32 bytes, actually!)

[pfrazee]

The scenario that concerns me is this:

Say somebody purposely creates a key (A) with a hash that collides with my key (B)'s hash. The odds are low, but still greater than zero. They distribute the key (A). A node (Alice) keeps a table of hashes to public keys. She has cached my key (B). However, the attacker distributes his key (A) under the same hash, and the node (Alice) naively accepts it, overwriting my key (B).

My concern here is the indirection involved. Even if the node (Alice) did not overwrite the entry, the path forward is indeterminate -- how do we handle such a scenario? Isn't the safer option to eliminate the indirection?

[dominictarr]

My point is that no rational attacker would attempt to attack that way, and we already depend on hash collisions for loads of other stuff. If you could generate a hash collision you could send a fake feed that had been signed with some one elses key, or return a different attachment.

here is an interesting article on SHA1, https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html also here is more context: https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

basically, if you bruteforced sha1 it would be 2^80 operations on average (searching through 50% or the 2^160 possibilities) but computer science has figured out how to prune the search space, bringing it down to 2^60 operations. That is a million times easier.

The first article has a calculation that sha1 by 2021 sha1 might cost 41k to break, but if it had not been weakened, it would still cost 41 billion dollars.

That is for sha1. We are using blake2s, which has 32 bytes (256 bits) like sha256 does. 2^128 is much much bigger than 2^60 (281,474,976,710,656 times larger!)

So, 41k * 281 trillion = 11 million trillion dollars.

Now, given that the world economy is 71 trillion dollars, that is like 10000 * earth 2014 AD worth of effort completely devoted to finding one hash collision.

I'm not worried anybody wants to break my ID hash that much.

[pfrazee]

Ok, that seems reasonable. You can mark this closed.

On Thu, Aug 28, 2014 at 5:19 PM, Dominic Tarr notifications@github.com wrote:

My point is that no rational attacker would attempt to attack that way, and we already depend on hash collisions for loads of other stuff. If you could generate a hash collision you could send a fake feed that had been signed with some one elses key, or return a different attachment.

here is an interesting article on SHA1, https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html also here is more context: https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

basically, if you bruteforced sha1 it would be 2^80 operations on average (searching through 50% or the 2^160 possibilities) but computer science has figured out how to prune the search space, bringing it down to 2^60 operations. That is a million times easier.

The first article has a calculation that sha1 by 2021 sha1 might cost 41k to break, but if it had not been weakened, it would still cost 41 billion dollars.

That is for sha1. We are using blake2s, which has 32 bytes (256 bits) like sha256 does. 2^128 is much much bigger than 2^60 (281,474,976,710,656 times larger!)

So, 41k * 281 trillion = 11 million trillion dollars.

Now, given that the world economy is 71 trillion dollars, that is like 10000 * earth 2014 AD worth of effort completely devoted to finding one hash collision.

I'm not worried anybody wants to break my ID hash that much.

— Reply to this email directly or view it on GitHub https://github.com/dominictarr/secure-scuttlebutt/issues/16#issuecomment-53811122 .