Re: [gentoo-dev] Manifest2 hashes, take n+1-th: 3 hashes for the tie-breaker case

[Robin H. Johnson]

On Mon, Oct 23, 2017 at 01:33:15PM +0200, Michał Górny wrote:
> Dnia 23 października 2017 10:16:38 CEST, "Robin H. Johnson" <robbat2@g.o> napisał(a):
> >On Fri, Oct 20, 2017 at 05:21:47PM -0500, R0b0t1 wrote:
> >> In general I do not mind updating the algorithms used, but I do feel
> >> it is important to keep at least three present. Without at least
> >three
> >> (or a larger odd number) it is not possible to break a tie.
> >>
> >> That may ultimately be beside the point, as any invalid hashes should
> >> result in the user contacting the developers or doing something else,
> >> but it is hard to know.
> >I'm dropping the rest of your email about about exactly which hashes
> >we're bike-shedding, to focus on the number of hashes.
> >
> >I agree with your opinion to have three hashes present, and I've give a
> >solid rationale with historical references.
> >
> >The major reason to have 3 hashes, is as a tie-breaker, to detect if
> >there was a bug in the hash somehow (implementation,
> >compiler/assembler,
> >interpreter), and not the distfile. This also strongly suggests that 3
> >hashes should have different construction.
>
> 1. How are you planning to distinguish a successful attack against two hashes from a bug in one of them?
>
> 2. Even if you do, what's the value of knowing that?
[BOBO06] is relevant research here, I cited it in the work that went into
GLEP59, the last time we updated the hashes. The less-technical explanation of it is:
"If you can express the output of H1(x)H2(x) in LESS bits than the combined
output size of H1,H2, then the attacks get a little bit easier"

Some important pieces from it:
[J04] "showed that the concatenation of two Merkle-Damgard functions is not
much more secure than the individual functions.", but this holds ONLY if
the hash functions chosen are of the same construction (MD).
Choosing hashes with different constructions (Merkle-Damgard, HAIFA,
Sponge) is important, and given a black box environment, 

The original mail reached the same approximate decision, just to look
for diverse hashes, but decided that 2 was enough.

Q: What are the odds of a simultaneous successful attack against two hashes? 
A: IDK, but if the hash functions are truly independent, it must be provably
   lower than the odds of an attack against a single hash.

Q: What's the big difference between a bug and a successful attack in a hash?
A: Bugs are more likely initially, and attacks come later.

All of that said, is there really a significant long-term gain in
multiple hashes? (setting aside the short-term advantage in a transition
period for changing hashes)

> >2009: https://bugs.gentoo.org/255131
> >app-crypt/mhash-0.9.9 segfaults with NULL digest in whirlpool/snefru
> >(portage uses python-mhash bindings)
> How is this one relevant? AFAICS it did not cause wrong result.
It output inconsistent garbage for the hash in at least one case that I
recall.

[BOBO06] Boneh, D. and Boyen, X. (2006). 
"On the Impossibility of Efficiently Combining Collision Resistant Hash Functions"; 
Proceedings of CRYPTO 2006, Dwork, C. (Ed.); 
Lecture Notes in Computer Science 4117, pp. 570-583. 
Available online from: http://crypto.stanford.edu/~dabo/abstracts/hashing.html

[J04] Joux A. (2004).
"Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions". 
In: Franklin M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. 
Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg
https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf

-- 
Robin Hugh Johnson
Gentoo Linux: Dev, Infra Lead, Foundation Asst. Treasurer
E-Mail   : robbat2@g.o
GnuPG FP : 11ACBA4F 4778E3F6 E4EDF38E B27B944E 34884E85
GnuPG FP : 7D0B3CEB E9B85B1F 825BCECF EE05E6F6 A48F6136