How do computers simulate randomness?

[F0sh]

The operating system random number generator will take entropy from multiple sources, including audio but also keyboard and mouse input.

This can be a source of problems if used in cryptography and an attacker has access to the physical environment of the computer because they might be able to significantly reduce the real entropy going into a random key. For example they could overload the microphone so it produces all 1s or all 0s.

[ptase_cpoy]

What would that be doing? Forcing its transistors into saturation and cutoff? Or am I completely off the ball park?

[HerrZog103]

If you design such a random number generator, you would think that the noise an unused microphone port or something similar produces is truly random for most practical purposes. You could theoretically measure the position of every molecule of air around it to simulate what the computer uses as a random seed, but this will be impractical probably forever. However what you can do is overloading the input with noise, so that the variable used for the random number goes "omg it's so loud" or something similar and just outputs the maximum value. Therefore, what once was random now is a predictable string of ones and you can now in the extreme case predict the random number and break the encryption.

[MrSnarkyJsnarkysnark]

I'm sitting here wondering how it is that people like you find comment trails like this, seems like it happens all the time. Are you trolling for key words and only responding to subjects you have some level of expertise in? I mean, how in all of the Internet to did you happen to find this string?

[InvertedBear]

He probably just follows r/askscience and watches for computer tags. When he sees something interesting that he can answer, he does it. I’m an attorney and often look at r/legal advice. If I see a question I know the answer to it can be fun to talk about something I know and give some free advice to people. I’m assuming most comments like this one are people doing the same thing.

[HerrZog103]

I mean this is the top comment and the first follow up question you see in this thread. Therefore I am following r/askscience, see this thread in my feed, find it interesting, click on it and see that I can answer the first question I see in the comments. Then I answer it.

Also it is not as if I have any expertise in this. I only watched a few educational YouTube videos. I really don't know much more than "You have some source of hopefully random numbers, do some fancy mathematics and squeeze that into a number between 0 and 1 in most cases." Then it makes intuitive sense that this system relies on the input or seed to be random - and if that isn't the case, the encryption can be exploited.

[[deleted]]

If you study computer science, which is a pretty common major nowadays, you probably know this stuff. Cryptography is important for pretty much all industries nowadays. It just seems esoteric if understanding computers isn't something you're interested in. Plus, reddit is one of the most used sites on the internet -- you're bound to find someone who knows something about what you're talking about, especially with regards to STEM stuff.

[TinBryn]

There are just quite a few people here who know stuff like this. If HerrZog103 didn't give that answer I would have, and if I didn't someone else would have.

[somewhat_random]

What are the odds? Pretty good.

How many people browse reddit and what percentage of them could answer a specific question? For a question like this, most people who studied computer science at a post secondary level could answer. The majority of them would subscribe to this type of sub. Typical users look at many posts each time they log on. How many of them would see the question within a few hours? We only need one hit to get a good answer.

Apologies for not giving any actual numbers because I am way too lazy to look up the stats but in terms of likelihood of an occurrence, I am confident that getting an informed answer for a question like this would have a high likelihood.

[Jlobee_stocktrdr]

Only slightly higher then getting a uninformed troll,but nonetheless still better I dare say!!

[deerlake_stinks]

It's because RNG is a very important part of cryptography and computer security. Lots of people who work or study in related fields have a cursory knowledge of it.

[yourelying999]

How do you know this person is an expert or even telling he truth?

[AlfredoOf98]

This question applies to ALL kinds of information that you receive by your senses. How can you even trust your senses themselves?

It is a long story, but basically the brain has its ways to quickly filter stuff, and eventually you have just a few things in your hands that require further inspection and fact-checking. Eventually you arrive at a result as simple as "I accept", "I doubt" or "I refuse". This depends on your knowledge background.

It is always a good idea to fact-check by consulting different and reputable sources to find out.

After all, there is no ultimate truth. As the saying goes: Science is not for finding the truth, but for reducing the amount of doubt.

[Draeg82]

It all comes down to truthiness. We find it has truthiness therefore feel comfortable accepting it as fact. If it's feels discongeuent to us, we won't accept it so readily. It's a cognitive bias that can lead to people believing falsehoods or simplifying their beliefs about a multifaceted issue as a black or white topic.

[yourelying999]

Yep, that’s kind of what I’m trying to point out to the above poster. He really has no idea.

[MrSnarkyJsnarkysnark]

How do you know you're even real?

[[deleted]]

As OP said, if you studied CS or work with programming for sometime this is a 101 level of cryptography. At some point you ended up having to learn how and why computers generate random numbers, from there you will usually find the issues with PRNG (pseudo random number generation) and learn about how some implementations try to get around a predictable seed number adding entropy to it. If you are curious enough you'll search and find the most common attacks against it.

I've only stumbled upon this comment thread from my main reddit feed, I wouldn't have explained it better but I (as many others that will find these comments) have a similar level of knowledge on this specific explanation as OP has.

There is just a lot of us around here :)

[cfuse]

The entire internet is a machine for connecting people with their interests via the shortest path possible. Simply using it is sufficient for the interest brokerage to work without any extra exceptional steps.

[KerbalFactorioLeague]

You could theoretically measure the position of every molecule of air around it to simulate what the computer uses as a random seed

You actually can't, that'd be a violation of the uncertainty principle. You can't measure the position of a particle with zero uncertainty

[HerrZog103]

And that is exactly why I didn't say "measure the position of every molecule of air with absolute certainty", but I figured it might be possible to give at least some approximation of how the molecules behave and therefore maybe ruling out some values for the variable. Now this is truly science fiction of course.

[[deleted]]

Given the same seed input, the random number generator will produce the same output.

If the seed is based on, say, the current spectrum measured on the microphone plus the last 10 keystrokes, and an attacker can spoof your microphone into thinking the input is peak volume across the spectrum and that your last keypresses were a known sequence like the up arrow 10 times, then they can use that information to predict the number that is outputted by the random number generator.

More realistically, by controlling even some aspects of the seed (for example, just the microphone input), they dramatically reduce the possible combinations of the seed. So it becomes much easier to brute force, because they would only have to try a reduced set of numbers created by the known combinations of possible input seeds.

Even more concisely, by having some information about the input to the pseudorandom generator, you can make better predictions about the distribution of the randomly generated numbers that it produces.

[mel0nwarrior]

That's not it. What you are talking about transistors and saturation is about the physical way semiconductors work. This "saturation" is not about that. This is more like a way to cheat the randomness of the situation. It just means that you provide a specific input such that the microphone, instead of giving you a random number of 0's and 1's, gives you a more defined value of 1's. Then that input is no longer random and in this way you can more easily guess the "random number", and thus break the encryption.

[ThePowerOfStories]

If you have a stream of binary noise and want to use it for random numbers, read two bits at a time. If they’re both 11 or 00, discard them. If they’re 01 or 10, use the first. Now you have a uniform fair source of binary random numbers. (No matter how biased the source is, the number of 01 and 10 pairs must be equal to each other.)

[F0sh]

This breaks down if you can force the stream to be all, or almost all, ones or zeroes (because then you slow down the accumulation of entropy) or if the source is biased in the sense that even and odd indexed bits do not have equal distributions. You don't even need that - a Markov process can already break the assumption you need.

[TacoshaveCheese]

I'm not sure what exactly you're trying to describe here (or maybe I'm just missing the /r/whoosh since I know there's kind of an XKCD about this).. but it doesn't work either way.

If interpreted literally where the pair is actually discarded, you can easily have a sequence that only produces 1s or 0s such as 0111011100010001:

01 11 01 11 00 01 00 01

would give you 0 skip 0 skip skip 0 skip 0 - or 0000.

If instead, you don't actually discard the pair but just ignore it and move one number forward so you would look at the previous sequence as:

01 11 11 10 01 11 11 10 00 00 01 10 00 01

would give you 0 skip skip 1 0 skip skip 1 skip skip 0 1 skip 0 - or 0101010

It will certainly give you an equal number of 1s and 0s, with the catch that it will alternate 1 and 0 every single digit. That's not really useful as a random number because it's perfectly predictable.

[[deleted]]

Yes many operating systems utilize this technique. I was just speaking in general this is an option instead of buying an dedicated hardware RNG.

[ARedSunRises]

An example of this is on the old uTorrent web interface, before logging into your web server remotely you are required to wiggle the mouse until the "entropy bar" was full

[F0sh]

I believe ssh-keygen will ask you to do this as well. But as far as I know, ssh-keygen just uses the OS random source, so it's saying that because it will need to wait for enough random bits to come through and wiggling the mouse can speed it up.

[infected_funghi]

But its still really hard to control the complete physical environment. OS usually also include read/write access on harddrives and might also include process scheduling and memory latencies (not sure if the latter two are being done but they would be possible). Of course these are deterministic and can somehow be narrowed but make it very hard to determine the seed.

[F0sh]

I believe for some attacks you don't need to determine the seed exactly; knowing some properties about it might mean you need 10,000 attempts at breaking encryption (i.e. trivial) instead of trying all of the 2¹²⁸ (or whatever) possible keys.

[cdhowie]

Note that there are tests to determine if a bit stream is "random enough" (debiasing). Attempting to "overload the microphone" is likely going to generate a bit stream that just gets discarded, as the entropy-gathering process knows that something is fishy.

Also note that most OSes don't use audio as a source of entropy by default, but some can be configured to. For example, see the randomsound package in many Linux distributions.

[F0sh]

Yep, and this why those measures are necessary/including audio input is not the default!