Take OpenPGP fingerprint for example. If the 40-digit hex standard remains unchanged, would it be helpful to upgrade SHA-1 to SHA-256 (but only taking the last 160 bits), in terms of reducing the risk of collision?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Using a reduced output hash may also help against length extension attacks (applicable for both SHA-1 and SHA-256). Those require a secret key to be used and are therefore not considered when taking a fingerprint of a key pair, but they may be of interest of other readers drawn here by the title of the question. $\endgroup$– Maarten Bodewes ♦Commented Dec 17, 2019 at 12:26
-
$\begingroup$ FYI To my own surprise I figured out how to take a PGP fingerprint here (found by an Internet search :P). As it does not contain any identifiable information of the user, it is possible to try for fingerprint matches of a large amount of keys, e.g. pulled from an online key server. $\endgroup$– Maarten Bodewes ♦Commented Dec 17, 2019 at 12:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
SHA-1 is broken in practice in terms of finding collisions. This shattered attack (identical-prefix collision attack) requires roughly $2^{63.1}$ SHA-1 evaluations and this is approximately 100,000 faster than finding collisions with generic birthday attack on 160-bit output that has $2^{80}$- time complexity. That is, for a hash function with $\ell$-bit output we expect at least one collision with a 50% probability within $2^{\ell/2}$ outputs.
There are no attacks on SHA-256 trimmed to 160 bit better than the generic collision attack due to the birthday attack. Therefore they are not the same in finding collisions, in this case, SHA-256 trimmed to 160-bit has better security than SHA-1.
The attacks on SHA-256 or similarly other iterated hash functions are performed on reduced rounds. We don't expect weakness on the trimmed version of well designed cryptographic hash functions. Except for the resistances which happens naturally. If such a weakness exists, it can represent a weakness in the designs of the hash function and this could be used to attack the full version.
Note that NIST deprecated the use of SHA-1 in 2011 way before the actual attack. 160-bit hash output is no longer considered secure. If you consider that Bitcoin miners reached $\approx 2^{92}$ double SHA-256 hashes per year in 06 Agust 2019, 160-bit is no longer secure, or even 180-bit. The hash rate $2^{92}$ for a year is for the double SHA-256 hashes. Therefore they can calculate $2^{93}$ SHA-256 in a year.
note: I've re-check the current hash rate of Bitcoin miners, it is was 80.294 Exa Hashes/s (1 exa is one quintillion (1,000,000,000,000,000,000) ) in 06 Agust 2019. It reached 110.6056 Exa on 23 October 2019, unfortunately, or hopefully, this is still $\approx 2^{92}$. In a second, this makes $2^{67}$ double SHA256 calculations which means, they can break the DES key less than a second or any 64-bit block-cipher.
answered Dec 13, 2019 at 7:44
-
1$\begingroup$ Also note that trying to find a key pair that matches the fingerprint of a particular key is still very (prohibitively) expensive, as the birthday bound would not apply. However, you could worry about large organizations trying to find key pairs that could match large amounts of key pairs. Shattered attacks don't work for pre-generated key pairs. So although above answer is correct w.r.t. collision resistance, there are quite a few things to consider when it comes to fingerprints (for OpenPGP compatible keys). $\endgroup$– Maarten Bodewes ♦Commented Dec 17, 2019 at 12:36
-
$\begingroup$ @Maarten-reinstateMonica Thank you for the addition. $\endgroup$ Commented Dec 17, 2019 at 13:01
-
1$\begingroup$ Now there's a demonstrated chosen plaintext collision too. $\endgroup$ Commented Jan 8, 2020 at 12:29