bug#41456: fix cases where insecure randomness could be used

[Taylor Hornby]

On Fri, May 22, 2020 at 10:48 AM Pádraig Brady <address@hidden> wrote:
>
> On 22/05/2020 16:47, Taylor Hornby wrote:
> > On Fri, May 22, 2020 at 8:17 AM Pádraig Brady <address@hidden> wrote:
> >>
> >> On 22/05/2020 08:19, Taylor Hornby wrote:
> >>> I reported a potential security bug on GitHub:
> >>> https://github.com/coreutils/coreutils/pull/32. To save you a click, I'll
> >>> copy-paste it here (for context this is on a PR with a fix):
> >>>
> >>> Comment #1:
> >>>
> >>> Apologies for submitting on GitHub, it's so much more convenient. I will
> >>> understand if no one sees this because I didn't follow the guidelines.
> >>>
> >>> Justification:
> >>>
> >>>      - The existing code is dangerous because it can silently fail to seed
> >>>      the random number generator securely, either when fopen() fails or 
> >>> when
> >>>      read() returns fewer bytes than requested, which can happen if the 
> >>> call
> >>>      is interrupted by an interrupt. This is important for utilities like
> >>>      shred where cryptographic-quality randomness is important.
> >>>      - I removed the bytes_bound stuff because it didn't seem necessary
> >>>      anywhere it was used, and if get_nonce is ever called with 
> >>> bytes_bound <
> >>>      bufsize, then part of ISAAC's initial state will contain
> >>>      timestamps/PIDs, so it will not be uniformly random. Usually, stream
> >>>      ciphers like ISAAC require their initial state to be uniformly 
> >>> random,
> >>>      otherwise there will be statistical biases in the early output.
> >>>
> >>> I have not tested all the utilities this affects.
> >>>
> >>> (Full disclosure is appropriate in this case because any damage has 
> >>> already
> >>> been done, fixing the problem in secret would not stop any attacks, but
> >>> disclosing might encourage users to stop using the dangerous code and
> >>> upgrade.)
> >>>
> >>> Comment #2:
> >>>
> >>> This is a more serious issue on Solars, which apparently has a blocking
> >>> /dev/random 
> >>> <https://icmconference.org/wp-content/uploads/G11b-Fenwick.pdf>
> >>> and NAME_OF_NONCE_DEVICE defaults to /dev/random (see gc-random.m4), or
> >>> when NAME_OF_NONCE_DEVICE is overriden to /dev/random with a configure 
> >>> flag
> >>> on a Linux system.
> >>>
> >>> I ran some experiments on a Debian 9 box, and read() from /dev/random
> >>> frequently returns very few bytes, sometimes as few as just 6 bytes. This
> >>> means, ironically, if someone built the code with /dev/random thinking it
> >>> would be more secure, it's actually less secure, because read() will 
> >>> return
> >>> fewer bytes and then very little of the ISAAC seed will be random and most
> >>> of it will be timestamp/PID/uninitialized memory.
> >>
> >> Testing on a Solaris 10 box indicates that /dev/random doesn't give short 
> >> reads.
> >> All other systems default to /dev/urandom.
> >> coreutils doesn't need cryptographic randomness, so the read from
> >> /dev/urandom should be seen as optional, and present to improve randomness 
> >> when available.
> >> I'm not sure your concerns are justified in the coreutils context.
> >>
> >
> > Thanks for your reply. Yeah, I really doubt it's a problem for most
> > use cases. However I do use the shred utility in a context that
> > requires high-quality randomness: filling a disk with random data
> > prior to using LUKS encryption. Doing so (with good randomness) makes
> > it impossible to tell which parts of the disk have ciphertext from
> > LUKS and which are "unwritten" (since the randomness pass), preventing
> > a small information leak where you can tell how much & where data
> > exists on the drive. I suppose instead of using shred, I should just
> > do a pass of zeros on the encrypted device, so that it's completely
> > filled with ciphertext. I think at the very least a warning should be
> > added to shred's help output or manpage that its output cannot be
> > relied on to be cryptographically secure.
>
> If you were considering changing from the operations,
> one could pass --random-source to shred, which will fail
> as you desire if there is not enough random data.
>
> For example you might pass --random-source=/dev/urandom,
> though noting that this may result in slower operation
> than the internal PRNG.
>
> The default operation is to seed the internal PRNG with 2K
> of random data from /dev/urandom. I think you're saying
> that's sufficient for your needs, but if there was ever
> a short read then the output from coreutils' PRNG would
> not be sufficient, and distinguishable from real LUKS encrypted data.
> Have you noticed that with an entropy determination utility?
> If that was actually the case, then it might be worth
> issuing a warning upon short/failed read of the default nonce device,
> as it would be both consequential and unlikely.
>

Yes that's exactly right. Using /dev/urandom is much slower because of
the overhead of having to make system calls, and a properly-seeded
ISAAC is safe for this use case while being much faster.

Because ISAAC is a stream cipher, its output will look random to
statistical analysis tools even when its seed is very simple (e.g. all
zeroes or a repeating pattern). The problem is that even though it
looks random, when a weak seed is used, there are almost certainly
cryptographic attacks that would let you recover the seed from the
output, which wouldn't be possible if the seed were random.
Furthermore, if the seed were low-enough entropy, like if it were
*only* the timestamp and PIDs in the case where open() fails, then you
could just brute-force all possible timestamps and PIDs until you find
the seed. For the disk-encryption-pre-wiping use case, once you've
recovered the seed, you can easily tell which data on the disk is
encrypted and which came from ISAAC.

I think we should decide whether shred should even support this use
case. If it should, then I think it should either do it safely or
completely fail, and if not then it should be documented in the help
(and maybe added to the list of rejected feature requests). I searched
found some posts online (e.g.
https://security.stackexchange.com/a/215966) that recommend using
shred for this use case, and at least one book that does:

https://books.google.ca/books?id=8R2CDwAAQBAJ&pg=PA299&lpg=PA299&dq=shred+luks+random&source=bl&ots=UhdDwvI2N0&sig=ACfU3U2O-NIKboGKdT_d1qq1gf_Sqy-QVQ&hl=en&sa=X&ved=2ahUKEwjw1I-5_cfpAhW0FTQIHdOlCf4Q6AEwBHoECAoQAQ#v=onepage&q=shred%20luks%20random&f=false

But thankfully the vast majority of the posts I found recommend using
/dev/urandom directly or shred with --random-source=/dev/urandom.

-Taylor