# BouncyCastle style ThreadedSeedGenerator

I've written a BouncyCastle style threaded seeder and was wondering about the predictability of the data the program generates.

The reason I'm not simply using BouncyCastle is because security isn't a concern, I don't want to use a whole library just for one function, and this code is MUCH faster.

The idea is to make several threads which operate on a circular buffer (a simple array), where each thread performs a different operation on the data in the buffer. The randomness comes from thread scheduling irregularities in the OS.

How much randomness can I expect from a mechanism like this?

C# code:

using System;

{
static public ulong[] buffer = new ulong[1024];
static public bool doThread = true;

{

}

{
{
};

b.Start();
}

static private void Add()
{
int i = 0;

{
buffer[i & 1023] += (ulong)DateTime.UtcNow.Ticks;
i++;
}
}

static private void Multiply()
{
int i = 0;

{
buffer[i & 1023] *= 6364136223846793005;
i++;
}
}

static private void Xorshift()
{
int i = 0;

{
ulong y = buffer[i & 1023];

y ^= (y << 13);
y ^= (y >> 17);
y ^= (y << 5);
buffer[i & 1023] = y;

i++;
}
}
}

• Note that CPU cycles are not free anymore; sleeping CPU's consume less power when idling, and cache swaps are still necessary even when running on low prio. Personally I would not like the chosen solution much. – Maarten Bodewes Dec 6 '18 at 15:13
• @MaartenBodewes No, it's majorly sub-optimal to put it nicely. It won't accumulate early enough in the boot cycle for the OS to use it naively, especially as C#. The generation rate is unreliable (although it does generate), and it can be relatively slow due to massive necessary safety factors. It's a niche solution, but if you've got the time to run it, it doesn't require external hardware. – Paul Uszak Dec 6 '18 at 16:15
• If you need unpredictable data then use the normal secure random number provider for whatever platform you're targeting. (RNGCryptoServiceProvider, getrandom, arc4random_buf, SecureRandom, os.urandom, etc.) – Future Security Dec 6 '18 at 23:38
• If security really isn't a concern (you really only want to prevent two processes from using the same random number sequence), then read a small number of bytes from those same secure random number sources to seed a PRNG (cryptographic or not-secure-but-high-quality). That PRNG can be used to seed other PRNGs. Avoid low quality PRNGs for the seeder. Don't do something like use an LCG to seed other LCGs or an XorShift generator to seed other XorShift generators. Copying the algorithm used by ThreadLocalRandom in jdk9 would work well in terms of speed and quality. (For an insecure RNG) – Future Security Dec 6 '18 at 23:55
• It seems like you'll want to look into HAVEGE or JitterEntropy. – forest Dec 7 '18 at 8:06

## The approach is deeply flawed in many ways.

1. It is very plausible that the whole buffer is returned at zero under heavy load, which is something that an attacker can often intentionally cause (e.g. with a flood of network traffic requiring high CPU load; starting a number of https connections comes to mind). That's likely to be a practical disaster.
Mechanism: the three threads launched by ThreadedSeeder are set to Lowest-priority, thus it is reasonable that they won't do anything before the Thread.Sleep(10). If the machine has higher-priority-than-Lowest things do during that pause, execution can proceed to doThread = false before the Add thread has ever tested doThread, thus with Add performing nothing related to buffer. The same could hold for Multiply and Shift too, but that's immaterial, as these threads can not un-zero buffer even if they run.
2. More generally there is little insurance about the number of times DateTime.UtcNow.Ticks is called; that could be very few, including less than once per buffer entry, thus always leaving all the other entries at zero. The busiest the machine, the more likely it is that a buffer entry has no, one, or very few readings of DateTime.UtcNow.Ticks to influence it.
3. I see no mechanism preventing Multiply or Xorshift from competing with Add about what element of buffer it operates on, and thus void a change Add makes meanwhile. This is an uncontrolled race condition, and it can loose some of the entropy gathered.
4. DateTime.UtcNow.Ticks can be closely approximated by adversaries. That's supposed to be the UTC time, which is not a secret. Further, common mechanisms such as RFC 7323 high-resolution TCP time stamps allow to find what a particular machine believes the UTC time is, even when it is poorly synchronized. And when the machine is under light load, with one CPU running each thread including Add at full blast, the difference between readings will be reasonably repeatable.
5. The transformation made from DateTime.UtcNow.Ticks to what is in each element of the buffer is one among relatively few public transformations. And each of these possible transformations is trivially reversible (modular multiplication by an odd constant modulo a power of two is reversible in Multiply, as well as each of the three bitwise operations in Xorshift). Combined with 4, it trivially allows a very selective distinguisher on each buffer element output whenever there is only a single DateTime.UtcNow.Ticks that influenced it, also revealing which transformation occurred. It looks like this could be extended to a few such influences.
6. Neither the code nor the text of the question shows any effort to create explicit diffusion of the entropy gathered: elements of buffer are never mixed. Absent such mixing or/and post-conditioning before use of buffer, some degree of 2/4/5 can be a practical disaster.
7. Timing execution won't gather any entropy in some precisely controlled execution environments, including VMs/simulators used by hardware engineers or reverse-engineering of malware. Ultimately, the state of buffer on output, and whatever is deterministically derived from that, will dependent only on when the task is launched.
• #7. You'll have seen my answer @ CS. Try that java nanoTime() snippet. It really does work. How can [buffer] isolate itself from those variates simply by encapsulation within a VM? The implications would be huge. A C# program would suddenly become entirely deterministic, which even a real time OS isn't. Thorham's technique exploits OS jitter to amass entropy into [buffer], as do HAVEGE and my toy nanoTime() example. I think the weakness of them all is that unpredictable jitter is itself unpredictable. Perhaps that's meta-stability(?) – Paul Uszak Dec 7 '18 at 17:14
• Don't forget that System.nanoTime() always runs in a VM. – Paul Uszak Dec 7 '18 at 17:15
• @PaulUszak “It really does work” — only on certain types of hardware under non-adversarial conditions. An assumption of non-adversarial conditions in cryptography is completely irrelevant. – Gilles Dec 7 '18 at 20:37
• @Gilles Actually, not everyone shares your opinion. Bernstein's view is that most greatly over egg the security concerns regarding RNGs and the manipulation of input entropy. And don't forget, Arduino's Entropy Library works and that's a very slow micro controller. So I think we have more wins than fails for nanoTime() et al. – Paul Uszak Dec 8 '18 at 15:44

I believe this approach will work on any computer given enough runtime because computers don't execute the same task in exactly the same time interval each run. Cache, other threads competing for CPU cycles, CPU temperature and throttling, etc. all come into play in this.

Unfortunately it is hard to estimate how much runtime is enough. I did a similar setup recently but instead of using a race condition between threads, I had one thread race a timer.

As I recall, my final version runs xoshiro128+ for about 100 microseconds, then cycles through the 128 bit state 5 times total, one bit at a time, flipping the bit or not depending on the parity of the timer in nanoseconds. I decided, with no evidence to back it up, that all of this might be worth 1 bit of entropy, so I set my RNG to repeat the above 64 times, after which it would have produced a good 64 bit seed for an RNG. I figure the whole process would take under 10 miliseconds.

I created a loop that set up my RNG and started the timer each time, emulating a cold boot. And each time, I had it push the resulting speed into a sqlite database. Many hours and about 4 billion seeds later, I had 1 collision, which seems in line with the birthday bound.

But removing the bit-by-bit bit flipping? That version generated thousands of collisions in just a few million seeds. Pure garbage.

So in general I would say the data race approach can work but that it's challenging to properly balance speed and entropy in this setup.

• If you can handle Java, try this doozy. It's a much simpler implementation of HAVEGE/Thorham's technique. Run it and look at the file. Do some tests. Mine gets ~5 bits/byte and surprisingly passes 4/5 of the ent test tests. I used spinning discs though. Your's will probably differ but it accumulates pretty quickly. It a valid proof of concept. – Paul Uszak Dec 8 '18 at 15:06
• I still use spinning disks as well. Not at all sure how well it would work with SSD, but it's a very nice, simple approach indeed. I'm not where I have access to my computer just now, but in a couple days I'll port the same concept to Rust. I'm sure I'll get very similar results to yours. – WDS Dec 8 '18 at 15:47
• Great. Huge tip: It works better in Java as written because I deliberately didn't use buffered IO. I did the same code in Python and the entropy rate is much lower as Python buffers natively. A feeling in my water is that a significant component of the jitter occurs accessing the HD. After all, there's a lot of physics and inertia zipping the heads about. – Paul Uszak Dec 8 '18 at 17:51
• The problems will start when you try to quantify what you've got. You can see from my thrashing that it's heresy to attempt to measure it. Perhaps it's like religion? So you'll ask how much entropy did I get and which method is more efficient, and then the screaming and nashing of teeth will start again :-) – Paul Uszak Dec 8 '18 at 18:08
• @PaulUszak Rust doesn't natively buffer either, but I think I'll try it in Java and Rust both, and maybe pure Asm for kicks, and see what I get. I recall a great document I saw linked recently where I'm fairly certain hard drive latency was one component in /dev/random, so I'm sure it's enough entropy to be worth the effort. But even Schneier gave up trying to estimate entropy when he gave up Yarrow for Fortuna, so no doubt it's very difficult to do. – WDS Dec 8 '18 at 18:54

In a nutshell, there will be entropy generated but you can't really predict it's rate. That said, it might be of the order of a few percent, based on experience. I got 10% but that involved much more computation and thus CPU jitter.

You need to measure it empirically. So run your buffer in a long burst, then write that buffer data to a disc file. Repeat to get say 100KB of data. Then find the strongest compressor you can. I use cmix, it's one of the stongest compressors in the world but requires a lot of RAM (32GB). Compress the data file, and the compressed size will represent the entropy content. For safety, you might divide that value by 2.

You also need to then increase that disc file in steps, making it longer and longer. Re-compress and the entropy should rise proportionately, proving that the entropy is not simply repeating itself.

A few percent entropy rate may not seem a lot, but it accumulates very quickly. So 0.01 bits/byte adds up and soon you have enough for a 256 bit seed/key. With that thing you can then generate all the randomness you need. Simply SHA-256 more than 64 bytes of entropy and you're done.

I advise you to try this ASAP (today) and convince yourself that it works. Also have a look at CPU Time Jitter Based Non-Physical True Random Number Generator. It's a working implementation, but your results will differ.

Note: You have to use compressive means to measure the unknown entropy as it will be highly correlated. You have no real alternative as the common Shannon log formula won't work on this such data. I've used this method previously and it works well. There are decorrelation techniques often used that aid the application of Shannon's formula, but you don't have go down that route.

• As has been said before, compression can only be used to detect obvious patterns. It absolutely cannot be used to empirically measure entropy. It's a useful part of a number of algorithms that can detect failed noise sources, but using it to detect entropy is foolish. For example, how would it possibly realize that the keystream from a stream cipher given a null seed is not entropic? – forest Dec 7 '18 at 7:48
• @forest H = |compress(jitter sample)| – Paul Uszak Dec 7 '18 at 16:17
• If you are an expert, then could you answer forests question and explain what part of the comments were wrong, rather than just simultaneously accusing him of logical fallacy while committing a logical fallacy (appeal to ethos)... – Ella Rose Dec 7 '18 at 18:00
• @EllaRose Hi. None of his comments were wrong per se. It's just that they were comments about entirely the wrong thing. He seems to have found a stream cipher somewhere, whilst the question is about OS jitter as a consequence of thermodynamic laws. You're not denying the laws of thermodynamics are you? He also seems to have some issues understanding Shannon's theory of entropy as irreducible information content. I've linked him to the wiki & quora pages, but to no avail. Festinger said that a man with conviction is a hard man to change. I respect that and welcome the discourse. – Paul Uszak Dec 7 '18 at 18:36
• The comments were not about the wrong thing: Forests comment demonstrates a situation where data with 0 entropy is incompressible by your recommended testing method, which by your argument implies that the sequence should have maximum entropy. This proves the recommended technique cannot accurately measure the entropy of data. I know that this has been explained to you before, by many users. When everyone understands entropy to have definition A, and you are the only one that thinks it has definition B, at some point you surely must consider that you might be wrong, instead of everyone else... – Ella Rose Dec 7 '18 at 19:08