Differences between revisions 7 and 18 (spanning 11 versions)
Revision 7 as of 2017-01-16 20:51:50
Size: 2503
Comment:
Revision 18 as of 2017-03-15 13:28:45
Size: 5109
Comment: reference
Deletions are marked like this. Additions are marked like this.
Line 11: Line 11:
== Implementation == == Implementations ==
Line 13: Line 13:
arc4random initialises itself with some random bytes from the kernel, but rather than using those bytes directly, a stream cipher is used to produce longer streams of output. Re-seeding happens occasionally thereafter. The intention was to avoid the overhead of a system call, for each call to arc4random(3) arc4random(3) initialises itself with some random bytes from the kernel, but rather than returning those bytes directly, a stream cipher is used to produce longer streams of output. Re-seeding happens occasionally thereafter. The intention was to avoid the overhead of making a system call, on each call to arc4random(3)
Line 15: Line 15:
The function when originally implemented in OpenBSD, used the RC4 cipher to produce the output stream. OpenBSD now uses a ChaCha20 stream cipher. The function when originally implemented in OpenBSD, used the RC4 cipher to produce the output stream. OpenBSD now uses a !ChaCha20 stream cipher.
Line 17: Line 17:
If a process forks, it should re-seed itself to avoid each process sharing the same RNG state. OpenBSD uses the mmap(2) INHERIT_ZERO flag to reliably detect forks, and then re-seed. If a process forks, it should re-seed itself to avoid each process sharing the same RNG state. OpenBSD uses the mmap(2) INHERIT_ZERO flag to reliably detect forks, and then re-seed.  (FreeBSD 11.1 shall implement this too).
Line 19: Line 19:
FreeBSD makes a system call to getpid(2) to check whether it should do this, but that means the overhead of arc4random(3) could be worse than if the RC4 cipher wasn't used at all... FreeBSD versions before 11.1 make a system call to getpid(2) to detect forking, but that means the overhead on every call to arc4random(3) may be worse than if no stream cipher was being used at all...
Line 21: Line 21:
libbsd changed from using RC4 to ChaCha20 in version 0.8.0 (Debian package version 0.8.0-1). https://lists.freebsd.org/pipermail/freebsd-security/2014-July/007849.html
Line 23: Line 23:
FreeBSD's libc still uses RC4 libkern/arc4random.c, but discards the first 1024 bytes of the stream cipher's output, to try to mitigate known weaknesses in the cipher. FreeBSD's libc still uses RC4 (in libkern/arc4random.c), but discarded the first 1024 bytes of the stream cipher's output, to try to mitigate the known weaknesses of that cipher.  (In 11.1 and STABLE-10, it now discards 3072 bytes).
Line 31: Line 31:
libbsd provides an arc4random(3), previously using RC4 but this was changed to !ChaCha20 in version 0.8.0 (Debian package version 0.8.0-1). GNU libc's atfork can be used to reliably detect forking.
Line 33: Line 35:
Similar code to arc4random can be found in libevent, and dozens of other free software programs.
Line 35: Line 36:
== Concerns == == Embedded code copies ==
Line 37: Line 38:
RC4 is not considered to be a cryptographically strong cipher any more. OpenBSD bundles implementations of arc4random, getentropy etc. in their 'portable' releases of: LibreSSL, OpenNTPd, OpenSMTPd, OpenSSH, signify. We should be consult with them before changing anything there.
Line 39: Line 40:
Some implementations discard the first 1KByte of more of the keystream as a possible countermeasure, but some do not. Embedded copies of this code can also be [[https://codesearch.debian.net/search?perpkg=1&q=_rs_stir|found]] in:
Line 41: Line 42:
Some implementations don't re-seed reliably (or perhaps at all) when a process forks.   * atheme-services - uses !ChaCha20, suffers issues 2, 3 described below
  * getdns - uses !ChaCha20, suffers issue 2 described below
  * ncrack - uses !ChaCha20, suffers issue 2 described below
  * newlib - uses !ChaCha20; unclear how it detects forking
  * pureftpd - uses !ChaCha20, suffers issues 2, 3 described below
  * unbound - uses !ChaCha20, suffers issue 2 described below; FTBFS on kfreebsd, hurd because getentropy implementations are missing

Embedded code copies are a concern because perhaps nobody will remember to maintain them. Here are some good examples where that happened already:

  * [[http://sources.debian.net/src/cmake/3.7.2-1/Utilities/cmlibarchive/libarchive/archive_random.c/?hl=54#L54|cmake]] - uses RC4! has issues 1, 2, 3
  * [[http://sources.debian.net/src/gtk-gnutella/1.1.8-2/src/lib/arc4random.c/|gtk-gnutella]] - uses RC4! has issues 1, 2, 3

A similar interface to arc4random(3) can also be found in libevent.

== Issues with some arc4random implementations ==

1. RC4 is not considered to be a cryptographically strong cipher any more.

1a. Some implementations using RC4, do not discard the start of the keystream which is known to have strong biases (i.e. predictability)

2b. Some implementations discard the first 1 KByte of the keystream as a possible countermeasure, but according to leaked US-govt. documents that is ''not'' sufficient; one ought to discard 3 KBytes:

https://lists.freebsd.org/pipermail/freebsd-security/2017-March/009245.html

2. Some implementations don't re-seed reliably (or perhaps at all) when a process forks. MAP_INHERIT_ZERO is reliable, but only available on OpenBSD, and in FreeBSD from version 11.1. atfork functions are the best thing available on most other platforms. getpid is slowest (requiring a syscall on every iteration), and there are edge cases where it doesn't work:
Line 45: Line 70:
Some methods of seeding are unsafe, and failures cannot be indicated to the caller. In a chroot/jail environment, perhaps /dev/urandom is missing. Or if all file descriptors are exhausted, nothing can be read from there. OpenBSD and FreeBSD provide system calls that are guaranteed to not fail. 3. Some methods of seeding are unsafe, and failures cannot be indicated to the caller. In a chroot/jail environment, perhaps /dev/urandom is missing. Or if all file descriptors are exhausted, nothing can be read from there. OpenBSD and FreeBSD provide system calls that are guaranteed to not fail.

== Issues with arc4random fallback code ==

When arc4random is not available, some software falls back to other methods of gathering entropy of generating random bytes. In some cases the fallback was insecure, e.g. using getpid or the clock:

  * CVE-2017-2625 in libxdmcp
  * CVE-2017-2626 in libice

https://www.x41-dsec.de/lab/advisories/x41-2017-001-xorg/ suggests compiling those libraries against libbsd instead.

arc4random(3) is random-number-generating library function, first available on BSD platforms, and also on GNU/Linux with libbsd.

Manual pages

http://man.openbsd.org/?query=arc4random

https://www.freebsd.org/cgi/man.cgi?query=arc4random

https://manpages.debian.org/cgi-bin/man.cgi?query=arc4random

Implementations

arc4random(3) initialises itself with some random bytes from the kernel, but rather than returning those bytes directly, a stream cipher is used to produce longer streams of output. Re-seeding happens occasionally thereafter. The intention was to avoid the overhead of making a system call, on each call to arc4random(3)

The function when originally implemented in OpenBSD, used the RC4 cipher to produce the output stream. OpenBSD now uses a ChaCha20 stream cipher.

If a process forks, it should re-seed itself to avoid each process sharing the same RNG state. OpenBSD uses the mmap(2) INHERIT_ZERO flag to reliably detect forks, and then re-seed. (FreeBSD 11.1 shall implement this too).

FreeBSD versions before 11.1 make a system call to getpid(2) to detect forking, but that means the overhead on every call to arc4random(3) may be worse than if no stream cipher was being used at all...

https://lists.freebsd.org/pipermail/freebsd-security/2014-July/007849.html

FreeBSD's libc still uses RC4 (in libkern/arc4random.c), but discarded the first 1024 bytes of the stream cipher's output, to try to mitigate the known weaknesses of that cipher. (In 11.1 and STABLE-10, it now discards 3072 bytes).

https://svnweb.freebsd.org/base/head/lib/libc/gen/arc4random.c?view=markup

and is also used within the kernel:

https://svnweb.freebsd.org/base/head/sys/libkern/arc4random.c?view=markup

libbsd provides an arc4random(3), previously using RC4 but this was changed to ChaCha20 in version 0.8.0 (Debian package version 0.8.0-1). GNU libc's atfork can be used to reliably detect forking.

GNU/kFreeBSD provides only the libbsd implementation.

Embedded code copies

OpenBSD bundles implementations of arc4random, getentropy etc. in their 'portable' releases of: LibreSSL, OpenNTPd, OpenSMTPd, OpenSSH, signify. We should be consult with them before changing anything there.

Embedded copies of this code can also be found in:

  • atheme-services - uses ChaCha20, suffers issues 2, 3 described below

  • getdns - uses ChaCha20, suffers issue 2 described below

  • ncrack - uses ChaCha20, suffers issue 2 described below

  • newlib - uses ChaCha20; unclear how it detects forking

  • pureftpd - uses ChaCha20, suffers issues 2, 3 described below

  • unbound - uses ChaCha20, suffers issue 2 described below; FTBFS on kfreebsd, hurd because getentropy implementations are missing

Embedded code copies are a concern because perhaps nobody will remember to maintain them. Here are some good examples where that happened already:

A similar interface to arc4random(3) can also be found in libevent.

Issues with some arc4random implementations

1. RC4 is not considered to be a cryptographically strong cipher any more.

1a. Some implementations using RC4, do not discard the start of the keystream which is known to have strong biases (i.e. predictability)

2b. Some implementations discard the first 1 KByte of the keystream as a possible countermeasure, but according to leaked US-govt. documents that is not sufficient; one ought to discard 3 KBytes:

https://lists.freebsd.org/pipermail/freebsd-security/2017-March/009245.html

2. Some implementations don't re-seed reliably (or perhaps at all) when a process forks. MAP_INHERIT_ZERO is reliable, but only available on OpenBSD, and in FreeBSD from version 11.1. atfork functions are the best thing available on most other platforms. getpid is slowest (requiring a syscall on every iteration), and there are edge cases where it doesn't work:

https://www.agwa.name/blog/post/libressls_prng_is_unsafe_on_linux

3. Some methods of seeding are unsafe, and failures cannot be indicated to the caller. In a chroot/jail environment, perhaps /dev/urandom is missing. Or if all file descriptors are exhausted, nothing can be read from there. OpenBSD and FreeBSD provide system calls that are guaranteed to not fail.

Issues with arc4random fallback code

When arc4random is not available, some software falls back to other methods of gathering entropy of generating random bytes. In some cases the fallback was insecure, e.g. using getpid or the clock:

  • CVE-2017-2625 in libxdmcp
  • CVE-2017-2626 in libice

https://www.x41-dsec.de/lab/advisories/x41-2017-001-xorg/ suggests compiling those libraries against libbsd instead.