Mark Spitzer was asking how to do a hash in hardware. The file nandhash.c simulates a hash I've designed for hardware.
It has 2x4 blocks of 4x4 bits apiece, for a total internal state of 128 bits. A single round first XORs a few bits to other blocks horizontally and vertically, then does a reversible nonlinear mixing of each 4x4 block. The 4x4 mix is actually a linear LFSR on bits 0..7 that XORs 3 or 4 bits per bit, while doing ~b^((w&x)|(y&z)) on bits 8..15, then swapping bit i with bit 15-i. I count a single round at being 9 NANDs deep. I skimped on long wires because I've heard they're slow and take lots of room.
To measure it, I started from a random state, made a copy with one bit flipped (0,0,14, which measurements suggested was the worst case), running both for n rounds, then XORing the results. I updated a count for every bit that changed. I did that 100,000 times, divided by 100,000, to get a probability p for each bit. Ideal is p=0.50.
Bits affected on average by modifying bit (0,0,14), after zero rounds:
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Bits affected on average by modifying bit (0,0,14), after one round:
0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Bits affected on average by modifying bit (0,0,14), after two round:
0.00 0.00 0.00 0.37 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.38 0.37 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Bits affected on average by modifying bit (0,0,14), after three rounds:
0.46 0.53 0.47 0.62 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.14 1.00 0.23 0.74 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.37 0.37 0.38 0.38 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.37 0.00 0.37 0.47 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.27 0.14 0.14 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.14 0.14 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.38 0.38 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.37 0.37 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Bits affected on average by modifying bit (0,0,14), after four rounds:
0.49 0.50 0.50 0.50 0.37 0.00 0.00 0.00 0.37 0.00 0.00 0.00 0.37 0.00 0.00 0.00 0.52 0.49 0.52 0.51 0.37 0.14 0.00 0.14 0.37 0.14 0.00 0.14 0.37 0.14 0.00 0.14 0.47 0.51 0.52 0.50 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.49 0.50 0.47 0.52 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.45 0.44 0.39 0.42 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.44 0.44 0.51 0.45 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.76 0.30 0.65 0.36 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.28 0.70 0.36 0.66 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Bits affected on average by modifying bit (0,0,14), after five rounds:
0.48 0.50 0.50 0.50 0.50 0.05 0.18 0.00 0.49 0.05 0.18 0.00 0.50 0.05 0.17 0.00 0.50 0.50 0.50 0.51 0.49 0.31 0.10 0.22 0.49 0.31 0.10 0.22 0.49 0.31 0.10 0.22 0.50 0.50 0.50 0.50 0.23 0.37 0.14 0.37 0.24 0.37 0.14 0.37 0.23 0.37 0.14 0.37 0.50 0.50 0.50 0.50 0.37 0.23 0.18 0.14 0.37 0.24 0.18 0.14 0.37 0.23 0.18 0.14 0.46 0.46 0.52 0.51 0.34 0.05 0.05 0.00 0.34 0.05 0.05 0.00 0.34 0.05 0.05 0.00 0.52 0.51 0.52 0.52 0.73 0.41 0.10 0.33 0.73 0.41 0.10 0.32 0.73 0.41 0.10 0.33 0.50 0.50 0.50 0.50 0.23 0.00 0.23 0.00 0.24 0.00 0.24 0.00 0.23 0.00 0.23 0.00 0.53 0.50 0.50 0.50 0.00 0.14 0.20 0.14 0.00 0.14 0.20 0.14 0.00 0.14 0.20 0.14
Bits affected on average by modifying bit (0,0,14), after six rounds:
0.50 0.50 0.50 0.50 0.50 0.25 0.34 0.18 0.50 0.22 0.33 0.18 0.50 0.22 0.33 0.18 0.50 0.50 0.50 0.50 0.50 0.42 0.26 0.27 0.50 0.41 0.24 0.27 0.50 0.41 0.26 0.41 0.50 0.50 0.50 0.50 0.38 0.50 0.50 0.49 0.38 0.49 0.50 0.49 0.38 0.49 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.50 0.29 0.49 0.50 0.50 0.29 0.50 0.50 0.50 0.29 0.50 0.50 0.50 0.50 0.51 0.25 0.34 0.18 0.51 0.28 0.35 0.18 0.51 0.27 0.33 0.15 0.50 0.50 0.50 0.50 0.50 0.42 0.35 0.32 0.50 0.42 0.37 0.32 0.50 0.42 0.35 0.32 0.50 0.50 0.50 0.50 0.51 0.35 0.52 0.35 0.51 0.35 0.52 0.35 0.50 0.35 0.52 0.35 0.50 0.50 0.50 0.50 0.35 0.48 0.51 0.40 0.35 0.48 0.51 0.40 0.35 0.48 0.51 0.40
Bits affected on average by modifying bit (0,0,14), after seven rounds:
0.50 0.50 0.50 0.50 0.50 0.49 0.42 0.39 0.50 0.44 0.50 0.43 0.50 0.39 0.42 0.41 0.50 0.50 0.50 0.50 0.50 0.49 0.39 0.37 0.50 0.47 0.50 0.37 0.50 0.46 0.39 0.50 0.50 0.50 0.50 0.50 0.48 0.50 0.50 0.50 0.49 0.50 0.50 0.50 0.49 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.46 0.50 0.50 0.50 0.46 0.50 0.50 0.50 0.46 0.50 0.50 0.50 0.50 0.50 0.48 0.49 0.47 0.50 0.49 0.50 0.48 0.50 0.48 0.49 0.45 0.50 0.50 0.50 0.50 0.50 0.48 0.48 0.40 0.50 0.48 0.51 0.39 0.50 0.47 0.48 0.45 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.46 0.50 0.50 0.50 0.46 0.50 0.50 0.50 0.46
Bits affected on average by modifying bit (0,0,14), after eight rounds:
0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.50 0.50 0.49 0.50 0.49 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50
Bits affected on average by modifying bit (0,0,14), after nine rounds:
0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50
At 9 NANDs deep, you might be able to do multiple rounds per cycle in hardware. To get a 32-bit hash, you could initialize with 16 bytes, repeatedly run four rounds then XOR in another 16 bytes until you've consumed the whole key, then run eight rounds and report any 32 bits as the hash value. To get a 64-bit hash you ought to do 5 and 9 rounds instead of 4 and 8.
I don't think this is optimal. I don't know if it's even competitive with other noncryptographic hardware hashes out there. I don't know whether you can do a round in a cycle, let alone multiple rounds per cycle. Obviously five rounds per cycle would be nice. There are probably complications that would come up if you actually made hardware implementing this that I haven't thought of.
I haven't tested this hash in reverse yet, though the reverse is the same as forward except for the LFSR part of the 4x4 mix.
A pseudorandom number generator for simulations
Evolution and human genetic diversity
Cartoons from college: "Overload" and "Spare Change"
Table of Contents