Belgian Biometric Passport does not get a pass...

Announcement

A research team in cryptography from the Catholic University of Louvain (Louvain-la-Neuve) disclosed serious weaknesses in the Belgian biometric passport, the only type of passport distributed in Belgium since the end of 2004. The work carried out in Louvain-la-Neuve during the course of May 2007 show that Belgian passports issued between end 2004 and July 2006 do not include any security mechanism to protect the personal data embedded in the passport's microchip. Passports issued after July 2006 do benefit from security mechanisms but these ones are flawed. This means that anyone possessing a little electronic reading device, which is easy and cheap to acquire, can steal the passport content while it is still in the pocket of the victim owners and thus without their knowing. Face and signature are among the data at risk. This news is all the more surprising because Karel De Gucht, the Minister for Foreign Affairs, declared in the Parliament on 9th January 2007 that the Belgian passport benefited from the security mechanisms advocated by the International Civil Aviation Organization.


Biometric passports appeared in Belgium around the end of 2004, putting the country among the forerunners in the field. Those passports can be recognized by the logo on their front cover. They possess a microchip (located in the back cover of the document) that embeds personal data on the owner: face, signature, name, first name, passport number, sex, date and place of birth, issue place, issuing authority, issue and expiry dates. The chip can be remotely queried (the communication range is about 10 cm with a reader available to the public) while the standard issued by the International Civil Aviation Organization (ICAO) includes the use of cryptographic means to prevent unauthorized remote access to this information. In accordance with the standard, the two coded lines (Machine Readable Zone) at the bottom of the first page of the passport have to be read in order to get access to the content of the chip. The aim is to prevent the personal data from being read by anyone who does not have the passport in his hands.

However, Gildas Avoine, Kassem Kalach, and Jean-Jacques Quisquater (who leads the Crypto Group at UCL) have discovered that Belgian passports of first generation (the ones issued until July 2006 and thus valid until 2011) do not possess any security mechanism to ensure the protection of personal data. They demonstrated that it is possible to read the content of a first generation passport at a distance and in a few seconds without the owner's notice. Not only do these passports not respect the recommendations from the ICAO but they contain non required information as the signature of the owner. The theft of this information opens the way to numerous malicious deeds.

This discovery is all the more surprising because Karel De Gucht, the Minister for Foreign Affairs, declared in the Parliament on 9th January 2007, after having been interpellated by MPs Joseph Arens and Jean-Claude Maene: "(...) the data embedded in the chip [of the Belgian passport] are protected by two security means: Basic Access Control and Active Authentication".

Unfortunately, only since July 2006, has the Belgian passport benefitted from the Basic Access Control (BAC), mechanism that allows protecting personal data. UCL researchers have thus studied these second generation passports and discovered that the latter also suffers from a very serious weakness, allowing anyone to read it at a distance without having received authorization. The weakness has already been revealed for English, Dutch, German and Swiss passports but the Belgian one is more sensitive than the others. In accordance with the ICAO standard, you just need to read the two coded lines at the bottom of the first page of the passport to get access to the content of the microchip. In fact, the only data considered in those lines are the date of birth, of expiry, and the passport number. It is then possible to "guess" this information with an exhaustive search on all the possible combinations of birth date/expiry date/passport number. The Belgian passport is less resistant to this attack than the other passports because the passport numbers are given in increasing order at the manufacture and are linked to the reference language of the passport. Moreover, the validity is only 5 years. All those elements reduce the scope of possible combinations. After having read first generation passports in a few seconds, UCL researchers managed to read any second generation passport in an hour if the date of birth and the date of expiry are known.

Further to their works, G. Avoine, K. Kalach and J.-J. Quisquater consider that Belgian biometric passports of first generation must be taken out of circulation without further delay. They also encourage the Belgian government and the European Commission to require that the ICAO modifies the standard. An easy way to fix this weakness without significantly changing the standard consists in adding random characters to the two coded lines. The researchers underline that the Belgian passport could also follow the example of the American passport and insert in its cover a radio-blocking shield (Faraday cage) that will prevent electronic reading of the passport while it is closed.

More Information

Conference

WHAT: Pas de mot de passe pour le passeport biométrique belge
WHO: Gildas Avoine and Jean-Jacques Quisquater
WHERE: Auditoire A.002, Bâtiment Euler, Louvain-La-Neuve, Belgium
WHEN: Le jeudi 14 juin 2007, de 11h à 12h

ABSTRACT: L'exposé visera à présenter le nouveau passeport électronique belge, émis depuis fin 2004, et retracera l'histoire, et les problèmes, des objets interrogeables à distance (RFID et carte sans contact). Votre vie privée peut être concernée. Enfin, apportez votre passeport, car nous terminerons par une démonstration de lecture de passeport avec du matériel courant et facilement accessible (Talk will be in French).

Scientific Paper
A scientific paper will be publicly available soon.

Technical Description

Introduction to Electronic Passport

Electronic Passport (ePassport) was used for the first time in Malaysia in 1998, thus pre-dating the ICAO standard [1]. Belgium was one of the first countries in the world to issue ePassport compliant to this standard. Nowadays, many other countries issue ePassport for example France, Germany, Nederlands, USA. The wide and fast deployment of ePassport has mainly been possible thanks to the ICAO efforts. ePassport specifications were drawn up on the basis of a detailed study over several years carried out by the ICAO since 1998. In addition the USA-VISIT program has considerably accelerated this wide spread. "The latest legislation (16/06/05) passed by US Congress states that VWP (Visa Waiver Program) countries are required to have a biometric passport issuing system in place by 26 October 2006 in order to continue as members of the program" [2].

The fundamental motivation of implementing electronic passport is to provide more secure passports through an electronic micro-chip embedded in its book. This chip allows ensuring data integrity, i.e. nobody can modify the content of a passport without being detected; this integrity is ensured by the issuing authority digital signature. Data authenticity is also protected: fabricating a passport from scratch is not possible because a counterfeiter can not create himself the signature in question. Besides, the electronic chip allows incorporating biometrics to bind a passport to its authentic citizenship, thus adding additional identification features. Due its physical and electrical properties, the chip is a very secure storage of biographical and biometric information (name, date-of-birth, passport number, facial image,...), that can be compared to those visually disclosed on the passport's first page and with biometrics of the physical person. Finally, the chip may prevent cloning or substitution through a mechanism in which the chip has to prove the possession of a public-key-based private key generated in highly secure way by the issuing state.

An electronic passport (also called biometric passport) is the same as a traditional passport combined with a small integrated circuit (chip) embedded in the book. Belgian passports incorporate this chip in the back cover.

The ICAO defines the biometric identification as a verification of human identity through the measurement of distinguishing physiological or behavioural characteristics. The ICAO only considers three types of biometrics: facial recognition, fingerprint and iris scan. Only facial recognition is mandatory.

According to the ICAO, the chip will store as a minimum the data contained on the first page of the passport and a digital image of the passport's holder. The chip may also contain optional information such as handwritten signatures, finger print, address, phone number, and may indicate information about other people namely the person to notify in case of emergency. (for more details see the Logical Data Structure [3] of the passport).

A contact-less technology (usually called RFID, short for Radio-Frequency Identification) has been chosen due to its numerous advantages compared with contact-based identification systems. Incorporating the IC into the passport book is much easier. Contact-based readers are expensive to maintain and prone to malfunction. This technology has been proven in other fields and provides high level of convenience. In the future the electronic passport may be used for automatic identity verification, self-identification, thus making the immigration inspections faster and the traveler's journey more comfortable.

However, with the absence of some cryptographic measures, this handy wireless property makes many security concerns arise in the context of electronic passport. Using a simple commercial reader, one can read all the electronic information stored in the passport. Still worse, this technology provides a way to know the presence of a passport's bearer at some place and at a specific time, thus raising the traceably problem.

Consequently, the ICAO has specified [1] amongst others many requirements and recommendations to countermeasure these issues in particular a Basic Access Control and Secure Messaging mechanism.

In this research we study the security of the Belgian electronic passport that has been deployed conforming to the ICAO standard since the end of October 2004. Before describing our attack, we will present a brief introduction to the RFID technology used in this new application, and then detail the security mechanisms required or recommended by the ICAO.

RFID technology

Formally, Radio-Frequency Identification (RFID) is an automatic identification technology relying on wireless communication, using special devices called tags. Any RFID system essentially consists of two main components: tags (transponders) and readers (transceivers).

The computational capabilities of tags depend on the target application. Tags may be a simple memory between 32 and 128 bits (tracking products and animals) up to a chip containing a microprocessor. In the case of electronic passport, the data storage capacity of the IC is a minimum of 32 KB, as specified by the ICAO, . Inin order to store the mandatory facial image and duplication of the MRZ data. States planning to store additional information must provide memories of much large capacity (70 KB). Besides, the passport chip contains a microprocessor in order to be able to accomplish complex cryptographic computations. As recommended by the ICAO the Belgian passport, for example, implements 3DES, SHA-1, and RSA. High-cost RFID tag is sometimes called contact-less chip or smart card instead, as in the case of electronic passport.

As for RFID readers they vary a lot according to the target application. Nowadays, passport readers are mainly available in governmental inspection systems on borders and airports. In the future, they may be found in airelines compagnies and hotels.

The electronic chip required by the ICAO must conform to ISO/IEC 14443 A/B, already adopted in other applications (smart cards); Belgian passport uses ISO/IEC 14443 A. One interesting property of this standard is that its maximum reading range is less than 10 cm. In fact, many researchers claim to be able to read a passport from a larger distance. In our attack we used a low-cost commercial reader without trying to go that direction.

ICAO Standards (Document 9303)

In the light of security issues arisen from the wireless technology, the ICAO has made considerable efforts in order to provide a flexible set of cryptographic mechanisms to protect the passport's data confidentiality, integrity (authenticity), and anti-cloning. These mechanisms are described below.

Passive Authentication. Thanks to the State digital signature, Passive Authentication provides data authenticity by proving that the content of the passport's chip (LDS) is not changed.

The LDS (Logical Data Structure) is a standard data organization that was specified by the ICAO to ensure global interoperability of ePassports . The LDS consists of 19 optional and mandatory Data Groups (DG) stored in separate elementary files using the same file structure as that adopted in smartcards. For example, DG1 contains the MRZ information; DG2 contains the face image in JPEG format, DG3 for encoded finger, DG4 for encoded iris and DG7 for handwritten signature. Note that only DG1 and DG2 are mandatory. The hash of each data group is computed. All these hashes together make up the LDS security object. This object is signed by the issuing State Private Key and the result is called Document Security Object (SO_D); therefore the inspection system should have the public key of all issuing States.

Surprisingly, it is the only mandatory cryptographic feature required in the ICAO standard. However, passive authentication does not prevent skimming, eavesdropping and chip cloning. For example, anyone who has a simple RFID reader and software can easily interrogate the chip and obtain all its contents. Therefore the ICAO recommended other additional security features incuding Basic Acess Control and Active Authentication.

Basic Access Control (BAC). Basic Access Control is a countermeasure against skimming and eavesdropping, by authenticating the reader and establishing session keys for secure messaging between the chip and the reader.

When BAC is supported the reader cannot get any information from the passport unless it goes through a challenge-response protocol (based on 3DES) in which it proves to the passport the knowledge of the Document Basic Access Keys (KENC and KMAC). These keys are derived from the MRZ information. The MRZ (Machine-Readable Zone) is the two-line string of characters located at the bottom of the passport's first page. The MRZ can be seen to the naked eye for visual inspection and usually read by an OCR reader. The only characters allowed in the MRZ are A-Z, 0-9, and < that acts as filler. MRZ information is the part that used to generate the BAC keys (KENC and KMAC): date of birth, date of expiry, document number and their corresponding check digit.

Fig. 1. Basic Access Control

Secure Messaging After successful execution of the reader authentication, two of the random values generated during this protocol are XORed together (K_P XOR K_R) to obtain a key seed which is in turn used to derive session keys using the same key derivation procedure. These keys are used to encrypt all the subsequent communications. This mechanism is called secure messaging.

Active Authentication (AA). When an attacker has access to the passport's chip, he is able to simulate it for cloning or for substituting it by another one (e.g. interchanging covers of two passports).

Active authentication is recommended to prevent chip cloning or substitution using a challenge-response protocol, based on public key cryptography, in which the passport proves the possession of a private key. This private key is stored in a secure memory while the corresponding public key is stored in DG15 of the LDS. This mechanism requires more computational power on the chip.

Fig. 2. Active Authentication

Attack on first generation passports

In this section we describe our attack against the first Belgian electronic passport. For that we did not use any homemade material, only a cheap and easy-to-acquire one. Indeed we used a reader ACG 13.56 MHz, compliant with ISO 14443 A/B. The reader can reach 115200 bauds.

To communicate with the reader, we implemented Document 9303, based on the previous work done by Adam Laurie. Our implementation failed when the command GET_CHALLENGE was sent; this command is required to perform the Basic Access Control. This failure was encountered because the passport we received from a member of the Crypto Group, did not implement the BAC mechanism. It turns out that some passports reply to this command correctly while others do not. We realized that Belgian passports may be grouped into two or more categories. Later, our study confirmed the presence of two generations: the first generation comprises passports issued from end 2004 till mid 2006 and does not support BAC, while the second generation includes passports issued after mid 2006 and does support BAC.

Since a first generation passports does not use BAC, it is very simple to get its electronic contents even without the knowledge of its holder: putting the passport in the field of our reader is enough... that may be desappointing to some cryptographers... It takes about 10 seconds with our modest reader to obtain all the information; that is the mandatory digitized picture of the passport's holder and the content of the MRZ (first and family name, birth date, passport number, etc.). Surprizingly, the Belgian passport contains data not required by document 9303. Indeed, it contains also a digitized picture of the handwritten signature of the passport's holder. It also contains optional information like place of birth, place of issue, and date of issue. Still worse, recovering the MRZ can be done in a fraction of a second, while recovering the two pictures requires a few seconds (face about 20 KB and signature about 10KB). This result implies that an attacker, interested in passport's MRZ only, can just pass near the victim even without staying in front of him.

To skim someone's passport, it is not always possible to have physical access to his passport. Therefore we tried the following tests to prove our claim. Whether the passport was in a purse, pocket or a handbag, we could also interrogate the passport and get its contents. This kind of attack is very realistic in trains, airplanes and airports. All you need is to pass close enough to the victim and stay a few seconds if you want to get the whole content of the passport.

During this research, we were not interested in extending the reading range, a field being worked on by other groups. So people or organizations interested in stealing information or tracking people can certainly have such powerful readers without any doubt. In this case this attack would be easier and more efficient.

Note that diplomats, in some countries, were among the first citizens to receive biometric passports. Unfortunately, we could not confirm this information in the case of Belgium. If it is the case, this implies that Belgian diplomats have first generation passports that are not protected by any security mechanism.

Attack on second generation passports

Secong generation passports are issued after July 2006 and they implement BAC. Therefore, they became more secure against clandestine skimming. However, the the access control keys are derived from easy-to-get MRZ information. In many real life situations, one may be somehow asked to reveal its passport's information. For example, here is a real life example of one of the authors. Being a foreigner, he had to provide a passport copy to local police, employees department, PhD student department and driving license office when arriving in Belgium. In addition, he had to reveal its visual data in the bank and hotel.

Now let's rather be optimistic and assume that the MRZ information is relatively difficult to find. We will show that an attacker can still have access to the passport's microchip by "guessing" the information needed to successfully perform the BAC. Note that similar works have been previously carried out in other countries (UK, Germany, Nederlands, Switzerland, etc.), but the Belgian passport is particularly weak against this attack as explained below.

According to Document 9303, the structure of the date of birth is YYMMDD, thus implying an entropy of log(100 x 365.25) = 15.16 bits. The entropy of the date of expiry is log(10 x 365.25) = 11.83, considering the maximum validity period of passports recommended by Document 9303(10 years). Containing up to 9 characters, the passport number may only contain A-Z and 0-9 (the symbol '<' is just a filler. Therefore the entropy of the passport number is log((26 + 10)⁹) = 46.53 at maximum. It turns out that the total entropy of the MRZ information is about 73 at best. However the effective entropy is much lower, estimated to 56 bits at best acccording to ICAO report, mainly because of the passport numbering schemes commonly used.

Passport numbers may consist of digits only or a combination of alphanumeric characters. Some countries adopt sequential numbering while others use random numbering. US passport number for example consists of 9 digits where the first two digits are used to encode one of the fifteen passport issuing agencies so that its entropy becomes 27 and the total entropy decreases to 54 at best.

In the case of Belgian passport the situation is even worse: the passport number consists of 2-letter prefix and 6­-digit suffix. Moreover, its validity period is 5 years only, implying a total entropy of 29+10+15= 54 at best. Having observed many passports supplied by members of our research department (but also supplied by their friends, sisters, daughters, mother, etc.), we noticed that passport numbers are chosen sequentialy (simple counter) during manufacture. More precisely, numbers given to passports while production remain the same in the personalisation (final) phase. This implies that the passport number depends on the manufacture date and there is consequently a strong correlation between the date of issue (and so date of expiry) and the passport number.

Fig. 3. (French-written) Belgian passport numbers according to expiry dates

A sample of  francophone (French-speaking people) passport numbers distribution is depicted in Fig.3, according to the date of issue. The crosses represent the passport numbers we observed. They are not on a straight line because passport numbers are drawn according to the issuing dates instead of manufacture dates.  For some unkown reason (probably logistic), there is not a perfect translation between date of manufacture and date of issue. This slows down our cracking program because we must search the targeted passport number in a 1-dimension space around the theoretical passport number that is perfectly on the expected line. Consequently, for a given expiry date, a few thousand passport numbers must be checked. Currently, for each expiry date, we check 24,000 passport numbers, but this value steadily decreases since we read new passports every day. Theoretically, we could decrease this number until the number of passport issued every day in Belgium, i.e. a few hundreds.

On the other hand, Fig.3 also shows discontinuous segments(strange behavior). In fact, it took time to determine that numbers corresponding to the "holes" (spaces) belong to Flemish-citizen (or possibly German-citizen) passport books. Belgium has tree official languages (French, Dutch, and German), and a Belgian citizen receives a passport with the language of the area he lives in or, in some special cases (e.g. in Brussels) with the language of his choice. Therefore, knowing the living place or the mother tongue of the victim decreases the complexity of the attack. For this reason, our attack is more efficient against passports of French-speaking citizens than Flemish passports because we did not receive enough Flemish passport numbers (The latter is not depicted on Fig. 3).

Given this heuristic on the passport numbers, and assuming that the date of birth is known, we carry out an exhaustive search on the expiry date and on each of the passport numbers (about 24,000). When the birth date is known, Fig. 4 represents the corresponding search space of the exhaustive search. The yellow area represents the search space without any heuristic on the passports. The red-dashed area represents the search space in which we carry out our exhaustive search, considering our heuristic. This technique really improves the attack because with a real-scaled picture, we would see that the red-dashed zone only represents 2.4% of the yellow zone.

Fig. 4. Search area

Let's consider now a practical attack where both birth date and expiry date are known. In this case, the attack takes less than one hour in the worst "common" case (having 24,000 passport numbers to verify at a rate of about 400 checks per minute). More precisely, this means that all the passports we tried during our work have been or would have been cracked within one hour in the worst case. However, it may arise that a passport number is not in our search space (passport with an specail number, e.g. an emergency passport). We never saw this case but it may happen.

Note that our program could be improved and the communication speed could be increased. We could even use further heuristics; for example we noticed that none of the passports we have read was issued on Saturdays or Sundays. This would allow to decrease by almost 30% the running time of the attack. Without any official information about that, we did not implement this heuristic.


References:
[1] PKI for Machine Readable Travel Documents offering ICC Read-Only Access, Technical Report Version 1.1, ICAO, October 01, 2004.
[2] http://www.trailfinders.com/visas/visawaiver.htm
[3] Machine Readable Travel Documents. Technical report, Doc 9303 Part 1 Volume 2, 9th draft (6th edition), ICAO, 20th July 2005.

Acknowledgment

We would like to kindly thank several people who helped us during this work. First of all, Danny De Cock (KULeuven) and Elke Demulder (KULeuven) for recent interesting discussions: they also worked on Belgian biometric passports and confirmed some of our results. Let's mention as well Yves Poullet (CRID, FUNDP), Serge Vaudenay (EPFL), Martin Vuagnoux (EPFL), Adam Laurie (RFIDIOt.org), and Pierre-Yves Millet (RTBF) for providing helpful information.

We would also like to thank all members of the ELEC department of the UCL for providing us their passports data. For their special help, we would like to thank namely: Sylvie Baudine, Lilian Bohy, Baudoin Collard, Marwan El-Habre, Damien Giry, Momamad Kalach, Olivier De Marneffe, Guerric Meurice De Dormale, Olivier Pereira.

Finally, we thank Eurocrypt 2004's organizers for the handbag they provided to attendees; it fits very well to hide our laptop and reader.