From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752308AbbIXTMN (ORCPT ); Thu, 24 Sep 2015 15:12:13 -0400 Received: from mail-io0-f169.google.com ([209.85.223.169]:36371 "EHLO mail-io0-f169.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752167AbbIXTML (ORCPT ); Thu, 24 Sep 2015 15:12:11 -0400 Subject: Re: [PATCH 1/3] Make /dev/urandom scalable To: Jeff Epler References: <1442963767-14945-1-git-send-email-andi@firstfloor.org> <5603004A.20801@gmail.com> <20150923232841.GK1747@two.firstfloor.org> <5603E083.8020004@gmail.com> <20150924131235.GB6841@thunk.org> <56041E2C.2030602@gmail.com> <20150924165204.GA2835@unpythonic.net> Cc: "Theodore Ts'o" , Andi Kleen , linux-kernel@vger.kernel.org, kirill.shutemov@linux.intel.com, herbert@gondor.apana.org.au, Andi Kleen From: Austin S Hemmelgarn Message-ID: <56044ADB.5050102@gmail.com> Date: Thu, 24 Sep 2015 15:11:23 -0400 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 MIME-Version: 1.0 In-Reply-To: <20150924165204.GA2835@unpythonic.net> Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg=sha-512; boundary="------------ms010208020807060006080106" X-Antivirus: avast! (VPS 150924-1, 2015-09-24), Outbound message X-Antivirus-Status: Clean Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org This is a cryptographically signed message in MIME format. --------------ms010208020807060006080106 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: quoted-printable On 2015-09-24 12:52, Jeff Epler wrote: > On Thu, Sep 24, 2015 at 12:00:44PM -0400, Austin S Hemmelgarn wrote: >> I've had cases where I've done thousands of dieharder runs, and it >> failed almost 10% of the time, while stuff like mt19937 fails in >> otherwise identical tests only about 1-2% of the time > > That is a startling result. Please say what architecture, kernel > version, dieharder version and commandline arguments you are using to > get 10% WEAK or FAILED assessments from dieharder on /dev/urandom. I do not remember what exact dieharder version or command-line arguments = (this was almost a decade ago), except that I compiled it from source=20 myself, I do remember it was a 32-bit x86 processor (as that was sadly=20 all I had to run Linux on at the time), and an early 2.6 series kernel=20 (which if I remember correctly was already EOL by the time I was using=20 it). It may haven been impacted by the fact that I did the testing in=20 QEMU, but I would not expect that to affect things that much. It is=20 worth noting that I only saw this happen three times, and and each time=20 it was in a sample of 2000 runs (which has always been the sample size=20 I've used, as that's the point at which I tend to get impatient). I don't tend to do any of that type of testing anymore (at least, not=20 since I started donating spare cycles to various BOINC projects). I=20 will make a point however to run some tests over the weekend on a=20 current kernel version (4.2.1), with the current dieharder version I=20 have available (3.31.1). > > Since the structure of linux urandom involves taking a cryptographic > hash the basic expectation is that it would fail statistical randomness= > tests at similar rates to e.g., dieharder's AES_OFB (-g 205) even in th= e > absence of any entropy in the kernel pools. > > So if 10% failures at correct statistical tests can be replicated it is= > important and needs attention. > > I did take a few moments to look into this today and got starling > failures (p-value 0.00000000) with e.g., > dieharder -g 501 -d 10 > (and a few other tests) using dieharder 3.31.1 on both debian > linux-4.1-rt-amd64 and debian kfreebsd-10-amd64, but this seems to be a= n > upstream bug known at least to debian and redhat, possibly fixed in > current Fedora but apparently not in Debian. > https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=3D745742 > https://bugzilla.redhat.com/show_bug.cgi?format=3Dmultiple&id=3D80= 3292 > if you have an affected version, these failures are seen only with -g > 501, not with -g 200 < /dev/urandom. They are probably also not seen > with 32-bit dieharder. > > diehard_parking_lot| 0| 12000| 100|0.00000000| FAILED > diehard_2dsphere| 2| 8000| 100|0.00000000| FAILED > diehard_3dsphere| 3| 4000| 100|0.00000000| FAILED > diehard_squeeze| 0| 100000| 100|0.00000000| FAILED > diehard_sums| 0| 100| 100|0.00000000| FAILED The diehard_sums test is known and documented to be a flawed test. As=20 far as the other failures, even a top quality RNG should get them=20 sometimes (because a good RNG _should_ spit out long runs of identical=20 bits from time to time, which is why the absolute insanity that is FIPS=20 cryptography standards should not ever be considered when doing anything = other than security work (and only considered cautiously even there)).=20 Based on what I've seen with the AES_OFB generator, 'perfect' generators = should be getting WEAK results about 1% of the time, and FAILED results=20 about 0.1% of the time (except on diehard_sums). A generator never getting FAILED or WEAK results over thousands of runs=20 should be an indication that either that generator is flawed in some way = (ie, it's actively trying to produce numbers that pass the tests, means=20 it's not really a RNG), or the test itself is flawed in some way. --------------ms010208020807060006080106 Content-Type: application/pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" Content-Description: S/MIME Cryptographic Signature MIAGCSqGSIb3DQEHAqCAMIACAQExDzANBglghkgBZQMEAgMFADCABgkqhkiG9w0BBwEAAKCC Brgwgga0MIIEnKADAgECAgMRLfgwDQYJKoZIhvcNAQENBQAweTEQMA4GA1UEChMHUm9vdCBD QTEeMBwGA1UECxMVaHR0cDovL3d3dy5jYWNlcnQub3JnMSIwIAYDVQQDExlDQSBDZXJ0IFNp Z25pbmcgQXV0aG9yaXR5MSEwHwYJKoZIhvcNAQkBFhJzdXBwb3J0QGNhY2VydC5vcmcwHhcN MTUwOTIxMTEzNTEzWhcNMTYwMzE5MTEzNTEzWjBjMRgwFgYDVQQDEw9DQWNlcnQgV29UIFVz ZXIxIzAhBgkqhkiG9w0BCQEWFGFoZmVycm9pbjdAZ21haWwuY29tMSIwIAYJKoZIhvcNAQkB FhNhaGVtbWVsZ0BvaGlvZ3QuY29tMIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEA nQ/81tq0QBQi5w316VsVNfjg6kVVIMx760TuwA1MUaNQgQ3NyUl+UyFtjhpkNwwChjgAqfGd LIMTHAdObcwGfzO5uI2o1a8MHVQna8FRsU3QGouysIOGQlX8jFYXMKPEdnlt0GoQcd+BtESr pivbGWUEkPs1CwM6WOrs+09bAJP3qzKIr0VxervFrzrC5Dg9Rf18r9WXHElBuWHg4GYHNJ2V Ab8iKc10h44FnqxZK8RDN8ts/xX93i9bIBmHnFfyNRfiOUtNVeynJbf6kVtdHP+CRBkXCNRZ qyQT7gbTGD24P92PS2UTmDfplSBcWcTn65o3xWfesbf02jF6PL3BCrVnDRI4RgYxG3zFBJuG qvMoEODLhHKSXPAyQhwZINigZNdw5G1NqjXqUw+lIqdQvoPijK9J3eijiakh9u2bjWOMaleI SMRR6XsdM2O5qun1dqOrCgRkM0XSNtBQ2JjY7CycIx+qifJWsRaYWZz0aQU4ZrtAI7gVhO9h pyNaAGjvm7PdjEBiXq57e4QcgpwzvNlv8pG1c/hnt0msfDWNJtl3b6elhQ2Pz4w/QnWifZ8E BrFEmjeeJa2dqjE3giPVWrsH+lOvQQONsYJOuVb8b0zao4vrWeGmW2q2e3pdv0Axzm/60cJQ haZUv8+JdX9ZzqxOm5w5eUQSclt84u+D+hsCAwEAAaOCAVkwggFVMAwGA1UdEwEB/wQCMAAw VgYJYIZIAYb4QgENBEkWR1RvIGdldCB5b3VyIG93biBjZXJ0aWZpY2F0ZSBmb3IgRlJFRSBo ZWFkIG92ZXIgdG8gaHR0cDovL3d3dy5DQWNlcnQub3JnMA4GA1UdDwEB/wQEAwIDqDBABgNV HSUEOTA3BggrBgEFBQcDBAYIKwYBBQUHAwIGCisGAQQBgjcKAwQGCisGAQQBgjcKAwMGCWCG SAGG+EIEATAyBggrBgEFBQcBAQQmMCQwIgYIKwYBBQUHMAGGFmh0dHA6Ly9vY3NwLmNhY2Vy dC5vcmcwMQYDVR0fBCowKDAmoCSgIoYgaHR0cDovL2NybC5jYWNlcnQub3JnL3Jldm9rZS5j cmwwNAYDVR0RBC0wK4EUYWhmZXJyb2luN0BnbWFpbC5jb22BE2FoZW1tZWxnQG9oaW9ndC5j b20wDQYJKoZIhvcNAQENBQADggIBADMnxtSLiIunh/TQcjnRdf63yf2D8jMtYUm4yDoCF++J jCXbPQBGrpCEHztlNSGIkF3PH7ohKZvlqF4XePWxpY9dkr/pNyCF1PRkwxUURqvuHXbu8Lwn 8D3U2HeOEU3KmrfEo65DcbanJCMTTW7+mU9lZICPP7ZA9/zB+L0Gm1UNFZ6AU50N/86vjQfY WgkCd6dZD4rQ5y8L+d/lRbJW7ZGEQw1bSFVTRpkxxDTOwXH4/GpQfnfqTAtQuJ1CsKT12e+H NSD/RUWGTr289dA3P4nunBlz7qfvKamxPymHeBEUcuICKkL9/OZrnuYnGROFwcdvfjGE5iLB kjp/ttrY4aaVW5EsLASNgiRmA6mbgEAMlw3RwVx0sVelbiIAJg9Twzk4Ct6U9uBKiJ8S0sS2 8RCSyTmCRhJs0vvva5W9QUFGmp5kyFQEoSfBRJlbZfGX2ehI2Hi3U2/PMUm2ONuQG1E+a0AP u7I0NJc/Xil7rqR0gdbfkbWp0a+8dAvaM6J00aIcNo+HkcQkUgtfrw+C2Oyl3q8IjivGXZqT 5UdGUb2KujLjqjG91Dun3/RJ/qgQlotH7WkVBs7YJVTCxfkdN36rToPcnMYOI30FWa0Q06gn F6gUv9/mo6riv3A5bem/BdbgaJoPnWQD9D8wSyci9G4LKC+HQAMdLmGoeZfpJzKHMYIE0TCC BM0CAQEwgYAweTEQMA4GA1UEChMHUm9vdCBDQTEeMBwGA1UECxMVaHR0cDovL3d3dy5jYWNl cnQub3JnMSIwIAYDVQQDExlDQSBDZXJ0IFNpZ25pbmcgQXV0aG9yaXR5MSEwHwYJKoZIhvcN AQkBFhJzdXBwb3J0QGNhY2VydC5vcmcCAxEt+DANBglghkgBZQMEAgMFAKCCAiEwGAYJKoZI hvcNAQkDMQsGCSqGSIb3DQEHATAcBgkqhkiG9w0BCQUxDxcNMTUwOTI0MTkxMTIzWjBPBgkq hkiG9w0BCQQxQgRA7E4e170QHWciceezanOxck33SzFek4GZCSC2BinbDRhZ2VTwDOCx1a2Z ljAUDYznb3fQPO5u+qDjP70vm9+yoDBsBgkqhkiG9w0BCQ8xXzBdMAsGCWCGSAFlAwQBKjAL BglghkgBZQMEAQIwCgYIKoZIhvcNAwcwDgYIKoZIhvcNAwICAgCAMA0GCCqGSIb3DQMCAgFA MAcGBSsOAwIHMA0GCCqGSIb3DQMCAgEoMIGRBgkrBgEEAYI3EAQxgYMwgYAweTEQMA4GA1UE ChMHUm9vdCBDQTEeMBwGA1UECxMVaHR0cDovL3d3dy5jYWNlcnQub3JnMSIwIAYDVQQDExlD QSBDZXJ0IFNpZ25pbmcgQXV0aG9yaXR5MSEwHwYJKoZIhvcNAQkBFhJzdXBwb3J0QGNhY2Vy dC5vcmcCAxEt+DCBkwYLKoZIhvcNAQkQAgsxgYOggYAweTEQMA4GA1UEChMHUm9vdCBDQTEe MBwGA1UECxMVaHR0cDovL3d3dy5jYWNlcnQub3JnMSIwIAYDVQQDExlDQSBDZXJ0IFNpZ25p bmcgQXV0aG9yaXR5MSEwHwYJKoZIhvcNAQkBFhJzdXBwb3J0QGNhY2VydC5vcmcCAxEt+DAN BgkqhkiG9w0BAQEFAASCAgA8kQXwiey5IsQefyTb4LjrJCnTsf48twTgyu80s7CcsDQ6acVS nfNzDZkC9Lb2g79WUyzZFIG2v2P78GyJHgBBW6gDublrNjOUTp00rxd5Zyik4FrXFJCC8Qc3 l/KWW/ByAFR+Z93irN8DDugGBaGhGAhHdZbfUPq5/MfOE5rCiWmiUzpkZG4JF0zD2eL76R2G 6h6WAWNCPHYKrbjhKNgI0bbqt+RTFl9JV7NU6G1PKjCNvvsD449MA17Kj88rp021y18dPPbj qEukT8V/WnFo9NYHW4atK8/6+Pn7GOOjYSnKPhiBsxwNty8qxu9WVXAbW/hBopsNmuW7p8ii fhs0E0pbmWnsHCnrugxmu5tRxQ9nzjSZ1/QUw3f4x9VWHY5sUmDx0WdF3CsoM3uS43pidBm1 BUT8tFDlGv8xPjAQe9Bhioa2Z5oQxhMRWQEq4nSB49DdoVAj6EUvVB1v2O+3poLu98wKoHGa 0slrLTrZY842zBfFvcnjFGjkwSHWmajs89UYdSzVh19RE+NOtmbqxjErA3iV9ZZxFXLyrYbv H5hcQxqucnPlSJgN5M3FWLpdAM0UHx1rfr05+UjycRHk5x5bBKKWJgftUX9t5UkagG8ZyGye 0D0ysroqSpsf1vdclWRTa191iinlu3EFsLjHuK/4kxGzaD3o9ls2oqGskQAAAAAAAA== --------------ms010208020807060006080106--