short read from /dev/urandom

short read from /dev/urandom

[Ulrich Drepper]

[-- Attachment #1: Type: text/plain, Size: 1308 bytes --]

The /dev/urandom device is advertised as always returning the requested 
number of bytes.  Yet, it fails to do this under some situations. 
Compile this

int main (void)
{
   alarm (100);
   char buf[32];
   int fd = open ("/dev/urandom", 0);
   while (1)
     if (read (fd, buf, sizeof buf) != sizeof (buf))
       abort ();
}

with

   gcc -o r r.c -g -O2 -pg


Note the -pg at the end to enable profiling.  Running this code fails 
for me after less than a second.

The relevant code in the kernel is this 
(drivers/char/random.c:extract_entropy)

         while (nbytes) {
                 /*
                  * Check if we need to break out or reschedule....
                  */
                 if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) {
                         if (signal_pending(current)) {
                                 if (ret == 0)
                                         ret = -ERESTARTSYS;
                                 break;
                         }


Here the loop is left prematurely if a signal is pending.

One solution is to redefine the /dev/urandom interface.  The problem is 
that this will cause program to fail.  I know since I found this while 
debugging such a program.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: short read from /dev/urandom

[David Wagner]

Ulrich Drepper  wrote:
>The /dev/urandom device is advertised as always returning the requested 
>number of bytes.

True.  Arguably, the solution is to fix the documentation.
Why not make /dev/urandom like every other kind of fd in the world,
and make no promises about whether a read() will always return as
many bytes as requested?  Is there any reason /dev/urandom fds special?

Re: short read from /dev/urandom

[Ulrich Drepper]

On Fri, 14 Jan 2005 05:56:41 +0000 (UTC), David Wagner
<daw@taverner.cs.berkeley.edu> wrote:

> True.  Arguably, the solution is to fix the documentation.

The problem is that no-short-reads behavior has been documented for a
long time and so programs might, correctly so, use

    while (read(fd, buf, sizeof buf) == -1)
      continue;

Image a program doing this.  It provides the possibility for a local
attack.  If one can determine the content of the to-be-filled buffer
before the 'read', then an attacker could limit the randomness in the
buffer after the read by sending signals to the program.

Not breaking the ABI is more important than symmetry.

Re: short read from /dev/urandom

[David Wagner]

Ulrich Drepper  wrote:
>On Fri, 14 Jan 2005 05:56:41 +0000 (UTC), David Wagner
><daw@taverner.cs.berkeley.edu> wrote:
>> True.  Arguably, the solution is to fix the documentation.
>
>The problem is that no-short-reads behavior has been documented for a
>long time and so programs might [become insecure]
>
>Not breaking the ABI is more important than symmetry.

Ok, I see your point.  I'm persuaded.  Thanks.

Re: short read from /dev/urandom

[Theodore Ts'o]

On Thu, Jan 13, 2005 at 08:54:54PM -0800, Ulrich Drepper wrote:
> The /dev/urandom device is advertised as always returning the requested 
> number of bytes.  Yet, it fails to do this under some situations. 
> Compile this
> 
> Note the -pg at the end to enable profiling.  Running this code fails 
> for me after less than a second.
> 
> The relevant code in the kernel is this 
> (drivers/char/random.c:extract_entropy)
> 
>         while (nbytes) {
>                 /*
>                  * Check if we need to break out or reschedule....
>                  */
>                 if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) {
>                         if (signal_pending(current)) {
>                                 if (ret == 0)
>                                         ret = -ERESTARTSYS;
>                                 break;
>                         }
> 
> 
> Here the loop is left prematurely if a signal is pending.

The problem is that the code doesn't have the code to support
restartable system calls, so it only returns ERESTARTSYS if the nuber
bytes generated is zero.  What we should do is implement the full
restartable system calls, such that whether or not /dev/urandom
returns a short read is dependent on whether or not SA_RESTART is
passed to the sigaction() system call.  

Yeah, /dev/urandom was advertised as "always" returning the requested
number of bytes, but that was always an informal description, not a
formal one --- such as for example documented behavioiur of SA_RESTART
in sigaction().  So I believe the correct approach is to make
/dev/urandom honor the SA_RESTART flag, and then change the
documentation to match.  This is a bit of a compromise between "always
returning" and the current "never returning" behaviour.

What do you think?  Does gcc -pg calls sigaction with SA_RESTART, to
avoid changing the behaviour of the programs that it is profiling?  If
so, it would allow the program to work, while also being much more
consistent.  The flip side is that if there are programs that blindly
read from /dev/urandom for reading without checking its return count,
they could still lose, if their program had any signal handlers that
used System V semantics.  I'm not aware of any such programs, but they
certainly could exist.

						- Ted

Re: short read from /dev/urandom

[Ulrich Drepper]

[-- Attachment #1: Type: text/plain, Size: 903 bytes --]

Theodore Ts'o wrote:
> What do you think?  Does gcc -pg calls sigaction with SA_RESTART, to
> avoid changing the behaviour of the programs that it is profiling?

Profiling certainly uses SA_RESTART.  But this was just one possible 
problem case.

I'm concerned that there is isgnificant code out there relying on the 
no-short-read promise.  And perhaps more importantly, other 
implementations promise the same.

The code in question comes from a crypto library which is in wide use 
(http://www.cryptopp.com) and it is using urandom under this assumption. 
  I fear there is quite a bit more code like this out there.  Changing 
the ABI after the fact is no good and dangerous in this case.

I know this is making the device special, but I really think the 
no-short-reads property should be perserved for urandom.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: short read from /dev/urandom

[Theodore Ts'o]

On Fri, Jan 14, 2005 at 01:04:52PM -0800, Ulrich Drepper wrote:
> I'm concerned that there is isgnificant code out there relying on the 
> no-short-read promise.  And perhaps more importantly, other 
> implementations promise the same.
> 
> The code in question comes from a crypto library which is in wide use 
> (http://www.cryptopp.com) and it is using urandom under this assumption. 
>  I fear there is quite a bit more code like this out there.  Changing 
> the ABI after the fact is no good and dangerous in this case.
> 
> I know this is making the device special, but I really think the 
> no-short-reads property should be perserved for urandom.

Good point.  The fact that there are other implementations out there
which are doing this is a convincing argument.  

I am still a bit concerned still that a stupidly written program that
opens /dev/urandom (perhaps unwittingly) and tries to read a few
hundred megabytes will become uninterruptible until the read
completes, but I'm not sure it's worth it to but in some kludge that
says "break if there's a signal and count > 1 megabyte --- otherwise
we'll return soon enough".

						- Ted

Re: short read from /dev/urandom

[H. Peter Anvin]

Followup to:  <20050114232154.GB18479@thunk.org>
By author:    "Theodore Ts'o" <tytso@mit.edu>
In newsgroup: linux.dev.kernel
> 
> Good point.  The fact that there are other implementations out there
> which are doing this is a convincing argument.  
> 
> I am still a bit concerned still that a stupidly written program that
> opens /dev/urandom (perhaps unwittingly) and tries to read a few
> hundred megabytes will become uninterruptible until the read
> completes, but I'm not sure it's worth it to but in some kludge that
> says "break if there's a signal and count > 1 megabyte --- otherwise
> we'll return soon enough".
> 

I'm very concerned about this; this is fundamentally a change to
signal delivery semantics.

What we might want to go along with is a read smaller than PIPE_BUF
(the largest size guaranteed to be atomic when writing to a pipe,
which is another special case) should not return fractional.

	-hpa

Re: short read from /dev/urandom

[Matt Mackall]

On Sat, Jan 15, 2005 at 02:36:56AM +0000, H. Peter Anvin wrote:
> Followup to:  <20050114232154.GB18479@thunk.org>
> By author:    "Theodore Ts'o" <tytso@mit.edu>
> In newsgroup: linux.dev.kernel
> > 
> > Good point.  The fact that there are other implementations out there
> > which are doing this is a convincing argument.  
> > 
> > I am still a bit concerned still that a stupidly written program that
> > opens /dev/urandom (perhaps unwittingly) and tries to read a few
> > hundred megabytes will become uninterruptible until the read
> > completes, but I'm not sure it's worth it to but in some kludge that
> > says "break if there's a signal and count > 1 megabyte --- otherwise
> > we'll return soon enough".
> > 
> 
> I'm very concerned about this; this is fundamentally a change to
> signal delivery semantics.
> 
> What we might want to go along with is a read smaller than PIPE_BUF
> (the largest size guaranteed to be atomic when writing to a pipe,
> which is another special case) should not return fractional.

What about signals to a process blocked on /dev/random (which also has no
documented mention of being interruptible by signals)?

Not handling short reads is always a bug.

-- 
Mathematics is the supreme nostalgia of our time.

Re: short read from /dev/urandom

[H. Peter Anvin]

Matt Mackall wrote:
> 
> What about signals to a process blocked on /dev/random (which also has no
> documented mention of being interruptible by signals)?
> 
> Not handling short reads is always a bug.
> 

Agreed it is.  All I was saying was that I could see a *small* exception 
(like PIPE_BUF) for /dev/urandom.

Sleeping would be utterly unacceptable.

	-hpa

Re: short read from /dev/urandom

[H. Peter Anvin]

Followup to:  <41E833F4.8090800@redhat.com>
By author:    Ulrich Drepper <drepper@redhat.com>
In newsgroup: linux.dev.kernel
> 
> The code in question comes from a crypto library which is in wide use 
> (http://www.cryptopp.com) and it is using urandom under this assumption. 
>   I fear there is quite a bit more code like this out there.  Changing 
> the ABI after the fact is no good and dangerous in this case.
> 
> I know this is making the device special, but I really think the 
> no-short-reads property should be perserved for urandom.
> 

Does *anything* have it, including files?

I think read() always has the option of returning a short read on
signal delivery.

What urandom has is a no-block guarantee, i.e. the behaviour should be
identical in the presense of the O_NONBLOCK flag, and select/poll
should always indicate that data can be read.

	-hpa

Re: short read from /dev/urandom

[Pavel Machek]

Hi!
> >What do you think?  Does gcc -pg calls sigaction with SA_RESTART, to
> >avoid changing the behaviour of the programs that it is profiling?
> 
> Profiling certainly uses SA_RESTART.  But this was just one possible 
> problem case.
> 
> I'm concerned that there is isgnificant code out there relying on the 
> no-short-read promise.  And perhaps more importantly, other 
> implementations promise the same.

Well, but such code will need to be fixed, anyway; pre-2.6.10 kernels
will stay here for quite a long time.
				Pavel
-- 
64 bytes from 195.113.31.123: icmp_seq=28 ttl=51 time=448769.1 ms         

Re: short read from /dev/urandom

[Matt Mackall]

On Thu, Jan 13, 2005 at 08:54:54PM -0800, Ulrich Drepper wrote:
> The /dev/urandom device is advertised as always returning the requested 
> number of bytes.  Yet, it fails to do this under some situations. 
> Compile this

Here's what random.c says:

 * The two other interfaces are two character devices /dev/random and
 * /dev/urandom.  /dev/random is suitable for use when very high
 * quality randomness is desired (for example, for key generation or
 * one-time pads), as it will only return a maximum of the number of
 * bits of randomness (as estimated by the random number generator)
 * contained in the entropy pool.
 *
 * The /dev/urandom device does not have this limit, and will return
 * as many bytes as are requested.  As more and more random bytes are
 * requested without giving time for the entropy pool to recharge,
 * this will result in random numbers that are merely cryptographically
 * strong.  For many applications, however, this is acceptable.

_Neither_ case mentions signals and the "and will return as many bytes
as requested" is clearly just a restatement of "does not have this
limit". Whoever copied this comment to the manpage was a bit sloppy
and dropped the first clause rather than the second:

       When read, /dev/urandom device will return as many bytes as are
       requested. As a result, if there is not sufficient entropy in
       the entropy pool...

Meanwhile, read(2) says:

	It is not an error if this number is smaller than the number
	of bytes requested; this may happen for example because fewer
	bytes are actually available right now (maybe because we were
	close to end-of-file, or because we are reading from a pipe,
	or from a terminal), or because read() was interrupted by a
	signal.

So anyone doing a read() can expect a short read regardless of the fd
and is quite clear that reads can be interrupted by signals. "It is
not an error". Ever.

-- 
Mathematics is the supreme nostalgia of our time.

Re: short read from /dev/urandom

[Ulrich Drepper]

[-- Attachment #1: Type: text/plain, Size: 679 bytes --]

Matt Mackall wrote:
> _Neither_ case mentions signals and the "and will return as many bytes
> as requested" is clearly just a restatement of "does not have this
> limit". Whoever copied this comment to the manpage was a bit sloppy
> and dropped the first clause rather than the second:

It still means the documented API says there are no short reads.


> So anyone doing a read() can expect a short read regardless of the fd
> and is quite clear that reads can be interrupted by signals. "It is
> not an error". Ever.

Of course are signal interruptions wrong if the signal uses SA_RESTART.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: short read from /dev/urandom

[Matt Mackall]

On Sat, Jan 15, 2005 at 07:58:23PM -0800, Ulrich Drepper wrote:
> Matt Mackall wrote:
> >_Neither_ case mentions signals and the "and will return as many bytes
> >as requested" is clearly just a restatement of "does not have this
> >limit". Whoever copied this comment to the manpage was a bit sloppy
> >and dropped the first clause rather than the second:
> 
> It still means the documented API says there are no short reads.

I maintain that it's ambiguous. And read(2) makes it clear that short
reads can happen any time, any where. Further, your interpretation
makes for a nonsensical API as it implies being uninterruptible for
arbitrary lengths of time. 

Changing the longstanding, sensible code to match a silly and highly
non-standard interpretation of the documentation doesn't fix the
problem in apps either. Presumably they'll still be running on kernels
older than 2.6.11 and I believe most *BSDs have /dev/urandom as well.

> >So anyone doing a read() can expect a short read regardless of the fd
> >and is quite clear that reads can be interrupted by signals. "It is
> >not an error". Ever.
> 
> Of course are signal interruptions wrong if the signal uses SA_RESTART.

That's a separate problem. I'll take a look at fixing that.

-- 
Mathematics is the supreme nostalgia of our time.

Re: short read from /dev/urandom

[Andries Brouwer]

On Sat, Jan 15, 2005 at 07:58:23PM -0800, Ulrich Drepper wrote:

> Matt Mackall wrote:
> >_Neither_ case mentions signals and the "and will return as many bytes
> >as requested" is clearly just a restatement of "does not have this
> >limit". Whoever copied this comment to the manpage was a bit sloppy
> >and dropped the first clause rather than the second:
> 
> It still means the documented API says there are no short reads.

No. It says that /dev/urandom "contains" an unlimited amount
of bits - you can read as many bits from there as you want,
while /dev/random "contains" a limited amount of information -
you can exhaust it.

That is information about the device. There is no suggestion at all
about some special property that would guarantee that the normal
read() system call has special behavior in connection with /dev/urandom.

There is no special documented API. Now that this misunderstanding
occurred I suppose a clarifying sentence will be added.
Nothing special with /dev/urandom.

Applications that make special assumptions are broken.

Andries