Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
> I already did this. Check my branch. Do you think it should return "u32" (as you currently have it) or "unsigned long"? I thought the latter, since it doesn't cost any more and makes more > I wonder if this could also lead to a similar aliasing > with arch_get_random_int, since I'm pretty sure all rdrand-like > instructions return native word size anyway. Well, Intel's can return 16, 32 or 64 bits, and it makes a small difference with reseed scheduling. >> - Ted, Andy Lutorminski and I will try to figure out a construction of >> get_random_long() that we all like. > And me, I hope... No need to make this exclusive. Gaah, engage brain before fingers. That was so obvious I didn't say it, and the result came out sounding extremely rude. A better (but longer) way to write it would be "I'm sorry that I, Ted, and Andy are all arguing with you and each other about how to do this and we can't finalize this part yet". -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Sat, Dec 17, 2016 at 12:44 AM, George Spelvinwrote: > Ths advice I'd give now is: > - Implement > unsigned long hsiphash(const void *data, size_t len, const unsigned long > key[2]) > .. as SipHash on 64-bit (maybe SipHash-1-3, still being discussed) and > HalfSipHash on 32-bit. I already did this. Check my branch. > - Document when it may or may not be used carefully. Good idea. I'll write up some extensive documentation about all of this, detailing use cases and our various conclusions. > - #define get_random_int (unsigned)get_random_long That's a good idea, since ultimately the other just casts in the return value. I wonder if this could also lead to a similar aliasing with arch_get_random_int, since I'm pretty sure all rdrand-like instructions return native word size anyway. > - Ted, Andy Lutorminski and I will try to figure out a construction of > get_random_long() that we all like. And me, I hope... No need to make this exclusive. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
> 64-bit security for an RNG is not reasonable even with rekeying. No no > no. Considering we already have a massive speed-up here with the > secure version, there's zero reason to start weakening the security > because we're trigger happy with our benchmarks. No no no. Just to clarify, I was discussing the idea with Ted (who's in charge of the whole thing, not me), not trying to make any sort of final decision on the subject. I need to look at the various users (46 non-trivial ones for get_random_int, 15 for get_random_long) and see what their security requirements actually are. I'm also trying to see if HalfSipHash can be used in a way that gives slightly more than 64 bits of effective security. The problem is that the old MD5-based transform had unclear, but obviously ample, security. There were 64 bytes of global secret and 16 chaining bytes per CPU. Adapting SipHash (even the full version) takes more thinking. An actual HalfSipHash-based equivalent to the existing code would be: #define RANDOM_INT_WORDS (64 / sizeof(long))/* 16 or 8 */ static u32 random_int_secret[RANDOM_INT_WORDS] cacheline_aligned __read_mostly; static DEFINE_PER_CPU(unsigned long[4], get_random_int_hash) __aligned(sizeof(unsigned long)); unsigned long get_random_long(void) { unsigned long *hash = get_cpu_var(get_random_int_hash); unsigned long v0 = hash[0], v1 = hash[1], v2 = hash[2], v3 = hash[3]; int i; /* This could be improved, but it's equivalent */ v0 += current->pid + jiffies + random_get_entropy(); for (i = 0; i < RANDOM_INT_WORDS; i++) { v3 ^= random_int_secret[i]; HSIPROUND; HSIPROUND; v0 ^= random_int_secret[i]; } /* To be equivalent, we *don't* finalize the transform */ hash[0] = v0; hash[1] = v1; hash[2] = v2; hash[3] = v3; put_cpu_var(get_random_int_hash); return v0 ^ v1 ^ v2 ^ v3; } I don't think there's a 2^64 attack on that. But 64 bytes of global secret is ridiculous if the hash function doesn't require that minimum block size. It'll take some thinking. Ths advice I'd give now is: - Implement unsigned long hsiphash(const void *data, size_t len, const unsigned long key[2]) .. as SipHash on 64-bit (maybe SipHash-1-3, still being discussed) and HalfSipHash on 32-bit. - Document when it may or may not be used carefully. - #define get_random_int (unsigned)get_random_long - Ted, Andy Lutorminski and I will try to figure out a construction of get_random_long() that we all like. ('scuse me for a few hours, I have some unrelated things I really *should* be working on...) -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
An idea I had which mght be useful: You could perhaps save two rounds in siphash_*u64. The final word with the length (called "b" in your implementation) only needs to be there if the input is variable-sized. If every use of a given key is of a fixed-size input, you don't need a length suffix. When the input is an even number of words, that can save you two rounds. This requires an audit of callers (e.g. you have to use different keys for IPv4 and IPv6 ISNs), but can save time. (This is crypto 101; search "MD-strengthening" or see the remark on p. 101 on Damgaard's 1989 paper "A design principle for hash functions" at http://saluc.engr.uconn.edu/refs/algorithms/hashalg/damgard89adesign.pdf but I'm sure that Ted, Jean-Philippe, and/or DJB will confirm if you'd like.) Jason A. Donenfeld wrote: > Oh, okay, that is exactly what I thought was going on. I just thought > you were implying that jiffies could be moved inside the hash, which > then confused my understanding of how things should be. In any case, > thanks for the explanation. No, the rekeying procedure is cleverer. The thing is, all that matters is that the ISN increments fast enough, but not wrap too soon. It *is* permitted to change the random base, as long as it only increases, and slower than the timestamp does. So what you do is every few minutes, you increment the high 4 bits of the random base and change the key used to generate the low 28 bits. The base used for any particular host might change from 0x1000 to 0x2fff, or from 0x1fff to 0x2000, but either way, it's increasing, and not too fast. This has the downside that an attacker can see 4 bits of the base, so only needs to send send 2^28 = 256 MB to flood the connection, but the upside that the key used to generate the low bits changes faster than it can be broken. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 11:13 PM, George Spelvinwrote: > Remembering that on "real" machines it's full SipHash, then I'd say that > 64-bit security + rekeying seems reasonable. 64-bit security for an RNG is not reasonable even with rekeying. No no no. Considering we already have a massive speed-up here with the secure version, there's zero reason to start weakening the security because we're trigger happy with our benchmarks. No no no. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v6 3/5] random: use SipHash in place of MD5
On Fri, Dec 16, 2016 at 1:45 PM, Jason A. Donenfeldwrote: > Hi Andy, > > On Fri, Dec 16, 2016 at 10:31 PM, Andy Lutomirski wrote: >> I think it would be nice to try to strenghen the PRNG construction. >> FWIW, I'm not an expert in PRNGs, and there's fairly extensive >> literature, but I can at least try. > > In an effort to keep this patchset as initially as uncontroversial as > possible, I kept the same same construction as before and just swapped > out slow MD5 for fast Siphash. Additionally, the function > documentation says that it isn't cryptographically secure. But in the > end I certainly agree with you; we should most definitely improve > things, and seeing the eyeballs now on this series, I think we now > might have a mandate to do so. > >> 1. A one-time leak of memory contents doesn't ruin security until >> reboot. This is especially value across suspend and/or hibernation. > > Ted and I were discussing this in another thread, and it sounds like > he wants the same thing. I'll add re-generation of the secret every > once in a while. Perhaps time-based makes more sense than > counter-based for rekeying frequency? Counter may be faster -- you don't need to read a timer. Lots of CPUs are surprisingly slow at timing. OTOH jiffies are fast. > >> 2. An attack with a low work factor (2^64?) shouldn't break the scheme >> until reboot. > > It won't. The key is 128-bits. Whoops, I thought the key was 64-bit... > >> This is effectively doing: >> >> output = H(prev_output, weak "entropy", per-boot secret); >> >> One unfortunately downside is that, if used in a context where an >> attacker can see a single output, the attacker learns the chaining >> value. If the attacker can guess the entropy, then, with 2^64 work, >> they learn the secret, and they can predict future outputs. > > No, the secret is 128-bits, which isn't feasibly guessable. The secret > also isn't part of the hash, but rather is the generator of the hash > function. A keyed hash (a PRF) is a bit of a different construction > than just hashing a secret value into a hash function. I was thinking in the random oracle model, in which case the whole function is just a PRF that takes a few input parameters, one of which is a key. > >> Second, change the mode so that an attacker doesn't learn so much >> internal state. For example: >> >> output = H(old_chain, entropy, secret); >> new_chain = old_chain + entropy + output; > > Happy to make this change, with making the chaining value additive > rather than a replacement. > > However, I'm not sure adding entropy to the new_chain makes a > different. That entropy is basically just the cycle count plus the > jiffies count. If an attacker can already guess them, then adding them > again to the chaining value doesn't really add much. Agreed. A simpler contruction would be: chaining++; output = H(chaining, secret); And this looks a whole lot like Ted's ChaCha20 construction. The benefit of my construction is that (in the random oracle model, assuming my intuition is right), if an attacker misses ~128 samples and entropy has at least one bit of independent min-entropy per sample, then the attacker needs ~2^128 work to brute-force the chaining value even fi the attacker knew both the original chaining value and the secret. --Andy -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 2:13 PM, George Spelvinwrote: >> What should we do with get_random_int() and get_random_long()? In >> some cases it's being used in performance sensitive areas, and where >> anti-DoS protection might be enough. In others, maybe not so much. > > This is tricky. The entire get_random_int() structure is an abuse of > the hash function and will need to be thoroughly rethought to convert > it to SipHash. Remember, SipHash's security goals are very different > from MD5, so there's no obvious way to do the conversion. > > (It's *documented* as "not cryptographically secure", but we know > where that goes.) > >> If we rekeyed the secret used by get_random_int() and >> get_random_long() frequently (say, every minute or every 5 minutes), >> would that be sufficient for current and future users of these >> interfaces? > > Remembering that on "real" machines it's full SipHash, then I'd say that > 64-bit security + rekeying seems reasonable. > > The question is, the idea has recently been floated to make hsiphash = > SipHash-1-3 on 64-bit machines. Is *that* okay? > > > The annoying thing about the currently proposed patch is that the *only* > chaining is the returned value. What I'd *like* to do is the same > pattern as we do with md5, and remember v[0..3] between invocations. > But there's no partial SipHash primitive; we only get one word back. > > Even > *chaining += ret = siphash_3u64(...) > > would be an improvement. This is almost exactly what I suggested in my email on the other thread from a few seconds ago :) --Andy -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
> What should we do with get_random_int() and get_random_long()? In > some cases it's being used in performance sensitive areas, and where > anti-DoS protection might be enough. In others, maybe not so much. This is tricky. The entire get_random_int() structure is an abuse of the hash function and will need to be thoroughly rethought to convert it to SipHash. Remember, SipHash's security goals are very different from MD5, so there's no obvious way to do the conversion. (It's *documented* as "not cryptographically secure", but we know where that goes.) > If we rekeyed the secret used by get_random_int() and > get_random_long() frequently (say, every minute or every 5 minutes), > would that be sufficient for current and future users of these > interfaces? Remembering that on "real" machines it's full SipHash, then I'd say that 64-bit security + rekeying seems reasonable. The question is, the idea has recently been floated to make hsiphash = SipHash-1-3 on 64-bit machines. Is *that* okay? The annoying thing about the currently proposed patch is that the *only* chaining is the returned value. What I'd *like* to do is the same pattern as we do with md5, and remember v[0..3] between invocations. But there's no partial SipHash primitive; we only get one word back. Even *chaining += ret = siphash_3u64(...) would be an improvement. Although we could do something like c0 = chaining[0]; chaining[0] = c1 = chaining[1]; ret = hsiphash(c0, c1, ...) chaining[1] = c0 + ret; -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v6 3/5] random: use SipHash in place of MD5
Hi Andy, Ted, I've made the requested changes. Keys now rotate and are per-CPU based. The chaining value is now additive instead of replacing. DavidL suggested I lower the velocity of `git-send-email` triggers, so if you'd like to take a look at this before I post v7, you can follow along at my git tree here: https://git.zx2c4.com/linux-dev/log/?h=siphash Choose the commit entitled "random: use SipHash in place of MD5" Thanks, Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v6 3/5] random: use SipHash in place of MD5
Hi Andy, On Fri, Dec 16, 2016 at 10:31 PM, Andy Lutomirskiwrote: > I think it would be nice to try to strenghen the PRNG construction. > FWIW, I'm not an expert in PRNGs, and there's fairly extensive > literature, but I can at least try. In an effort to keep this patchset as initially as uncontroversial as possible, I kept the same same construction as before and just swapped out slow MD5 for fast Siphash. Additionally, the function documentation says that it isn't cryptographically secure. But in the end I certainly agree with you; we should most definitely improve things, and seeing the eyeballs now on this series, I think we now might have a mandate to do so. > 1. A one-time leak of memory contents doesn't ruin security until > reboot. This is especially value across suspend and/or hibernation. Ted and I were discussing this in another thread, and it sounds like he wants the same thing. I'll add re-generation of the secret every once in a while. Perhaps time-based makes more sense than counter-based for rekeying frequency? > 2. An attack with a low work factor (2^64?) shouldn't break the scheme > until reboot. It won't. The key is 128-bits. > This is effectively doing: > > output = H(prev_output, weak "entropy", per-boot secret); > > One unfortunately downside is that, if used in a context where an > attacker can see a single output, the attacker learns the chaining > value. If the attacker can guess the entropy, then, with 2^64 work, > they learn the secret, and they can predict future outputs. No, the secret is 128-bits, which isn't feasibly guessable. The secret also isn't part of the hash, but rather is the generator of the hash function. A keyed hash (a PRF) is a bit of a different construction than just hashing a secret value into a hash function. > Second, change the mode so that an attacker doesn't learn so much > internal state. For example: > > output = H(old_chain, entropy, secret); > new_chain = old_chain + entropy + output; Happy to make this change, with making the chaining value additive rather than a replacement. However, I'm not sure adding entropy to the new_chain makes a different. That entropy is basically just the cycle count plus the jiffies count. If an attacker can already guess them, then adding them again to the chaining value doesn't really add much. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi George, On Fri, Dec 16, 2016 at 10:25 PM, George Spelvinwrote: > But yes, the sequence number is supposed to be (random base) + (timestamp). > In the old days before Canter & Siegel when the internet was a nice place, > people just used a counter that started at boot time. > > But then someone observed that I can start a connection to host X, > see the sequence number it gives back to me, and thereby learn the > seauence number it's using on its connections to host Y. > > And I can use that to inject forged data into an X-to-Y connection, > without ever seeing a single byte of the traffic! (If I *can* observe > the traffic, of course, none of this makes the slightest difference.) > > So the random base was made a keyed hash of the endpoint identifiers. > (Practically only the hosts matter, but generally the ports are thrown > in for good measure.) That way, the ISN that host X sends to me > tells me nothing about the ISN it's using to talk to host Y. Now the > only way to inject forged data into the X-to-Y connection is to > send 2^32 bytes, which is a little less practical. Oh, okay, that is exactly what I thought was going on. I just thought you were implying that jiffies could be moved inside the hash, which then confused my understanding of how things should be. In any case, thanks for the explanation. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v6 3/5] random: use SipHash in place of MD5
On Thu, Dec 15, 2016 at 7:03 PM, Jason A. Donenfeldwrote: > -static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash) > - __aligned(sizeof(unsigned long)); > +static DEFINE_PER_CPU(u64, get_random_int_chaining); > [...] > unsigned long get_random_long(void) > { > - __u32 *hash; > unsigned long ret; > + u64 *chaining; > > if (arch_get_random_long()) > return ret; > > - hash = get_cpu_var(get_random_int_hash); > - > - hash[0] += current->pid + jiffies + random_get_entropy(); > - md5_transform(hash, random_int_secret); > - ret = *(unsigned long *)hash; > - put_cpu_var(get_random_int_hash); > - > + chaining = _cpu_var(get_random_int_chaining); > + ret = *chaining = siphash_3u64(*chaining, jiffies, > random_get_entropy() + > + current->pid, random_int_secret); > + put_cpu_var(get_random_int_chaining); > return ret; > } I think it would be nice to try to strenghen the PRNG construction. FWIW, I'm not an expert in PRNGs, and there's fairly extensive literature, but I can at least try. Here are some properties I'd like: 1. A one-time leak of memory contents doesn't ruin security until reboot. This is especially value across suspend and/or hibernation. 2. An attack with a low work factor (2^64?) shouldn't break the scheme until reboot. This is effectively doing: output = H(prev_output, weak "entropy", per-boot secret); One unfortunately downside is that, if used in a context where an attacker can see a single output, the attacker learns the chaining value. If the attacker can guess the entropy, then, with 2^64 work, they learn the secret, and they can predict future outputs. I would advocate adding two types of improvements. First, re-seed it every now and then (every 128 calls?) by just replacing both the chaining value and the percpu secret with fresh CSPRNG output. Second, change the mode so that an attacker doesn't learn so much internal state. For example: output = H(old_chain, entropy, secret); new_chain = old_chain + entropy + output; This increases the effort needed to brute-force the internal state from 2^64 to 2^128 (barring any weaknesses in the scheme). Also, can we not call this get_random_int()? get_random_int() sounds too much like get_random_bytes(), and the latter is intended to be a real CSPRNG. Can we call it get_weak_random_int() or similar? --Andy -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Jason A. Donenfeld wrote: > I saw that jiffies addition in there and was wondering what it was all > about. It's currently added _after_ the siphash input, not before, to > keep with how the old algorithm worked. I'm not sure if this is > correct or if there's something wrong with that, as I haven't studied > how it works. If that jiffies should be part of the siphash input and > not added to the result, please tell me. Otherwise I'll keep things > how they are to avoid breaking something that seems to be working. Oh, geez, I didn't realize you didn't understand this code. Full details at https://en.wikipedia.org/wiki/TCP_sequence_prediction_attack But yes, the sequence number is supposed to be (random base) + (timestamp). In the old days before Canter & Siegel when the internet was a nice place, people just used a counter that started at boot time. But then someone observed that I can start a connection to host X, see the sequence number it gives back to me, and thereby learn the seauence number it's using on its connections to host Y. And I can use that to inject forged data into an X-to-Y connection, without ever seeing a single byte of the traffic! (If I *can* observe the traffic, of course, none of this makes the slightest difference.) So the random base was made a keyed hash of the endpoint identifiers. (Practically only the hosts matter, but generally the ports are thrown in for good measure.) That way, the ISN that host X sends to me tells me nothing about the ISN it's using to talk to host Y. Now the only way to inject forged data into the X-to-Y connection is to send 2^32 bytes, which is a little less practical. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016, at 22:01, Jason A. Donenfeld wrote: > Yes, on x86-64. But on i386 chacha20 incurs nearly the same kind of > slowdown as siphash, so I expect the comparison to be more or less > equal. There's another thing I really didn't like about your chacha20 > approach which is that it uses the /dev/urandom pool, which means > various things need to kick in in the background to refill this. > Additionally, having to refill the buffered chacha output every 32 or > so longs isn't nice. These things together make for inconsistent and > hard to understand general operating system performance, because > get_random_long is called at every process startup for ASLR. So, in > the end, I believe there's another reason for going with the siphash > approach: deterministic performance. *Hust*, so from where do you generate your key for siphash if called early from ASLR? Bye, Hannes -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi Daniel, On Fri, Dec 16, 2016 at 9:44 PM, Daniel Micaywrote: > On Fri, 2016-12-16 at 11:47 -0800, Tom Herbert wrote: >> >> That's about 3x of jhash speed (7 nsecs). So that might closer >> to a more palatable replacement for jhash. Do we lose any security >> advantages with halfsiphash? > > Have you tested a lower round SipHash? Probably best to stick with the > usual construction for non-DoS mitigation, but why not try SipHash 1-3, > 1-2, etc. for DoS mitigation? > > Rust and Swift both went with SipHash 1-3 for hash tables. Maybe not a bad idea. SipHash2-4 for MD5 replacement, as we've done so far. This is when we actually want things to be secure (and fast). And then HalfSipHash1-3 for certain jhash replacements. This is for when we're talking only about DoS or sort of just joking about security, and want things to be very competitive with jhash. (Of course for 64-bit we'd use SipHash1-3 instead of HalfSipHash for the speedup.) I need to think on this a bit more, but preliminarily, I guess this would be maybe okay... George, JP - what do you think? Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi Ted, On Fri, Dec 16, 2016 at 9:43 PM, Theodore Ts'owrote: > What should we do with get_random_int() and get_random_long()? In > some cases it's being used in performance sensitive areas, and where > anti-DoS protection might be enough. In others, maybe not so much. > > If we rekeyed the secret used by get_random_int() and > get_random_long() frequently (say, every minute or every 5 minutes), > would that be sufficient for current and future users of these > interfaces? get_random_int() and get_random_long() should quite clearly use SipHash with its secure 128-bit key and not HalfSipHash with its 64-bit key. HalfSipHash is absolutely insufficient for this use case. Remember, we're already an order of magnitude or more faster than md5... With regard to periodic rekeying... since the secret is 128-bits, I believe this is likely sufficient for _not_ rekeying. There's also the chaining variable, to tie together invocations of the function. If you'd prefer, instead of the chaining variable, we could use some siphash output to mutate the original key, but I don't think this approach is actually better and might introduce vulnerabilities. In my opinion chaining+128bitkey is sufficient. On the other hand, rekeying every X minutes is 3 or 4 lines of code. If you want (just say so), I'll add this to my next revision. You asked about the security requirements of these functions. The comment says they're not cryptographically secure. And right now with MD5 they're not. So the expectations are pretty low. Moving to siphash adds some cryptographic security, certainly. Moving to siphash plus rekeying adds a bit more. Of course, on recent x86, RDRAND is used instead, so the cryptographic strength then depends on the thickness of your tinfoil hat. So probably we shouldn't change what we advertise these functions provide, even though we're certainly improving them performance-wise and security-wise. > P.S. I'll note that my performance figures when testing changes to > get_random_int() were done on a 32-bit x86; Jason, I'm guessing your > figures were using a 64-bit x86 system?. I haven't tried 32-bit ARM > or smaller CPU's (e.g., mips, et. al.) that might be more likely to be > used on IoT devices, but I'm worried about those too, of course. Yes, on x86-64. But on i386 chacha20 incurs nearly the same kind of slowdown as siphash, so I expect the comparison to be more or less equal. There's another thing I really didn't like about your chacha20 approach which is that it uses the /dev/urandom pool, which means various things need to kick in in the background to refill this. Additionally, having to refill the buffered chacha output every 32 or so longs isn't nice. These things together make for inconsistent and hard to understand general operating system performance, because get_random_long is called at every process startup for ASLR. So, in the end, I believe there's another reason for going with the siphash approach: deterministic performance. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 12:41 PM, George Spelvinwrote: > Tom Herbert wrote: >> Tested this. Distribution and avalanche effect are still good. Speed >> wise I see about a 33% improvement over siphash (20 nsecs/op versus 32 >> nsecs). That's about 3x of jhash speed (7 nsecs). So that might closer >> to a more palatable replacement for jhash. Do we lose any security >> advantages with halfsiphash? > > What are you testing on? And what input size? And does "33% improvement" > mean 4/3 the rate and 3/4 the time? Or 2/3 the time and 3/2 the rate? > Sorry, that is over an IPv4 tuple. Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz. Recoded the function I was using to look like more like 64 bit version and yes it is indeed slower. > These are very odd results. On a 64-bit machine, SipHash should be the > same speed per round, and faster because it hashes more data per round. > (Unless you're hitting some unexpected cache/decode effect due to REX > prefixes.) > > On a 32-bit machine (other than ARM, where your results might make sense, > or maybe if you're hashing large amounts of data), the difference should > be larger. > > And yes, there is a *significant* security loss. SipHash is 128 bits > ("don't worry about it"). hsiphash is 64 bits, which is known breakable > ("worry about it"), so we have to do a careful analysis of the cost of > a successful attack. > > As mentioned in the e-mails that just flew by, hsiphash is intended > *only* for 32-bit machines which bog down on full SipHash. On all 64-bit > machines, it will be implemented as an alias for SipHash and the security > concerns will Just Go Away. > > The place where hsiphash is expected to make a big difference is 32-bit > x86. If you only see 33% difference with "gcc -m32", I'm going to be > very confused. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 9:17 PM, George Spelvinwrote: > My (speaking enerally; I should walk through every hash table you've > converted) opinion is that: > > - Hash tables, even network-facing ones, can all use hsiphash as long > as an attacker can only see collisions, i.e. ((H(x) ^ H(y)) & bits) == > 0, and the consequences of a successful attack is only more collisions > (timing). While the attack is only 2x the cost (two hashes rather than > one to test a key), the knowledge of the collision is statistical, > especially for network attackers, which raises the cost of guessing > beyond an even more brute-force attack. > - When the hash value directly visible (e.g. included in a network > packet), full SipHash should be the default. > - Syncookies *could* use hsiphash, especially as there are > two keys in there. Not sure if we need the performance. > - For TCP ISNs, I'd prefer to use full SipHash. I know this is > a very hot path, and if that's a performance bottleneck, > we can work harder on it. > > In particular, TCP ISNs *used* to rotate the key periodically, > limiting the time available to an attacker to perform an > attack before the secret goes stale and is useless. commit > 6e5714eaf77d79ae1c8b47e3e040ff5411b717ec upgraded to md5 and dropped > the key rotation. While I generally agree with this analysis for the most part, I do think we should use SipHash and not HalfSipHash for syncookies. Although the security risk is lower than with sequence numbers, it previously used full MD5 for this, which means performance is not generally a bottleneck and we'll get massive speedups no matter what, whether using SipHash or HalfSipHash. In addition, using SipHash means that the 128-bit key gives a larger margin and can be safe longterm. So, I think we should err on the side of caution and stick with SipHash in all cases in which we're upgrading from MD5. In other words, only current jhash users should be potentially eligible for hsiphash. > Current code uses a 64 ns tick for the ISN, so it counts 2^24 per second. > (32 bits wraps every 4.6 minutes.) A 4-bit counter and 28-bit hash > (or even 3+29) would work as long as the key is regenerated no more > than once per minute. (Just using the 4.6-minute ISN wrap time is the > obvious simple implementation.) > > (Of course, I defer to DaveM's judgement on all network-related issues.) I saw that jiffies addition in there and was wondering what it was all about. It's currently added _after_ the siphash input, not before, to keep with how the old algorithm worked. I'm not sure if this is correct or if there's something wrong with that, as I haven't studied how it works. If that jiffies should be part of the siphash input and not added to the result, please tell me. Otherwise I'll keep things how they are to avoid breaking something that seems to be working. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [kernel-hardening] Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, 2016-12-16 at 11:47 -0800, Tom Herbert wrote: > > That's about 3x of jhash speed (7 nsecs). So that might closer > to a more palatable replacement for jhash. Do we lose any security > advantages with halfsiphash? Have you tested a lower round SipHash? Probably best to stick with the usual construction for non-DoS mitigation, but why not try SipHash 1-3, 1-2, etc. for DoS mitigation? Rust and Swift both went with SipHash 1-3 for hash tables. signature.asc Description: This is a digitally signed message part
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 03:17:39PM -0500, George Spelvin wrote: > > That's a nice analysis. Might one conclude from that that hsiphash is > > not useful for our purposes? Or does it still remain useful for > > network facing code? > > I think for attacks where the threat is a DoS, it's usable. The point > is you only have to raise the cost to equal that of a packet flood. > (Just like in electronic warfare, the best you can possibly do is force > the enemy to use broadband jamming.) > > Hash collision attacks just aren't that powerful. The original PoC > was against an application that implemented a hard limit on hash chain > length as a DoS defense, which the attack then exploited to turn it into > a hard DoS. What should we do with get_random_int() and get_random_long()? In some cases it's being used in performance sensitive areas, and where anti-DoS protection might be enough. In others, maybe not so much. If we rekeyed the secret used by get_random_int() and get_random_long() frequently (say, every minute or every 5 minutes), would that be sufficient for current and future users of these interfaces? - Ted P.S. I'll note that my performance figures when testing changes to get_random_int() were done on a 32-bit x86; Jason, I'm guessing your figures were using a 64-bit x86 system?. I haven't tried 32-bit ARM or smaller CPU's (e.g., mips, et. al.) that might be more likely to be used on IoT devices, but I'm worried about those too, of course. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 9:41 PM, George Spelvinwrote: > What are you testing on? And what input size? And does "33% improvement" > mean 4/3 the rate and 3/4 the time? Or 2/3 the time and 3/2 the rate? How that I've published my hsiphash implementation to my tree, it should be possible to conduct the tests back to back with nearly identical implementation strategies, to remove a potential source of error. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Tom Herbert wrote: > Tested this. Distribution and avalanche effect are still good. Speed > wise I see about a 33% improvement over siphash (20 nsecs/op versus 32 > nsecs). That's about 3x of jhash speed (7 nsecs). So that might closer > to a more palatable replacement for jhash. Do we lose any security > advantages with halfsiphash? What are you testing on? And what input size? And does "33% improvement" mean 4/3 the rate and 3/4 the time? Or 2/3 the time and 3/2 the rate? These are very odd results. On a 64-bit machine, SipHash should be the same speed per round, and faster because it hashes more data per round. (Unless you're hitting some unexpected cache/decode effect due to REX prefixes.) On a 32-bit machine (other than ARM, where your results might make sense, or maybe if you're hashing large amounts of data), the difference should be larger. And yes, there is a *significant* security loss. SipHash is 128 bits ("don't worry about it"). hsiphash is 64 bits, which is known breakable ("worry about it"), so we have to do a careful analysis of the cost of a successful attack. As mentioned in the e-mails that just flew by, hsiphash is intended *only* for 32-bit machines which bog down on full SipHash. On all 64-bit machines, it will be implemented as an alias for SipHash and the security concerns will Just Go Away. The place where hsiphash is expected to make a big difference is 32-bit x86. If you only see 33% difference with "gcc -m32", I'm going to be very confused. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi JP, On Fri, Dec 16, 2016 at 2:22 PM, Jean-Philippe Aumassonwrote: > It needs some basic security review, which I'll try do next week (check for > security margin, optimality of rotation counts, etc.). But after a lot of > experience with this kind of construction (BLAKE, SipHash, NORX), I'm > confident it will be safe as it is. I've implemented it in my siphash kernel branch: https://git.zx2c4.com/linux-dev/log/?h=siphash It's the commit that has "HalfSipHash" in the log message. As the structure is nearly identical to SipHash, there wasn't a lot to change, and so the same implementation strategy exists for each. When you've finished your security review and feel good about it, some test vectors using the same formula (key={0x03020100, 07060504}, input={0x0, 0x1, 0x2, 0x3...}, output=test_vectors) would be nice for verification. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
>> On a 64-bit machine, 64-bit SipHash is *always* faster than 32-bit, and >> should be used always. Don't even compile the 32-bit code, to prevent >> anyone accidentally using it, and make hsiphash an alias for siphash. > Fascinating! Okay. So I'll alias hsiphash to siphash on 64-bit then. I > like this arrangement. This is a basic assumption I make in the security analysis below: on most machines, it's 128-bit-key SipHash everywhere and we can consider security solved. Our analysis *only* has to consider 32-bit machines. My big concern is home routers, with IoT appliances coming second. The routers have severe hardware cost constraints (so limited CPU power), but see a lot of traffic and need to process (NAT) it. > That's a nice analysis. Might one conclude from that that hsiphash is > not useful for our purposes? Or does it still remain useful for > network facing code? I think for attacks where the threat is a DoS, it's usable. The point is you only have to raise the cost to equal that of a packet flood. (Just like in electronic warfare, the best you can possibly do is force the enemy to use broadband jamming.) Hash collision attacks just aren't that powerful. The original PoC was against an application that implemented a hard limit on hash chain length as a DoS defense, which the attack then exploited to turn it into a hard DoS. >> Let me consider your second example above, "secure against local users". >> I should dig through your patchset and find the details, but what exactly >> are the consequences of such an attack? Hasn't a local user already >> got much better ways to DoS the system? > For example, an unpriv'd user putting lots of entries in one hash > bucket for a shared resource that's used by root, like filesystems or > other lookup tables. If he can cause root to use more of root's cpu > schedule budget than otherwise in a directed way, then that's a bad > DoS. This issue was recently discussed when we redesigned the dcache hash. Even a successful attack doesn't slow things down all *that* much. Before you overkill every hash table in the kernel, think about whether it's a bigger problem than the dcache. (Hint: it's probably not.) There's no point armor-plating the side door when the front door was just upgraded from screen to wood. >> These days, 32-bit CPUs are for embedded applications: network appliances, >> TVs, etc. That means basically single-user. Even phones are 64 bit. >> Is this really a threat that needs to be defended against? > I interpret this to indicate all the more reason to alias hsiphash to > siphash on 64-bit, and then the problem space collapses in a clear > way. Yes, exactly. > Right. Hence the need for always using full siphash and not hsiphash > for sequence numbers, per my earlier email to David. > >> I wish we could get away with 64-bit security, but given that the >> modern internet involves attacks from NSA/Spetssvyaz/3PLA, I agree >> it's just not enough. > > I take this comment to be relavent for the sequence number case. Yes. > For hashtables and hashtable flooding, is it still your opinion that > we will benefit from hsiphash? Or is this final conclusion a rejection > of hsiphash for that too? We're talking about two different use cases, > and your email kind of interleaved both into your analysis, so I'm not > certain so to precisely what your conclusion is for each use case. Can > you clear up the ambiguity? My (speaking enerally; I should walk through every hash table you've converted) opinion is that: - Hash tables, even network-facing ones, can all use hsiphash as long as an attacker can only see collisions, i.e. ((H(x) ^ H(y)) & bits) == 0, and the consequences of a successful attack is only more collisions (timing). While the attack is only 2x the cost (two hashes rather than one to test a key), the knowledge of the collision is statistical, especially for network attackers, which raises the cost of guessing beyond an even more brute-force attack. - When the hash value directly visible (e.g. included in a network packet), full SipHash should be the default. - Syncookies *could* use hsiphash, especially as there are two keys in there. Not sure if we need the performance. - For TCP ISNs, I'd prefer to use full SipHash. I know this is a very hot path, and if that's a performance bottleneck, we can work harder on it. In particular, TCP ISNs *used* to rotate the key periodically, limiting the time available to an attacker to perform an attack before the secret goes stale and is useless. commit 6e5714eaf77d79ae1c8b47e3e040ff5411b717ec upgraded to md5 and dropped the key rotation. If 2x hsiphash is faster than siphash, we could use a double-hashing system like syncookies. One 32-bit hash with a permanent key, summed with a k-bit counter and a (32-k)-bit hash, where the key is rotated (and the counter incremented) periodically. The requirement is that the increment rate of the counter hash doesn't
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
On Fri, Dec 16, 2016 at 4:39 AM, Jason A. Donenfeldwrote: > Hey JP, > > On Fri, Dec 16, 2016 at 9:08 AM, Jean-Philippe Aumasson > wrote: >> Here's a tentative HalfSipHash: >> https://github.com/veorq/SipHash/blob/halfsiphash/halfsiphash.c >> >> Haven't computed the cycle count nor measured its speed. > Tested this. Distribution and avalanche effect are still good. Speed wise I see about a 33% improvement over siphash (20 nsecs/op versus 32 nsecs). That's about 3x of jhash speed (7 nsecs). So that might closer to a more palatable replacement for jhash. Do we lose any security advantages with halfsiphash? Tom > This is incredible. Really. Wow! > > I'll integrate this into my patchset and will write up some > documentation about when one should be used over the other. > > Thanks again. Quite exciting. > > Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi George, On Fri, Dec 16, 2016 at 6:36 PM, George Spelvinwrote: > A 128-bit output option was added to SipHash after the initial publication; > this is just the equivalent in 32-bit. > Personally, I'd put in a comment saying that "there's a 64-bit output > variant that's not implemented" and punt until someone find a need. That's a good way to think about it. Okay, I'll do precisely that. > On a 64-bit machine, 64-bit SipHash is *always* faster than 32-bit, and > should be used always. Don't even compile the 32-bit code, to prevent > anyone accidentally using it, and make hsiphash an alias for siphash. Fascinating! Okay. So I'll alias hsiphash to siphash on 64-bit then. I like this arrangement. > Fortunately, the cost of brute-forcing hash functions can be fairly > exactly quantified, thanks to bitcoin miners. It currently takes 2^70 > hashes to create one bitcoin block, worth 25 bitcoins ($19,500). Thus, > 2^63 hashes cost $152. > > Now, there are two factors that must be considered: > - That's a very very "wholesale" rate. That's assuming you're doing > large numbers of these and can put in the up-front effort designing > silicon ASICs to do the attack. > - That's for a more difficult hash (double sha-256) than SipHash. > That's a constant fator, but a pretty significant one. If the wholesale > assumption holds, that might bring the cost down another 6 or 7 bits, > to $1-2 per break. > > If you're not the NSA and limited to general-purpose silicon, let's > assume a state of the art GPU (Radeon HD 7970; AMD GPUs seem do to better > than nVidia). The bitcoin mining rate for those is about 700M/second, > 29.4 bits. So 63 bits is 152502 GPU-days, divided by some factor > to account for SipHash's high speed compared to two rounds of SHA-2. > Call it 1000 GPU-days. > > It's very doable, but also very non-trivial. The question is, wouldn't > it be cheaper and easier just to do a brute-force flooding DDoS? > > (This is why I wish the key size could be tweaked up to 80 bits. > That would take all these numbers out of the reasonable range.) That's a nice analysis. Might one conclude from that that hsiphash is not useful for our purposes? Or does it still remain useful for network facing code? > Let me consider your second example above, "secure against local users". > I should dig through your patchset and find the details, but what exactly > are the consequences of such an attack? Hasn't a local user already > got much better ways to DoS the system? For example, an unpriv'd user putting lots of entries in one hash bucket for a shared resource that's used by root, like filesystems or other lookup tables. If he can cause root to use more of root's cpu schedule budget than otherwise in a directed way, then that's a bad DoS. > The thing to remember is that we're worried only about the combination > of a *new* Linux kernel (new build or under active maintenance) and a > 32-bit host. You'd be hard-pressed to find a *single* machine fitting > that description which is hosting multiple users or VMs and is not 64-bit. > > These days, 32-bit CPUs are for embedded applications: network appliances, > TVs, etc. That means basically single-user. Even phones are 64 bit. > Is this really a threat that needs to be defended against? I interpret this to indicate all the more reason to alias hsiphash to siphash on 64-bit, and then the problem space collapses in a clear way. > For your first case, network applications, the additional security > is definitely attractive. Syncookies are only a DoS, but sequence > numbers are a real security issue; they can let you inject data into a > TCP connection. > With sequence numbers, large amounts (32 bits) the hash output is > directly observable. Right. Hence the need for always using full siphash and not hsiphash for sequence numbers, per my earlier email to David. > > I wish we could get away with 64-bit security, but given that the > modern internet involves attacks from NSA/Spetssvyaz/3PLA, I agree > it's just not enough. I take this comment to be relavent for the sequence number case. For hashtables and hashtable flooding, is it still your opinion that we will benefit from hsiphash? Or is this final conclusion a rejection of hsiphash for that too? We're talking about two different use cases, and your email kind of interleaved both into your analysis, so I'm not certain so to precisely what your conclusion is for each use case. Can you clear up the ambiguity? Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
> It appears that hsiphash can produce either 32-bit output or 64-bit > output, with the output length parameter as part of the hash algorithm > in there. When I code this for my kernel patchset, I very likely will > only implement one output length size. Right now I'm leaning toward > 32-bit. A 128-bit output option was added to SipHash after the initial publication; this is just the equivalent in 32-bit. > - Is this a reasonable choice? Yes. > - Are there reasons why hsiphash with 64-bit output would be > reasonable? Or will we be fine sticking with 32-bit output only? Personally, I'd put in a comment saying that "there's a 64-bit output variant that's not implemented" and punt until someone find a need. > With both hsiphash and siphash, the division of usage will probably become: > - Use 64-bit output 128-bit key siphash for keyed RNG-like things, > such as syncookies and sequence numbers > - Use 64-bit output 128-bit key siphash for hashtables that must > absolutely be secure to an extremely high bandwidth attacker, such as > userspace directly DoSing a kernel hashtable > - Use 32-bit output 64-bit key hsiphash for quick hashtable functions > that still must be secure but do not require as large of a security > margin. On a 64-bit machine, 64-bit SipHash is *always* faster than 32-bit, and should be used always. Don't even compile the 32-bit code, to prevent anyone accidentally using it, and make hsiphash an alias for siphash. On a 32-bit machine, it's a much trickier case. I'd be tempted to use the 32-bit code always, but it needs examination. Fortunately, the cost of brute-forcing hash functions can be fairly exactly quantified, thanks to bitcoin miners. It currently takes 2^70 hashes to create one bitcoin block, worth 25 bitcoins ($19,500). Thus, 2^63 hashes cost $152. Now, there are two factors that must be considered: - That's a very very "wholesale" rate. That's assuming you're doing large numbers of these and can put in the up-front effort designing silicon ASICs to do the attack. - That's for a more difficult hash (double sha-256) than SipHash. That's a constant fator, but a pretty significant one. If the wholesale assumption holds, that might bring the cost down another 6 or 7 bits, to $1-2 per break. If you're not the NSA and limited to general-purpose silicon, let's assume a state of the art GPU (Radeon HD 7970; AMD GPUs seem do to better than nVidia). The bitcoin mining rate for those is about 700M/second, 29.4 bits. So 63 bits is 152502 GPU-days, divided by some factor to account for SipHash's high speed compared to two rounds of SHA-2. Call it 1000 GPU-days. It's very doable, but also very non-trivial. The question is, wouldn't it be cheaper and easier just to do a brute-force flooding DDoS? (This is why I wish the key size could be tweaked up to 80 bits. That would take all these numbers out of the reasonable range.) Let me consider your second example above, "secure against local users". I should dig through your patchset and find the details, but what exactly are the consequences of such an attack? Hasn't a local user already got much better ways to DoS the system? The thing to remember is that we're worried only about the combination of a *new* Linux kernel (new build or under active maintenance) and a 32-bit host. You'd be hard-pressed to find a *single* machine fitting that description which is hosting multiple users or VMs and is not 64-bit. These days, 32-bit CPUs are for embedded applications: network appliances, TVs, etc. That means basically single-user. Even phones are 64 bit. Is this really a threat that needs to be defended against? For your first case, network applications, the additional security is definitely attractive. Syncookies are only a DoS, but sequence numbers are a real security issue; they can let you inject data into a TCP connection. Hash tables are much harder to attack. The information you get back from timing probes is statistical, and thus testing a key is more expensive. With sequence numbers, large amounts (32 bits) the hash output is directly observable. I wish we could get away with 64-bit security, but given that the modern internet involves attacks from NSA/Spetssvyaz/3PLA, I agree it's just not enough. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi David, On Fri, Dec 16, 2016 at 6:06 PM, David Laightwrote: > A 32bit hash would also remove all the issues about the alignment > of IP addresses (etc) on 64bit systems. The current replacements of md5_transform with siphash in the v6 patch series will continue to use the original siphash, since the 128-bit key is rather important for these kinds of secrets. Additionally, 64-bit siphash is already faster than the md5_transform that it replaces. So the alignment concerns (now, non-issues; problems have been solved, I believe) still remain. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
RE: [PATCH v5 1/4] siphash: add cryptographically secure PRF
From: George Spelvin > Sent: 15 December 2016 23:29 > > If a halved version of SipHash can bring significant performance boost > > (with 32b words instead of 64b words) with an acceptable security level > > (64-bit enough?) then we may design such a version. > > I was thinking if the key could be pushed to 80 bits, that would be nice, > but honestly 64 bits is fine. This is DoS protection, and while it's > possible to brute-force a 64 bit secret, there are more effective (DDoS) > attacks possible for the same cost. A 32bit hash would also remove all the issues about the alignment of IP addresses (etc) on 64bit systems. > (I'd suggest a name of "HalfSipHash" to convey the reduced security > effectively.) > > > Regarding output size, are 64 bits sufficient? > > As a replacement for jhash, 32 bits are sufficient. It's for > indexing an in-memory hash table on a 32-bit machine. It is also worth remembering that if the intent is to generate a hash table index (not a unique fingerprint) you will always get collisions on the final value. Randomness could still give overlong hash chains - which might still need rehashing with a different key. David -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 3/4] secure_seq: use SipHash in place of MD5
Hi David, On Fri, Dec 16, 2016 at 10:59 AM, David Laightwrote: > You are still putting over-aligned data on stack. > You only need to align it to the alignment of u64 (not the size of u64). > If an on-stack item has a stronger alignment requirement than the stack > the gcc has to generate two stack frames for the function. Yesterday, folks were saying that sometimes 32-bit platforms need 8-byte alignment for certain 64-bit operations, so I shouldn't fall back to 4-byte alignment there. But actually, looking at this more closely, I can just make SIPHASH_ALIGNMENT == __alignof__(u64), which will take care of all possible concerns, since gcc knows best which platforms need what alignment. Thanks for making this clear to me with "the alignment of u64 (not the size of u64)". > Oh - and wait a bit longer between revisions. Okay. We can be turtles. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hi JP & George, My function names: - SipHash -> siphash - HalfSipHash -> hsiphash It appears that hsiphash can produce either 32-bit output or 64-bit output, with the output length parameter as part of the hash algorithm in there. When I code this for my kernel patchset, I very likely will only implement one output length size. Right now I'm leaning toward 32-bit. Questions: - Is this a reasonable choice? - When hsiphash is desired due to its faster speed, are there any circumstances in which producing a 64-bit output would actually be useful? Namely, are there any hashtables that could benefit from a 64-bit functions? - Are there reasons why hsiphash with 64-bit output would be reasonable? Or will we be fine sticking with 32-bit output only? With both hsiphash and siphash, the division of usage will probably become: - Use 64-bit output 128-bit key siphash for keyed RNG-like things, such as syncookies and sequence numbers - Use 64-bit output 128-bit key siphash for hashtables that must absolutely be secure to an extremely high bandwidth attacker, such as userspace directly DoSing a kernel hashtable - Use 32-bit output 64-bit key hsiphash for quick hashtable functions that still must be secure but do not require as large of a security margin Sound good? Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
RE: [PATCH v5 2/4] siphash: add Nu{32,64} helpers
Jason A. Donenfeld wrote: > Isn't that equivalent to: > v0 = key[0]; > v1 = key[1]; > v2 = key[0] ^ (0x736f6d6570736575ULL ^ 0x646f72616e646f6dULL); > v3 = key[1] ^ (0x646f72616e646f6dULL ^ 0x7465646279746573ULL); (Pre-XORing key[] with the first two constants which, if the constants are random in the first place, can be a no-op.) Other than the typo in the v2 line, yes. If they key is non-public, then you can xor an arbitrary constant in to both halves to slightly speed up the startup. (Nits: There's a typo in the v2 line, you don't need to parenthesize associative operators like xor, and the "ull" suffix is redundant here.) > Those constants also look like ASCII strings. They are. The ASCII is "somepseudorandomlygeneratedbytes". > What cryptographic analysis has been done on the values? They're "nothing up my sleeve numbers". They're arbitrary numbers, and almost any other values would do exactly as well. The main properties are: 1) They're different (particulatly v0 != v2 and v1 != v3), and 2) Neither they, nor their xor, is rotationally symmetric like 0x. (Because SipHash is mostly rotationally symmetric, broken only by the interruption of the carry chain at the msbit, it helps slightly to break this up at the beginning.) Those exact values only matter for portability. If you don't need anyone else to be able to compute matching outputs, then you could use any other convenient constants (like the MD5 round constants). -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: algif for compression?
> > The compression interface is currently in a state of flux. We > should make it settle down first before exporting it to user-space. > > For a start it would be good to actually switch IPsec/IPcomp over > to the new compression interface. Thanks Herbert. Are there timelines or ongoing efforts for moving IPcomp/Ipsec to use acomp? Or any proposals that have been or need to be taken up in this regard. Thanks, Abed -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
Am Freitag, 16. Dezember 2016, 20:31:27 CET schrieb Herbert Xu: Hi Herbert, > > > > You are right, this will introduce a memleak. But with the immediate > > freeing of sreq->tsg in the current code, the AIO interface cannot > > support multiple IOCBs. > > > > Thus, the entire memory handling in the AIO case seems broken. > > Right, but can we please fix it properly? For example, you could > save the original tsg in a new field and free that when you are > done. Absolutely, I concur. I will work on that. Ciao Stephan -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 1/4] siphash: add cryptographically secure PRF
Hey JP, On Fri, Dec 16, 2016 at 9:08 AM, Jean-Philippe Aumassonwrote: > Here's a tentative HalfSipHash: > https://github.com/veorq/SipHash/blob/halfsiphash/halfsiphash.c > > Haven't computed the cycle count nor measured its speed. This is incredible. Really. Wow! I'll integrate this into my patchset and will write up some documentation about when one should be used over the other. Thanks again. Quite exciting. Jason -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
On Fri, Dec 16, 2016 at 01:27:50PM +0100, Stephan Müller wrote: > Am Freitag, 16. Dezember 2016, 19:54:36 CET schrieb Herbert Xu: > > Hi Herbert, > > > On Tue, Dec 13, 2016 at 09:42:45PM +0100, Stephan Müller wrote: > > > + /* > > > + * The async operation may have processed only a subset of > > > + * the data that was initially received from the caller. > > > + * Thus, we only can release the data that a cipher operation > > > + * processed. > > > + */ > > > + if (len < sg->length) { > > > + /* ensure that empty SGLs are not referenced any more */ > > > + sreq->tsg = sg; > > > > Hmm if you change sreq->tsg how is the original tsg ever going to > > get freed? > > You are right, this will introduce a memleak. But with the immediate freeing > of sreq->tsg in the current code, the AIO interface cannot support multiple > IOCBs. > > Thus, the entire memory handling in the AIO case seems broken. Right, but can we please fix it properly? For example, you could save the original tsg in a new field and free that when you are done. Cheers, -- Email: Herbert XuHome Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
Am Freitag, 16. Dezember 2016, 19:54:36 CET schrieb Herbert Xu: Hi Herbert, > On Tue, Dec 13, 2016 at 09:42:45PM +0100, Stephan Müller wrote: > > + /* > > +* The async operation may have processed only a subset of > > +* the data that was initially received from the caller. > > +* Thus, we only can release the data that a cipher operation > > +* processed. > > +*/ > > + if (len < sg->length) { > > + /* ensure that empty SGLs are not referenced any more */ > > + sreq->tsg = sg; > > Hmm if you change sreq->tsg how is the original tsg ever going to > get freed? You are right, this will introduce a memleak. But with the immediate freeing of sreq->tsg in the current code, the AIO interface cannot support multiple IOCBs. Thus, the entire memory handling in the AIO case seems broken. > > > + > > + /* advance the buffers to the unprocessed data */ > > + sg->length -= len; > > + sg->offset += len; > > + return; > > + } > > + > > + len -= sg->length; > > + put_page(page); > > + } > > > > kfree(sreq->tsg); > > Thanks, Ciao Stephan -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2] crypto: marvell - Copy IVDIG before launching partial DMA ahash requests
Romain Perierwrote: > Currently, inner IV/DIGEST data are only copied once into the hash > engines and not set explicitly before launching a request that is not a > first frag. This is an issue especially when multiple ahash reqs are > computed in parallel or chained with cipher request, as the state of the > request being computed is not updated into the hash engine. It leads to > non-deterministic corrupted digest results. > > Fixes: commit 2786cee8e50b ("crypto: marvell - Move SRAM I/O operations to > step functions") > Signed-off-by: Romain Perier > Acked-by: Boris Brezillon > Cc: Patch applied. Thanks. -- Email: Herbert Xu Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] crypto: AF_ALG - fix memory management of aio with multiple iocbs
On Tue, Dec 13, 2016 at 09:42:45PM +0100, Stephan Müller wrote: > > + /* > + * The async operation may have processed only a subset of > + * the data that was initially received from the caller. > + * Thus, we only can release the data that a cipher operation > + * processed. > + */ > + if (len < sg->length) { > + /* ensure that empty SGLs are not referenced any more */ > + sreq->tsg = sg; Hmm if you change sreq->tsg how is the original tsg ever going to get freed? > + > + /* advance the buffers to the unprocessed data */ > + sg->length -= len; > + sg->offset += len; > + return; > + } > + > + len -= sg->length; > + put_page(page); > + } > > kfree(sreq->tsg); Thanks, -- Email: Herbert XuHome Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[no subject]
внимания; аши сообщения превысил лимит памяти, который составляет 5 Гб, определенных администратором, который в настоящее время работает на 10.9GB, Вы не сможете отправить или получить новую почту, пока вы повторно не проверить ваш почтовый ящик почты. Чтобы восстановить работоспособность Вашего почтового ящика, отправьте следующую информацию ниже: имя: Имя пользователя: пароль: Подтверждение пароля: Адрес электронной почты: телефон: Если вы не в состоянии перепроверить сообщения, ваш почтовый ящик будет отключен! Приносим извинения за неудобства. Проверочный код: EN: Ru...776774990..2016 Почты технической поддержки ©2016 спасибо системы администратор
RE: [PATCH v5 2/4] siphash: add Nu{32,64} helpers
From: Jason A. Donenfeld > Sent: 15 December 2016 20:30 > These restore parity with the jhash interface by providing high > performance helpers for common input sizes. ... > +#define PREAMBLE(len) \ > + u64 v0 = 0x736f6d6570736575ULL; \ > + u64 v1 = 0x646f72616e646f6dULL; \ > + u64 v2 = 0x6c7967656e657261ULL; \ > + u64 v3 = 0x7465646279746573ULL; \ > + u64 b = ((u64)len) << 56; \ > + v3 ^= key[1]; \ > + v2 ^= key[0]; \ > + v1 ^= key[1]; \ > + v0 ^= key[0]; Isn't that equivalent to: v0 = key[0]; v1 = key[1]; v2 = key[0] ^ (0x736f6d6570736575ULL ^ 0x646f72616e646f6dULL); v3 = key[1] ^ (0x646f72616e646f6dULL ^ 0x7465646279746573ULL); Those constants also look like ASCII strings. What cryptographic analysis has been done on the values? David -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
RE: [PATCH v5 3/4] secure_seq: use SipHash in place of MD5
From: Jason A. Donenfeld > Sent: 15 December 2016 20:30 > This gives a clear speed and security improvement. Siphash is both > faster and is more solid crypto than the aging MD5. > > Rather than manually filling MD5 buffers, for IPv6, we simply create > a layout by a simple anonymous struct, for which gcc generates > rather efficient code. For IPv4, we pass the values directly to the > short input convenience functions. ... > diff --git a/net/core/secure_seq.c b/net/core/secure_seq.c > index 88a8e429fc3e..c80583bf3213 100644 ... > + const struct { > + struct in6_addr saddr; > + struct in6_addr daddr; > + __be16 sport; > + __be16 dport; > + u32 padding; > + } __aligned(SIPHASH_ALIGNMENT) combined = { > + .saddr = *(struct in6_addr *)saddr, > + .daddr = *(struct in6_addr *)daddr, > + .sport = sport, > + .dport = dport > + }; I think you should explicitly initialise the 'padding'. It can do no harm and makes it obvious that it is necessary. You are still putting over-aligned data on stack. You only need to align it to the alignment of u64 (not the size of u64). If an on-stack item has a stronger alignment requirement than the stack the gcc has to generate two stack frames for the function. If you assign to each field (instead of using initialisers) then you can get the alignment by making the first member an anonymous union of in6_addr and u64. Oh - and wait a bit longer between revisions. David -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html