OSDev.org

The Place to Start for Operating System Developers
It is currently Sun Jun 13, 2021 10:01 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: The Random Number Generator page needs reworking
PostPosted: Sat May 22, 2021 3:18 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1016
Hi all,

I think the Random Number Generator page is due for an overhaul. The information there is not bad per se, it's just incomplete and misleading. I think the main division of the page into "true" and "pseudo" RNGs is already misguided, and I think the article maybe ought to focus on entropy and CSPRNGs. I have some ideas how to start, but would end up throwing away most of the current article, and I don't know if that would be a welcome change. Any ideas how to get started?

Another thing that ought to be addressed is the prominent placement of the RDRAND instruction. That thing has the potential of seeding entropy buffers, sure, but I would not use it as sole source of random numbers. Because it is a black box. Does the CPU/mainboard contain an avalanche diode or something, or does RDRAND merely give the output of some NSA approved PRNG? Who knows, you can't check it.

Maybe I ought to draft it in my user namespace first... I'll get on it. Has anyone else tried to do a similar thing already?

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: The Random Number Generator page needs reworking
PostPosted: Sat May 22, 2021 4:00 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1016
Update: Draft created: https://wiki.osdev.org/User:Nullplan/Random_Number_Generator. Only an outline for now.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
 Post subject: Re: The Random Number Generator page needs reworking
PostPosted: Sat May 22, 2021 9:58 am 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 690
Looks good to me... Keep at it :)

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: The Random Number Generator page needs reworking
PostPosted: Sat May 22, 2021 8:38 pm 
Offline
Member
Member
User avatar

Joined: Thu Oct 13, 2016 4:55 pm
Posts: 1514
nullplan wrote:
Another thing that ought to be addressed is the prominent placement of the RDRAND instruction. That thing has the potential of seeding entropy buffers, sure, but I would not use it as sole source of random numbers. Because it is a black box. Does the CPU/mainboard contain an avalanche diode or something, or does RDRAND merely give the output of some NSA approved PRNG? Who knows, you can't check it.
Actually, that's the purpose of a random generator... It has to be a black box without any recognizable algorithm. But I agree it's only good for setting the seed though.

nullplan wrote:
Update: Draft created: https://wiki.osdev.org/User:Nullplan/Random_Number_Generator. Only an outline for now.
Otherwise your page looks good to me, but you must mention hardware random sources. It would also worth adding a section on how to add real entropy (for example by changing the seed on every interrupt, which includes some real-life event entropy, like the user's typing speed, how often the mouse is moved, when network packets arrives etc. These are non-algorithmic changes to the seed, impossible to calculate and backtrack.)

wiki wrote:
Explain cryptographic security, and simple idea for SHA-based PRNG.
As for using sha on the seed, take a look at MBedTLS' entropy.c as example. But I'd like to point out this has nothing to do with cryptographically sound random, that requires real-life event entropy. (For example, have you ever generated a key with GPG? It's not using libc and srand at all, instead you have to type for quite a while because it's gaining entropy from the elapsed time between your keystrokes.)

Cheers,
bzt


Top
 Profile  
 
 Post subject: Re: The Random Number Generator page needs reworking
PostPosted: Sun May 23, 2021 2:09 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1016
bzt wrote:
Actually, that's the purpose of a random generator... It has to be a black box without any recognizable algorithm.
Only in use. In design, the random generator has to preclude the sequence of numbers being predicted. It can only do that when its design and its inner workings are known. For the PRNG in Linux, you can know exactly what goes into the entropy pool, and how it is mixed in, and see that there is no predetermined sequence of numbers being generated. For the RDRAND instruction, there are no such assurances. Only Intel's word that they are definitely not trying to undermine your security, honest!

bzt wrote:
But I'd like to point out this has nothing to do with cryptographically sound random, that requires real-life event entropy.
That would be the section on high-entropy generators I'm preparing. The idea is that if the entropy pool has some entropy, and some message has entropy, then SHA-1(entropy pool + message) has the same amount of entropy as both combined, while compressing down to a single SHA-1 block size. You can also use SHA-2 or SHA-3, or even hashing algorithms not called SHA. In any case, distribution of entropy and compression are properties of hash algorithms.

You then have to jealously guard the entropy pool, so nobody gets a look at it. When asked to generate random numbers based on the pool, you take the pool contents, calculate a hash based on them, and return the hash. However, that would lead to a repeating pattern in the hash block size, so before you return it, you must also mix the output back into the entropy pool again. That is basically the entire design. In production, the algorithm to mix the entropy into the pool does not have to be secure, but the point of the article should be to start with simplicity and move on to speed afterwards.

The idea of cryptographic security of the RNG is also about the entropy pool: The state of the random generator must not be knowable for anyone observing the outputs before or after another process has used it for some secure purpose. That is also a failing of the low-entropy generators, that you can identify their internal state by observing the outputs. For an RNG that is shared across the entire system, this is even more important. If the two of us were sharing a computer, it would not help you to generate a random key if right before that, I figured out the state of the RNG and know exactly what random numbers you are going to get.

Most of my knowledge about this comes from a talk I forgot the title of, but the subtitle was "How I learned to stop worrying and love the urandom", which was held at some Chaos Communication Conference if memory serves, and it made so many things so much clearer for me. For instance why the blocking behavior of /dev/random on Linux is nonsense, except maybe at boot when not many random events have happened yet. But gauging the entropy of arbitrary events is really hard in general, so guessing how many bits you may have added now is an inexact science at best. Hard disk command timing is random due to the behavior of air molecules on the surface of the disk, but an SSD has the exact same interface and no randomness at all. And similar for all other sources.7

And then there's adversarial entropy, which I was looking for the paper DJB wrote about it (or was it just a blog post? I forget). Essentially, it is possible an adversarial entropy device would try to get the state of the entropy pool and then deliver "random" numbers to the system such that the entropy pool is forced to become less random. Which sounds far fetched, but really, all you need is a rootkit and a local network device willing to time packets just right. And suddenly the attack becomes scarily plausible and hard to defend against. And the rootkit doesn't have to write into kernel space, only read, and Meltdown just recently happened... oh boy. And if it isn't Meltdown, it's Rowhammer or something like that.

So yeah, I have some writing to do.

_________________
Thou hast outraged, not insulted me, sir; but for that I ask thee not to beware of Starbuck; thou wouldst but laugh; but let Ahab beware of Ahab; beware of thyself, old man.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group