Friday, January 31, 2014

Targeted

Everyone is well aware of retail runner up Target and their recent hacking.  And this event couldn't have come at a worse time for them.  Their systems were compromised over Thanksgiving weekend, the traditional start of the holiday shopping season, and stayed pwned for several weeks.  Fortunately, they've plugged the holes and were able to continue on with their holiday sales season.
Meanwhile, banks around the country are taking steps to protect their customers' banking details.  Apparently, in light of lessons learned from major breaches like Heartland Payment Systems, many found it less expensive to just reissue thousands to millions of new cards to any customers who may or even might not be affected.  A major credit union here in Arizona is issuing new cards and numbers for 877 potentially compromised accounts.
While the stolen credit card information has already been put up for sale, Target insists that at least the PINs associated with debit cards were securely encrypted, specifically with Triple DES, or more properly, the Triple Data Encryption Algorithm, TDEA.
Triple DES is a block cipher, which means it encrypts blocks of data, 64 bits at a time, and does so in three passes, each with a different key based on the keying option used.  Data Encryption Standard (DES), with only a 56 bit key, is too weak to protect data against brute force attacks by modern hardware and has been removed as a standard.  Triple DES itself, by stacking up on the encryption with multiple keys, is considered secure enough against any practical attacks.  It has, however, been replaced in most applications with Advanced Encryption Standard (AES).
Target wasn't specific as to which keying option of Triple DES was being used, though they made it clear that they never had any of the keys.  Knowing which keying option was being employed could direct an attacker to a method of exploit.  Since Triple DES encrypts with key one, decrypts with key two, and then encrypts again with key three, the most secure option is that all three keys are different.  That usually isn't the way it's done in practice; typically the first and third key are the same.  Obviously, if there's only a single key being used three times, the encryption simplifies to a single round of DES and that compatibility is, in fact, why Triple DES does encrypt-decrypt-encrypt instead of three rounds of encrypt.
So what attacks are available?  Essentially a rainbow table attack.  We can only hope that the payment processor who held the keys held more that one.  Single key Triple DES is only DES and that could be broken in less that a day ten years ago.  That's a trivial brute force attack today.  Option two is the most commonly used method of implementing Triple DES and it's the one that encrypts with the first key, decrypts with a second key, then encrypts once more with the first key again.  The issue is that the plaintext being encrypted, all those PINs, is such a small domain.  PINs for debit cards are typically only four digits long.  At best, 32 bits or half a block.  Even worse, the Feistel algorithm that underpins DES and thus Triple DES operates on only a half block at a time.  The fluff and random bits that fill out the block might be irrelevant when decrypting stolen debit card PINs.  With such a limited domain, chosen plaintext and known plaintext attacks become available.  Insanely resource intensive, but available.
As a shout-out, my cryptography professor at the University of Maryland, Lawrence C Washington, along with Wade Trappe, also a Maryland professor at the time, literally wrote the book on cryptography.  I have the first edition.  Maybe I should've gotten it signed by the authors; I hear signed first editions are valuable.  Anyway, it's good to be a terrapin.  Let's Go Maryland!  Rah!  Rah!  Ra-ra-rah!