Pursuant to further analysis of the birthday attack myth, I don't think that a strong hash need be longer than 512 bits (and that's probably overstated even so). To the extent that no hash is optimally strong, of course, we need extra bits to compensate. But it's a fool's game to try to guess how much redundancy is sufficient, in the absence of a solid understanding of the weaknesses of a given hash.
It boils down to this: if you have a 2N-bit hash, then a birthday attack can crack it in O(2^N) operations. However, this process requires memory large enough to store O(2^N) hashes. If your memory size is only 2^S, where S<N, then the complexity expands to O(2^(S+2*(N-S))). (The execution time doesn't expand quite as much, on account of faster communication in smaller memories.)
At the extreme where S=0, the memory is only large enough to store 1 working hash (ignoring the readonly hash to which it must be compared), which is minimally sufficient for cracking. A quantum computer comes to mind. In this case, the classical complexity is about O(2^2N), which the quantum computer would then square root to roughly O(2^N), which is no better than the classical complexity, given sufficient memory.
2^256 of them, on the other hand, would consume (3x10^25) Earth masses. Barring some discovery of much denser matter amenable to data storage, it's not happening.
Bear in mind, however, that all of this is of course predicated on the hash being optimally hard, which is most certainly never the case. And perhaps I'm wrong about quantum computers not being helpful. We could, of course, also use some number of bits that wasn't a power of 2, but that gets yucky. So for now, I think I'm comfortable with a 512-bit hash. In time, maybe I'll feel comfortable with 256 bits as well, and invent LMD9. We'll see.
LMD8 is exactly like LMD7, but LMD8 has N=256. Because there are 64 words in a block with LMD8, instead of 32, the oscillator values LMD8_D0 and LMD8_D1 have been selected to hit maximum entropy after 33 iterations, in order to sufficiently protect the weakest bit in the block, which is still bit ((2^14)-1). Changing this bit when the rest of the block is 0s results in very nearly 256 bit transitions in xor of the hashes, averaged over many identical seed pairs -- in other words, chaos.
LMD8_A0=2^0x100-LMD7_D0
LMD8_A1=2^0x100-LMD7_D1
where:
LMD7_D0=0x9C20E342
LMD7_D1=0xD28CC42E
I won't reiterate the algo, because it was covered in the LMD7 blog entry. LMD8_A0 and LMD8_A1 satisfy the usual primality requirements for a long Marsaglia oscillator. Specifically, the period is ((LMD8_A0*(2^0x1FF))-1), and similarly for LMD8_A1. The high bit bias in either case is on the order of 1 part in (10^67) in favor of 0, i.e. negligible even for cryptographic purposes. Here's a sample input for Mathematica Kernel:
A=(2^256-16^^9C20E342);B=(2^256-16^^D28CC42E);n=256;t=2^n;u=2^(n+n);X0=1;C0=2;Y0=3;D0=4;M=0;j=((2^15)/n)-1;L=Array[#&,j+1];x=X0;c=C0;y=Y0;d=D0;For[i=0,i<j,i+=2,x=BitXor[x,y];c=BitXor[c,d];p=(A*BitXor[x,L[[i+1]]])+BitXor[c,L[[i+2]]];x=Mod[p,t];c=BitShiftRight[p,n];q=(B*BitXor[y,L[[BitXor[i,((j+1)/2)]+1]]])+BitXor[d,L[[BitXor[i,((j+1)/2)]+2]]];y=Mod[q,t];d=BitShiftRight[q,n]];p=Mod[p+BitShiftLeft[y,n]+d,u];z=BitXor[p,M];Print[BaseForm[z,16]];
This is the same output generated by demo.c in the source code.
I don't need to reiterate the whole evolutionary process by which its security has been inferred from LMD7 and ultimately LMD6.
...and its output hash:
7909b4a019a49f859f47b9aee785db957a79dd8838bb8ddac46d25c5f3470c8e3d324c97a7b8f647fcafd945db87257006eb86d92363204567ec5483f37a3ef6
This is the same output generated by demo.c in the source code.
I don't need to reiterate the whole evolutionary process by which its security has been inferred from LMD7 and ultimately LMD6.
