[FFmpeg-devel] [PATCH 2/5] fate: avoid framemd5, use framecrc its faster

[Michael Niedermayer]

On Thu, May 09, 2013 at 01:28:43PM +0200, Reimar Döffinger wrote:
> On 09.05.2013, at 13:14, Michael Niedermayer <michaelni at gmx.at> wrote:
> > On Thu, May 09, 2013 at 07:58:45AM +0200, Reimar Döffinger wrote:
> >> On 09.05.2013, at 02:12, Michael Niedermayer <michaelni at gmx.at> wrote:
[...]
> >>>> It also suggests that they may fail to detect e.g. padding changing
> >>>> from 0x00 to 0xFF. This might be relevant to the valgrind memory
> >>> 
> >>> do you have a example of such colission with changed padding ?
> >> 
> >> Paper said it can't distinguish long runs of those since they are both 0 in one's complement, but I don't feel like doing my own research.
> > 
> > are you talking about fletcher or adler ?
> 
> They wrote both are based on one's complement and thus have the same issue.

iam still curious about an example


> 
> >> Well, MurMur3 has had at least some use, and it has a fast x64_128 method that at least gives us 128 bit instead of just 32.
> >> Don't know if you feel it's worth spending time implementing it in FFmpeg though, I probably won't have time :-(
> >> http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp
> > 
> > 5th line of this says:
> > // Note - The x86 and x64 versions do _not_ produce the same results, as the
> > 
> > any other suggestions ?
> 
> Why is that a problem? The hash optimized for 32 bit and only supporting 32 or 64 bit outputs has a different result than the one that gives up to 128 bit output and runs best on 64 bit.
> Using the 64 bit version would probably mean a performance hit on a 32 bit system, but even there it should still be a lot faster than MD5 and I presume you mostly run 64 bit.

ok i looked more at murmur3 (x86 32bit 128bit hash)
there are 2 things on it that dont look sane

First, before the finalization step it has 128bits of state
the finalization then (excluding the first line) does nothing to
improve collisions, any colission that existed before, exists
afterwards. Aka the code is useless and just might make the hash
look more random to human eyes. But at the same time it makes
interrupting and continuing the checksum calculation annoying

The second thing is, a similar permutation exists on the input,
again for any collision that exists with this part of murmur3:
k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2;
k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3;
k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4;
k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1;

you also have a collision without these 4 lines (with the input
bytestream changed accordingly)

so while i dont dispute murmur3 works well, its design looks a bit
fishy to me

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20130509/fc6377bd/attachment.asc>