MD5 Collisions: Forged ICA
The attack presented yesterday at the CCC is very interesting. The researchers were able to predict the serial number by monitoring certificate issuance rates from a Certificate Authority, and use that information to mount a pretext attack against a future issued certificate whereby they generated an Intermediate CA cert with the same MD5 hash as the certificate they would request in the future. (I know that is a little difficult to parse.)
The end result is an ICA that can issue certificates trusted by web browsers for any domain and allow main in the middle attacks against SSL/HTTPS connections. There were apparently a few CAs still using MD5 hashes for verification, but according to the presentation those have been contacted and are converting to another hash algorithm.
Hashing: Trusting the Black Box
Hash algorithms are widely used for a variety of tasks including verifying data integrity, authenticating passwords, and signing certificates. For the laymen the hash algorithm seems like a magic sausage grinder: dump in whatever you have and out comes a unique number. The trouble is, the internal mechanics of a hash algorithm are less like a simple mechanical machine and more like a Rube-Goldberg device. The internal mechanisms of bit shifting and mathematics would be incomprehensible to most who place blind faith in the algorithm’s ability to generate “unique” numbers.
The first illusion to dispel is uniqueness. Hash algorithms do not generate unique numbers, nor do they claim to. If you look at the problem logically the hash space is infinitely smaller than the possible inputs. MD5, for example, generates 128 bit hashes. If you have 129bits of data, then you end up with 2128 more unique inputs than possible hash numbers which implies collisions. Given data significantly larger than the hash number size, there will always be a possible collision differing by some small number of bits or bytes in the file.
DC3 Challenge Results
I might as well kick this blog off with a bang. Working full time while being a full time graduate student doesn’t leave much time for extracurricular activities other than (occasionally) sleep , but over the past few months I was on the department team for the DC3 challenge. The results of the challenge were announced this month, and we did fairly well.
DC3 stands for the Department of Defense Cyber Crime Center, and every year they publish a forensics challenge. The challenge is open to anyone and has participants from industry, academia, and government. This year had 199 teams participating, with only 20 returning solutions. The challenge has a reputation for being fairly tough, and some of the problems may not be solveable. In any event, our team placed 4th over all with the top slots seperated by a fairly small margin (less than one of the upper level problems.) The University posted a little summary: