Subject: Any SHA-1 dependencies?

From: [email-masked] ("Hal Finney")
Date: Thu, 15 Sep 2005 15:58:58 -0700 (PDT)

There are a few places in the OpenPGP spec where we hard-code the use of
the SHA-1 hash.  Given the recent attacks on this hash, we should look
and see if there will be any security weaknesses if it should turn out
that SHA-1 is broken and it becomes easier to generate collisions.

This is actually a pretty complicated issue and it becomes something of a
"can of worms" situation, ie. there are many complexities and subtleties
that arise in the analysis.  Here are some:

 - We don't know how badly SHA-1 might be broken.  Current attacks can
   theoretically generate limited sorts of collisions in (at last
   report) about 2^64 work.  Perhaps this work level will be lowered.
   Perhaps the limitations on collisions may be reduced.  Perhaps even
   more powerful attacks such as preimage attacks (to find data that
   matches the hash of a given value) will become possible.

 - Any hash algorithm might in principle be broken eventually.  A spec
   like OpenPGP can at best allow a choice of hash algorithms.  However
   even then it will be necessary for communicators to decide which
   hash algorithms they trust.  If someone loses confidence in a hash
   algorithm while others are still using it, interoperability is lost.

My approach to these problems is to assume that SHA-1 will be broken
to the extent that collisions can be found with moderate effort, even
collisions with particular structures.  However, preimages will not be
possible.  I think this is a conservative assumption given what is known
about the new attacks.  As far as the second issue, I will outline places
where we hard-code SHA-1, and we should think about what would be involved
in trying to allow for different hash algorithms to be used in place.

Here then are the places we hard-code SHA-1 and the security implications.

5.5.3 Secret Key Packet Formats

This has the option of using a 20-byte SHA-1 hash as a checksum of the
secret key material.  This should be safe.

5.13. Sym. Encrypted Integrity Protected Data Packet (Tag 18)

This uses the SHA-1 hash of the message as a checksum for integrity.
This should be safe.

9.4. Hash Algorithms

SHA-1 is the only MUST implement hash algorithm.  I would recommend
that we include at least SHA-256 as a MUST implement algorithm, for
future security.

11.2. Key IDs and Fingerprints

A V4 key fingerprint is the SHA-1 hash of the key material.  If SHA-1
is broken then it will be possible to create two keys which have the
same fingerprint.  Any places in the spec where fingerprints are used as
pointers to keys, it will be possible for the key creator to substitute
another key he created.  Likewise, the V4 key ID is a substring of the
fingerprint so the same considerations arise.  (However, with respect to
key IDs it is an old problem, since 64 bit key IDs can be made to collide
with only 2^32 work, a very tractable amount.)  Places where fingerprints
are used:

5.2.3.15. Revocation key

The revocation key (designated revoker) is specified via key fingerprint.
This should be safe since the key holder is trusted to perform this
service, so if he created a key collision he would only be able to
transfer this power among keys he controlled.

It is not an OpenPGP issue, but PGP uses signature subpacket 10 as an
additional decryption key indicator, and this is also done via a key
fingerprint.  Similar considerations apply as for the designated
revoker.

With regard to key IDs, these are used in the following places:

5.1. Public-Key Encrypted Session Key Packets (Tag 1)

The key ID indicates which key can decrypt the message.  Ability to
create keys with colliding key IDs should not cause security problems.

5.2.2. Version 3 Signature Packet Format

The key ID of the signing key is stored in the V3 signature packet.
Ability to create keys with colliding key IDs should not cause security
problems.

5.2.3.5. Issuer

This is the V4 key ID.  Same situation as for V3.  In fact we usually
put this signature packet in the unhashed region.

5.4. One-Pass Signature Packets (Tag 4)

Same situation as above.

Summary

None of the hard-coded uses of SHA-1 in the OpenPGP spec appear to
introduce security problems, even if creating SHA-1 collisions becomes
easy.  This analysis does not cover the case of finding pre-images.

The one change we might consider is to expand the set of MUST algorithms
beyond SHA-1 since the community is shifting away from that hash.

In the longer term it would be desirable to consider parameterizing the
few places where SHA-1 is hard-coded, to take a hash algorithm specifier.
This will allow us to avoid even the appearance of weakness which may
be of concern to potential users, as SHA-1 becomes deprecated in a wide
range of products and protocols in future years.

Hal Finney

---

From: [email-masked] (Daniel A. Nagy)
Date: Fri, 16 Sep 2005 03:26:25 +0200

Hal,

Basically, what you are proposing is a sort of universal hash function,
where the hash algorithm identifier is followed by the hash computed using
that particular algorithm.

This is potentially very dangerous, as it does not follow several
assumptions about a good hash function. Namely the hash value is not
unique and parts of the hash function are not uniformly strong.

On the other hand, there is a fair chance that SHA1 (and even MD5, though
its 128 bit length is a problem by itself) might be fixed. The known
collision attacks are based on collisions in the compression function
and it seems that in both cases the set of "problematic" blocks is actually
very sparse and easily detectable. This allows for several security
improvements: first, (and it has already been done, AFAIK) one can
immediately detect a data stream as one that is likely to be an
attempted attack on the hash function, second, one might create a "fixed"
compression function that does something different for problematic blocks,
thus yielding a hash function that gives the same output as SHA1 for the
vast majority of inputs, while being resistant against SHA1 collisions.

The detection result is very likely to be presented at Eurocrypt2006, and
there's a chance that the fix will be presented too.

The sparsity of problematic blocks also implies (although this is not
strictly within the scope of the discussion) that key-id binding signatures
might collide only on the key part (*), which is not dangerous. If the above
mentioned sanity check is performed, it removes even the non-dangerous key
collision as a possibility.

Also remember, that collisions are of concern only if the data is to be signed by
someone different from its author. There are protocol-level safeguards
against this possibility, though employing these would require a major
overhaul of OpenPGP, which in the light of the above is not warranted (yet).
Someday, however, we might very well be forced to introduce version 5
signatures for certification and other notarial purposes. It is better to
postpone that as long as possible, because important discoveries with
immediate consequencnes on design and standardization decisions might lay ahead.

So, I would recommend sticking to SHA1 for the time being, as there is no
hash function with a better design at this point. Alternatives that belong
to the same MD4 family of hash functions (e.g. the now-fashionable
RIPEMD-160) have not been attacked only because SHA1 was a more rewarding
target.

Now, moving to 256-bit hash functions in order to have a built-in "safety
factor" keeping the hash-function safe even if it's partially broken, seems
to be inconsistent with market-economies. In our case it is particularly
relevant, because the standard we are designing is not enforced, leaving the
choice to the user.

The thing is that partially broken security products are a tough sell even if
the remaining part is still secure enough. It is pretty clear from your
post that you _are_ concerned about this. Let me digress a bit:

In the USSR, it was okay to slash development costs by building in safety
factors, so that even if the hash function or the block cipher turned out to
be weaker than the designers originally thought, they would be still secure
enough. Hence the 256-bit key length of the standard soviet block cipher
(GOST 28147-89) which also doubles as the compression function of their
standard hash function (standardized later as GOST 34.11-94). For government
use (**) and for use in a planned economy this was the most rational way of
designing the system: quick, cheap and a little dirty. In market economies,
this approach won't fly, because as soon as your product is discredited by
being partially broken, you will have to switch anyway, so cheap development
with safety factors won't save you money in the long run. Hence, it's not a
rational approach to cryptographic algorithm design and indeed, we don't see
it in successful products in the free market. It is important to emphasize
that it is not because your customers are somehow dumber in a market economy
but because in addition to your development costs, they also have to bear
the cost of choosing the right product for themselves (this cost does not
occur in planned economies -- in certain cases, it can be a significant
saving), and they are rational about minimizing it by not touching anything
that has been discredited in any way -- they simply cannot afford to behave
otherwise (in most cases).

Back on topic, this is why I would advise against moving to 256-bit hashes
based on the MD4 design. Yes, it would add some security against hypotetical
ultra-motivated adversaries flush with resources, but you are interested in
these not because they are actually threats but because you are catering to
paranoid customers. Those would sneer at a partially broken SHA256 just as
they sneer at a partially broken SHA1. So, you will have to switch again
very soon, without gaining anything from the previous switch. It's not
rational behavior, especially in standardization.

Thus, my recommendation would be to postpone the discussion until more is
known, to avoid swift moves and stick to SHA1 for the time being. Maybe a
footnote would be warranted to explain why it's still safe to do things the
way we do them.

Now, I have a separate set of grievances about the v4 private key packet format
and the way v4 key fingerprints are being calculated, but that has very
little to do with the recent developments around our once-favorite hash
function. In a separate post, I will explain why I would like to introduce a
new version of key packets (both public and private), and once we embark on
designing new packet formats, we can address the use of hash functions in
that context as well, but again, it's a separate topic.

(*) It is impossible to trick someone into binding a sane-looking unseen UID
to a given public key by presenting him with another sane-looking UID that
would collide with the unseen one for signature.

(**) There is evidence suggesting that the mentioned algorithms were in
government use long before having been released to the public as industry
standards. Probably since the early eighties or even earlier.

Bests,

-- 
Daniel

---

From: [email-masked] ("Hal Finney")
Date: Thu, 15 Sep 2005 19:33:25 -0700 (PDT)

> unique and parts of the hash function are not uniformly strong.

I agree that is one way to look at it.  In a hypothetical future key
fingerprint system, there would be multiple kinds: a SHA-1 fingerprint,
a SHA256 fingerprint, a RIPEMD160 fingerprint, and so on.  So it is
non-unique.  The idea is that if SHA-1 or some other hash became broken,
the other kinds of fingerprints could be used, without revising the spec.
Of course an attacker could replace a fingerprint with one based on an
old, weak hash, but it would ultimately be up to the verifier to decide
which hashes he would trust.

In the event of a break, switching over to a new hash would be a
potentially costly operation but it would not require issuing a new spec.
I'm not sure what dangers you see over a system which would require
changing both implementations and specifications.

> there's a chance that the fix will be presented too.

I will look forward to seeing that.  I wonder if it might be discussed
at the NIST Halloween "hash bash", it sounds like it would be of great
interest there.

Without knowing the details it is hard to comment, but in general I
would worry that any detection system might be "brittle" and possibly
small changes to the attack method might bypass the detector while still
producing collisions (perhaps somewhat more expensively).  For example
the Wang attacks always use the same initial differential, but there
is no reason they could not work with slightly different differentials,
I think.  She chose the best one but I gather that there are others that
weren't too bad.  A detection system tuned too closely to known attacks
might miss these alternatives.

> collision as a possibility.

I also remember Eli Biham last year at Crypto demonstrating very textual
looking collisions on truncated SHA-1.  His collisions were composed
of ascii characters and even English words.  Granted, truncation makes
a world of difference in the ease of the attack but I wonder if we can
be sure that the full SHA-1 attacks can never be improved in this way.

> immediate consequencnes on design and standardization decisions might lay ahead.

Yes, there have been strong debates in online forums for example about
changing signature procedures so that the signer prepends a block of
data of his choice to the message to be signed, in case the message is
prepared by someone else.  There seems to be no consensus on whether
this is on balance a good idea or not.

> RIPEMD-160) have not been attacked only because SHA1 was a more rewarding

I didn't recommend stopping using SHA-1.  In fact my only actual
recommendation was to include SHA256 as another MUST hash, in case SHA-1
gets broken more badly (and in the hope that SHA256 will be OK).

> relevant, because the standard we are designing is not enforced, leaving the

In general, though, it is risky to use non-MUST hashes in your
signatures, for interoperability reasons.  Of course we have only limited
leverage over this via the spec, and as you note the market may force
implementations to move to SHA256 regardless of whether it is MUST or not.

[Skipping on a bit]

> rational behavior, especially in standardization.

So, are you predicting that SHA256 will have at least theoretical breaks
of its own?  The people I have talked to seem quite non-committal about
this prospect.  No one can rule it out but most people say it should be
stronger than SHA-1 and more resistant to this kind of attack.

> footnote would be warranted to explain why it's still safe to do things the

Again, the only thing I recommended was to add SHA256 as a MUST.  The only
MUST-implement hash we have now is SHA-1.  What do you think of that change?

> that context as well, but again, it's a separate topic.

I have another change to suggest as well, which will also go into a future
message.

Thanks for your comments, they are very interesting and helpful.

Hal Finney