Bug->Req #70744 [Opn->Csd]: random_bytes() should not use libc arc4random

Edit report at https://bugs.php.net/bug.php?id=70744&edit=1 ID: 70744 Updated by: leigh@php.net Reported by: fsb at thefsb dot org Summary: random_bytes() should not use libc arc4random -Status: Open +Status: Closed -Type: Bug +Type: Feature/Change Request Package: *Encryption and hash functions Operating System: All except Windows PHP Version: 7.0.0RC5 -Assigned To: +Assigned To: leigh Block user comment: N Private report: N New Comment: After further research and discussion, I have decided to remove arc4random. Systems maintainers that believe they have a reliably secure implementation can quite easily add it via their ports trees. Previous Comments: ------------------------------------------------------------------------ [2015-10-21 14:05:07] fsb at thefsb dot org Corrected Summary: limc -> libc ------------------------------------------------------------------------ [2015-10-21 01:37:46] fsb at thefsb dot org 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. ------------------------------------------------------------------------ [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. ------------------------------------------------------------------------ The remainder of the comments for this report are too long. To view the rest of the comments, please view the bug report online at https://bugs.php.net/bug.php?id=70744 -- Edit this bug report at https://bugs.php.net/bug.php?id=70744&edit=1