From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-1.1 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 77746C43381 for ; Wed, 27 Mar 2019 18:34:14 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 3CF7420651 for ; Wed, 27 Mar 2019 18:34:14 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=stressinduktion.org header.i=@stressinduktion.org header.b="g2rO9iLP"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="bkra7F1w" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2391708AbfC0SeM (ORCPT ); Wed, 27 Mar 2019 14:34:12 -0400 Received: from out3-smtp.messagingengine.com ([66.111.4.27]:48903 "EHLO out3-smtp.messagingengine.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2388544AbfC0SeL (ORCPT ); Wed, 27 Mar 2019 14:34:11 -0400 Received: from compute7.internal (compute7.nyi.internal [10.202.2.47]) by mailout.nyi.internal (Postfix) with ESMTP id 793FC21AB4; Wed, 27 Mar 2019 14:34:10 -0400 (EDT) Received: from imap2 ([10.202.2.52]) by compute7.internal (MEProxy); Wed, 27 Mar 2019 14:34:10 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= stressinduktion.org; h=mime-version:message-id:in-reply-to :references:date:from:to:cc:subject:content-type; s=fm3; bh=kT29 lIbn5fx7PGACMwudyYigIBNW23qgD1x2UPBza/o=; b=g2rO9iLPVK0hCfXGQK0J ekcS8Kw/iVbXZDCUYxM7siwyKWMwWz3bdPqze5hgFfZsV5zN7HfXOAnNriv4khqS EPcHS/juiIcN89KOV6R2IEWzlRCzyfH4YT8cEHzsW9A+qfRGFSnJuKc+yfEoftq5 EQFCjXS6lkOs3y7Fel1FlTZ4vMlOAq9+fJfllPS0ypruZwhsA74/CtD/jnYY/BN4 AHM4FZ0DfloCjQ0Fh03r/1dzPWiyOCSqMv9XbrWhn9VhdwhqWWjymOXN3VkoU5If cCZ2VKMmLjUhaVzcNH46HcmNpCqtbFmkL2UcdC94z4BpSRgJLYDS1tI5PRneABkx Ww== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=kT29lI bn5fx7PGACMwudyYigIBNW23qgD1x2UPBza/o=; b=bkra7F1wHt/ROtSZgQm9R4 65e7HvEshOlNG0cFIl6oyumQmmMxr70himTBj8HFYrpTKFZ/S7EmqpwjIb20tdiy N3+e2JDJW9Vw3JPtF/VQQrloFoos1rKzfzKGKiQhbh6is/PublP4tGsQi62mhCZ9 /tv1DDg5H3APjG0Cezz0gZaxplB4I369wVf7F/BMj5Dkw8HbtoYP2OnWnE1nXGXa bkTtQteqCn3khnk8/ZOPf6zG5FKpP5xpAHTUBFbTUVbqgDG24LbWxHV8R6ZUDwb5 RGVkPfHwpprJU0Klqt661Ver1tIVZF2OnLWRI0/Wvvg/iao3jyCVcUwa0TREtqXQ == X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedutddrkedvgddutdelucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepofgfggfkjghffffhvffutgesthdtredtreertdenucfhrhhomhepfdfjrghn nhgvshcuhfhrvgguvghrihgtucfuohifrgdfuceohhgrnhhnvghssehsthhrvghsshhinh guuhhkthhiohhnrdhorhhgqeenucfrrghrrghmpehmrghilhhfrhhomhephhgrnhhnvghs sehsthhrvghsshhinhguuhhkthhiohhnrdhorhhgnecuvehluhhsthgvrhfuihiivgeptd X-ME-Proxy: Received: by mailuser.nyi.internal (Postfix, from userid 501) id CE9977C1B7; Wed, 27 Mar 2019 14:34:09 -0400 (EDT) X-Mailer: MessagingEngine.com Webmail Interface User-Agent: Cyrus-JMAP/3.1.5-976-g376b1f3-fmstable-20190314v3 Mime-Version: 1.0 X-Me-Personality: 20898249 Message-Id: <0ce9983d-f257-4808-bd84-4385587e1b41@www.fastmail.com> In-Reply-To: <201903261907.x2QJ7148017418@sdf.org> References: <201903261110.x2QBAFmp001613@sdf.org> <201903261117.x2QBHTnl002697@sdf.org> <109c67e3-7cda-40cf-80e1-a2d3500a2b5d@www.fastmail.com> <201903261907.x2QJ7148017418@sdf.org> Date: Wed, 27 Mar 2019 14:32:55 -0400 From: "Hannes Frederic Sowa" To: "George Spelvin" , "Daniel Borkmann" Cc: netdev@vger.kernel.org Subject: Re: Revising prandom_32 generator Content-Type: text/plain Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org On Tue, Mar 26, 2019, at 20:07, George Spelvin wrote: > On Tue, 26 Mar 2019 at 14:03:55 -0400, Hannes Frederic Sowa wrote: > > On Tue, Mar 26, 2019, at 12:10, George Spelvin wrote: > > The conversation definitely makes sense. > > I also fixed the seeding of prandom; it now uses the > random_ready_callback system for seeding. > > > Are you trying to fix the modulo biases? I think that prandom_u32_max > > also has bias, would that be worth fixing as well? > > I could if you like. I submitted a patch (appended) to do that > for /dev/urandom (using a very clever new algorithm that does it > all with a single multiply in the common case!), but didn't think > the prandom users were critical enough to care. I am not sure. A quick look shows that it might get used for selecting timeouts in the networking stack. Should not matter here at all. If used to select an index in pre-allocated arrays, then effects might be visible. Additionally, by adding all the branches it might make sense to downgrade the function from 'static inline' to regular function. All in all, I don't think it is required and I would just add it if you think it is worth it as well. The additional comments you proposed are definitely worth to add. > > I think tausworthe is not _trivially_ to predict, what about your > > proposed algorithms? I think it is a nice to have safety-net in > > case too much random numbers accidentally leaks (despite reseeding). > > lfsr113 is indeed trivial to predict. It's a 113-bit LFSR defined > by a degree-113 polynomial. (The implementation as four separate > polynomials of degree 31, 29, 28 and 25 doesn't change this.) Given > any 113 bits of its output (not necessarily consecutive), that's > 113 boolean linear equations in 113 unknowns to find the internal > state. > > I don't have PoC code, but Gaussian elimination is not exactly > rocket science. Fair enough; the attack vector I had in mind was solely that some random output could be observed from the kernel via prandom_u32() and the security bar I wanted to beat was a PRNGs which outputs its entire state or a considerable amount of them. As you wrote, your proposed RNGs exhibit more non-linearity, so it is time to switch. :) I wasn't sure if the non-consecutive extraction of output would blow up the Gaussian Elimination at some point (as in taking a few hours to reduce), which I would not consider trivial anymore. Anyway, using those functions in those situations would already be a bug, as Stephen correctly said, but some safety net would be useful (e.g. observing timeouts from a box right after boot up to determine the initial state of the fragmentation IDs would be bad - but early reseeding etc. makes that already difficult). > All of the proposed replacements are considerably less linear and > harder to invert. The xoshiro family are the most linear, > with an LFSR core and only a very simple non-linear state masking. Then all of the proposed prngs are an improvement? Definitely go for it. > Here's the patch mentioned above for unbiased range reduction. > > I just thought of a great improvement! The slow computation > is "-range % range". I could use __buitin_constant_p(range) > to decide between the following implementation and one that > has -range % range pre-computed and passed in. I.e. Heh, if you already made the work and maybe benchmarked it, it might make sense to kill the bias in prandom_u32_max anyway? :) The proposal below looks great! > static inline u32 get_random_max32(u32 range) > { > if (__builtin_constant_p(range)) > return get_random_max32_const(range, -range % range); > else > return get_random_max32_var(range); > } > > [...] > > u32 get_random_max32_var(u32 range) > { > u64 prod = mul_u32_u32(get_random_u32(), range); > > if ((u32)prod < range - 1) { Maybe 'unlikely' could help here? > u32 lim = -range % range; /* = (1<<32) % range */ > > while ((u32)prod < lim) > prod = mul_u32_u32(get_random_u32(), range); > } > return prod >> 32; > } Bye, Hannes