Fun with Cryptographic Hash Functions and PBKDF1-Like Constructions
soatok.blog
soatok.blog
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.
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.)