If you're just looking for source code, it's here. But it's poorly documented (sorry), so definitely check out my expanded notes and examples here.
This post won't make any sense unless you've read the previous one.
This post won't make any sense unless you've read the previous one.
First of all, a semantic point: I use the word "hash" to mean "digest". But I use the former because industry experts often discuss "secure hashes" but rarely "secure digests". The rest of this article presumes that you understand the basic requirements for a secure hash: (1) that it be intractable to construct 2 messages with the same hash and (2) that the message cannot be derived with any useful statistical certainty from the hash. If this doesn't make sense, then Google around first.
Secure hash design is a humbling process (as distinct from evolution, which gave rise to the LMD family), because computers are so good at demonstrating the hidden statistical weaknesses of hashes which appear strong. To make the point obvious, consider a checksum. A checksum is a crude hash. At first blush, a 128-bit checksum is almost impossible to defeat because there are 2^128 possible checksums. But on closer examination, it turns out that it's very easy to get the same hash from 2 different messages -- even by accident! Namely, 2 bit flips in the same column simply add and subtract the same power of 2 from the checksum, resulting in no change. This concept extends even to choatic iterators, which, contrary to common sense, often show predictable behavior when seen through the right statistical analytic lens.
LMD4, LMD5, and LMD6 (abstractly, "LMDx"), when used in tandem with a symmetric encryption algo, are secure hashes, provided that said algo is harder to crack than the hashes themselves. That's because they rely on the algo for pseudorandom data.
These 3 hashes share a common precision-abstract algo, as defined below. So first, without further comment, I will provide their parameters, which constitute the entirety of their mutually distinguishing features:
LMD4 (256 bits)
N=128
A=(2^128-2^125-2^110-2^100)
B=(2^128-2^101-2^98-2^76)
LMD5 (512 bits)
N=256
A=(2^256-2^243-2^236-2^194)
B=(2^256-2^220-2^206-2^183)
LMD6 (1024 bits)
N=512
A=(2^512-2^498-2^496-2^427)
B=(2^512-2^481-2^404-2^362)
The number of bits in each hash is 2N. Half this value happens to be a useful quantity for the sake of defining the algo.
A and B are multiply-with-carry generator coefficients, in the LMD and LMD2 sense, chosen such that:
A*(2^N)-1 is prime;
A*(2^(N-1))-1 is prime;
B*(2^N)-1 is prime;
B*(2^(N-1))-1 is prime;
and A and B are easy to multiply by (for speed).
This is critical so that we can guarantee that the period of the generators (A,X0,C0) and (B,Y0,D0), in which (X0, C0)<>(0,0) and (Y0, D0)<>(0,0), is given by:
A*(2^(N-1))-1 or B*(2^(N-1))-1, respectively.
The important thing is simply that these huge cycle lengths can be guaranteed ahead of time, so we're not just stuck hoping that they're "long". And for their part, transient subcycle resonances are thwarted by virtue of the LMD generators' compliance with the reflexive density constant.
Granted, it's possible to maliciously construct a block L of data which exhibits resonance with the outputs of a particular LMDx generator. That's why, as shown below, (1) the seeds are implied by the cryptographic context, but not stored; and (2) we use 2 orthogonal generators to the compute the hash. Such construction is still possible because, after all, the hash is always many times shorter than L itself. However, I suspect that it's computationally intractable for reasons discussed below..
LMDx should be sufficient to satisfy both hash criteria above. However, it's still encrypted, as a measure of cheap insurance. It's specifically designed to plug into an encryption algo which has the following properties:
1. It can produce 4 pseudorandom seeds, each of N bits, to initiate LMDx. These seeds -- (x0, c0) and (y0, d0) -- are known only to the 2 parties which share a private symmetric encryption key. They are implied by the cryptographic context, and thus not transmitted in any form.
2. It can produce a 2N-bit xor mask, M, which is used to encrypt (by xoring) and decrypt (by xoring again) to the LMDx.
3. Neither of the above pseudorandom values is to be used for other purpose, which might permit statistical analysis attacks.
LMDx operates on a block of 2^15 bits (2^12 bytes, or 4KiB) of data -- regardless of N. This block is denoted as L. L[N,r] means the (r+1)th N-bit value of the block. For example, L[256,1] means the second 256 bits of the block. The maximum value j of r is thus:
j=(2^15)/N-1
j=(2^15)/N-1
x=X0
c=C0
y=Y0
d=D0
FOR (i=0 to j){
x=x xor y
p=A*(x xor L[N, i])+c
x=p MOD 2^N
x=p MOD 2^N
c=p/(2^N)
q=B*(y xor L[N, i xor ((j+1)/2)])+d
y=q MOD 2^N
y=q MOD 2^N
d=q/(2^N)
}
p=p+(y*(2^N))+d
p=p MOD 2^(2N)
z=p xor M
The algo above may appear arbitrary, but every step in the process serves a specific purpose, without which the hash would have known weaknesses. These weaknesses were extrapolated by statistical analysis of comparable hashes where N={8,12,13}. It's possible that other weaknesses (or strengths) occur when N>=128, but I lack the computational tools to expose them. However, the behavior in the aforementioned "small N" cases is so consistent, as to lend confidence to the latter case.
Assume that z is stored in plain view. Thus we could crack the hash if we could find U such that:
LMDx(L,N,A,B,X0,C0,Y0,D0,M)=LMDx(L',N,A,B,X0,C0,Y0,D0,M xor U)
At first blush, it's impossible to find U because the 4 seeds are secret; one must crack the encryption in order to find them, in which case the cracking the LMDx is probably a moot consideration anyway. One might surmise that 2^(2N) values of U are possible, given that U consists of 2N bits.
While this may be true in the general case where L and L' do not resemble one another, we want to concentrate on cases where L and L' differ by only a bit. In the worst case, this amounts to setting a single bit in a field of 0s, or clearing a single bit in a field of 1s. (Anything more complex is probably an exercise in self-deceipt with respect to hash strength.) In these painfully simple cases, it appears that only about 63% of all possible U values are actually roots (solutions) of the above equation.
63% is very close to the reflexive density constant. The upshot is thus that the roots of the hash appear as though chosen at random. In turn, this lends credence to the notion that we have a strong hash, the binary equations for which being as complex as possible, at least in the sense of root obfuscation, given the computational complexity required to compute the hash in the first place. (A more complex algo would create more obfuscated roots, but given the computational cost that we have, we appear to be getting maximum bang for the buck, because if any piece of it is removed, it exhibits statistical weaknesses.)
Again, this algo didn't come from thin air. It started as something more like LMD2, and evolved, step by step, until it satisfied the reflexive density constant and Poisson Criterion constraints sufficiently well.
So I hope you'll excuse its "warts", which are a necessary evil. In particular, the "x=x xor y" may seem arbitrary, particularly as it communicates data from the second generator to the first, but not the other way round. Without this instruction, the algo is a lot weaker. But with it, we seem to have achieved our goal. Providing a reverse dataflow is then just a waste of time, and might actually allow for easier hash compensation.
Secondly, the 2 instructions before the final xor may seem weird; why are we endian-flipping the second generator state before adding it to the first, and why not xor, which is faster than add due to the lack of carry propagation? Well, in the first case, the endian flip is required to ensure that the high bit of the generator state is not biased, which it would (slightly) be otherwise. (This is important with respect to the Poisson Criterion.) And we use addition instead of xor because -- you guessed it -- the algo would otherwise exhibit weaknesses.
Lastly, what's up with the "i xor ((j+1)/2)" in the expression for the second generator? All this does is ensure that the 2 generators are processing data which is halfway out of phase. What this means is that they are 128, 64, and 32 iterations apart for LMD4, LMD5, and LMD6, respectively. This guards against final-iteration attacks, in which changes to the last chunk of data in the block may fail to result in sufficient bit flips in the hash.
What about files which do not happen to be a multiple of 2^15 bits? And how do I compute the LMDx of a null file? That's all discussed here, in the "UPDATE" at bottom.
What's that? You want a demo? OK fine. Compile the source code from here.
After all that, did you manage to crack LMDx with "arbitrary" seeds, even in the case of a single-bit message modification? Cool! Please tell me how you did it, at hpkejjy@gmail.com without the "h".
