Folks:
We're going to be deploying a new crypto scheme in Tahoe-LAFS next
year -- the year 2010. Tahoe-LAFS is used for long-term storage, and
I won't be surprised if people store files on Tahoe-LAFS in 2010 and
then rely on the confidentiality and integrity of those files for
many years or even decades to come. (People started storing files on
Tahoe-LAFS in 2008 and so far they show no signs of losing interest
in the integrity and confidentiality of those files.)
This long-term focus makes Tahoe-LAFS's job harder than the job of
protecting transient network packets. If someone figures out in 2020
or 2030 how to spoof a network transaction that you sent in 2010 (see
[1]), it'll be far too late to do you any harm, but if they figure
out in 2030 how to alter a file that you uploaded to a Tahoe-LAFS
grid in 2010, that might harm you.
Therefore I've been thinking about how to make Tahoe-LAFS robust
against the possibility that SHA-256 will turn out to be insecure.
A very good way to do this is to design Tahoe-LAFS so that it relies
as little as possible on SHA-256's security properties. The property
that seems to be the hardest for a secure hash function to provide is
collision-resistance. We are analyzing new crypto schemes to see how
many security properties of Tahoe-LAFS we can continue to guarantee
even if the collision-resistance of the underlying secure hash
function fails, and similarly for the other properties of the secure
hash function which might fail [2].
This note is not about that design process, though, but about how to
maximize the chance that the underlying hash function does provide
the desired security properties.
We could use a different hash function than SHA-256 -- there are many
alternatives. SHA-512 would probably be safer, but it is extremely
expensive on the cheap, low-power 32-bit ARM CPUs that are one of our
design targets [3], and the output size of 512 bits is too large to
fit into Tahoe-LAFS capabilities. There are fourteen candidates left
in the SHA-3 contest at the moment. Several of them have
conservative designs and good performance, but there is always the
risk that they will be found to have catastrophic design flaws or
that a great advance in hash function cryptanalysis will suddenly
show how to crack them. Of course, a similar risk applies to SHA-256!
So I turn to the question of how to combine multiple hash functions
to build a hash function which is secure even if one or more of the
underlying hash functions turns out to be weak.
I've read several interesting papers on the subject -- such as [4, 5]
and especially Robust Multi-Property Combiners for Hash Functions
Revisited by Marc Fischlin, Anja Lehmann, and Krzysztof Pietrzak
[6]. The good news is that it turns out to be doable! The latter
two papers show nice strong theoretical results -- ways to combine
hash functions so that the resulting combination is as strong or
stronger than the two underlying hash functions. The bad news is
that the proposal in [6] builds a combined function whose output is
twice the size of the output of a single hash function. There is a
good theoretical reason for this [4], but it won't work for our
practical engineering requirements -- we need hash function outputs
as small as possible (partially due to usability issues)
The other bad news is that the construction proposed in [6] is
complicated, underspecified, and for the strongest version of it, it
imposes a limit on the length of the inputs that you can feed to your
hash function. It grows to such complexity and incurs such
limitations because it is, if I may call it this, too theoretical.
It is designed to guarantee certain output properties predicated on
minimal theoretical assumptions about the properties of the
underlying hash functions. This is a fine goal, but in practice we
don't want to pay such a high cost in complexity and performance in
order to gain such abstract improvement. We should be able to hedge
our bets and achieve a comfortable margin of safety with a very
simple and efficient scheme by making stronger, less formal, but very
plausible assumptions about the underlying hash functions. Read on.
I propose the following combined hash function C, built out of two
hash functions H1 and H2:
C(x) = H1(H1(x) || H2(x))
The first observation is that if H1 is collision-resistant then so is
C. In practice I would expect to use SHA-256 for H1, so the
resulting combiner C[SHA-256, H2] will be at least as strong as
SHA-256. (One could even think of this combiner C as just being a
tricky way to strengthen SHA-256 by using the output of H2(x) as a
randomized salt -- see [7].)
The next observation is that finding a pair of inputs x1, x2 which
collide in *both* H1 and in H2 is likely to be much harder than
finding a pair of inputs that collide in H1 and finding a pair
