[tahoe-dev] Fwd: implementing Comb4P for serious use

[Zooko O'Whielacronx]

---------- Forwarded message ----------
From: Anja Lehmann <anja.lehmann at minicrypt.de>
Date: Wed, Apr 21, 2010 at 5:35 AM
Subject: Re: implementing Comb4P for serious use
To: Zooko O'Whielacronx <zookog at gmail.com>


Hi Zooko,

thanks for your email. It would indeed be great to see our combiners
used in practice or even in an IETF proposal! Just a few questions
from my side ... who is actually "behind" that project? Is is just an
open community or is there any company involved? And will all the
implementations be open-source?

I'm unfortunately quite busy these days, so I couldnt read all
discussions in full detail yet, but I can make some remarks:

i) There was the question on how to handle different output lengths of
H0,H1 in the Feistel part of the Comp4P combiner.

As the Feistel part is essential for the PRF property, one has to
ensure that the XOR-Combiner used as round function is a pseudorandom
function. Thus, when dealing with different output lengths, one has to
truncate the longer output to the size of the shorter one. Otherwise
the security could get lost, if there would be a PRF attack against
the longer hash function. As a theoretic counter example why for
instance padding the output of the shorter hash function (here H0),
i.e. (H0 || 0...0) xor H1
doesnt work, consider the case where H1 is an insecure PRF that always
ends with the '1' bit. Then also the XOR combination would be insecure
independent of the strength of H0. Thus, the padded XOR construction
is not a PRF anymore which is the necessary assumption for our Comp4P
Combiner to be PRF as well.

As it was already mentioned in the mailing list, the easiest way would
be to combine hash functions that already have the same output length.
(Or using SHA-3 candidiates, as they have to support variable output
lengths?)


i) Another issue was: It would also be interesting to find out/study
what properties Comb4P maintains under truncation of the final output.

>From a theoretical point of view, truncating the final output harms a
lot of security properties. It was shown that by truncating the output
of a collision resistant hash function (considered as black-box) one
would lose the collision-resistance guarantee [1]. A similar problem
seems to exist with TCR and the MAC property as well. On the other
hand, it is known that the PRF-property is closed under truncation,
i.e., any truncated output of a PRF is still a pseudorandom value.

[1] Krzysztof Pietrzak. Compression from Collisions, or why CRHF
Combiners have a Long Output. CRYPTO 2008.


Feel free to communicate my remarks to others interested. I'll try to
follow the discussions in the mailing list, and I would be happy to
help whenever issues concerning the specification of our combiners
arise.


ciao,
anja


--
Darmstadt University of Technology

Adr.: Hochschulstraße 10 | Tel: +49 6151/16-5416
     64289 Darmstadt    | Fax: +49 6151/16-6036
Web:  www.cdc.informatik.tu-darmstadt.de/~alehmann/