Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hannes Frederic Sowa wrote: > We call extract_crng when we run out of batched entropy and reseed. How > often we call down to extract_crng depends on how much entropy we > extracted by calls to get_random_int/long, so the number of calls into > those functions matter. > > In extract_crng we have

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hello, On Fri, 2016-12-23 at 20:17 -0500, George Spelvin wrote: > Hannes Frederic Sowa wrote: > > On 24.12.2016 00:39, George Spelvin wrote: > > > We just finished discussing why 8 bytes isn't enough. If you only > > > feed back 8 bytes, an attacker who can do 2^64 computation can find it > > >

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hannes Frederic Sowa wrote: > On 24.12.2016 00:39, George Spelvin wrote: >> We just finished discussing why 8 bytes isn't enough. If you only >> feed back 8 bytes, an attacker who can do 2^64 computation can find it >> (by guessing and computing forward to verify the guess) and recover the >>

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hi, On 24.12.2016 00:39, George Spelvin wrote: > Hannes Frederic Sowa wrote: >> In general this looks good, but bitbuffer needs to be protected from >> concurrent access, thus needing at least some atomic instruction and >> disabling of interrupts for the locking if done outside of >>

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hannes Frederic Sowa wrote: > In general this looks good, but bitbuffer needs to be protected from > concurrent access, thus needing at least some atomic instruction and > disabling of interrupts for the locking if done outside of > get_random_long. Thus I liked your previous approach more where

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hi, On Fri, 2016-12-23 at 13:26 -0500, George Spelvin wrote: > (Cc: list trimmed slightly as the topic is wandering a bit.) > > Hannes Frederic Sowa wrote: > > On Thu, 2016-12-22 at 19:07 -0500, George Spelvin wrote: > > > Adding might_lock() annotations will improve coverage a lot. > > > >

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

(Cc: list trimmed slightly as the topic is wandering a bit.) Hannes Frederic Sowa wrote: > On Thu, 2016-12-22 at 19:07 -0500, George Spelvin wrote: >> Adding might_lock() annotations will improve coverage a lot. > > Might be hard to find the correct lock we take later down the code > path, but if

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

On Thu, 2016-12-22 at 19:07 -0500, George Spelvin wrote: > Hannes Frederic Sowa wrote: > > A lockdep test should still be done. ;) > > Adding might_lock() annotations will improve coverage a lot. Might be hard to find the correct lock we take later down the code path, but if that is possible,

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Hannes Frederic Sowa wrote: > A lockdep test should still be done. ;) Adding might_lock() annotations will improve coverage a lot. > Yes, that does look nice indeed. Accounting for bits instead of bytes > shouldn't be a huge problem either. Maybe it gets a bit more verbose in > case you can't

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

On 22.12.2016 22:11, George Spelvin wrote: >> I do tend to like Ted's version in which we use batched >> get_random_bytes() output. If it's fast enough, it's simpler and lets >> us get the full strength of a CSPRNG. > > With the ChaCha20 generator, that's fine, although note that this abandons >

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

> I do tend to like Ted's version in which we use batched > get_random_bytes() output. If it's fast enough, it's simpler and lets > us get the full strength of a CSPRNG. With the ChaCha20 generator, that's fine, although note that this abandons anti-backtracking entirely. It also takes locks,

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

On Thu, Dec 22, 2016 at 11:24 AM, George Spelvin wrote: >> Having slept on this, I like it less. The problem is that a >> backtracking attacker doesn't just learn H(random seed || entropy_0 || >> secret || ...) -- they learn the internal state of the hash function >>

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

> Having slept on this, I like it less. The problem is that a > backtracking attacker doesn't just learn H(random seed || entropy_0 || > secret || ...) -- they learn the internal state of the hash function > that generates that value. This probably breaks any attempt to apply > security

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

On Wed, Dec 21, 2016 at 6:07 PM, Andy Lutomirski wrote: > On Wed, Dec 21, 2016 at 5:13 PM, George Spelvin > wrote: >> As a separate message, to disentangle the threads, I'd like to >> talk about get_random_long(). >> >> After some thinking, I still

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

> True, but it's called get_random_int(), and it seems like making it > stronger, especially if the performance cost is low to zero, is a good > thing. If it's cheap enough, I don't mind. But it's documented as being marginal-quality, used where speed is more important. In particular, it's

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

On Wed, Dec 21, 2016 at 9:01 PM, George Spelvin wrote: > Andy Lutomirski wrote: >> I don't even think it needs that. This is just adding a >> non-destructive final operation, right? > > It is, but the problem is that SipHash is intended for *small* inputs, > so the

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

Andy Lutomirski wrote: > I don't even think it needs that. This is just adding a > non-destructive final operation, right? It is, but the problem is that SipHash is intended for *small* inputs, so the standard implementations aren't broken into init/update/final functions. There's just one big

Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage

Hi George, On Thu, Dec 22, 2016 at 4:55 AM, George Spelvin wrote: > Do we have to go through this? No, the benchmark was *not* bogus. > Then I replaced the kernel #includes with the necessary typedefs > and #defines to make it compile in user-space. > * I didn't

Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage

> Plus the benchmark was bogus anyway, and when I built a more specific > harness -- actually comparing the TCP sequence number functions -- > SipHash was faster than MD5, even on register starved x86. So I think > we're fine and this chapter of the discussion can come to a close, in > order to

Re: George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

> On Wed, Dec 21, 2016 at 5:13 PM, George Spelvin >> After some thinking, I still like the "state-preserving" construct >> that's equivalent to the current MD5 code. Yes, we could just do >> siphash(current_cpu || per_cpu_counter, global_key), but it's nice to >> preserve a bit more. >> >> It

George's crazy full state idea (Re: HalfSipHash Acceptable Usage)

On Wed, Dec 21, 2016 at 5:13 PM, George Spelvin wrote: > As a separate message, to disentangle the threads, I'd like to > talk about get_random_long(). > > After some thinking, I still like the "state-preserving" construct > that's equivalent to the current MD5 code.

Re: HalfSipHash Acceptable Usage

On Wed, Dec 21, 2016 at 9:25 AM, Linus Torvalds wrote: > On Wed, Dec 21, 2016 at 7:55 AM, George Spelvin > wrote: >> >> How much does kernel_fpu_begin()/kernel_fpu_end() cost? > > It's now better than it used to be, but it's absolutely

Re: HalfSipHash Acceptable Usage

As a separate message, to disentangle the threads, I'd like to talk about get_random_long(). After some thinking, I still like the "state-preserving" construct that's equivalent to the current MD5 code. Yes, we could just do siphash(current_cpu || per_cpu_counter, global_key), but it's nice to

Re: HalfSipHash Acceptable Usage

Theodore Ts'o wrote: > On Wed, Dec 21, 2016 at 01:37:51PM -0500, George Spelvin wrote: >> SipHash annihilates the competition on 64-bit superscalar hardware. >> SipHash dominates the field on 64-bit in-order hardware. >> SipHash wins easily on 32-bit hardware *with enough registers*. >> On

Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage

On Wed, Dec 21, 2016 at 11:27 PM, Theodore Ts'o wrote: > And "with enough registers" includes ARM and MIPS, right? So the only > real problem is 32-bit x86, and you're right, at that point, only > people who might care are people who are using a space-radiation > hardened 386 ---

Re: HalfSipHash Acceptable Usage

On Wed, Dec 21, 2016 at 01:37:51PM -0500, George Spelvin wrote: > SipHash annihilates the competition on 64-bit superscalar hardware. > SipHash dominates the field on 64-bit in-order hardware. > SipHash wins easily on 32-bit hardware *with enough registers*. > On register-starved 32-bit machines,

Re: HalfSipHash Acceptable Usage

On Wed, Dec 21, 2016 at 7:37 PM, George Spelvin wrote: > SipHash annihilates the competition on 64-bit superscalar hardware. > SipHash dominates the field on 64-bit in-order hardware. > SipHash wins easily on 32-bit hardware *with enough registers*. > On

Re: HalfSipHash Acceptable Usage

Eric Dumazet wrote: > Now I am quite confused. > > George said : >> Cycles per byte on 1024 bytes of data: >> Pentium Core 2 Ivy >> 4 Duo Bridge >> SipHash-2-4 38.9 8.3 5.8 >> HalfSipHash-2-4 12.7 4.5 3.2 >> MD5

Re: HalfSipHash Acceptable Usage

Linus wrote: >> How much does kernel_fpu_begin()/kernel_fpu_end() cost? > > It's now better than it used to be, but it's absolutely disastrous > still. We're talking easily many hundreds of cycles. Under some loads, > thousands. I think I've been thoroughly dissuaded, but just to clarify one

Re: HalfSipHash Acceptable Usage

On Wed, Dec 21, 2016 at 7:55 AM, George Spelvin wrote: > > How much does kernel_fpu_begin()/kernel_fpu_end() cost? It's now better than it used to be, but it's absolutely disastrous still. We're talking easily many hundreds of cycles. Under some loads, thousands. And

Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage

On Wed, 2016-12-21 at 11:39 -0500, Rik van Riel wrote: > Does anybody still have a P4? > > If they do, they're probably better off replacing > it with an Atom. The reduced power bills will pay > for replacing that P4 within a year or two. Well, maybe they have millions of units to replace. >

Re: [kernel-hardening] Re: HalfSipHash Acceptable Usage

On Wed, 2016-12-21 at 10:55 -0500, George Spelvin wrote: > Actually, DJB just made a very relevant suggestion. > > As I've mentioned, the 32-bit performance problems are an x86- > specific > problem.  ARM does very well, and other processors aren't bad at all. > > SipHash fits very nicely (and

Re: HalfSipHash Acceptable Usage

Hi Eric, On Wed, Dec 21, 2016 at 4:56 PM, Eric Dumazet wrote: > That really was for 1024 bytes blocks, so pretty much useless for our > discussion ? > > Reading your numbers last week, I thought SipHash was faster, but George > numbers are giving the opposite impression.

Re: HalfSipHash Acceptable Usage

Hi George, On Wed, Dec 21, 2016 at 4:55 PM, George Spelvin wrote: > Actually, DJB just made a very relevant suggestion. > > As I've mentioned, the 32-bit performance problems are an x86-specific > problem. ARM does very well, and other processors aren't bad at all. >

Re: HalfSipHash Acceptable Usage

On Wed, 2016-12-21 at 15:42 +0100, Jason A. Donenfeld wrote: > Hi Eric, > > I computed performance numbers for both 32-bit and 64-bit using the > actual functions in which talking about replacing MD5 with SipHash. > The basic harness is here [1] if you're curious. SipHash was a pretty > clear

Re: HalfSipHash Acceptable Usage

Actually, DJB just made a very relevant suggestion. As I've mentioned, the 32-bit performance problems are an x86-specific problem. ARM does very well, and other processors aren't bad at all. SipHash fits very nicely (and runs very fast) in the MMX registers. They're 64 bits, and there are 8

Re: HalfSipHash Acceptable Usage

Hi Eric, I computed performance numbers for both 32-bit and 64-bit using the actual functions in which talking about replacing MD5 with SipHash. The basic harness is here [1] if you're curious. SipHash was a pretty clear winner for both cases. x86_64: [1.714302]

Re: HalfSipHash Acceptable Usage

Hi George, On Wed, Dec 21, 2016 at 7:34 AM, George Spelvin wrote: > In fact, I have an idea. Allow me to make the following concrete > suggestion for using HalfSipHash with 128 bits of key material: > > - 64 bits are used as the key. > - The other 64 bits are used as

Re: HalfSipHash Acceptable Usage

Eric Dumazet wrote: > On Tue, 2016-12-20 at 22:28 -0500, George Spelvin wrote: >> Cycles per byte on 1024 bytes of data: >> Pentium Core 2 Ivy >> 4 Duo Bridge >> SipHash-2-4 38.9 8.3 5.8 >> HalfSipHash-2-4 12.7 4.5

Re: HalfSipHash Acceptable Usage

On Tue, 2016-12-20 at 22:28 -0500, George Spelvin wrote: > > I do not see why SipHash, if faster than MD5 and more secure, would be a > > problem. > > Because on 32-bit x86, it's slower. > > Cycles per byte on 1024 bytes of data: > Pentium Core 2 Ivy >

Re: HalfSipHash Acceptable Usage

> I do not see why SipHash, if faster than MD5 and more secure, would be a > problem. Because on 32-bit x86, it's slower. Cycles per byte on 1024 bytes of data: Pentium Core 2 Ivy 4 Duo Bridge SipHash-2-4 38.9 8.3 5.8

Re: HalfSipHash Acceptable Usage

On Tue, 2016-12-20 at 16:36 -0500, Theodore Ts'o wrote: > On Mon, Dec 19, 2016 at 06:32:44PM +0100, Jason A. Donenfeld wrote: > > 1) Anything that requires actual long-term security will use > > SipHash2-4, with the 64-bit output and the 128-bit key. This includes > > things like TCP sequence

Re: HalfSipHash Acceptable Usage

Theodore Ts'o wrote: > On Mon, Dec 19, 2016 at 06:32:44PM +0100, Jason A. Donenfeld wrote: >> 1) Anything that requires actual long-term security will use >> SipHash2-4, with the 64-bit output and the 128-bit key. This includes >> things like TCP sequence numbers. This seems pretty uncontroversial

Re: HalfSipHash Acceptable Usage

On Mon, Dec 19, 2016 at 06:32:44PM +0100, Jason A. Donenfeld wrote: > 1) Anything that requires actual long-term security will use > SipHash2-4, with the 64-bit output and the 128-bit key. This includes > things like TCP sequence numbers. This seems pretty uncontroversial to > me. Seem okay to

Re: HalfSipHash Acceptable Usage

Hi JP, On Mon, Dec 19, 2016 at 9:49 PM, Jean-Philippe Aumasson wrote: > > On Mon, Dec 19, 2016 at 6:32 PM Jason A. Donenfeld wrote: >> >> Hi JP, >> >> With the threads getting confusing, I've been urged to try and keep >> the topics and threads

HalfSipHash Acceptable Usage

Hi JP, With the threads getting confusing, I've been urged to try and keep the topics and threads more closely constrained. Here's where we're at, and here's the current pressing security concern. It'd be helpful to have a definitive statement on what you think is best, so we can just build on