To read all comments associated with this story, please click here.

Isn't it possible to defeat hash signing by producing a binary which has the same hash, but different code ? After all, the transformation which turns a multi-MB binary into a small, easy to compute and check hash, loses so much information that there's a huge number of possible binaries associated to a given hash.

(It is my understanding that this is what happened with MD5, and is potentially also happening with SHA-1... Breaking hashes this way seems to be purely a matter of time, given that you have some skilled mathematicians at hand)

*Edited 2011-09-26 05:48 UTC*

(It is my understanding that this is what happened with MD5, and is potentially also happening with SHA-1... Breaking hashes this way seems to be purely a matter of time, given that you have some skilled mathematicians at hand)

For cryptographically secure hash algorithms, it's not really feasible time-wise to do this.

Neolander,

"Isn't it possible to defeat hash signing by producing a binary which has the same hash, but different code ? After all, the transformation which turns a multi-MB binary into a small, easy to compute and check hash, loses so much information that there's a huge number of possible binaries associated to a given hash."

You are absolutely right about the hash. Furthermore, you might say the same thing about RSA itself. There are only a finite number of possibilities to try, which implies that it's not difficult to build algorithms to enumerate them.

The key to all digital cryptography is that all known algorithms to crack the numbers use exponential time. Every additional bit is exponentially more difficult crack.

However these problems also fit squarely into the class of parallel problems considered "embarrassingly parallel", with no IO/sync overhead. This means shorter bit lengths are vulnerable against massive specialized cracking clusters.

History shows us that we need to be much more conservative with our estimates of cryptographic security. I recall when the EFF deliberately build a DES cracking machine in 1998 to publicly embarrass the US government on it's legal policy of restricting international crypto products to algorithms known to be extremely weak.

http://news.cnet.com/Record-set-in-cracking-56-bit-crypto/2100-1017...

Now days that we routinely use far larger bit lengths, and our encryption is much more resilient to brute force attacks. 256 bit cryptography cannot be brute forced today or in the near future. But we are still occasionally finding flaws in the algorithms which mathematically etch away at their security.

It is an open question whether cryptographers will ever be able to place a lower boundary on the work needed to crack a code, or whether sufficiently clever algorithms will always exist to reduce the search space ever further.

Member since:

2011-01-28

For anyone who's interested, here is a quick example of RSA public key encryption:

(Follow along by installing the "apcalc" package and running "calc" or use arbitrary math package of your choice).

Set variables representing the public and private keys. These are 1024 bit RSA keys in raw decimal form:

pub=65537

priv=10034701516581607751438717050886575134854567927773406346110095389 3880607258989277229978848721573396656818709713200926839511880509613865 9474100668909735440576231560731353120314326442917250425554249145477285 0129649359760655421361386946859858098073967083122130092429101461607165 5771225693620196033624908952782337

mod=129569752008079601861068484388831561709544451549075130369811908254 0636251464335302589077903827282626033952198454182587729744288942896196 0350330116308876109346648935805264992779319753450874988762827064435308 9787488188343904181776607311622352871569989214585044083692694467436005 432575044089339511423879924748093

Encryption and decryption are astonishingly simple:

ciphertext = (plaintext ^ pub) % mod

where (pub, mod) make up the public key.

plaintext = (ciphertext ^ priv) % mod

where (priv, mod) make up the private key.

Now lets put this to use, our secret message is "12345"(using calc's syntax):

ct = pmod(12345, pub, mod)

ct =649561333757451757004248916422444207210624792546812513939697190576800 5598628412789281587428693978445925410757595668337235621964710636482986 7678609454140521694918033207929545708825534606806618029320280335294395 2108081515947478212104872619337026831010184080090087060494955661721844 6386794696129430701630814522

And to decrypt using the private key:

pt = pmod(ct, priv, mod)

pt

=12345 VOILA! We get back our secret "message".

Real life implementations use extra padding to eliminate vulnerabilities with certain trivial cases like the following (they work, but they're not secure):

ct = pmod(0, pub, mod) = 0

ct = pmod(1, pub, mod) = 1

Notice the public factor is very short, and public factors are often hand picked to increase performance (65537 has only two "1" bits in binary). Until rather recently, it was even common to use 2 & 3.

To do RSA signatures, do modular exponentiation with the private key.

sig = pmod(12345, priv, mod)

sig

=100205529258865419244879929646186044045195253646483476594890711551327 4982492169370293702770904064497440555524437909863740900509951289739909 0562448712559790233458569876089221632715449998674923202958889156494344 0373081036036755363704923479676797763088081336323388508085704457488066 5932754001725793366736813449

To verify a signature, use the public key:

pmod(sig, pub, mod)

= 12345

A few things to note:

the value being signed/encrypted may not be larger than the modulus (1024 bit=128 byte). Additionally RSA is much slower than block level ciphers and hashes, therefor RSA is always used in conjunction with other cryptographic primitives.

Anyways, if you play around with the examples, it should become clear that to verify a signature, one does not require the private key which generated the signature. This is one of the basic properties of PKI cryptography. And this is the reason that reverse engineering the bios will not yield the signing keys that microsoft/OEM possess.

If anyone's got questions, I love talking about this stuff!