# Cryptanalysis of Marvin32 compared to SipHash

So I am curious about the security analysis of Marvin32, the randomized hash algorithm used in .NET (to prevent hash-table DoS). I found the source code here: marvin32.h, marvin32.c.

At first glance, the construction looks really similar to that of SipHash, but:

• Marvin32: 1 round per block and 2 finalization rounds
SipHash: 2 rounds per block and 4 finalization rounds
• Marvin32: 64-bit key space (seed)
SipHash: 128-bit key space

Nevertheless, the construction seems so similar that it looks like MS was trying to build something like a PRF. The 64-bit key space is certainly too small for a general-purpose PRF, but assuming that 64-bit is enough, is this a secure PRF? Do you see anything else wrong with the construction (key expansion, hash)?

To me it looks like the rounds are too short for this to be a crypto-grade PRF (again, ignoring the key-space for a moment), but maybe it's enough to thwart the hash-table DoS assuming the key is changed from time to time using a CSPRNG?

It isn't a good cryptographical PRF (and, to be fair to the inventor, he never claimed it was).

Marvin32 starts with a secret state, and processing the message and the state to give a new state, and at the end, outputs the state. However, it outputs the entire state, and the state update process is invertible (if you know the message); hence if you know the message and the output, you can reconstruct the original state (and with that, compute the output for any other arbitrary message).

Even if we ignore the state recovery attack, there are also issues with propagating deltas from the final message bits into the output; if we take a message and flip a bit in the final byte, it wouldn't appear that that change gets propagated to all the bits of the output with probability anywhere close to 0.5 (this effect is stronger if the message length isn't a multiple of 4); this raises questions whether it's a good statistical PRF.

• Thanks for the answer. The second part seems really bad, as it's pretty much an invitation for someone to find collisions in Marvin32 just like they did in MurmurHash. I guess the good part is that Marvin32 is internal in .NET framework, so they can just replace it with something that works once it gets broken.
– Paya
Jun 6, 2015 at 15:55
• @Paya: actually, it would appear that you can find preimages in $O(2^{16})$ work (trivial), that is, given a target hash value, find something that hashes to that. You do need a single message/hash pair (needn't be the target hash) to allow us to compute the initial state. Once there, we can do a fairly standard meet in the middle attack, looking for a colision on s1 (and at a place where add a value to s0) Jun 6, 2015 at 17:07
• Can you elaborate what "it" is in your first sentence ("It isn't a good cryptographical PRF ")? I assume it's Marvin32, but it isn't entirely clear (to me). Jul 27, 2016 at 13:49
• @FredrickNord: The question was about Marvin32, and hence it's a fairly decent guess that 'it' in the answer refers to Marvin32. In this answer, the first paragraph is the summary answer to the question; the second and third paragraphs in the answer expands on why that is, that is, why 'it' isn't a good cryptographical PRF... Jul 27, 2016 at 14:00

Looks like Marvin32 is a part of a patent :-) And Microsoft really do believe it is resistant to Hash Flood attack.