Re: use of RDRAND in $random_library
Gunnar Wolf gwolf at gwolf.org writes: using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware Your theory may be good, but we are talking about a scenario in which at least one of the other sources may be not just “shitty entropy” but “a bytestream specifically designed to counteract entropy in the output stream of the XOR” (independence is needed). You’d better use a mechanism that first hashes together the “untrusted” sources¹ and only combine that with the “a bit more trusted” entropy later, using appropriate algorithms. Sure, XOR is fast, but arc4random on MirBSD performs pretty well too (I get about 40 MiB/s easily… on old Pentium-M hardware). ① MirBSD first accumulates them, using a hash that is almost² Bob Jenkins’ one-at-a-time hash (plus, thanks for tytso for pointing this out, some stirring) in an 128-byte buffer, no matter how fast they come in. Then, at most once a second, if the buffer has accumulated at least 128 bytes, this is mixed into an aRC4 structure which is never used directly (i.e. no costly “throw away initial keystream” and all that needed) but only used for contributing bytes to the “main” entropy pool (what is /dev/urandom in Linux) and the “real” aRC4 pool. (We don’t use XOR here either because we know they are not entirely independent… in fact we use this property to ensure some amount of stirring/mixing around.) ② It adds 1 in the initial step so that even adding a NUL byte to a 0x state contributes, and the finaliser step is replaced by AES’ MixColumn step, which is a bit slower, but has better mixing properties without losing anything from the original finalising step. Also, it is used during stirring the 128-byte buffer. bye, //mirabilos -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/loom.20140616t140448-...@post.gmane.org
Re: use of RDRAND in $random_library
Thorsten Glaser t...@debian.org writes: Your theory may be good, but we are talking about a scenario in which at least one of the other sources may be not just “shitty entropy” but “a bytestream specifically designed to counteract entropy in the output stream of the XOR” (independence is needed). You’d better use a mechanism that first hashes together the “untrusted” sources¹ and only combine that with the “a bit more trusted” entropy later, using appropriate algorithms. Sure, XOR is fast, but arc4random on MirBSD performs pretty well too (I get about 40 MiB/s easily… on old Pentium-M hardware). This is the reason why Fortuna uses SHA-256 to mix in entropy. Provided that you use a hash function to mix in entropy and that hash function satisfies the requirements of a cryptographic hash function, there should be no way for an attacker with control over an entropy source to reduce the total entropy created by the the other entropy sources. The worst they should be able to do is add zero entropy. Cryptography Engineering has an excellent chapter on pseudorandom number generators that gets into the issues here. -- Russ Allbery (r...@debian.org) http://www.eyrie.org/~eagle/ -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/87lhsw24su@windlord.stanford.edu
Re: use of RDRAND in $random_library
On 6/13/14, Theodore Ts'o ty...@mit.edu wrote: On Fri, Jun 13, 2014 at 06:51:44PM +, Jacob Appelbaum wrote: I would expect that if the NSA wanted to take control of the RDRAND or the rest of the CPU, they'd dynamically update the microcode in the CPU to change how it behaves. To do this, it appears that they'd need to sign a microcode and then apply an update. The Intel CPU doesn't support a persistent microcode update. A microcode update has to be uploaded after each power cycle. I'm aware and happy about that fact. However, I have a few concerns that come from a different core assumption: we know nothing about the microcode updates that are applied at boot on many systems. What do we know about the microcode updates that are shipping in various operating systems? I think very little. Ben's research is pretty fantastic for this reason. That means that a microcode hack would require that you break root first. I agree that a microcode insertion requires root but I'm not sure that an attacker must always be the one to insert it. Microcode seems like a perfect trojan horse and I am very suspect of it. And if you can break root, you can just bugger the kernel or one or more the userspace binaries. That's going to be as detectable as leaving an extra firmware file in /lib/firmware/intel-ucode. It would be interesting to allow microcode updates at boot only and to signal the kernel that no more are expected. That may change how such an update could be applied. I'm unsure if it would matter as you correctly state. Lots to do! I've long considered that there are so many zero-day exploits that if the NSA decides to carry out a focused attack on a single machine, or machines belonging to a single person, there is a very high probability they can do whatever they want. And this isn't a new problems; even before the days of computers things like black bag jobs were always a thing. Of course, though they have certain advantages and we can ensure that there is a level playing field for all attackers. So I'm personally much more concerned about bulk surveillance, whether it involves passive surveillance using fiber taps, or trojans introduced into distribution-provided binaries. Other people may have their own personal sense of paranoia, but that's mine. I happen to think mine corresponds more with reality, but I'm sure Keith Alexander and James Clapper would try to claim that I should be wearing tin foil hats or something. :-) I think paranoia isn't the right term, your rationale is grounded squarely in reality. :-) All the best, Jacob -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/CAFggDF1wDAEPdYx=p7t7iokmevf6j_o_dkriuv+x4r1yzah...@mail.gmail.com
Re: use of RDRAND in $random_library
On Fri, 13 Jun 2014, Joey Hess wrote:
Henrique de Moraes Holschuh wrote:
Now, the kernel can soft-blacklist RDRAND (and RDSEED) usage[2]. In that
case, the kernel won't use it and it disappears from /proc/cpuinfo, and we
could do that also to avoid processor errata, not just due to user request.
However, AFAIK kernel blacklisting would not cause the instructions to trap
or fail on bare-metal, so userspace could still just use them anyway.
Not sure what you mean by bare metal here.
Not under a hypervisor.
Joey, what does that Haskell lib uses to detect availability of RDRAND?
int cpu_has_rdrand()
{
uint32_t ax,bx,cx,dx,func=1;
__asm__ volatile (cpuid:\
=a (ax), =b (bx), =c (cx), =d (dx) : a (func));
return (cx 0x4000);
}
Oh dear. Can you try running that on a kernel that was booted with the
nordrand command line parameter? I don't have a box with RDRAND support
to test it myself ATM.
Please try it on bare metal (not on a VM).
--
One disk to rule them all, One disk to find them. One disk to bring
them all and in the darkness grind them. In the Land of Redmond
where the shadows lie. -- The Silicon Valley Tarot
Henrique Holschuh
--
To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: https://lists.debian.org/20140614220026.gb18...@khazad-dum.debian.net
Re: use of RDRAND in $random_library
On 13 June 2014 06:27, Gunnar Wolf gw...@gwolf.org wrote: Excuse me if I'm blunt here, but I understand that, on the point of using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware entropy source is faulted and produces just an endless stream of '001001001001001001', xoring it with a valid Golomb sequence will give you something even more random than a Golomb sequence. Or am I misunderstanding my crypto? The proof that XORing streams can't reduce the entropy relies on the sources being independant. I think the issue here is we don't know if RDRAND is independent or not. That said, doing a SHA256 over the output should be sufficient (assuming the CPU doesn't see you're doing a hash and short circuits it). Have a nice day, -- Martijn van Oosterhout klep...@gmail.com http://svana.org/kleptog/
Re: use of RDRAND in $random_library
Martijn van Oosterhout dijo [Fri, Jun 13, 2014 at 10:09:02AM +0200]: Excuse me if I'm blunt here, but I understand that, on the point of using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware entropy source is faulted and produces just an endless stream of '001001001001001001', xoring it with a valid Golomb sequence will give you something even more random than a Golomb sequence. Or am I misunderstanding my crypto? The proof that XORing streams can't reduce the entropy relies on the sources being independant. I think the issue here is we don't know if RDRAND is independent or not. That said, doing a SHA256 over the output should be sufficient (assuming the CPU doesn't see you're doing a hash and short circuits it). Ofcourse. Were your CPU to have a SHA256-defeating algorithm, it would have to detect the purpose it was being used for, or problems would be easily detected :) -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140613125118.ga18...@gwolf.org
Re: use of RDRAND in $random_library
On Wed, 11 Jun 2014, Joey Hess wrote: I don't have a stong opinion on the security of RDRAND, which is a contentious topic in a domain I am not expert in. However, I would much rather rely on linux developers to make the right decision on that, rather than libraries deciding on an ad-hoc basis. Especially because I second that. Previous experience with the xstore-rng instruction for the VIA PadLock on-die HRNG[1] taught me just how dangerous it is dangerous to call model-specific instructions directly. Although it is Intel we're talking about here, so you could at least expect a microcode update to disable RDRAND/RDSEED where broken (it is a known fact that they can enable or disable it through a microcode update, refer to errata BV54 for the 3rd gen Intel Core processor, where the microcode update does the opposite and enables RDRAND). It would take like 6 months for such a microcode update to show up anywhere, and the low adoption rates would ensure a lot of boxes would never get the fix. So it would be up to the kernel to avoid disaster. Now, the kernel can soft-blacklist RDRAND (and RDSEED) usage[2]. In that case, the kernel won't use it and it disappears from /proc/cpuinfo, and we could do that also to avoid processor errata, not just due to user request. However, AFAIK kernel blacklisting would not cause the instructions to trap or fail on bare-metal, so userspace could still just use them anyway. Joey, what does that Haskell lib uses to detect availability of RDRAND? [1] Due to processor errata, instead of writing the requested number of bytes, the xstore-rng instruction will write 16 bytes, trashing nearby data. Known to happen at least to the Via Nano processor. [2] Add nordrand to the kernel command line to soft-blacklist RDRAND. You cannot blacklist RDSEED on most kernels at this time, the fix was not sent to -stable (yet). -- One disk to rule them all, One disk to find them. One disk to bring them all and in the darkness grind them. In the Land of Redmond where the shadows lie. -- The Silicon Valley Tarot Henrique Holschuh -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140613134310.gc30...@khazad-dum.debian.net
Re: use of RDRAND in $random_library
On Fri, Jun 13, 2014 at 10:09:02AM +0200, Martijn van Oosterhout wrote: Excuse me if I'm blunt here, but I understand that, on the point of using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware entropy source is faulted and produces just an endless stream of '001001001001001001', xoring it with a valid Golomb sequence will give you something even more random than a Golomb sequence. The proof that XORing streams can't reduce the entropy relies on the sources being independant. I think the issue here is we don't know if RDRAND is independent or not. That said, doing a SHA256 over the output should be sufficient (assuming the CPU doesn't see you're doing a hash and short circuits it). Basically, the question is how blatently do you think the NSA could bugger the CPU. If you believe they can completely bugger the CPU, so they can detect that you are implementing some explicit crypto instruction, and change its behaviour, or they can peek ahead in the instruction pipeline, notice an XOR, determine that one of its inputs is an RDRAND instruction, and the other inputs come from a read of /dev/urandom, and then modify the behaviour of the XOR, all in such a way that the hundreds or thousands of Intel employees that need to improve, test, debug, etc. the CPU instruction execution engine wouldn't notice, then you might as well give up now and start implementing your own CPU from transitors, capictors, resistors, and wires. While I am willing to believe they might be able to secretly subvert or bribe Intel to subvert the RDRAND engine, in some way which no other or very few other employees at Intel would detect, to believe they could then do so with the entire CPU is MUCH harder to believe. There are probably much easier things to do, such as subverting someone in Red Hat's release engineering department, for example. A buggered kernel is easier to accomplish, and much harder to detect. This is one of the reasons why implementing reproducible binary builds is a realy good idea from a security perspective. This allows you to spot check that various binaries correspond to the sources that they claim to be form. Cheers, - Ted -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140613140444.ga19...@thunk.org
Re: use of RDRAND in $random_library
Henrique de Moraes Holschuh wrote:
Now, the kernel can soft-blacklist RDRAND (and RDSEED) usage[2]. In that
case, the kernel won't use it and it disappears from /proc/cpuinfo, and we
could do that also to avoid processor errata, not just due to user request.
However, AFAIK kernel blacklisting would not cause the instructions to trap
or fail on bare-metal, so userspace could still just use them anyway.
Not sure what you mean by bare metal here.
Joey, what does that Haskell lib uses to detect availability of RDRAND?
int cpu_has_rdrand()
{
uint32_t ax,bx,cx,dx,func=1;
__asm__ volatile (cpuid:\
=a (ax), =b (bx), =c (cx), =d (dx) : a (func));
return (cx 0x4000);
}
--
see shy jo
signature.asc
Description: Digital signature
Re: use of RDRAND in $random_library
On 6/13/14, Theodore Ts'o ty...@mit.edu wrote: On Fri, Jun 13, 2014 at 10:09:02AM +0200, Martijn van Oosterhout wrote: Excuse me if I'm blunt here, but I understand that, on the point of using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware entropy source is faulted and produces just an endless stream of '001001001001001001', xoring it with a valid Golomb sequence will give you something even more random than a Golomb sequence. The proof that XORing streams can't reduce the entropy relies on the sources being independant. I think the issue here is we don't know if RDRAND is independent or not. That said, doing a SHA256 over the output should be sufficient (assuming the CPU doesn't see you're doing a hash and short circuits it). Basically, the question is how blatently do you think the NSA could bugger the CPU. If you believe they can completely bugger the CPU, so they can detect that you are implementing some explicit crypto instruction, and change its behaviour, or they can peek ahead in the instruction pipeline, notice an XOR, determine that one of its inputs is an RDRAND instruction, and the other inputs come from a read of /dev/urandom, and then modify the behaviour of the XOR, all in such a way that the hundreds or thousands of Intel employees that need to improve, test, debug, etc. the CPU instruction execution engine wouldn't notice, then you might as well give up now and start implementing your own CPU from transitors, capictors, resistors, and wires. While I am willing to believe they might be able to secretly subvert or bribe Intel to subvert the RDRAND engine, in some way which no other or very few other employees at Intel would detect, to believe they could then do so with the entire CPU is MUCH harder to believe. I would expect that if the NSA wanted to take control of the RDRAND or the rest of the CPU, they'd dynamically update the microcode in the CPU to change how it behaves. To do this, it appears that they'd need to sign a microcode and then apply an update. According to some great research by Ben Hawkes, it may be that there is a 2048bit RSA key that is used for signing: http://inertiawar.com/microcode/ In the case of Lavabit, we have learned that the US Government will assert that they can request cryptographic keys in a Grand Jury. Is it that case that they might try the same with Intel? Is 2048 a large enough key size to stop the NSA? There are quite a few open questions. If the NSA can update the microcode, I believe we could fairly state that they have subverted the security of the entire CPU. There are probably much easier things to do, such as subverting someone in Red Hat's release engineering department, for example. A buggered kernel is easier to accomplish, and much harder to detect. This is one of the reasons why implementing reproducible binary builds is a realy good idea from a security perspective. This allows you to spot check that various binaries correspond to the sources that they claim to be form. I agree and I'd add that they're likely taking many angles all at once. And it isn't just the NSA. The NSA just has a great head start and a home field advantage. Intel Inside could have a few different meanings! :-) All the best, Jacob -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/cafggdf34pi1ojup0l48ncyk+szneosc7semjxqxh4gefg-n...@mail.gmail.com
Re: use of RDRAND in $random_library
Joey Hess wrote:
int cpu_has_rdrand()
{
uint32_t ax,bx,cx,dx,func=1;
__asm__ volatile (cpuid:\
=a (ax), =b (bx), =c (cx), =d (dx) : a (func));
return (cx 0x4000);
}
That's actually buggy on any platform building position-independent code
(common with hardened build flags). PIC uses ebx, and that would conflict with
this code, resulting in a compile failure. GCC provides a cpuid.h
with a __get_cpuid function that avoids that problem.
- Josh Triplett
--
To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: https://lists.debian.org/20140613191608.GA3593@jtriplet-mobl1
Re: use of RDRAND in $random_library
On Fri, Jun 13, 2014 at 06:51:44PM +, Jacob Appelbaum wrote: I would expect that if the NSA wanted to take control of the RDRAND or the rest of the CPU, they'd dynamically update the microcode in the CPU to change how it behaves. To do this, it appears that they'd need to sign a microcode and then apply an update. The Intel CPU doesn't support a persistent microcode update. A microcode update has to be uploaded after each power cycle. That means that a microcode hack would require that you break root first. And if you can break root, you can just bugger the kernel or one or more the userspace binaries. That's going to be as detectable as leaving an extra firmware file in /lib/firmware/intel-ucode. I've long considered that there are so many zero-day exploits that if the NSA decides to carry out a focused attack on a single machine, or machines belonging to a single person, there is a very high probability they can do whatever they want. And this isn't a new problems; even before the days of computers things like black bag jobs were always a thing. So I'm personally much more concerned about bulk surveillance, whether it involves passive surveillance using fiber taps, or trojans introduced into distribution-provided binaries. Other people may have their own personal sense of paranoia, but that's mine. I happen to think mine corresponds more with reality, but I'm sure Keith Alexander and James Clapper would try to claim that I should be wearing tin foil hats or something. :-) Cheers, - Ted -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140613232132.gb5...@thunk.org
Re: use of RDRAND in $random_library
Joey Hess wrote:
Josh Triplett wrote:
However, just as we encourage projects to reuse libraries rather than
copying code around, we *should* encourage projects to use standardized
randomness libraries rather than hardcoding rdrand (or, for that matter,
hardcoding /dev/urandom).
Performance aside, why is a standardized randomness library (which does
not currently exist) better than a stanardized kernel interface?
At least two reasons: because a random number source that doesn't
require kernel privileges should not need to take the performance hit of
going through the kernel, and because many userspace applications will
not want to follow the kernel's rejection of hardware random number
generation.
Also, while no widely used library exists, at least one library does
exist: libcryptorandom. Given the straightforward nature of the
algorithm (if hardware random numbers available, use them, otherwise
read from /dev/{,u}random as appropriate), I'd bet other such
implementations exist. To encourage code reuse and ease of systemwide
changes, I think it makes sense to package such libraries and have
userspace applications use them rather than hardcoding support for any
particular hardware random number source.
- Josh Triplett
--
To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: https://lists.debian.org/20140612062538.GA27235@thin
Re: use of RDRAND in $random_library
Hi, Steve Langasek: Debian should do the right thing, regardless of what upstreams may believe. I don't trust the hardware random generator. At all. Given what's been revealed about the NSA so far, being extra paranoid about anything we cannot verify to be secure is the right thing to do. That being said, sometimes you just need the binary equivalent of an uncompressible Lorem Ipsum text (dd if=/dev/urandom), but IMHO the kernel could (and should) provide a device for that. -- -- Matthias Urlichs signature.asc Description: Digital signature
Re: use of RDRAND in $random_library
On Wed, 11 Jun 2014, Josh Triplett wrote: Any program desiring high-performance random numbers has a good reason to use RDRAND or RDSEED: they produce randomness *far* faster than the kernel, and Yes, because SIGILL is so much faster… Anyway. Even on systems supporting RDRAND, user space SHALL not use it as sole source of entropy. http://crypto.stackexchange.com/a/10397/8475 shows why. If user space needs *a lot* of entropy, it should use arc4random_buf() from -lbsd (libbsd-dev). However, the default setting uses only a handful of bytes from /dev/urandom for seeding, because Linux’ urandom device is inferiour to the random devices on OpenBSD/MirBSD, so you should seed the aRC4 state with additional random bytes: /* aRC4 state has about 1700 bits of entropy */ char buf[212]; if ((fd = open(/dev/urandom, O_RDONLY)) == -1) err(1, open); if ((size_t)read(fd, buf, sizeof(buf)) != sizeof(buf)) /* or use saturated read loop */ err(1, read); arc4random_addrandom(buf, sizeof(buf)); explicit_bzero(buf, sizeof(buf)); /* now throw away early keystream */ char anotherbuf[256]; int i; for (i = 0; i 12; ++i) arc4random_buf(anotherbuf, sizeof(anotherbuf)); /* actually, make sure the compiler doesn’t optimise away the above */ explicit_bzero(anotherbuf, sizeof(anotherbuf)); After this, you can use arc4random() and arc4random_buf() to your heart’s content. The library will reseed every 1.6M of output or so. If you really want rdrand, use a second arc4random_addrandom() call with a buffer filled by rdrand; they are accumulative. You may pass buffers between 1 and 256 bytes of length to arc4random_addrandom(). You can do this manually in a loop, too (there is no indication that, once seeded properly as above, you need to repeat throwing away the initial keystream, for this purpose and as long as the data added is sufficiently random and not dependent on arc4random’s output). bye, //mirabilos -- “ah that reminds me, thanks for the stellar entertainment that you and certain other people provide on the Debian mailing lists │ sole reason I subscribed to them (I'm not using Debian anywhere) is the entertainment factor │ Debian does not strike me as a place for good humour, much less German admin-style humour” -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/alpine.deb.2.10.1406121014170.17...@tglase.lan.tarent.de
Re: use of RDRAND in $random_library
At Thu, 12 Jun 2014 08:36:16 +0200, Matthias Urlichs wrote: That being said, sometimes you just need the binary equivalent of an uncompressible Lorem Ipsum text (dd if=/dev/urandom), but IMHO the kernel could (and should) provide a device for that. If you just want to overwrite something with random data, you can use shred instead of doing a dd from /dev/urandom. Shred uses an internal PRNG that should be fast enough: http://www.gnu.org/software/coreutils/manual/coreutils.html#Random-sources -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/87ha3q6zlx.wl%jer...@dekkers.ch
Re: use of RDRAND in $random_library
Josh Triplett j...@joshtriplett.org writes: At least two reasons: because a random number source that doesn't require kernel privileges should not need to take the performance hit of going through the kernel, I'm very dubious that this performance hit is substantial enough that it should have an influence on our decision. If we really care about good random numbers, we're probably in an application where, given a performance versus security tradeoff, we should always choose security without a second thought. The small number of applications for which random numbers are in the performance-critical path are generally crypto applications where security is paramount. So the remaining question is if the Linux /dev/random is more secure than using the hardware random number generator. and because many userspace applications will not want to follow the kernel's rejection of hardware random number generation. I've never seen a convincing argument that the kernel /dev/random is likely to be *less* secure than the hardware random number generator. It's either more secure or the same level of security. Given that, it's a risk analysis, and the fact that we have absolutely no idea what the hardware random number generator is doing, it would be quite possible to insert a mathematical back door into it, and there's no way to audit it, I understand why people want to put a software randomization layer that we *can* audit in front of it. -- Russ Allbery (r...@debian.org) http://www.eyrie.org/~eagle/ -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/878up2jb9y@windlord.stanford.edu
Re: use of RDRAND in $random_library
On Thu, Jun 12, 2014 at 10:19:37AM -0700, Russ Allbery wrote: I've never seen a convincing argument that the kernel /dev/random is likely to be *less* secure than the hardware random number generator. It's either more secure or the same level of security. Given that, it's a risk analysis, and the fact that we have absolutely no idea what the hardware random number generator is doing, it would be quite possible to insert a mathematical back door into it, and there's no way to audit it, I understand why people want to put a software randomization layer that we *can* audit in front of it. One thing to worry about is what happens if the software library (if it is implemented as a shared library) gets modified by a bad guy. One thing a really paranoid program can do is to mix (via XOR, for example) the output that it gets from /dev/urandom or this cryptorandom shared library with RDRAND. That way, if Unit 61398 tries to hack the cryptrandom shared library, there's a fail safe (assuming they haven't hacked Intel's internal systems to introduce a back door --- if anyone has done that it's much more likely to be the NSA :-) since the PRC presumably wouldn't be able to hack RDRAND. The reason why /dev/urandom combines RDRAND with other sources of entropy is something that is something that userspace programs can do as well, especially if it's as easy to do as grabbing entropy from RDRAND if it happens to be available. Even if /dev/urandom is bug-free(tm), I can't guarantee that the bad guy hasn't hacked your kernel --- or worse, hacked whoever is building and uplodaing the kernel .deb's to the upload queue (or hacked someone on the ftpmaster team --- remember, the NSA hunts sysadmins :-). - Ted -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140612180609.ga24...@thunk.org
Re: use of RDRAND in $random_library
On Thu, Jun 12, 2014 at 10:23:58AM +0200, Thorsten Glaser wrote: On Wed, 11 Jun 2014, Josh Triplett wrote: device is inferiour to the random devices on OpenBSD/MirBSD, so you should seed the aRC4 state with additional random bytes: As far as I know, OpenBSD stopped using (A)RC4 for their random number generation for good reason, even though the function is still called that way. You now seems to suggest to use RC4 again, which seems like a bad idea to me. Kurt -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140612191906.ga9...@roeckx.be
Re: use of RDRAND in $random_library
Hi! On Thu, 2014-06-12 at 21:19:06 +0200, Kurt Roeckx wrote: On Thu, Jun 12, 2014 at 10:23:58AM +0200, Thorsten Glaser wrote: On Wed, 11 Jun 2014, Josh Triplett wrote: device is inferiour to the random devices on OpenBSD/MirBSD, so you should seed the aRC4 state with additional random bytes: As far as I know, OpenBSD stopped using (A)RC4 for their random number generation for good reason, even though the function is still called that way. You now seems to suggest to use RC4 again, which seems like a bad idea to me. For the next libbsd upstream release I'm planning on pulling the implementation from OpenBSD, as I saw mentioned in a previous thread here on d-d, and afterwards submitted as a bug report. Thanks, Guillem -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140612200421.ga7...@pulsar.hadrons.org
Re: use of RDRAND in $random_library
Kurt Roeckx dixit: As far as I know, OpenBSD stopped using (A)RC4 for their random number generation for good reason, even though the function is They stopped, but not for good reason. But you can also use the new unlicenced algorithm they use, if you really feel like it, it’s not bad either, just lacks a proper licence. Or just use whatever libbsd ships. still called that way. You now seems to suggest to use RC4 again, which seems like a bad idea to me. It is not a bad idea. Using RC4 in certain environments (WEP, TLS) has its downsides, but I analysed each of them in the context of using it for a stretching RNG, and found out that, with a tweak¹², aRC4 is still good there. ① Not included in OpenBSD or libbsd, TTBOMK ② Change arc4random() to drop 1 or 2 bytes randomly, in addition to those four it reads. Change arc4random_buf() to drop 1/2/3/4 bytes randomly for every up to 256 bytes it reads. Increase the amount of bytes thrown away after rekeying to 12*256 plus some random amount of bytes. Using arc4_getbyte to determine these random amounts is correct (and takes care of one byte already). bye, //mirabilos -- “ah that reminds me, thanks for the stellar entertainment that you and certain other people provide on the Debian mailing lists │ sole reason I subscribed to them (I'm not using Debian anywhere) is the entertainment factor │ Debian does not strike me as a place for good humour, much less German admin-style humour” -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/pine.bsm.4.64l.1406122048380.5...@herc.mirbsd.org
Re: Re: use of RDRAND in $random_library
Theodore Ts'o wrote: On Thu, Jun 12, 2014 at 10:19:37AM -0700, Russ Allbery wrote: I've never seen a convincing argument that the kernel /dev/random is likely to be *less* secure than the hardware random number generator. It's either more secure or the same level of security. Given that, it's a risk analysis, and the fact that we have absolutely no idea what the hardware random number generator is doing, it would be quite possible to insert a mathematical back door into it, and there's no way to audit it, I understand why people want to put a software randomization layer that we *can* audit in front of it. One thing to worry about is what happens if the software library (if it is implemented as a shared library) gets modified by a bad guy. One thing a really paranoid program can do is to mix (via XOR, for example) the output that it gets from /dev/urandom or this cryptorandom shared library with RDRAND. If you don't trust a hardware random number generator, you should not xor it and another random number source together; after all, if you believe the numbers coming out of the hardware random source are not actually random, you might just as easily believe that they're the precise non-random values needed to xor with another CPU register to produce non-random values. And assuming you *don't* believe that, then there's little point in mixing a fast random source you trust with a slow random source you trust. (Also, if you don't trust a hardware random number generator, you should ask yourself why you trust any other instruction on your CPU. If you don't trust the hardware you run on, you're doomed anyway; it's a good idea to reduce your attack surface, but your attack surface *always* includes your hardware. But I'd prefer to sidestep that entire argument, and instead suggest that it's (more) ridiculous to have this argument in Debian rather than elsewhere.) That way, if Unit 61398 tries to hack the cryptrandom shared library, If you can intercept calls to an arbitrary shared library, what stops you from intercepting calls to open and read, feeding back non-random data for reads of /dev/random and /dev/urandom? - Josh Triplett -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140613015610.GA7986@thin
Re: use of RDRAND in $random_library
Josh Triplett j...@joshtriplett.org writes: If you don't trust a hardware random number generator, you should not xor it and another random number source together; after all, if you believe the numbers coming out of the hardware random source are not actually random, you might just as easily believe that they're the precise non-random values needed to xor with another CPU register to produce non-random values. I would certainly hope that the mixing algorithm of any decent random number source is better than just xor. And given that, I don't believe the mathematics supports your assertion here. It's considerably harder to backdoor a random number generator to cause a higher-level mixing random number generator that combines multiple sources of entropy to produce predictable random numbers than it is to cause it to spit out predictable random numbers directly. (Also, if you don't trust a hardware random number generator, you should ask yourself why you trust any other instruction on your CPU. Because it's way easier to hide a backdoor in a random number generator than it is in other parts of the CPU instruction set. A random number generator does one specific thing, which is unpredictable by the calling code by *definition*, and which has known ways to backdoor via mechanisms that provide the attacker with a trap-door attack. This is far more difficult to do for instructions that are hidden behind layers of unknown future code. Yes, you can add backdoor paths that trigger on certain data patterns, but you have to then engineer ways of introducing those data patterns and the backdoor behavior has to be useful. It's a far trickier problem. By comparison, backdooring the random number generator with a trap-door function gets you a general crypto break of crypto done with that random number generator pretty much directly. If you don't trust the hardware you run on, you're doomed anyway; This is far too simple of a statement to be accurate. It depends on the type of hardware attack. At best, this statement is true of a targetted, specific attack against one piece of hardware (*your* laptop in particular), which is not what we're talking about here. We're talking about the possibility of embedding a generic backdoor in widely-distributed commodity hardware. The specific attack that people are concerned about here is a long-lived, wide-spread backdoor in a consumer product, which requires very careful design to not be detected. This is far more likely for random number generators because (a) we already know exactly how to backdoor a random number generator in this fashion to allow an attacker with secret knowledge to reproduce the number stream while still passing statistical randomness checks, and (b) the use case for random number generators is very narrow and this sort of backdoor won't be revealed as a bug by other normal use. -- Russ Allbery (r...@debian.org) http://www.eyrie.org/~eagle/ -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/871tuty313@windlord.stanford.edu
Re: use of RDRAND in $random_library
Russ Allbery dijo [Thu, Jun 12, 2014 at 07:08:40PM -0700]: If you don't trust a hardware random number generator, you should not xor it and another random number source together; after all, if you believe the numbers coming out of the hardware random source are not actually random, you might just as easily believe that they're the precise non-random values needed to xor with another CPU register to produce non-random values. I would certainly hope that the mixing algorithm of any decent random number source is better than just xor. And given that, I don't believe the mathematics supports your assertion here. It's considerably harder to backdoor a random number generator to cause a higher-level mixing random number generator that combines multiple sources of entropy to produce predictable random numbers than it is to cause it to spit out predictable random numbers directly. Excuse me if I'm blunt here, but I understand that, on the point of using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware entropy source is faulted and produces just an endless stream of '001001001001001001', xoring it with a valid Golomb sequence will give you something even more random than a Golomb sequence. Or am I misunderstanding my crypto? -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140613042708.ga17...@gwolf.org
Re: use of RDRAND in $random_library
Gunnar Wolf gw...@gwolf.org writes: Russ Allbery dijo [Thu, Jun 12, 2014 at 07:08:40PM -0700]: I would certainly hope that the mixing algorithm of any decent random number source is better than just xor. And given that, I don't believe the mathematics supports your assertion here. It's considerably harder to backdoor a random number generator to cause a higher-level mixing random number generator that combines multiple sources of entropy to produce predictable random numbers than it is to cause it to spit out predictable random numbers directly. Excuse me if I'm blunt here, but I understand that, on the point of using entropy to seed a PRNG, if you have several shitty entropy sources and one _really_ good one, and you xor them all together, the resulting output is as random as the best of them. If your hardware entropy source is faulted and produces just an endless stream of '001001001001001001', xoring it with a valid Golomb sequence will give you something even more random than a Golomb sequence. Or am I misunderstanding my crypto? I don't think you are, but xor has a bunch of unintuitive properties where, if you know or can predict even portions or mathematical properties of one of the byte streams involved in the xor, you can do lots of interesting things with the results. I was assuming that Josh was thinking of something along those lines. It's possible that xor with other entropy sources is good enough and xor defeats a backdoored random number source, but I don't know the math well enough to hazard an opinion. I do know that the cryptographically secure random number generators whose algorithms I've read about use stronger one-way functions instead of xor: stream ciphers, block ciphers, or cryptographic hash functions. At least based on my understanding of the theory, I think that mixing a backdoored entropy source with other entropy sources in a random number generator like Fortuna (which is based on the AES block cipher in counter mode) would make it quite difficult for an attacker with knowledge of the back door to exploit that knowledge. I don't know enough about the exact algorithm behind /dev/random to be sure that the same is true for it, but I would hope that it is. (Although Wikipedia says that it's hash-based, which would probably make it quite a bit slower than Fortuna since hashes are slower than block ciphers.) -- Russ Allbery (r...@debian.org) http://www.eyrie.org/~eagle/ -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/87bntxwhh5@windlord.stanford.edu
Re: use of RDRAND in $random_library
Ugh, sorry to follow up to myself, but I got a key part of this wrong. Russ Allbery r...@debian.org writes: At least based on my understanding of the theory, I think that mixing a backdoored entropy source with other entropy sources in a random number generator like Fortuna (which is based on the AES block cipher in counter mode) would make it quite difficult for an attacker with knowledge of the back door to exploit that knowledge. Fortuna does indeed use AES in counter mode to generate the random number stream, but it uses SHA-256 to mix in entropy. This is the primary defense against a backdoored entropy source (like the hardware random number generator, if one is concerned that it has a back door): mixing it with other entropy sources using a one-way hash like SHA-256 should mean that any one entropy source cannot *decrease* the total entropy of the system when added to other entropy sources, assuming SHA-256 functions correctly as a cryptographic hash. I don't know enough about the exact algorithm behind /dev/random to be sure that the same is true for it, but I would hope that it is. (Although Wikipedia says that it's hash-based, which would probably make it quite a bit slower than Fortuna since hashes are slower than block ciphers.) Fortuna is also hash-based in that sense (it uses a hash to mix in entropy), so I should say that I don't know any of the details of the difference between it and /dev/random. -- Russ Allbery (r...@debian.org) http://www.eyrie.org/~eagle/ -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/877g4lwh5m@windlord.stanford.edu
Re: use of RDRAND in $random_library
Joey Hess wrote: I stumbled over a library which has switched to using RDRAND in a new upsteam version (not yet packaged), instead of /dev/urandom[1]. I don't have a stong opinion on the security of RDRAND, which is a contentious topic in a domain I am not expert in. However, I would much rather rely on linux developers to make the right decision on that, rather than libraries deciding on an ad-hoc basis. Especially because the kernel has a wider spectrum of choices than use/avoid (IIRC it currently mixes in RDRAND with other entropy sources.) Perhaps we should avoid libraries in Debian using RDRAND directly, if the library has uses related to security. (Maybe some game or simulation library would have a good reason to use it.) Any program desiring high-performance random numbers has a good reason to use RDRAND or RDSEED: they produce randomness *far* faster than the kernel, and with less latency. (For instance, dd if=/dev/urandom of=/dev/disk-to-wipe is typically gated by the speed of /dev/urandom rather than the disk.) The kernel should be using RDRAND or RDSEED as appropriate, and it's sad that it doesn't (or, at least, it's sad that there's no configuration option to do so). That said, we might want to encourage upstreams to use standardized libraries that detect the availability of hardware random number generation and automatically fall back to /dev/urandom or /dev/random (depending on the type of randomness requested), rather than open-coding such detection/fallback and inline assembly. That would also help incorporate support for other types of hardware random number generators, rather than only supporting whatever random randomness a library author happened to add support for. Would it make sense to scan for the opcode? No, let's not propagate this issue outside the kernel. Anyone wishing to complain about the use of hardware-accelerated randomness should argue that upstream with projects that adopt it; Debian should not be taking a position on this one way or another. However, just as we encourage projects to reuse libraries rather than copying code around, we *should* encourage projects to use standardized randomness libraries rather than hardcoding rdrand (or, for that matter, hardcoding /dev/urandom). - Josh Triplett -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/20140611224541.GA12701@jtriplet-mobl1
Re: use of RDRAND in $random_library
On 6/11/14, Joey Hess jo...@debian.org wrote: I stumbled over a library which has switched to using RDRAND in a new upsteam version (not yet packaged), instead of /dev/urandom[1]. Which library is using it? I don't have a stong opinion on the security of RDRAND, which is a contentious topic in a domain I am not expert in. However, I would much rather rely on linux developers to make the right decision on that, rather than libraries deciding on an ad-hoc basis. Especially because the kernel has a wider spectrum of choices than use/avoid (IIRC it currently mixes in RDRAND with other entropy sources.) I tend to agree for a few reasons. Genreally, I don't trust RDRAND and the doping paper doesn't help: http://arstechnica.com/security/2013/09/researchers-can-slip-an-undetectable-trojan-into-intels-ivy-bridge-cpus/ Perhaps we should avoid libraries in Debian using RDRAND directly, if the library has uses related to security. (Maybe some game or simulation library would have a good reason to use it.) Quite a few programs and libraries will have this issue if a cursory search of the internet is an indication. Would it make sense to scan for the opcode? Yes, very much so. It is potentially a security bug. It will be interesting to track it. All the best, Jacob -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: https://lists.debian.org/cafggdf0rcbmta0wyu5wwjefmirkrj2rnuyl9ra-3xvo5mgk...@mail.gmail.com
Re: use of RDRAND in $random_library
On Wed, Jun 11, 2014 at 03:46:07PM -0700, Josh Triplett wrote: Would it make sense to scan for the opcode? No, let's not propagate this issue outside the kernel. Anyone wishing to complain about the use of hardware-accelerated randomness should argue that upstream with projects that adopt it; Debian should not be taking a position on this one way or another. Debian should do the right thing, regardless of what upstreams may believe. (Which is not to say anything about what the right thing is in this case.) -- Steve Langasek Give me a lever long enough and a Free OS Debian Developer to set it on, and I can move the world. Ubuntu Developerhttp://www.debian.org/ slanga...@ubuntu.com vor...@debian.org signature.asc Description: Digital signature
Re: use of RDRAND in $random_library
Josh Triplett wrote: However, just as we encourage projects to reuse libraries rather than copying code around, we *should* encourage projects to use standardized randomness libraries rather than hardcoding rdrand (or, for that matter, hardcoding /dev/urandom). Performance aside, why is a standardized randomness library (which does not currently exist) better than a stanardized kernel interface? -- see shy jo signature.asc Description: Digital signature
Re: use of RDRAND in $random_library
Jacob Appelbaum wrote: On 6/11/14, Joey Hess jo...@debian.org wrote: I stumbled over a library which has switched to using RDRAND in a new upsteam version (not yet packaged), instead of /dev/urandom[1]. Which library is using it? I didn't want to name names and am more interested in the general question, but it's http://hackage.haskell.org/package/entropy/ -- which is a foundation for a sizable chunk of the Haskell security stack including eg, its TLS implementation. -- see shy jo signature.asc Description: Digital signature
