|
|
Subscribe / Log in / New account

You can in fact "add whatever to the pool forever"

You can in fact "add whatever to the pool forever"

Posted Sep 8, 2020 11:31 UTC (Tue) by tialaramex (subscriber, #21167)
In reply to: You can in fact "add whatever to the pool forever" by tanriol
Parent article: Theoretical vs. practical cryptography in the kernel

Mmm. You can experiment with this by building a toy HMAC that uses a too small hash so that the numbers are tractable. My guess is that for non-trivial N this takes a very long time (lots of data you 100% control shoved in as "random") to not do very much at all to the pool.

I don't see why a method that exploits this for real (on an actual HMAC with an actual N-bit pool) wouldn't also work perfectly well to collide arbitrary hashes, which is not supposed to be practical. But maybe you can explain why it doesn't do that?


to post comments

You can in fact "add whatever to the pool forever"

Posted Sep 8, 2020 12:11 UTC (Tue) by tanriol (guest, #131322) [Link] (1 responses)

Sorry, looks like I've been unclear. On the other hand, I'm not a cryptographer so you've been right to double-check for yourself :-)

In the original statement you said that spewing a bunch of something does not benefit the adversary *at all*. The way I understood that was that the N-bit pool still has N bits of entropy. That's obviously not the case because the number of possible states goes down, and quick experiments with a really small toy HMAC confirm that (repeatedly running it causes the entropy to reduce from the original 16 bits to 8 or so, just as expected from the birthday paradox style configuration). To avoid that you need your primitive to be an (input-driven, obviously) permutation in the state space so that the number of states stays the same. There are constructions like this - IIUC, SHA3 uses one, unlike MD5/SHA1/SHA2 - but you need to pay attention to this.

On the other hand, for collision attacks N/2 is already the baseline due to the birthday paradox, so by itself this effect does not provide any improvements over that - a hash resistant to collision attacks would also be resistant to this effect.

You can in fact "add whatever to the pool forever"

Posted Sep 9, 2020 10:00 UTC (Wed) by tialaramex (subscriber, #21167) [Link]

Ah, so you can get from N to N/2 (half the pool size) but no further? I guess I can see no intuitive objection to that and if you've done the experiment then it must be so. I agree that's significantly weaker than my original claim though.


Copyright © 2025, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds