Le passeport biométrique belge recalé au BAC...

Announcement

Une équipe de recherche en cryptographie de l'Université catholique de Louvain a mis au jour de graves faiblesses dans le passeport biométrique belge, le seul type de passeport distribué depuis fin 2004 en Belgique. Les travaux menés à Louvain-la-Neuve durant le mois de mai 2007 ont montré que les passeports belges émis entre fin 2004 et juillet 2006 ne possèdent aucun mécanisme de sécurité pour protéger les informations personnelles contenues dans la puce électronique du passeport. Quant à ceux émis après juillet 2006, ils bénéficient de mécanismes de sécurité, mais ceux-ci se révèlent insuffisants. Cela signifie que quiconque muni d'un petit dispositif électronique de lecture, facile et peu coûteux à se procurer, peut voler le contenu de passeports alors qu'ils sont encore dans la poche de leur victime et, donc, à l'insu de celle-ci. Photo d'identité et signature manuscrite font partie des informations menacées. Cette nouvelle est d'autant plus surprenante que le ministre des affaires étrangères, Karel De Gucht, a déclaré le 9 janvier 2007 devant la chambre des représentants que le passeport belge bénéficiait des mécanismes de sécurité préconisés par l'Organisation de l'Aviation Civile Internationale.


Les passeports biométriques ont vu le jour en Belgique vers la fin de l'année 2004, faisant de la Belgique l'un des pays précurseurs dans le domaine. Ces passeports identifiables à leur logo sur la face avant de la couverture possèdent une puce électronique (située dans la couverture arrière du passeport) qui contient des informations personnelles sur le porteur : photo d'identité, signature manuscrite, nom, prénoms, numéro de passeport, sexe, date de naissance, lieu de naissance, lieu d'émission du document, autorité ayant délivré le document, dates d'émission et d'expiration. Cette puce est interrogeable à distance (environ 10cm avec un lecteur disponible dans le commerce) mais le standard émis par l'Organisation de l'Aviation Civile Internationale (OACI) prévoit l'utilisation de moyens cryptographiques pour protéger l'accès à distance à ces informations. Il faut selon le standard lire les deux lignes codées (Machine Readable Zone) en bas de la première page du passeport pour obtenir l'accès au contenu de la puce électronique. Le but est d'empêcher la lecture des données personnelles à quiconque ne possédant pas le passeport entre les mains.

Gildas Avoine, Kassem Kalach et Jean-Jacques Quisquater qui dirige le groupe de cryptographie de l'UCL ont cependant découvert que les passeports belges de première génération, ceux émis jusqu'en juillet 2006 et donc valides jusqu'en 2011, ne possèdent aucun mécanisme de sécurité pour assurer la protection des informations personnelles. Ils ont ainsi démontré qu'il est possible de lire le contenu d'un passeport de première génération à distance en quelques secondes sans que le porteur ne s'en aperçoive. Non seulement ces passeports ne respectent pas les préconisations de l'OACI mais ils contiennent des informations qui ne sont pas exigées par cette organisation, comme la signature manuscrite du porteur. Le vol de cette information ouvre la voie à de nombreuses actions malveillantes.

Cette découverte est d'autant plus surprenante que le ministre des affaires étrangères, Karel De Gucht, avait déclaré le 9 janvier 2007 devant la chambre des représentants, sur interpellation des députés Joseph Arens et Jean-Claude Maene : "(...) les données contenues dans la puce [du passeport] sont protégées par deux sécurités : le Basic Access Control et l'Active Authentification".

Ce n'est malheureusement qu'à partir de juillet 2006 que le passeport belge a bénéficié du Basic Access Control (BAC), mécanisme qui permet de protéger les informations personnelles. Les chercheurs de l'UCL ont alors étudié ces passeports de seconde génération et ont montré que ceux-ci souffrent également d'une très grave faiblesse, permettant à quiconque de les lire à distance sans y être autorisé. Cette faiblesse avait déjà été mise en évidence dans les passeports anglais, néerlandais, allemands, et suisses mais le passeport belge est plus sensible à cette faiblesse que les autres. Conformément au standard de l'OACI, il suffit de lire les deux lignes codées en bas de la première page du passeport pour accéder au contenu de la puce électronique. En fait, seuls sont pris en compte dans ces deux lignes la date de naissance, la date d'émission et le numéro du passeport. Il est alors possible de "deviner" ces informations en effectuant une recherche exhaustive sur toutes les combinaisons possibles date naissance / date d'expiration / numéro de passeport. Le passeport belge résiste mal à cette attaque car les numéros des passeports sont attribués par ordre croissant au moment de leur fabrication, ils sont liés à la langue du passeport, et la durée de validité du document n'est que de 5 ans. Ce sont autant d'éléments qui réduisent la plage de recherche des combinaisons possibles. Après avoir lu des passeports de première génération en quelques secondes, les chercheurs de l'UCL sont ainsi capables de lire les passeports de seconde génération en une heure si les dates de naissance et d'expiration sont connues.

Suite à leurs travaux, G. Avoine, K. Kalach et J.-J. Quisquater estiment que les passeports biométriques belges de première génération doivent être retirés de la circulation sans attendre. Ils encouragent également le gouvernement belge et la communauté européenne à exiger de l'OACI une modification du standard. Une manière simple de réparer cette faiblesse sans changer significativement le standard consiste à ajouter des caractères aléatoires dans les deux lignes codées. Les chercheurs soulignent que le passeport belge devrait également s'inspirer du passeport américain en intégrant dans sa couverture du métal, afin de former une cage de protection, dite de Faraday, qui empêcherait la lecture électronique du passeport lorsque celui-ci est fermé.

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 (English only)

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 if we assume 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 a special 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.