# Random Number Generator based on AES CTR

I've just about done tinkering with an open source DRBG, and I sure would appreciate a bit of advice from this community. Here's the link to the project, hosted at codeproject.com.

It is written in C#, the code is clean and well commented.

The design criteria:

1. The same seed must generate the same random output each time.
2. It must be fast.
3. It must be extremely difficult to unwind.
4. It must produce excellent random output.

In its simplest form, it is an AES CTR using block chaining. To address criteria #3, I have added methods that reset the state of the key/iv/counter by whitening them and then using the SHA256 hash value. An example of 'whitening' the data:

private byte[] ExtractArray32(byte[] SubBuffer)
{
UInt32[] tmpNum = new UInt32[8];
UInt32[] arrNum = new UInt32[16];
byte[] data = new byte[64];
Int32 ct = 0;
// copy first array in
Buffer.BlockCopy(SubBuffer, 0, tmpNum, 0, 32);
// get the first buffer table index
UInt16 iter = ExtractShort(tmpNum[0], 10);

// randomize the bits
for (int i = 0; i < 8; i++)
{
arrNum[ct++] = ~tmpNum[i] ^ SEED1024[iter];
iter = ExtractShort(arrNum[ct - 1], 10);
arrNum[ct++] = tmpNum[i] ^ SEED1024[iter];
iter = ExtractShort(arrNum[ct - 1], 10);
}

// copy it to byte array
Buffer.BlockCopy(arrNum, 0, data, 0, 64);
// get the hash
return ComputeHash64(data);
}


I know some people don't like it when someone posts code here, but it makes it so much easier to explain with a visual representation…

So what's happening here, is a 32 byte value, say the original key, is copied to a uint32 array (8 * 4 bytes), then copied into a new uint32 array (16 * 4 bytes), on the first interval, the value is reversed, on both, the value is XORed with a uint32 from a 1024 * uint32 table of random values. The table index is the last 10 bits of the previous value (0-1023). This is how I whiten and expand the array so that it aligns with the 64 byte block size of SHA256. The return is the hash value, which becomes the new value.

Questions:

1. Is this a good way to whiten the data? Is there a better way?

I do realize that flipping a single bit will give me a completely different hash value, but this goes towards criteria #3, make it difficult to unwind.

There are 4 different prototypes, their primary difference being how and when a state reset occurs; one is configurable via a property (10Kib default), another resets after every 4 block transforms (64 bytes), another resets at random.

2. Is there an ideal interval at which an AES CTR generator should be reseeded? Is reseeding too often introducing patterns that might be exposed by some form of differential analysis?

I think the best way to get a handle on what I've done, is to just check out the article, nothing too complex, but it really could do with some scrutiny before people start using it in the wild, which leads me to my last question..

3. How can this be made stronger? How would you improve upon this? ..and are there any serious flaws in the implementation?

I think the most important criteria is that, should an attacker get a portion of the random output, say message data from an xor cipher, it must be as difficult as possible for the attacker to unwind it back to the initial state, given that any changes do not seriously impede upon the other criteria..

Here's the new algorithm:

-
Have you considered the CTR_DRBG from csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf ; that's mostly your idea, with the details worked out –  poncho Jul 9 at 16:57
Actually the sample application tests against my C# version of the bouncycastle 80090 implementation and RNGCrypto. The sample program contains an Ent class that does some basic comparisons between the engines and mine comes out on top most of time, (small margins, but still..). I have also run output through diehard and the NIST test suite with good results, so entropy seems to be covered as a criteria.. What mine does that the 80090 spec does not, is introduce some variable state resets independent of user scheduled reseeding.. (again, fulfilling criteria #3) –  John Jul 9 at 17:02
If you have anything that shows that CTR_DRBG is computationally distinguishable from a truly random source (given an unknown seed), I would strongly urge you to publish it. I am personally skeptical that you have any such evidence. –  poncho Jul 9 at 17:11
I have no such data, nor claim to, my intention is to create my own implementation following the guidelines I've set forth here, (which strive to be a rigorous standard).. nothing more, nothing less. My implementation seems to get very good results, now I am asking for advice from people with far more expertise then I.. that's all –  John Jul 9 at 17:17
I am working on a DRBG using similar principles, (hash + ctr) but am doing it in a very different way, (security over speed). I would recommend posting a block diagram of the DRBG operation, it makes it easier to see what it is doing as a whole (very important) –  Richie Frame Jul 9 at 20:14

First, the obvious advice is not to use this in practice. Rolling your own is fine for learning, but you should use standard primitives when you need actual security. E.g. one from SP 800-90A which poncho linked in comments.

Now, some observations. I haven't read all your code, so I may misunderstand things.

1. Is this a good way to whiten the data? Is there a better way?

Looks unnecessarily complex. AES output is already white, unless AES is broken, so you shouldn't need to do any whitening on the output. The massive table which you use for stretching doesn't seem very secure. For example, you are using secret array indices, which may allow for timing attacks.

2. Is there an ideal interval at which an AES CTR generator should be reseeded?

A normal AES generator should be reseeded after $2^{48}$ blocks of output at the latest, according to NIST. That number prevents the attacker from having more than a $2^{-32}$ probability of an advantage.

Is reseeding too often introducing patterns that might be exposed by some form of differential analysis?

If you have a good source of numbers to feed it, you can do it often, but then why not use those numbers directly? (Performance, maybe, in which case you want relatively infrequent reseeding, but much more often than required is possible.)

Seeding with bad input should only hurt if you use an update system that overwrites previous state and can lead to identical key & IV.

3. How can this be made stronger? How would you improve upon this? ..and are there any serious flaws in the implementation?

I would rip out the whitening stage, for the reasons I mention above, and use AES output as the random output. If you want frequent reseeds and don't have access to a fast TRNG, you could leave an SHA-256 loop for updating the AES key.

Alternatively, if security is the objective, decouple the hash based RNG from AES and run them independently, e.g. XORing the outputs.

A couple more things that seem unnecessary: you are XORing two halves of an SHA-256 output together – using one would be as strong unless SHA-256 is broken; you are XORing the AES counter into the IV, when I think you would be better off treating it as a single counter with a longer period.

-
Thanks for the comment otus.. I think you do misunderstand a few things.. output is AES transform, that is not whitened. Whitening is applied to state variables during internal state reset only. IV and counter are xored because this is block chaining, I have found this improves random output significantly. I use SHA for state reset, because I do not want overlap, and do not want to use data directly from output stream. No doubt, there are some unnecessary calculations. But results are hard to argue with, and this nets better test results (with Ent), then the 80090DRBG or CryptGenRandom –  John Jul 10 at 12:38
As for the table, yes this does concern me, it is a recent addition, and replaces some arbitrary shifts and unary reversals that accomplished that task. I just didn't want to lose any byte resolution, so I thought that might be a better way, as well, a user can build their own table with the method I included, creating a unique distribution.. but you're right, and that may go. Xoring hashes and counters, you say why, I say, why not? Excessive? Of course.. but there is a straight CTR method in class if speed is what you're after.. I am looking at improvements though, and things will evolve.. –  John Jul 10 at 13:03
@John, ok, your use of "whitening" confused me. Regarding IV and counter XOR, that cannot matter unless AES CTR is broken (assuming I understand what you are doing), so could you link to e.g. test results that show a difference? (Cannot matter for sequences shorter than the counter period that is. For longer ones it should be worse than using a larger counter.) –  otus Jul 11 at 8:31
I don't really see the point. If your ultimate output is AES_k(X), where X is not a perfectly random number, you will still only get as strong security as AES gives you. Further, unless AES is broken that's more than random enough. I don't know Ent tests, but I would take a look at your significance levels if I were you: it may be that you are simply seeing noise in the test results if some of your tweaks seem to change something. –  otus Jul 11 at 13:18
@John: The statistics tests are best seen as a hurdle to pass for your design. They are important, but do not quantitatively assess randomness beyond "yes that looks random, there doesn't seem to be a way to tell the difference". Once you pass those tests, other properties of the PRNG are relevant. Such as performance. And analysis of the construction. –  Neil Slater Jul 13 at 20:23