zips: Computation of hSig requires 1 byte more than a BLAKE2b input block

For the record, I disagree.

I think this is an example of the dangers of “provable security” that people like Koblitz, Menezes, and DJB have warned about.

Our options here are between:

a) a more complicated protocol which rests on the collision-resistance of SHA-256-compression function, or

b) a simpler protocol which rests on the collision-resistance of BLAKE2b-truncated-to-256-bits.

I assert, and I think Daira would agree, that the danger of a bug in the “more complicated protocol” part (or in some unforseen interaction between that part and something else) is orders of magnitude greater than the danger of a failure of the “collision-resistance of BLAKE2b-truncated-to-256-bits” part.

In fact, the collision-resistance of BLAKE2b-truncated-to-256-bits is better than the collision-resistance of SHA-256-compression-function, according to the best modern cryptanalysis [*].

Therefore option “a” above comes with a substantially increased danger (the more complicated protocol) plus a mildly increased danger (the worse primitive), compared to option “b”, but in return for that trade-off, it offers the possibility that its security proof (a.k.a. “security reduction”) can be grounded in a property which is more familiar as the grounding for these sorts of reductions.

If I understand the criticisms of the “provable security” approach that have been leveled by Koblitz, Menezes, and DJB (which is doubtful), this is the sort of decision that they would warn against.

[edited to add] That said, there is real value in the positive trade-off that option “a” is offering us: that the security proof rests on a more widely-appreciated property, even if that property is slightly less certain of holding up.

I believe we can make this secure either way, and I’m content to let Daira make this decision, provided that we have intensive scrutiny of the “more complicated protocol” part, if she chooses option “a”. Also I’m very curious if this comment causes her to change her mind again.

[*] There is no reason to think that BLAKE2b-truncated-to-256-bits is less safe than SHA-256-compression function against collisions, and indeed there is substantial reason to think that it is more safe, because the best known attacks on SHA-256 leave less of SHA-256 untouched than the best known attacks on BLAKE2b. (This is called “security margin”.)

And, as Samuel mentioned in https://github.com/zcash/zips/issues/36#issuecomment-204111300, those “best known attacks” are not only collision attacks, in which case they would not directly apply to the question of the relative strengths of these two options “a” and “b” above. Instead they are distinguisher attacks (of various kinds) that do apply directly to this question.

Here is an example:

“Second-Order Differential Collisions for Reduced SHA-256” Biryukov, Lamberger, Mendel, Nicolić 2011 http://www.iacr.org/archive/asiacrypt2011/70730269/70730269.pdf

Note especially the discussion about distinguishers in the Introduction, which echoes sneves’s comment above, and this quote: “the attacks give a clear indication that if we compare the security of SHA-256 to the security of the third round SHA-3 candidates [BLAKE, Grøstl, JH, Keccak, and Skein], in the this setting, then SHA-256 has one of the lowest security margins.”

This paper is comparing SHA-256 against BLAKE here, and saying that BLAKE has a greater security margin than SHA-256 when using “best known distinguisher attack” as the metric. As sneves pointed out above, BLAKE2 appears to be even stronger than BLAKE against near-collisions.

I have no idea if this is the current best attack on SHA-256. Perhaps sneves knows. This is just one that I happened upon with a little searching.

I don’t know much about BLAKE2 but the front page of the website says “BLAKE2b (or just BLAKE2) is optimized for 64-bit platforms—including NEON-enabled ARMs—and produces digests of any size between 1 and 64 bytes.” Can we not just choose the output length to be 32 bytes?