U2F/True2F Cryptographic Protocols Under the Hood

Nowadays, two-factor authentication is standard security best practice for user authentication in applications. Requiring a second factor for authentication besides a password diminishes an attacker’s ability to compromise a user’s account via techniques such as phishing. A common second factor is a one-time password (OTP) that is generated by a mobile application such as Google Authenticator or Duo.

A Universal 2nd Factor (U2F) hardware token is another second factor that is growing in popularity. Users complete an authentication workflow by pressing a button on an inserted USB-based hardware token that communicates with the user’s browser. Check out Yubico’s blog post for a comparison of U2F vs. OTP based two-factor authentication.

In this post, we will explore the cryptographic protocols used by U2F hardware tokens under the hood. Additionally, we will review some interesting extensions for improving hardware token resiliency against supply chain attacks as described in a paper by Dauterman et. al.

U2F Registration

U2F uses a challenge-response protocol in which a token responds to challenges sent by the server with the user’s browser serving as a intermediary that forwards messages between the token and server. Prior to using the token for authentication, a user must first register the token with the server.

The registration process consists of the following steps [1]:

  1. The server sends an application ID.
  2. The token generates an identity ECDSA key pair for the given application ID. Tokens use a unique ECDSA key pair during authentication for each unique identity. The token also generates a key handle.
  3. The token sends the identity public key and the key handle to the server.

In order to reduce the storage used on the token (which has very limited storage to begin with), in step 2, the token does not store the identity secret key and instead derives it using a key handle and a keyed one way function. Yubico generates identity secret keys using the application ID and a nonce as parameters in HMAC-SHA256 keyed by a global device secret. The nonce and a MAC created using the application ID and the device secret compose the key handle [2]. The server stores the key handle alongside the identity public key.

U2F Authentication

The authentication process consists of the following steps [3]:

  1. The server sends an application ID, challenge and key handle.
  2. The browser also includes an origin and TLS channel ID when forwarding the server’s message to the token.
  3. The token uses the key handle to derive the identity secret key for the application ID.
  4. The token increments a local counter that tracks the number of authentications performed using the token.
  5. The token sends the identity secret key’s signature over the application ID, challenge, origin, TLS channel ID and counter value to the server.
  6. If the signature is valid for the registered identity public key, the origin and TLS channel ID are correct and the counter value is valid, the server accepts the token’s response.

In step 2, since the key handle is scoped to the application ID, a token can determine if a received key handle is valid for a particular application ID. For example, using Yubico’s key generation scheme, a token would use the MAC included in the key handle to verify that the nonce was originally generated by the token for the given application ID. Then, the token would pass the nonce and application ID into HMAC-SHA256 keyed by the device secret to derive the identity secret key [2].

The token uses a local counter to defend against device cloning attacks. If an attacker is able to physically clone a token, the counter value would be same on both copies as the counter is only incremented during authentication. As a result, if a server sees a particular counter value more than once, it can infer that a device has been cloned and then block further authentication attempts [3].

The browser’s inclusion of the origin and TLS channel ID in step 2 followed by the server’s check of these fields in step 6 create phishing and man-in-the-middle (MITM) attack protection. The server can check that the same browser origin is included in the token’s signed response to confirm that a token did not sign data provided by a phishing site that differs from the origin that the server first communicated with. The server can also check that the same TLS channel ID is included in the token’s signed response to confirm that the same TLS channel session from the server’s first communication with the browser is used.

U2F also supports device attestation which is not discussed in this post [3].

U2F Areas for Improvement

While U2F includes features to protect against common phishing and MITM attack, the protocols used in production still have some areas that could be improved which are highlighted by Dauterman et. al [4]:

  • Many U2F tokens use a global authentication counter across all services. This global counter value could potentially be used to track a user authenticating at various services if service providers colluded.
  • If a token is faulty or compromised during a supply chain attack, then the user loses out on U2F security guarantees.

True2F

Dauterman et. al. propose True2F, a two-factor authentication system that provides user protection even in the presence of compromised tokens, as an improvement over U2F. Instead of solely relying on the token while executing the challenge-response protocol with the server, True2F has the token and browser collaborate in order to respond to a server. As long as the user’s browser is not compromised, the user can still securely authenticate with services even if the token is compromised. Then, once the token is discovered to be compromised, it can be discarded.

True2F leverages a few additional cryptographic primitives not used in U2F. and we will touch on the following:

  • Verifiable random functions (VRFs) [5]
  • Collaborative key generation
  • Firewalled ECDSA signatures

Note: The use of these primitives do not cover the entirety of the paper’s contributions. The paper also describes a log data structure for minimizing storage requirements while still mitigating the privacy risk of using a global counter among other topics.

True2F Key Generation

Instead of defining a master key pair as a single ECDSA key pair, True2F defines a master key pair as:

  • A master public key composed of a ECDSA public key and a VRF public key
  • A master secret key composed of a ECDSA secret key and a VRF secret key

When initializing a token, the token and the browser will execute the following collaborative key generation protocol [4]:

  1. The browser randomly samples a value v from the elliptic curve group. The browser sends a commitment to v.
  2. The token randomly samples its own value v' from the elliptic curve group. The token sends g^{v'} to the browser where g is the curve generator.
  3. The browser opens its commitment and reveals v. Then, the browser generates the public key as g^{v} \times g^{v'} or g^{v + v'}.
  4. The token verifies that v corresponds to the browser’s commitment. If browser’s commitment opening is valid, the token accepts the public key as g^{v + v'} and uses v + v' as the secret key.

The collaborative key generation protocol can be used to generate the full master key pair such that upon completion, the token has the master secret key and the browser has the master public key.

True2F Registration

True2F introduces verifiable identity families (VIFs), a method for deriving multiple ECDSA key pairs from a single master key pair [4]. A token and browser can use this method such that the browser can verify that the token correctly generated the ECDSA key pair. The browser is not able to audit the token’s operations in this manner in U2F.

The VIFs described in the True2F paper use VRFs which is why the master key pair contains a VRF key pair. During registration, the token, the browser and the server execute the following steps [4]:

  1. The server sends an application ID.
  2. The browser includes a random key handle when forwarding the server’s message to the token.
  3. The token uses its VRF secret key and the key handle to generate a pseudorandom output y and a proof \pi. Recall that \pi can be used in VRF verification along with the VRF public key to check that the output y was correctly produced using the VRF secret key.
  4. The token computes the identity public key by raising the master public key by y and sends it to the browser with y and \pi.
  5. The browser executes VRF verification using the VRF public key, the key handle, y and \pi. If VRF verification passes, the browser checks that the identity public key is equal to the master public key raised by y.
  6. If the checks in step 5 pass, the browser forwards the key handle and the identity public key to the server.

True2F Authentication

During authentication, the token, the browser and the server execute the following steps [4]:

  1. The server sends an application ID, challenge and key handle.
  2. The browser also includes an origin and TLS channel ID when forwarding the server’s message to the token.
  3. The token uses the key handle, and its VRF secret key to generate the pseudorandom output y. The token can derive the identity secret key by multiplying the master secret key by y.
  4. The token increments a local counter that tracks the number of authentications performed using the token.
  5. The token and the browser execute a firewalled ECDSA signature protocol in order to produce the identity secret key’s signature over the application ID, challenge, origin, TLS channel ID and counter value which is sent to the server.
  6. If the signature is valid for the registered identity public key, the origin and TLS channel ID are correct and the counter value is valid, the server accepts the token’s response.

The firewalled ECDSA signature protocol described in step 5 uses a cryptographic reverse firewall which is defined as a machine that modifies the messages of a user’s machine as it interacts with the outside world in an effort to secure the user against a compromised machine while still preserving the functionality of the underlying protocol [7]. In True2F, the browser serves as the firewall that prevents a compromised token from using bad randomness when producing signatures or leaking information using signatures. The protocol consists of the following steps [4]:

  1. The token and the browser execute the collaborative key generation protocol previously described such that upon completion, the token has some value k and the browser has a value g^{k}.
  2. The token uses k as the random ECDSA nonce [6] when producing a signature.
  3. The browser checks that the correct nonce was used to produce the signature.
  4. The browser uses the token’s signature to produce another valid signature and sends it to the server.

As mentioned in a previous post, ECDSA verification requires the calculation of a point P = kG where k is a nonce. In step 3, the browser checks that the correct value for k is used. In step 4, the browser makes use of ECDSA signature malleability where both (r, s) and (r, -s \mod n) are valid signatures to produce another valid signature to send to the server.

Conclusion

U2F utilizes the basic cryptographic building blocks of digital signatures and keyed one way functions to enable the use of hardware tokens for two-factor authentication systems resistant to phishing and MITM attacks. True2F attempts to improve U2F by introducing a few new building blocks that allow a user’s browser to participate in protocols thereby protecting the user from compromised tokens. The paper is pretty interesting and worth a read!

References

[1] https://fidoalliance.org/specs/fido-u2f-v1.2-ps-20170411/FIDO-U2F-COMPLETE-v1.2-ps-20170411.pdf

[2] https://developers.yubico.com/U2F/Protocol_details/Key_generation.html

[3] https://developers.yubico.com/U2F/Protocol_details/Overview.html

[4] Dauterman et. al. “True2F: Backdoor-Resistant Authentication Tokens”. https://arxiv.org/pdf/1810.04660.pdf.

[5] https://en.wikipedia.org/wiki/Verifiable_random_function

[6] https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/

[7] Mironov et. al. “Cryptographic Reverse Firewalls”. https://eprint.iacr.org/2014/758.pdf.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s