From: George Spelvin <hidden> Date: 2014-12-07 05:20:43
If you want DoS-resistant hash tables, I'm working on adding SipHash
to the kernel.
This is a keyed pseudo-random function designed specifically for that
application. I am starting with ext4 directory hashes, and then intended
to expand to secure sequence numbers (since it's far faster than MD5).
(I'm trying to figure out a good interface, since the crypto API
is a bit heavy for something to heavily optimized.)
But one comment caught my eye:
Even if security wasn't an issue, straight CRC32 has really poor
lower-order bit distribution, which makes it a terrible choice for
a hash table that simply uses the lower-order bits.
Er... huh? That's the first time I've heard that claim, and while I'm not
Philip Koopman or Guy Castagnoli, I thought I understood CRCs pretty well.
CRCs generally mix bits pretty well. The sparse 16-bit CRCs chosen
for implementation simplicity had some limitations, but the Castagnoli
polynomial is quite dense.
And their mathematical symmetry means that the low bits really shouldn't
be any different from any other bits. But if it is an issue, it's just
as easy work to shift down the correct number of high bits rather than
using the low.
Can you point me to a source for that statement?
From: George Spelvin <hidden> Date: 2014-12-07 10:02:58
For a start why don't you print out the hashes of 1-255 and then
find out how easy it is to deduce the last bit of the hash result.
They're available in lib/crc32table.h, as crc32ctable_le[0].
As a CRC is a linear function, every bit is the XOR of some
selected bits of the input, i.e. the parity of the input and
some bit-specific mask sequence.
Furthermore, CRCs are cyclic, so the mask sequences for adjacent bits are
shifts of each other.
The lsbit of the CRC32c of x is the parity of x & 0x1f.
This is because the LFSR sequence generated by the polynomial
starts 0001111110010001110010101111011000111000011011110010110000100101...
The first bit corresponds to the msbit of the last byte.
How does this implicate the low bits specifically?
From: Herbert Xu <herbert@gondor.apana.org.au> Date: 2014-12-07 12:52:11
On Sun, Dec 07, 2014 at 05:02:52AM -0500, George Spelvin wrote:
How does this implicate the low bits specifically?
If you can easily deduce the pre-images that make the last bit
of the hash even or odd, then you've just cut your search space
for collisions by half. The real killer is that you can do this
without knowing what the secret is.
Our entire scheme is dependent on using the secret to defeat
would-be attackers. If CRC does not make effective use of the
secret, then we're essentially naked against attackers.
Cheers,
--
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
From: Hannes Frederic Sowa <hidden> Date: 2014-12-07 13:14:46
Hi,
On So, 2014-12-07 at 00:20 -0500, George Spelvin wrote:
If you want DoS-resistant hash tables, I'm working on adding SipHash
to the kernel.
This is a keyed pseudo-random function designed specifically for that
application. I am starting with ext4 directory hashes, and then intended
to expand to secure sequence numbers (since it's far faster than MD5).
From: George Spelvin <hidden> Date: 2014-12-07 13:23:12
quoted
How does this implicate the low bits specifically?
If you can easily deduce the pre-images that make the last bit
of the hash even or odd, then you've just cut your search space
for collisions by half. The real killer is that you can do this
without knowing what the secret is.
Um, yes, if you're in a situation where a hash collsion DoS is possible,
a CRC is disastrous choice. You can trivially find collisions for *all*
bits of a CRC. Low or high, they're all equally easy.
When you said
quoted
quoted
quoted
quoted
Even if security wasn't an issue, straight CRC32 has really poor
lower-order bit distribution, which makes it a terrible choice for
a hash table that simply uses the lower-order bits.
This is talking about:
- Non-malicious inputs,where security isn't an issue, and
- Low-order bits specifically, implying that the high-order bits are different.
*That's* the claim I'm curious about. I know perfectly well that if
security *is* an issue, a fixed-polynomial CRC is a disaser.
But for non-malicious inputs, like normal software identifiers, a CRC
actually works very well.
If you want to do secure hashing with a CRC, you need to have a secret
*polynomial*. That *is* provably secure (it's a universal family of hash
functions), but isn't provided by x86 unless you use SSE and PCLMUL.
That's why it's a non-cryptographic hash, suitable for non-malicious
inputs only. That's the same security claim as many other common hash
functions.
Our entire scheme is dependent on using the secret to defeat
would-be attackers. If CRC does not make effective use of the
secret, then we're essentially naked against attackers.
Okay, I'm confused. *What* scheme? The arch_fast_hash interface doesn't
have any provision for a secret. Because there's no point to having one;
you can't change the polynomial, and anything additive has just moves
collisions around without reducing them.
So there are plenty of hash tables in Linux that you don't dare use this
with. In fact, so many that, as you rightly point out, it's not clear
if it's worth providing this special optimization for the few remaining.
Is that something that *can* be changed without breaking the
disk format? SipHash is explicitly *not* designed to be secure as
an unkeyed hash in the way that SHA-type algorithms are.
What it's designed to do is provide second preimage resistance
of its output, or a function (like modular reduction) of its output,
against an attacker who doesn't know the secret seed.
Ack. If we want to use it in the networking stack we should be able to
use it without a dependency to the crypto framework.
Already understood. My big question is whether a single function call
is okay or we need something inlinable.
Is that something that *can* be changed without breaking the
disk format? SipHash is explicitly *not* designed to be secure as
an unkeyed hash in the way that SHA-type algorithms are.
I did some research and it looked like it would need a change to the
disk format but it should be doable by incrementing the super block
version, so at least newly created filesystem would benefit from it.
What it's designed to do is provide second preimage resistance
of its output, or a function (like modular reduction) of its output,
against an attacker who doesn't know the secret seed.
quoted
Ack. If we want to use it in the networking stack we should be able to
use it without a dependency to the crypto framework.
Already understood. My big question is whether a single function call
is okay or we need something inlinable.
Like md5_transfrom, I think a non-inline function would be just fine.
Otherwise kernel code size would increase. Most hash users in the
network stack mostly deal with less bytes of input than one round needs.
Bye,
Hannes
Is that something that *can* be changed without breaking the
disk format? SipHash is explicitly *not* designed to be secure as
an unkeyed hash in the way that SHA-type algorithms are.
I did some research and it looked like it would need a change to the
disk format but it should be doable by incrementing the super block
version, so at least newly created filesystem would benefit from it.
quoted
What it's designed to do is provide second preimage resistance
of its output, or a function (like modular reduction) of its output,
against an attacker who doesn't know the secret seed.
quoted
Ack. If we want to use it in the networking stack we should be able to
use it without a dependency to the crypto framework.
Already understood. My big question is whether a single function call
is okay or we need something inlinable.
Like md5_transfrom, I think a non-inline function would be just fine.
Otherwise kernel code size would increase. Most hash users in the
network stack mostly deal with less bytes of input than one round needs.
Of course, if it looks feasable (from a performance PoV, but I doubt
that) to migrate the current jhash users to siphash, it might be worth
dealing with larger input sizes and maybe also doing it inline. But that
very much depends on the code size it would add. Currently we use jhash
as the non-linear "secure" hashing functions at most places.
Also rhashtable takes a pointer to the hasing function, thus causing gcc
to generate a function in each compilation unit if it would be static
inline.
From: Hannes Frederic Sowa <hidden> Date: 2014-12-07 14:06:50
On So, 2014-12-07 at 08:23 -0500, George Spelvin wrote:
So there are plenty of hash tables in Linux that you don't dare use this
with. In fact, so many that, as you rightly point out, it's not clear
if it's worth providing this special optimization for the few remaining.
In case of openvswitch it shows a performance improvment. The seed
parameter could be used as an initial biasing of the crc32 function, but
in case of openvswitch it is only set to 0.
Bye,
Hannes
From: George Spelvin <hidden> Date: 2014-12-07 21:33:58
On Sun, 2014-12-07 at 15:06 +0100, Hannes Frederic Sowa wrote:
In case of openvswitch it shows a performance improvment. The seed
parameter could be used as an initial biasing of the crc32 function, but
in case of openvswitch it is only set to 0.
NACK.
This is the Fatal Error in thinking that Herbert was warning about.
The seed parameter doesn't affect CRC32 collisions *at all* if the inputs
are the same size.
For fixed-size inputs, a non-zero seed is equivalent to XORing a
constant into the output of the CRC computation.
for *different* sized inputs, a non-zero seed detects zero-padding
better than a zero one, but *which* non-zero value is also irrelevant;
all-ones is the traditional choice because it's simplest in hardware.
A CRC is inherently linear. CRC(a^b) = CRC(a) ^ CRC(b). This makes
them easy to analyze mathematically and gives them a number of nice
properties for detecting hardware corruption.
But that same simplicity makes it *ridiculously* easy to generate
collisions if you try.
One way of looking at a CRC is to say that each bit in the input
has a CRC. The CRC of a message string is just the XOR of the CRCs
of the individual bits that are set in the message.
Now, a CRC polynomial is chosen so that all of the bits of a
message have different CRCs. Obviously, there's a limit: when the
message is 2^n bits long, it's not possible for all the bits to
have different, non-zero n-bit CRCs.
But a CRC is a really efficient way of assigning different bit patterns
to different input bits up to that limit.
(Something like CRC32c is also chosen so that, for messages up to a
reasonable length, no 3-bit, 4-bit, etc. combinations have CRCs that
XOR to zero.)
But, and this might be what Herbert was trying to say and I was
misunderstanding, if you then *truncate* that CRC, the CRCs of the
message bits lose that uniqueness guarantee. They're just pseudorandom
numbers, and a CRC loses its special collision-resistance properties.
It's just an ordinary random hash, and thanks to the birthday paradox,
you're likely to find two bits whose CRCs agree in any particular 8 bits
within roughly sqrt(2*256) or 22 bits.
Here are a few such collisions for the least significant 8 bits of CRC32c:
Msg1 CRC32c Msg2 CRC32c Match
1<<11 3fc5f181 1<<30 bf672381 81
1<<12 9d14c3b8 1<<31 dd45aab8 b8
1<<5 c79a971f 1<<44 6006181f 1f
1<<15 13a29877 1<<45 b2f53777 77
There's nothing special about the lsbits of the CRC.
Within 64 bits, the most significant 8 bits have it worse:
1<<5 c79a971f 1<<17 c76580d9 c7
1<<6 e13b70f7 1<<18 e144fb14 e1
1<<19 70a27d8a 1<<38 7022df58 70
1<<20 38513ec5 1<<39 38116fac 38
1<<13 4e8a61dc 1<<52 4e2dfd53 4e
1<<23 a541927e 1<<53 a5e0c5d1 a5
Now, I'd like to stress that this collision rate is no worse than any
*other* hash function. A truncated CRC loses its special resistance to
the birthday paradox (you'd have been much smarter to use 8-bit CRC),
but it doesn't become especially bad. A truncated SHA-1 will have
coillisions just as often.
The concern with a CRC is that, once you've found one collision, you've
found a huge number of them. Just XOR the bit pattern of your choice
into both of the colliding messages, and you have a new collision.
For another example, if you consider the CRC32c of all possible 1-byte
messages *and then take only the low byte*, there are only 128 possible
values.
It turns out that the byte 0x5d has a CRC32c of 0xee0d9600. This ends
in 00, so if I XOR 0x5d into anything, the low 8 bits of the CRC
don't change.
Likewise, the message "23 00" has a CRC32c of 0x00ee0d96. So you can
XOR 0x23 into the second-last byte of anything, and the high 8 bits of
the CRC don't change.
From: Hannes Frederic Sowa <hidden> Date: 2014-12-08 11:25:14
Hi,
On Sun, Dec 7, 2014, at 22:33, George Spelvin wrote:
On Sun, 2014-12-07 at 15:06 +0100, Hannes Frederic Sowa wrote:
quoted
In case of openvswitch it shows a performance improvment. The seed
parameter could be used as an initial biasing of the crc32 function, but
in case of openvswitch it is only set to 0.
NACK.
This is the Fatal Error in thinking that Herbert was warning about.
The seed parameter doesn't affect CRC32 collisions *at all* if the inputs
are the same size.
For fixed-size inputs, a non-zero seed is equivalent to XORing a
constant into the output of the CRC computation.
Sorry for being unclear, I understood that and didn't bother patching
that '0' with a random seed exactly because of this.
for *different* sized inputs, a non-zero seed detects zero-padding
better than a zero one, but *which* non-zero value is also irrelevant;
all-ones is the traditional choice because it's simplest in hardware.
A CRC is inherently linear. CRC(a^b) = CRC(a) ^ CRC(b). This makes
them easy to analyze mathematically and gives them a number of nice
properties for detecting hardware corruption.
But that same simplicity makes it *ridiculously* easy to generate
collisions if you try.
Yes, understood and I totally agree we shouldn't use crc32 hashing in a
lot of places where unsafe data is going to be hashed and inserted into
hash tables.
One way of looking at a CRC is to say that each bit in the input
has a CRC. The CRC of a message string is just the XOR of the CRCs
of the individual bits that are set in the message.
Now, a CRC polynomial is chosen so that all of the bits of a
message have different CRCs. Obviously, there's a limit: when the
message is 2^n bits long, it's not possible for all the bits to
have different, non-zero n-bit CRCs.
But a CRC is a really efficient way of assigning different bit patterns
to different input bits up to that limit.
(Something like CRC32c is also chosen so that, for messages up to a
reasonable length, no 3-bit, 4-bit, etc. combinations have CRCs that
XOR to zero.)
But, and this might be what Herbert was trying to say and I was
misunderstanding, if you then *truncate* that CRC, the CRCs of the
message bits lose that uniqueness guarantee. They're just pseudorandom
numbers, and a CRC loses its special collision-resistance properties.
It's just an ordinary random hash, and thanks to the birthday paradox,
you're likely to find two bits whose CRCs agree in any particular 8 bits
within roughly sqrt(2*256) or 22 bits.
Here are a few such collisions for the least significant 8 bits of
CRC32c:
Msg1 CRC32c Msg2 CRC32c Match
1<<11 3fc5f181 1<<30 bf672381 81
1<<12 9d14c3b8 1<<31 dd45aab8 b8
1<<5 c79a971f 1<<44 6006181f 1f
1<<15 13a29877 1<<45 b2f53777 77
There's nothing special about the lsbits of the CRC.
Within 64 bits, the most significant 8 bits have it worse:
1<<5 c79a971f 1<<17 c76580d9 c7
1<<6 e13b70f7 1<<18 e144fb14 e1
1<<19 70a27d8a 1<<38 7022df58 70
1<<20 38513ec5 1<<39 38116fac 38
1<<13 4e8a61dc 1<<52 4e2dfd53 4e
1<<23 a541927e 1<<53 a5e0c5d1 a5
Now, I'd like to stress that this collision rate is no worse than any
*other* hash function. A truncated CRC loses its special resistance to
the birthday paradox (you'd have been much smarter to use 8-bit CRC),
but it doesn't become especially bad. A truncated SHA-1 will have
coillisions just as often.
The concern with a CRC is that, once you've found one collision, you've
found a huge number of them. Just XOR the bit pattern of your choice
into both of the colliding messages, and you have a new collision.
Ack.
For another example, if you consider the CRC32c of all possible 1-byte
messages *and then take only the low byte*, there are only 128 possible
values.
It turns out that the byte 0x5d has a CRC32c of 0xee0d9600. This ends
in 00, so if I XOR 0x5d into anything, the low 8 bits of the CRC
don't change.
Likewise, the message "23 00" has a CRC32c of 0x00ee0d96. So you can
XOR 0x23 into the second-last byte of anything, and the high 8 bits of
the CRC don't change.
A very interesting read, thanks for your mail!
Bye,
Hannes
From: George Spelvin <hidden> Date: 2014-12-08 16:20:03
quoted
quoted
In case of openvswitch it shows a performance improvment. The seed
parameter could be used as an initial biasing of the crc32 function, but
in case of openvswitch it is only set to 0.
quoted
NACK. [...]
Sorry for being unclear, I understood that and didn't bother patching
that '0' with a random seed exactly because of this.
And I'm sorry for delivering a long lecture on a subject you already
understood perfectly well.
I'd just been thinking about it because of Herbert's comments, so it was
conveniently at hand. :-)
Out of curiousity, what *were* you referring to when you talked
about biasing the crc32 function? "Biasing" is a good term becuase
it just applies an offset, but what do you gain from doing that?
There are nifty things one can do with the CRC32 instruction, however.
A lot of ciphers these days use an ARX (add, rotate, XOR) kernel.
A crc32 instruction, although linear, does some very powerful rotate &
xor operations, and could replace the XOR and rotate.
From: Hannes Frederic Sowa <hidden> Date: 2014-12-08 16:32:12
On Mon, Dec 8, 2014, at 17:19, George Spelvin wrote:
quoted
quoted
quoted
In case of openvswitch it shows a performance improvment. The seed
parameter could be used as an initial biasing of the crc32 function, but
in case of openvswitch it is only set to 0.
quoted
quoted
NACK. [...]
quoted
Sorry for being unclear, I understood that and didn't bother patching
that '0' with a random seed exactly because of this.
And I'm sorry for delivering a long lecture on a subject you already
understood perfectly well.
I learned something, so your time wasn't completely wasted. ;)
I'd just been thinking about it because of Herbert's comments, so it was
conveniently at hand. :-)
Out of curiousity, what *were* you referring to when you talked
about biasing the crc32 function? "Biasing" is a good term becuase
it just applies an offset, but what do you gain from doing that?
Actually, I don't know why the seed parameter was added. I just wanted
to mention that there is a way to bias the crc32 function which fits
into the style of the other hashing functions, like jhash with its
initval parameter.
I just kept it around during the rewrite.
The only use case I can imagine would be if one would like to calculate
a crc32c over a non-contiguous array, thus feeding the result of one crc
operation into the next one.
There are nifty things one can do with the CRC32 instruction, however.
A lot of ciphers these days use an ARX (add, rotate, XOR) kernel.
A crc32 instruction, although linear, does some very powerful rotate &
xor operations, and could replace the XOR and rotate.