[Cryptography] An interesting little pseudorandom number generator

[Jon Callas]

I like it, it's clever.

Comments:

* Whiny nit: when you write C-like pseudocode, avoid "int" or "long" because we don't know how big they are. The days (and implementations) in which "int" was 16-bits are long gone; I am presuming you're not doing that and yet when I searched for "size of an int in C" that's what I got from the top hit, even today, sigh. For pseudocode you can say something like "u32" and we'd know that you mean an unsigned 32-bit quantity. 

* You're absolutely right that it's hard to do these things so that someone else can't break them. This is clever and pretty, but so is RC4. It's perhaps the most elegant cipher I've ever seen, and yet it was ultimately broken by the same thing Jacob Munch-Anderson noted, a non-linearity in the output. So that's a concern.

* A PRNG is ultimately a pseudorandom function, which we usually call a PRF. That's what we want, mathematically pseudorandom output, even if there are other issues. Decent block ciphers are decent approximations of PRFs, a pseudorandom permutation (PRP). Decent hash functions are also decent approximations of PRFs. This is why counter mode gets used as well as some form of iterated hashing. They're also in hardware, which makes them fast, too. Thus, from an engineering standpoint, those are better.

* From an aesthetics standpoint, this is pretty, and yes, you could probably make it be the core of a cipher which could then be the core of a hash function, bringing it all full circle. One of the things we know best is that you can iterate a crappy function and get a strong cipher out of it. You could either Feistel this, or make an SP network out of it, and it's likely that with enough rounds it would be completely secure. The issue is then knowing how many "enough" is. Since the only real mixing function you're using is addition, you probably need a lot, and maybe an unbounded number of them. 

ARX design uses all three because their properties combine nicely. XOR provides some non-linearity horizontally, but vertically (bit-slice columnarly) is addition without carry for each bit column and thus addition becomes a majority function via carries. Rotates are good for what I think of as un-sticking things as the majority property of addition only carries (pun intended) leftward.

I think you need something else in there to make it really be secure, but it's pretty. I like pretty functions. Sadly, though, the things that make functions pretty are often symmetries that make cryptanalysis possible.

	Jon