Date: Thu, 12 Oct 2017 00:11:43 +0200 From: "Jason A. Donenfeld" <Jason@...c4.com> To: Linus Torvalds <torvalds@...ux-foundation.org> Cc: "Tobin C. Harding" <me@...in.cc>, "kernel-hardening@...ts.openwall.com" <kernel-hardening@...ts.openwall.com>, KVM list <kvm@...r.kernel.org>, Linux Kernel Mailing List <linux-kernel@...r.kernel.org>, Kees Cook <keescook@...omium.org>, Paolo Bonzini <pbonzini@...hat.com>, Tycho Andersen <tycho@...ker.com>, "Roberts, William C" <william.c.roberts@...el.com>, Tejun Heo <tj@...nel.org>, Jordan Glover <Golden_Miller83@...tonmail.ch>, Greg KH <gregkh@...uxfoundation.org>, Petr Mladek <pmladek@...e.com>, Joe Perches <joe@...ches.com>, Ian Campbell <ijc@...lion.org.uk>, Sergey Senozhatsky <sergey.senozhatsky@...il.com>, Catalin Marinas <catalin.marinas@....com>, Will Deacon <will.deacon@....com>, Steven Rostedt <rostedt@...dmis.org>, Chris Fries <cfries@...gle.com>, Dave Weinstein <olorin@...gle.com>, Daniel Micay <danielmicay@...il.com>, Djalal Harouni <tixxdz@...il.com>, Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com>, Jann Horn <jann@...jh.net>, pbsd-hn@...tonmail.com Subject: Re: [PATCH 0/3] add %pX specifier On Wed, Oct 11, 2017 at 11:29 PM, Linus Torvalds <torvalds@...ux-foundation.org> wrote: > Yeah, siphash is probably the sanest thing to use. > > How bad would it be to use HalfSipHash on 32-bit architectures? > > On a 32-bit machine, the full siphash is pretty expensive - big > constants, and lots of 64-bit shifts. And 32-bit machines also tend to > mean "slow machines" these days. > > I suspect there's little point in worrying a ton about the 64-bit key, > considering that I think the *input* is generally more guessable than > the output or the key. [1.0000] Warning: kernel object at address A has a problem [2.0000] Warning: kernel object at address B has a problem A and B are known to be in the interval [M, N] ("they're both 128 byte GFP_KERNEL allocations") and |A-B| is in the smaller interval [m, n] ("they're successive net_devices"). With a 64-bit key (as in hsiphash), A and B can probably be bruteforced. If you can bruteforce the key, then %pX==%p, so no good. While this still requires likely >2^64 computation, this can be offloaded from a victim box and parallelized. So we probably want to stick with the 128-bit key of full SipHash for both platforms. Fortunately, it's still pretty fast. On another topic: the approach we're discussing here is using a PRF (pseudo-random function), also known as a keyed hash function. It's not reversible; it isn't encryption. Mapping 64-bit inputs to 64-bit outputs means there _might_ be collisions. Not a very huge chance, considering kernel pointers are nowhere near the full 64-bit domain, but there's a non-zero chance. Of course, this kind of silly tiny possibility doesn't actually matter at all for us, since it means there'd just be an extremely rare confusing dmesg message. So who cares. But there is something slightly different that you might be interested in: a PRP (psuedo-random permutation), also known as a block cipher. In this case, there'd be a 64-bit to 64-bit reversible map, based on a secret key, with no collisions. In other words, pointer encryption, rather than hashing. Aarch64 has some special instructions for this, with the QARMA tweakable block cipher being built-in. Might be fun to nerd out about, but I don't know that we actually need this or would want the complexity, and probably a PRF like SipHash is sufficient. But thought I'd make you aware of the possibility, in case you're interested.
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.