Estonian Electronic Identity Card:
`Security Flaws in Key Management
`Arnis Parsovs, Software Technology and Applications Competence Center
`and University of Tartu
`https://www.usenix.org/conference/usenixsecurity20/presentation/parsovs
`
`This paper is included in the Proceedings of the
`29th USENIX Security Symposium.
`August 12–14, 2020
`978-1-939133-17-5
`
`Open access to the Proceedings of the
`29th USENIX Security Symposium
`is sponsored by USENIX.
`
`1
`
`APPLE 1015
`
`

`

`Estonian Electronic Identity Card:
`Security Flaws in Key Management
`
`Arnis Parsovs1,2
`1Software Technology and Applications Competence Center, Estonia
`2University of Tartu, Estonia
`
`Abstract
`The Estonian electronic identity card (ID card) is considered
`to be one of the most successful deployments of smart card-
`based national ID card systems in the world. The public-
`key cryptography and private keys stored on the card enable
`Estonian ID card holders to access e-services, give legally
`binding digital signatures and even cast an i-vote in national
`elections.
`In this paper, we describe several security flaws found in
`the ID card manufacturing process. The flaws have been dis-
`covered by analyzing public-key certificates that have been
`collected from the public ID card certificate repository. In
`particular, we find that in some cases, contrary to the secu-
`rity requirements, the ID card manufacturer has generated
`private keys outside the chip. In several cases, copies of the
`same private key have been imported in the ID cards of differ-
`ent cardholders, allowing them to impersonate each other. In
`addition, as a result of a separate flaw in the manufacturing
`process, corrupted RSA public key moduli have been included
`in the certificates, which in one case led to the full recovery
`of the corresponding private key. This paper describes the
`discovery process of these findings and the incident response
`taken by the authorities.
`
`1 Introduction
`
`Estonia issues several types of credit card-sized identity doc-
`uments (hereinafter – ID cards) that contain a smart card
`chip. The cryptographic functionality embedded in the chip
`enables secure authentication over the Internet and creation
`of legally binding digital signatures. The Estonian ID card
`roll-out started in 2002 and is considered to be one of the
`most successful in the world in respect to dissemination and
`active use. From the 1.3 million Estonian residents, 67% have
`used the ID card electronically at least once in the second half
`of 2018 [1].
`The security of this electronic identity scheme depends on
`the secrecy of a cardholder’s private keys. It is crucial for
`
`private keys to be generated in a secure manner and to be
`accessible only to the corresponding cardholder. In the Es-
`tonian ID card scheme, similarly as in many other countries,
`the key management (key generation, certificate issuance) is
`delegated to the ID card manufacturer. It is therefore essen-
`tial to ensure that the manufacturer generates keys of good
`quality and does not store copies of the generated keys. Un-
`fortunately, there are no effective controls to verify that the
`manufacturer is trustworthy and handles the key management
`correctly. The industry response to these concerns has been
`that manufacturers are in the business of trust and therefore
`they would never risk their reputation by engaging in sloppy
`security practices or malicious behavior.
`Our contribution in this work is to show, by example of
`the Estonian ID card, that this trust model does not always
`work. We show that the ID card manufacturer has engaged in
`sloppy security practices, ignoring repeated signs of faults in
`the key management process, and has intentionally breached
`the ID card manufacturing contract in some cases creating
`copies of cardholders’ private keys. While these findings
`have resulted in open litigation against ID card manufacturer
`Gemalto [2], there is no evidence that this loss of trust would
`have an impact on Gemalto’s reputation or its business value
`and hence would have served as a deterring factor for such
`misbehavior.
`Our findings are based on the analysis of the ID card public-
`key certificates collected over the years from the public ID
`card certificate repository. The findings are presented as three
`separate studies performed over different periods of time. For
`each study we present the context and describe the process of
`how the flaws were identified and handled.
`First, we discovered that several ID card certificates shared
`the same RSA public keys. After further investigation we
`found that the affected ID cards also shared the same private
`keys. The discovery of duplicate private keys suggested that
`contrary to the security requirements, the ID card manufac-
`turer had generated keys outside of the card. We obtained
`convincing evidence that most of the ID card keys had been
`generated in the card, while a specific set of keys produced in
`
`USENIX Association
`
`29th USENIX Security Symposium 1785
`
`2
`
`

`

`the ID card renewal process had been generated outside the
`card. Our conclusion is that this violation was likely motivated
`by performance reasons.
`We also found a separate fault in the ID card manufacturing
`process that resulted in corrupted RSA public key moduli
`being included in the certificates. In one instance we were
`able to fully factorize the affected key demonstrating the
`security impact of the fault. We analyzed the possible causes
`for the corruption and discussed prevention and detection
`measures.
`The rest of the paper is organized as follows. Section 2 in-
`troduces the Estonian ID card ecosystem and smart card chip
`platforms used over the years. Section 3 gives an overview of
`related security flaws the Estonian ID card has experienced.
`The next three sections describe the main findings of this
`paper. Finally, Section 7 concludes the paper.
`
`2 Estonian ID card
`
`2.1 Cryptographic functionality
`From its introduction in 2002 until now, the core crypto-
`graphic functionality provided by the Estonian ID card has
`stayed the same. The ID card contains two asymmetric (RSA
`or ECC) keys with the corresponding X.509 public-key cer-
`tificates, and symmetric keys to perform card management
`operations with the card.
`Authentication key. The authentication key is used to log
`into e-services by providing a signature in the TLS client
`certificate authentication process [3]. This key can also be
`used to decrypt documents encrypted for the cardholder [4].
`Signature and decryption operations with this key have to be
`authorized using the 4-digit PIN1 code.
`Digital signature key. The digital signature key is used to
`give legally binding digital signatures that under eIDAS [5]
`are recognized as qualified electronic signatures. Each sig-
`nature operation with the key has to be authorized using the
`5-digit PIN2 code.
`Card management operations. The cards are preloaded
`with symmetric keys that can be used by the manufacturer
`to perform various card management operations in the post-
`issuance phase. This allows to reset PIN codes in case the
`cardholder forgets them, generate new keys, write new cer-
`tificates, and even reinstall the whole smart card applet if
`needed.
`
`2.2 Parties involved
`ID cards are identity documents issued by the state. The Police
`and Border Guard Board (Politsei- ja Piirivalveamet – PPA)
`is the authority responsible for procurement of ID card manu-
`facturing services and the issuance of identity documents.
`From the introduction of ID cards in 2002, the manufac-
`turing and personalization of cards was performed by Trüb
`
`Baltic AS. In February 2015, Trüb Baltic AS with their parent
`company Trüb AG was acquired by Gemalto. As of the end
`of 2018, the ID cards have been manufactured by Oberthur
`(now known as IDEMIA).
`The ID card certificates are issued by the privately-owned
`Estonian Certificate Authority (CA) SK ID Solutions AS
`(hereinafter – SK). According to eIDAS terminology, SK is a
`qualified trust service provider issuing qualified certificates.
`SK is a subcontractor of the card manufacturer.
`The Estonian Information System Authority (Riigi Infos-
`üsteemi Amet – RIA) is the state agency responsible for co-
`ordination and development of electronic identity and cyber
`security. Among other tasks, RIA organizes the development
`of ID card client-side software.
`
`2.3 Chip platforms and document types
`In this section, we chronologically introduce smart card plat-
`forms used over the years and the corresponding identity
`document types. We use the generic term ID card to refer
`to all identity document types covered. The SIM card-based
`digital identity card, in a Mobile-ID format, is not covered in
`this work.
`
`2.3.1 MICARDO
`
`In 2002, Estonia introduced the identity card, a mandatory
`identity document for all Estonian residents aged 15 and
`above. The electronic functionality of the card was imple-
`mented on top of smart card operating system MICARDO
`Public 2.1 [6]. The smart card interface is documented in
`the EstEID specification [7], which later became a national
`standard [8]. MICARDO-powered ID cards were issued from
`2002 to 2011 (Figure 1). The platform is limited to 1024-bit
`RSA keys.
`
`Figure 1: MICARDO-powered identity card issued from
`2002-01-01 to 2010-12-31 [9]
`
`2.3.2 MULTOS
`
`In October 2010, a digital identity card was introduced. Since
`this document can only be used electronically, it can be per-
`sonalized in PPA customer service points and issued instantly.
`The purpose of the digital identity card is to provide a backup
`solution in the event the cardholder’s identity card cannot be
`
`1786 29th USENIX Security Symposium
`
`USENIX Association
`
`3
`
`

`

`used. The card is powered by MULTOS I4E platform by Key-
`Corp [10]. The MULTOS applet has been developed to mimic
`the MICARDO interface described in the EstEID specifica-
`tion. MULTOS-powered cards were issued until December
`2014 (Figure 2). The platform is limited to 1024-bit RSA
`keys.
`
`Figure 2: MULTOS-powered digital identity card issued from
`2010-10-01 to 2014-11-30 [9]
`
`2.3.3 jTOP SLE66
`
`In 2011, the manufacturing of identity cards switched to a
`new chip platform implemented on top of Infineon’s product
`JCLX80jTOP20ID masked on a SLE66CX800PE chip [11]
`(Figure 3). The card runs jTOP (Java Trusted Open Platform)
`JavaCard operating system developed by Trusted Logic. The
`EstEID functionality is implemented in the JavaCard applet.
`The platform uses 2048-bit RSA keys. With the introduc-
`tion of the jTOP SLE66 platform, the residence permit card
`was introduced (Figure 4). This card is issued to non-EU
`third-country nationals residing in Estonia. The jTOP SLE66-
`powered ID cards were issued until the end of 2014.
`
`Figure 3: jTOP SLE66/SLE78-powered identity card issued
`from 2011-01-01 [9]
`
`Figure 4: jTOP SLE66/SLE78-powered residence permit card
`issued from 2011-01-01 [9]
`
`2.3.4
`
`jTOP SLE78
`
`At the end of 2014, the production of identity cards, resi-
`dence permit cards and digital identity cards switched to
`jTOP SLE78 platform. The visual design of identity cards
`and residence permit cards stayed the same (Figure 3 and 4),
`however, the visual appearance of digital identity cards be-
`came a bit more colorful (see Figure 5). The EstEID func-
`tionality was implemented in a JavaCard applet on top of
`Infineon’s product SLJ52GCA080CL [12] masked on the
`SLE78CLX800P chip [13] that runs the jTOP JavaCard oper-
`ating system developed by Trusted Logic. With the switch to
`jTOP SLE78 platform, the e-resident’s digital identity card
`was introduced (Figure 5). This card is issued through the
`e-Residency program [14] to persons who are not residents
`of Estonia. In the beginning of 2017, the diplomatic identity
`card was introduced (Figure 6). This card is issued to persons
`with diplomatic status. Initially, the jTOP SLE78 platform
`used 2048-bit RSA keys, but due to the ROCA flaw (see Sec-
`tion 3), at the end of 2017, the switch to ECC keys using curve
`P-384 was made. The jTOP SLE78-powered ID cards were
`issued until the end of 2018. ID cards manufactured currently
`are powered by the chip platform supplied by IDEMIA (not
`covered in this work).
`
`Figure 5: jTOP SLE78-powered digital identity card and e-
`resident’s digital identity card issued from 2014-12-01 [9]
`
`Figure 6: jTOP SLE78-powered diplomatic identity card is-
`sued from 2017 [15]
`
`USENIX Association
`
`29th USENIX Security Symposium 1787
`
`4
`
`

`

`Figure 7: ID card certificates analyzed in this work (by issuance month)
`
`2.4 Certificate repository
`All valid ID card certificates issued by SK are available in
`the public LDAP directory ldap://ldap.sk.ee [16]. The
`publication of certificates is motivated by the document en-
`cryption use case, providing convenient means for senders to
`obtain public keys of recipients.
`ID card certificates contain the cardholder’s full name and
`personal identification code (personal ID code). The personal
`ID code is a unique 11-digit number that generally remains
`fixed for the lifetime of the person and therefore is widely
`used in public and private databases to identify persons. The
`validity period of the certificate usually corresponds to the
`validity period of the identity document in which the corre-
`sponding private key resides.
`
`2.5 Certificates analyzed in this work
`Over the years, we have collected more than 7 million ID card
`certificates published in LDAP certificate repository. The
`certificate search in the repository is restricted to the personal
`ID code. However, since the search space for all possible
`personal ID codes is relatively small, over time certificates
`of all possible personal ID code holders could be crawled.
`Our certificate dataset is not complete, but we believe that it
`contains a representative sample of ID card certificates issued
`throughout the years. Figure 7 shows the distribution of ID
`card certificates in our dataset by issuance month (based on the
`certificate’s notBefore field1) for different ID card platforms.
`The corresponding platforms have been determined by the
`certificate fields and properties of the public keys. Due to the
`crawling process, the dataset lacks certificates issued from
`2002 to 2007 and certificates which have been valid for a short
`period of time. Therefore, in general, our findings provide only
`a lower bound for the number of affected certificates.
`We also collected certificate revocation information accu-
`mulated in publicly available CRLs [17]. The information in
`
`1The notBefore field represents the time at which the certificate starts to
`be valid and usually corresponds to the time when the certificate was issued.
`
`CRLs can be used to deduce the time when the cardholder vis-
`ited the document issuer to receive their new ID card and the
`old one was revoked. This information and also some other
`peculiarities of the ecosystem allowed us to deduce many
`important insights for this study.
`
`3 Related work
`
`Over the 17 years of the Estonian ID card history, several
`ID card-related security flaws have been publicly disclosed.
`More than 700 000 ID cards powered by the jTOP SLE78
`platform were affected by Infineon’s RSA key generation flaw
`(the ROCA flaw) [18]. The vulnerability in Infineon’s propri-
`etary RSA key generation algorithm allowed the factoring of
`2048-bit RSA key in only 140.8 CPU-years. The discovery
`of this flaw in 2017 started the so-called Estonian ID card cri-
`sis, which was mitigated by switching to the ECC algorithm
`implemented by the platform and revoking vulnerable RSA
`certificates [19].
`Publicly less noticed was a flaw in the jTOP SLE66
`ID cards issued in 2011. Due to a publicly undisclosed flaw
`in EstEID JavaCard applet developed by the ID card manu-
`facturer, 120 000 ID cards issued in 2011 were recalled [20].
`While the authorities claimed that the card is secure and all
`transactions made with the card are fully reliable [20], later
`after the ROCA flaw broke out, it was disclosed in the media
`that the flaw in the 2011 ID cards was exploitable by having
`access to the card [21]. The context indicates that this may
`have been a type of PIN bypass flaw.
`In 2002, it was discovered that PIN codes were printed
`in too dark, allowing for them to be seen through the PIN
`envelope [22]. Ironically, the same flaw in PIN envelopes
`was reintroduced by IDEMIA in 2018 after taking over the
`manufacturing of ID cards [23].
`There have been incidents of including duplicate email ad-
`dresses in certificates [24], issuing certificates with incorrectly
`encoded public keys [25], failing to revoke certificates of de-
`ceased persons [26] and others. Detailed analysis of these and
`other flaws related to the Estonian ID card are covered in [19].
`
`1788 29th USENIX Security Symposium
`
`USENIX Association
`
`MICARDO
`MULTOS
`jTOP SLE66
`jTOP SLE78
`
`70K
`
`60K
`
`50K
`
`40K
`
`30K
`
`20K
`
`10K
`
`0K
`
`
`
`2008-012008-032008-052008-072008-092008-112009-012009-032009-052009-072009-092009-112010-012010-032010-052010-072010-092010-112011-012011-032011-052011-072011-092011-112012-012012-032012-052012-072012-092012-112013-012013-032013-052013-072013-092013-112014-012014-032014-052014-072014-092014-112015-012015-032015-052015-072015-092015-112016-012016-032016-052016-072016-092016-112017-012017-032017-052017-072017-092017-112018-012018-032018-052018-072018-092018-112019-012019-032019-05
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5
`
`

`

`4 Certificates with duplicate RSA public keys
`
`In spring 2013, we discovered several certificate pairs in our
`dataset containing the same RSA public key. In most cases
`the public keys were shared between the authentication and
`digital signature certificates of the same ID card, however,
`in two occasions the same public key was shared between
`two different cardholders. The occurrence of such a fault
`could only have happened through a deep violation of the
`production processes, since each key pair is required to be
`unique even for the keys on the same ID card.
`The set of 10 identified certificate pairs containing duplicate
`public key is listed in Table 1. All certificates have been
`issued for jTOP SLE66-powered ID cards. For each pair, the
`certificate issuance times have just a few seconds difference,
`indicating that the certificates were issued in parallel or close
`to each other. In most of the cases, the duplicate public keys
`were the result of the ID card renewal process, performed in
`the PPA customer service points, to replace the vulnerable
`applet for ID cards issued in 2011 (see Section 3).
`
`No Time of cert issuance Type Cardholder
`sign Ülle
`2012-11-06 15:35:09
`2012-11-06 15:35:46
`auth
`Toivo
`2013-02-06 15:35:54
`auth
`2013-02-06 15:35:56
`sign
`2013-02-07 12:18:34
`auth
`Sandra
`2013-02-07 12:18:37
`sign
`2013-02-19 09:09:58
`auth Nadiia
`2013-02-19 09:10:08
`sign
`auth Moonika
`2013-02-25 09:33:17
`2013-02-25 09:33:29
`sign
`sign
`Richard
`2013-03-04 11:36:08
`2013-03-04 11:36:38
`auth Anu
`2013-03-30 13:40:38
`auth
`2013-03-30 13:40:40
`sign
`2013-03-30 13:42:03
`auth
`2013-03-30 13:42:05
`sign
`2013-04-15 09:16:11
`auth
`2013-04-15 09:16:28
`sign
`2014-10-08 12:01:16
`auth
`2014-10-08 12:04:31
`sign
`
`Phillip
`
`Leili
`
`Jaan
`
`Liis
`
`Siim
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`Issuance
`PPA renewal
`PPA renewal
`
`Expiry date Revoked
`2016-07-07
`2016-06-27
`2016-07-04
`2014-11-21
`
`Warranty
`2014-10-09
`2014-10-09
`
`PPA renewal
`
`2016-11-14
`
`2015-05-04
`
`2015-01-06
`
`PPA renewal
`
`2016-01-02
`
`expired
`
`not issued
`
`PPA renewal
`
`2016-11-24
`
`2016-11-08
`
`2014-12-22
`
`PPA renewal
`
`2016-08-22
`
`2014-12-30
`
`2014-12-22
`
`PPA renewal
`PPA renewal
`
`2016-11-30
`2016-08-12
`
`2014-10-13
`2014-10-23
`
`2014-10-09
`2014-10-09
`
`initial
`
`initial
`
`2018-03-26
`
`2015-05-14
`
`2014-12-22
`
`2018-03-26
`
`2014-12-30
`
`2014-12-22
`
`PPA renewal
`
`2016-05-06
`
`expired
`
`2014-12-22
`
`initial
`
`2019-10-07
`
`2017-10-03
`
`not issued
`
`In the cases where the same public key is shared between
`the digital signature and authentication certificates of the same
`ID card, the risk is that the knowledge of only one PIN (PIN1
`or PIN2 depending on which slot contains the corresponding
`private key) allows the card to be used for both purposes.
`A more serious risk occurs in the two cases where the same
`public key is shared between different cardholders. For exam-
`ple, in case of pair 1, depending on whose ID card contains the
`corresponding private key, either Toivo can sign on behalf of
`Ülle, or Ülle can use her digital signature key to authenticate
`electronically as Toivo and decrypt files encrypted for Toivo
`(these use cases, however, would require the modification of
`the software).
`It could not be excluded that the ID cards actually do con-
`tain duplicate private keys. However, if this was the case, the
`only credible explanation would be that contrary to the secu-
`rity requirements, the manufacturer had generated the keys
`outside the card and due to a flaw in the personalization pro-
`cess the same key was imported in two different ID cards/key
`slots.
`4.2 Proof that ID cards share the same keys
`Since we had a suspicion that private keys might be generated
`outside the ID card, we decided to investigate the shared
`public keys of the digital signature certificate of Ülle and
`authentication certificate of Toivo (pair 1).
`In summer 2013, we were able to get in contact with Toivo,
`who informed us that his ID card was renewed in a PPA cus-
`tomer service point in Viljandi. He provided us cryptographic
`proof that both private keys in his ID card correspond to the
`public keys specified in the certificates. To demonstrate that
`Toivo’s authentication private key can be successfully used
`to forge a digital signature of Ülle, with the assistance from
`Toivo2, we created a proof-of-concept digital signature con-
`tainer in the name of Ülle (see Figure 8).
`We did not manage to get in contact with Ülle to obtain
`a similar cryptographic proof from her ID card. In October
`2014, we learned that the manufacturer had discovered the
`incident, since Toivo was invited to replace his ID card with a
`new one issued under warranty. The certificates of Ülle’s ID
`card, however, remained valid. In spring 2015, we obtained
`confirmation from an Estonian service provider that Ülle had
`used the ID card for both authentication and signing in the
`e-service of the service provider. While this convinced us that
`her ID card contained the same private key, we still hoped
`to obtain cryptographic proof of that. In summer 2016, we
`managed to get in contact with Ülle’s daughter who informed
`us that her mother used the card daily to sign banking trans-
`actions online, however, attempts to get in touch with Ülle
`herself did not succeed. Later we learned that her ID card was
`renewed in a PPA customer service point in Tallinn.
`
`2Toivo was informed about the proof-of-concept signature forgery experi-
`ment, but not the nature of the flaw being exploited.
`
`Table 1: Certificate pairs with duplicate public keys
`
`4.1 Possible cause and impact
`One explanation for these duplicate keys could be a poor
`source of randomness used in the on-card key generation pro-
`cess. However, we would expect such a failure to manifest
`randomly, independently of the time when the key is gener-
`ated, since the ID card chip has no built-in time source that
`could be, for example, used to seed a pseudo-random number
`generator. Since the keys for the affected ID cards have been
`generated within an interval of a few seconds, this hypothesis
`can be safely rejected.
`The close timing of the certificate issuance suggests that
`due to some software bug (such as race condition) a wrong
`public key was included in the certificate, i.e., the same public
`key was sent as a part of certificate signing request twice.
`This, however, would result in at least one of the certificates
`from the pair not being usable electronically, as the actual
`private key residing on the ID card would not correspond to
`the public key included in the certificate.
`
`USENIX Association
`
`29th USENIX Security Symposium 1789
`
`6
`
`

`

`her, therefore she kept using her ID card until its expiration.
`In a meeting on 2017-02-06, we informed RIA about the
`case of Toivo and Ülle and the most likely explanation of keys
`being generated outside the ID card. At that time, we did not
`exclude the possibility that RIA and PPA may be well aware
`of the true reasons behind the flaw.
`When approached by the authorities, the manufacturer re-
`sponded that this was the old case already investigated in
`2014 and that the mistake only occured with public keys. At
`the end of 2017, RIA ordered a follow-up study to determine
`whether any further evidence of key generation outside the
`ID card could be found [27]. Using statistical methods, strong
`evidence was found, that in the renewal process in PPA cus-
`tomer service points the keys were generated outside the ID
`card (see Section 5).
`As we see in Table 1, the certificates with duplicate public
`keys were also found in 3 pairs of initially issued ID cards.
`These cases could be the result of a separate personaliza-
`tion fault where the cards actually do not contain duplicate
`keys. We urged RIA and PPA to investigate this, by using the
`database of OCSP certificate validity responses maintained
`by SK, to see whether the relying parties had requested va-
`lidity confirmation of the involved certificates. From this it
`would be possible to infer whether the ID cards had been
`used successfully hence containing the keys specified in the
`certificates. We are not aware if this has been investigated.
`
`5 Private keys generated outside the ID card
`
`At the end of 2013, in the context of Snowden revelations,
`an opinion piece was published in Estonia [28] expressing
`concerns about authorities having copies of ID card private
`keys. The authorities rebutted the concerns [29], claiming that
`the recording of private keys is ruled out by the technological
`scheme used, i.e., the keys are generated inside the chip and
`the ID card is designed so that the private key itself never
`leaves the card.
`Indeed, the security requirement of ID card key genera-
`tion inside the chip has already been present in the ID card
`concept [30], has been documented in the EstEID technical
`specification (Section 4.1.5 in [7]), has been specified in SK
`certification policy according to which the CA is audited (Sec-
`tion 6.1.2 in [31]), and has also been present in the ID card
`manufacturing contract between the manufacturer and the
`state.
`The rationale behind this requirement is that key generation
`inside the chip provides higher security. It is easier to ensure
`that copies are not created, rather than to make sure that all the
`copies have been irreversibly destroyed to eliminate potential
`misuse. For example, the Mobile-ID technology comes with
`extra risks, since it is documented that the keys for Mobile-ID
`are generated outside the chip (Section 6.1.1.3 in [32]).
`In this section we describe our efforts to establish the true
`origins of the ID card private keys on each ID card platform.
`
`Figure 8: Digital signature of Ülle forged using the authenti-
`cation key of Toivo
`
`A similar (non-cryptographic) confirmation that both keys
`of the card are usable electronically was also obtained from
`Liis (pair 9).
`The ability to successfully use both certificates involved
`in the duplicate certificate pair shows that the affected ID
`cards/key slots do share the same private keys that were ap-
`parently imported due to an error (e.g., race condition) in the
`ID card renewal process.
`
`4.3 Incident response
`In October 2014, at the latest, the manufacturer learned of
`the anomaly of duplicate keys. On 2014-10-09 a new ID card
`was produced for Toivo and on 2014-10-10 Toivo received
`an invitation from PPA to replace his ID card with a new one
`under warranty. The email stated that the ID card renewal
`on 2012-11-06 was unsuccessful and the card could not be
`used electronically (which actually was not true). For other
`cardholders the replacement cards were issued on 2014-10-09,
`2014-12-22 and 2015-01-06 (the last column in Table 1). For
`unknown reasons the duplicate keys on the ID card of Sandra
`(pair 3) were missed, as for her the replacement ID card was
`not issued. Apparently, the cause of the flaw was not fully
`fixed and detection mechanisms were not implemented. As a
`result, a similar fault occured later again with the ID card of
`Siim (pair 10).
`It is crucial to note that the incident was not handled as
`a security issue. The affected certificates were not revoked
`until the cardholders visited a PPA customer service point to
`receive the replacement card. Ülle was able to use her ID card
`until shortly before its expiration where it was then replaced.
`Liis informed us that the invitation from PPA did not reach
`
`1790 29th USENIX Security Symposium
`
`USENIX Association
`
`7
`
`

`

`5.1 Finding the evidence
`In 2016, Svenda et al. in their paper “The Million-Key Ques-
`tion – Investigating the Origins of RSA Public Keys” [33]
`described a method which can be used to infer from the RSA
`public key modulus some details about the algorithm used
`to generate the key. In particular, it was found that the most
`significant byte (MSB) of modulus N allows to establish the
`range from which primes p and q were selected. This range
`turned out to be different for different implementations of the
`RSA key generation algorithm. We used this and other tech-
`niques to verify whether the properties in the RSA keys from
`the ID card certificates match the properties of the key gen-
`eration algorithm implemented by the ID card platform. To
`obtain reference keys, we generated and exported thousands
`of keys from each ID card platform (when it was possible),
`simultaneously measuring the time taken by the on-card key
`generation process.
`
`5.1.1 MICARDO
`
`We found a configuration flaw in all MICARDO-powered
`ID cards that allowed us to perform card management oper-
`ations with PIN2, without knowing the manufacturer’s sym-
`metric card management keys [19]. We used this to generate
`and export over a million 1024-bit RSA key pairs generated
`by the platform.
`The MICARDO platform does not allow setting the value
`of the public exponent e. For each key the platform chooses
`a random public exponent e, either 2, 3 or 4 bytes in length,
`depending on the configuration. This peculiarity is visible in
`the certificates – for all, more than one million MICARDO-
`powered ID card certificates in our dataset, the public expo-
`nent value is random, no single value being over-represented.
`
`(a) From the keys generated by the platform
`
`(b) From the ID card certificates
`
`Figure 9: MICARDO: distribution of the MSB of N
`
`As we see in Figure 9, the distribution of the MSB of N
`from the keys generated by the MICARDO platform closely
`matches the keys from MICARDO-powered ID card certifi-
`cates. Since the distribution of the MSB of N from the keys
`generated by MICARDO platform shows a unique pattern
`not observed in keys generated by any known software li-
`brary (see Figure 12 in [33]), we can conclude that the keys
`
`in MICARDO-powered ID cards have been generated by the
`platform. We note, however, that our dataset does not have
`enough certificates issued in the period from 2002 to 2007
`to draw definite conclusions about the keys generated in this
`period.
`
`5.1.2 MULTOS
`
`We did not have access to a non-personalized MULTOS plat-
`form, therefore we could not generate reference keys. In
`our dataset we have 29 262 certificates issued for MULTOS-
`powered ID cards. Figure 10 shows the distribution of the
`MSB values of these keys. The public keys have a random
`4-byte public exponent, mimicking the non-standard behavior
`of MICARDO.
`We cannot make conclusions about the origins of these keys.
`However, we see that these keys have not been generated by
`OpenSSL (non-FIPS), since moduli are not always congruent
`to 1 modulo 3 (see Section 4.2 in [33]).
`
`Figure 10: Distribution of the MSB of N from the MULTOS-
`powered ID card certificates
`
`5.1.3
`
`jTOP SLE66 (initially issued)
`
`To export a million keys generated by jTOP SLE66 platform,
`we used blank jTOP SLE66 JavaCards. Since RSA key gener-
`ation is implemented on the level of the JavaCard platform,
`access to the manufacturer’s proprietary EstEID JavaCard
`applet was not required.
`We observed that this CC certified [34] JavaCard platform
`has a functional bug. When asked to generate a 2048-bit RSA
`key, in 38% of the cases a 2047-bit key is returned. This is
`close to the theoretical ratio of 38.6294% when p and q are
`chosen uniformly from the distribution of 1024-bit primes. In
`order to generate an RSA modulus of required length, usually
`either the rejection sampling method is used to regenerate
`primes until their product is of the required length, or the
`√
`primes are sampled making sure that k-bit prime is larger than
`2 · 2k−1 (see Section 3.2 in [33]). The distribution of the
`MSB of N from the keys generated by jTOP SLE66 platform
`is shown in Figure 11.
`
`Figure 11: Distribution of the MSB of N for keys generated
`by jTOP SLE66 platform
`
`USENIX Association
`
`29th USENIX Security Sym