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
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?
Posted Sep 8, 2020 12:11 UTC (Tue)
by tanriol (guest, #131322)
[Link] (1 responses)
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.
Posted Sep 9, 2020 10:00 UTC (Wed)
by tialaramex (subscriber, #21167)
[Link]
You can in fact "add whatever to the pool forever"
You can in fact "add whatever to the pool forever"
