[Cryptography] Are Momentum and Cuckoo Cycle PoW algorithms broken?

Zooko Wilcox-OHearn zooko at leastauthority.com
Mon Jul 13 07:59:54 EDT 2015


One detail that bothers me is that SipHash is being used in Cuckoo PoW
in a way that the attacker gets to control all the inputs to SipHash,
and that is not what SipHash was designed to resist. SipHash was
designed to resist an attacker who doesn't control — and actually
doesn't even *know* — the key. There's a possibility (although it
seems unlikely to me) that an attacker could exploit something about
the way Cuckoo uses SipHash to find Cuckoo solutions faster than by
treating SipHash as a random oracle.

I expressed this concern of mine multiple times to John Tromp in
private communication, and he was not persuaded that it is a real
problem, and he said that the CPU performance is important. I can see
his point: I wasn't able to figure out how to exploit Cuckoo's use of
SipHash after spending a few minutes peering at it. But I'm not a good
cryptanalyst, and the people who are good cryptanalysts have never, to
my knowledge, evaluated SipHash's strength under such conditions.

I would suggest someone like Bill Cox who is experimenting with such
constructions could replace the use of SipHash in Cuckoo with a
reduced-round version of Blake2. By reducing the rounds, that means
you are no longer covered by the positive cryptanalytic results on
Blake2 (https://blake2.net/#cr), but on the other hand those
cryptanalysts *have* studied reduced-round versions of Blake2 (and
Blake, and ChaCha, and Salsa20), and that they have published any
interesting weaknesses that they found in reduced-round versions of
Blake2.

So, I'd suggest that if full Blake2 is too CPU-intensive for this
usage, then reduce the rounds of Blake2, but keep as many rounds as
you can tolerate. But definitely not fewer than 3 rounds. Or 4. Maybe
5. ☺ Hopefully that would make it close enough in performance to
SipHash for this usage.

Regards,

Zooko


More information about the cryptography mailing list