Yasmarang
May 25, 2004 by Ilya Levin
There was a 32-bit hash function I played around some time ago. Not a big deal, nobody needs such hashes in any case, even back in these days. However, the benefit of this hash was its easy conversion to a PRNG, and this is why Yasmarang came up as a replacement.
Yasmarang is a simple pseudorandom number generator with a small footprint and good statistical characteristics. Yep, yet another small random number generator but do not worry. There would not be any the best ever and the rest of usual blah-blah-blah here. Instead, here is the portable C implementation:
unsigned long yasmarang(void)
{
static unsigned long pad = 0xeda4babaL, n = 69, d = 233;
static unsigned char dat = 0;
pad += dat + d * n;
pad = (pad<<3) + (pad>>29);
n = pad | 2;
d ^= (pad<<31) + (pad>>1);
dat ^= (char) pad ^ (d>>8) ^ 1; /* changed, see update below (1) */
return (pad^(d<<5)^(pad>>18)^(dat<<1)); /* changed, see update below (2) */
} /* yasmarang */
The output is a 32-bit random integer, and it passes all the tests of randomness from Diehard Battery. Even though Yasmarang looks like a linear feedback congruential shift generator of some sort :)
Here are the fist 20 sample output values, generated by the code above. Use these as the reference while translating the above code to another programming language:
BF5B0806 7334585E BC0C7B9D BDEC5ADE A5F12D68
978CA203 8CE2E203 37B2CE15 1B986BD2 2F3F1111
40197A2D 31057AB0 579401A4 1CF95A3C 744882AD
E6179123 9E1CAC6A 0D77D709 FB34195F 77831C40
Update
There are two points were highlighted in the originally proposed variant during the discussion about Yasmarang on sci.crypt.random-numbers.
Despite the fact Yasmarang passes all tests from the Diehard suite, it demonstrates ambiguous results on Gorilla and Collisions difficult-to-pass tests (something that referenced as improved and stringent tests over the Diehard ones).
Muddle would avoid this ambiguity. Yasmarang was designed to be able to muddle together with input data from an external source by having 8 bits from the input stream confused by XOR with dat as a last step of the generation cycle. The input data stream does not have to be random or even variable. A single non-zero bit is sufficient.
The additional ⊕ 1 at (1) let Yasmarang pass all tests: the classic Diehard, and the tough tests.
Another point was the fact that it is possible to recover Yasmarang internal state after the first cycle and subsequently is possible to predict its output.
Yasmarang was designed as a source of randomness in a first place, with cryptographic security provided mostly by its usage.
For example, we may implement a cryptographically secure stream cipher by using two differently seeded and cross-muddled instances of Yasmarang, where the output of each generator is confused with each other and a data stream. The value of pad shall not be revealed to make Yasmarang a reasonable secure primitive. The proposed obfuscation method is shown at (2) above.
However, mind that Yasmarang is not meant to be a cryptographically strong PRNG alone. It is simple impossible for any pseudorandom number generator with such small internal state.