search

tromp / cuckoo

a memory-bound graph-theoretic proof-of-work system
Other
822 stars 173 forks source link

Siphash implementation does not match with standard specification #50

Closed remagpie closed 6 years ago

remagpie commented 6 years ago

According to Section 2.2 of SipHash specification, last byte of of input string should be prefixed with message length.

But according to following line in siphash.h, it seems that message length is not appended. https://github.com/tromp/cuckoo/blob/c79d6605d9b266a5b1dc890239aeaca51a30bf18/src/siphash.h#L48

Is there any reason for this difference?

tromp commented 6 years ago

dear Joon-Mo,

According to Section 2.2 of SipHash specification, last byte of of input string should be prefixed with message length.

But according to following line in siphash.h, it seems that message length is not appended. https://github.com/tromp/cuckoo/blob/c79d6605d9b266a5b1dc890239aeaca51a30bf18/src/siphash.h#L48

Is there any reason for this difference?

Yes; my siphash is specialized to 8 byte nonces, so I wanted to avoid the overhead of encoding the (fixed) message length. Following 2.2 would require processing of a (fixed) 2nd 64 word 0x0800000000000000, unnecessarily doubling the computation effort.

regards, -John

remagpie commented 6 years ago

Thanks for response. Is this modified version of siphash part of the cuckoo cycle's spec? I see it's included in spec document, but I'm curious whether it was intended or not. If it's not, I think SIPHASH_COMPAT flag should make implementation operate as normal siphash.

tromp commented 6 years ago

dear Joon-Mo,

Is this modified version of siphash part of the cuckoo cycle's spec?

Yes; you can see that the siphash24 function in the specification at https://github.com/tromp/cuckoo/blob/master/doc/spec is the specialized one that doesn't encode the fixed input length of 8 bytes.

I see it's included in spec document, but I'm curious whether it was intended or not.

Yes, that's intended.

If it's not, I think SIPHASH_COMPAT flag should make implementation operate as normal siphash.

The SIPHASH_COMPAT flag was introduced when I expanded the siphash keys from 128 bits to 256 bits, and to allow comparison between the old and new results. It was not intended to reproduce the length encoding of the general siphash function. That would be much harder to support across all my implementations, since for instance the AVX2 optimized ones have the siphash functionality spread over multiple locations in the source code.

regards, -John

remagpie commented 6 years ago

Thanks for your explanation!