10 ms·
Fun with Cryptographic Hash Functions and PBKDF1-Like Constructions
- some_furry 6y agoI wrote this because the cautionary tale of PBKDF1 led to some really interesting thought experiments. After I wrote this, I received some math corrections from cryptographers, which led me to discover an interesting (but intuitively sensible) observation: 1. There are roughly O(sqrt(N)) cycles. 2. The average cycle length is roughly O(sqrt(N)). Unless you're supremely unlucky, most of the hashes you generate will fall within a cycle. (That is, of course, assuming that your hash is securely pseudorandom in the first place.)
- tromp 6y agoCuriously, finding cycles in graphs defined by siphash-2-4 is exactly what my Cuckoo Cycle Proof-of-Work is about [1]. Furthermore, the most efficient algorithm for solving it, by edge-trimming, also suggests an interesting memory-hard PBKDF, where you hash the edge bitmap after a small fixed number of edge trimming rounds. [1] https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo