Thanks for the answer... though there are a couple of things I'd like clarified. Do you have a reference regarding the "rho pattern"?

The other issue is whether or not the real hash function "is good"... If there is any narrowing of the state space, it strikes me that there must be a finite limit to the number of times the hash function can be recursively applied before there's insufficient entropy to assure security. It also strikes me as unlikely that all (any?) hash functions are entropy preserving when applied to values of the same length as the hash. In order to establish the limit, I'd need to estimate information loss on each application... but I don't know how to go about that.

@aSteve: for the "rho pattern", see the Handbook of Applied Cryptography, chapter 2, section 2.1.6 (page 54).

@aSteve: the point of the rho pattern is that the "narrowing" is limited to the size of the cycle -- you cannot narrow down any further because that's a cycle. And the size of the cycle is about $2^{n/2}$.

@aSteve: it is proven that the probability of not having a very small cycle with a random function is vanishingly small. The risks involved in that probability are negligible with regards to other unlucky events such as, e.g., getting hit by an old satellite reentering the atmosphere. The "real" issue is rather on whether a given hash function behaves like a random function.

Many thanks for the ref. I think I grasp what you meant by 'rho patterns' now. I still find your answer counter-intuitive... but guess that, if I could prove that repeated application always results in the large cycle, I'd be fully convinced. With my practical hat on, I wonder if some hashes can be shown to reliably have larger cycles than others? Must I accept these large cycles on faith, or are they proven? Is the answer the same if I use H(some-published-constant,m) in place of H(m)?

@aSteve: Actually, we even expect no to be able to prove things on cycle lengths with an actual hash function: such a proof would require intimate structural knowledge of the function graph, and resistance to collisions and preimages relies on the difficulty of gaining such intimate knowledge.

That proving cycle lengths is genuinely "hard" for real hash functions is no surprise. For practical purposes, I guess extensive simulation would provide me with adequate confidence... for example, if several million randomly chosen messages create a million non-repeating values each - then I'd feel less anxious. Do such studies exist, or would I need to do them myself?

The site suggested these comments were moved to "chat" - and as I seemed to be picking your brains, rather than contributing knowledge, I agreed to 'automatically convert' - I hope that's OK with you... I think your reference on rho-patterns might help others... perhaps it needs to be moved back?

I also agree - the 'real' issue is definitely whether or not a hash function behaves like a random function... I'm trying to establish if this is a safe assumption for some/all well known hash functions.

There is no proof that hash functions really exist.

That being said, we must make do with "candidates"

Functions which seem to behave like what an ideal hash function will do.

Among the kind of behaviour that we expect is the presence of a large cycle in the middle.

To know whether a hash function is "trustworthy", we let loose a few dozen cryptographers on it.

They gnaw at it for a few years.

And if they find no weakness at all, then the function is deemed "secure -- so far".

That's the best we can do right now, and SHA-256 is at that stage.

Now we can try things on "reduced" versions, e.g. hash functions with a 32-bit output, where the structure can be explored exhaustively, and see if things behave as we expect.

This is part of the arsenal of cryptographers.

So, to sum up: you can assume that SHA-256 behaves as a random function about as much as you can assume that SHA-256 is resistant to collisions. Which I assume.

Those are reassuring words.... :)

Of course, I 'assumed' that this would hold when I came up with a strategy to solve a problem I faced which depends upon it holding. What I'm now trying to do is to establish whether or not I can convince others that it's "OK"...

I've flexibility to use MD5 or SHA256 or SHA512 - or anything else... and I'm free to use seeds... but I need to be confident that no hash in the sequence of hashes provides useful information about the previous hash.

I recognise that with repeated application of the hash function, I'm stressing it in a way other users do not...

Hence why I'm hunting for 'evidence' that I'm (probably) safe.

Suitable evidence might include empirical studies or other credible systems that depend upon the property for the same hash function as I'm using.

@aSteve You can have a look at one-time password schemes which use hash chains. E.g. S/KEY:

Such systems rely on the idea that recursive hashing does not weaken (too much) resistance to preimages.

You can also see the Handbook, chapter 10, page 396

So there are "other users" of hash functions who use repeated application, and they seem to do fine.

That's a great example - and one I'd not encountered in my Linux dabbling.

I see I'm going to have to read the handbook of applied cryptography - not just leave it on my bookshelf and hope that's enough. :)

@aSteve Yep, sometimes we believe that knowledge just sips through the pages and diffuses in the room, but in fact books don't work like that. You really have to read them.

You've moved the handbook significantly towards the front of my queue of books I should read cover-to-cover... Thanks. :)