I'm not trying to defend adler. But I'm not sure I buy this:
"Granted the failure rate is pretty low (3/13068402) but that's not secure."
Why is 3/13,068,402 not secure, but 3/130,068,402 is secure? (Note, I pulled that number out of my butt, but it's compatible with the the 0/13,068,402 numbers.)
Obviously one is more secure than the other, but it's not you postulated some binary test based on some minimum threshhold before you started.
Eh, yeah, okay. I'm not making rigorous statements. I don't really know this field at all. But it seems like Adler32 was just a mistake. Fletcher32 is older, simpler, faster, and more robust.
I think "secure" was a poor choice of word, and lets leave it at that.
Yeah, Fletcher has some annoying known collisions. IIRC, I think it confuses 0xFFFF with 0x0000. And adler and fletcher are both vectorizable so should be way faster than burtle or murmur.
It is curious that Fletcher32 is obscure and Adler32 is not, considering Fletcher is the older. However, Fletcher16 had some serious problems, so people must have just tossed it aside.
Also murmur is substantially faster if you interleave words 2x. See MurmurHash64B. You could also vectorize interleave murmur-like hashes using the parallel integer multiply instructions in SSE4. SSE2 has multiply, but it isn't particularly useful for murmur.
I think all the hashes are trivially vectorizable by treating the data packet as 4 different streams and computing a hash for each stream in each lane, then mixing them at the end. I believe that does slightly compromise the quality of the hash though.
I still think Burtle might well be the fastest on the SPU since it does DWORD lookups, and reading shit out of the array is going to be one of the slowest parts on the SPU. A huge speed difference on the SPU would also be whether I could align my words or not.
If Bob could cook me up one that used 4 dwords instead of 3 I'm sure that would be the nuts (if my data could be 16-byte aligned).
But I really don't feel like spending another month micro-optimizing some useless shit for this damn obsolete hunk of junk platform. I think PS3's are actually manufactured from the blood and tears of programmers.
Oh, you totally commented on Fletcher's 0s v 1s behavior in my original comment on the other thread.
"I think all the hashes are trivially vectorizable by treating the data packet as 4 different streams and computing a hash for each stream in each lane, then mixing them at the end."
Of course. But I mean adler/fletcher are vectorizable as a single stream.
"I believe that does slightly compromise the quality of the hash though."
It would amplify the issue if you have weaknesses in short strings (like adler, or fnv to some extent), but you should be able to compensate for this with a better final mix.
But yeah, it is unlikely that hashing will be a significant part of your runtime or any of your critical paths. It's there if you ever feel like mental masturbation, neglecting your loved ones, etc.
There is one huge advantage of Adler32 (or any byte-at-a-time hash) , which is that you can roll up to alignment, then run on 16-byte aligned pieces, then roll down the tail.
"I think PS3's are actually manufactured from the blood and tears of programmers." And you don't even have to deal with the RSX! It only does everything... wrong.
August 22, 2010 at 10:20 PM
Anonymous said...
Also, poking around wikipedia, it looks like common understanding (like the thesis "The Effectiveness of Checksums for Embedded Networks") is that Adler32 and Fletcher32 are basically indistinguishable in terms of behavior (Adler32 slightly theoretically worse, but in graphs shown as essentially identical).
I wonder what the deal is with that.
August 23, 2010 at 3:48 AM
Anonymous said...
The other thing to look at is 1-byte/1-bit stomps. These are the sort of things that CRC and Fletcher/Adler are generally guaranteed to detect. The hashes aren't normally analyzed on that front, but it wouldn't surprise me if they could be. The biggest concern would be something like Burtle that has more internal state than is visible in the hash, so you might be able to get cases where flipping a bit only affects the invisible state. (If the Burtle one you're looking at is like that.)
Of course whether 1-bit/1-byte flips are plausible in your data I dunno.
August 23, 2010 at 3:56 AM
Anonymous said...
Oh wait, I found stuff later in that thesis where they underscore that Adler32 is worse than Fletcher32. Apparently historically, Adler32 was invented as an improvement of Fletcher16, unaware that you could just extend Fletcher as-is to 32.
" The other thing to look at is 1-byte/1-bit stomps. These are the sort of things that CRC and Fletcher/Adler are generally guaranteed to detect."
Yeah, this is exactly what I did in the "So I figured I'd test on what is more like my real usage scenario." portion of the post.
"The biggest concern would be something like Burtle that has more internal state than is visible in the hash,"
Yeah but the Burtle one is rigorously designed so that all internal state maps to visible bits. In fact I think he specifically gaurantees that one bit flips show up. I guess the issue is how easy is it for two changes to cancel each other.
I guess the issue is how easy is it for two changes to cancel each other.
I think even a single 1-bit change could be potentially invisible. The statistical goal is that every 1-bit change flip half the output bits, but there's no requirement that a 1-bit flip of ANY input produce flips in half the bits, hence no requirement they flip any visible bits. The problem is how much testing you'd have to do to find a bad case if you can't prove it, and a question of how meaningful the proof of such properties for adler/fletcher is if you're worried about larger stomps.
Also, that thesis seemed to claim both that Fletcher32/Adler32 can detect any single error up to 16-bits wide (it talked in terms of k-bit-error, where I believe k in this case is 16), but also that they don't detect 0x0000 vs 0xffff, which seems kind of mystifying.
But whatever the actual proven guarantee is, the question of whether such a proven guarantee buys you much for errors-found-in-practice compared to a hash like burtle/fnv is unclear.
BTW the reason why the Fletcher looks so bad in one of those tests is because one of my Fuzz Munge modes is "stomp byte to 00" and another mode is "stomp byte to FF" , and those hit the bad case.
So I had thought about how to deal with Fletcher's weird 00/FF problem. Maybe all you do is xor the input words with a counter or maybe some pseudorandom thing which would spread the naughtiness around a bit.
"So I had thought about how to deal with Fletcher's weird 00/FF problem. Maybe all you do is xor the input words with a counter or maybe some pseudorandom thing which would spread the naughtiness around a bit."
Yeah I was thinking the same thing. I mean Fletcher does work okay as long as you don't hit the bad case. If you used an actually pseudorandom generator that changed as you went, it would be pretty hard to hit the bad case. But yeah then your complexity is back up to Burtle levels so fuck it.
August 24, 2010 at 8:56 AM
Anonymous said...
To put it in perspective, if there is exactly 1 2^16 bit number which can be replaced by another specific 2^16 bit number without detection, then this possibility occurs on 1 in 2^32 possible random 16-bit munges.
In fact there are two cases, since the swap can go in either direction, so the chance is 2^31.
In the grand scheme of things that's not so bad (given that it's a 32-bit checksum). So a randomized version of it might be tolerable -- obviously having the 0x0000 for 0xffff error itself is untenable. But I agree at that point you might as well go with something else.
"Conclusion: Fletcher32 looks perfectly solid and is very fast." "
You didn't read the addenda !
November 19, 2010 at 11:54 AM
Sean pointed out that I should try Adler32 for
corruption checking. For reference I did some study of file hashes
before and I'll use
the same test set now, so you can compare to that. I'm using the Adler32 from zlib which looks like a
decent implementation.
Testing on 10M arrays of average length 192 (random in [128,256]).
count : 10000000
totalBytes : 1920164768
clocks per byte :
burtle : 1.658665
crc32 : 10.429893
adler32 : 1.396631
murmur : 1.110712
FNV : 2.520380
So Adler is in fact decently fast, not as fast as Murmur but a bit faster than Burtle. (everything is
crazy fast on my x64 lappy; the old post was on my work machine, everything is 2-3X faster on this beast;
it's insane how much Core i7 can do per clock).
BTW I wasn't going to add Murmur and FNV to this test - I didn't test them before because they are really not
"corruption detection" hashes, they are hashes for hash tables, in particular they don't really try to
specifically gaurantee the one bit flips will change the hash or whatever it is that CRC's gaurantee, but
after I saw how non-robust Adler was I figured I should add them to the test, and we will see that they
do belong...
Now when I count collisions in the same way as before, a problem is evident :
collisions :
rand32 : 11530
burtle : 0
crc32 : 11774
adler32 : 1969609
murmur : 11697
FNV : 11703
note that as before, rand32 gives you a baseline on how many collisions a perfect 32 bit hash should
give you - those collisions are just due to running into the limitted space of the 32 bit word. Burtle
here is a 64 bit hash and never collides. (I think I screwed up my CRC a little bit, it's colliding
more than it should. But anyhoo). Adler does *terribly*. But that's actually a known problem for short
sequences.
How does it do on longer sequences ? On arrays of random length between 2k and 4k (average 3k) :
num hashes : 10000000
totalBytes : 30722620564
clocks per byte :
burtle : 1.644675
crc32 : 11.638417
adler32 : 1.346784
murmur : 1.027105
FNV : 2.999243
collisions :
rand32 : 11530
burtle : 0
crc32 : 11586
adler32 : 12335
murmur : 11781
FNV : 11653
it's better, but still the worst of the group.
BTW I should note that the adler32 implementation does unrolling
and rollup/rolldown and all that kind of stuff and none of the other ones do. So it's speed advantage is a bit
unfair. All these sort of informal speed surveys should be taken with a grain of salt, since to really fairly
compare them I would have to spend a few weeks on each one making sure I got it as fast as possible, and of
course testing on various platforms. In particular FNV and Murmur use multiplies with is a no-go, but you
could probably use shift and add to replace the multiplies, and you'd get something like Bob's "One at a Time"
hash.
So I figured I'd test on what is more like my real usage scenario.
In the RAD LZH , I compress 16k data quanta, and check the CRC of each compressed chunk before decompressing.
So compressed chunks are between 0 and 16k bytes. Since they are compressed they are near random bits.
Corruption will take various forms, either complete stompage with random shite, or some bit flips, or tail or
head stomps. Complete stompage has been tested in the above runs (it's the same as checking the collision
rate for two unrelated sequences), so I tested incremental stomps.
I made random arrays between 256 and 16k bytes long. I then found the hash of that array, did some randomized
incremental stomping, and took the hash after the changes. If the hashes were the same, it counts as a
collision. The results are :
numTests : 13068402
burtle : 0 : 0.00000%
crc32 : 0 : 0.00000%
adler32 : 3 : 0.00002%
murmur : 0 : 0.00000%
FNV : 0 : 0.00000%
Adler32 is the only one that fails to detect these incremental stomps. Granted the failure rate is pretty low
(3/13068402) but that's not secure. Also, the hashes which are completely not designed for this (Murmur
and FNV) do better. (BTW you might think the Adler32 failures are all on very short arrays; not quite,
it does fail on a 256 byte case, then twice at 3840 bytes).
ADDENDUM : Ok I tested Fletcher32 too.
cycles :
rand32 : 0.015727
burtle : 1.364066
crc32 : 4.527377
adler32 : 1.107550
fletcher32 : 0.697941
murmur : 0.976026
FNV : 2.439253
large buffers :
num hashes : 10000000
totalBytes : 15361310411
rand32 : 11530
burtle64 : 0
crc32 : 11710
adler32 : 12891
fletcher32 : 11645
murmur : 11792
FNV : 11642
small buffers :
num hashes : 10000000
totalBytes : 1920164768
rand32 : 11530
burtle64 : 0
crc32 : 11487
adler32 : 24377
fletcher32 : 11793
murmur : 11673
FNV : 11599
difficult small buffers :
num hashes : 10000000
totalBytes : 1920164768
rand32 : 11530
burtle64 : 0
burtle32 : 11689
crc32 : 11774
adler32 : 1969609
fletcher32 : 11909
murmur : 11665
FNV : 11703
Conclusion : Adler32 is very bad and unsafe. Fletcher32 looks perfectly solid and is very fast.
ADDENDUM 2 : a bit more testing. I re-ran the test of munging the array with incremental small changes
of various types again. Running on lengths from 256 up to N, I get :
munge pattern 1 :
length : 6400
numTests : 25069753
rand32 : 0
burtle64 : 0
burtle32 : 0
crc32 : 0
adler32 : 14
fletcher32 : 22
murmur : 0
FNV : 0
munge pattern 2 :
length : 4096
numTests : 31322697
rand32 : 0
burtle64 : 0
burtle32 : 0
crc32 : 0
adler32 : 9
fletcher32 : 713
murmur : 0
FNV : 0
So I strike my conclusion that Fletcher is okay. Fletcher and Adler are both bad.
ADDENDUM 3 : Meh, it depends what kind of "corruption" you expect. The run above in which Fletcher is
doing very badly includes some "munges" which tend to fill the array with lots of zeros, in which area
it does very badly.
If you look at really true random noise type errors, and you always start your array full of random bits,
and then you make random bit flips or random byte changes (between 1 and 7 of them), and then refill the
array with rand, they perform as expected over a very large
number of runs :
numTests : 27987536
rand32 : 3 : 0.00001%
burtle64 : 2 : 0.00001%
burtle32 : 2 : 0.00001%
crc32 : 1 : 0.00000%
adler32 : 1 : 0.00000%
fletcher32 : 2 : 0.00001%
murmur : 2 : 0.00001%
FNV : 1 : 0.00000%
"08-21-10 - Adler32"
22 Comments -
I'm not trying to defend adler. But I'm not sure I buy this:
"Granted the failure rate is pretty low (3/13068402) but that's not secure."
Why is 3/13,068,402 not secure, but 3/130,068,402 is secure? (Note, I pulled that number out of my butt, but it's compatible with the the 0/13,068,402 numbers.)
Obviously one is more secure than the other, but it's not you postulated some binary test based on some minimum threshhold before you started.
August 22, 2010 at 7:27 PM
Eh, yeah, okay. I'm not making rigorous statements. I don't really know this field at all. But it seems like Adler32 was just a mistake. Fletcher32 is older, simpler, faster, and more robust.
August 22, 2010 at 7:50 PM
I think "secure" was a poor choice of word, and lets leave it at that.
Yeah, Fletcher has some annoying known collisions. IIRC, I think it confuses 0xFFFF with 0x0000. And adler and fletcher are both vectorizable so should be way faster than burtle or murmur.
It is curious that Fletcher32 is obscure and Adler32 is not, considering Fletcher is the older. However, Fletcher16 had some serious problems, so people must have just tossed it aside.
Also murmur is substantially faster if you interleave words 2x. See MurmurHash64B. You could also vectorize interleave murmur-like hashes using the parallel integer multiply instructions in SSE4. SSE2 has multiply, but it isn't particularly useful for murmur.
August 22, 2010 at 8:16 PM
I think all the hashes are trivially vectorizable by treating the data packet as 4 different streams and computing a hash for each stream in each lane, then mixing them at the end. I believe that does slightly compromise the quality of the hash though.
I still think Burtle might well be the fastest on the SPU since it does DWORD lookups, and reading shit out of the array is going to be one of the slowest parts on the SPU. A huge speed difference on the SPU would also be whether I could align my words or not.
If Bob could cook me up one that used 4 dwords instead of 3 I'm sure that would be the nuts (if my data could be 16-byte aligned).
But I really don't feel like spending another month micro-optimizing some useless shit for this damn obsolete hunk of junk platform. I think PS3's are actually manufactured from the blood and tears of programmers.
August 22, 2010 at 8:30 PM
Oh, you totally commented on Fletcher's 0s v 1s behavior in my original comment on the other thread.
"I think all the hashes are trivially vectorizable by treating the data packet as 4 different streams and computing a hash for each stream in each lane, then mixing them at the end."
Of course. But I mean adler/fletcher are vectorizable as a single stream.
"I believe that does slightly compromise the quality of the hash though."
It would amplify the issue if you have weaknesses in short strings (like adler, or fnv to some extent), but you should be able to compensate for this with a better final mix.
But yeah, it is unlikely that hashing will be a significant part of your runtime or any of your critical paths. It's there if you ever feel like mental masturbation, neglecting your loved ones, etc.
August 22, 2010 at 8:59 PM
There is one huge advantage of Adler32 (or any byte-at-a-time hash) , which is that you can roll up to alignment, then run on 16-byte aligned pieces, then roll down the tail.
August 22, 2010 at 9:18 PM
"But I mean adler/fletcher are vectorizable as a single stream"
Oh yeah that's true. Though that may be true of some of the other mathematical hashes as well.
August 22, 2010 at 9:30 PM
"I think PS3's are actually manufactured from the blood and tears of programmers."
And you don't even have to deal with the RSX! It only does everything... wrong.
August 22, 2010 at 10:20 PM
Also, poking around wikipedia, it looks like common understanding (like the thesis "The Effectiveness of Checksums for Embedded Networks") is that Adler32 and Fletcher32 are basically indistinguishable in terms of behavior (Adler32 slightly theoretically worse, but in graphs shown as essentially identical).
I wonder what the deal is with that.
August 23, 2010 at 3:48 AM
The other thing to look at is 1-byte/1-bit stomps. These are the sort of things that CRC and Fletcher/Adler are generally guaranteed to detect. The hashes aren't normally analyzed on that front, but it wouldn't surprise me if they could be. The biggest concern would be something like Burtle that has more internal state than is visible in the hash, so you might be able to get cases where flipping a bit only affects the invisible state. (If the Burtle one you're looking at is like that.)
Of course whether 1-bit/1-byte flips are plausible in your data I dunno.
August 23, 2010 at 3:56 AM
Oh wait, I found stuff later in that thesis where they underscore that Adler32 is worse than Fletcher32. Apparently historically, Adler32 was invented as an improvement of Fletcher16, unaware that you could just extend Fletcher as-is to 32.
August 23, 2010 at 3:57 AM
" The other thing to look at is 1-byte/1-bit stomps. These are the sort of things that CRC and Fletcher/Adler are generally guaranteed to detect."
Yeah, this is exactly what I did in the "So I figured I'd test on what is more like my real usage scenario." portion of the post.
"The biggest concern would be something like Burtle that has more internal state than is visible in the hash,"
Yeah but the Burtle one is rigorously designed so that all internal state maps to visible bits. In fact I think he specifically gaurantees that one bit flips show up. I guess the issue is how easy is it for two changes to cancel each other.
August 23, 2010 at 9:14 AM
Some addendums to original post.
August 23, 2010 at 11:54 AM
I guess the issue is how easy is it for two changes to cancel each other.
I think even a single 1-bit change could be potentially invisible. The statistical goal is that every 1-bit change flip half the output bits, but there's no requirement that a 1-bit flip of ANY input produce flips in half the bits, hence no requirement they flip any visible bits. The problem is how much testing you'd have to do to find a bad case if you can't prove it, and a question of how meaningful the proof of such properties for adler/fletcher is if you're worried about larger stomps.
Also, that thesis seemed to claim both that Fletcher32/Adler32 can detect any single error up to 16-bits wide (it talked in terms of k-bit-error, where I believe k in this case is 16), but also that they don't detect 0x0000 vs 0xffff, which seems kind of mystifying.
But whatever the actual proven guarantee is, the question of whether such a proven guarantee buys you much for errors-found-in-practice compared to a hash like burtle/fnv is unclear.
August 23, 2010 at 12:59 PM
Thanks for running these tests public.
What are the munge patterns? What do the collisions look like?
August 23, 2010 at 2:51 PM
The munges are the same ones I used for fuzz testing :
http://cbloomrants.blogspot.com/2010/08/08-19-10-fuzz-testing.html
there's a variety of munge methods (single bit flip, stomp byte to zero, stomp byte to random, etc.).
I pick a random munge method and check collision.
I haven't done the study to see which munge types exactly it is that are causing problems for Adler and Fletcher. Maybe I'll do that for thoroughness.
August 23, 2010 at 2:55 PM
BTW the reason why the Fletcher looks so bad in one of those tests is because one of my Fuzz Munge modes is "stomp byte to 00" and another mode is "stomp byte to FF" , and those hit the bad case.
August 23, 2010 at 3:18 PM
So I had thought about how to deal with Fletcher's weird 00/FF problem. Maybe all you do is xor the input words with a counter or maybe some pseudorandom thing which would spread the naughtiness around a bit.
But yeah, screw it, just use Burtle
August 23, 2010 at 10:08 PM
"So I had thought about how to deal with Fletcher's weird 00/FF problem. Maybe all you do is xor the input words with a counter or maybe some pseudorandom thing which would spread the naughtiness around a bit."
Yeah I was thinking the same thing. I mean Fletcher does work okay as long as you don't hit the bad case. If you used an actually pseudorandom generator that changed as you went, it would be pretty hard to hit the bad case. But yeah then your complexity is back up to Burtle levels so fuck it.
August 24, 2010 at 8:56 AM
To put it in perspective, if there is exactly 1 2^16 bit number which can be replaced by another specific 2^16 bit number without detection, then this possibility occurs on 1 in 2^32 possible random 16-bit munges.
In fact there are two cases, since the swap can go in either direction, so the chance is 2^31.
In the grand scheme of things that's not so bad (given that it's a 32-bit checksum). So a randomized version of it might be tolerable -- obviously having the 0x0000 for 0xffff error itself is untenable. But I agree at that point you might as well go with something else.
August 25, 2010 at 12:11 AM
Hi Mr. Bloom,
"Conclusion: Fletcher32 looks perfectly solid and is very fast."
Just check the collision table at:
http://encode.ru/threads/1160-Fastest-non-secure-hash-function!
Regards,
Georgi 'Sanmayce'
November 19, 2010 at 8:20 AM
"Hi Mr. Bloom,
"Conclusion: Fletcher32 looks perfectly solid and is very fast."
"
You didn't read the addenda !
November 19, 2010 at 11:54 AM