Re: [Monotone-devel] Fwd: SHA-1 broken

[Jack Lloyd]

Markus pointed out some of this may be of interest to the list in
general.

----- Forwarded message from Jack Lloyd <address@hidden> -----

From: Jack Lloyd <address@hidden>
To: Markus Wanner <address@hidden>
Date: Wed, 29 Jul 2009 13:36:25 -0400
Subject: Re: [Monotone-devel] Fwd: SHA-1 broken

Hi Markus,

In attempting to clean out my mailbox, I noticed this email which I had
neglected to reply to earlier:

On Mon, May 11, 2009 at 07:52:33AM +0200, Markus Wanner wrote:

>> In my view monotone has much more serious security issues WRT it's
>> authorization design
>
> Can you quickly elaborate on this, please?

The major issues I see with Monotone's auth system are as follows:

- Keys identified by name rather than by hash. This makes meaningful
  key revocation and key rollover very difficult. It also makes it
  hard to use more than one key at a time for different projects.

- Little support for centralized trust. In many environments it would
  be very useful to bootstrap off existing trust structures (PGP web
  of trust or locally administered PKI).

- Non-distributed trust - the trust hooks exist, effectively, outside
  of the monotone distributed system. This means out of band data must
  be kept in sync.

- Per-db rather than per-branch trust.

Policy branches, should that ever occur, would fix some but not all of
these problems.

A system that I think that could inform many enhancements to
Monotone's security is OpenCM. Much of this design is only poorly
documented, but the paper "Access and Integrity Control in a
Public-Access, High-Assurance Configuration Management System" has
many good ideas. (http://opencm.org/docs.html)

One design decision I think OpenCM did well was use self-signed X.509
certificates for keys, and then using SSL with client certificates for
authentication. This provides a standard binding of key bits and
metadata, allows keys to be revoked, and (though it was never
implemented) allows for per-project PKIs to issue developer
certificates rather than deal with manual key import/trust
configuration.

> Agreed again. However, keeping the nuskool and the atomic-cert (or
> super-cert) idea in mind, there might be several flag days ahead of us
> anyway. ;-)   Maybe we can combine some?
>
> I'd also tend to make the choice of hash function configurable, so as to
> prevent further flag days in the future.

This might be a good idea.

My experience with protocol algorithm agility suggests that if this is
the desirable path, it would be best to support 2 different hashes
right out of the gate - this ensures that everything is good to
go. Otherwise it is too easy to miss a subtle situation. An obvious
pairing would be SHA-512 (or perhaps SHA-384) and a SHA-3 candidate.

WRT atomic-cert, it would certainly make sense to do the switch at the
same time - if you are resigning everything anyway, might as well do
it with the new hash.

>> SHA-3 will likely be much faster than any SHA-2
>> variant on current/future desktops; many of the submissions are slower
>> than SHA-2, but several are or could be faster, and the fastest ones
>> will tend to win, perhaps even if a slower and more conservative
>> design is in the running (at least going off the results of the AES
>> competition).
>
> Hm.. how about simply using SHA-512 from your fine library? Or is that
> affected as well?

No, SHA-256 and SHA-512 are not affected by any currently known
attacks. Either would probably be fine as a SHA-1 replacement.

However there are some substantial advantages to using a SHA-3
candiate instead.

1) Speed. The only SHA-3 candidate currently in botan is Skein-512,
since that seems to me the most likely to win, but other round 2
candidates including Keccack, CubeHash (with the right parameters),
and Blue Midnight Wish, are also very fast [1]. Comparing SHA-2 and
Skein on my 2.4 GHz Core2:

SHA-160:                   297.03 MiB/sec
SHA-256:                   102.83 MiB/sec
SHA-512:                   154.44 MiB/sec
Skein-512:                 239.60 MiB/sec

[1] http://skein-hash.info/sha3-engineering

2) Avoiding problems inherent to the Merkle-Damgard structure. In
particular, length extension attacks. I have not studied Monotone's
hash usage well enough to be sure one way or another if length
extension attacks can be used profitably, but it certainly seems
plausible. It is likely that any SHA-3 will prevent such
attacks. Current systems like Tahoe avoid the possibility by using
hash constructions like SHA-256d, which is:
  SHA-256d(x) = SHA-256(SHA-256(x))

3) Hash personalization. Monotone uses SHA-1 for many different uses.
This is potentially problematic in that two hashes computed in
different contexts might have identical inputs, and would thus
collide. Personalization (or tagging) are methods which generate from
the single hash a family of related functions, for instance on hash
being used for content data, another for revision signing, etc.  Skein
and some of the other SHA-3 candidates support this directly. It
could also be created with a construction, for instance

  H(tag, msg) = H(H(tag) || msg)

which is slightly less efficient than most of the schemes used by
hashes which implement this functionality natively, but would suffice.

Both (2) and (3) avoid attacks which might not apply at all to
monotone. The advantage of avoiding them entirely is that it obviates
any need for analysis.

-Jack

----- End forwarded message -----