LMD8

LMD8, whose source code is here, is a 512-bit hash with 32-kilobit blocks. It's about 30% faster than LMD7 (in addition to the reduced IO time), or better if the loops are unrolled at the expense of instruction cache efficiency.

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. In principle, O(2^S) qubits would provide a quantum complexity of O(2^(S+(N-S))), which is somewhat better, but probably not much use in practice because we usually have S<<N, especially when dealing with qubits. (So far as I know, multiverses can't communicate with each other, which means that a quantum computer isn't of much use in problems where all the elements need to interact.)

So how long of a hash is enough, assuming that it's strong? Obviously, the answer is subject to massive error, but we can at least turn to physics for a suggestion. Let's assume that you can encode a hash on a neutron, and that you can pack them densely, neutron star style, for the purposes of creating storage media. 2^128 of these bits would then weigh (9x10^(-14)) as much as Earth. That's like the weight of a modest sized asteroid -- huge, but not inconceivable, with all the talk of asteroid mining these days. At neutron star density, it would probably fit in a room.

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]];

---

...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.