Discussion:
[nuttx] /dev/urandom [1 Attachment]
David Alessio david.alessio@yahoo.com [nuttx]
2016-07-15 08:35:51 UTC
Permalink
Hi Greg,

Attached is a patch that optionally adds /dev/urandom to all architectures. The pseudo-random algorithm I choose strikes an arguably-good balance between being “random” and small/fast enough for 8/16 bit MCUs. It’s the well-documented xorshift128 algorithm. It has an internal state of 128 bits that can be [re-]seeded with a write.

Best regards,
-david
spudarnia@yahoo.com [nuttx]
2016-07-15 12:15:10 UTC
Permalink
Hi, David,


One question before I commit this.


I have not looked at the patch yet, but from your comments it sounds like your wrote another rand() algorithm. That is fine. Knowing you, it is probably better than the one that I have in libc/stdlib. I think that came from an old CRC handbook


But don't you think that there should be only one support software random number generator? Don't you think that /dev/urandom should be based on the same underlying RNG as srand?


Can we replace libc/stdlib/lib_rand.c with your algorithm? Adding internal OS-only APIs as necessary to support /dev/urandom?


Greg
'David S. Alessio' david.s.alessio@gmail.com [nuttx]
2016-07-16 19:52:44 UTC
Permalink
Hi Greg,

Sorry for the delayed reply.

There seems to be quite a bit of confusion and misunderstanding in the later email msgs about the use of /dev/urandom vs. /dev/random. I’ll address those individually


(please see inline comments below)

Best regards,
-david
Post by ***@yahoo.com [nuttx]
Hi, David,
One question before I commit this.
I have not looked at the patch yet, but from your comments it sounds like your wrote another rand() algorithm. That is fine. Knowing you, it is probably better than the one that I have in libc/stdlib. I think that came from an old CRC handbook
I don’t deserve credit for writing the PRNG, I simply chose a fast, reasonably-good PRNG suitable for use in /dev/urandom.

/dev/urandom is traditionally used as a source of “decently random” numbers and is usually used with the ‘dd’ command. It should be fast, repeatable (with constant seed), and fairly random. I wanted an algorithm that meets these expectations and yet would compile and run on the 8-bit and 16-bit MCU Nuttx supports. That pretty much rules out uint64_t multiplication.

Should we replace libc/rand()? Maybe, but only because it used double precision floating point operations; and it’s going to be slow. I haven’t tested it for randomness, so I can’t comment directly on what’s a “better” PRNG for randomness. But that’s less important, rand() has always been anything but random


In short, I think xorshift128() would be a better choice for rand() because 1) it’s faster; 2) smaller code footprint; and 3) it’s far superior than may other traditional implementations of rand() (again, I haven’t tested the current implementation). (see below)
Post by ***@yahoo.com [nuttx]
But don't you think that there should be only one support software random number generator? Don't you think that /dev/urandom should be based on the same underlying RNG as stand?
It can be, but it’s not necessarily. For example NetBSD uses a simple, traditional:
next = next * 1103515245 + 12345) % ((u_long)RAND_MAX + 1);
while /dev/urandom and /dev/random are based on one of several far more complex algorithms.
Post by ***@yahoo.com [nuttx]
Can we replace libc/stdlib/lib_rand.c with your algorithm? Adding internal OS-only APIs as necessary to support /dev/urandom?
Again, it’s not “my” algorithm ;)

You raise a few questions:
Can we use the same algorithm in lib_rand.c? I think we can copy and use the same algorithm in libc, but I don’t think we can share the same PRNG state variables. How would this work in a kernel mode build?

Can rand() use /dev/urandom? No, this would create an unnecessary dependency on /dev/urandom when only rand() is needed. Not to mention the unnecessary overhead for what was a simple libc call.
Post by ***@yahoo.com [nuttx]
Greg
'Juha Niskanen (Haltian)' juha.niskanen@haltian.com [nuttx]
2016-07-15 12:43:42 UTC
Permalink
Just remember to never ever use this for any crypto work e.g. when porting TLS libraries to NuttX. I think /dev/urandom should be by default a cryptographically-secure generator to avoid mistaken security assumptions.


See what Thingsee OS uses:


https://github.com/thingsee/thingsee-sdk/blob/dev/nuttx/drivers/dev_random.c


This is my foray into amateur crypto, design has not been checked with real crypto experts, so beware. We have used this in few real NuttX-based products (that had minimal security requirements, though). There is the legacy /dev/random but main API is a single function speckrandom_buf() just like OpenBSD's arc4random_buf().


Github has older version than what we have in our internal repos, if anyone is interested I can check if I can publish our current version. This could be adapted to 8/16 bit MCU by switching to speck32/64, I think. This also shows how up_waste() is a useful NuttX API.


Best Regards,

Juha Niskanen


________________________________
From: ***@yahoogroups.com <***@yahoogroups.com> on behalf of David Alessio ***@yahoo.com [nuttx] <***@yahoogroups.com>
Sent: Friday, July 15, 2016 11:35:51 AM
To: zhuopeng luo ***@yahoo.com [nuttx]
Subject: [nuttx] /dev/urandom [1 Attachment]


[Attachment(s) from David Alessio included below]

Hi Greg,

Attached is a patch that optionally adds /dev/urandom to all architectures. The pseudo-random algorithm I choose strikes an arguably-good balance between being "random" and small/fast enough for 8/16 bit MCUs. It's the well-documented xorshift128 algorithm. It has an internal state of 128 bits that can be [re-]seeded with a write.

Best regards,
-david
dev@ziggurat29.com [nuttx]
2016-07-15 13:44:34 UTC
Permalink
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
If either or both of these supported a configurable option of:
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)


Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.


-dave
'Juha Niskanen (Haltian)' juha.niskanen@haltian.com [nuttx]
2016-07-15 17:58:59 UTC
Permalink
Hi Dave,


"We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it)."


HW rng, when available, could be just used to supply entropy to entropy pool instead of used directly. Haltian boards for NuttX-based products typically have many sensors so we just feed low order bits from sensors and other noise to entropy pool (as our MCU most often lacks true rng).


"some generally suitable CSPRNG (as I believe Juha is suggesting)"


Well the Thingsee OS (=fork of NuttX) /dev/random definitely should go under CONFIG_EXPERIMENTAL, if it is ever accepted by mainline at all. I designed it and I'm far from expert with crypto, so it may not be generally suitable :)


But I urge Greg and others see for themselves if it is good for anything. (github link in previous email leads to our somewhat old public SDK)


"/dev/urandom is simply a symlink to /dev/random"


Since NuttX is a new OS, there is no need to have two names for a same thing for compatibility. But I agree that preferably there should be just one excellent source of arbitrary amounts of CS-randomness in the system instead of several HW-specific or insecure generators.


File based interface to rng is problematic because of extra hassle of opening, closing and consuming fd for it. Also an attacker may be able to exhaust CONFIG_NFILE_DESCRIPTORS fds somehow.


Thingsee uses speckrandom_buf() function as only randomness source throughout the system (both OS and apps) for both crypto and simple things like network protocol sequence numbers or deciding (flipping a coin) whether to query primary or secondary DNS server first etc. There are no calls to rand() as the better alternative is only negligibly slower.


Best Regards,

Juha Niskanen


________________________________
From: ***@yahoogroups.com <***@yahoogroups.com> on behalf of ***@ziggurat29.com [nuttx] <***@yahoogroups.com>
Sent: Friday, July 15, 2016 4:44:34 PM
To: ***@yahoogroups.com
Subject: Re: [nuttx] /dev/urandom



I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).

If either or both of these supported a configurable option of:
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)

Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.

-dave
dev@ziggurat29.com [nuttx]
2016-07-15 19:11:23 UTC
Permalink
"File based interface to rng is problematic because of extra hassle of opening, closing and consuming fd for it. Also an attacker may be able to exhaust CONFIG_NFILE_DESCRIPTORS fds somehow."



I suspect that the utility in the file-based api to the RNG is:
* existing code (e.g. other projects/products) understands this design, so porting an app to nuttx would ostensibly be easier
* is there any other application api available to the rng?


Not entirely related, but I found the following an interesting read nonetheless:


How To Safely Generate A Random Number — Quarrelsome http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/

How To Safely Generate A Random Number — Quarrelsome http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ Use urandom Use urandom. Use urandom. Use urandom. Use urandom. Use urandom. Use urandom. But what about for crypto keys? Still urandom. Why not {SecureRandom, OpenSSL, havaged, &c}?



View on sockpuppet.org http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/
Preview by Yahoo



I do agree with it in at least that the blocking nature of /dev/random (c.f. non-blocking /dev/urandom) is a silly thing. (note Nuttx /dev/random does not block). But both are presumed to be suitable for cryptographic purposes, which any linear rng is not.


OK, I am done adding noise (hmm, which is good thing for a csprng, haha).


-dave
Sebastien Lorquet sebastien@lorquet.fr [nuttx]
2016-07-16 08:57:26 UTC
Permalink
Hello,

I let everyone remember that security in the IoT is globally crap, so
please lets not add more crap in that field...
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is
a CSPRNG. We do already have /dev/random (well, I guess it is
dependent on there being a hardware rng underlying it).
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I
believe David is suggesting)
* some externally provided implementation (for those who are picky,
and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD
actually does)
Then that might be ideal. Actually, then you could probably merge all
the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.

But let me remind you something. Linux has entropy problems: There are
no hardware RNG in normal desktop computers, but there is a need for
enough "entropy" (unpredictable random bits) for security reasons
(generation of RSA keys, openssl, ssh, etc). - we dont have most of this
in NuttX.

So, linux gathers entropy from multiple low rate sources (keystrokes,
mouse mouvements, disk IO - often, each event generates one good bit, or
less), but this random data is very scarce. Because of this, directly
reading /dev/ramdom will deplete the entropy too fast, so the
/dev/urandom CSPRNG was added to allow generation of enough pseudorandom
bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs:
https://eprint.iacr.org/2006/086.pdf

Also, according to wikipedia: "On systems using the Linux kernel,
programs needing significant amounts of random data from /dev/urandom
<https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with
programs reading little data from /dev/random
<https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes
/dev/random whenever it is being read.^[6]
<https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>"

Entropy manipulation is not trivial, you could introduce biases or
discard entropy without paying attention.

However, on embedded platforms targeted by nuttx, the conditions are
different:
-there are no low-rate system entropy sources such as the ones that
makes urandom necessary
-there is often a hardware RNG of sufficient quality that will provide
random bits at a high enough rate for key generation or stuff like that,
when it's required at all (who really needs RSA key generation on a
nuttx embedded platform?)
-if even more pseudorandom bits are required (with a hw rng, this is
rare), then a proper CSPRNG such as Yarrow or another well designed
generator should be used.
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed,
which I doubt... the other option is to avoid /dev/urandom entirely, and
use /dev/random instead.

I advise against yet another low quality RNG in NuttX.

libc random is completely different. It has to be available even without
hardware RNG and no one with a sane mind would think it is
cryptographically secure. It could be implemented by xorshift128 as a
replacement of the current generator if we wanted a "slightly better",
but still fast, generator.

Sebastien
David Alessio david.alessio@yahoo.com [nuttx]
2016-07-16 21:38:57 UTC
Permalink
Sebastien,

(see comments below)

Regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but given that your English appears to be slightly better than my French, I’ll cut you some slack ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random. Traditionally, /dev/urandom has been as source of uniformly distributed pseudorandom numbers, fast, and non-blocking — nothing more, nothing less.

One typical use is to wipe a 1GB drive:
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000

Create a garbage 1MB file:
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random

/dev/random, if it exists, *must* be cryptographically secure. And it should use a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
But let me remind you something. Linux has entropy problems: There are no hardware RNG in normal desktop computers, but there is a need for enough "entropy" (unpredictable random bits) for security reasons (generation of RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from making references to Linux — it’s just examining a pathological case...

(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes, mouse mouvements, disk IO - often, each event generates one good bit, or less), but this random data is very scarce. Because of this, directly reading /dev/ramdom will deplete the entropy too fast, so the /dev/urandom CSPRNG was added to allow generation of enough pseudorandom bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: https://eprint.iacr.org/2006/086.pdf <https://eprint.iacr.org/2006/086.pdf>
Thanks for the link, but again, this is very Linux-specific.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel, programs needing significant amounts of random data from /dev/urandom <https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with programs reading little data from /dev/random <https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes /dev/random whenever it is being read.[6] <https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and /dev/urandom don’t need to be related. It’s just that typically the implementation of /dev/random builds on top of /dev/urandom and injects entropy...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Entropy manipulation is not trivial, you could introduce biases or discard entropy without paying attention.
Quite right; and I would argue against trying to implement a /dev/random with PRNG and entropy injection. If a project needs this, choose an appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there are no low-rate system entropy sources such as the ones that makes random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or it’s too slow, but a source of fast “decent” random numbers is desired. That’s where /dev/urandom fits.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there is often a hardware RNG of sufficient quality that will provide random bits at a high enough rate for key generation or stuff like that, when it's required at all (who really needs RSA key generation on a nuttx embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is rare), then a proper CSPRNG such as Yarrow or another well designed generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if one needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed, which I doubt... the other option is to avoid /dev/urandom entirely, and use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be “wrong”, but it breaks the tradition that /dev/urandom doesn’t block.

In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly complicated entropy pool management...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I advise against yet another low quality RNG in NuttX.
I’m happy to entertain an argument for a higher quality PRNG for /dev/urandom. But it has to:
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
libc random is completely different. It has to be available even without hardware RNG and no one with a sane mind would think it is cryptographically secure. It could be implemented by xorshift128 as a replacement of the current generator if we wanted a "slightly better", but still fast, generator.
And on this we agree.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Sebastien
Sebastien Lorquet sebastien@lorquet.fr [nuttx]
2016-07-16 21:59:44 UTC
Permalink
Hello

Please forgive my rude choice of words, I probably have a lesser english
knowledge than you may think :)

Also, your response clarified a lot of things, I dont think that my
second email is useful now.

So if I understand correctly, you main idea is : linux urandom is good
quality, nuttx is not linux, we dont need quality for nuttx urandom... ?

OK... lets forget Linux.

NuttX is not only for low-end microprocessors. On the contrary, it is
more a RTOS for mid/high-end mcus. That's why I dont think that the
argument about constrained memory holds.

Also, there comes my remark about IoT security: Accepting that urandom
is NOT a CSPRNG clearly makes us go in the bad IoT security route, which
I dont like at all.

If we continue this route, if HW AES is not available on all chips,
would you recommend DES? (or, xor?)

However, I could admit that the range of supported targets is so wide
that a correct PRNG is not doable everywhere.

I would be okay if:
-we had multiple implementations (say: 2) for fast, non blocking random
sources available at /dev/urandom
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in
Kconfig
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32
bytes, a correct CSPRNG would not be the bigger NuttX subsystem.

What about this?

Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but
given that your English appears to be slightly better than my French,
I’ll cut you some slack ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that
is a CSPRNG. We do already have /dev/random (well, I guess it is
dependent on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random.
Traditionally, /dev/urandom has been as source of uniformly
distributed pseudorandom numbers, fast, and non-blocking — nothing
more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I
believe David is suggesting)
* some externally provided implementation (for those who are picky,
and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge
all the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And it should use a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
But let me remind you something. Linux has entropy problems: There
are no hardware RNG in normal desktop computers, but there is a need
for enough "entropy" (unpredictable random bits) for security reasons
(generation of RSA keys, openssl, ssh, etc). - we dont have most of
this in NuttX.
Linux has many problems. And that’s why I try to refrain from making
references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes,
mouse mouvements, disk IO - often, each event generates one good bit,
or less), but this random data is very scarce. Because of this,
directly reading /dev/ramdom will deplete the entropy too fast, so
the /dev/urandom CSPRNG was added to allow generation of enough
pseudorandom bits even if the real entropy has a far lower rate.
Here is a doc describing the linux
RNGs: https://eprint.iacr.org/2006/086.pdf
Thanks for the link, but again, this is very Linux-specific.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel,
programs needing significant amounts of random data from /dev/urandom
<https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with
programs reading little data from /dev/random
<https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes
/dev/random whenever it is being read.^[6]
<https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and
/dev/urandom don’t need to be related. It’s just that typically the
implementation of /dev/random builds on top of /dev/urandom and
injects entropy...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Entropy manipulation is not trivial, you could introduce biases or
discard entropy without paying attention.
Quite right; and I would argue against trying to implement a
/dev/random with PRNG and entropy injection. If a project needs this,
choose an appropriate MCU — one that has a HW RNG (PIC32MZ,
STM32F4xx, etc.).
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there are no low-rate system entropy sources such as the ones that
makes random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or
it’s too slow, but a source of fast “decent” random numbers is
desired. That’s where /dev/urandom fits.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there is often a hardware RNG of sufficient quality that will
provide random bits at a high enough rate for key generation or stuff
like that, when it's required at all (who really needs RSA key
generation on a nuttx embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is
rare), then a proper CSPRNG such as Yarrow or another well designed
generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if
one needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
On 15/07/2016 19:58, 'Juha Niskanen
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed,
which I doubt... the other option is to avoid /dev/urandom entirely,
and use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be
“wrong”, but it breaks the tradition that /dev/urandom doesn’t block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly
complicated entropy pool management...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I advise against yet another low quality RNG in NuttX.
I’m happy to entertain an argument for a higher quality PRNG for
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
libc random is completely different. It has to be available even
without hardware RNG and no one with a sane mind would think it is
cryptographically secure. It could be implemented by xorshift128 as a
replacement of the current generator if we wanted a "slightly
better", but still fast, generator.
And on this we agree.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Sebastien
'David S. Alessio' david.s.alessio@gmail.com [nuttx]
2016-07-17 00:19:51 UTC
Permalink
Hello Sebastien,

(please see comments below)

Best regards,
-david
Hello
Please forgive my rude choice of words, I probably have a lesser english knowledge than you may think :)
No worries. ;)
Also, your response clarified a lot of things, I dont think that my second email is useful now.
So if I understand correctly, you main idea is : linux urandom is good quality, nuttx is not linux, we dont need quality for nuttx urandom… ?
It all depends on the application, but I don’t want to allow “perfect” to become the enemy of “good enough” for the particular application in hand.
OK... lets forget Linux.
NuttX is not only for low-end microprocessors. On the contrary, it is more a RTOS for mid/high-end mcus. That's why I dont think that the argument about constrained memory holds.
I agree. But then we’ll have to revisit the [my?] assumption that the same algorithm compile/execute on all MCUs.
Also, there comes my remark about IoT security: Accepting that urandom is NOT a CSPRNG clearly makes us go in the bad IoT security route, which I dont like at all.
If we continue this route, if HW AES is not available on all chips, would you recommend DES? (or, xor?)
My view is it’s all relative to the application and its attraction to hackers. Plenty of papers have been written on the advantages of AES over DES and 3DES, but if my application is measuring temperature in my water heater and sending the sensor data to a website that does nothing more than plot the data, isn’t DES still OK?

As for xor, no, I wouldn’t use it by itself. It works well when combined 1 or 2 other operations… Perhaps xor | rot13 | rot13 ?
However, I could admit that the range of supported targets is so wide that a correct PRNG is not doable everywhere.
Yes, that’s a difficult constraint. I tried to strike a balance… How would you balance the constraints?
-we had multiple implementations (say: 2) for fast, non blocking random sources available at /dev/urandom
I’m OK with 3, but not 15+ ;)
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config
I could not agree more! If we do this with xorshift128, “NOT CRYPTO SECURE” warnings should go everywhere.

How about:
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?

Does anyone really want Fortuna? Why would this be a better design choice than an MCU with dedicated HW?
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32 bytes, a correct CSPRNG would not be the bigger NuttX subsystem.
Sure, this is acceptable.

Then we have the problem of how to “properly” seed and condition the PRNGs…
What about this?
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but given that your English appears to be slightly better than my French, I’ll cut you some slack ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random. Traditionally, /dev/urandom has been as source of uniformly distributed pseudorandom numbers, fast, and non-blocking — nothing more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And it should use a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
But let me remind you something. Linux has entropy problems: There are no hardware RNG in normal desktop computers, but there is a need for enough "entropy" (unpredictable random bits) for security reasons (generation of RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from making references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes, mouse mouvements, disk IO - often, each event generates one good bit, or less), but this random data is very scarce. Because of this, directly reading /dev/ramdom will deplete the entropy too fast, so the /dev/urandom CSPRNG was added to allow generation of enough pseudorandom bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: https://eprint.iacr.org/2006/086.pdf <https://eprint.iacr.org/2006/086.pdf>
Thanks for the link, but again, this is very Linux-specific.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel, programs needing significant amounts of random data from /dev/urandom <https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with programs reading little data from /dev/random <https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes /dev/random whenever it is being read.[6] <https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and /dev/urandom don’t need to be related. It’s just that typically the implementation of /dev/random builds on top of /dev/urandom and injects entropy...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Entropy manipulation is not trivial, you could introduce biases or discard entropy without paying attention.
Quite right; and I would argue against trying to implement a /dev/random with PRNG and entropy injection. If a project needs this, choose an appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there are no low-rate system entropy sources such as the ones that makes random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or it’s too slow, but a source of fast “decent” random numbers is desired. That’s where /dev/urandom fits.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there is often a hardware RNG of sufficient quality that will provide random bits at a high enough rate for key generation or stuff like that, when it's required at all (who really needs RSA key generation on a nuttx embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is rare), then a proper CSPRNG such as Yarrow or another well designed generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if one needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed, which I doubt... the other option is to avoid /dev/urandom entirely, and use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be “wrong”, but it breaks the tradition that /dev/urandom doesn’t block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly complicated entropy pool management...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I advise against yet another low quality RNG in NuttX.
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
libc random is completely different. It has to be available even without hardware RNG and no one with a sane mind would think it is cryptographically secure. It could be implemented by xorshift128 as a replacement of the current generator if we wanted a "slightly better", but still fast, generator.
And on this we agree.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Sebastien
'Juha Niskanen (Haltian)' juha.niskanen@haltian.com [nuttx]
2016-07-17 16:05:17 UTC
Permalink
Hi David,


"Please, let’s not conflate /dev/urandom with /dev/random."


Your assumptions about /dev/urandom properties and usage do not match real world. There are lots and lots of security-related SW packages that assume and absolutely *NEED* /dev/urandom to be a CSPRGN. This includes most, if not all, TLS implementations. Take a look of mbedTLS function mbedtls_platform_entropy_poll() for instance (a colleague recently ported mbedTLS to NuttX):

https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c#L150<https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c>

Worse example comes from LibreSSL's _rs_stir() function:

https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96

that first tries to read from /dev/urandom, and if that fails, falls back to getting somewhat predictable values from gettimeofdate() and getpid()!


Now that Greg has accepted your patch, a developer porting these libs (and many others) to NuttX needs to be extra careful to NOT use the default /dev/urandom


"isn’t DES still OK?"


This is 2016. Plain DES should have died long ago. Please lets not add it into any new operating systems. NuttX is currently the best OS for IOT devices, but crypto and security need more work (I hope to contribute something if/when have the time).


Best Regards,

Juha Niskanen

________________________________
From: ***@yahoogroups.com <***@yahoogroups.com> on behalf of 'David S. Alessio' ***@gmail.com [nuttx] <***@yahoogroups.com>
Sent: Sunday, July 17, 2016 3:19:51 AM
To: ***@yahoogroups.com
Subject: Re: [nuttx] /dev/urandom



Hello Sebastien,

(please see comments below)

Best regards,
-david




On Jul 16, 2016, at 2:59 PM, Sebastien Lorquet ***@lorquet.fr<mailto:***@lorquet.fr> [nuttx] <***@yahoogroups.com<mailto:***@yahoogroups.com>> wrote:


Hello

Please forgive my rude choice of words, I probably have a lesser english knowledge than you may think :)

No worries. ;)


Also, your response clarified a lot of things, I dont think that my second email is useful now.

So if I understand correctly, you main idea is : linux urandom is good quality, nuttx is not linux, we dont need quality for nuttx urandom… ?


It all depends on the application, but I don’t want to allow “perfect” to become the enemy of “good enough” for the particular application in hand.


OK... lets forget Linux.

NuttX is not only for low-end microprocessors. On the contrary, it is more a RTOS for mid/high-end mcus. That's why I dont think that the argument about constrained memory holds.

I agree. But then we’ll have to revisit the [my?] assumption that the same algorithm compile/execute on all MCUs.


Also, there comes my remark about IoT security: Accepting that urandom is NOT a CSPRNG clearly makes us go in the bad IoT security route, which I dont like at all.

If we continue this route, if HW AES is not available on all chips, would you recommend DES? (or, xor?)

My view is it’s all relative to the application and its attraction to hackers. Plenty of papers have been written on the advantages of AES over DES and 3DES, but if my application is measuring temperature in my water heater and sending the sensor data to a website that does nothing more than plot the data, isn’t DES still OK?

As for xor, no, I wouldn’t use it by itself. It works well when combined 1 or 2 other operations… Perhaps xor | rot13 | rot13 ?


However, I could admit that the range of supported targets is so wide that a correct PRNG is not doable everywhere.

Yes, that’s a difficult constraint. I tried to strike a balance… How would you balance the constraints?



I would be okay if:
-we had multiple implementations (say: 2) for fast, non blocking random sources available at /dev/urandom

I’m OK with 3, but not 15+ ;)



-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config

I could not agree more! If we do this with xorshift128, “NOT CRYPTO SECURE” warnings should go everywhere.

How about:
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?

Does anyone really want Fortuna? Why would this be a better design choice than an MCU with dedicated HW?



-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32 bytes, a correct CSPRNG would not be the bigger NuttX subsystem.

Sure, this is acceptable.

Then we have the problem of how to “properly” seed and condition the PRNGs…



What about this?

Sebastien


On 16/07/2016 23:38, David Alessio ***@yahoo.com<mailto:***@yahoo.com> [nuttx] wrote:

Sebastien,

(see comments below)

Regards,
-david



On Jul 16, 2016, at 1:57 AM, Sebastien Lorquet ***@lorquet.fr<mailto:***@lorquet.fr> [nuttx] <***@yahoogroups.com<mailto:***@yahoogroups.com>> wrote:


Hello,


I let everyone remember that security in the IoT is globally crap,

This is true and I feel your frustration, but it’s an non sequitur.


so please lets not add more crap in that field…

Monsieur Sébastien, such statements are easy to misunderstand, but given that your English appears to be slightly better than my French, I’ll cut you some slack ;)



On 15/07/2016 15:44, <mailto:***@ziggurat29.com> ***@ziggurat29.com<mailto:***@ziggurat29.com> [nuttx] wrote:

I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).



Please, let’s not conflate /dev/urandom with /dev/random. Traditionally, /dev/urandom has been as source of uniformly distributed pseudorandom numbers, fast, and non-blocking — nothing more, nothing less.

One typical use is to wipe a 1GB drive:
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000

Create a garbage 1MB file:
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024



If either or both of these supported a configurable option of:
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)

Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.

Same here, CSPRNG or nothing.

I would agree with you here, but *only* with respect to /dev/random

/dev/random, if it exists, *must* be cryptographically secure. And it should use a HW RNG.


But let me remind you something. Linux has entropy problems: There are no hardware RNG in normal desktop computers, but there is a need for enough "entropy" (unpredictable random bits) for security reasons (generation of RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.

Linux has many problems. And that’s why I try to refrain from making references to Linux — it’s just examining a pathological case...

(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)


So, linux gathers entropy from multiple low rate sources (keystrokes, mouse mouvements, disk IO - often, each event generates one good bit, or less), but this random data is very scarce. Because of this, directly reading /dev/ramdom will deplete the entropy too fast, so the /dev/urandom CSPRNG was added to allow generation of enough pseudorandom bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: https://eprint.iacr.org/2006/086.pdf

Thanks for the link, but again, this is very Linux-specific.


Also, according to wikipedia: "On systems using the Linux kernel, programs needing significant amounts of random data from /dev/urandom<https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with programs reading little data from /dev/random<https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes /dev/random whenever it is being read.[6]<https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”

This, again, is a Linux-specific implementation. /dev/random and /dev/urandom don’t need to be related. It’s just that typically the implementation of /dev/random builds on top of /dev/urandom and injects entropy...



Entropy manipulation is not trivial, you could introduce biases or discard entropy without paying attention.

Quite right; and I would argue against trying to implement a /dev/random with PRNG and entropy injection. If a project needs this, choose an appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).



However, on embedded platforms targeted by nuttx, the conditions are different:
-there are no low-rate system entropy sources such as the ones that makes random necessary

There are several use cases were an MCU either doesn’t have HW RNG, or it’s too slow, but a source of fast “decent” random numbers is desired. That’s where /dev/urandom fits.


-there is often a hardware RNG of sufficient quality that will provide random bits at a high enough rate for key generation or stuff like that, when it's required at all (who really needs RSA key generation on a nuttx embedded platform?)

HW RNG is perfect for key generation, if needed, but it can be slow.

-if even more pseudorandom bits are required (with a hw rng, this is rare), then a proper CSPRNG such as Yarrow or another well designed generator should be used.

No, these are too heavy for a small MCU. Again, I would argue that if one needs that level of quality in a PRNG, choose an MCU with a HW RNG.



On 15/07/2016 19:58, 'Juha Niskanen (Haltian)' <mailto:***@haltian.com> ***@haltian.com<mailto:***@haltian.com> [nuttx] wrote:
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed, which I doubt... the other option is to avoid /dev/urandom entirely, and use /dev/random instead.

I haven’t explored FreeBSD. But if /dev/random blocks, it may not be “wrong”, but it breaks the tradition that /dev/urandom doesn’t block.

In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly complicated entropy pool management...


I advise against yet another low quality RNG in NuttX.


I’m happy to entertain an argument for a higher quality PRNG for /dev/urandom. But it has to:
— compile on all supported architectures
— be reasonably fast on those architectures
— never block


libc random is completely different. It has to be available even without hardware RNG and no one with a sane mind would think it is cryptographically secure. It could be implemented by xorshift128 as a replacement of the current generator if we wanted a "slightly better", but still fast, generator.

And on this we agree.


Sebastien
David Alessio david.alessio@yahoo.com [nuttx]
2016-07-17 19:20:22 UTC
Permalink
Juha, Sebastien, Greg,

Sebastien cracked my stubborn argument; Juha may have just shattered it. Thank you both.

Let me see if I can rephrase and strengthen their counterargument:

— the argument re /dev/urandom vs /dev/random may be valid in a historical perspective, but we need to take cognizance of reality. The reality is that the quality of /dev/urandom has evolved, in both Linux and *BSD spaces, to a point where today it’s commonly and correctly used by crypto libs. The fact is, both are assumed good sources of CSRNGs.
— NuttX is the best RTOS for IoT [I could not agree more; I can write a paper on this].
— People will port crypto libs to Nuttx without grokking that our /dev/urandom departs from their assumptions/experience of its quality on Linux/*BSD. And we will have thus enabled them to create insecure IoT devices.
— That risk, and the damage it will do to the NuttX brand, far outweigh any benefit of a simple/fast /dev/urandom.

I’m now convinced that the patch, as I submitted it, is too dangerous. Can we fix or rename it before it escapes into the wild?


Lets reset and start with a few design constraints. If we can converge on the design constraints, then the implementation should become self-evident. I’ll take a first stab:

We need to view this in the context of IoT and security (my initial mistake, I hacked up a quick driver for a quick problem…)

1) How should /dev/random be spec’d?

This has to be a CSRNG, should be based on a HW True RNG (TRNG).
It can block (HW TRNGs can be slow, usually interrupt-driven), but it must be deterministic (this is an RTOS after all).
If we accept that it must be deterministic, that rules out most/all entropy pool schemes.
And if the TRNG is “fast enough” (however we decide to define that), why would we need /dev/urandom?


2) How should /dev/urandom be spec’d? What minimum tests of randomness must it pass?

It should be based on a PRNG
must be cryptographically secure assuming properly seeded
must not block.
must generate uniformly distributed RNGs.
writing to /dev/urandom writes to the seed, important for testing.
given the same seed, it must reproduce the same data


3) PRNGs need to be seeded, not all seeds are equal. Depending on the seed, the PRNG may need to be cycled a few times before it stabilizes. Tests have shown “few times” can range from 10 to ~10000.
How do we best manage this?
Do we need an internal source of entropy (LSBs of an ADC, etc.) for the seed?
And if we don’t have one, do we disable /dev/urandom?


4) Do we need to support /dev/urandom on 8 and 16 bit MCUs.

I now think NO. It places too many constraints on the 32-bit+ implementation.
If needed, maybe it should be registered as something other than /dev/urandom



Finally, I want to follow up on Juha last comment re DES. Maybe I should have been more careful in framing my question so I’m not misunderstood as standing in support of DES. I believe DES should have disappeared a long time ago. But it hasn’t, why? Security isn’t black and white, it’s gray — a system is “secure” until computers become fast enough to crack it, or a researcher discovers a clever exploit… My question should have been posed more along the lines of: under what circumstances (if any) might DES, today, be “good enough?” I don’t want to open up a debate here, just clarify my thought behind that short and misleading question.

Best regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Hi David,
"Please, let’s not conflate /dev/urandom with /dev/random."
https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c#L150 <https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c>
https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96 <https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96>
that first tries to read from /dev/urandom, and if that fails, falls back to getting somewhat predictable values from gettimeofdate() and getpid()!
Now that Greg has accepted your patch, a developer porting these libs (and many others) to NuttX needs to be extra careful to NOT use the default /dev/urandom
"isn’t DES still OK?"
This is 2016. Plain DES should have died long ago. Please lets not add it into any new operating systems. NuttX is currently the best OS for IOT devices, but crypto and security need more work (I hope to contribute something if/when have the time).
Best Regards,
Juha Niskanen
Sent: Sunday, July 17, 2016 3:19:51 AM
Subject: Re: [nuttx] /dev/urandom
Hello Sebastien,
(please see comments below)
Best regards,
-david
Hello
Please forgive my rude choice of words, I probably have a lesser english knowledge than you may think :)
No worries. ;)
Also, your response clarified a lot of things, I dont think that my second email is useful now.
So if I understand correctly, you main idea is : linux urandom is good quality, nuttx is not linux, we dont need quality for nuttx urandom… ?
It all depends on the application, but I don’t want to allow “perfect” to become the enemy of “good enough” for the particular application in hand.
OK... lets forget Linux.
NuttX is not only for low-end microprocessors. On the contrary, it is more a RTOS for mid/high-end mcus. That's why I dont think that the argument about constrained memory holds.
I agree. But then we’ll have to revisit the [my?] assumption that the same algorithm compile/execute on all MCUs.
Also, there comes my remark about IoT security: Accepting that urandom is NOT a CSPRNG clearly makes us go in the bad IoT security route, which I dont like at all.
If we continue this route, if HW AES is not available on all chips, would you recommend DES? (or, xor?)
My view is it’s all relative to the application and its attraction to hackers. Plenty of papers have been written on the advantages of AES over DES and 3DES, but if my application is measuring temperature in my water heater and sending the sensor data to a website that does nothing more than plot the data, isn’t DES still OK?
As for xor, no, I wouldn’t use it by itself. It works well when combined 1 or 2 other operations… Perhaps xor | rot13 | rot13 ?
However, I could admit that the range of supported targets is so wide that a correct PRNG is not doable everywhere.
Yes, that’s a difficult constraint. I tried to strike a balance… How would you balance the constraints?
-we had multiple implementations (say: 2) for fast, non blocking random sources available at /dev/urandom
I’m OK with 3, but not 15+ ;)
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config
I could not agree more! If we do this with xorshift128, “NOT CRYPTO SECURE” warnings should go everywhere.
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?
Does anyone really want Fortuna? Why would this be a better design choice than an MCU with dedicated HW?
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32 bytes, a correct CSPRNG would not be the bigger NuttX subsystem.
Sure, this is acceptable.
Then we have the problem of how to “properly” seed and condition the PRNGs…
What about this?
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but given that your English appears to be slightly better than my French, I’ll cut you some slack ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random. Traditionally, /dev/urandom has been as source of uniformly distributed pseudorandom numbers, fast, and non-blocking — nothing more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And it should use a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
But let me remind you something. Linux has entropy problems: There are no hardware RNG in normal desktop computers, but there is a need for enough "entropy" (unpredictable random bits) for security reasons (generation of RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from making references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes, mouse mouvements, disk IO - often, each event generates one good bit, or less), but this random data is very scarce. Because of this, directly reading /dev/ramdom will deplete the entropy too fast, so the /dev/urandom CSPRNG was added to allow generation of enough pseudorandom bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: https://eprint.iacr.org/2006/086.pdf <https://eprint.iacr.org/2006/086.pdf>
Thanks for the link, but again, this is very Linux-specific.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel, programs needing significant amounts of random data from /dev/urandom <https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with programs reading little data from /dev/random <https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes /dev/random whenever it is being read.[6] <https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and /dev/urandom don’t need to be related. It’s just that typically the implementation of /dev/random builds on top of /dev/urandom and injects entropy...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Entropy manipulation is not trivial, you could introduce biases or discard entropy without paying attention.
Quite right; and I would argue against trying to implement a /dev/random with PRNG and entropy injection. If a project needs this, choose an appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there are no low-rate system entropy sources such as the ones that makes random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or it’s too slow, but a source of fast “decent” random numbers is desired. That’s where /dev/urandom fits.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there is often a hardware RNG of sufficient quality that will provide random bits at a high enough rate for key generation or stuff like that, when it's required at all (who really needs RSA key generation on a nuttx embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is rare), then a proper CSPRNG such as Yarrow or another well designed generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if one needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed, which I doubt... the other option is to avoid /dev/urandom entirely, and use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be “wrong”, but it breaks the tradition that /dev/urandom doesn’t block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly complicated entropy pool management...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I advise against yet another low quality RNG in NuttX.
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
libc random is completely different. It has to be available even without hardware RNG and no one with a sane mind would think it is cryptographically secure. It could be implemented by xorshift128 as a replacement of the current generator if we wanted a "slightly better", but still fast, generator.
And on this we agree.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Sebastien
spudarnia@yahoo.com [nuttx]
2016-07-17 19:53:11 UTC
Permalink
I think I have enough warnings in the Kconfig file with regard to /dev/urandom. You might check to see if the warning need beefed up, but otherwise, I don't think the is an immediate need for a change.

If I understand right, what you need is a higher performance software CPRNG. Is that righ?

I ran across these standard interfaces: http://pubs.opengroup.org/onlinepubs/7908799/xsh/drand48.html

Would those meet the need? Do congruential algorithms, in general, meet the need? If so, the srand() congruential generator may be okay (albeit slow).

Greg
Sebastien Lorquet sebastien@lorquet.fr [nuttx]
2016-07-18 05:42:26 UTC
Permalink
Hello,

I added replies below.
Post by David Alessio ***@yahoo.com [nuttx]
Juha, Sebastien, Greg,
Sebastien cracked my stubborn argument; Juha may have just shattered it. Thank you both.
— the argument re /dev/urandom vs /dev/random may be valid in a
historical perspective, but we need to take cognizance of reality.
The reality is that the quality of /dev/urandom has evolved, in both
Linux and *BSD spaces, to a point where today it’s commonly and
correctly used by crypto libs. The fact is, both are assumed good
sources of CSRNGs.
— NuttX is the best RTOS for IoT [I could not agree more; I can write a paper on this].
— People will port crypto libs to Nuttx without grokking that our
/dev/urandom departs from their assumptions/experience of its quality
on Linux/*BSD. And we will have thus enabled them to create insecure
IoT devices.
— That risk, and the damage it will do to the NuttX brand, far
outweigh any benefit of a simple/fast /dev/urandom.
I’m now convinced that the patch, as I submitted it, is too dangerous.
Can we fix or rename it before it escapes into the wild?
Thanks, I really appreciate that we come back to interesting discussion.
Post by David Alessio ***@yahoo.com [nuttx]
Lets reset and start with a few design constraints. If we can
converge on the design constraints, then the implementation should
We need to view this in the context of IoT and security (my initial
mistake, I hacked up a quick driver for a quick problem…)
1) How should /dev/random be spec’d?
This has to be a CSRNG, should be based on a HW True RNG (TRNG).
Most drivers for /dev/random in nuttx outputs the raw data from the
TRNG, but this is not a problem, because all RNGs in SoCs are designed
for this usage (they often include a LFSR). This should not be done
unless the reference manual says so, I know some chips where the RNG
output must be debiased, verified, and used as input to a CSPRNG.
Post by David Alessio ***@yahoo.com [nuttx]
It can block (HW TRNGs can be slow, usually interrupt-driven), but it
must be deterministic (this is an RTOS after all).
What do you mean by deterministic? see below.
Post by David Alessio ***@yahoo.com [nuttx]
If we accept that it must be deterministic, that rules out most/all entropy pool schemes.
And if the TRNG is “fast enough” (however we decide to define that),
why would we need /dev/urandom?
2) How should /dev/urandom be spec’d? What minimum tests of
randomness must it pass?
It should be based on a PRNG
must be cryptographically secure assuming properly seeded
must not block.
The last two are a kind of conflict or compromise. If you want good
crypto properties, you have to seed regularly, but.. the reseed itself
is not guaranteed to be posssible at a given date. This means that
crypto quality will vary, this is acceptable. We only need to ensure a
predetermined minimum quality. Note: I would not be bothered by a
urandom that finally blocks after it was not seeded for a very long time
(this time depends on the PRNG), or warns you that random quality is too
low.
Post by David Alessio ***@yahoo.com [nuttx]
must generate uniformly distributed RNGs.
This is one of the randomness tests.
Post by David Alessio ***@yahoo.com [nuttx]
writing to /dev/urandom writes to the seed, important for testing.
given the same seed, it must reproduce the same data
The last requirement is a consequence of being pseudo random. This is
the real meaning of "deterministic" for RNGs. The reverse is
non-deterministic, this is the nature of True RNGs.
Post by David Alessio ***@yahoo.com [nuttx]
3) PRNGs need to be seeded, not all seeds are equal. Depending on the
seed, the PRNG may need to be cycled a few times before it stabilizes.
Tests have shown “few times” can range from 10 to ~10000.
How do we best manage this?
Um... By choosing a PRNG that stabilizes in ~10 rounds instead of ~10000? :p

This is the difficulty of a proper urandom on an embedded platform.
Post by David Alessio ***@yahoo.com [nuttx]
Do we need an internal source of entropy (LSBs of an ADC, etc.) for the seed?
Yes. And, you also ideally need a writable filesystem to save the seed
when the system is shut down, and restore it at next boot, because it
can take a long time with low rate sources until the full entropy pool
is replenished. At least that's the case in Linux...
Post by David Alessio ***@yahoo.com [nuttx]
And if we don’t have one, do we disable /dev/urandom?
Security wise, I think that it would be safe and sane. Reusing the same
seed at successive boot events means that software tools will generate
the exact same keys and nonces, which is dangerous. An alternative is to
block (once) until the pool has gathered enough fresh entropy from the
non-deterministic sources.

I am working in a crypto environment. We have a rule: Dont invent new
crypto mechanisms if there exists an algorithm for our purpose. It is
dangerous to design crypto algorithms from scratch, because a small
mistake can become a full disaster unknowingly. So I would suggest a
litterature review of "good" CSPRNGs. Most of them will be based on a
solid hash algorithm, because this algs cannot be reversed, provided
they do not have collisions (this would make the PRNG to wrap around) .
I would really suggest evaluation of Bruce Schneier work in this domain,
he designed some "solid" CSPRNGs. They may not be slow nor memory
expensive, they may be worth implementing and evaluating.

Greg: I dont think that linear congruence algorithms are CSPRNGs but
this would has to be verified.

An important feature, is that any "brand new" CSPRNG should be at least
tested using RNG test suites. Wikipedia entry about xorshift names a few.
Post by David Alessio ***@yahoo.com [nuttx]
4) Do we need to support /dev/urandom on 8 and 16 bit MCUs.
I now think NO. It places too many constraints on the 32-bit+
implementation.
If needed, maybe it should be registered as something other than /dev/urandom
NuttX is probably only for 32-bit targets I think. hah, atmel and z80...
... okay :p
Post by David Alessio ***@yahoo.com [nuttx]
Finally, I want to follow up on Juha last comment re DES. Maybe I
should have been more careful in framing my question so I’m not
misunderstood as standing in support of DES. I believe DES should
have disappeared a long time ago. But it hasn’t, why? Security isn’t
black and white, it’s gray — a system is “secure” until computers
become fast enough to crack it, or a researcher discovers a clever
under what circumstances (if any) might DES, today, be “good enough?”
I don’t want to open up a debate here, just clarify my thought behind
that short and misleading question.
If I understand correctly, Simple DES was broken by the EFF in 1998. It
is not considered as a secure algorithm anymore. So it is good enough
for nothing. However, triple-des (DES-EDE, TDEA) (with two or three
keys) offers an acceptable security level (this is difficult to define
:) ) for a lot of things that still require 8-byte data blocks. All of
this is no secret, it is wikipedia wisdom :)

Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Best regards,
-david
On Jul 17, 2016, at 9:05 AM, 'Juha Niskanen (Haltian)'
Hi David,
"Please, let’s not conflate /dev/urandom with /dev/random."
Your assumptions about /dev/urandom properties and usage do not match
real world. There are lots and lots of security-related SW packages
that assume and absolutely *NEED* /dev/urandom to be a CSPRGN. This
includes most, if not all, TLS implementations. Take a look of
mbedTLS function mbedtls_platform_entropy_poll() for instance (a
https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c#L150
<https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c>
https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96
that first tries to read from /dev/urandom, and if that fails, falls
back to getting somewhat predictable values from gettimeofdate() and
getpid()!
Now that Greg has accepted your patch, a developer porting these libs
(and many others) to NuttX needs to be extra careful to NOT use the
default /dev/urandom
"isn’t DES still OK?"
This is 2016. Plain DES should have died long ago. Please lets not
add it into any new operating systems. NuttX is currently the best OS
for IOT devices, but crypto and security need more work (I hope to
contribute something if/when have the time).
Best Regards,
Juha Niskanen
------------------------------------------------------------------------
*Sent:* Sunday, July 17, 2016 3:19:51 AM
*Subject:* Re: [nuttx] /dev/urandom
Hello Sebastien,
(please see comments below)
Best regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On Jul 16, 2016, at 2:59 PM, Sebastien
Hello
Please forgive my rude choice of words, I probably have a lesser
english knowledge than you may think :)
No worries. ;)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Also, your response clarified a lot of things, I dont think that my
second email is useful now.
So if I understand correctly, you main idea is : linux urandom is
good quality, nuttx is not linux, we dont need quality for nuttx
urandom… ?
It all depends on the application, but I don’t want to allow
“perfect” to become the enemy of “good enough” for the particular
application in hand.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
OK... lets forget Linux.
NuttX is not only for low-end microprocessors. On the contrary, it
is more a RTOS for mid/high-end mcus. That's why I dont think that
the argument about constrained memory holds.
I agree. But then we’ll have to revisit the [my?] assumption that
the same algorithm compile/execute on all MCUs.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Also, there comes my remark about IoT security: Accepting that
urandom is NOT a CSPRNG clearly makes us go in the bad IoT security
route, which I dont like at all.
If we continue this route, if HW AES is not available on all chips,
would you recommend DES? (or, xor?)
My view is it’s all relative to the application and its attraction to
hackers. Plenty of papers have been written on the advantages of AES
over DES and 3DES, but if my application is measuring temperature in
my water heater and sending the sensor data to a website that does
nothing more than plot the data, isn’t DES still OK?
As for xor, no, I wouldn’t use it by itself. It works well when
combined 1 or 2 other operations… Perhaps xor | rot13 | rot13 ?
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
However, I could admit that the range of supported targets is so
wide that a correct PRNG is not doable everywhere.
Yes, that’s a difficult constraint. I tried to strike a balance…
How would you balance the constraints?
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-we had multiple implementations (say: 2) for fast, non blocking
random sources available at /dev/urandom
I’m OK with 3, but not 15+ ;)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config
I could not agree more! If we do this with xorshift128, “NOT CRYPTO
SECURE” warnings should go everywhere.
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?
Does anyone really want Fortuna? Why would this be a better design
choice than an MCU with dedicated HW?
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer
is 32 bytes, a correct CSPRNG would not be the bigger NuttX subsystem.
Sure, this is acceptable.
Then we have the problem of how to “properly” seed and condition the PRNGs…
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
What about this?
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On Jul 16, 2016, at 1:57 AM, Sebastien
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but
given that your English appears to be slightly better than my
French, I’ll cut you some slack ;)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be
that is a CSPRNG. We do already have /dev/random (well, I guess
it is dependent on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random.
Traditionally, /dev/urandom has been as source of uniformly
distributed pseudorandom numbers, fast, and non-blocking — nothing
more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is
now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I
believe David is suggesting)
* some externally provided implementation (for those who are
picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably
merge all the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And
it should use a HW RNG.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
But let me remind you something. Linux has entropy problems: There
are no hardware RNG in normal desktop computers, but there is a
need for enough "entropy" (unpredictable random bits) for security
reasons (generation of RSA keys, openssl, ssh, etc). - we dont
have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from
making references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
So, linux gathers entropy from multiple low rate sources
(keystrokes, mouse mouvements, disk IO - often, each event
generates one good bit, or less), but this random data is very
scarce. Because of this, directly reading /dev/ramdom will deplete
the entropy too fast, so the /dev/urandom CSPRNG was added to
allow generation of enough pseudorandom bits even if the real
entropy has a far lower rate.
Here is a doc describing the linux
RNGs: https://eprint.iacr.org/2006/086.pdf
Thanks for the link, but again, this is very Linux-specific.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel,
programs needing significant amounts of random data
from /dev/urandom
<https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with
programs reading little data from /dev/random
<https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom
depletes /dev/random whenever it is being read.^[6]
<https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and
/dev/urandom don’t need to be related. It’s just that typically
the implementation of /dev/random builds on top of /dev/urandom and
injects entropy...
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Entropy manipulation is not trivial, you could introduce biases or
discard entropy without paying attention.
Quite right; and I would argue against trying to implement a
/dev/random with PRNG and entropy injection. If a project needs
this, choose an appropriate MCU — one that has a HW RNG (PIC32MZ,
STM32F4xx, etc.).
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-there are no low-rate system entropy sources such as the ones
that makes random necessary
There are several use cases were an MCU either doesn’t have HW RNG,
or it’s too slow, but a source of fast “decent” random numbers is
desired. That’s where /dev/urandom fits.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-there is often a hardware RNG of sufficient quality that will
provide random bits at a high enough rate for key generation or
stuff like that, when it's required at all (who really needs RSA
key generation on a nuttx embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this
is rare), then a proper CSPRNG such as Yarrow or another well
designed generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that
if one needs that level of quality in a PRNG, choose an MCU with a
HW RNG.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On 15/07/2016 19:58, 'Juha Niskanen
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be
changed, which I doubt... the other option is to avoid
/dev/urandom entirely, and use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not
be “wrong”, but it breaks the tradition that /dev/urandom doesn’t
block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some
fairly complicated entropy pool management...
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
I advise against yet another low quality RNG in NuttX.
I’m happy to entertain an argument for a higher quality PRNG for
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
libc random is completely different. It has to be available even
without hardware RNG and no one with a sane mind would think it is
cryptographically secure. It could be implemented by xorshift128
as a replacement of the current generator if we wanted a "slightly
better", but still fast, generator.
And on this we agree.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Sebastien
David Alessio david.alessio@yahoo.com [nuttx]
2016-07-18 07:48:19 UTC
Permalink
Sebastien,

Please see inline comments below

Cheers,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I added replies below.
Post by David Alessio ***@yahoo.com [nuttx]
Juha, Sebastien, Greg,
Sebastien cracked my stubborn argument; Juha may have just shattered it. Thank you both.
— the argument re /dev/urandom vs /dev/random may be valid in a historical perspective, but we need to take cognizance of reality. The reality is that the quality of /dev/urandom has evolved, in both Linux and *BSD spaces, to a point where today it’s commonly and correctly used by crypto libs. The fact is, both are assumed good sources of CSRNGs.
— NuttX is the best RTOS for IoT [I could not agree more; I can write a paper on this].
— People will port crypto libs to Nuttx without grokking that our /dev/urandom departs from their assumptions/experience of its quality on Linux/*BSD. And we will have thus enabled them to create insecure IoT devices.
— That risk, and the damage it will do to the NuttX brand, far outweigh any benefit of a simple/fast /dev/urandom.
I’m now convinced that the patch, as I submitted it, is too dangerous. Can we fix or rename it before it escapes into the wild?
Thanks, I really appreciate that we come back to interesting discussion.
Post by David Alessio ***@yahoo.com [nuttx]
We need to view this in the context of IoT and security (my initial mistake, I hacked up a quick driver for a quick problem…)
1) How should /dev/random be spec’d?
This has to be a CSRNG, should be based on a HW True RNG (TRNG).
Most drivers for /dev/random in nuttx outputs the raw data from the TRNG, but this is not a problem, because all RNGs in SoCs are designed for this usage (they often include a LFSR). This should not be done unless the reference manual says so, I know some chips where the RNG output must be debiased, verified, and used as input to a CSPRNG.
Post by David Alessio ***@yahoo.com [nuttx]
It can block (HW TRNGs can be slow, usually interrupt-driven), but it must be deterministic (this is an RTOS after all).
What do you mean by deterministic? see below.
Sorry, I mean temporally deterministic. The single most important quality of an RTOS is that its response time can be calculated (it’s deterministic). The calculation may or may not be easy, but it’s possible and the response time is bounded (never greater than X).
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by David Alessio ***@yahoo.com [nuttx]
If we accept that it must be deterministic, that rules out most/all entropy pool schemes.
And if the TRNG is “fast enough” (however we decide to define that), why would we need /dev/urandom?
2) How should /dev/urandom be spec’d? What minimum tests of randomness must it pass?
It should be based on a PRNG
must be cryptographically secure assuming properly seeded
must not block.
The last two are a kind of conflict or compromise. If you want good crypto properties, you have to seed regularly, but.. the reseed itself is not guaranteed to be posssible at a given date. This means that crypto quality will vary, this is acceptable. We only need to ensure a predetermined minimum quality. Note: I would not be bothered by a urandom that finally blocks after it was not seeded for a very long time (this time depends on the PRNG), or warns you that random quality is too low.
Post by David Alessio ***@yahoo.com [nuttx]
must generate uniformly distributed RNGs.
This is one of the randomness tests.
Post by David Alessio ***@yahoo.com [nuttx]
writing to /dev/urandom writes to the seed, important for testing.
given the same seed, it must reproduce the same data
The last requirement is a consequence of being pseudo random. This is the real meaning of "deterministic" for RNGs. The reverse is non-deterministic, this is the nature of True RNGs.
Post by David Alessio ***@yahoo.com [nuttx]
3) PRNGs need to be seeded, not all seeds are equal. Depending on the seed, the PRNG may need to be cycled a few times before it stabilizes. Tests have shown “few times” can range from 10 to ~10000.
How do we best manage this?
Um... By choosing a PRNG that stabilizes in ~10 rounds instead of ~10000? :p
What would you suggest?

maybe xorshift1024* ?
ref: http://vigna.di.unimi.it/ftp/papers/xorshift.pdf <http://vigna.di.unimi.it/ftp/papers/xorshift.pdf>

Keccak? It’s computationally expensive.
http://sponge.noekeon.org/SpongePRNG.pdf
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
This is the difficulty of a proper urandom on an embedded platform.
Post by David Alessio ***@yahoo.com [nuttx]
Do we need an internal source of entropy (LSBs of an ADC, etc.) for the seed?
Yes. And, you also ideally need a writable filesystem to save the seed when the system is shut down, and restore it at next boot, because it can take a long time with low rate sources until the full entropy pool is replenished. At least that's the case in Linux...
Post by David Alessio ***@yahoo.com [nuttx]
And if we don’t have one, do we disable /dev/urandom?
Security wise, I think that it would be safe and sane. Reusing the same seed at successive boot events means that software tools will generate the exact same keys and nonces, which is dangerous. An alternative is to block (once) until the pool has gathered enough fresh entropy from the non-deterministic sources.
Agreed.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I am working in a crypto environment. We have a rule: Dont invent new crypto mechanisms if there exists an algorithm for our purpose. It is dangerous to design crypto algorithms from scratch, because a small mistake can become a full disaster unknowingly. So I would suggest a litterature review of "good" CSPRNGs. Most of them will be based on a solid hash algorithm, because this algs cannot be reversed, provided they do not have collisions (this would make the PRNG to wrap around) . I would really suggest evaluation of Bruce Schneier work in this domain, he designed some "solid" CSPRNGs. They may not be slow nor memory expensive, they may be worth implementing and evaluating.
Greg: I dont think that linear congruence algorithms are CSPRNGs but this would has to be verified.
It’s been shown that Linear Congruent Generators (LCG) are not acceptable for CSPRNGs. But an LCG with a nonlinear operation (+ or *, for example) may be acceptable.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
An important feature, is that any "brand new" CSPRNG should be at least tested using RNG test suites. Wikipedia entry about xorshift names a few.
We should choose a CSPRNG that has at least been vetted by a few experts.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by David Alessio ***@yahoo.com [nuttx]
4) Do we need to support /dev/urandom on 8 and 16 bit MCUs.
I now think NO. It places too many constraints on the 32-bit+ implementation.
If needed, maybe it should be registered as something other than /dev/urandom
NuttX is probably only for 32-bit targets I think. hah, atmel and z80... ... okay :p
Post by David Alessio ***@yahoo.com [nuttx]
Finally, I want to follow up on Juha last comment re DES. Maybe I should have been more careful in framing my question so I’m not misunderstood as standing in support of DES. I believe DES should have disappeared a long time ago. But it hasn’t, why? Security isn’t black and white, it’s gray — a system is “secure” until computers become fast enough to crack it, or a researcher discovers a clever exploit… My question should have been posed more along the lines of: under what circumstances (if any) might DES, today, be “good enough?” I don’t want to open up a debate here, just clarify my thought behind that short and misleading question.
If I understand correctly, Simple DES was broken by the EFF in 1998. It is not considered as a secure algorithm anymore. So it is good enough for nothing. However, triple-des (DES-EDE, TDEA) (with two or three keys) offers an acceptable security level (this is difficult to define :) ) for a lot of things that still require 8-byte data blocks. All of this is no secret, it is wikipedia wisdom :)
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Best regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Hi David,
"Please, let’s not conflate /dev/urandom with /dev/random."
https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c#L150 <https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c>
https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96 <https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96>
that first tries to read from /dev/urandom, and if that fails, falls back to getting somewhat predictable values from gettimeofdate() and getpid()!
Now that Greg has accepted your patch, a developer porting these libs (and many others) to NuttX needs to be extra careful to NOT use the default /dev/urandom
"isn’t DES still OK?"
This is 2016. Plain DES should have died long ago. Please lets not add it into any new operating systems. NuttX is currently the best OS for IOT devices, but crypto and security need more work (I hope to contribute something if/when have the time).
Best Regards,
Juha Niskanen
Sent: Sunday, July 17, 2016 3:19:51 AM
Subject: Re: [nuttx] /dev/urandom
Hello Sebastien,
(please see comments below)
Best regards,
-david
Hello
Please forgive my rude choice of words, I probably have a lesser english knowledge than you may think :)
No worries. ;)
Also, your response clarified a lot of things, I dont think that my second email is useful now.
So if I understand correctly, you main idea is : linux urandom is good quality, nuttx is not linux, we dont need quality for nuttx urandom… ?
It all depends on the application, but I don’t want to allow “perfect” to become the enemy of “good enough” for the particular application in hand.
OK... lets forget Linux.
NuttX is not only for low-end microprocessors. On the contrary, it is more a RTOS for mid/high-end mcus. That's why I dont think that the argument about constrained memory holds.
I agree. But then we’ll have to revisit the [my?] assumption that the same algorithm compile/execute on all MCUs.
Also, there comes my remark about IoT security: Accepting that urandom is NOT a CSPRNG clearly makes us go in the bad IoT security route, which I dont like at all.
If we continue this route, if HW AES is not available on all chips, would you recommend DES? (or, xor?)
My view is it’s all relative to the application and its attraction to hackers. Plenty of papers have been written on the advantages of AES over DES and 3DES, but if my application is measuring temperature in my water heater and sending the sensor data to a website that does nothing more than plot the data, isn’t DES still OK?
As for xor, no, I wouldn’t use it by itself. It works well when combined 1 or 2 other operations… Perhaps xor | rot13 | rot13 ?
However, I could admit that the range of supported targets is so wide that a correct PRNG is not doable everywhere.
Yes, that’s a difficult constraint. I tried to strike a balance… How would you balance the constraints?
-we had multiple implementations (say: 2) for fast, non blocking random sources available at /dev/urandom
I’m OK with 3, but not 15+ ;)
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config
I could not agree more! If we do this with xorshift128, “NOT CRYPTO SECURE” warnings should go everywhere.
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?
Does anyone really want Fortuna? Why would this be a better design choice than an MCU with dedicated HW?
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32 bytes, a correct CSPRNG would not be the bigger NuttX subsystem.
Sure, this is acceptable.
Then we have the problem of how to “properly” seed and condition the PRNGs…
What about this?
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but given that your English appears to be slightly better than my French, I’ll cut you some slack ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random. Traditionally, /dev/urandom has been as source of uniformly distributed pseudorandom numbers, fast, and non-blocking — nothing more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And it should use a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
But let me remind you something. Linux has entropy problems: There are no hardware RNG in normal desktop computers, but there is a need for enough "entropy" (unpredictable random bits) for security reasons (generation of RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from making references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes, mouse mouvements, disk IO - often, each event generates one good bit, or less), but this random data is very scarce. Because of this, directly reading /dev/ramdom will deplete the entropy too fast, so the /dev/urandom CSPRNG was added to allow generation of enough pseudorandom bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: <https://eprint.iacr.org/2006/086.pdf>https://eprint.iacr.org/2006/086.pdf <https://eprint.iacr.org/2006/086.pdf>
Thanks for the link, but again, this is very Linux-specific.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel, programs needing significant amounts of random data from /dev/urandom <https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with programs reading little data from /dev/random <https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes /dev/random whenever it is being read.[6] <https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and /dev/urandom don’t need to be related. It’s just that typically the implementation of /dev/random builds on top of /dev/urandom and injects entropy...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Entropy manipulation is not trivial, you could introduce biases or discard entropy without paying attention.
Quite right; and I would argue against trying to implement a /dev/random with PRNG and entropy injection. If a project needs this, choose an appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there are no low-rate system entropy sources such as the ones that makes random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or it’s too slow, but a source of fast “decent” random numbers is desired. That’s where /dev/urandom fits.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-there is often a hardware RNG of sufficient quality that will provide random bits at a high enough rate for key generation or stuff like that, when it's required at all (who really needs RSA key generation on a nuttx embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is rare), then a proper CSPRNG such as Yarrow or another well designed generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if one needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed, which I doubt... the other option is to avoid /dev/urandom entirely, and use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be “wrong”, but it breaks the tradition that /dev/urandom doesn’t block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly complicated entropy pool management...
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I advise against yet another low quality RNG in NuttX.
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
libc random is completely different. It has to be available even without hardware RNG and no one with a sane mind would think it is cryptographically secure. It could be implemented by xorshift128 as a replacement of the current generator if we wanted a "slightly better", but still fast, generator.
And on this we agree.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Sebastien
Sebastien Lorquet sebastien@lorquet.fr [nuttx]
2016-07-18 08:41:57 UTC
Permalink
Hello,

Again, comments included below.
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
Please see inline comments below
Cheers,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I added replies below.
Post by David Alessio ***@yahoo.com [nuttx]
Juha, Sebastien, Greg,
Sebastien cracked my stubborn argument; Juha may have just shattered it.
Thank you both.
— the argument re /dev/urandom vs /dev/random may be valid in a historical
perspective, but we need to take cognizance of reality. The reality is that
the quality of /dev/urandom has evolved, in both Linux and *BSD spaces, to a
point where today it’s commonly and correctly used by crypto libs. The fact
is, both are assumed good sources of CSRNGs.
— NuttX is the best RTOS for IoT [I could not agree more; I can write a
paper on this].
— People will port crypto libs to Nuttx without grokking that our
/dev/urandom departs from their assumptions/experience of its quality on
Linux/*BSD. And we will have thus enabled them to create insecure IoT devices.
— That risk, and the damage it will do to the NuttX brand, far outweigh any
benefit of a simple/fast /dev/urandom.
I’m now convinced that the patch, as I submitted it, is too dangerous. Can
we fix or rename it before it escapes into the wild?
Thanks, I really appreciate that we come back to interesting discussion.
Post by David Alessio ***@yahoo.com [nuttx]
Lets reset and start with a few design constraints. If we can converge on
the design constraints, then the implementation should become self-evident.
We need to view this in the context of IoT and security (my initial mistake,
I hacked up a quick driver for a quick problem…)
1) How should /dev/random be spec’d?
This has to be a CSRNG, should be based on a HW True RNG (TRNG).
Most drivers for /dev/random in nuttx outputs the raw data from the TRNG, but
this is not a problem, because all RNGs in SoCs are designed for this usage
(they often include a LFSR). This should not be done unless the reference
manual says so, I know some chips where the RNG output must be debiased,
verified, and used as input to a CSPRNG.
Post by David Alessio ***@yahoo.com [nuttx]
It can block (HW TRNGs can be slow, usually interrupt-driven), but it must be
deterministic (this is an RTOS after all).
What do you mean by deterministic? see below.
Sorry, I mean temporally deterministic. The single most important quality of an
RTOS is that its response time can be calculated (it’s deterministic). The
calculation may or may not be easy, but it’s possible and the response time is
bounded (never greater than X).
Okay, and, sure. I think that most PRNGs will have a bounded execution time,
since they dont depend on external entropy collection. In this case they are
"temporally deterministic" because they are, well, deterministic :)
Post by David Alessio ***@yahoo.com [nuttx]
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by David Alessio ***@yahoo.com [nuttx]
If we accept that it must be deterministic, that rules out most/all entropy
pool schemes.
And if the TRNG is “fast enough” (however we decide to define that), why
would we need /dev/urandom?
2) How should /dev/urandom be spec’d? What minimum tests of randomness must
it pass?
It should be based on a PRNG
must be cryptographically secure assuming properly seeded
must not block.
The last two are a kind of conflict or compromise. If you want good crypto
properties, you have to seed regularly, but.. the reseed itself is not
guaranteed to be posssible at a given date. This means that crypto quality
will vary, this is acceptable. We only need to ensure a predetermined minimum
quality. Note: I would not be bothered by a urandom that finally blocks after
it was not seeded for a very long time (this time depends on the PRNG), or
warns you that random quality is too low.
Post by David Alessio ***@yahoo.com [nuttx]
must generate uniformly distributed RNGs.
This is one of the randomness tests.
Post by David Alessio ***@yahoo.com [nuttx]
writing to /dev/urandom writes to the seed, important for testing.
given the same seed, it must reproduce the same data
The last requirement is a consequence of being pseudo random. This is the real
meaning of "deterministic" for RNGs. The reverse is non-deterministic, this is
the nature of True RNGs.
Post by David Alessio ***@yahoo.com [nuttx]
3) PRNGs need to be seeded, not all seeds are equal. Depending on the seed,
the PRNG may need to be cycled a few times before it stabilizes. Tests have
shown “few times” can range from 10 to ~10000.
How do we best manage this?
Um... By choosing a PRNG that stabilizes in ~10 rounds instead of ~10000? :p
What would you suggest?
maybe xorshift1024* ?
ref: http://vigna.di.unimi.it/ftp/papers/xorshift.pdf
Keccak? It’s computationally expensive.
http://sponge.noekeon.org/SpongePRNG.pdf
yes, kekkac feels like a rather complex hash algorithm.

Wikipedia (again!) has a list:

https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

Anything based on bignums (EC, Diffie Hellman) will be slow.

NIST approved algorithms except Dual_EC_DRBG could be a good idea, they have
been studied extensively.

http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf

( https://en.wikipedia.org/wiki/Dual_EC_DRBG )

I think that Hash_DRBG using SHA-256 is worth testing. It would be a good
opportunity to bring this good hash into NuttX.

Also this NeuG project tries to make an embedded TRNG in an STM32F103, maybe
this can be an inspiration? It is based on SHA-256 :)

http://www.gniibe.org/memo/development/gnuk/rng/neug.html

( You said that you had a crypto subsystem in mind for nuttx, I also have, we
can talk about that later).
Post by David Alessio ***@yahoo.com [nuttx]
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
This is the difficulty of a proper urandom on an embedded platform.
Post by David Alessio ***@yahoo.com [nuttx]
Do we need an internal source of entropy (LSBs of an ADC, etc.) for the seed?
Yes. And, you also ideally need a writable filesystem to save the seed when
the system is shut down, and restore it at next boot, because it can take a
long time with low rate sources until the full entropy pool is replenished. At
least that's the case in Linux...
Post by David Alessio ***@yahoo.com [nuttx]
And if we don’t have one, do we disable /dev/urandom?
Security wise, I think that it would be safe and sane. Reusing the same seed
at successive boot events means that software tools will generate the exact
same keys and nonces, which is dangerous. An alternative is to block (once)
until the pool has gathered enough fresh entropy from the non-deterministic
sources.
Agreed.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I am working in a crypto environment. We have a rule: Dont invent new crypto
mechanisms if there exists an algorithm for our purpose. It is dangerous to
design crypto algorithms from scratch, because a small mistake can become a
full disaster unknowingly. So I would suggest a litterature review of "good"
CSPRNGs. Most of them will be based on a solid hash algorithm, because this
algs cannot be reversed, provided they do not have collisions (this would make
the PRNG to wrap around) . I would really suggest evaluation of Bruce Schneier
work in this domain, he designed some "solid" CSPRNGs. They may not be slow
nor memory expensive, they may be worth implementing and evaluating.
Greg: I dont think that linear congruence algorithms are CSPRNGs but this
would has to be verified.
It’s been shown that Linear Congruent Generators (LCG) are not acceptable for
CSPRNGs. But an LCG with a nonlinear operation (+ or *, for example) may be
acceptable.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
An important feature, is that any "brand new" CSPRNG should be at least tested
using RNG test suites. Wikipedia entry about xorshift names a few.
We should choose a CSPRNG that has at least been vetted by a few experts.
I agree.

As said before, we can go with the NIST (Hash_DRBG) or with Bruce Schneier
(Yarrow, Fortuna). arc4_random is probably usable (AND lightweight) if enough
output is discarded from the beginning of the stream. Also, block ciphers in
counter mode, but the "fast" option will then require hardware crypto acceleration.

But algo choice is just a part of the design. We also need entropy collection or
these RNG are just bit pattern generators. This is easily solved for platforms
with a HW RNG, but something has to be done for the situations where the HW RNG
is disabled or unavailable.

Sebastien
----------
Post by David Alessio ***@yahoo.com [nuttx]
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by David Alessio ***@yahoo.com [nuttx]
4) Do we need to support /dev/urandom on 8 and 16 bit MCUs.
I now think NO. It places too many constraints on the 32-bit+ implementation.
If needed, maybe it should be registered as something other than /dev/urandom
NuttX is probably only for 32-bit targets I think. hah, atmel and z80... ... okay :p
Post by David Alessio ***@yahoo.com [nuttx]
Finally, I want to follow up on Juha last comment re DES. Maybe I should
have been more careful in framing my question so I’m not misunderstood as
standing in support of DES. I believe DES should have disappeared a long
time ago. But it hasn’t, why? Security isn’t black and white, it’s gray — a
system is “secure” until computers become fast enough to crack it, or a
researcher discovers a clever exploit… My question should have been posed
more along the lines of: under what circumstances (if any) might DES, today,
be “good enough?” I don’t want to open up a debate here, just clarify my
thought behind that short and misleading question.
If I understand correctly, Simple DES was broken by the EFF in 1998. It is not
considered as a secure algorithm anymore. So it is good enough for nothing.
However, triple-des (DES-EDE, TDEA) (with two or three keys) offers an
acceptable security level (this is difficult to define :) ) for a lot of
things that still require 8-byte data blocks. All of this is no secret, it is
wikipedia wisdom :)
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Best regards,
-david
On Jul 17, 2016, at 9:05 AM, 'Juha Niskanen
Hi David,
"Please, let’s not conflate /dev/urandom with /dev/random."
Your assumptions about /dev/urandom properties and usage do not match real
world. There are lots and lots of security-related SW packages that assume
and absolutely *NEED* /dev/urandom to be a CSPRGN. This includes most, if
not all, TLS implementations. Take a look of mbedTLS
function mbedtls_platform_entropy_poll() for instance (a colleague recently
https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c#L150
<https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c>
https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96
that first tries to read from /dev/urandom, and if that fails, falls back to
getting somewhat predictable values from gettimeofdate() and getpid()!
Now that Greg has accepted your patch, a developer porting these libs (and
many others) to NuttX needs to be extra careful to NOT use the default
/dev/urandom
"isn’t DES still OK?"
This is 2016. Plain DES should have died long ago. Please lets not add it
into any new operating systems. NuttX is currently the best OS for IOT
devices, but crypto and security need more work (I hope to contribute
something if/when have the time).
Best Regards,
Juha Niskanen
--------------------------------------------------------------------------------
*Sent:* Sunday, July 17, 2016 3:19:51 AM
*Subject:* Re: [nuttx] /dev/urandom
Hello Sebastien,
(please see comments below)
Best regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello
Please forgive my rude choice of words, I probably have a lesser english
knowledge than you may think :)
No worries. ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, your response clarified a lot of things, I dont think that my second
email is useful now.
So if I understand correctly, you main idea is : linux urandom is good
quality, nuttx is not linux, we dont need quality for nuttx urandom… ?
It all depends on the application, but I don’t want to allow “perfect” to
become the enemy of “good enough” for the particular application in hand.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
OK... lets forget Linux.
NuttX is not only for low-end microprocessors. On the contrary, it is more
a RTOS for mid/high-end mcus. That's why I dont think that the argument
about constrained memory holds.
I agree. But then we’ll have to revisit the [my?] assumption that the same
algorithm compile/execute on all MCUs.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, there comes my remark about IoT security: Accepting that urandom is
NOT a CSPRNG clearly makes us go in the bad IoT security route, which I
dont like at all.
If we continue this route, if HW AES is not available on all chips, would
you recommend DES? (or, xor?)
My view is it’s all relative to the application and its attraction to
hackers. Plenty of papers have been written on the advantages of AES over
DES and 3DES, but if my application is measuring temperature in my water
heater and sending the sensor data to a website that does nothing more than
plot the data, isn’t DES still OK?
As for xor, no, I wouldn’t use it by itself. It works well when combined 1
or 2 other operations… Perhaps xor | rot13 | rot13 ?
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
However, I could admit that the range of supported targets is so wide that
a correct PRNG is not doable everywhere.
Yes, that’s a difficult constraint. I tried to strike a balance… How would
you balance the constraints?
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-we had multiple implementations (say: 2) for fast, non blocking random
sources available at /dev/urandom
I’m OK with 3, but not 15+ ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config
I could not agree more! If we do this with xorshift128, “NOT CRYPTO SECURE”
warnings should go everywhere.
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?
Does anyone really want Fortuna? Why would this be a better design choice
than an MCU with dedicated HW?
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32
bytes, a correct CSPRNG would not be the bigger NuttX subsystem.
Sure, this is acceptable.
Then we have the problem of how to “properly” seed and condition the PRNGs…
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
What about this?
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On Jul 16, 2016, at 1:57 AM, Sebastien
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but given
that your English appears to be slightly better than my French, I’ll cut
you some slack ;)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a
CSPRNG. We do already have /dev/random (well, I guess it is dependent
on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random. Traditionally,
/dev/urandom has been as source of uniformly distributed pseudorandom
numbers, fast, and non-blocking — nothing more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for
/dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I
believe David is suggesting)
* some externally provided implementation (for those who are picky, and
particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all
the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And it
should use a HW RNG.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
But let me remind you something. Linux has entropy problems: There are no
hardware RNG in normal desktop computers, but there is a need for enough
"entropy" (unpredictable random bits) for security reasons (generation of
RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from making
references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build process)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes,
mouse mouvements, disk IO - often, each event generates one good bit, or
less), but this random data is very scarce. Because of this, directly
reading /dev/ramdom will deplete the entropy too fast, so the
/dev/urandom CSPRNG was added to allow generation of enough pseudorandom
bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: https://eprint.iacr.org/2006/086.pdf
Thanks for the link, but again, this is very Linux-specific.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel,
programs needing significant amounts of random data from /dev/urandom
<https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with
programs reading little data from /dev/random
<https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes
/dev/random whenever it is being read.^[6]
<https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and
/dev/urandom don’t need to be related. It’s just that typically the
implementation of /dev/random builds on top of /dev/urandom and injects
entropy...
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Entropy manipulation is not trivial, you could introduce biases or
discard entropy without paying attention.
Quite right; and I would argue against trying to implement a /dev/random
with PRNG and entropy injection. If a project needs this, choose an
appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-there are no low-rate system entropy sources such as the ones that makes
random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or
it’s too slow, but a source of fast “decent” random numbers is desired.
That’s where /dev/urandom fits.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-there is often a hardware RNG of sufficient quality that will provide
random bits at a high enough rate for key generation or stuff like that,
when it's required at all (who really needs RSA key generation on a nuttx
embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is
rare), then a proper CSPRNG such as Yarrow or another well designed
generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if one
needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On 15/07/2016 19:58, 'Juha Niskanen
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed,
which I doubt... the other option is to avoid /dev/urandom entirely, and
use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be
“wrong”, but it breaks the tradition that /dev/urandom doesn’t block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly
complicated entropy pool management...
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
I advise against yet another low quality RNG in NuttX.
I’m happy to entertain an argument for a higher quality PRNG for
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
libc random is completely different. It has to be available even without
hardware RNG and no one with a sane mind would think it is
cryptographically secure. It could be implemented by xorshift128 as a
replacement of the current generator if we wanted a "slightly better",
but still fast, generator.
And on this we agree.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Sebastien
------------------------------------

------------------------------------


------------------------------------

Yahoo Groups Links

<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/nuttx/

<*> Your email settings:
Individual Email | Traditional

<*> To change settings online go to:
http://groups.yahoo.com/group/nuttx/join
(Yahoo! ID required)

<*> To change settings via email:
nuttx-***@yahoogroups.com
nuttx-***@yahoogroups.com

<*> To unsubscribe from this group, send an email to:
nuttx-***@yahoogroups.com

<*> Your use of Yahoo Groups is subject to:
https://info.yahoo.com/legal/us/yahoo/utos/terms/
Sebastien Lorquet sebastien@lorquet.fr [nuttx]
2016-07-18 08:51:54 UTC
Permalink
Addendum: There is also "ChaCha20":

https://en.wikipedia.org/wiki/Salsa20#ChaCha_variant

Sébastien Lorquet
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
Again, comments included below.
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
Please see inline comments below
Cheers,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello,
I added replies below.
Post by David Alessio ***@yahoo.com [nuttx]
Juha, Sebastien, Greg,
Sebastien cracked my stubborn argument; Juha may have just shattered it.
Thank you both.
— the argument re /dev/urandom vs /dev/random may be valid in a historical
perspective, but we need to take cognizance of reality. The reality is that
the quality of /dev/urandom has evolved, in both Linux and *BSD spaces, to a
point where today it’s commonly and correctly used by crypto libs. The fact
is, both are assumed good sources of CSRNGs.
— NuttX is the best RTOS for IoT [I could not agree more; I can write a
paper on this].
— People will port crypto libs to Nuttx without grokking that our
/dev/urandom departs from their assumptions/experience of its quality on
Linux/*BSD. And we will have thus enabled them to create insecure IoT devices.
— That risk, and the damage it will do to the NuttX brand, far outweigh any
benefit of a simple/fast /dev/urandom.
I’m now convinced that the patch, as I submitted it, is too dangerous. Can
we fix or rename it before it escapes into the wild?
Thanks, I really appreciate that we come back to interesting discussion.
Post by David Alessio ***@yahoo.com [nuttx]
Lets reset and start with a few design constraints. If we can converge on
the design constraints, then the implementation should become self-evident.
We need to view this in the context of IoT and security (my initial mistake,
I hacked up a quick driver for a quick problem…)
1) How should /dev/random be spec’d?
This has to be a CSRNG, should be based on a HW True RNG (TRNG).
Most drivers for /dev/random in nuttx outputs the raw data from the TRNG, but
this is not a problem, because all RNGs in SoCs are designed for this usage
(they often include a LFSR). This should not be done unless the reference
manual says so, I know some chips where the RNG output must be debiased,
verified, and used as input to a CSPRNG.
Post by David Alessio ***@yahoo.com [nuttx]
It can block (HW TRNGs can be slow, usually interrupt-driven), but it must be
deterministic (this is an RTOS after all).
What do you mean by deterministic? see below.
Sorry, I mean temporally deterministic. The single most important quality of an
RTOS is that its response time can be calculated (it’s deterministic). The
calculation may or may not be easy, but it’s possible and the response time is
bounded (never greater than X).
Okay, and, sure. I think that most PRNGs will have a bounded execution time,
since they dont depend on external entropy collection. In this case they are
"temporally deterministic" because they are, well, deterministic :)
Post by David Alessio ***@yahoo.com [nuttx]
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by David Alessio ***@yahoo.com [nuttx]
If we accept that it must be deterministic, that rules out most/all entropy
pool schemes.
And if the TRNG is “fast enough” (however we decide to define that), why
would we need /dev/urandom?
2) How should /dev/urandom be spec’d? What minimum tests of randomness must
it pass?
It should be based on a PRNG
must be cryptographically secure assuming properly seeded
must not block.
The last two are a kind of conflict or compromise. If you want good crypto
properties, you have to seed regularly, but.. the reseed itself is not
guaranteed to be posssible at a given date. This means that crypto quality
will vary, this is acceptable. We only need to ensure a predetermined minimum
quality. Note: I would not be bothered by a urandom that finally blocks after
it was not seeded for a very long time (this time depends on the PRNG), or
warns you that random quality is too low.
Post by David Alessio ***@yahoo.com [nuttx]
must generate uniformly distributed RNGs.
This is one of the randomness tests.
Post by David Alessio ***@yahoo.com [nuttx]
writing to /dev/urandom writes to the seed, important for testing.
given the same seed, it must reproduce the same data
The last requirement is a consequence of being pseudo random. This is the real
meaning of "deterministic" for RNGs. The reverse is non-deterministic, this is
the nature of True RNGs.
Post by David Alessio ***@yahoo.com [nuttx]
3) PRNGs need to be seeded, not all seeds are equal. Depending on the seed,
the PRNG may need to be cycled a few times before it stabilizes. Tests have
shown “few times” can range from 10 to ~10000.
How do we best manage this?
Um... By choosing a PRNG that stabilizes in ~10 rounds instead of ~10000? :p
What would you suggest?
maybe xorshift1024* ?
ref: http://vigna.di.unimi.it/ftp/papers/xorshift.pdf
Keccak? It’s computationally expensive.
http://sponge.noekeon.org/SpongePRNG.pdf
yes, kekkac feels like a rather complex hash algorithm.
https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
Anything based on bignums (EC, Diffie Hellman) will be slow.
NIST approved algorithms except Dual_EC_DRBG could be a good idea, they have
been studied extensively.
http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf
( https://en.wikipedia.org/wiki/Dual_EC_DRBG )
I think that Hash_DRBG using SHA-256 is worth testing. It would be a good
opportunity to bring this good hash into NuttX.
Also this NeuG project tries to make an embedded TRNG in an STM32F103, maybe
this can be an inspiration? It is based on SHA-256 :)
http://www.gniibe.org/memo/development/gnuk/rng/neug.html
( You said that you had a crypto subsystem in mind for nuttx, I also have, we
can talk about that later).
Post by David Alessio ***@yahoo.com [nuttx]
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
This is the difficulty of a proper urandom on an embedded platform.
Post by David Alessio ***@yahoo.com [nuttx]
Do we need an internal source of entropy (LSBs of an ADC, etc.) for the seed?
Yes. And, you also ideally need a writable filesystem to save the seed when
the system is shut down, and restore it at next boot, because it can take a
long time with low rate sources until the full entropy pool is replenished. At
least that's the case in Linux...
Post by David Alessio ***@yahoo.com [nuttx]
And if we don’t have one, do we disable /dev/urandom?
Security wise, I think that it would be safe and sane. Reusing the same seed
at successive boot events means that software tools will generate the exact
same keys and nonces, which is dangerous. An alternative is to block (once)
until the pool has gathered enough fresh entropy from the non-deterministic
sources.
Agreed.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
I am working in a crypto environment. We have a rule: Dont invent new crypto
mechanisms if there exists an algorithm for our purpose. It is dangerous to
design crypto algorithms from scratch, because a small mistake can become a
full disaster unknowingly. So I would suggest a litterature review of "good"
CSPRNGs. Most of them will be based on a solid hash algorithm, because this
algs cannot be reversed, provided they do not have collisions (this would make
the PRNG to wrap around) . I would really suggest evaluation of Bruce Schneier
work in this domain, he designed some "solid" CSPRNGs. They may not be slow
nor memory expensive, they may be worth implementing and evaluating.
Greg: I dont think that linear congruence algorithms are CSPRNGs but this
would has to be verified.
It’s been shown that Linear Congruent Generators (LCG) are not acceptable for
CSPRNGs. But an LCG with a nonlinear operation (+ or *, for example) may be
acceptable.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
An important feature, is that any "brand new" CSPRNG should be at least tested
using RNG test suites. Wikipedia entry about xorshift names a few.
We should choose a CSPRNG that has at least been vetted by a few experts.
I agree.
As said before, we can go with the NIST (Hash_DRBG) or with Bruce Schneier
(Yarrow, Fortuna). arc4_random is probably usable (AND lightweight) if enough
output is discarded from the beginning of the stream. Also, block ciphers in
counter mode, but the "fast" option will then require hardware crypto acceleration.
But algo choice is just a part of the design. We also need entropy collection or
these RNG are just bit pattern generators. This is easily solved for platforms
with a HW RNG, but something has to be done for the situations where the HW RNG
is disabled or unavailable.
Sebastien
----------
Post by David Alessio ***@yahoo.com [nuttx]
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Post by David Alessio ***@yahoo.com [nuttx]
4) Do we need to support /dev/urandom on 8 and 16 bit MCUs.
I now think NO. It places too many constraints on the 32-bit+ implementation.
If needed, maybe it should be registered as something other than /dev/urandom
NuttX is probably only for 32-bit targets I think. hah, atmel and z80... ... okay :p
Post by David Alessio ***@yahoo.com [nuttx]
Finally, I want to follow up on Juha last comment re DES. Maybe I should
have been more careful in framing my question so I’m not misunderstood as
standing in support of DES. I believe DES should have disappeared a long
time ago. But it hasn’t, why? Security isn’t black and white, it’s gray — a
system is “secure” until computers become fast enough to crack it, or a
researcher discovers a clever exploit… My question should have been posed
more along the lines of: under what circumstances (if any) might DES, today,
be “good enough?” I don’t want to open up a debate here, just clarify my
thought behind that short and misleading question.
If I understand correctly, Simple DES was broken by the EFF in 1998. It is not
considered as a secure algorithm anymore. So it is good enough for nothing.
However, triple-des (DES-EDE, TDEA) (with two or three keys) offers an
acceptable security level (this is difficult to define :) ) for a lot of
things that still require 8-byte data blocks. All of this is no secret, it is
wikipedia wisdom :)
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Best regards,
-david
On Jul 17, 2016, at 9:05 AM, 'Juha Niskanen
Hi David,
"Please, let’s not conflate /dev/urandom with /dev/random."
Your assumptions about /dev/urandom properties and usage do not match real
world. There are lots and lots of security-related SW packages that assume
and absolutely *NEED* /dev/urandom to be a CSPRGN. This includes most, if
not all, TLS implementations. Take a look of mbedTLS
function mbedtls_platform_entropy_poll() for instance (a colleague recently
https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c#L150
<https://github.com/ARMmbed/mbedtls/blob/4e6248fa1515f3af01e7d0754b6690d90c2ea5d8/library/entropy_poll.c>
https://github.com/busterb/libressl/blob/089aaf7ad3c4c4c32d216b05e69a83d0f2f75140/crypto/compat/arc4random.c#L96
that first tries to read from /dev/urandom, and if that fails, falls back to
getting somewhat predictable values from gettimeofdate() and getpid()!
Now that Greg has accepted your patch, a developer porting these libs (and
many others) to NuttX needs to be extra careful to NOT use the default
/dev/urandom
"isn’t DES still OK?"
This is 2016. Plain DES should have died long ago. Please lets not add it
into any new operating systems. NuttX is currently the best OS for IOT
devices, but crypto and security need more work (I hope to contribute
something if/when have the time).
Best Regards,
Juha Niskanen
--------------------------------------------------------------------------------
*Sent:* Sunday, July 17, 2016 3:19:51 AM
*Subject:* Re: [nuttx] /dev/urandom
Hello Sebastien,
(please see comments below)
Best regards,
-david
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Hello
Please forgive my rude choice of words, I probably have a lesser english
knowledge than you may think :)
No worries. ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, your response clarified a lot of things, I dont think that my second
email is useful now.
So if I understand correctly, you main idea is : linux urandom is good
quality, nuttx is not linux, we dont need quality for nuttx urandom… ?
It all depends on the application, but I don’t want to allow “perfect” to
become the enemy of “good enough” for the particular application in hand.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
OK... lets forget Linux.
NuttX is not only for low-end microprocessors. On the contrary, it is more
a RTOS for mid/high-end mcus. That's why I dont think that the argument
about constrained memory holds.
I agree. But then we’ll have to revisit the [my?] assumption that the same
algorithm compile/execute on all MCUs.
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
Also, there comes my remark about IoT security: Accepting that urandom is
NOT a CSPRNG clearly makes us go in the bad IoT security route, which I
dont like at all.
If we continue this route, if HW AES is not available on all chips, would
you recommend DES? (or, xor?)
My view is it’s all relative to the application and its attraction to
hackers. Plenty of papers have been written on the advantages of AES over
DES and 3DES, but if my application is measuring temperature in my water
heater and sending the sensor data to a website that does nothing more than
plot the data, isn’t DES still OK?
As for xor, no, I wouldn’t use it by itself. It works well when combined 1
or 2 other operations… Perhaps xor | rot13 | rot13 ?
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
However, I could admit that the range of supported targets is so wide that
a correct PRNG is not doable everywhere.
Yes, that’s a difficult constraint. I tried to strike a balance… How would
you balance the constraints?
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-we had multiple implementations (say: 2) for fast, non blocking random
sources available at /dev/urandom
I’m OK with 3, but not 15+ ;)
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-the xor128 implementation was clearly marked as NOT CRYPTO SECURE in Config
I could not agree more! If we do this with xorshift128, “NOT CRYPTO SECURE”
warnings should go everywhere.
1) xorshift128 (uses only uint32_t and would work well on mega128, z80, etc.)
2) xorshift128+ (uses uint64_t, passes BigCrush)
3) ?
Does anyone really want Fortuna? Why would this be a better design choice
than an MCU with dedicated HW?
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
-we also make available a CSPRNG for bigger CPUs. A SHA-256 buffer is 32
bytes, a correct CSPRNG would not be the bigger NuttX subsystem.
Sure, this is acceptable.
Then we have the problem of how to “properly” seed and condition the PRNGs…
Post by Sebastien Lorquet ***@lorquet.fr [nuttx]
What about this?
Sebastien
Post by David Alessio ***@yahoo.com [nuttx]
Sebastien,
(see comments below)
Regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On Jul 16, 2016, at 1:57 AM, Sebastien
Hello,
I let everyone remember that security in the IoT is globally crap,
This is true and I feel your frustration, but it’s an non sequitur.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
so please lets not add more crap in that field…
Monsieur Sébastien, such statements are easy to misunderstand, but given
that your English appears to be slightly better than my French, I’ll cut
you some slack ;)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a
CSPRNG. We do already have /dev/random (well, I guess it is dependent
on there being a hardware rng underlying it).
Please, let’s not conflate /dev/urandom with /dev/random. Traditionally,
/dev/urandom has been as source of uniformly distributed pseudorandom
numbers, fast, and non-blocking — nothing more, nothing less.
dd if=/dev/urandom of=/dev/sda bs=1000 count=1000000
dd if=/dev/urandom of=/mnt/usb/garbage.bin bs=1024 count=1024
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Post by ***@ziggurat29.com [nuttx]
* hardware source (requires chip support) (i.e. like as it is now for
/dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I
believe David is suggesting)
* some externally provided implementation (for those who are picky, and
particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually
does)
Then that might be ideal. Actually, then you could probably merge all
the /dev/(u) random into one thing.
Same here, CSPRNG or nothing.
I would agree with you here, but *only* with respect to /dev/random
/dev/random, if it exists, *must* be cryptographically secure. And it
should use a HW RNG.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
But let me remind you something. Linux has entropy problems: There are no
hardware RNG in normal desktop computers, but there is a need for enough
"entropy" (unpredictable random bits) for security reasons (generation of
RSA keys, openssl, ssh, etc). - we dont have most of this in NuttX.
Linux has many problems. And that’s why I try to refrain from making
references to Linux — it’s just examining a pathological case...
(BTW: on my TODO list is to bring good crypto libs into the Nuttx build
process)
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
So, linux gathers entropy from multiple low rate sources (keystrokes,
mouse mouvements, disk IO - often, each event generates one good bit, or
less), but this random data is very scarce. Because of this, directly
reading /dev/ramdom will deplete the entropy too fast, so the
/dev/urandom CSPRNG was added to allow generation of enough pseudorandom
bits even if the real entropy has a far lower rate.
Here is a doc describing the linux RNGs: https://eprint.iacr.org/2006/086.pdf
Thanks for the link, but again, this is very Linux-specific.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Also, according to wikipedia: "On systems using the Linux kernel,
programs needing significant amounts of random data from /dev/urandom
<https://en.wikipedia.org/wiki//dev/urandom> cannot co-exist with
programs reading little data from /dev/random
<https://en.wikipedia.org/wiki//dev/random>, as /dev/urandom depletes
/dev/random whenever it is being read.^[6]
<https://en.wikipedia.org/wiki/Entropy_%28computing%29#cite_note-6>”
This, again, is a Linux-specific implementation. /dev/random and
/dev/urandom don’t need to be related. It’s just that typically the
implementation of /dev/random builds on top of /dev/urandom and injects
entropy...
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Entropy manipulation is not trivial, you could introduce biases or
discard entropy without paying attention.
Quite right; and I would argue against trying to implement a /dev/random
with PRNG and entropy injection. If a project needs this, choose an
appropriate MCU — one that has a HW RNG (PIC32MZ, STM32F4xx, etc.).
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
However, on embedded platforms targeted by nuttx, the conditions are
-there are no low-rate system entropy sources such as the ones that makes
random necessary
There are several use cases were an MCU either doesn’t have HW RNG, or
it’s too slow, but a source of fast “decent” random numbers is desired.
That’s where /dev/urandom fits.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-there is often a hardware RNG of sufficient quality that will provide
random bits at a high enough rate for key generation or stuff like that,
when it's required at all (who really needs RSA key generation on a nuttx
embedded platform?)
HW RNG is perfect for key generation, if needed, but it can be slow.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
-if even more pseudorandom bits are required (with a hw rng, this is
rare), then a proper CSPRNG such as Yarrow or another well designed
generator should be used.
No, these are too heavy for a small MCU. Again, I would argue that if one
needs that level of quality in a PRNG, choose an MCU with a HW RNG.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
On 15/07/2016 19:58, 'Juha Niskanen
Post by ***@ziggurat29.com [nuttx]
"/dev/urandom is simply a symlink to /dev/random"
This is probably not bad, if the original program cannot be changed,
which I doubt... the other option is to avoid /dev/urandom entirely, and
use /dev/random instead.
I haven’t explored FreeBSD. But if /dev/random blocks, it may not be
“wrong”, but it breaks the tradition that /dev/urandom doesn’t block.
In NetBSD /dev/urandom doesn’t block; and /dev/random has some fairly
complicated entropy pool management...
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
I advise against yet another low quality RNG in NuttX.
I’m happy to entertain an argument for a higher quality PRNG for
— compile on all supported architectures
— be reasonably fast on those architectures
— never block
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
libc random is completely different. It has to be available even without
hardware RNG and no one with a sane mind would think it is
cryptographically secure. It could be implemented by xorshift128 as a
replacement of the current generator if we wanted a "slightly better",
but still fast, generator.
And on this we agree.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Sebastien
------------------------------------

------------------------------------


------------------------------------

Yahoo Groups Links

<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/nuttx/

<*> Your email settings:
Individual Email | Traditional

<*> To change settings online go to:
http://groups.yahoo.com/group/nuttx/join
(Yahoo! ID required)

<*> To change settings via email:
nuttx-***@yahoogroups.com
nuttx-***@yahoogroups.com

<*> To unsubscribe from this group, send an email to:
nuttx-***@yahoogroups.com

<*> Your use of Yahoo Groups is subject to:
https://info.yahoo.com/legal/us/yahoo/utos/terms/

dev@ziggurat29.com [nuttx]
2016-07-16 22:13:30 UTC
Permalink
I cannot more strongly disagree on the position that /dev/urandom is intended to be simply a uniformly distributed source of random numbers. Any of the three links I have previously sent attest to that /dev/urandom is cryptographic in intent. (or, if you simply google "/dev/urandom" as I did you'll find all those and many others). I'm not sure what more I can do to provide corroborating evidence.

Indeed, the implementation between the two is sometimes either identical (BSD derivative, via symlink) or the same except for as to choosing to block (/dev/random) on some criterion based on calculated entropy metric, or not (/dev/urandom), and is the case in Linux (and apparently only in that case).

What dispute /does/ seem to remain is as to whether the whole 'blocking on apparently depleted entropy' in /dev/random is a good thing. The man page (man 4 random) seems to suggest so, and makes vaguely scary warnings against using /dev/urandom (re-reading it now, the verbiage seems to have been toned-down from when I can remember it last), however, again, current practitioners in the field believe this is to be nonsense. And really, after a moment's thought, it should become obvious: that you need only as many bits of entropy as the equivalent symmetric key strength of the underlying algorithm.


Most folks consider the distinction to be factitious, and simply a design booboo when it was introduced in the mid 90s.


Lastly, I will not shed many tears if ultimately you guys put a linear generator in for /dev/urandom. I do think it is technically wrong, but I can appreciate the desire to have a lightweight generator for those who do not care about cryptographic purpose. I do strongly suggest making that an option in Kconfig, though, and also not the default, and also having a tasty caveat in the help text clearly stating that it is not suitable for any cryptographic purpose at all ever.


Cheers!


-dave
David Alessio david.alessio@yahoo.com [nuttx]
2016-07-16 20:20:56 UTC
Permalink
Hi Juha,

Only /dev/random promises to be truly random. There are a couple of ways to do this:
— use a HW RNG. We see an increasing number of MCUs with HW RNGs.
— start with the best (read: computationally expensive) pseudorandom number generator algorithm, then introduce entropy. This is what’s done in the BSDs and Linux OSs. But then the entropy budget needs to be managed and that may be too expensive for MCUs.

I believe that if an application demands cryptographically secure random numbers, then it start by choosing an MCU with a HW RND. And /dev/random (no u) should be built on top of the HW RNG. There are several, Nuttx has very good support for the STM32F4 family.

Best regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Hi Dave,
"We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it)."
HW rng, when available, could be just used to supply entropy to entropy pool instead of used directly. Haltian boards for NuttX-based products typically have many sensors so we just feed low order bits from sensors and other noise to entropy pool (as our MCU most often lacks true rng).
"some generally suitable CSPRNG (as I believe Juha is suggesting)"
Well the Thingsee OS (=fork of NuttX) /dev/random definitely should go under CONFIG_EXPERIMENTAL, if it is ever accepted by mainline at all. I designed it and I'm far from expert with crypto, so it may not be generally suitable :)
But I urge Greg and others see for themselves if it is good for anything. (github link in previous email leads to our somewhat old public SDK)
"/dev/urandom is simply a symlink to /dev/random"
Since NuttX is a new OS, there is no need to have two names for a same thing for compatibility. But I agree that preferably there should be just one excellent source of arbitrary amounts of CS-randomness in the system instead of several HW-specific or insecure generators.
File based interface to rng is problematic because of extra hassle of opening, closing and consuming fd for it. Also an attacker may be able to exhaust CONFIG_NFILE_DESCRIPTORS fds somehow.
Thingsee uses speckrandom_buf() function as only randomness source throughout the system (both OS and apps) for both crypto and simple things like network protocol sequence numbers or deciding (flipping a coin) whether to query primary or secondary DNS server first etc. There are no calls to rand() as the better alternative is only negligibly slower.
Best Regards,
Juha Niskanen
Sent: Friday, July 15, 2016 4:44:34 PM
Subject: Re: [nuttx] /dev/urandom
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.
-dave
'David S. Alessio' david.s.alessio@gmail.com [nuttx]
2016-07-16 20:03:39 UTC
Permalink
Hello Dave,

Again, let’s not confuse /dev/random with /dev/random. /dev/urandom is a source of random numbers with uniform distribution, doesn’t block, and is fast.
/dev/urandom is often used with the ‘dd’ command to create large files with random data or wipe the contents of a disk by filling it with random data.

Regards,
-david
Post by ***@ziggurat29.com [nuttx]
I second that the general assumption for /dev/urandom will be that is a CSPRNG. We do already have /dev/random (well, I guess it is dependent on there being a hardware rng underlying it).
* hardware source (requires chip support) (i.e. like as it is now for /dev/random)
* some generally suitable CSPRNG (as I believe Juha is suggesting)
* some non-CS rng (for convenience of those who don't care? as I believe David is suggesting)
* some externally provided implementation (for those who are picky, and particularly want, say Yarrow, as I am suggesting)
* /dev/urandom is simply a symlink to /dev/random (as FreeBSD actually does)
Then that might be ideal. Actually, then you could probably merge all the /dev/(u) random into one thing.
-dave
dev@ziggurat29.com [nuttx]
2016-07-16 20:09:26 UTC
Permalink
Interesting; well there's a lot of very flawed implementations out there -- we've always used /dev/urandom.

I think I put a link to one discussion in a previous message, and here is another from the top of google query I just did.


Myths about /dev/urandom http://www.2uo.de/myths-about-urandom/

http://www.2uo.de/myths-about-urandom/

Myths about /dev/urandom http://www.2uo.de/myths-about-urandom/ Myths about /dev/urandom by Thomas HÃŒhn There are a few things about /dev/urandom and /dev/random that are repeated again and again. Still they are ...



View on www.2uo.de http://www.2uo.de/myths-about-urandom/
Preview by Yahoo




But of course, the Internet is filled with contradictory statements.
dev@ziggurat29.com [nuttx]
2016-07-16 20:13:50 UTC
Permalink
Interesting; well there's a lot of very flawed implementations out there -- we've always used /dev/urandom.


I think I put a link to one discussion in a previous message, and here is another from the top of google query I just did.


http://www.2uo.de/myths-about-urandom/


And lest we forget, the great and holy wikipedia


https://en.wikipedia.org/wiki//dev/random

But of course, the Internet is filled with contradictory statements.
'David S. Alessio' david.s.alessio@gmail.com [nuttx]
2016-07-16 19:56:11 UTC
Permalink
Juha,

(please see inline comments below)

Best regards,
-david
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
Just remember to never ever use this for any crypto work e.g. when porting TLS libraries to NuttX. I think /dev/urandom should be by default a cryptographically-secure generator to avoid mistaken security assumptions.
Let’s not confuse /dev/urandom with /dev/random. It’s the latter that promises to be cryptographically secure. The former only promises to be fast, reasonably uniform, and never block.
Post by 'Juha Niskanen (Haltian)' ***@haltian.com [nuttx]
https://github.com/thingsee/thingsee-sdk/blob/dev/nuttx/drivers/dev_random.c <https://github.com/thingsee/thingsee-sdk/blob/dev/nuttx/drivers/dev_random.c>
This is my foray into amateur crypto, design has not been checked with real crypto experts, so beware. We have used this in few real NuttX-based products (that had minimal security requirements, though). There is the legacy /dev/random but main API is a single function speckrandom_buf() just like OpenBSD's arc4random_buf().
Github has older version than what we have in our internal repos, if anyone is interested I can check if I can publish our current version. This could be adapted to 8/16 bit MCU by switching to speck32/64, I think. This also shows how up_waste() is a useful NuttX API.
Best Regards,
Juha Niskanen
Sent: Friday, July 15, 2016 11:35:51 AM
Subject: [nuttx] /dev/urandom [1 Attachment]
Hi Greg,
Attached is a patch that optionally adds /dev/urandom to all architectures. The pseudo-random algorithm I choose strikes an arguably-good balance between being “random” and small/fast enough for 8/16 bit MCUs. It’s the well-documented xorshift128 algorithm. It has an internal state of 128 bits that can be [re-]seeded with a write.
Best regards,
-david
spudarnia@yahoo.com [nuttx]
2016-07-16 18:30:49 UTC
Permalink
So what is the disposition of this change. I think the summary comments are:


1. There should be one software implementation of a random number generator in libc/stdlib.
2. We use the name /dev/random vs. /dev/urandom
3. There are security issues with software random number generators.


I think the first two (only) gate incorporation of the change.


Greg
dev@ziggurat29.com [nuttx]
2016-07-16 19:13:28 UTC
Permalink
Personally, I think having the option to have a software-based implementation for /dev/(u)random is a good thing, because as it is, hardware support is required, so other chips are left out in the cold. However, I think a non-cryptographic rng is inappropriate for /dev/(u)random, because that is not how that device is supposed to work.

OTOH, having a fast, non-cryptographic alternative implementation for rand() seems useful (and I think there are already a couple alternatives in the Kconfig), and the shift128 implementation might have a good home there.


If you want a simple software-only implementation that preserves the assumed cryptographic properties of for /dev/(u)random, I would suggest perhaps a stream cipher, where teh 'entropy' is used to derive the key. (e.g. a block cipher in counter mode; I think there's an AES implementation already in the source somewhere...).


I'm less religious about whether there is a /dev/random vs /dev/urandom. The folks I know conventionally /dev/urandom, because the blocking nature of /dev/random was considered by many to be a basic design error. (And I think only Linux actually tries to do that, with the other platforms simply symlinking the two and never blocking in either case). I can't remember how entropy is injected; maybe and ioctl but I'd have to look.


Lastly, I do suggest making it possible to have a board def be able to replace the implementation. As I've said, I'd probably use Yarrow myself (well, I'd rather Fortuna, but then I'd kiss all my RAM goodbye).


-dave
david_s5@usa.net [nuttx]
2016-07-16 19:21:14 UTC
Permalink
I have minor request - We used the rand() function in the UAVCAN bootloaders and there is only 60-70 bytes left in FLASH on some if the platforms. So please gate things with CONFIG_yada if there will be major changes to the underlying rand() and friends.

Thank you


David
dev@ziggurat29.com [nuttx]
2016-07-16 19:44:37 UTC
Permalink
If y'all want, I will volunteer to make the changes I suggested, and also of course taking David's concerns into account. -dave
Sebastien Lorquet sebastien@lorquet.fr [nuttx]
2016-07-16 21:27:31 UTC
Permalink
Post by ***@ziggurat29.com [nuttx]
because as it is, hardware support is required, so other chips are
left out in the cold.
Without a real entropy source, urandom is predictable. A real entropy
source is required to seed and reseed urandom.

Implementing urandom properly without a hardware RNG, as I said,
requires low-rate entropy gathering from other parts of the system,
which is hard in an embedded OS since you dont have a mouse, a keyboard,
or disk IO. Or you're going to get Sony PS4 randoms. The ThingSee
platform has sensors, which could be used, ADC noise can also be used,
but you need "something", entropy cannot come from nowhere.
Unfortunately, a digital system is too predictable!
Post by ***@ziggurat29.com [nuttx]
reasonably-good PRNG suitable for use in /dev/urandom.
Sorry but XOR is reasonably-bad and no close to the quality required for
urandom :(
No one will ever think of using xor for anything that requires crypto
security.
The only generators based on xorshift to pass all classic random tests
requires post-processing using multiplications/additions.
Post by ***@ziggurat29.com [nuttx]
/dev/urandom is traditionally used as a source of “decently random”
numbers and is usually used with the ‘dd’ command.
That is YOUR (valid) usecase , but I dont think this is a generality.
Post by ***@ziggurat29.com [nuttx]
/dev/urandom is often used with the ‘dd’ command to create large files
with random data or wipe the contents of a disk by filling it with
random data.
Again this is certainly not the case, you're trying to make an example
into a generality. urandom is ALSO a CSPRNG whose randomness is enough
for cryptographic key generation. I really wonder where you are getting
this information from.
Post by ***@ziggurat29.com [nuttx]
Let’s not confuse /dev/urandom with /dev/random. It’s the latter that
promises to be cryptographically secure.
I ask a source for that claim. My opinion is strongly different based
on this source, which is probably verifiable elsewhere:
http://security.stackexchange.com/questions/3936/is-a-rand-from-dev-urandom-secure-for-a-login-key
Post by ***@ziggurat29.com [nuttx]
Only /dev/random promises to be truly random.
No. Or again, please prove this.


I feel that you are trying to drown everyone in repeated, unverified
assertions that are only partially valid. xor has never been and will
never be a valid algorithm for a cryoptographically secure RNG as
requested for an upstreamable implementation of /dev/urandom. xor is
linear, it's a modulo2 addition, which means that it's Caesar / Vigenere
(1586) crypto. NuttX deserves better than 16th century technology. At
least, please suggest something using sha-1 or sha-256.

Using urandom to fill a disk with DD is a good use case, but you cannot
suggest that this is the only one, and that no one in the future will
attempt to generate cryptographic keys from urandom. As OS designers, we
have to be responsible and plan for the future, instead of throwing
random bits in a bucket for whatever project we're currently working on.

However I have nothing against xor128 as a replacement for the libc
random. Then, you can have a local character driver for you only that
generate fast random-looking numbers from any libc-provided rand().

Sebastien
spudarnia@yahoo.com [nuttx]
2016-07-16 21:30:50 UTC
Permalink
Could you reseed in the IDLE loop. Nothing else better to do there and time when the IDLE loop runs may not be random, but it is not entirely predictable either.
spudarnia@yahoo.com [nuttx]
2016-07-16 21:36:18 UTC
Permalink
In general, I am going to stay out this discussion. I am concerned with architectural, implementation details, but I am not impassioned as other people in the discussion.


My only questions is when and how do we get closure so that I can properly dispose of David's change.


Greg
David Alessio david.alessio@yahoo.com [nuttx]
2016-07-16 20:39:49 UTC
Permalink
Hi Greg,

I’d be happy to submit a patch for your consideration that addresses (1) below.

As for (2), I believe /dev/urandom should be available in Nuttx as a source of uniformly-distributed pseudorandom numbers, as it was alway intended. Than means it must be fast, non-blocking, and simply pretty-good at being random; and it should never be mistaken as a source of cryptographically secure random numbers (that job is claimed by /dev/random). I’d be happy to entertain an argument for an alternate PRNG more suitable for use across MCUs from Z80 on up, but /dev/urandom makes no commitment to crypto...

/dev/random should be available on those platforms that HAVE_RNG as a source of HW-generated random numbers, the quality of which is then subject to the silicon vender’s design.

And for (3), I would argue that if anyone wants cryptographically secure random numbers, they should start their design by choosing an appropriate MCU — one that has a HW RNG. Trying to implement the entropy injection into computationally-expensive algorithms from Linux or the BSD class OSs in Nuttx on an MCU is a very poor design choice.

Best regards,
-david
Post by ***@yahoo.com [nuttx]
1. There should be one software implementation of a random number generator in libc/stdlib.
2. We use the name /dev/random vs. /dev/urandom
3. There are security issues with software random number generators.
I think the first two (only) gate incorporation of the change.
Greg
Gregory Nutt spudarnia@yahoo.com [nuttx]
2016-07-17 12:47:37 UTC
Permalink
Hi, David and reviewers,

After letting the discussion go for awhile, I decided to commit the
/dev/urandom patch. Controversy still seems to involve:

1. The difference between /dev/random and /dev/urandom -- although I
think we are getting close to closure on that.

2. The required quality of the underlying RNG. This commit uses the
simple xorshift128 algorithm which some people objected to.

My thinking is that having the different /dev random number generators
has value. Certainly if someone wants a better algorithm that would a
good natural extension to this initial commit.

Greg
spudarnia@yahoo.com [nuttx]
2016-07-17 14:02:41 UTC
Permalink
I also added an option to use the computationally heavy congruential PRNG that is used with srand() for those of you who are unhappy with xorshift128. The code is now also set up so that you should be able to plug in any PRNG you want.


Greg
Loading...