Jan 252011

The other day, I saw a report on the CBC about increasingly sophisticated methods thieves use to steal credit and bank card numbers. They showed, for instance, how a thief can easily grab a store card reader when the clerk is not looking, replacing it with a modified reader that steals card numbers and PIN codes.

That such thefts can happen in the first place, however, I attribute to the criminal negligence of the financial institutions involved. There is no question about it, when it’s important to a corporation, they certainly find ways to implement cryptographically secure methods to deny access by unauthorized equipment. Such technology has been in use by cable companies for many years already, making it very difficult to use unauthorized equipment to view cable TV. So how hard can it be to incorporate strong cryptographic authentication into bank card reader terminals, and why do banks not do it?

The other topic of the report was the use of insecure (they didn’t call it insecure but that’s what it is) RFID technology on some newer credit cards, the information from which can be stolen in a split second by a thief that just stands or sits next to you in a crowded mall. The use of such technology on supposedly “secure” new electronic credit cards is both incomprehensible and inexcusable. But, I am sure the technical consultant who recommended this technology to the banks in some bloated report full of flowery prose and multisyllable jargon received a nice paycheck.

 Posted by at 1:39 pm
Jan 012009

I am starting the new year by reading about a substantial piece of cryptographic work, a successful attack against a widely used cryptographic method for validating secure Web sites, MD5.

That nothing lasts forever is not surprising, and it was always known that cryptographic methods, however strong, may one day be broken as more powerful computers and more clever algorithms become available. What I find astonishing, however, is that even though this particular vulnerability of MD5 has been known theoretically for years, several of the best known Certification Authorities continued to use this broken method to certify secure Web sites. This is hugely irresponsible, and should a real attack actually occur, I’d not be surprised if many lawsuits followed.

The theory behind this attack is complicated, and the hardware is substantial (200 Playstations used as a supercomputing cluster were required to carry out the attack.) One basic reason why the attack was possible in the first place has to do with the “birthday paradox”: it is much easier to construct a fake certificate that has the same signature as a valid certificate than it is to recover the original cryptographic key used to sign the valid certificate.

This has to do with the probability that two persons at a party have the same birthday. For a greater than 50% chance that another person at a party has your birthday, the party has to be huge, with more than 252 guests. However, the probability that at a given party, you find at least two people who share the same birthday (but not necessarily yours) is greater than 50% even for a fairly small party of just over 22 guests.

This apparent paradox is not hard to understand. When you meet another person at a party, the probability that he has the same birthday as you is 1/365 (I’m ignoring leap years here.) The probability that he does NOT have the same birthday as you, then, is 364/365. The probability that two individuals both do NOT have the same birthday as you is the square of this number, (364/365)2. The probability that none of three separate invididuals has the same birthday as you is the cube, (364/365)3. And so on, but you need to go all the way to 253 before this results drops below 0.5, i.e., that the probability that at least one of the people you meet DOES have the same birthday as you becomes greater than 50%.

However, when we relax the condition and no longer require a guest to have the same birthday as you, only that there’s a pair of guests who happen to share their birthday, we need to think in terms of pairs. When there are n guests, they can form n(n – 1)/2 pairs. For 23 guests, the number of pairs they can form is already 253, and therefore, the probability that at least one of these pairs has a shared birthday becomes greater than 50%.

On the cryptographic front, what this basically means is that even as breaking a cryptographic key requires 2k operations, a much smaller number, only 2k/2 is needed to create a rogue cryptographic signature, for instance. It was this fact, combined with other weaknesses of the MD5 algorithm, that allowed these researchers to create a rogue Certification Authority certificate, with which they can go on and create rogue secure certificates for any Web site.

 Posted by at 2:30 pm