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

[Joshua Kinard]

On 10/24/2017 00:11, Michał Górny wrote:
> W dniu wto, 24.10.2017 o godzinie 06∶04 +0200, użytkownik Michał Górny
> napisał:

[snip]

>>> [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.
>>
>> We're talking about really huge (→∞) numbers here. It's not a 'random'
>> attack against one hash. It's an attack that allows to sneak a malicious
>> code with unchanged file size (since we store that too), and no apparent
>> side effects (what's the point of spending up that much resources
>> if the user is going to notice?).
>>
>>> 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.
>>
>> Sounds like an entirely abstract point in time ;-).
>>
>>> 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)
>>
>> No, and that's my point. One hash is perfectly fine.
>>
>> Two hashes are useful for transition purposes. If we take two fast
>> hashes (e.g. proposed SHA512 + BLAKE2B which have similar speed),
>> we can use 2 threads to prevent the speed loss (except for old single-
>> core machines).

Minor clarification, old single core //and// uni-processor.  Some older
machines have multiple physical CPUs that are single-core.  Threading should be
okay on these, as long as the thread count stays under NR_CPUS.

I also have a really old single-CPU system, MIPS (obviously).  Not the fastest
on the block compared to the other equipment I've got, but does anyone know of
any simple timing scripts/programs available that can benchmark some of these
proposed digest hashes?  If they turn out to be reasonably quick on my old
machine, I doubt then that speed will be too much of an issue.

Also, for whatever hashes we ultimately go with, what are considerations for
the userland support for them on non-glibc systems?  E.g., are they provided by
third-party libraries or do they need implementations in
uclibc/uclibc-ng/musl/*?  And what about the Alt/BSD side of things?  I assume
FreeBSD implements this already, but worth verifying with all of the
combinations of arches/libc's/kernels and whatnot.  I mean, there still might
be a lonely m68k install out there...

-- 
Joshua Kinard
Gentoo/MIPS
kumba@g.o
6144R/F5C6C943 2015-04-27
177C 1972 1FB8 F254 BAD0 3E72 5C63 F4E3 F5C6 C943

"The past tempts us, the present confuses us, the future frightens us.  And our
lives slip away, moment by moment, lost in that vast, terrible in-between."

--Emperor Turhan, Centauri Republic