Patent Description:
It is therefore required that users (collective term for citizens, consumers, employees) and Service Providers (SPs, collective term for businesses and public authorities) have trust in online mechanisms on:.

In the three sections below we further discuss these aspects.

In July <NUM> the European Union has passed the eIDAS regulation [eIDAS-<NUM>]. Amongst other things, the regulation covers interoperable electronic identification between member states. For this the regulation specifies three assurance levels for user authentication: Low, Substantial and High. These assurance levels are further specified in the eIDAS implementing regulation [eIDAS-<NUM>]. The eIDAS assurance levels stipulate requirements:.

Each the three eIDAS level has its designated assurance requirements on the Authenticator and the user binding thereof. Other standards on user authentication such as [NIST-8oo-<NUM>], actually differentiate assurance levels for the Authenticator (Authenticator Assurance Level, or AAL) and the user binding thereof (Identity Assurance Level, or IAL). The level eIDAS Low corresponds to AAL/IAL <NUM>, Substantial to AAL/IAL <NUM> and High to AAL/IAL <NUM>.

A fundamental Authenticator requirement for both eIDAS assurance levels Substantial and High is that it should be based on at least two of the three authentication factors: possession (something the user has), knowledge (something the user knows) and biometrics (something the user is). A user-id/password is only based on one (possession) factor is a typical Authenticator of Low authentication assurance level.

An essential Authenticator difference between the levels Substantial and High is stipulated in Section <NUM>. <NUM> of [eIDAS-<NUM>]: an Authenticator at level Substantial, respectively High, should be resistant against an attacker with moderate, respectively high attack potential. As indicated in the (informal) EU guidance [eIDASGuide] on the eIDAS implementing regulation [eIDAS-<NUM>] the term attack potential refers to Appendix B of the standard ISO/IEC <NUM>, the Common Criteria methodology for IT security evaluation.

In essence, two methods are deployed in practice authenticating a user for a service provider using the Authenticator of the user: direct and centralized (in-direct). In the first approach the service provider needs to directly interact with the Authenticator to authenticate the user, i.e. there is no other party involved other than the user and the service provider. This setup does not only require the service provider to implement Authenticator specific protocols but also setting up a helpdesk for users. Also, the SP needs to interact with the issuer of the Authenticator, e.g. to validate that is not revoked. The implementational complexity grows when different Authenticator types need to be supported.

In the centralized approach these issues are addressed by letting the actual Authenticator interaction be done by a third party, i.e. an Authentication Provider (AP) that also issues the Authenticator. When the user wants authenticate to the service provider he is redirected to the AP accompanied with an authentication request. The AP handles the Authenticator interaction and the user is sent back to the Service Provider with the authentication result. If problems arise with the Authenticator interaction the user contacts the AP.

Although the direct approach has certain security and privacy advantages the operational advantages for SPs make it the favorable method in current practice. The elDAS regulation does not favor the direct or the centralized approach.

in November <NUM> other European legislation was passed in which user authentication has a prominent position. This is the second Payment Services Directive [PSD2-<NUM>] that introduces the term Strong Customer Authentication (SCA) that needs to be applied by banks ('payment service providers') as part of "customer-initiated" online payments. The SCA requirements are further specified in a Commission delegated regulation [PSD2-<NUM>]. SCA is quite similar to the elDAS levels Substantial and High, e.g. it is required that SCA is based on at least two of the three authentication factors. As understandable from its origin, specific SCA requirements relate to the protection of the amount and beneficiary in the online payment. Although SCA does not need be based on electronic signatures this is commonly referred to as WYSIWYS (What You See Is What You Sign).

To achieve SCA, banks issue electronic identification means to their customers which are similar to the Authenticators discussed above. The actual interaction in an online payment closely resembles that of <FIG> where the bank plays both the role of AP and SP.

We refer to strong authentication as a collective term for two-factor authentication comparable with eIDAS Substantial and High, SCA and NIST levels AAL/IAL <NUM> or <NUM>.

Historically, strong Authenticators were implemented as separate hardware devices, such as smartcards or One-Time-Password tokens. With the rise of mobile devices such as smartphones there is a trend to base an Authenticators on a mobile application (Authenticator App). The rationale behind this trend is both efficiency and user-friendliness. This trend is also very visible in the banking sector where classical internet banking using a personal computer based internet browser is being replaced by a mobile application (banking App). The security of both an Authenticator App and a banking App is based on the security features of the underling platform. Here it is challenging to meet the security requirements on strong authentication, most notably the resistance against attackers with moderate or high attack potential as discussed earlier. This in particular includes the implementation of a knowledge factor (Personal Identification Number, or PIN) that is strongly connected to the Authenticator App. The regular solution is to implement the PIN in an online service, requiring the user to successfully present this to the service as part of authentication. One can argue that this approach does not strongly binds the PIN to the authenticator as it precludes the PIN to be under its "sole control".

The elDAS regulation also defines the legal notion of various types of electronic signatures and seals and stipulates requirements on these. An electronic seal is technically the same as an electronic signature, but a seal is associated only to a legal person/entity. For simplicity we only discuss signatures in this document but the techniques discussed also apply to seals. The eIDAS regulation specifies an electronic signature as "data in electronic form which is attached to or logically associated with other data in electronic form and which is used by the signatory to sign". The regulation also specifies advanced and qualified electronic signature which are most relevant for this document. An advanced signature:.

In practice, strong electronic signatures are based on public key cryptography, cf. Here the user generates a public-private key pair. The private key is kept secret by the user and the public key can be provided to service providers. The private key allows the user to generate a signature on a message that can be verified with the public key. The basic idea is that the private key cannot be derived from the public key. We use the term digital signature for an electronic signature bases on public key cryptography.

To allow binding with the user identity, the public key can be bound to the user identity in a so-called public key certificate. This is a message containing the user public key and the user identity that is digitally signed by a Certificate Authority (CA). The public verification key of the CA is publicized. Amongst other things, certificates contain an issuance data/time and a unique serial number.

Certificates also allow for convenient mechanisms assessing their validity, e.g. non-revoked and non-suspended, providing additional assurance to the certificate. For this two mechanisms exist, cf. [ETSI-<NUM><NUM>]. The first mechanism consists of the certificate issuer periodically, e.g. daily, publicizing a list of revoked or suspended certificates. This list, called Certificate Revocation List (CRL), is typically based on the serial numbers of the certificates only. Relying parties can download the CRL and assess the validity of a certificate. The second mechanism, more commonly used, is that certificate issuer makes the Online Certificate Service Protocol (OCSP) available for relying parties. These parties can send a certificate or only its serial number to the OCSP-service which will respond with the status of the certificate. This status is electronically signed by the OCSP-serviee/certificate issuer.

The elDAS regulation lets the user "creation data" (e.g. private key) be stored in an electronic signature creation device (SCD) that creates the electronic signatures. According to the eIDAS regulation, an SCD is configured software or hardware used to create an electronic signature.

One can conveniently turn an SCD into an Authenticator. This can support use eases of various assurance and convenience levels. Compare <FIG>. In the basic use case the service provider generates a random nonce, e.g. <NUM> or more random bytes, and requests the user to sign this with its SCD. The user signs the nonce and sends the signature back to the service provider together with the public key certificate allowing for verification. The service provider verifies the signature with the public key and, if this is successful, assesses the user identity from the certificate.

The regulation also introduces the notion of qualified electronic signatures (QES). Such signatures correspond with signatures of the highest assurance level and have the equivalent legal effect of a conventional, i.e. handwritten, signature.

An qualified signature is an advanced electronic signature that is created by a qualified electronic signature creation device, and which is based on a qualified certificate for electronic signatures. The referral to a "certificate" indicates that implementations of elDAS advanced and qualified signatures are based on public key cryptography as discussed above.

A qualified electronic signature should be generated using a qualified electronic signature creation device (QSCD). An important QSCD requirement is that the user can "with a high level of confidence, use [the QSCD] under his/her sole control". The context of (qualified) signatures closely resembles that of (What You See Is What You Sign) in SCA.

In the predecessor of the eIDAS regulation (the <NUM> directive on electronic signatures) an QSCD could formally only be implemented as a "smartcard" based device (smartcard). This is a separate integrated circuit card (ICC) on which an application is deployed to perform security critical functions such as electronic signing or performing authentication. Similar to a strong authenticator, such function are protected with access control based on at least two of the three authentication factors.

Smartcards are rather user unfriendly as the user needs to carry these around including equipment (smartcard reader) to interact with the device.

It would be convenient if a QSCD could be implemented as a mobile application, i.e. as a signing app. The eIDAS regulation has made this possible by the term "with a high level of confidence" in the QSCD requirement mentioned above which in fact is an addition to the <NUM> directive requirement. This addition allows for qualified "remote signing" through a remote qualified electronic creation device (rQSCD) at service provider. The idea is that the user authenticates to a signing service provider at eIDAS assurance level High which then forms the qualified electronic signature on behalf of the user.

That is, the eIDAS regulation allows forming an rQSCD based on Authenticators of eIDAS assurance level High. Compare <FIG>. We note that the roles of AP and SP (remote signing service) could coincide. Through the relation with (qualified) electronic signing the availability of Authenticators meeting eIDAS High requirements, most notably those based on mobile applications, becomes very important.

The General Data Protection Regulation [GDPR] is an important step for data protection in the European Union. The GDPR sets out seven key principles including that of data minimization: "personal data collection shall be adequate, relevant and limited to what is necessary in relation to the purposes for which they are processed". In several articles, e.g. the "data protection by design" article <NUM>, the GDPR suggests the usage of pseudonymization and encryption as technical enablers achieving data minimization.

One can argue that a conventional public key certificate setup, used in a direct approach does not satisfy the data minimization requirement. Indeed, in such a setup the certificate will typically contain directly identifying data of the user, such as first and last names and perhaps even a social security number. In many use cases, this personal data is not required. Moreover, this data (and in fact the certificate itself including the user public key) can serve as a unique identifier allowing service providers to conveniently link their databases. That, one can argue that using a static certificate itself contains too much information and is conflicting the data minimization requirement.

The FIDO (Fast. ID Online) [FIDO], its successor WebAuthn [WebAuthn] and the German eID-card [BENDER] address this issue. FIDO is completely based on pseudonymized authentication as the public-private keypairs generated by the FIDO Authenticator are service provider specific. As the FIDO pseudonyms are formed by the public keys they are service provider specific by construction.

The German eID-card allows users to authenticate using a persistent pseudonym as an alternative to directly identifying personal data such a social security number or a name. See [BENDER]. The German eID also provides service provider specific pseudonyms. An important privacy requirement, cryptographically met in both examples, is that service providers cannot link users through their pseudonyms.

Such privacy properties typically come with a price in security, user-friendliness or both. This is related to Authenticator revocation, i.e. the process allowing the user to (temporarily) disable her Authenticator that has gone awry, e.g. stolen or lost. The eIDAS regulation [eIDAS-<NUM>] explicitly requires that timely revocation of Authenticators must be possible. The choice for pseudonymous authentication typically implies that the Authenticator revocation becomes more challenging. Indeed, each service provider associates the Authenticator with a different pseudonym. For this the issuer of the German elD distributes service provider-specific revocation lists ('black lists') containing the pseudonyms corresponding with revoked eID-cards. As the number of lists grows linearly with the number of service providers, this makes the mechanism quite cumbersome. Such revocation itself introduces a privacy risk too. Indeed, if only one eID-card is revoked only one pseudonym will be new to all the service providers revocation lists allow linking the user.

The FIDO standard does not support revocation at all. Instead it requires the user to revoke its FIDO Authenticator at all service providers he registered it. This is not user-friendly and in practice users will typically not revoke their FIDO Authenticator at all individual service providers thus hampering security.

Providing privacy in a centralized authentication approach can also be challenging. Indeed, in a typical implementation the AP knows both the identity of the user as the service provider the user wants to logon to. There are many cases where just the information that a user was accessing a given service may constitute a breach of privacy. Such cases include a user retrieving results from a certain medical testing facility or a user getting an on-line psychiatric consult. This concern is also explicitly mentioned in the broadly used centralized authentication standard SAML [SAML]. A simple solution to remedy this is making the AP 'blind', i.e. by not giving him access to the service provider identity he is authenticating for. Although this appears privacy friendly, this would hamper security as it would make the system vulnerable to so-called Man-in-the-Browser attacks. That is, malware in the user browser manipulates the user that he is authenticating to another service provider then is actually the case. In this case a fraudster could for instance get access to sensitive health data. A 'blind' AP cannot warn the user against this. More fundamentally, a 'blind' AP seems in conflict with privacy regulations as he is not able to tell the user which service providers he has given data to.

The classical implementation of an Authenticator of elDAS assurance level High consists of a PKI smartcard application deployed on a smartcard based on a static certificate binding the user identity with public key. Compare [IAS].

As indicated in the previous sections, the usage of a static certificate hampers user privacy as it allows relying parties to link their databases using the certificate. On the other hand, the alternative of not using certificates and giving relying parties their own, unique public keys hampers timely revocation.

Also, a classical smartcard implementation is both expensive and user-unfriendly. It is expensive as a separate smartcard is required which needs to be securely sent to the user too. A classical smartcard implementation is user-unfriendly as users do not want to carry around with smartcard and smartcard readers. There is a trend that users only want to carry around their mobile devices, e.g. smartphones.

To remedy this, efforts are made to implement Authenticators as mobile application on mobile devices, Although such devices have trusted execution environments to securely store and use cryptographic keys in a mobile application, one of fundamental issues binding a possession or biometric factor to the mobile application. This is due to the fact that mobile trusted execution environments do not cater for trusted storage of separate application possession factors such as PINs or biometric factors such as fingerprint templates. This is due to the fact that, different from smartcards, mobile trusted execution environments are not equipped with their own trusted storage available for applications. See [COOIJMANS].

The previous discussion leads to the following problem statement. For both the direct and the centralized approach strong Authenticator implementations are required meeting the following requirements:.

implementations should provide authentication based on two of the three authentication factors, e.g. based on possession and knowledge.

The implementation should support on public key cryptography in order to provide for the strongest form of signatures and authentication possible.

Implementations should support for flexible implementation, i.e. not necessarily based on smartcards. It should be possible to base implementation on a mobile application.

Implementations should support pseudonymous authentication preventing different service providers linking their registrations based on authentication results.

Implementations should support for timely revocation of Authenticators in a user-friendly fashion.

The model we take for an Authenticator is based on the centralized authentication model and consists of the five parts as indicated in <FIG>. In Section <NUM> we discuss variants and extensions to this model and our techniques, including one in the direct authentication approach.

This is the physical manifestation of the Authenticator for the user. It for instance can be a personal computer or a mobile device such as a smartphone.

This forms the lowest layer of the user computing environment and is based on the platform. It supports interaction with the outside world including the user, forms the basis for the user Application Environment and the interaction of that with the Secure Cryptographic Environment (see below).

In the A-APP all of the functional part of the Authenticator is implemented and some of the security part. The A-APP resides in an Application Environment (AE) in which developers can implement their own cryptographic operations but the protection of cryptographic keys is not as secure as in the Trusted Execution Environment. The A-APP has its own local storage that is typically separated by the local storage of other applications by the Operating System.

This SCE allows for secure (random) generation and storage of cryptographic keys and for secure usage of the keys in cryptographic operations. An application in the Application Environment can instruct the Trusted Execution Environment to generate cryptographic keys and to use them. However, secret/private keys can only be used but cannot be exported from the Trusted Execution Environment. Moreover, developers are not able to implement their own cryptographic operations inside the SCE.

The AP will issue Authenticators to users and appropriately bind them to the user, e.g. in line with the elDAS requirements [eIDAS-<NUM>]. As indicated in Section <NUM>, the user and its Authenticator is redirected to the AP by an SP accompanied with an authentication request. The AP interacts with the user Authenticator to authenticate him. If this is successful, the AP sends an authentication response to the SP. The AP can recognize the user and the user A-APP, e.g. through a User-ID.

This Authenticator model corresponds with the setup of modern mobile devices, e.g. Android (Google) based mobile devices and Apple (e.g. iOS, macOS) based devices and. In Android context the SCE is typically known as "hardware backed Android keystore" and in Apple context is known as "Secure Enclave". We note that the SCE could also be formed by a separate hardware device. This could for instance be a SIM card with a specific card application on it or a cryptographic device connected to the platform in a wired fashion, e.g. through the MicroSD interface, or in a wireless fashion, e.g. through Bluetooth.

We let Fr denote the Galois field consisting of the integers modulo a prime number r. We let o and <NUM> respectively denote the zero and unit element of Fr. We also let <MAT> denote the multiplicative subgroup, i.e. the non-zero elements in Fr.

See [STINSON]. We sometimes implicitly use that Fr, respectively <MAT>, corresponds to the integers in the interval [<NUM>, r - <NUM>], respectively [<NUM>, r - <NUM>]. We let |r|b denote the length of r in bits and |r|B its length in bytes.

Central in our constructions is an additive group ((G), +) of order q, generated by a generator element G. We use additive notation as this is customary in the context of elliptic curve groups one deploys in practice. For simplicity of presentation we assume that q is prime but the constructions discussed also work when q is not a prime number. For any natural number scalar n and element H ∈ 〈G〉 we define the (point) multiplication n · H as adding H n-times, e.g. <NUM> · H = H + H. The discrete logarithm of J ∈ 〈G〉 with respect to H is the unique x ∈ Fq such that J = xH. We write logH(J). We often use compact notation omitting the "·" symbol. As nH = mH if and only if n = m mod q we can represent scalars as elements of Fq, i.e. the Galois field consisting of the integers modulo the prime number q. This allows for compact notation such as x · G, -x · G for x ∈ Fq and y-<NUM> · G for <MAT>. A randomly, or cryptographically secure pseudo randomly, chosen element from a set is denoted by εR.

We assume that the group (〈G〉, +) satisfies the usual cryptographic security properties, i.e., that the discrete logarithm problem, the Diffie-Hellman problem and the Decision Diffie-Hellman are intractable. See [HANKERSON].

Although our constructions work for any group (〈G〉, +), one can think in our constructions of the group of points over a field Fp on a curve with simplified Weierstrass equation <MAT> for some suitable a, b ∈ Fp. That is, each non-zero group element takes the form (x,y) where <NUM> ≤ x, y < p satisfying Equation (<NUM>) modulo p. Compare [HANKERSON]. We denote the zero element (point at infinity) as O. For practical implementations one can use, for instance, a curve from [BRAINPOOL], [SEC-<NUM>] or [DSA], i.e. the NIST curves.

A Personal Identification Number (PIN) is typically a numeric string of length <NUM>, <NUM>, <NUM>. For generality and simplicity of presentation we choose a more generic PIN representation. A PIN is a byte array of length L, i.e. of the form {PL-<NUM>,PL-<NUM>,. ,P<NUM>} with all <NUM> < Pi < <NUM>, i.e. representing a non-zero byte value. Typically the byte values correspond to printable ASCII-values in which case the PIN can also be represented as a string "PL-<NUM>, PM-<NUM>,. Every PIN has an integer PIN-value given by <MAT> and each PIN-value corresponds to one unique PIN.

For example, the ASCII value of the digits <NUM>, <NUM>, <NUM>, <NUM>, <NUM> are 0x30, 0x31, 0x32, 0x33, 0x34 in hexadecimal representation. Consequently the PIN <NUM> is a PIN of length <NUM> and is represented by the array {<NUM>x<NUM>, <NUM>x<NUM>, <NUM>x<NUM>, <NUM>x<NUM>, <NUM>x<NUM>} and has a PIN-value equal to <NUM>.

For simplicity of presentation our method descriptions only support one fixed PIN length L. However these methods can be easily extended to simultaneously support various PIN lengths, e.g. all PIN lengths smaller than a certain maximum length M.

Part of our novel setup for strong authenticators is a method to strongly bind the user PIN to a digital signature. This method works for several standard digital signature algorithms including the most commonly used DSA. We specify this method for ECDSA, the Elliptic Curve variant of DSA, from which the generic method for DSA easily follows. In Section <NUM> we discuss other standard digital signature algorithms for this method works.

We first describe the working of ECDSA. The context of this is the group ((G), +) introduced earlier. Here the user has a private key <MAT> and a public key U = uG. Algorithm <NUM> and <NUM> below specify ECDSA signing and verification following [HANKERSON]. In this construction a secure hash function H(. ) appears with output length equal to |q|B bytes. Such a hash function can typically be constructed by taking a hash function with a larger output size and truncating it. See [NIST-<NUM>-<NUM>].

Input: message M, private key u. Output: Signature Sig = (r, s).

We note that in practical implementations the calculation of the hash value (Step <NUM>) is not performed by the SCE. Instead the hash value of M is pre-computed as is the integer e in the AE which is then sent to the device. The SCE then performs Steps <NUM>-<NUM>. The rationale for this is that SCEs typically have limited computational and communicational capabilities making the hash calculation time expensive. Most cryptographic libraries and Application Programming Interfaces (APIs) for ECDSA allow the specification of a "DIGEST_NONE" mode facilitating this. Also the Secure Cryptographic Devices in Android based devices and Apple based (e.g. iOS, macOS) devices cater for this.

Input: public key U, message M, signature (r,s). Output: Acceptance or rejection of the signature.

For reasons indicated later, Algorithm <NUM> is not the regular description of ECDSA signature verification. In de regular description Steps <NUM> and <NUM> are:.

One can easily verify that our description is equivalent to the regular one. We also observe that instead as an alternative to (r, s) one can also represent the signature as (X, s) where X ∈ 〈G〉 is formed as in step <NUM> of Algorithm <NUM>. Indeed, one can compute (a candidate) r from the x-coordinate of X as indicated in Step <NUM>. One can easily verify that this will result in the same (valid) signature one started with. Note that X takes the form kG for some k ∈ Fq by Step <NUM> of Algorithm <NUM>. The point X holds more information than the original r which shall be beneficial in Section <NUM>.

We now specify Split-ECDSA. The context of this is the similar to that of regular ECDSA. The difference is that in the Split-ECDSA the user possesses another secret <MAT>, called the split secret, next to its private key d. In Split-ECDSA the user public key takes the form <MAT>.

Split-ECDSA signature generation is different from regular ECDSA signature verification but Split-ECDSA verification is not. That is, Split-ECDSA verification with respect to U' corresponds to regular ECDSA verification with respect to U'. That is, relying party will not see the difference between a Split-ECDSA signature and a regular ECDSA signature. In Algorithm <NUM> we have specified Split-ECDSA signature generation.

Input: message M, private key u, split secret key σ. Output: Signature (r,s).

That the Split-ECDSA signature (r, s) of M is indeed an ECDSA signature with respect to U' is easily verified. Indeed, s takes the form σ · k-<NUM>(e' + u · r) mod q which is equal to k-<NUM>(e + σ · u · r) mod q as σ · e' = e. It follows that (r,s) is an ECDSA signature of M with respect to public key σ · u · G which is equal to U'.

Another, somewhat more elaborate, verification of this property consists of following Algorithm <NUM> for the signature (r, s) returned by Algorithm <NUM> with public U'. To this end,.

To this end, (r,s) is an ECDSA signature with respect to e' and private key u with public key U = u · G. By inspecting Algorithm <NUM> it follows that r is equal to the x-coordinate of <MAT>.

The first equality follows as e' = σ-<NUM> · e mod q the construction in Line <NUM> of Algorithm <NUM>. The second equality follows as <MAT> which directly follows from the construction in Line <NUM> of Algorithm <NUM>. The last equality follows from a direct verification and the definition of public key U. It follows that (r,s) is a ECDSA signature on the hash of the message based on private key u · σ mod q.

What makes Split-ECDSA signature generation interesting is it enables separation of the environments where Steps <NUM>-<NUM> are performed and where Steps <NUM>-<NUM> and <NUM> are performed. Steps <NUM>-<NUM> can be performed in the SCE and Steps <NUM>-<NUM> and <NUM> in the AE. Note that this requires that the cryptographic device supports generation of ECDSA signatures based on pre-computed hash values which is often the case. See the discussion following Algorithm <NUM>.

In our application of Split-ECDSA the split secret σ will be based on the user PIN. To further mitigate brute-force we require a PIN-Binder. This is a keyed one-way function <MAT> where K is a secret/private key and where L denotes the PIN length. A PIN-Binder function has the following properties:.

The idea is that the key K is maintained in an SCE, i.e. in a non-exportable fashion and (a fundamental part of) the PBK(. ) calculation takes place inside this environment. In this way, the PBK(. ) calculation is strongly bound to the secure environment, i.e. without the secure environment the function PBK(. ) cannot be computed. The PIN-Binder is called from the Application Environment. In the algorithms below we have indicated by {SCE} which part of the PIN-Binder algorithm takes place inside the SCE.

We note that the calculation inside the SCE can be iterated, using the SCE output as part of a new calculation inside the SCE. This arranges that the time it takes to compute the PIN-Binder is configurable, e.g. can be set to one second. This allows for further resistance against brute-force attacks.

The PIN-Binder generation methods used will all be based on the output of a pseudorandom function considered as an integer and taken modulo q. To avoid that the output is zero and to mitigate statistical incorrectness we follow [BSI-<NUM>]. Here one generates a byte array H of |q|B + <NUM> pseudorandom bytes, interprets that as an integer h and returns <NUM> + (h mod (q - <NUM>)) as the output. This construction always leads an non-zero integer modulo q and the generation of the <NUM> more bytes mitigates the effect of statistical incorrectness.

In the discussion below, H(. ) is a secure hash function with an output length equal to |q|B + <NUM> bytes. Such a hash function can typically be constructed by taking a hash function with a larger output size and truncating it. See [NIST-<NUM>-<NUM>].

A straightf or ward way to construct a PIN-Binder is using an SCE that supports HMAC [NIST-<NUM>-<NUM>-<NUM>] or CMAC [NIST-<NUM>-38B] as we can based the PIN-Binder directly on [NIST-<NUM>-<NUM>].

Input: PIN array P, HMAC key K in SCE. Output: PIN-Binder key PBK(P) in <MAT>.

Input: PIN array P, CMAC key K in SCE. Output: PIN-Binder key PBK(P) in <MAT>.

As the CMAC operation is based on a block cipher it can be inverted in principle, conflicting with the first property of a PIN-Binder. The hashing in Step <NUM> precludes this inversion.

The current "hardware backed Android keystore" supports the HMAC algorithm so Algorithm <NUM> can be used in that context. At the time of writing it does not support CMAC so Algorithm <NUM> cannot be used. The current "hardware backed Android keystore" does support AES in various encryption modes including the basic Electronic Code Book (ECB) mode, i.e. LAES). In the following algorithm we indicate how a PIN-Binder can be constructed based on AES-ECB. This algorithm is limited to PIN of length <NUM> which in practice should not be a limitation. Variants using other encryptions modes, such as CBC, can also easily be constructed also addressing the PIN length limitation. Compare [NIST-MODES].

Input: PIN array P of length not exceeding <NUM>, AES key K in SCE. Output: PIN-Binder key PBK(P) in <MAT>.

The integer L in Step <NUM> corresponds to the minimal number of AES blocks required to achieve a total of [q]B + <NUM> bytes or more. In the above example we have shown how a AES encryption function can used to form a PIN-Binder. One can also use an AES decryption function for this but this requires some care. In most AES encryption modes arbitrary ciphertext will not successfully decrypt. Most encryption modes add extra information ('padding') to the plaintext prior to encryption. Padding is done to ensure that the plaintext size is an integer multiple of the AES block size (<NUM> bytes) but also as a rudimentary integrity check. During decryption it is verified that correct padding was performed and if this is not the case an error is returned. This means that one cannot AES decrypt arbitrary byte arrays. This can be remedied by ensuring that the PIN based byte array is an integer multiple of the AES block size (<NUM> bytes) and by using a non-padded AES encryption mode.

Another example of how a PIN-Binder can be based on a SCE is using its asymmetric decryption capabilities. The simplest method for this is using the Diffie-Hellman capabilities of the SCE. Here one simply generates a Diffie-Hellman public-private keypair, e.g. X = xG inside the SCE allowing it to compute (a key from) the shared Diffie-Hellman key xyG by offering the SCE the element Y = yG ∈ 〈G〉. See [STINSON]. Now by embedding the user PIN into the group 〈G〉, e.g. as point P and offering this to the SCE as input to the Diffie-Hellman one obtains (a key from) xY which can be used to derive a PIN-Binder key from. There are many methods known for embedding a string or a byte array into an elliptic curve group of points. Note that in this application one does not need to know the discrete logarithm of Y with respect to G as is normally required in the Diffie-Hellman key exchange protocol. One can also base a PIN-Binder on the textbook RSA decryption capabilities of the SCE. See [STINSON]. In the RSA cryptosystem the public key consists of the product n of two large prime number p, q and public exponent e usally taken as <NUM><NUM> + <NUM> = <NUM> and the private key consists of a number d = e-<NUM> mod (p - <NUM>)(q - <NUM>). Textbook RSA encryption, respectively decryption, consists of the functions x → xe mod n, respectively x → xd mod n. Textbook RSA is not normally used in practice as it is not resistant against so-called chosen ciphertext attacks. To remedy against this kind of attacks redundancy ("padding") needs to be added to plaintext prior to encryption that is checked against as part of decryption. Most cryptographic libraries/API for RSA allow the configuration of a "PADDING_NONE" mode facilitating textbook RSA. In this way flexible support for various kinds of other padding is provided to developers. We can then construct a PIN-Binder as sketched below. This starts with the generation of an RSA key in the SCE of appropriate size, e.g. a modulus n with bit length |n| = <NUM> bits, i.e. <NUM> byte.

Input: PIN array P, RSA private key d in SCE. Output: PIN-Binder key PBK(P) in F^.

The byte of value <NUM> is a non-printable byte and can thus not occur in P. This means that the construction in Step <NUM> leads to different results for different PINs. The RSA decryption operation in Step <NUM> can be inverted with the public key in principle, conflicting with the first property of a PIN-Binder. The hashing in Step <NUM> precludes this inversion.

As Android based devices typically provide for AES, HMAC and textbook RSA in their SCE they allow for various PIN-binding mechanisms. However, Apple (e.g. iOS, macOS) based devices, do not provide for either of those algorithms. Apart from ECDSA signatures, Apple based devices typically only provide authenticated encryption an decryption, most notably ECIES see [HANKERSON]. This means that the SCE will only return plaintext if the ciphertext is properly formed. In other words, feeding an ECIES decryption function with arbitrary ciphertext will typically result in errors and not in useful responses. This resembles the padding situation discussed above on using an AES decryption operation to base a PIN-Binder on. However, this could be easily resolved there by using non-padded decryption. One can also base a PIN-Binder on ECIES decryption but this takes somewhat more effort.

We first explain the basic working of ECIES encryption/decryption following [HANKERSON]. For simplicity our description we limit ourselves again to on an elliptic curve with co-factor <NUM>. This is the case in commonly used elliptic curves such as those in [BRIAINPOOL], [SEC-<NUM>] and [DSS]. We note that Apple based devices only support the curves from [DSS]. Moreover we do not take the sender's ephemeral key as part of the key derivation which is also the case on Apple based devices. Our constructions are also possible when these limitations apply but the formula become somewhat more complex.

Similar to the ECDSA setup, a user has a private key <MAT> and a public key D = dG. Part of an ECIES implementation is an encryption algorithm Enc(K,. ) with corresponding decryption algorithm Dec(K,. ) and a message authentication code algorithm MAC (K,. In all algorithms K represents a key appropriate for the algorithm.

The message authentication code algorithm can be based on a block cipher, e.g. [NIST-<NUM>-38B], or on a hash function, e.g. [NIST-<NUM>-<NUM>-<NUM>]. As we discuss below, modern ECIES implementations including those of Apple combine the encryption and message authentication algorithm. Part of an ECIES implementation is also a Key Derivation Function KDF(. ), That takes as input a two elements of the group (G) and returns two secret keys (kENC, kMAC) that fit the encryption/decryption and a message authentication code algorithm in the ECIES implementation. In Algorithms <NUM>, <NUM> we have sketched the working of ECIES encryption and decryption respectively.

Input: message M, public key D. Output: Encrypted message (R, C, t).

The elliptic curve point R in Line <NUM> is known as the ephemeral key and the point Z is known as the Diffie-Hellman shared key. Compare [STINSON].

Input: encrypted message (R, C, t), private key d. Output: Plaintexts message m or rejection of the encrypted message.

The elliptic curve point Z in Step <NUM> of Algorithm <NUM>, coincides with the point Z from Step <NUM> in Algorithm <NUM>. This effectively is an execution of the Diffie-Hellman key exchange protocol, cf.

It follows that one will only get useful data in Algorithm <NUM> if the input C passes the Step <NUM> of Algorithm <NUM>. To arrange for this in our PIN-Binder construction, one generates a random ephemeral key R in the Application Environment, computes kMAC and stores R and kMAC in local storage. These two values now enable to form for each byte array C a valid triplet (R, C, t) that can be offered for ECIES decryption. Indeed, with kMAC one is able to calculate the value t allowing to pass Step <NUM> of Algorithm <NUM>. Step <NUM> of Algorithm <NUM> will only result in non-erroneous output if the ECIES symmetric encryption/decryption does not use padding which is usually the case. Moreover, this will only lead to secure PIN-binding if the key kENC can not be derived from kMAC which is always the case.

We further elaborate on this method in the context of Apple (e.g. iOS, macOS) based devices. Here ECIES implicitly uses a message authentication code algorithm as it is based on AES-GCM, i.e. an authenticated encryption mode. Effectively only an AES-GCM encryption K key and an initialisation vector is formed in Step <NUM> of Algorithm <NUM>. As part of the AES-GCM operation a core encryption key kENC and a message authentication key kMAC are formed from K. More specifically, the encryption key kENC is used in AES-GCTR for encryption. Next to an AES-key, this mode takes an initialisation vector as input. During its operation it AES encrypts <NUM>-byte blocks (the AES block size) holding a incrementing sequence number starting with an initialisation vector. These encrypted blocks are then XOR-ed with the plaintext. Decryption is similar to encryption. GCTR does not use padding implying that it accepts any ciphertext. The key kMAC is used in GMAC to generate a message authentication code on the message encrypted with GCTR. We actually have kMAC = AES(K, <NUM><NUM>) where <NUM><NUM> is the all zero AES block. So similar as discussed above the key kENC cannot be derived from the key kMAC (although the reverse does not hold).

We can now sketch a PIN-binding algorithm in the ECIES context based on AES-GCM. This starts with the generation of an ECIES private key <MAT> and corresponding public key D = dG in the SCE. The public key D is sent to the AE. Next one generates a k ∈R [<NUM>, q - <NUM>] in the AE, forms the ephemeral key R = kG and the shared key k. D, the AES-GCM key K and then the GMAC key kMAC = AES(K, <NUM><NUM>). All data except R, kMAC are deleted.

Input: PIN array P, ephemeral key R and message authentication key kMAC in AE, ECIES private key d in SCE. Output: PIN-Binder key PBK(P) in <MAT>.

We remark that we can additionally encrypt P, kMAC using the SCE in another ECIES application, allowing an additional security layer.

We introduce some terms allowing convenient description of the methods on which the Authenticator application A-APP is based.

The AP will manage one or more Certificate Authorities (CAs) and related certificate management systems administrating related information, e.g. on certificate status. We assume there mechanisms are in place providing the user/A-APP with the related CA verification certificates in a trusted fashion. That is, the user/A-APP can validate that a certificate is indeed issued by a CA managed by the AP. This could for instance be arranged by letting the CA verification keys be signed by root public key that is trusted by the user platform and by placing copies of the CA public key certificates in the A-APP.

Included in the A-APP is a public key certificate A issued by an AP managed CA that allows the A-APP encrypting an arbitrary number of data elements {D_i} for the AP protecting confidentiality and preferably also authenticity. This will be denoted as Enc<NUM> ({Di}). We assume that this encryption arranges for injective representation of its input allowing unambiguous decryption. It might be convenient to base EncA (. ) on ECIES see [HANKERSON]. This encryption can (and typically will) take place in Authenticator Application environment, i.e. in software, allowing for flexible implementation. We let A denote the range of EncA (.

We next introduce three types of public-private key pairs:.

A mechanism to publicly make verifiable that two Randomized Authenticator public keys P<NUM>, P<NUM> belong to the same SCE (and thus user) is important in our discussions. To this end, suppose we have to two Randomized Authenticator public keys P<NUM>, P<NUM> belonging to two potentially different SCEs S<NUM>, S<NUM> and users. Suppose that each SCE has proven possession of the corresponding private key, e.g. by having signed a random message. Also assume that one of the users or the AP can prove it knows an <MAT> such that that <MAT>.

In that case we conclude that the two SCEs (and thus the users) must coincide. For this we offer an informal reasoning, arguing by contradiction. This reasoning can be made more formal. Suppose we could construct a situation where the above could occur with different SCEs. Then we could use this construction with one real SCE and a simulated SCE that would allow for extraction of its private keys. Using Formula (<NUM>) we would then be able to extract the private key of the real SCE as well, what we assumed not to be possible.

Using the techniques from [SCHNORR] anyone knowing an <MAT> satisfying Formula (<NUM>) can easily transform this into a non-interactive proof of knowledge (PoC) using the techniques from [FIAT] allowing allows public verification of Formula (<NUM>) without losing secret information on x.

The issuance process starts by the user installing an Authenticator Application (A-APP). We assume that mechanisms are in place whereby the user can assess the trustworthiness of A-APP. For instance, A-APP could be digitally signed and/or the user could download the A-APP from of trusted APP stores of Google or Apple. We also assume that the A-APP is able to set up a secure session with the AP, e.g. by using a TLS session based on a TLS server certificate issued to the AP. The required TLS certificate and the PKI certificate hierarchy proving its trustworthiness could be provided by the Operation System or could be stored in the local storage of the A-APP.

Next the user instructs the A-APP to commence the Authenticator issuance process. The A-APP then generates a fresh SCE key pair and a fresh PIN-Binder PBK(. ) for some K securely generated and stored in the SCE. The A-APP asks the user to choose a PIN. The A-APP uses the PIN to generate a PIN-Binder key KP. Next the A-APP generates a Raw key pair related to the SCE pair and the PIN-Binder Key KP. The A-APP next generates a fresh Randomized Authenticator public key (UR,E, r, s) and registers that at the AP. Here the A-APP proves possession of the corresponding private key uR using Split- ECDSA (Algorithm <NUM>) with private key u and split secret R · KP where R is the randomization factor used. The generation of the signature (r, s) as part of the Randomized public key can suffice to prove such possession but this can be done explicitly too.

The AP validates Randomized Authenticator public key by verifying the signature using UR and by verifying that E is properly formed.

Next user identity proofing takes place, leading to some verified user information IU. This information could for instance be a name, a social security number, a pseudonym or encrypted information under EncA(.

The AP issues a certificate Cert on UR which also includes the user information lU. The AP registers both the certificate as (UR, E, r, s) in its certificate management system. The certificate Cert is also provide to the A-APP and stored inside its local storage. The A-APP deletes all sensitive/secret information in its memory/local storage, e.g. the PIN, randomization factor R and PIN-Binder key KP.

As part of the registration/certification issuing process the AP provides the user A-APP with a User-ID allowing opening a user account and registering information on the user and/or the A-APP. At the start of communication between the user A-APP and AP this User-ID is sent allowing the AP to recognize the user/A-APP and to lookup information on the user and/or the A-APP. Part of the register information is PIN-Counter holding the number of false PINs used by the user. Initially the PIN-Counter is set to zero.

The AP arranges that the user is able to revoke or suspend its certificate Cert and (consequently) its Authenticator. This for instance could be based on providing the user with a Revocation Passphrase.

The user together with the issued A-APP can now sign a message M for the AP as follows. The A-APP generates a new randomization factor R' and Randomized Authenticator public key (UR', E', r', s') and signs message M using Split-ECDSA (Algorithm <NUM>) with private key u and split secret R' - KP. The certificate Cert, the new Randomized Authenticator public key and the signature are sent to the AP. The A-APP deletes all sensitive/secret information in its memory/local storage, e.g. the PIN, randomization factor R' and PIN-Binder key KP.

The AP verifies that the certificate Cert is valid, i.e. properly signed and issued and is not revoked or suspended. The AP verifies the signature on message M using UR' using standard ECDSA signature verification, cf. Algorithm <NUM>. Next the AP verifies that the new Randomized Authenticator public key (UR' , E', r', s') is also correctly formed, i.e. that the signature (r', s') is correct and that E' is correctly formed. Next the AP looks up the Randomized Authenticator public key (UR, E, r, s) in its certificate management, system on which the certificate is based. The AP also looks ups the user PIN-Counter belonging to the A-APP. If this exceeds a certain threshold, e.g. <NUM>, the APP rejects the signature.

The AP verifies that both the new as the registered Randomized public key correspond to the same Raw Authenticator public key by decrypting R (respectively R') from E (respectively E') and by verifying that <MAT> or alternatively and equivalently <MAT>.

If this Equation (<NUM>) holds, the AP concludes that the user has used the correct PIN and the PIN-Counter is set to zero. If this is not the case, the PIN-Counter is incremented with one and stored in the user account belonging to the A-APP.

We use the Randomized Authenticator public keys for each digital signature instead of the (encrypted) Raw Authenticator public key itself to securely allow dispute handling. See Section <NUM>. A Raw Authenticator public key together with access to the A-APP environment, would allow brute forcing the PIN. So a Raw Authenticator public key can be considered security sensitive and it is not appropriate to provide to third parties. A Randomized Authenticator public key can be provided to third parties, as long as the used randomization factor is kept secret,.

The user can authenticate to the AP by digitally signing a fresh random nonce generated and sent by the AP to the user and it's A-APP as indicated in Section <NUM>, When the AP has assessed that this nonce is properly signed as indicated in Section <NUM>, the AP can consider the user authenticated under the information IU retrieved from the certificate Cert. The use and management of the PIN -Counter is similar as indicated in Section <NUM>.

The handling of the Authenticator PIN takes special care. This is related to the required functionality that the user should be able to change her PIN without reperforming the issuing/ identity proofing process.

If the user want to change its Authenticator PIN he proceeds as follows in interaction with the A-APP and AP. The A-APP generates a new PIN-Binder and a new PIN-Binder key KP based on the new PIN P. Next the A-APP generates a corresponding new Raw Authenticator public key of type Up = KP - US. This is based on the new PIN-Binder key KP but still based on the existing SCE key pair (US, us). Next, the A-APP generates a Randomized Authenticator public key UR = R · KP - US related to the new Raw Authenticator public key, forms (UR, E, r, s) and registers at the AP by signing that using the previously registered Randomized Authenticator public key including a message Consent consenting in the PIN change.

That is, the A-APP generates a Randomized Authenticator public key R' · KP · US related to the current registered Raw Authenticator public key and signs the new Randomized Authenticator public key and Consent with the private key corresponding to R' · KP · US. Also, the A-APP generates a proof that both Randomized Authenticator public key belong to the same SCE as indicated above. For this the A-APP uses the techniques from [SCHNORR] to form a proof of knowledge PoC for the AP that the A-APP knows a
<MAT>
such that
<MAT>
and sends this to the AP. The A-APP can do this as,
<MAT>
satisfies Formula (<NUM>) and is known by A-APP. The AP stores the PoC in its certificate management system. The A-APP deletes all sensitive/secret information in its memory/local storage, e.g. the PINs, randomization factors, PIN-Binder key KP and the PoC.

Suppose a signature on a message M related to a Randomized Authenticator public key ( <MAT>,E',r',s') is disputed, e.g. in court, the AP can proceed as follows to resolve this. First assume that the signature was based on the first PIN used by the user. Let (UR, E, r, s) be the Randomized Authenticator public key that was registered. It follows from Formula (<NUM>) that, <MAT>.

As the AP can decrypt R, R' from E, E' respectively it knows R. Consequently the AP can use the techniques from [SCHNORR] to generate a zero-knowledge proof of knowledge PoC showing that the AP knows a secret x such that <MAT> where UR is part the registered Randomized Authenticator public key (UR, E, r,s).

By providing the certificate Cert and the PoC to the court can prove that UR and UR' belong to the same user. If the message was signed with a changed PIN, the AP can proceed as above, proving that the message must be signed by the private owner of the registered Randomized Authenticator public key corresponding to the PIN. In addition, the AP can use the transcripts formed during PIN change (see Section <NUM>) to prove that the registered Randomized Authenticator public-private key pair was in possession of the same user as the previous one. This process then ends with the Randomized Authenticator public key that is part of the issued certificate Cert. The AP finally proves that its certificate issuing processes are sufficient to prove that the certificate Cert was indeed issued to the user. This proof can for instance be based on following [ETSI-<NUM><NUM>] and handing a proof of conformity on this from an independent auditor.

In the basic Split-ECDSA Algorithm (Algorithm <NUM>) we used that most cryptographic libraries and Application Programming Interfaces (APIs) for ECDSA allow taking as input the hash of the message thereby allowing pre-computing of that hash outside the device (SCE) actually generating the ECDSA signature. However, some libraries/APIs do not allow for this, most notably the library used in FIDO, cf. [FIDO], [WebAuthn], and the W3C Web Cryptography API [WebCrypto]. The first library/API was already discussed in Section <NUM>. The latter specifies the native support of various cryptographic algorithms from within an internet browser through JavaScript. W3C Web Cryptography API supports most standard algorithms including ECDSA, RSA, HMAC and AES. W<NUM>C Web Cryptography API is implemented in all major web browsers.

When a cryptographic library/API does not support ECDSA signatures based on pre-computed hash we cannot execute (only) Steps <NUM>-<NUM> of Algorithm <NUM> inside the Secure Cryptographic Environment (SCE) as this only accepts the message M itself. This thus excludes using of basic Split-ECDSA in this context, i.e. with only a Raw Authenticator public key as described in Section <NUM>. However, the support of a Randomized Authenticator public key is still possible. For this one proceeds as indicated in Algorithm <NUM> below.

Input: message M, private key u, split secret key σ. Output: Randomization factor R and signature (r,s) for private key u · σ · R.

A straightforward computation shows that the number s in Step <NUM> of Algorithm <NUM> is equal to <MAT>.

That is, (r<NUM>,s) is an ECDSA signature of message M corresponding to the private key u · δ. By construction of the randomization factor R this private key is equal to u · σ · R.

In the context of Section <NUM>, the split secret key σ is equal to a PIN-Binder key KP is based on a PIN-Binder PB and a PIN P. That is, the randomized public key corresponding to Algorithm <NUM> is equal to UR = u · σ · R · G = R · UP=R · KP · US where US is the SCE public key and UP is the raw authenticator public. As also indicated in Section <NUM>, the randomization factor R needs to be sent to the verifying party in a protected form.

We already remarked that the W<NUM>C Web Cryptography API next to ECDSA also supports ECDSA, RSA, HMAC and AES implying that the PIN binder constructions from Section <NUM> also can be used in the context of W<NUM>C Web Cryptography API. We also note that the W<NUM>C Web Cryptography also supports keys that are not extractable from the key storage.

This allows for a two factor authenticator that is bound to the W<NUM>C Web Cryptography API key storage through both the possession as the knowledge factor. The strength of this binding depends of the (hardware) protection given by the underlying browser implementation. If this is based on proper hardware then this binding is strong. With respect to such hardware one can think of a "hardware backed keystore" in Android context and of the "Secure Enclave" in Apple context, cf. Section <NUM>. We note that [FIDO] and its successor [WebAuthn] also allow for confidentiality algorithms implying that the same situation occurs in that context. If a (hardware based) FIDO token only supports ECDSA then one could base the possession factor on that and the knowledge factor on the W<NUM>C Web Cryptography API. This still would be considered strong.

We also note that in Windows context one can also make use of the Trusted Platform Module (TPM) that is typically present on high-end personal computers and laptops and that also supports most standard algorithms including ECDSA. Compare [ISO-<NUM>].

Some SCEs, e.g. the hardware backed Android KeyStore, support attestation allowing the SCE to convey to outside parties that a generated (ECDSA) is actually generated in a (trusted) SCE in a non-exportable fashion. This typically works by letting the generated key be wrapped inside a certificate generated by an existing private key inside the SCE on which the SCE provider has issued a certificate. By allowing the generated to include a challenge sent by an external party, freshness of the key can also be guaranteed to the external party. Attestation could be supplemented to the Authenticator issuance process in Section <NUM> on the SCE public key which would then be sent (wrapped into a certificate) to the AP. Compare https://developer. com/training/articles/security-key-attestation.

The construction of Split-ECDSA and subsequent usage in a Strong Authenticator can also be based on other digital signature algorithms that allow feeding the signature generation algorithm with a pre-computed hash value. This for instance is the case for DSA (non elliptic curve variant ECDSA), EC-GDSA (Elliptic Curve German Digital Signature Algorithm) and EC-RDSA (Elliptic Curve Russian Digital Signature Algorithm) from [ISO-<NUM>-<NUM>].

Although this obvious for anybody with basic mathematical knowledge, we write this out for completeness sake.

The DSA case is almost identical to the ECDSA case previously specified. The difference is that DSA is not set in an elliptic curve group but in the multiplicative subgroup of order q modulo a prime number p. The signature is (r,s) almost identically formed as in the ECDSA case. Here r = (gk mod p) mod q for a random integer k and s = k-<NUM>(e + u · r) mod q similar as in the case of EC-DSA. It directly follows that in this context one can form Split-DSA using the same formulae as in Split-ECDSA. specified in Algorithm <NUM>.

In the EC-GDSA case the signature takes the same form (r,s) as in ECDSA, the integer r is formed in a similar way as in ECDSA. However, using the ECDSA notation, we have s = u(r · k - e) mod q in the situation of EC-GDSA. It easily forms that Split-EC-GDSA can be formed from Algorithm <NUM> by letting e' = e and s = σ · s<NUM> mod q. In this case we once again obtain an EC-GDSA signature (r, s) relative to the private key σ · u mod q as in the ECDSA situation, which can be easily verified.

In the EC-RDSA case the signature takes the same form (r, s) as in ECDSA, the integer r is formed in a similar way as in ECDSA. However, using the ECDSA notation, we have s = (r · u + e · k) mod q in the situation of EC-RDSA. It easily forms that Split-EC-RDSA can be formed the same as in Algorithm <NUM> i.e. by letting e' = e · σ-<NUM> and s = σ · s<NUM> mod q. In this case we once again obtain an EC-RDSA signature (r, s) relative to the private key σ · u mod q as in the ECDSA situation, which can be easily verified.

Instead of using a key based from a user PIN one could, if the platform supports it, also store a key protected with a biometric characteristic of the user, e.g. a fingerprint. This key would then play the role of KP in the construction in Section <NUM> and would require that the user biometrically authenticates to the platform for digital signing.

We could encrypt all information sent by the A-APP to the AP using EncA (. ) including the certificate Cert. By letting all decryption and verifications be performed inside a separated, trusted environment within the AP, e.g. a Hardware Security Module (HSM), we could then provide additional privacy protection. Moreover, the certificate Cert could contain encrypted information only accessible within the HSM. This would allow the AP providing information to service providers as part of authentication in an encrypted fashion only accessible for the Service Provider and even not for the AP itself.

Instead of providing a digital signature and an authentication to the AP as described in Section <NUM> one can also provide these direct to an external party, e.g. a Service Provider. The result, i.e. a certificate Cert, a Randomized Authenticator public key and a signature could then be sent to the AP comparable to the setup of OCSP, cf.

On the centralized method in Section <NUM> can easily base various variants in a direct authentication approach, i.e. where the Authenticator is used in direct interaction with a Service provider. The Authenticator is issued a certificate from a certificate issuer similar to as discussed in Section <NUM> but with some minor changes. Compare <FIG>.

As a first, very simple variant, one simply does not deploy Randomized Authenticator public/private keys, or in alternative words always chooses the randomization factor to be one, i.e. the unit element of Fq. That is, the certificate issuer issues a certificate Cert directly on the Raw Authenticator Key.

To allow for PIN change without certificate change required we replace the PIN-Binder Key KP with a fixed (but randomly chosen) <MAT> and store the element <MAT> inside A-APP storage. During signing/authentication the user provides her PIN from which the PIN-Binder key KP is formed. Together with S the A-APP then computes the static PIN-Binder key K as KP · S which can then be used to digitally sign messages for the Service provider, ef. Section <NUM>, or authenticate towards the Service Provider, cf. Section <NUM>, If the user want to change the PIN she generates a new PIN-Binder, a new PIN-Binder Key Kp, and forms a new element S' = K · Kp'.

As part of signing of and authentication the A-APP sends along the certificate Cert to the Service Provider that binds the Raw. Authenticator Key to the user. The Service Provider could additionally query the issuer on the status of the certificate, i.e. whether it is revoked or suspended. This would then be similar to the setup of OCSP, cf.

A privacy disadvantage of this approach is that is provides the certificate Cert to all Service Providers, allowing them linking the user. A security disadvantage of this approach compared to the approach of Section <NUM> is that the certificate Cert needs to be stored inside local storage which holds the user Raw Authenticator Key. If an attacker would be able to get hold of the Authenticator and obtain specialized access to the A-APP then in principle he would be able to mount a brute-force attack against the user PIN. For this he could proceed as follows:.

If this is a realistic scenario depends both on the additional security controls in A-APP.

One of the mitigation controls is that the time it takes to generate the PIN-Binder key KP, can be controlled as indicated in Section <NUM>. This means that if the A-APP requires that there are many user PINs possible, e.g. by letting it be a long passphrase instead of six digit string, one can control the time it takes for the attacker to find the PIN. To illustrate, suppose that each try takes about <NUM> second. Then a brute force approach has an expected run time of more than <NUM> years for a <NUM> digit PIN from an alphabet of <NUM> characters. This follows as <MAT>.

If the certificate is only valid for <NUM> years, then by the time the PIN is found it would be useless. Moreover, the user would typically have revoked its certificate within a few days and could be contractually forced to do so.

We note that in the approach of Section <NUM>, the AP can follow a similar scenario but one can argue that the associated risk is generally accepted. Indeed, there are simpler ways for the AP to impersonate as the user as he can simply generate a fraudulent Authenticator named to a user. Moreover, it is generally accepted in PKI-smartcard based authentication, i.e. the strongest formed of authentication, that the issuer can produce a PIN Unlocking Key (PUK) for each of the cards issued. When the issuer gets hold of a user PKI-smartcard then with the corresponding PUK the issuer can (ab)use the card. That is, in this context the PUK cater for similar scenarios as discussed which are easier to implement too. In other words, if the classical PKI-smartcard protects against attackers with high attack potential in this context, then the Authenticators following from our techniques do.

The second direct variant, is a variant of the first variant. There is a still a certificate Cert issued on the user Raw Authenticator Key but the certificate is directly encrypted by the A-APP following issuance and stored in the A-APP this way. Instead of sending the certificate in plaintext to the Service Provider, the A-APP sends the encrypted variant to the Service Provider. The Service Provider is still sent the Raw Authenticator Key (in plaintext) but is no longer able himself that this is bound by the certificate. For this, the Service Provider would then need to query the certificate issuer by sending both the certificate as the Raw Authenticator Key. The issuer then verifies if the certificate is valid and if it binds the Raw Authenticator Key. The issuer could also return user information from inside certificate. This would also be similar to the setup of OCSP, cf.

The second direct variant has as security advantage over the first variant that there is no longer (plaintext) information in the A-APP storage allowing for a brute-force of the PIN by any attacker getting (physical) access to the A-APP. However, with the user Raw Authenticator Key given the Service Provider could proceed as the attacker in the first direct variant. This scenario seems far less likely.

The second direct, variant has the same privacy disadvantage as the first variant.

The third direct variant, is a variant of the second variant. There is a still a certificate Cert issued on the user Raw Authenticator Key but the certificate is directly encrypted by the A-APP following issuance and stored in the A-APP this way. Instead of sending the certificate in plaintext to the Service Provider, the A-APP sends the encrypted variant to the Service Provider. In the third variant the Service Provider is no longer sent the Raw Authenticator Key but is sent a SP-bound Authenticator Key. This key resembles a Randomized Authenticator public key with the difference that the randomization factor R is fixed and only depends of the identity of the service provider. Once can construct such a SP-Binder key in a similar way as the PIN-Binder Key. That is, the A-APP constructs an extra PIN-Binder (the name SP-Binder seems appropriate) and forms the SP-Binder key from the SP-Binder and the identity of the Service Provider. The A-APP additionally constructs a non-interactive proof of knowledge (PoC) as in Section <NUM> showing knowledge of the SP-Binder key with respect to the Raw Authenticator key. This PoC is also encrypted for the certificate issuer. As part of signing, the A-APP sends the signature, the SP-bound Authenticator Key (plaintext) and the certificate and PoC in encrypted form. The SP-bound Authenticator Key can now be used by the Service Provider as a pseudonym similar to the FIDO setup. Moreover, by sending the SP-bound Authenticator Key, encrypted certificate and encrypted PoC to the certificate issuer the Service Provider can obtain information on the status of the SP-bound Authenticator Key and optionally additional user information. Indeed, the issuer can obtain the certificate and verify if it is valid. The issue could also obtain the PoC and verify if this a valid proof of knowledge with respect to the provided SP-bound Authenticator Key and the Raw Authenticator key in the certificate.

The security of the third variant is comparable to the second variant but has better privacy properties as Service Providers no longer obtain the user Raw Authenticator key allowing linking the user over Service Providers. As the certificate issuer receives the user certificate from all Service Provider, he is able to link the visits of the user.

The fourth variant is almost the same as the third variant. The only difference is that Service Providers also encrypt the SP-bound Authenticator Key for the certificate issuer. If then all cryptographic operations of the issuer take place in a separated, trusted environment within the AP, e.g. a Hardware Security Module (HSM), then the issuer is no longer able to link the user visits. This is comparable to the approach discussed in Section <NUM>.

In the fifth variant a certificate is issued on the Raw Authenticator Key that is encrypted in a specific, convenient fashion. During the certificate issuance process the AP generates a user specific, random scalar aU εR Fq and securely registers this under the account of the user, i.e. using the User-ID of the user. Next the AP computes the certified public keys of the user-. Gc = aU - G ∈〈G〉, Uc = aU · UP ∈〈G〉 these public keys are included in a certificate also binding other user information, e.g. the user name. Next the AP forms uses the techniques from [SCHNORR] and [FIAT] to form a non-interactive proof of knowledge PoC showing the relation between Gc and Uc, i.e. that: <MAT>.

Note that Equation (<NUM>) holds as logG(Gc) is equal to a. The certificate and the proof of knowledge PoC is sent to the user who can then validate the certificate: both the user information as the relation between Gc and Uc indicated Equation (<NUM>) in using the proof of knowledge PoC in combination with G and UP. If this validation is successful the user accepts the certificate and deletes the proof of knowledge PoC and UP.

When the user wants to sign a message M he proceeds as before leading to a signature (r, s) on message M corresponding to the Raw Authenticator Key UP. Next A-APP represents the signature as the pair (X, s) with X ∈〈G〉 as indicated in the observations following Algorithm <NUM>. Now the user calculates w = s-<NUM> mod q and encrypts this in two parts: <MAT>.

Note the resemblance of these expressions with those in Step <NUM> of Algorithm <NUM>. Next A-APP uses the techniques from [SCHNORR] and [FIAT to form a non-interactive proof of knowledge PoC<NUM> that Equation (<NUM>) holds, i.e.
there exists an x ∈ Fq such that: E<NUM> = x · Gc, E<NUM> = x · Uc (<NUM>).

Now A-APP sends the message M, the certificate together with X, E<NUM>, E<NUM> and PoC to the AP also referring to the User-Id. On receipt the AP validates that X, E<NUM>, E<NUM> are elements of 〈G〉 and also validates PoC1 proving statement (<NUM>) holds. Also the AP converts the x-coordinate of X to an integer x; and computes r = x mod q. If this is zero, the AP rejects the signature on message M returns an error to the user/A-APP. The APP increments the incorrect PIN. Counter with one as indicated earlier. Next the AP uses the registered scalar aU ∈ Fq to compute <MAT>.

Next the AP computes the hash H(M) of the message M and convert this to an integer e. Now the AP verifies that the following equality holds: <MAT>.

If this equality holds one can easily verify that (r,x-<NUM>) is a valid digital signature on message M corresponding to the Raw Authenticator Key and thus that the user has knowledge of the PIN. Here x refers to Equation (<NUM>) of which the AP knows exists but has no knowledge of. In other words, the AP knows there is signature without having access to it. Indeed, it easily follows that Equality (<NUM>) corresponds to Step <NUM> in Algorithm <NUM> albeit left and right side multiplied with the scalar aU.

If successful, the AP accepts the signature and resets the PIN-Counter to zero. Next the AP uses the techniques from [SCHNORR] and [FIAT to form a non-interactive proof of knowledge PoC<NUM> that
there exists an y ∈ Pq such that: X' = y - X, Gc = y · G.

Of course y = aU. Next the AP sends to the SP:.

Claim 1:
A method enabling a user generating a digital signature whereby the digital signature is fully under control of the user and that is dependent of a possession factor and a secret knowledge factor PIN, based on a software application, A-APP, on a platform holding a Secure Cryptographic Environment, SCE, that can be called by the A-APP, comprising of the following steps:
a) generating, in the SCE, a specific private signing key u and corresponding public key U, wherein the private key is non-exportable from the SCE,
b) forming a private key KP, based on secret knowledge factor PIN of the user entered in the A-APP and on another secret, non-exportable key in the SCE,
c) forming the digital signature on a message M by first performing an operation in A-APP on the hash e of message M on basis of the private key KP and letting call A-APP the SCE with the result e' of that creating a digital signature H using private key u whereby the SCE is not aware of the existence of private key KP,
d) operating on the returned digital signature H once again with the private key KP leading to another signature H' , which is actually a signature of a private key u', with corresponding public key U', wherein the private key u' depends on the original private signing key u and the private key KP in a fixed way and whereby the public key U' can be formed on basis of the public key U and private key KP and where U' is the signature verification key for signature H',
e) making available the signature H' and public key U' for a party which can then verify signature H' and associate public key U' with the user.