3
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Paya
    Commented Jun 6, 2015 at 15:55
  • 1
    $\begingroup$ @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) $\endgroup$
    – poncho
    Commented Jun 6, 2015 at 17:07
  • $\begingroup$ 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). $\endgroup$
    – Frederick Nord
    Commented Jul 27, 2016 at 13:49
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Commented Jul 27, 2016 at 14:00
1
$\begingroup$

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

http://www.google.com/patents/US20130262421

Improve this answer
$\endgroup$
6
  • $\begingroup$ The patent explicitly says "non-cryptographic". Your answer seems to suggest the opposite. $\endgroup$
    – otus
    Commented May 17, 2016 at 4:46
  • $\begingroup$ No, I didn't used any word containing "crypto". I've said Marvin32 is resistant to Hash Flood attack. And it really is. Function does not ought to be "crypto-blah-blah-blah" to be safely used in hash tables, cause hash-function result is not returned to attacker in this use case. It just ought to be resistant to Seed Independent Collisions. $\endgroup$
    – funny_falcon
    Commented May 17, 2016 at 7:49
  • $\begingroup$ The question asked about whether it is PRF. Also, resistance to seed independent collisions (which it may lack, see the final paragraph of the other answer) is not necessarily enough, because an attacker can find out information about the result through timing (which values collided modulo something). Anyway, the pointer to the patent is useful. $\endgroup$
    – otus
    Commented May 17, 2016 at 14:54
  • 1
    $\begingroup$ Resistance to seed independent (multi)collisions is enough. @poncho didn't test and didn't read algo carefully. With non-zero seed avalanche is really great (though with zero seed it is awful). And it outputs not "entire state", but xor-ed halves of state (the same way SipHash outputs xor-ed quarters of state. Do you think SipHash is crackable in O(2^32) time?) Returning to Seed Independent Multicollisions: attacker may measure time of insertion of a key (so that, length of a collision chain), but he cannot recover Seed, so he cannot create new key that falls into same chain. $\endgroup$
    – funny_falcon
    Commented May 24, 2016 at 18:48
  • 3
    $\begingroup$ You said: "Normal use of the hash in a hash table leaks information about the outputs." May you tell me more about? what information leaks? What amount of information is enough to find preimage? (especially, for function like Marvin32) Is there any publication on this? $\endgroup$
    – funny_falcon
    Commented May 25, 2016 at 17:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.