[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Any SHA-1 dependencies?



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