Re: [PATCH v3] siphash: add cryptographically secure hashtable function

[Jason A. Donenfeld]

Hi Linus,

On Tue, Dec 13, 2016 at 8:25 PM, Linus Torvalds
 wrote:
> Yeah,. the TCP sequence number md5_transform() cases are likely the
> best example of something where siphash might be good. That tends to
> be really just a couple words of data (the address and port info) plus
> the net_secret[] hash. I think they currently simply just fill in the
> fixed-sized 64-byte md5-round area.
>
> I wonder it's worth it to have a special spihash version that does
> that same "fixed 64-byte area" thing.

What happens in MD5 the hash function is that it first initializes its
initial 128-bit hash to a magic constant, and then reads 64 bytes at a
time from the input and calls md5_transform on that, which each time
manipulates that 128-bit value from its starting value. At the end of
the input, some special padding is applied for small final blocks,
some finalization, and then the resultant hash is whatever that
128-bit value is at the end of the process.

What the tcp stack does with secure_tcp_sequence_number function in
net/core/secure_seq.c, and a variety of other places, is to just
supply that 128-bit initial value not with the magic constant, but
instead with saddr||daddr||sport||dport||net_secret[15] and then calls
md5_transform on the 64-byte long term secret random value
(net_secret). From the resultant 128-bit value, they take the first
32-bits. In addition to being rather heavy weight, this strikes me as
cryptographically a bit dubious too. But that's where your "fixed
64-byte area" notion comes from.

Siphash makes things a lot more simple than that. Since siphash is a
PRF and not a mere hash function, it takes an explicit secret key
parameter, which would be net_secret, some input data, which would be
saddr||daddr||sport||dport, and then spits out a 64-bit number, 32
bits of which would be used as the sequence number.

seq_num = seq_scale(siphash24(saddr||daddr||sport||dport, net_secret));

A lot simpler, faster, and actually secure.


> But please talk to the netwotrking people. Maybe that's the proper way
> to get this merged?

I had hoped to do it the lazy way, and just have it just wind up in
lib/. But I suppose you and Greg are of course right, and I should
submit this with a real usage. So I'll do that, and resubmit in
another thread as a series to LKML and netdev.

Thanks for your feedback!

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 v3] siphash: add cryptographically secure hashtable function

[Jason A. Donenfeld]

Hi Eric,

On Tue, Dec 13, 2016 at 9:39 AM, Eric Biggers  wrote:
> Hmm, I don't think you can really do load_unaligned_zeropad() without first
> checking for 'left != 0'.  The fixup section for load_unaligned_zeropad()
> assumes that rounding the pointer down to a word boundary will produce an
> address from which an 'unsigned long' can be loaded.  But if 'left = 0' and we
> happen to be on a page boundary with the next page unmapped, then this will 
> not
> be true and the second load will still fault.

Excellent point. I haven't been able to trigger this in my
experiments, but it doesn't look like there's much to prevent this
from happening. I'll submit a v4 with this as fixed, since there
hasn't been any other code quality issues.

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 v3] siphash: add cryptographically secure hashtable function

[Linus Torvalds]

On Tue, Dec 13, 2016 at 12:39 AM, Eric Biggers  wrote:
>
> Hmm, I don't think you can really do load_unaligned_zeropad() without first
> checking for 'left != 0'.

Right you are. If the allocation is at the end of a page, the 0-size
case would be entirely outside the page and there's no fixup.

Of course, that never happens in normal code, but DEBUG_PAGE_ALLOC can
trigger it.

  Linus
--
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 v3] siphash: add cryptographically secure hashtable function

[Linus Torvalds]

On Mon, Dec 12, 2016 at 3:04 PM, Jason A. Donenfeld  wrote:
>
> Indeed this would be a great first candidate. There are lots of places
> where MD5 (!!) is pulled in for this sort of thing, when SipHash could
> be a faster and leaner replacement (and arguably more secure than
> rusty MD5).

Yeah,. the TCP sequence number md5_transform() cases are likely the
best example of something where siphash might be good. That tends to
be really just a couple words of data (the address and port info) plus
the net_secret[] hash. I think they currently simply just fill in the
fixed-sized 64-byte md5-round area.

I wonder it's worth it to have a special spihash version that does
that same "fixed 64-byte area" thing.

But please talk to the netwotrking people. Maybe that's the proper way
to get this merged?

Linus
--
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 v3] siphash: add cryptographically secure hashtable function

[Eric Biggers]

On Mon, Dec 12, 2016 at 11:18:32PM +0100, Jason A. Donenfeld wrote:
> + for (; data != end; data += sizeof(u64)) {
> + m = get_unaligned_le64(data);
> + v3 ^= m;
> + SIPROUND;
> + SIPROUND;
> + v0 ^= m;
> + }
> +#if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
> + b |= le64_to_cpu(load_unaligned_zeropad(data) & 
> bytemask_from_count(left));
> +#else

Hmm, I don't think you can really do load_unaligned_zeropad() without first
checking for 'left != 0'.  The fixup section for load_unaligned_zeropad()
assumes that rounding the pointer down to a word boundary will produce an
address from which an 'unsigned long' can be loaded.  But if 'left = 0' and we
happen to be on a page boundary with the next page unmapped, then this will not
be true and the second load will still fault.

Eric
--
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 v3] siphash: add cryptographically secure hashtable function

[Jason A. Donenfeld]

On Tue, Dec 13, 2016 at 12:01 AM, Andi Kleen  wrote:
> It would be nice if the network code could be converted to use siphash
> for the secure sequence numbers. Right now it pulls in a lot of code
> for bigger secure hashes just for that, which is a problem for tiny
> kernels.

Indeed this would be a great first candidate. There are lots of places
where MD5 (!!) is pulled in for this sort of thing, when SipHash could
be a faster and leaner replacement (and arguably more secure than
rusty MD5).
--
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 v3] siphash: add cryptographically secure hashtable function

[Andi Kleen]

> Dozens of languages are already using this internally for their hash
> tables. Some of the BSDs already use this in their kernels. SipHash is
> a widely known high-speed solution to a widely known problem, and it's
> time we catch-up.

It would be nice if the network code could be converted to use siphash
for the secure sequence numbers. Right now it pulls in a lot of code
for bigger secure hashes just for that, which is a problem for tiny
kernels.

-Andi
--
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