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] [day] [month] [year] [list]
Date:   Sat, 8 Oct 2022 20:57:54 -0600
From:   "Jason A. Donenfeld" <Jason@...c4.com>
To:     David Laight <David.Laight@...LAB.COM>
Cc:     Kees Cook <keescook@...omium.org>,
        Christophe Leroy <christophe.leroy@...roup.eu>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "patches@...ts.linux.dev" <patches@...ts.linux.dev>,
        Andreas Noever <andreas.noever@...il.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Borislav Petkov <bp@...en8.de>,
        Catalin Marinas <catalin.marinas@....com>,
        Christoph Böhmwalder 
        <christoph.boehmwalder@...bit.com>, Christoph Hellwig <hch@....de>,
        Daniel Borkmann <daniel@...earbox.net>,
        Dave Airlie <airlied@...hat.com>,
        Dave Hansen <dave.hansen@...ux.intel.com>,
        "David S . Miller" <davem@...emloft.net>,
        Eric Dumazet <edumazet@...gle.com>,
        Florian Westphal <fw@...len.de>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        "H . Peter Anvin" <hpa@...or.com>,
        Heiko Carstens <hca@...ux.ibm.com>,
        Helge Deller <deller@....de>,
        Herbert Xu <herbert@...dor.apana.org.au>,
        Huacai Chen <chenhuacai@...nel.org>,
        Hugh Dickins <hughd@...gle.com>,
        Jakub Kicinski <kuba@...nel.org>,
        "James E . J . Bottomley" <jejb@...ux.ibm.com>,
        Jan Kara <jack@...e.com>, Jason Gunthorpe <jgg@...pe.ca>,
        Jens Axboe <axboe@...nel.dk>,
        Johannes Berg <johannes@...solutions.net>,
        Jonathan Corbet <corbet@....net>,
        Jozsef Kadlecsik <kadlec@...filter.org>,
        KP Singh <kpsingh@...nel.org>, Marco Elver <elver@...gle.com>,
        Mauro Carvalho Chehab <mchehab@...nel.org>,
        Michael Ellerman <mpe@...erman.id.au>,
        Pablo Neira Ayuso <pablo@...filter.org>,
        Paolo Abeni <pabeni@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Richard Weinberger <richard@....at>,
        Russell King <linux@...linux.org.uk>,
        Theodore Ts'o <tytso@....edu>,
        Thomas Bogendoerfer <tsbogend@...ha.franken.de>,
        Thomas Gleixner <tglx@...utronix.de>,
        Thomas Graf <tgraf@...g.ch>,
        Ulf Hansson <ulf.hansson@...aro.org>,
        Vignesh Raghavendra <vigneshr@...com>,
        WANG Xuerui <kernel@...0n.name>, Will Deacon <will@...nel.org>,
        Yury Norov <yury.norov@...il.com>,
        "dri-devel@...ts.freedesktop.org" <dri-devel@...ts.freedesktop.org>,
        "kasan-dev@...glegroups.com" <kasan-dev@...glegroups.com>,
        "kernel-janitors@...r.kernel.org" <kernel-janitors@...r.kernel.org>,
        "linux-arm-kernel@...ts.infradead.org" 
        <linux-arm-kernel@...ts.infradead.org>,
        "linux-block@...r.kernel.org" <linux-block@...r.kernel.org>,
        "linux-crypto@...r.kernel.org" <linux-crypto@...r.kernel.org>,
        "linux-doc@...r.kernel.org" <linux-doc@...r.kernel.org>,
        "linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>,
        "linux-media@...r.kernel.org" <linux-media@...r.kernel.org>,
        "linux-mips@...r.kernel.org" <linux-mips@...r.kernel.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-mmc@...r.kernel.org" <linux-mmc@...r.kernel.org>,
        "linux-mtd@...ts.infradead.org" <linux-mtd@...ts.infradead.org>,
        "linux-nvme@...ts.infradead.org" <linux-nvme@...ts.infradead.org>,
        "linux-parisc@...r.kernel.org" <linux-parisc@...r.kernel.org>,
        "linux-rdma@...r.kernel.org" <linux-rdma@...r.kernel.org>,
        "linux-s390@...r.kernel.org" <linux-s390@...r.kernel.org>,
        "linux-um@...ts.infradead.org" <linux-um@...ts.infradead.org>,
        "linux-usb@...r.kernel.org" <linux-usb@...r.kernel.org>,
        "linux-wireless@...r.kernel.org" <linux-wireless@...r.kernel.org>,
        "linuxppc-dev@...ts.ozlabs.org" <linuxppc-dev@...ts.ozlabs.org>,
        "loongarch@...ts.linux.dev" <loongarch@...ts.linux.dev>,
        "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
        "sparclinux@...r.kernel.org" <sparclinux@...r.kernel.org>,
        "x86@...nel.org" <x86@...nel.org>,
        Toke Høiland-Jørgensen <toke@...e.dk>,
        Chuck Lever <chuck.lever@...cle.com>, Jan Kara <jack@...e.cz>
Subject: Re: [PATCH v3 3/5] treewide: use get_random_u32() when possible

On Sat, Oct 08, 2022 at 09:53:33PM +0000, David Laight wrote:
> From: Jason A. Donenfeld
> > Sent: 07 October 2022 18:56
> ...
> > > Given these kinds of less mechanical changes, it may make sense to split
> > > these from the "trivial" conversions in a treewide patch. The chance of
> > > needing a revert from the simple 1:1 conversions is much lower than the
> > > need to revert by-hand changes.
> > >
> > > The Cocci script I suggested in my v1 review gets 80% of the first
> > > patch, for example.
> > 
> > I'll split things up into a mechanical step and a non-mechanical step.
> > Good idea.
> 
> I'd also do something about the 'get_random_int() & 3' cases.
> (ie remainder by 2^n-1)
> These can be converted to 'get_random_u8() & 3' (etc).
> So they only need one random byte (not 4) and no multiply.
> 
> Possibly something based on (the quickly typed, and not C):
> #define get_random_below(val) [
> 	if (builtin_constant(val))
> 		BUILD_BUG_ON(!val || val > 0x100000000ull)
> 		if (!(val & (val - 1)) {
> 			if (val <= 0x100)
> 				return get_random_u8() & (val - 1);
> 			if (val <= 0x10000)
> 				return get_random_u16() & (val - 1);
> 			return get_random_u32() & (val - 1);
> 		}
> 	}
> 	BUILD_BUG_ON(sizeof (val) > 4);
> 	return ((u64)get_random_u32() * val) >> 32;

This is already how the prandom_u32_max() implementation works, as
suggested in the cover letter. The multiplication by constants in it
reduces to bit shifts and you already get all the manual masking
possible.

> get_random_below() is a much better name than prandom_u32_max().

Yes, but that name is reserved for when I succeed at making a function
that bounds with a uniform distribution. prandom_u32_max()'s
distribution is non-uniform since it doesn't do rejection sampling. Work
in progress is on https://git.zx2c4.com/linux-rng/commit/?h=jd/get_random_u32_below .
But out of common respect for this already huge thread with a massive
CC list, if you want to bikeshed my WIP stuff, please start a new thread
for that and not bog this one down. IOW, no need to reply here directly.
That'd annoy me.

Jason

Powered by blists - more mailing lists