From: "George Spelvin" <firstname.lastname@example.org> To: Jason@zx2c4.com, email@example.com Cc: firstname.lastname@example.org, email@example.com, David.Laight@aculab.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org, email@example.com, firstname.lastname@example.org Subject: Re: HalfSipHash Acceptable Usage Date: 20 Dec 2016 18:07:52 -0500 [thread overview] Message-ID: <email@example.com> (raw) In-Reply-To: <firstname.lastname@example.org> 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 to >> me. Seem okay to you? > Um, why do TCP sequence numbers need long-term security? So long as > you rekey every 5 minutes or so, TCP sequence numbers don't need any > more security than that, since even if you break the key used to > generate initial sequence numbers seven a minute or two later, any > pending TCP connections will have timed out long before. > > See the security analysis done in RFC 6528, where among other > things, it points out why MD5 is acceptable with periodic rekeying, > although there is the concern that this could break certain hueristics > used when establishing new connections during the TIME-WAIT state. Because we don't rekey TCP sequence numbers, ever. See commit 6e5714eaf77d79ae1c8b47e3e040ff5411b717ec To rekey them requires dividing the sequence number base into a "random" part and some "generation" msbits. While we can do better than the previous 8+24 split (I'd suggest 4+28 or 3+29), only 2 is tricks, and 1 generation bit isn't enough. So while it helps in the long term, it reduces the security offered by the random part in the short term. (If I know 4 bits of your ISN, I only need to send 256 MB to hit your TCP window.) At the time, I objected, and suggested doing two hashes, with a fixed 32-bit base plus a split rekeyed portion, but that was vetoed on the grounds of performance. On further consideration, the fixed base doesn't help much. (Details below for anyone that cares.) Suppose we let the TCP initial sequence number be: (Hash(<srcIP,dstIP,srcPort,dstPort>, fixed_key) & 0xffffffff) + (i << 28) + (Hash(<srcIP,dstIP,srcPort,dstPort>, key[i]) & 0x0fffffff) + (current_time_in_nanoseconds / 64) It's not hugely difficult to mount an effective attack against a 64-bit fixed_key. As an attacker, I can ask the target to send me these numbers for dstPort values i control and other values I know. I can (with high probability) detect the large jumps when the generation changes, so I can make a significant number of queries with the same generation. After 23-ish queries, I have enough information to identify a 64-bit fixed_key. I don't know the current generation counter "i", but I know it's the same for all my queries, so for any two queries, the maximum difference between the 28-bit hash values is 29 bits. (We can also add a small margin to allow for timeing uncertainty, but that's even less.) So if I guess a fixed key, hash my known plaintexts with that guess, subtract the ciphertexts from the observed sequence numbers, and the difference between the remaining (unknown) 28-bit hash values plus timestamps exceeds what's possible, my guess is wrong. I can then repeat with additional known plaintexts, reducing the space of admissible keys by about 3 bits each time. Assuming I can rent GPU horsepower from a bitcoin miner to do this in a reasonable period of time, after 22 known plaintext differences, I have uniquely identified the key. Of course, in practice I'd do is a first pass with maybe 6 plaintexts on the GPU, and then deal with the candidates found in a second pass. But either way, it's about 2.3 SipHash evaluations per key tested. As I noted earlier, a bitcoin blockchain block, worth 25 bitcoins, currently costs 2^71 evaluations of SHA-2 (2^70 evaluations of double SHA-2), and that's accomplished every 10 minutes, this is definitely practical.
next prev parent reply other threads:[~2016-12-20 23:07 UTC|newest] Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-12-19 17:32 Jason A. Donenfeld [not found] ` <CAGiyFdduUNSGq24zfsk0ZU=hnOCmewAw8vw6XvDoS-3f+3UPKQ@mail.gmail.com> 2016-12-19 21:00 ` Jason A. Donenfeld 2016-12-20 21:36 ` Theodore Ts'o 2016-12-20 23:07 ` George Spelvin [this message] 2016-12-20 23:55 ` Eric Dumazet 2016-12-21 3:28 ` George Spelvin 2016-12-21 5:29 ` Eric Dumazet 2016-12-21 6:34 ` George Spelvin 2016-12-21 14:24 ` Jason A. Donenfeld 2016-12-21 15:55 ` George Spelvin 2016-12-21 16:37 ` Jason A. Donenfeld 2016-12-21 16:41 ` [kernel-hardening] " Rik van Riel 2016-12-21 17:25 ` Linus Torvalds 2016-12-21 18:07 ` George Spelvin 2016-12-22 1:54 ` Andy Lutomirski 2016-12-21 14:42 ` Jason A. Donenfeld 2016-12-21 15:56 ` Eric Dumazet 2016-12-21 16:33 ` Jason A. Donenfeld 2016-12-21 16:39 ` [kernel-hardening] " Rik van Riel 2016-12-21 17:08 ` Eric Dumazet 2016-12-21 18:37 ` George Spelvin 2016-12-21 18:40 ` Jason A. Donenfeld 2016-12-21 22:27 ` Theodore Ts'o 2016-12-22 0:18 ` George Spelvin 2016-12-22 1:13 ` George Spelvin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --email@example.com \ --firstname.lastname@example.org \ --cc=David.Laight@aculab.com \ --cc=Jason@zx2c4.com \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --subject='Re: HalfSipHash Acceptable Usage' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).