Wednesday, January 30, 2013

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!

No comments:

Post a Comment