linux-kernel - Re: [PATCH RFC v4 1/1] random: WARN on large getrandom() waits and introduce getrandom2()

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <9f359f02-0b43-888c-2c05-8e6661bfa38f@gmail.com>
Date:   Fri, 20 Sep 2019 04:44:30 +0500
From:   "Alexander E. Patrakov" <patrakov@...il.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>
Cc:     "Theodore Y. Ts'o" <tytso@....edu>,
        "Ahmed S. Darwish" <darwish.07@...il.com>,
        Lennart Poettering <mzxreary@...inter.de>,
        "Eric W. Biederman" <ebiederm@...ssion.com>,
        Michael Kerrisk <mtk.manpages@...il.com>,
        lkml <linux-kernel@...r.kernel.org>, linux-ext4@...r.kernel.org,
        linux-man@...r.kernel.org
Subject: Re: [PATCH RFC v4 1/1] random: WARN on large getrandom() waits and
 introduce getrandom2()

20.09.2019 03:23, Alexander E. Patrakov пишет:
> 20.09.2019 02:47, Linus Torvalds пишет:
>> On Thu, Sep 19, 2019 at 1:45 PM Alexander E. Patrakov
>> <patrakov@...il.com> wrote:
>>>
>>> This already resembles in-kernel haveged (except that it doesn't credit
>>> entropy), and Willy Tarreau said "collect the small entropy where it is,
>>> period" today. So, too many people touched upon the topic in one day,
>>> and therefore I'll bite.
>>
>> I'm one of the people who aren't entirely convinced by the jitter
>> entropy - I definitely believe it exists, I just am not necessarily
>> convinced about the actual entropy calculations.
>>
>> So while I do think we should take things like the cycle counter into
>> account just because I think it's a a useful way to force some noise,
>> I am *not* a huge fan of the jitter entropy driver either, because of
>> the whole "I'm not convinced about the amount of entropy".
>>
>> The whole "third order time difference" thing would make sense if the
>> time difference was some kind of smooth function - which it is at a
>> macro level.
>>
>> But at a micro level, I could easily see the time difference having
>> some very simple pattern - say that your cycle counter isn't really
>> cycle-granular, and the load takes 5.33 "cycles" and you see a time
>> difference pattern of (5, 5, 6, 5, 5, 6, ...). No real entropy at all
>> there, it is 100% reliable.
>>
>> At a macro level, that's a very smooth curve, and you'd say "ok, time
>> difference is 5.3333 (repeating)". But that's not what the jitter
>> entropy code does. It just does differences of differences.
>>
>> And that completely non-random pattern has a first-order difference of
>> 0, 1, 1, 0, 1, 1.. and a second order of 1, 0, 1, 1, 0,  and so on
>> forever. So the "jitter entropy" logic will assign that completely
>> repeatable thing entropy, because the delta difference doesn't ever go
>> away.
>>
>> Maybe I misread it.
> 
> You didn't. Let me generalize and rephrase the part of the concern that 
> I agree with, in my own words:
> 
> The same code is used in cryptoapi rng, and also a userspace version 
> exists. These two have been tested by the author via the "dieharder" 
> tool (see the message for commit d9d67c87), so we know that on his 
> machine it actually produces good-quality random bits. However, the 
> in-kernel self-test is much, much weaker, and would not catch the 
> situation when someone's machine is deterministic in a way that you 
> describe, or something similar.

A constructive suggestion here would be to put the first few thousands 
(ok, a completely made up number) raw timing intervals through a "gzip 
compression test" in addition to the third derivative test, just based 
on what we already have in the kernel.

-- 
Alexander E. Patrakov


Download attachment "smime.p7s" of type "application/pkcs7-signature" (4052 bytes)