Add master DRBG for reseeding by mspncp · Pull Request #4402 · openssl/openssl

mspncp · 2017-09-22T00:29:53Z

Checklist

documentation is added or updated (as comments)
tests are added or updated

The master DRBG

Up to now, there was an asymmetry between the public and the private global DRBG. Only the former was reseeded by the RAND_add() call. This pull request introduces a master DRBG which is not publicly accessible. So there are now three global DRBGs:

 <os entropy sources>
        |
     <master>          \
      /   \            | three global DRBGs with locking
<public>  <private>    /
    |
  <ssl>

The master DRBG is the only DRBG that pulls entropy from the trusted entropy sources, and that is reseeded by the RAND_add() call. Three of the DRBGs, namely master, public and private DRBG, have a locking mechanism, while the DRBGs chained to the public DRBG are intended to be used by a single thread and have no locking.

Naming

In order to get a consistent naming of the three global DRBGs, the two existing DRBGs had to be renamed. This includes the RAND_DRBG_get0_*() method which are exported from libcrypto to libssl, but that's no problem because these functions were introduced in master only recently and are not part of an official API yet.

Module globals

static RAND_DRBG drbg_master;  /* The master DRBG. Seeded from the os */
static RAND_DRBG drbg_public;  /* The global public DRBG. */
static RAND_DRBG drbg_private; /* The global private-key DRBG. */

Accessors

RAND_DRBG *RAND_DRBG_get0_master(void);
RAND_DRBG *RAND_DRBG_get0_public(void);
RAND_DRBG *RAND_DRBG_get0_private(void);

Seed Propagation

Instead of having RAND_add() reseed all global DRBGs (which would require taking all three locks), we only reseed the master DRBG (because it holds the lock already) and use a simple mechanism to propagate the reseeding to to all chained DRBGs: Every DRBG has a seed count which is incremented whenever the DRBG pulls fresh random input. Any chained DRBG compares in the RAND_DRBG_generate() call its seed count with the one of its parent. If there is a mismatch, it seeds itself automatically.

This propagation works for regular reseedings, too, not only for the ones triggered by RAND_add().

Update: As suggested by @paulidale, seed propagation will not proceed to the DRBGs which are owned by a thread or an SSL context, because this would make RAND_add() a very expensive operation. Only the global public and private DRBGs will be automatically restarted.

Remark: This "seed count" should have been named seed_count, however this name unfortunately collides with the reseed_counter member which actually counts generate requests, not reseeds. However, the name reseed_counter comes from the NIST standard, so I didn't dare to rename it. Hence I called my counter the restart_count. If anybody has a better suggestion for the name, I'm happy to hear about it.

Locking

Currently, only the three global DRBGs have a lock. The other chained (SSL) locks are considered to be owned by a single thread. So all locking code needs to check for the presence of the lock first. The lock is currently taken by the caller and it is not clear, whether all cases are currently handled. This is somewhat unsatisfying.

The lock is owned by the RAND_DRBG "class", which should be an opaque structure, in particular the locking should be managed entirely from within the RAND_DRBG "methods". (Sorry for my C++ speak).
I doubt that the performance gain of having an rwlock only in some dedicated global DRBGs does not justifies destroying simplicity. So why not have an rwlock in all DRBGs and don't have to check for the presence of the rwlock. (But I'm not an expert w.r.t. the performance of rwlocks.)

Debugging

You can debug into the code paths of RAND_add() using the openssl rand command:

echo 'this is some random input' > /tmp/randfile
./util/shlib_wrap.sh gdb --args ./apps/openssl rand -hex -rand /tmp/randfile  12

(gdb) start
(gdb) b drbg_setup
(gdb) b drbg_add

paulidale · 2017-09-22T03:34:22Z

crypto/rand/drbg_lib.c

Is the locking needed here? I thought integer reads were considered atomic.

It might require an atomic increment when the count is changed but that's cheaper than locking when it is available.

Then I just leave it as it is: Only the three global DRBGs are created with a lock, the other DRBGs don’t have a lock by default. For completeness sake, I would add a RAND_DRBG_enable_locking() method to the RAND_DRBG API.

I agree with you that letting CRYPTO_THREAD_xxx_lock() accept NULL pointers as no-ops is probably not a good idea. So the call needs to be wrapped by a conditional.

Thanks for suggesting the atomic operations. I hope the following question does not sound naive: I was wondering whether any special precaution is necessary in the first place. Even in the unlikely case that due to concurrency issues the if-block

if (drbg->restart_count != drbg->parent->restart_count) { … }

is not entered erroneously, this would only mean that automatic restarting of the chained DRBG would be postponed until the next generate request. And failing twice in a row is extremely unlikely. What do you think about this kind of reasoning?

integer reads were considered atomic

In many cases, yes. Certain combinations of processor architecture, memory coherency model in use, and alignment of access can cause integer reads to not be atomic, so when there is a potential for concurrent reads/writes, it's generally best to explicitly use a primitive that guarantees atomicity -- in the common case, such primitives are supposed to decay to "normal" memory accesses.
I guess with the current APIs one would have to CRYPTO_atomic_add() with a zero increment to perform an atomic read, incurring a write as well; we could probably add a CRYPTO_atomic_read() primitive if the overhead was a concern.

I would prefer the CRYPTO_atomic_read(), not for performance reasons but for clarity. Provided that's not too much effort for you to add.

CRYPTO_atomic_read sounds like a good idea.

If there is a race reading either drbg->restart_count or drbg->parent->restart_count, a reseed will occur now and again the next time the DRBG is used. I.e. not a big concern. If a stale value remains in cache, the reseed will be delayed.

paulidale · 2017-09-22T03:35:00Z

crypto/rand/rand_lib.c

Unnecessary locking again?

paulidale · 2017-09-22T03:41:23Z

crypto/rand/drbg_lib.c

Certainly the global public and private DRBGs should reseed when the master does. I'm less sure about the levels below these.

There could be hundreds or thousands of DRBGs in the SSL objects and this would make a reseeding an exceedingly expensive operation. I recognise that the child DRBGs will reseed in a lazy manner so the cost is spread over time but it's still a large cost.

I understand your concerns about the reseeding chain reaction. As you suggested, I could enable automatic restarting only for the two global chained DRBGs (private and public). There are three possibilities to selectively enable this auto-restart feature for DRBGs:

Use lock != 0 as an indicator that automatic restart is enabled. => Looks hacky to me.

Add an auto_restart member. => Adds a seldomly used member: Most DRBGs will have it disabled, so there are two unused members, auto_restart and restart_count.

Use restart_count != 0 as indicator that automatic restart is enabled. In order to enable auto restart, one simply sets the counter to 1. An integer overflow check when incrementing can safely be omitted. Before this ever overflows, madness rules ;-).

As usual, the third variant is my favourite choice. :-) What is your opinion?

If we aren't reseeding from a parent, reseed the global public and private DRBGs. It's a bit hacky but could be reworked to "if we're reseeding the global master, flag the other two global RNGs for reseeding".

Have a global variable indicating that all DRBGs should be reseeded rather than just the global ones. It wouldn't need locking since it will essentially be read-only. I can't think of a case where you want some but not all of the non-global DRBGs reseeded. That usually means there are several and I'm just not thinking straight enough.

paulidale · 2017-09-22T04:35:13Z

Another possibility would be changing the CRYPTO_THREAD_xxx_lock calls to accept a NULL argument, returning 1 ? I'm not sure I like this. Nothing else is coming to mind at the moment.

The cost of using an unlocked lock is implementation and architecture dependent. The worst case would likely be a context switch to the operating system (which is extremely expensive), the best an atomic memory operation (which is a lot more than a normal instruction but not thousands of cycles).

richsalz · 2017-09-22T07:51:45Z

i think the master forcing a reseed on the two global ones, and using the regular locking, is probaby the good-enough trade-off for this work. I really really like it. I will remove more closely when i get home. I will not be upset if it gets approved and merged before then :)

richsalz · 2017-09-22T07:52:55Z

BTW, the writeup you put into your PR's is awesome. I think the commit message might want to explicitly point to the PR text for more details.

mspncp · 2017-09-22T08:29:17Z

Rich, your compliments make me blush again... 😊

mspncp · 2017-09-22T08:45:13Z

Ups, the cla-check is failing again?!

mspncp · 2017-09-22T09:06:22Z

But seriously, I believe that an important aspect of a pull request is to convince other people and make them agree with the change. For a trivial pull request, the patch will be self explanatory, but for a larger work-in-progress, it is probably always a good idea to explain what one is doing.

dot-asm · 2017-09-22T12:34:44Z

I'm not going do remove cla-check, nor do I want others to do so. I'd like to see/verify that next commit will remove it automatically...

mspncp · 2017-09-22T12:51:40Z

Pushed and removed an additional commit to trigger the cla-check

mspncp · 2017-09-22T13:23:28Z

OS reseeding interval

One question to everybody: With the private and public DRBG now being chained, the number of generate requests (RAND_bytes() resp. RAND_priv_bytes()) between two OS reseeds now effectively jumps from 2^24 to 2^48. Does everybody agree that one should compensate this change by reducing the reseed_interval of the three global DRBG's (and only these) accordingly?

Please vote:

Leave all reseeding intervals at 2^24.
Change the reseeding intervals of the three global DRBG's to 2^12.
Change the reseeding interval of the public and private DRBG to 2^16, and of the master DRBG to 2^8.
Other choice.

richsalz · 2017-09-22T13:35:05Z

if we make them all 2^8, then reseeding happens every 2^16 private keygens.
I think boring reseeds before every private keygen but I think that's too much
I mean, the "official math" says for the mode we use 2^24, right?

paulidale · 2017-09-23T00:28:03Z

I suspect something that uses both a time based reseed and a bytes produced reseed. I.e. if time since last reseed > X or number of bytes > Y then reseed. The values for X and Y should perhaps be via a setter/getter interface. 2^48 for Y seems way too much.

For long life private stuff, an explicit reseed is beneficial. I've got an item on my to do list to create some fast low quality non-blocking sources that can be added in this situation to provide some differentiation even if it isn't cryptographically good. The idea being to mutate the state to make things more difficult. I'm thinking things like gettimeofday, clock_gettime, TSC, RDRAND, /dev/urandom for this. A full reseed every time is better from a security viewpoint but isn't practical.

If the caller requests prediction resistance, then a proper reseed from the OS should always be done. I think this is mentioned in NIST's SP 800-90A.

Both these will be new PRs.

mspncp · 2017-09-25T21:47:18Z

Just in case anybody wonders why this PR is stalled: The reviewers are keeping my busy on #4328 ;-)

paulidale · 2017-09-25T22:06:18Z

I misunderstood slightly about the 2^48 in my previous response.

NIST's claim is that DRBGs are secure for 2^24 bytes. I don't see a reason to dispute this, so the status quo is likely fine. If we want to reduce this, we can but I'd not go too low due to the overhead involved in reseeding. 2^16 should be fine. 2^8 seems a bit too frequent.

NIST permits chains of DRBGs without crediting all of the output from all the DRBGs to the root of the chain. For example, a chain of five DRBGs would reseed the root every 2^120 bytes output but at any point no DRBG will have produced more than 2^24 which is safe.

I still suggest a time based reseed lifetime as well, but again it doesn't have to be extremely frequent.

mspncp · 2017-09-29T00:19:02Z

The code does not compile yet and still needs testing. I commited nevertheless to give you a short update about where I'm heading to in this PR.

In addition to automatic reseeding based on generate counts and seed propagation from master to its children, I also implemented an automatic reseeding of the master DRBG based on elapsed time.

See the commit message for more details. (And yes: the contents of the commit message should better go into a manual page...)

mspncp · 2017-09-29T00:37:22Z

I chose to lower the reseeding interval of the public and private DRBG to 2^16, and of the master DRBG to 2^8. This ensures that randomness from the os entropy source is queried every 2^24 generate requests.

From the NIST point of view this would not be necessary, since a DRBG with access to a trusted entropy source is more or less equivalent to a NDRBG. So it would be sufficient to reseed from the OS every 2^48 requests. However, in practice there is an essential difference: all three DRBGs live in the address space of the user program, whereas the OS RNG lives in the kernel, so its internal state is more secured than the state of the user space DRBGs: If one of the DRBG states gets leaked, the states of the other two might not be secret anymore either.

kroeckx · 2017-10-18T14:09:52Z

Can you rebase this now that the other commits have been merged?

mspncp · 2017-10-18T14:25:49Z

Of course, this PR will be my next focus. Just give me a day.

kroeckx · 2017-12-17T21:06:46Z

test/drbgtest.c

It should be time(NULL), there is also an extra space.

(Can be fixed when merging)

kroeckx · 2017-12-17T21:07:00Z

test/drbgtest.c

kroeckx · 2017-12-17T21:15:50Z

test/drbgtest.c

extra space

kroeckx · 2017-12-17T21:25:06Z

@paulidale: Can you confirm you're happy with this?

paulidale · 2017-12-17T21:37:46Z

The recent changes look good.

I didn't go through everything again but can if desirable.

kroeckx · 2017-12-17T21:38:22Z

I think we're still missing a test for the reseed_time_interval, but maybe we can do that in an other PR.

kroeckx · 2017-12-17T21:39:06Z

@paulidale: It's really up to you to say if this is good to merge or not. It's up to you to decide what is needed for you to approve it.

mspncp · 2017-12-17T21:56:11Z

@kroeckx, @paulidale Thank you very much for reviewing my pr.

I would like to add the final fixups myself, because they belong to two different commits. Please let me know if it's ok for you when I autosquash the fixups (without moving the base) while leaving the unsquashed fix at mspncp:pr-add-master-drbg-unsquashed for inspection. If you prefer to do the rebasing yourself, then please do it using git rebase -i --autosquash after I added the fixups.

kroeckx · 2017-12-17T22:00:09Z

Feel free to rebase/squash as needed

A third shared DRBG is added, the so called master DRBG. Its sole purpose is to reseed the two other shared DRBGs, the public and the private DRBG. The randomness for the master DRBG is either pulled from the os entropy sources, or added by the application using the RAND_add() call. The master DRBG reseeds itself automatically after a given number of generate requests, but can also be reseeded using RAND_seed() or RAND_add(). A reseeding of the master DRBG is automatically propagated to the public and private DRBG. This construction fixes the problem, that up to now the randomness provided by RAND_add() was added only to the public and not to the private DRBG. Signed-off-by: Dr. Matthias St. Pierre <[email protected]>

Every DRBG now supports automatic reseeding not only after a given number of generate requests, but also after a specified time interval. Signed-off-by: Dr. Matthias St. Pierre <[email protected]>

Signed-off-by: Dr. Matthias St. Pierre <[email protected]>

…ther Previously, the RAND_DRBG_uninstantiate() call was not exactly inverse to RAND_DRBG_instantiate(), because some important member values of the drbg->ctr member where cleared. Now these values are restored internally. Signed-off-by: Dr. Matthias St. Pierre <[email protected]>

mspncp · 2017-12-17T22:14:45Z

Autosquashed and rebased to the tip of master. Thanks again to everybody for taking the time to review this pr!

mspncp · 2017-12-17T22:20:06Z

I think we're still missing a test for the reseed_time_interval, but maybe we can do that in an other PR.

Maybe I'll find some time the next days to prepare a pr for the missing test.

paulidale · 2017-12-17T22:28:03Z

Okay, I've gone through it again and still approve.
I'll merge.

A third shared DRBG is added, the so called master DRBG. Its sole purpose is to reseed the two other shared DRBGs, the public and the private DRBG. The randomness for the master DRBG is either pulled from the os entropy sources, or added by the application using the RAND_add() call. The master DRBG reseeds itself automatically after a given number of generate requests, but can also be reseeded using RAND_seed() or RAND_add(). A reseeding of the master DRBG is automatically propagated to the public and private DRBG. This construction fixes the problem, that up to now the randomness provided by RAND_add() was added only to the public and not to the private DRBG. Signed-off-by: Dr. Matthias St. Pierre <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Kurt Roeckx <[email protected]> (Merged from #4402)

Every DRBG now supports automatic reseeding not only after a given number of generate requests, but also after a specified time interval. Signed-off-by: Dr. Matthias St. Pierre <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Kurt Roeckx <[email protected]> (Merged from #4402)

Signed-off-by: Dr. Matthias St. Pierre <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Kurt Roeckx <[email protected]> (Merged from #4402)

…ther Previously, the RAND_DRBG_uninstantiate() call was not exactly inverse to RAND_DRBG_instantiate(), because some important member values of the drbg->ctr member where cleared. Now these values are restored internally. Signed-off-by: Dr. Matthias St. Pierre <[email protected]> Reviewed-by: Paul Dale <[email protected]> Reviewed-by: Kurt Roeckx <[email protected]> (Merged from #4402)

paulidale · 2017-12-17T22:48:33Z

Merged but not squashed to a single commit.

paulidale · 2017-12-17T22:48:49Z

Thanks for everyone's patience.

mspncp mentioned this pull request Sep 22, 2017

Make RAND_DRBG a public OpenSSL API #4403

Closed

paulidale reviewed Sep 22, 2017

View reviewed changes

openssl-machine added the hold: cla required The contributor needs to submit a license agreement label Sep 22, 2017

mspncp mentioned this pull request Sep 22, 2017

Cleanup whitespace in ssl_lib.c (tabs to spaces) #4399

Closed

openssl-machine removed the hold: cla required The contributor needs to submit a license agreement label Sep 22, 2017

mspncp force-pushed the pr-add-master-drbg branch from 715c090 to 55b08e1 Compare September 22, 2017 12:51

mspncp mentioned this pull request Sep 23, 2017

Fix reseeding issues introduced by new RAND_OpenSSL() method #4328

Closed

1 task

paulidale mentioned this pull request Sep 25, 2017

CRYPTO_atomic_read #4414

Closed

2 tasks

mspncp force-pushed the pr-add-master-drbg branch from 55b08e1 to ec889e9 Compare September 29, 2017 00:08

mspncp force-pushed the pr-add-master-drbg branch 2 times, most recently from acb06b9 to de66186 Compare September 29, 2017 07:18

mspncp force-pushed the pr-add-master-drbg branch from de66186 to a780a8d Compare October 21, 2017 00:02

mspncp changed the title ~~WIP: Add master DRBG~~ Add master RAND_DRBG for reseeding Oct 21, 2017

kroeckx reviewed Dec 17, 2017

View reviewed changes

test/drbgtest.c Outdated

Copy link

Member

kroeckx Dec 17, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It should be time(NULL), there is also an extra space.

(Can be fixed when merging)

kroeckx reviewed Dec 17, 2017

View reviewed changes

test/drbgtest.c Outdated

Copy link

Member

kroeckx Dec 17, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

time(NULL)

kroeckx reviewed Dec 17, 2017

View reviewed changes

test/drbgtest.c Outdated

Copy link

Member

kroeckx Dec 17, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

extra space

kroeckx approved these changes Dec 17, 2017

View reviewed changes

mspncp added 4 commits December 17, 2017 23:12

Implement automatic reseeding of DRBG after a specified time interval

c4e601b

Every DRBG now supports automatic reseeding not only after a given number of generate requests, but also after a specified time interval. Signed-off-by: Dr. Matthias St. Pierre <[email protected]>

Allocate the three shared DRBGs on the secure heap

92cbf97

Signed-off-by: Dr. Matthias St. Pierre <[email protected]>

mspncp force-pushed the pr-add-master-drbg branch from 7f35b71 to 70d4dcb Compare December 17, 2017 22:13

paulidale closed this Dec 17, 2017

mspncp deleted the pr-add-master-drbg branch January 9, 2018 17:03

kroeckx mentioned this pull request Feb 18, 2018

Return error when trying to use prediction resistance #5402

Closed

mspncp mentioned this pull request Mar 8, 2018

Make the public and private DRBG thread local #5547

Closed

mspncp mentioned this pull request Oct 13, 2018

data race in RAND_DRBG_generate #7394

Closed

mspncp mentioned this pull request Mar 22, 2020

test/drbgtest.c: Fix error check test #11195

Closed

1 task

Uh oh!

Comments

Conversation

mspncp commented Sep 22, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Checklist

The master DRBG

Naming

Module globals

Accessors

Seed Propagation

Locking

Debugging

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

paulidale Sep 23, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

paulidale commented Sep 22, 2017

Uh oh!

richsalz commented Sep 22, 2017

Uh oh!

richsalz commented Sep 22, 2017

Uh oh!

mspncp commented Sep 22, 2017

Uh oh!

mspncp commented Sep 22, 2017

Uh oh!

mspncp commented Sep 22, 2017

Uh oh!

dot-asm commented Sep 22, 2017

Uh oh!

mspncp commented Sep 22, 2017

Uh oh!

mspncp commented Sep 22, 2017

OS reseeding interval

Uh oh!

richsalz commented Sep 22, 2017

Uh oh!

paulidale commented Sep 23, 2017

Uh oh!

mspncp commented Sep 25, 2017

Uh oh!

paulidale commented Sep 25, 2017

Uh oh!

mspncp commented Sep 29, 2017

Uh oh!

mspncp commented Sep 29, 2017

Uh oh!

kroeckx commented Oct 18, 2017

Uh oh!

mspncp commented Oct 18, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

mspncp commented Sep 22, 2017 •

edited

Loading

paulidale Sep 23, 2017 •

edited

Loading

kroeckx commented Dec 17, 2017 •

edited

Loading