Bug #70744 [Opn]: random_bytes() should not use linc arc4random
Edit report at https://bugs.php.net/bug.php?id=70744&edit=1
ID: 70744
User updated by: fsb at thefsb dot org
Reported by: fsb at thefsb dot org
Summary: random_bytes() should not use linc arc4random
Status: Open
Type: Bug
Package: *Encryption and hash functions
Operating System: All except Windows
PHP Version: 7.0.0RC5
Block user comment: N
Private report: N
New Comment:
Thanks, Leigh, for the info. I'm no cryptographer and don't pretend to understand cipher
algorithms. I just try to keep up to date with security BCPs as they apply to PHP etc. The current
stance seemed to be: Don't use RC4! But...
I was no aware that the legacy RC4 arc4random implementations in the various BSDs (I took current
FreeBSD as model) include the mitigations you mentioned. I have now read the code and see what you
mean. Otoh, I haven't found any sources saying, in effect, "These mitigations make it
safe." If you can refer me, that would be great but I take your word for it if not. (And I
remain unclear why, if the BSD arc4random is safe, are all the BSDs phasing out RC4? And if
it's safe, what is Yarrow for? But that's my problem, not yours.)
However, what led me to discovering that arc4random is random_bytes() first choice on not-Windows
was discovering in tests that random_bytes() on OS X and FreeBSD produces seemingly endless streams
(400 Mbyte/sec for several hours) when PHP cannot read the random devices.
Now that I have read the FreeBSD source it's clear why. The stir function silently falls back
to using PID and gettimeofday().
https://github.com/freebsd/freebsd/blob/master/lib/libc/gen/arc4random.c#L139-L178
This situation does arise in practice. It's not just theoretical.
So while the libc arc4random may be safe when they are seeded from RANDOMDEV (line 156), I'm
not so sure if they can't.
"Is the RNG properly seeded?" is turning out to be the ultimate security question in PHP.
If you can read from the random device or from CryptGenRandom then I think you can be confident. If
not, I'm not so sure.
Previous Comments:
------------------------------------------------------------------------
[2015-10-20 17:29:40] leigh@php.net
Hey fsb,
I did quite a bit of research before including arc4random as an option in this function. I'll
detail what I am aware of, please correct me if I'm wrong.
The weaknesses in RC4 revolve around biases in the keystream or recovery of the initial bytes -
we're not using the keystream for a stream cipher so we can ignore any kind of plaintext
recovery attacks.
Most of these weaknesses relate to the first few bytes of the stream, some the first 256 byes (from
memory). Biases have been observed in longer keystreams too - from 2^24 to 2^25 bytes I believe.
The arc4random implementation in BSD (and OSX) both discards the first few kilobytes of the
keystream, and re-keys regularly - before the 2^24 threshold.
In order to observe biases, you need to observe the uninterrupted keystream. As the keystream shared
between all consumers, it is unlikely that you will observe a complete stream, and you also have no
idea when a rekey will happen.
I would go as far as saying the chance of observing any meaningful bias is negligible.
If you have seen research that suggests the BSD implementation with its mitigations (rather than the
known-broken vanilla RC4) is still unfit for a CSPRNG I'd really like to see it.
------------------------------------------------------------------------
[2015-10-20 16:48:51] fsb at thefsb dot org
Fwiw, asking in Freenode #openbsd this morning:
11:43 tom[] is there a reliable way for a program to determine if the linked libc arc4random
(assuming there is one) is ChaCha20 or heirloom 96 ARC4?
11:47 Straylight tom[]: if the OS version is >= 5.5 (uname(3) should tell you that?), then
it's chaha
11:48 tom[] Straylight: yes, but then this eventually has to evolve into a small database for
all the BSDs
11:49 Straylight tom[]: If you're asking for a mechanism that works across any possible BSD
derivative, then it doesn't exist
In which I am tom[] and time is UTC-04:00. I don't know who is Straylight.
[Sorry again for suggesting in OP that NetBSD introduced ChaCha20. It was OpenBSD in 2013.]
------------------------------------------------------------------------
[2015-10-20 14:57:28] fsb at thefsb dot org
CORRECTION: OpenBSD since 5.5 uses ChaCha20.
But random_bytes() use of arc4random_buf() remains unsafe.
------------------------------------------------------------------------
[2015-10-19 22:04:57] fsb at thefsb dot org
Description:
------------
ARC4 is known to be unsafe for use either as a stream cipher or a CSPRNG. You can read about it on
Wikipedia and elsewhere.
As far as I can tell, until recently, all implementations of the libc arc4random functions are based
on David Mazieres 1996 implementation of ARC4. In November 2014, NetBSD replaced the cipher
underneath libc's arc4random API with ChaCha20, a modern stream cipher currently considered
safe. But this change hasn't made it into a NetBSD release yet. OS X, FreeBSD and OpenBSD have
not yet incorporated NetBSD's source code change and I don't know if they will. So for the
time being we have to assume that libc arc4random is ARC4 cipher and therefore unsafe.
This code branch should be removed.
https://github.com/php/php-src/blob/php-7.0.0RC5/ext/standard/random.c#L91
------------------------------------------------------------------------
--
Edit this bug report at https://bugs.php.net/bug.php?id=70744&edit=1
Thread (7 messages)