Visualizing Marsaglia Oscillators

In the question of assessing the pseudorandom quality of a Marsaglia multiply-with-carry oscillator with 2N bits of state, of the sort underlying LMDx after LMD1 [EDIT:  As in, (2^(N-1))<=A<(2^N)], it occurred to me that pictures might be of some use.

To do this, I took various A values that are possible with N=9. (By "possible", I mean that the period (P=(A*(2^(N-1))-1)) is a Sophie Germain prime.) Then I created a map of the entire cycle space. It's pretty clear that only 4 cycles exist in such an oscillator:

---

1. 0 maps to itself.

2. ((A-1)*2^N)+((2^N)-1) maps to itself. This is a "nuisance cycle" because it's easily overlooked and threatens to shut down the oscillator if chosen as a seed.

3a. One of the big cycles has period P.

3b. There are some integers greater than or equal to (A*(2^N)) which eventually find their way onto cycle 3a, but never return to 3b due to limits on the maximum possible output value within 3a.

4a. The other big cycle has period P as well.

4b. Analagous to cycle 3b, there are points which degenerate into to cycle 4a as well.

---

The number of integers in 3b and 4b is empirically similar, but not equal. I can't explain the difference.

You can see all this in the images below, which have A values of 495, 465, 459, 402, 390, 369, 297, and 270, respectively. There is a bright area, which contains 3a and 4a, and a dark area, which contains 3b and 4b. The upper left and lower right corners of the bright area are white pixels indicating cycles 1 and 2. The rest is red and blue, for cycles 3 and 4.

These images show clearly why these oscillators suffer from bias in the high bit: once you jump from the dark to the bright region, you can't return. One way to deal with that is to engineer A so that the dark area has negligible size.

And I don't know about you, but I'm seeing squarish cells and somewhat nonrandom lower frequency oscillations in the images. Still, it looks very solid for such a simple function. (They are losslessly encoded 512x512 GIF images, so there are no JPEG artifacts here. Right-click and "open in new window" if your browser is scaling them in some annoying way, which mine appears to be doing.)

---

---

The Reflexive Density Theorem

This proof solidifies some of the earlier observations of the reflexive density constant, a necessary-but-not-sufficient requirement in the evaluation of random number generator security.

Given T, an unbiased true random number generator, which can produce 1 of N unique integers; and S, a set consisting of N such sample outputs. Then the expected number E of unique integers in S, in the limit that N approaches infinity, is given by:

---

E = (1-1/e)N
E = RN

---

Here is the proof:

Construct a bitmap B, consisting of N 0s. Obtain S by performing N invocations of T. For each integer in S, set a bit in B corresponding to the sorted order of all possible outputs of T; that is, bit 0 would correspond to the least such integer, and bit (N-1) would correspond to the greatest. (In practice, the possible outputs would be 0 through N-1, where N is a power of 2. But that's not required here.)

Because T is unbiased, the probability of any given bit ending up as 1 is uniform throughout B. So consider one of these bits in isolation.

After the first invokation of T, the odds that this bit is 1 is just 1/N. Put another way, the odds that it's 0 is (1-1/N).

After the second invokation, the odds that it's still 0 are: the odds that it was still 0 after the first iteration, times another factor of (1-1/N). Thus the odds that it's still 0 are (1-1/N)^2.

We can continue this logic over all N invocations of T. The odds that this bit ends up as 0 is then ((1-1/N)^N). Thus, in the limit of infinite N, the odds R that this bit is 1 is just 1 minus this quantity:

---

R = lim(N->infinity,1-((1-1/N)^N))
R = 1-1/e
R ~ 0.6321205588285576784044762298385391325541888689682321

---

This last step was computed here from everything that WolframAlpha knows about math. Due to the symmetry of the problem, the "oneness" of any such bit applies to whole of B, so RN is indeed the expected number of 1s.

It turns out that the reflexive density constant shows up in lots of places. For example:

1. Neural network stability at equation 6.27.

2. The exponential cummulative distribution function.

3. The Poisson distribution, if we were to add up the 1s at each bit of B, instead of ORing them.

4. The Random Arrival Time Best-Choice Problem on p. 499.

5. Some other discussion about it which shows that I wasn't the first to prove the reflexive density theorem, although hopefully you find my proof to be intuitive.

Mathematica Source Code for LMD4, LMD5, and LMD6

It's been brought to my attention that the C source code provided in this blog post isn't exactly well commented. I apologise for that. I think the most instructive way to show what's going on, however, is to use Wolfram Mathematica, specifically the Mathematica Kernel, which is a command line interface for math nerds. I have used this wonderful piece of software to verify the functionality of these hashes. But in the interest of reproducible research, you should be able to do the same.

So let's do an example. I'll give you the exact code you need to cut and paste in, and the expected output. Here again is the algo which underlies all 3 hashes:

---

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

  c=p/(2^N)

  q=B*(y xor L[N, i xor ((j+1)/2)])+d

  y=q MOD 2^N

  d=q/(2^N)

}

p=p+(y*(2^N))+d

p=p MOD 2^(2N)

z=p xor M

---

And here again is a summary of what stuff means, in order of appearance above:

---

j is the maximum index of the block, each item of which is N bits wide.

N is half the bit width of the hash: 128 for LMD4, 256 for LMD5, or 512 for LMD6.

X0, C0, Y0, and D0 are the N-bit hash seeds, which are intended to be sourced from a cryptographic pseudorandom algo, and which is not used for any other purpose, nor ever used again. In the C source code, they appear in memory in the aforementioned order at p_base on input to the hash. Note that we have 4N bits going into a hash which will ultimately be only 2N bits wide.

x, c, y, and d are also N bits wide. (x, c) and (y, d) function in a manner similar to (x, c) in a Marsaglia oscillator. (x is at the memory address immediately below c.)

p is the first oscillator state, 2N bits wide. It's more complicated than a Marsaglia oscillator because its design is a product of evolution, but it contains the components of one.

A is the first Marsaglia oscillator's multiplier. For example, this is (2^128-2^125-2^110-2^100) in the case of LMD4.

L is the array of (j+1) N-bit words whose hash to evaluate. (In all cases, L is 2^15 bits long. It's just a question of how wide we consider a word to be, and thus how many words L contains.) Note that L is indexed starting from 1 in Mathematica, but from 0 in the algo above.

q is the second oscillator state, 2N bits wide.

B is the second Marsaglia oscillator's multiplier.

M is a xor mask, essentially a cryptographically generated nonce, which will mask the hash. (Encrypting the hash with this mask would appear to be overkill, but it's dirt cheap compared to encrypting and taking the hash of the payload, so why not.)

z is the hash output (the digest) of L, which is 2N bits wide.

---

In this example, we'll set things up like this:

---

X0=0
C0=1
Y0=2
D0=3
L={1, 2, 3... (j+1)}
M=0

---

(M is 0 because nothing exciting happens with it anyway.) So what we're doing is just taking the hash of a series of incrementing integers, using seeds that also happen to be incremental. If you want to do something more complicated, you can modify the code to do so. Just Google around for the primitives I'm using, for example "mathematica array" if you want to learn how Array[] works,

OK let's write all this in a way that you can paste into Mathematica. (They probably have a free trial if you don't own it.) Note that all these text strings are intended to be interpreted as a single line, so if your text editor inserts line breaks, then remove them before pasting (Ctrl+V) into the Mathematica Kernel.

After the fact, you can print out individual values, for example the data block, L. (Just type "L".)

LMD4 Input

---

A=(2^128-2^125-2^110-2^100);B=(2^128-2^101-2^98-2^76);n=128;X0=0;C0=1;Y0=2;D0=3;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++,x=BitXor[x,y];p=(A*BitXor[x,L[[i+1]]])+c;x=Mod[p,2^n];c=BitShiftRight[p,n];q=(B*BitXor[y,L[[BitXor[i,((j+1)/2)]+1]]])+d;y=Mod[q,2^n];d=BitShiftRight[q,n]];p=p+(y*(2^n))+d;p=Mod[p,2^(2*n)];z=BitXor[p,M];Print[BaseForm[z,16]]

---

LMD4 Output

---

6f2fefec0cae3656703ceb0aed691a7d0d7d58c6bf42e053040a71eeeea525b3

---

LMD5 Input

---

A=(2^256-2^243-2^236-2^194);B=(2^256-2^220-2^206-2^183);n=256;X0=0;C0=1;Y0=2;D0=3;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++,x=BitXor[x,y];p=(A*BitXor[x,L[[i+1]]])+c;x=Mod[p,2^n];c=BitShiftRight[p,n];q=(B*BitXor[y,L[[BitXor[i,((j+1)/2)]+1]]])+d;y=Mod[q,2^n];d=BitShiftRight[q,n]];p=p+(y*(2^n))+d;p=Mod[p,2^(2*n)];z=BitXor[p,M];Print[BaseForm[z,16]]

---

LMD5 Output

---

25cace35c4330243a20f890f14704503d12f1d998146e01857167ba3d811300b52995621358cd9f92194810c3213c04c2f96a7867f9fa819e41ea73642d59230

---

LMD6 Input

---

A=(2^512-2^498-2^496-2^427);B=(2^512-2^481-2^404-2^362);n=512;X0=0;C0=1;Y0=2;D0=3;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++,x=BitXor[x,y];p=(A*BitXor[x,L[[i+1]]])+c;x=Mod[p,2^n];c=BitShiftRight[p,n];q=(B*BitXor[y,L[[BitXor[i,((j+1)/2)]+1]]])+d;y=Mod[q,2^n];d=BitShiftRight[q,n]];p=p+(y*(2^n))+d;p=Mod[p,2^(2*n)];z=BitXor[p,M];Print[BaseForm[z,16]]

---

LMD6 Output

---

a5f593b3e7b791959da4a0973cc319520925b996699452eeecc2a6ed98ee0cd0c9f770ca77c68748e85d29867f45d9900495aec0463c3418d228d1d1f7c9bdc583e22e63d0005b8ab113ff81f05ccbf595a9bd8b737c3c70bff40fe571234550c080a4f32e66f7908be8366edf75c186cede240c566415cce5c6d636e470c565

---

The encryption engine is left explicitly unspecified because these hashes are designed to satisfy the requirements for high entropy, high bit flip sensitivity, and irreversibility -- nothing more than that. LMD6 is used in the Karacell encryption algo, for instance. Karacell is the main motivation for putting these examples on the Web. Now you have readily accessible reference code, so that you can try to find serious weaknesses in them. Good luck!

GetLMD with Checksum Capability

GetLMD source code is here (and more specifically, here) on Github for Linux (32/64-bit), Mac (64-bit), and Windows (32-bit) now has the ability to calculate 8-bit, 16-bit, 32-bit, and 64-bit checksums over nested folders, in addition to LMD, LMD2, LMD3, LMD7, and LMD8. Precompiled binaries included. See readme.txt or run it (getlmd64 for X64 Linux, getlmd32 for X86 Linux, or getlmd.exe for Windows) for syntax instructions. As with LMDx, checksums are evaluated as though the file is a multiple of the checksum width, padded with high 0 bytes.

GetLMD, a File Hashing Utility

Want an easy way to find duplicate files, or check for errors? Try GetLMD. It's a command line utility that I wrote long ago, and only just got around to publishing. It was intended to demonstrate the LMD hash family, so the code is written in an obtuse manner which forgoes some obvious optimizations in exchange for clarity. Nevertheless, it's very fast. The output looks like this, for example:

GetLMD build 47
Computes the LMD/LMD2/LMD3 of a file or directory.
Copyright (c) 2012 Russell Leidich, all rights reserved.
http://leidich-message-digest.blogspot.com

D2E2C9132E17DF1A: getlmd/build.h
BE37DA2850485A67: getlmd/constant.h
94EED84F26B6CC2C: getlmd/COPYING
844D8481E6860212: getlmd/file_sys.h
5056B4444D7F617C: getlmd/getlmd.c
6E6A243555254A52: getlmd/getlmd.exe
9A74D885D069BF92: getlmd/getlmd32
F9EA958FDAC7F040: getlmd/getlmd64
373446334609A081: getlmd/linux32_build.sh
93E60B9867442314: getlmd/linux64_build.sh
253A2F6F4ED2A8BC: getlmd/readme.txt
59997B11FC9D6990: getlmd/win32_build.bat

476542E8D2313940 (Sum of file-size-hashed (LMD2)s modulo 2^64.)

The source code is included under the licensing terms explained in COPYING. It does, however, seem to work in a manner consistent with the hash definitions provided in this blog, and has been tested against the LMD2 and LMD3 reference code. See readme.txt for details. Really, this was all just intended as a demo, so the code could be much more elegant and performant. Nevertheless, it's quite useful.

For example, you can capture the hashes to a file, like this (in 64-bit Linux):

./getlmd64 your_folder >your_output_file.txt

Or detect duplicate files by looking for the same LMD twice in a row:

./getlmd64 your_folder |sort

I don't have time to do further development, but I'll try to help if you find any bugs. pkerjjy@gmail.com, without the fourth letter.

Enjoy, and by all means feel free to build something better with it!

The LMD4, LMD5, and LMD6 Secure Hashes

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.

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

---

Here, then, is the LMDx algo in terms of N, A, and B above; the seeds (X0, C0) and (Y0, D0); and the xor mask, M; where "x/y" denotes the integer quotient obtained by dividing x by y.

---

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

c=p/(2^N)

q=B*(y xor L[N, i xor ((j+1)/2)])+d
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 LMDx of the block is then given by z, which is 2N bits long.

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)

---

where L' is a (probably maliciously) modified derivative of L, because we could simply xor U to z.

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

The Reflexive Density Constant

Before proceeding with further discussion, it's useful at this point to introduce what I call the "reflexive density constant", or "R". This may sound totally unrelated to error detection and secure hashes, but bear with me.

What is R? The best way to define it is procedurally:

---

1. Set all N bits in a bitfield to 0.

2. N times, choose one of the bits in the bitfield at (true) random. Set the bit to 1, regardless of its current value.

3. Count all the 1s in the bitfield. Divide by N. R is the limit of this ratio as N approaches infinity.

---

There is an infinite expression tree for R, which I don't have time to investigate. So I approximated it using a true random number generator. It appears to be close to 0.6321...

This value appears to equal 1-1/e. (Isn't transcendental reverse approximation cool? Thank you, WolframAlpha!) [EDIT: This turns out to be correct, as proven here.] Granted, this could all just be an elegant coincidence, as I have no formal proof. Either way, I surmise that an infinite Bayesian logic tree is at the heart of R. [EDIT: Alternatively, one could use the Jytter userspace true random number generator to arrive at an empirical approximation of R.]

1-1/e also comes up in the online stochastic bipartite matching problem. Is this significant? I don't know and don't have time to find out, but maybe you do.

Anyway, what about the name? "Reflexive" refers to choosing N bits at random from a bitfield which contains equally many bits. "Density" refers to the fraction of 1s. "Constant" reflects the apparent constancy of R in the infinite limit of N.

Now, how does this relate to pseudorandom number generators (PRNGs), EDCs, and secure hashes? Well, it turns out that compliance with R is a very good measure of the quality of each of these:

R AND PSEUDORANDOM NUMBER GENERATORS

For a PRNG to look convincing, its outputs must mimic an unbiased true random number generator (TRNG). We can ascertain the quality of this mimicry by running the test above using the PRNG instead of a TRNG. The result should be close to R. If it's much less than R, then the PSNG is getting trapped in a small subset of possible outputs (a tight orbit). If it's much more than R -- in the worst case, 1 -- then it's starting to act like an out-of-order counter.

R AND ERROR DETECTION CODES

A good EDC requires a PRNG of the above criteria. Otherwise, who knows what data resonances might occur, which would weaken said EDC. All multiply-with-carry generators in the LMD family appear to adhere to within 1% of R.

R AND (SECURE) HASH FUNCTIONS

Consider the hash function H(L), where L is a message and H(L) is its hash. Given L', a derivative of L, which is probably only slightly different, e.g. a single bit flipped. We can then crack this hash by finding some integer U such that:

---

H(L)=H(L') xor U

---

Simply xor U to H(L'), and presto, L' appears to be legit. (The xor could be replaced by addition or some other operator, depending on the cryptographic context. The point is, if it's easy to find U, the "difference" of the hashes, then it's easy to crack the hash.)

We can also crack the hash by finding L' such that:

---

H(L)=H(L')

---

but in practice, because U is generally much shorter than L', it's easier to take L' as a given, and solve for U.

Now... how do we know how easy it is to solve for U, in the general case of a long hash? We don't -- at least, not precisely. However, by gathering statistics from similar hashes of tractable length (perhaps 24 bits or less, given the limits of desktop computer power), we can often extrapolate to hashes of similar construction but merely longer length. Is this foolproof? No. But it's probably the best that we can do, absent more computer power. (And if we had enough computer power to do a complete analysis of the real hash, then, prima facia, the hash would be of insufficient length to be secure.) At least, if the short hash turns out to be weak, then we know that the long hash is in jeopardy. If the short hash turns out to be strong, then we can attempt to try as many samples as possible, in order to bolster our faith that the real hash is also strong.

How does all this relate to R? Well, think of U as an N-bit integer, where N is equal to the number of bits in the hash itself. Then R tells us that ~63% of the 2^N possible U values are actually roots of the hash with respect to L vs. L'. The number of actual roots, divided by 2^N, is what I call the "root density", D. If D is not close to R, then we have a weak (or, suboptimally strong) hash. Why?

Here's where your brain has to twist... fasten your seatbelt.

First of all, remember that we can't gather statistics on a hash of "interesting" length because, after all, the length of the hash is meant to hamper all attempts to solve for U. So, we're solving for U on hashes of tractable length, but similar construction, in the hopes that the statistics are extapolatable to the actual hash in question. (It's easy to solve for U in the above case, for example. Just compute H(L) and H(L'), then xor them together. Depending on the cryptographic context, this process could be more complex, but the concept is the same.)

So just create 2^N versions of L', and count the populations of all associated values of U. What you get is a population histogram of U over all 2^N versions of L'. (The same process allows us to compare how H(L) differs from H'(L), where H and H' differ by only their pseudorandom seeds. Suffice to say, this technique can be applied to a wide variety of hash modifications.)

So the question is, how many roots (unique values of U) are there, compared to how many there could possibly be (2^N)? For example, if we find only 3 unique values of U, which occur over and over again, then the answer is 3/(2^N). If we find all 2^N values, then the answer is 1. I would suggest that we want the answer (D) to be as close to R as possible.

To understand why, first consider the extreme cases: 1 unique root, and 2^N unique roots. In the first case, it might be that the binary equation trees for deriving U from L and L' (and yes, there are such equations, despite the fact that you couldn't write them down in a lifetime) might have a hidden simplicity, which a smart computer could discover. In the second case, a comparable argument prevails: the set of solutions is "too perfect", such that every possible root is in fact a root. In this case, there might be a boring linear relationship between L, L', and U. In the absence of any other information, then, it's compelling to believe that the binary equations reach maximum complexity when D=R.

The point here is wider than simply creating memory capacity pains for classical computers attempting to subvert the hash. There's a quantum computer issue here, as well: if the roots appear to have been chosen at random, then it stands to reason that a quantum computer will behave as if they are in fact arranged at random, which is to say that they will represent (unstable) excited states for the wave function, eluding the quantum computer's attempts to discover the global minimum, i.e. the particular value of U which legitimizes a particular L'.

But there's one other consideration for the quantum case: root multiplicity. Essentially, the larger the ratio between maximum and (nonzero) minimum root multiplicity (the "root multiplicity ratio"), the greater the odds that a quantum computer will find the root with maximum multiplicity.

What distribution of root multiplicities would we expect if we chose 2^N values of U at random? That's a question related to Poisson distributions and beyond the scope of this blog. (I call it the "Poisson Criterion".) Suffice to say that if my extrapolations from shorter hashes are valid, then LMD4, LMD5, and LMD6 all exhibit root multiplicity ratios close enough to what a Poisson distribution would dictate, as to be unhelpful to the best known attack method, which is a birthday attack.

Got it? Good. Now we can talk about secure hashes...