0
$\begingroup$

Assume an operating system uses digital signatures to ensure executable files can be authenticated and can't be modified; where the digital signatures are constructed by creating a hash of the executable file (e.g. SHA256), encrypting the hash with a private key (e.g. RSA), then attaching the encrypted hash and public key (the signature) to the executable file.

Assume there's 1000 pieces of software (from multiple publishers) that are updated (on average) once per month for 5 years.

An attacker collects the hash and the digital signature for all 60000 pieces of software. The attacker writes their own trojan malware with some spare padding at the end of their executable file. The attacker calculates a partial hash of their executable, but stops (saving hash calculation state) just before the padding.

The attacker resets the hash calculation state, finishes the hash calculation extremely quickly, then checks if the hash corresponds to one of the 60000 digital signatures they've collected. If it doesn't, they increment the padding at the end of their executable file and retry. The attacker does this on multiple (multi-CPU) computers in parallel, until they find something else's signature they can use to sign their malware.

How can this be prevented?

The strength of the encryption scheme is unimportant. Increasing the hash size just means the attacker needs to collect more digital signatures and/or use more CPUs for longer to find a valid signature for their malware. Assume the attacker can get more CPUs by hiding javascript in a popular web page, using cloud services, hiding it in software published with their own legitimate signature (e.g. a crypto-currency mining utility), etc.

Is any existing hash algorithm strong enough?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
4
$\begingroup$

Is any existing hash algorithm strong enough?

Yes; actually, any cryptographically secure hash algorithm (such as SHA-2, SHA-3, Blake2) would be plenty strong enough.

To emphasize this, let me point out that MD5 is strong enough. Now, MD5 is considered quite weak (and no one here would endorse its use); however even with its known weaknesses, it is still strong enough against this specific attack.

MD5 has a 128 bit output (contrasted with the cryptographical hash functions we use in practice, which have much larger outputs). In addition, there are known ways to generate "collisions", that is, pairs of inputs that MD5-hash to the same value. However, those methods assume that the attack has control over both inputs - in this case, the valid publisher generates the valid image and the attacker cannot alter what the publisher signs, and so the collision weakness of MD5 does not apply. MD5 has no known weaknesses to 'second preimage' attacks, or to a 'multitarget second preimage' attack (which is exactly what this is), and so the only approach the attacker has is the hash various inputs until he finds a match.

Now, we assume that there are $60,000 \approx 2^{16}$ valid signatures; if the attacker hashes a guess, that has about a $2^{-128+16} = 2^{-112}$ probability of hashing to one of the targets. In other words, to get a one-in-a-thousand chance at finding an image that hashes to one of the targets, he would need to hash about $2^{102}$ images.

Now, it is estimated that the global bitcoin mining industry evaluates about $2^{68}$ hashes per second (actually, a bit less); that means that if the attack would be able to devote all that processing [1] to attacking your system, they would need to go at it for about $2^{34}$ seconds (or about 500 years) to get up to that 1-in-a-thousand chance.

If you swap out MD5 with a real crypto hash, that 500 years turns into 'heat death of the universe' type of timeframe.

[1]: Of course, the current bitcoin mining infrastructure is built around SHA-256 - I'll ignore that detail.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Are you overlooking the birthday problem? I would've expected that a 1 << -112 probability of one guess matching means you only need about 1 << 61 guesses. With SHA256 acceleration in most CPUs (and only needing to do the final few bytes), I'd be disappointed if I failed to achieve several million hashes per CPU per second. 1 << 61 guesses / 1 << 23 guesses per second per CPU = 1 << 38 seconds (about 1 year, for a thousand 8-core CPUs). Note: I couldn't get superscript or "double asterisk for exponents" to work in comments, sorry about the left shifts! $\endgroup$
    – Brendan
    Commented Jan 4, 2022 at 21:29
  • $\begingroup$ @Brendan: as I mentioned above "in this case, the valid publisher generates the valid image and the attacker cannot alter what the publisher signs, and so the collision weakness of MD5 does not apply". If this is not true (that is, the attacker can insert his own alterations into what the publisher signs), then MD5 may be insufficient. On the other hand, if we were to go back to SHA256 (far more realistic), a collision attack takes an expected $2^{128}$ hashes - that's close to the number of evaluations that we got for the MD5 multitarget preimage attack - a similar time estimate applies. $\endgroup$
    – poncho
    Commented Jan 4, 2022 at 21:35
  • $\begingroup$ @Brendan: of course, if the attacker can insert his own alterations into what the publisher signs, why wouldn't he just include his malware in that, and not bother trying to generate a forgery? $\endgroup$
    – poncho
    Commented Jan 4, 2022 at 21:36
  • $\begingroup$ Ah, you're right (I was miss-applying birthday attacks). 1<< 102 hashes / 1 << 23 = 1 << 79 seconds = about a million 8-core computers for a few million years. $\endgroup$
    – Brendan
    Commented Jan 4, 2022 at 21:43
1
$\begingroup$

SHA-256 is resistant to preimage attacks. The only way to find a preimage that produces given hash is brute-forcing. Current computation resources used for bitcoin mining in the world compute about $2^{90}$ hashes per year. Thus, even if the whole world tries to create an image (in your case, to find particular padding) with the given hash, it will not be possible even in a couple of millions years.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Actually, "in a couple of millions years" is vastly overoptimistic; at $2^{90}$ hashes/year, and 60,000 targets, the search will take an expected $1.5 \times 10^{45}$ years $\endgroup$
    – poncho
    Commented Jan 4, 2022 at 19:07
  • $\begingroup$ @poncho: Correct :-) But I am afraid that it is hard to imagine if it is really much time. You can say it is longer than the Universe exists. But even this may be hard to imagine. May be even million of years is hard to imagine and thousand might be better :-) That's why I hope that using such wording makes the answer more helpful. $\endgroup$
    – mentallurg
    Commented Jan 4, 2022 at 19:25
  • $\begingroup$ I get that, however your statement sounded similar to "the stars are more than 10 meters away". Technically true, I suppose, but also a comic understatement... $\endgroup$
    – poncho
    Commented Jan 4, 2022 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.