Want another ID?

November 17, 2006 3:49 AM

New "Hi - tech" passport cracked. Standards for the new passports were set by the International Civil Aviation Organisation (ICAO) in 2003 and adopted by the waiver countries and the US. The UK Home Office has adopted a very high encryption technology called 3DES - that is, to a military-level data-encryption standard times three. However they used non-secret information actually published in the passport to create a 'secret key'. That is the equivalent of installing a solid steel front door to your house and then putting the key under the mat.
posted by adamvasco (53 comments total)

3DES isn't even *that* hard to crack anyway, from what I understand. It may once have been military-grade encryption, but I don't think it is anymore.

They'd have done much better with AES or Blowfish... although given the poor key choice, it doesn't matter a whit in this particular case.
posted by Malor at 4:01 AM on November 17, 2006

Adam is a really interesting guy, he did an excellent talk at my conference on magstripe security this past spring, and I think we're gonna convince him to talk about his RFIDIOt stuff used in the article in london.
posted by mock at 4:15 AM on November 17, 2006

My girlfriend just got one of the fancy new high tech passports here in Ireland. I want to get an RFID reader to see what information I can read off it.
posted by antifuse at 4:49 AM on November 17, 2006

I agree with Malor.

I think characterizing 3DES as high encryption is inappropriate. Yeah, if it's implemented correctly, it's three times stronger than DES, but, a civilian organization (the EFF) was able to demonstrably crack DES for under $250,000 in 1998.

If I remember correctly, this was part of the reason that the AES selection process came about, and why the feds officially chose a better encryption mechanism.
posted by kalessin at 4:50 AM on November 17, 2006

This is exactly the same problem/virtue of DRM media. In commercial DVD's, the key to the content is right next to the encoded content. Everybody knows the ciphers (3DES, CSS). If you have the cipher, the ciphertext (encoded content or passport data) and the key, you can decrypt it. This use of encryption was impossible from the start, but i guess its the nature of greed to invest in the impossible. Essentially, the data in DVDs, passports and itunes songs either provides the means (key) to be read or not, and in these cases it does, but it does so without discrimination. Any descrimination (like itunes only playing on your computer) comes from the media player you use, and could be applied to any file without encryption.

However, during design, IT consultants are quick to point out data is encrypted, just as the door installers would have said it locked, just before putting the key under the mat. These highly paid simpletons are a disgrace to the art and lower the general public's trust in encryption, just as encryption becomes more and more a tool of freedom. In the end, math sets us free.
posted by CautionToTheWind at 4:51 AM on November 17, 2006 [1 favorite]

FIPS 46 (a.k.a. DES) has been withdrawn by NIST - basically, it's no longer an approved standard. 3DES is, in theory, "triple DES", but the key length is only twice that of DES. 3DES is "bank grade encryption". I believe it's used in cash machine networks.

If they wanted a little more security, they would have used FIPS 197 (a.k.a. AES or Advanced Encryption Standard), an algorithm that was selected through public competition, has a number of different key lengths (128, 192 and 256 bit), and can be implemented within limited hardware resources.

Oh, and putting the key in plaintext with the encrypted content is just dumb. As usual, a crypto system fails because of the implementation rather than the algorithm itself.
posted by lowlife at 4:54 AM on November 17, 2006

I don't quite understand what the encryption is for. It seems like it is only intended to protect the data from being read by those that can't see inside the passport, and for that sort of casual data sniffing it seems to me that 3DES with that sort of key system is likely to be adequate.

Why they didn't choose something better remains beyond me however.
posted by edd at 5:55 AM on November 17, 2006

When airports and airlines start offering express queues and price reductions to people who have been chipped like pets, so that you are your passport and black box, things will get interesting.

(I keep my passport under my tin-foil hat.)
posted by pracowity at 6:00 AM on November 17, 2006

Saying 3DES is 'three times stronger' than DES is misleading. DES uses a 56-bit key, 3DES has an effective 112 bit key. If you had a supercomputer that could crack DES in 1 second, it would still take that machine 10^9 years to crack 3DES.

If someone knows of a civilian-accessible way to crack 3DES in a reasonable amount of time, let me know.
posted by These Premises Are Alarmed at 6:03 AM on November 17, 2006

3DES is still reasonably strong (much more than "three times stronger than DES"), but this implementation is really typical of the magic bullet approach to security. I expect the underlying problem is rather similar to that faced by the US with its voting machines: a clueless, non-technical government administrator has been put in charge of a major IT project and been sold the (pointless, unworkable, counterproductive, and expensive) technology by a wily contractor. It's the latest in a long line of IT projects that the British government has proved itself totally incapable of delivering (see NHS "connecting for health" disaster).
posted by hoverboards don't work on water at 6:04 AM on November 17, 2006

They all laughed at me when I bought one of these. But, luckily, it saves me the trouble of traveling with a roll of aluminum foil, unlike pracowity.
posted by Mayor West at 6:10 AM on November 17, 2006

I think characterizing 3DES as high encryption is inappropriate. Yeah, if it's implemented correctly, it's three times stronger than DES, but, a civilian organization (the EFF) was able to demonstrably crack DES for under $250,000 in 1998.

Wow! What a hair-brained statement! Why do people who don't know things feel the need to mouth off like that? A lot of bad info gets passed around that way.
posted by Paris Hilton at 6:21 AM on November 17, 2006

sad, but funny
posted by caddis at 6:23 AM on November 17, 2006

However they used non-secret information actually published in the passport to create a 'secret key'. That is the equivalent of installing a solid steel front door to your house and then putting the key under the mat.

For fuck sake, that's how it's meant to work:

"Basic Access Control, or BAC, works this way: The data on a passport would be stored on an RFID chip in the passport's back folder, but the data would be locked and unavailable to any reader that doesn't know a secret key or password to unlock the data. To obtain the key, a passport officer would need to physically scan the machine-readable text that's printed on the passport page beneath the photo"

Words fail me.
posted by cillit bang at 6:40 AM on November 17, 2006 [1 favorite]

It sounds like you still need physical access to the passport to make any sense of the RFID data. How is that different from non-RFID passports?
posted by stopgap at 6:44 AM on November 17, 2006

The problem isn't the 3DES, which is working just fine. If they had used AES instead they would still have the exact same problem of having a key that is not secret. In fact, because AES is faster than 3DES, brute forcing a keyspace of the same size is faster!

stopgap, according to the article all of the information in the key other than the passport number can be easily found out or guessed, and the passport number is easily brute forced, so the "rogue postman" example certainly is plausible.
posted by zsazsa at 7:26 AM on November 17, 2006

I swear, people see the word encryption, their brain goes into idiot mode, and they start babbling all sorts of bullshit about algorithms and key size and shit.

Ultimately the insecurity of this comes down to the following:

1) You can read the data remotely
2) The key to decrypt that data is not random

What people always forget is that as soon as you allow remote electronic access, sybil attacks become trivial. If I wanted to be a very evil boy what I would do is put a small rfid snooper somewhere where a lot of people will walk in close proximity (say a tube station). Now since the key is made up of passport number (not very random), birth date, and passport expiry date (both really not random), that really is sweet fuck all in the way of randomness preventing you from just trying keys until you get one that works.

But here's the best part, the passports all include biometrics as part of the rfid data. So the question then becomes, how long do I have to wait before someone walks by my snooper who looks like enough like me so I can pass as them, and what is the cost of actually physically creating a look alike passport?
posted by mock at 7:27 AM on November 17, 2006

Well, Paris, now that you've used an ad hominem to teach me that I don't know anything, how about letting me know what I got wrong?
posted by kalessin at 7:37 AM on November 17, 2006

Thanks mock for bringing the discussion up. What gets me is who are the fuckwits who use public money (i.e yours and mine) on badly thought out mega projects, and are they ever held accountable. Is it the ICAO or just UK idiots? Is the US encryption and therefore hack the same?
posted by adamvasco at 7:39 AM on November 17, 2006

It's an international standard, so presumably the US passports are the same. Fuck, I bet someone could make a mint selling a package that set off a blasting cap when countrycode = USA.
posted by mock at 7:43 AM on November 17, 2006

It seems that the correct implementation is for the encryption key to be random, but machine-readable via a mechanism that requires physical access to the passport, eg MICR.

Given that even the correct approach doesn't throw up much of a barrier to cloning the card (postmen, hotel clerks, car hire companies, all get access to passports regularly), it appears that the whole RFID passport thing is fundamentally flawed.

(Something I'm missing: why can the data only be copied wholesale, and not modified? Are there two keypairs involved here, one government-held?)
posted by Leon at 7:47 AM on November 17, 2006

From the article: "After the 9/11 attack on the World Trade Centre, in which fake passports were used, the US decided it wanted foreign citizens who presented themselves at its borders to have more secure "machine-readable" identity documents."

Were fake passports used? All those guys were already in the country, the flights were all domestic, and I was under the impression their worst immigration-related offenses were expired visas.
posted by adamrice at 7:47 AM on November 17, 2006

Maybe I wasn't clear enough. They came up with the system to prevent casual remote snooping of passports, not to keep the data secret from someone with physical access to the passport, and not to prevent cloning (which I presume there are other systems for).

Maybe it's possible to snoop the data and then bruteforce the key, I don't know (and I can't see how any of you can from the details in the article), but that's not the "crack" that's being claimed here. They (and adamvasco) are claiming victory because they tried the handle on a door that no one said was locked, and gosh golly, it opened.
posted by cillit bang at 7:48 AM on November 17, 2006

Kalessin: just because you can break DES in a given amount of time with a given amount of money doesn't mean it scales linearly to 3DES. There are actually two different modes of 3DES: EEE and EDE. The former uses three seperate 56-bit keys performing the encryption transform in sequence using each of them; the latter performs encryption using key 1, decryption using key 2, then encryption using key 1.

To say that 3DES is obsolete is just wrong. It's used in military-grade applications, in finance, and it's still a viable - and widely used - encryption algorithm. It's considered to be secure against brute-force attacks using modern hardware. From a cryptanalysis perspective, the EDE variant has a proposed attack but no practical implementation of that attack (I believe Merkle and Hellman found something that worked on paper).

In any case, the security of any cryptosystem depends on how you protect the secret (and all cryptosystems out there require secrets). If you fail to adeqately protect the secret, your specific implementation (not the algorithm itself, just your implementation of it) is compromised. THAT'S the issue here.
posted by aberrant at 7:49 AM on November 17, 2006

3DES isn't even *that* hard to crack anyway, from what I understand.

It's plenty hard. You can crack DES in under a day, and if you purpose built a machine today, you can probably brute-force it in an hour.

DES has 56 bit. 3DES has an effective 112 bits (3DES is, just as it implies, DES run three times, using three keys, the first encrypts, the second *decrypts* the encrypted first stream, the third encrypts the "decrypted" stream.)

112-56 = 56. Each extra bit doubles the time it takes to brute force. So, DES takes an hour, and 3DES takes 2⁵⁶hours, or 72,057,594,037,927,936 hours, or 3,002,399,751,580,330 days, or about 8 trillion years. The best attack, as of early this year, required 2³² plaintexts and 2⁸⁸ bytes of memory, which allows you to break it in 2¹¹⁹ steps. (There are other tradeoffs between time and memory. Good luck with that.)

3DES is currently more than adequately strong. 3DES's problem is that DES wasn't exactly easy to compute, and 3DES is three times as hard to do. A big factor in the AES computation was feasibility -- the less CPU it took to encrypt or decrypt, the higher the cipher ranked, which is what put Rijndael over the top in the AES competition. (AES is Rijndael, with selected keylengths and options, Rijndael proper supports more than a 128bit block and 128, 192 and 256 bit keylengths.)
posted by eriko at 7:51 AM on November 17, 2006

mock wrote...
I swear, people see the word encryption, their brain goes into idiot mode, and they start babbling all sorts of bullshit about algorithms and key size and shit.

Too true.
posted by tkolar at 7:57 AM on November 17, 2006

cillit bang; please try not to be a dickhead. I claim no victory.
I posted an article from a reputable scource which suggests once again that huge amounts of money has been wasted in the name of security. As I am not an expert on such matters but know that several people here know much more than I do
about this subject - though many disagree. Please explain to how this new passport makes us more secure, and if it is not meant to be more secure, what is the point of it, and why are my tax $ being pissed up the wall. ThxBi.
posted by adamvasco at 7:57 AM on November 17, 2006

As I was saying idiot mode goes on.

Right then, please read this before making further comments informed only by your own ignorance filtered through the ignorance of a reporter. Don't be afraid to click on some of the links and look at the code and standards documents involved.

Next most awesome use for this - autodetecting trannies/jailbait in the bar.
posted by mock at 7:58 AM on November 17, 2006

My question is this: what's the sensitivity of the data they're trying to protect? Facial data? Who cares? What other personal, non-public data will be stored on these things that require encryption?
posted by aberrant at 8:04 AM on November 17, 2006

Please explain to how this new passport makes us more secure, and if it is not meant to be more secure, what is the point of it, and why are my tax $ being pissed up the wall.

What's that got to with anything? The point is nothing has been cracked. No big metal security doors have been opened. When someone demonstrates being able to remotely read one of these chips without physical access to the passport, that's when it's cracked, and you can splooge it over the front page all you like.

what's the sensitivity of the data they're trying to protect?

None that wouldn't otherwise be known to someone with access to the passport and/or passport holder. Or in essence, this crack only allows you to find out stuff you already know.
posted by cillit bang at 8:18 AM on November 17, 2006

Fuck, I bet someone could make a mint selling a package that set off a blasting cap when countrycode = USA.

You forgot the XML Markup.
posted by srboisvert at 8:20 AM on November 17, 2006

please read this again and digest.
posted by adamvasco at 8:26 AM on November 17, 2006

List of evil things I can do with this:

1) automate cloning passports of people who look like me

2) country code detonatable explosives

3) remote detection of age and sex - awesome for stalking

4) credit checks on customers as soon as they enter the store

4) track people as they walk around - great for police states

5) auto retrieve girls' names and birthdays in bars

6) criminal record checks on people you casually meet

7) easily retrievable biometric data (for those countries who implement the fingerprint biometric - I'm looking at you US and A) makes every other fingerprint scanner insecure

8) excellent for con artists - "Hi John Doe, I'm from the fbi and we'd like to talk with you"

9) replicate the identities of people you meet in trusted positions

10) great for assassination - set the bomb to only detonate when John Doe is within a foot

Luckily there's no sensitive information at risk!
posted by mock at 8:27 AM on November 17, 2006

I'm not sure which key could have been used -- something that the traveller has to remember? Forget about it. A secret uniq key? Bad -- false sense of umost security, disastrous when it is cracked/leaked.

It looks like the encryption is there to protect the bearer (but some of the passport data, which are somewhat interesting, can be discovered if you want to. Most of then are semi-public data: name, DOB, etc... The digitized picture and the passport number are probably the most valuable one.)

The danger lies in the control: you present your fake passport with a cloned RFID chip -- it is read by a system, the operator still as to enter the key, possibly optically scanning it (it means physically handling the passport.) Once aquired, that data is transmitted to verify you have the right to travel and that you are who you appear to be. If the agent relies on the chip not to try to look for a fake passport, then that's a problem.

Now, how many time have people looked at your passport to see whether it was fake or not? They don't. They scan the passport or enter its number in a computer and if it comes up with an entry that bears some of your info, you're fine. If they don't have a computerized system, they will look at some pages, stamp and let you go.

(Note: hack the passport lookup computerized system, and you have a big problem.)

Bottom line: this implementation makes it somewhat easier to obtain information about a valid passport, if you try hard enough (with the postman posing as a MIM.) But just a bit easier -- fake passport already exist, people are able to replicate its physical properties and somehow obtain/steal passport numbers that could be looked up positively in whatever unified database of passport numbers the customs are using...

Not sure what the big deal is all about... And I don't see anyone screaming about the lack of security surounding the computer systems that are used to lookup passport data -- what about them? How secure are they? How secure is the information they're transmitting? Who do they talk to? Where are the databases? Are these databases properly encrypted? How are they being backed up? Where are the backups being stored? Where are these computer located anyways? Who has access to them?
posted by NewBornHippy at 8:33 AM on November 17, 2006

Mock: most of those scenarios assume that the victim is carrying around his/her passport as a matter of course. Whatever the policy is in other countries, it's not that way in the US (at least yet). I still don't buy the need for encryption of this data.
posted by aberrant at 8:34 AM on November 17, 2006

Just in case there is any doubt about this being remotely brute forceable.

Relevant quote (since I know nobody will actually click the damn link):

"Theoretically, after intercepting the data, the security can be broken on a PC in 2 hours. This way, access is gained to personal details such as the date of birth and the facial image. The flaw is caused by dependencies in the secret key used to protect the data communication. As a result, number of keys that an attacker needs to search is considerably smaller than claimed (reduced to 35 bits). Since eavesdropping on the communication of the card or the reader is required, the eavesdropping equipment must be placed within a distance of 5 to 10 meters of the passport.

The secret key is made up of the passport expiry date, birth date and the passport number stored in the passport's Machine Readable Zone. The Dutch passport numbering scheme proves to be sequential and has a relation with the passport expiry date. Further, the last digit of the number is a checksum introducing additional predictability. The selection of a new and unpredictable passport numbering scheme would considerably improve the security"

So some back of the envelope math - if it can be broken on a pc in 2 hours, then anyone with a few hundred spare pcs can break it in under a minute. Which puts it within reach of realtime cracking for anyone who has even a shitty botnet.
posted by mock at 8:41 AM on November 17, 2006

please read this again and digest.

Like I said, when someone gets that to work, you can rightly claim this aspect of the system has been cracked. Otherwise, stop with the Cory Doctorow routine.
posted by cillit bang at 9:05 AM on November 17, 2006 [1 favorite]

Mock: most of those scenarios assume that the victim is carrying around his/her passport as a matter of course.

They may not carry it around as a matter of course, but all you have to do is stand at the main subway station for any big tourist city, and you'll find yourself a whole heckuva lot of passports!
posted by antifuse at 9:05 AM on November 17, 2006

aberrant: Most americans don't have passports. However the rest of the world doesn't have its head as far up its own ass and occasionally has to travel to other countries. This means carrying a passport. Many countries require you to carry your passport at all times when you visit them, so essentially this is the equivalent of wearing a nice big "I AM A FOREIGNER" armband. Now between this, and the possibility of indefinite stay in sunny Cuba, I'm beginning to think my dear cousins to the south don't want me to visit.

Or in slightly less hysterical terms - it means I can only use this to check for trannies in the airport lounge.
posted by mock at 9:05 AM on November 17, 2006

Mock -- I doubt it's anywhere near as long as two hours, if you have a current PC -- 2^35 is about 35 trillion keys. That may seem like a great deal, but given that modern Pentium Ds are in fact two CPUs, you're looking at throwing 2x3GHz cpus at the problem. I'd think that get 10M kps isn't unfeasible out of such of a box, that puts exhaustion of the keyspace in 3600 seconds -- an hour, and average crack into the thirty minute range.

(The big trick here, coding junkies, is get the core of the decryptor to fit into the CPU cache, so the only hits to main memory are result writes. Given that 2MB cache isn't hard to buy right now...)

Get something like a GPU working the problem, and you might easily drop that by a factor of 10.
posted by eriko at 9:07 AM on November 17, 2006

cillit bang: I've seen this software demoed by Adam. It work as I described.
posted by mock at 9:09 AM on November 17, 2006

Well make an FPP about it and we can delete this utter bullshit.
posted by cillit bang at 9:23 AM on November 17, 2006

Er, no.

3DES is actually the most secure symmetric cipher known. AES (Rijndael, really) has survived a few years of cryptanalysis; 3DES has survived decades.

2DES is the one that's only twice as hard to crack as DES -- there's a meet in the middle that works against it. But 3DES is solid. GPU's aren't relevant here; custom ASICs aren't going to be able to touch this problem.

Interestingly, there's a theoretical design that can go after RSA-1024 that involves massive amounts of custom wafers (forget chips -- think entire wafers, operating in parallel.) It's described, along with other devices, here.

Now, the problem of course is that whenever you have a strong key, the question becomes how do you safely distribute it? People are interestingly wise to the fact that they don't want to have one key shared everywhere...but they tend not to know what to do about it.

And then they put the key in the data. This happens all the time. Seriously. Key management is not only hard; it's solved wrong in similar ways over and over again.

Oh, Cillit -- it would have been real nice, in 1996, if we'd stopped using MD5 after Dobbertin showed it was going to fall, or even in 1997 after the US Government decertified it. But nooooo...we had to keep putting it into stuff. Even now, with working collisions, we still have people creating systems with this hash -- "it couldn't possibly get any worse!". *sigh*

Also, nobody pulls out 3DES to stop "casual snooping". They put it out so they could say "it's safe because it's encrypted using military grade cryptography".
posted by effugas at 9:28 AM on November 17, 2006 [1 favorite]

Someone got around a static defense? No way!
posted by Smedleyman at 9:30 AM on November 17, 2006

mock writes "Most americans don't have passports."

There is going to be a massive uptick in Americans owning passports, if for no other reason than not every American is going to stop traveling to Canada/Mexico in the next few years.
posted by Mitheral at 9:31 AM on November 17, 2006

Well, Paris, now that you've used an ad hominem to teach me that I don't know anything, how about letting me know what I got wrong?

<sub>Saying 3DES is 'three times stronger' than DES is misleading. DES uses a 56-bit key, 3DES has an effective 112 bit key. If you had a supercomputer that could crack DES in 1 second, it would still take that machine 10^9 years to crack 3DES.
--These Premises Are Alarmed

3DES is still reasonably strong (much more than "three times stronger than DES"), but this implementation is really typical of the magic bullet approach to security. I expect the underlying problem is rather similar to that faced by the US with its voting machines: a clueless, non-technical government administrator has been put in charge of a major IT project and been sold the (pointless, unworkable, counterproductive, and expensive) technology by a wily contractor. It's the latest in a long line of IT projects that the British government has proved itself totally incapable of delivering (see NHS "connecting for health" disaster).
-- hoverboards don't work on water

DES has 56 bit. 3DES has an effective 112 bits (3DES is, just as it implies, DES run three times, using three keys, the first encrypts, the second *decrypts* the encrypted first stream, the third encrypts the "decrypted" stream.)

112-56 = 56. Each extra bit doubles the time it takes to brute force. So, DES takes an hour, and 3DES takes 256hours, or 72,057,594,037,927,936 hours, or 3,002,399,751,580,330 days, or about 8 trillion years. The best attack, as of early this year, required 232 plaintexts and 288 bytes of memory, which allows you to break it in 2119 steps. (There are other tradeoffs between time and memory. Good luck with that.)
--eriko</sub>

Since others had already pointed out why you were wrong, I felt I didn't need too. But I did want to call attention to the magnitude of your error
posted by Paris Hilton at 9:53 AM on November 17, 2006

The basic problem is that they're trying to use crypto to do what a digital signature normaly does. What they want to do is prove that the passports are valid, and they could use a digital signature to do that (with or without RFID)

In fact, what they end up doing is creating an universally readable ID system (Since the encrypted data is unique). You find out what their cyphertext is, you find out who they are, and once you do that you can determine identy from the cyphertext, which is readable at a distance.
posted by Paris Hilton at 9:59 AM on November 17, 2006

@mock and aberrant:

True that most americans don't carry around their passports in daily life. But most do carry around a government issued id card (driver's license). Guess what's going soon going to be machine-readable at a distance (most likely RFID). You guess it... the REAL ID. That's by 2008.
posted by i_am_a_Jedi at 10:24 AM on November 17, 2006

Mayor West said: They all laughed at me when I bought one of these...

Exactly what is it you wish to hide, citizen?
posted by cenoxo at 10:47 AM on November 17, 2006

effugas don't all the estimates of cracking time in this thread assume a full 112 bits of random key? I think the major flaw here is that the key is horrifically unrandom. If the keyspace is only 35 bits (as implied above), doesn't that bring the cracking time, 3DES or no, down substantially?

I mean even if I have 3DES'd some data, if I tell you the key is between a and b, you don't care if it's theoretically age-of-the-universe uncrackable, you only have to try the keys from a - b.
posted by Skorgu at 11:30 AM on November 17, 2006

i_am_a_Jedi writes "@mock and aberrant:"

i_am_a_Jedi, just an FYI: we don't use the @ style here, UserIds are enough.
posted by Mitheral at 12:55 PM on November 17, 2006

One of those "my key is bigger than your key" threads.
posted by pracowity at 1:13 PM on November 17, 2006

Wait.. wait... using wireless technology like RFID to make passports... SAFER? BAHAHAHAHAHAHA
posted by tehloki at 3:25 PM on November 17, 2006