hash function serves an auxiliary role in a number of cryptography
utilities, notably OpenPGP, where it is used to sign documents and generate
key fingerprints. Researchers recently published an attack on SHA-1 that
can find collisions in drastically shorter time than previously thought,
accelerating the move to replace SHA-1. A contest is underway to select a
replacement, that will be designated SHA-3, but it will not be standardized
2012. Between now and then, there are several steps interested individuals
can take to harden themselves against attack — starting with
understanding just what a hash collision can and cannot compromise.
SHA-1 was created by the National Security Agency (NSA) in 1995. It
computes a 160-bit hash or "digest" of any message less than 2^64 bits
long. Like any cryptographic hash function, its value as a message
authentication tool depends on it being mathematically hard to find a
collision: two messages that generate the same hash value. A brute-force
search would, on average, take 2^80 evaluations of the function to find a
collision (80 being half of the 160 bit digest length). Such a search
would find two arbitrary messages that result in the same hash, not allow
an attacker to find a collision with any specific message, but the 2^80
steps of a brute-force attack serves as a metric for the comparative
efficiency of other attacks.
In recent years, the most efficient known attack
on SHA-1 required 2^63 evaluations — around 1/100,000th the number of
steps for a brute force search, but still safely outside the reach of a
real-world attacker. That changed in April of 2009, when Cameron McDonald,
Josef Pieprzyk, and Phil Hawkes presented findings
at the Eurocrypt 2009 conference that lowered the bar to 2^52 — a
2,000-fold speedup over 2^63. The existence of such an attack is far from
a crisis-level weakness, but the upshot is that it is better to start
migrating away from SHA-1 while it is still relatively safe.
SHA-1 in free software cryptography
SHA-1 is used in public-key cryptographic systems, including the OpenPGP specification (RFC 4880) implemented on most
Linux desktop and server distributions by GnuPG. Since SHA-1 is a hash function, and
not a cipher, it does not play a direct role in encryption, but it
is used for digital signatures. In addition, OpenPGP key
fingerprints are created with SHA-1, and key fingerprints are in turn used
in key revocation and modification detection codes (MDC).
An OpenPGP digital signature
involves computing a hash of the original message, then encrypting the hash
with the signer's private encryption key. To verify the signed message's
integrity, the recipient also needs to be able to compute the same hash on
the received text. That requires support from the software and
the keys used — although OpenPGP supports multiple hash algorithms in
addition to SHA-1, old DSA
keys can only use 160-bit signatures. Historically, that meant SHA-1,
although RIPEMD-160 is
compatible as well. Consequently, selecting a stronger algorithm when
signing messages is possible with an application like GnuPG, but in the
worst case scenario a user wishing to avoid SHA-1 would need to create a
new DSA2 or RSA signing
Key fingerprints are
digests of public keys, useful for key management because they are
considerably shorter than the key from which they are hashed — thus
making them human-readable so they can be compactly referenced more easily.
Applications often list keys in a user's keyring by their fingerprint, so a
SHA-1 collision that results in two keys having the same fingerprint could
cause user confusion or unpredictable application behavior. Perhaps more
importantly, key revocation certificates reference
keys using fingerprints, again opening the door to unpredictable behavior
if the application finds two keys with identical fingerprints. OpenPGP
specifies SHA-1 as the only hash algorithm for version 4 keys (the latest
revision), so there is no current workaround for fingerprint
MDC is an
OpenPGP system to provide message integrity-checking with less overhead and
less stringent requirements than full digital signatures. RFC 4880
describes it as "analogous to a checksum." MDC also specifies SHA-1 as its
sole hash algorithm, but because its modest goals cover message integrity
but not authentication, the existence of collisions does not adversely
affect it. The checksum-like usage of the hash algorithm in this context
simply verifies that the message content was not altered or corrupted in
Although 2^52-evaluation collisions represent a significant weakening of
SHA-1, it is important to note that hash collisions are not as easy to
exploit as broken ciphers. On the GnuPG users' mailing list, maintainer
David Shaw evaluated
some of the possible scenarios, such as attempting to forge a signature.
Even with the easier-to-exploit MD5 collision problem, thus far no one has
been able to create a phony signature to match the signature of an existing
key; the closest anyone has come is to generate two keys that can be used
to create the same signature — an attack with little practical value.
opinion on the IETF's OpenPGP Working Group list was much the same. A
more likely problem is the unexpected behavior of applications when
confronted with fingerprint collisions.
Practical migration and looking forward
Nevertheless, users are encouraged to transition away from SHA-1 usage
to stronger hash algorithms. The US government has mandated
deprecation of SHA-1 for its use by the end of 2010. There are several
alternative hash functions available today, including the family known as
SHA-2 includes several functions that are related but use different digest
lengths: SHA-224, SHA-256, SHA-384, and SHA-512. The SHA-2 functions are
algorithmically similar to SHA-1, and so would be vulnerable to the same
type of attacks, but because of their larger digest size they remain
significantly more secure.
The National Institute of Standards and Technology (NIST) is currently
holding a competition
to select a next-generation hash algorithm to be designated SHA-3.
Submissions were due in October of 2008, and the final winner is expected
to be announced in 2012.
Debian's Daniel Kahn Gillmor posted a step-by-step
guide to migrating away from SHA-1 in GnuPG. Included are instructions
for setting up signing algorithm preferences in gpg.conf, attaching digest
preferences to a public key so that other users will select a stronger
algorithm when sending a message, and generating a replacement for an old
DSA key. It is an important read particularly for key replacement, because
setting strong digest preferences must be done before generating a
new key — otherwise GnuPG will default to using SHA-1.
GnuPG for its part is planning
to change its defaults in future releases, so that newly-created keys will
default to RSA instead of DSA, and be able to use newer hash algorithms.
Gillmor has also proposed
a tool to scan OpenPGP keys and offer suggestions to the user for
strengthening them — including using the current format, key type and
size, appropriate sub-keys, and several other parameters.
The trickier problem is the OpenPGP specification's inclusion of SHA-1
as the "hardwired" choice for fingerprinting, revocation, and MDC. A thread
on the OpenPGP Working Group's mailing list exposes several points of view.
Some think that the group should wait for SHA-3, some think a change is due
now, and others think that hash collisions even on fingerprints are not a
significant enough security risk to warrant changing the specification.
As Gillmor's migration guide indicates, Debian is trying migrate its
developers, maintainers, and teams away from SHA-1 digests and DSA keys and
towards RSA keys with SHA-512 digests. Likewise, the Fedora project has
undertaken a concerted migration
to SHA-2 hashes. Ubuntu's security team administrator Kees Cook says that
that distribution will update its keys over time, but that there is no
rush. OpenSUSE's Marcus Meissner echos that sentiment, observing that the
distribution is phasing out SHA-1 and MD5 for signing, but that collisions
do not constitute a security threat for simple download integrity checking.
All four distributions already use RSA master keys to sign packages.
Shaw emphasized that the recent attacks on SHA-1 still require a
significant amount of work, and at best would allow an attacker to produce
two original documents that hash to the same value, which does not directly
impact most people's usage of OpenPGP. "This is not an attack where someone
could take an existing OpenPGP-signed document and make a new document that
matches the signature or the like." He advised individuals and maintainers
who know that their intended recipients can accept larger hashes to use
larger hashes, particularly when signing documents created by someone else
(such as at a key-signing event), but not to worry unduly about using SHA-1
when that is the only option. In other words, he said, walk, but don't
run, for the exits.
to post comments)