Join Log in
Score:0
avatar Crypto

Digital Signatures forgery on 60000 messages with brute force

us flag
Brendan

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?

125
0 + 0
kelalaka avatar
in flag
kelalaka
Related [Multi-target attack for hashes](https://crypto.stackexchange.com/q/75880/18298)
1
Reply
Score:4
poncho avatar Crypto
my flag
poncho

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.

0 + 0
us flag
Brendan
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!
0
Reply
poncho avatar
my flag
poncho
@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.
0
Reply
poncho avatar
my flag
poncho
@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?
0
Reply
us flag
Brendan
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.
0
Reply
Score:1
avatar Crypto
kr flag
mentallurg

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.

0 + 0
poncho avatar
my flag
poncho
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
2
Reply
kr flag
mentallurg
@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.
0
Reply
poncho avatar
my flag
poncho
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...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.