Authentication and Software Security: Course Notes

notes
Author

Rebecca Kempe

Published

November 15, 2026

Password-Authenticated Key Exchange (PAKE) Protocols

SPEKE Paper (Strong Password-Only Authenticated Key Exchange, David Jablon)

David Jablon’s paper (Jablon 1996) was published in 1996. The goal was to propose a way to do remote authentication over an insecure channel using only a “small password” (i.e. a user chosen, memorizable secret). One of the goals of this was to resist dictionary attacks:

A new simple password exponential key exchange method (SPEKE) is described. It belongs to an exclusive class of methods which provide authentication and key establishment over an insecure channel using only a small password, without risk of offline dictionary attack.

At the time, Password Authenticated Key Exchange (PAKE) was known to be a hard problem. (It is still known to be a hard problem now.)

The remote password problem

  • “Passwords must be memorized, and are thus small, while keys can be recorded, and can be much larger.”
  • “Most methods of remote secret-based authentication presume the secret to be large. We really want to use an easily memorized small secret password, and not be vulnerable to dictionary attack.”

The general problem with memorizable secrets is that they are brute-force searchable.

A lot of attempts at password-based authentication protocols failed because passwords are brute-froceable. For example, the paper describes this bad way for Alice to verify that Bob knows a password:

Let \(h\) be a one-way hash function, \(R\) be a random nonce, and \(S\) be a password, let | denote concatenation, and consider the following protocol:

  • Alice sends \(R\) to Bob.
  • Bob receives \(R\) and sends \(Q = h(R|S)\) to Alice.

In this protocol, Alice is able to verify that Bob knows \(S\) by computing \(h(R|S)\) and comparing the value she obtains to \(Q\). However, an attacker can obtain \(S\) through exhaustive search or dictionary attack by computing \(h(R|S_i)\) and checking whether the result is equal to \(Q\) for every password candidate \(S_i\) found.

Characteristics of “strong password-only methods”

The following were Jablon’s goals while designing his protocol:

  1. Prevent offline dictionary attacks (more on this later)
  2. Survive online dictionary attacks (doable through throttling/limiting access attempts)
  3. Providing mutual authentication (in this method, each party must prove to the other that they know the password
  4. Integrated key exchange (the authentication and key exchange steps must happen as part of an integrated protocol to avoid the possibility of an attacker in the middle)
  5. The protocol should not require any additional infrastructure (e.g. PKI) or additional secrets.
  6. Perfect forward secrecy (disclosure of the password doesn’t reveal prior recorded conversations.)
  7. Direct authentication (both sides verify the session key before proceeding)
  8. No timestamps (the messages don’t contain time-dependant data, which might require time synchonization between the parties.)

When this paper refers to offline dictionary attacks, it is not just the traditional idea of stealing a password file and calculating all of the hashes. This protocol is trying to avoid leaking any information that could help an attacker guess the password or even just narrow the range of possible passwords. It is also trying to avoid leaking any verifiable text. The idea is that an attacker who observes multiple runs of the protocol should not be able to obtain any information about the password at all.

Note: the Diffie-Hellman protocol is unauthenticated and vulnerable to middle-person attacks.

The SPEKE Protocol

One of the goals of password-authenticated key exchange is to “amplify” the power of the shared secret to establish a much larger (and hopefully therefore more secure) session key. (Session keys are typically ephemeral.) The idea is to two parties, which share a password (S) over an insecure network and generate a new session key K. This involves doing math in finite groups.

Terminology:

  • \(S\) is Alice and Bob’s shared password
  • \(p\) is a Diffie-Hellman prime
  • \(q\) is a large prime factor of \(p-1\)
  • \(g\) a “Diffie-Hellman (DH) base”, which is either primitive (i.e. a generator of the entire group) or of large prime order
  • \(G_x\) is a subgroup of \(\mathbb{Z}_n^*\) of order \(x\), where \(x\) is a factor of \(p-1\)
  • \(f(S)\) is a function that converts \(S\) into a suitable DH base
  • \(R_A\), \(R_B\) are random numbers chosen by Alice and Bob
  • \(Q_A\), \(Q_B\) are exponential values chosen by Alice and Bob
  • \(E_k(m)\) is a symmetric encryption function that encrypts \(m\) using key \(k\)
  • \(h(m)\) is a strong one-way hash function of \(m\)
  • \(K\) is the generated session key
  • \(A \rightarrow B : m\) means Alice sends \(m\) to Bob

SPEKE has two stages. In the first stage, Alice and Bob use a DH exchange to establish a shared key \(K\), but instead of using a fixed primitive base \(g\), a function \(f\) is used to convert the password \(S\) into a base for exponentiation. In the second stage of SPEKE, Alice and Bob each confirm that the other knows K before using it as a session key (there are multiple ways to do this).

Stage 1:

  1. \(A \rightarrow B: Q_A = f(S)^{R_A} \mod p\)
  2. \(B \rightarrow A: Q_B = f(S)^{R_B} \mod p\)
  3. Alice computes \(K = h({Q_B}^{R_A} \mod p)\) 1
  4. Bob computes \(K = h({Q_A}^{R_B} \mod p)\)

Stage 2, method one (\(C_A\) is a random nonce chosen by Alice, \(C_B\) is a random nonce chosen by Bob):

  1. \(A \rightarrow B: E_K(C_A)\)
  2. \(B \rightarrow A: E_K(C_B, C_A)\) 2
  3. Alice verifies that \(C_A\) is correct
  4. \(A \rightarrow B: E_K(C_B)\)
  5. Bob verifies that \(C_B\) is correct

Stage 2, method two (this one is way more elegant, in my opinion):

  1. Alice sends proof of K: \(A \rightarrow B: h(h(K))\)
  2. Bob verifies that \(h(h(K))\) is correct, then \(B \rightarrow A: h(K)\)
  3. Alice verifies that \(h(K)\) is correct.

This approach just uses the key \(K\) in place of using random nonces, which is allowed because \(K\) was built using random information from both sides. 3

Security constraints

Here are a few important constraints on choosing the parameters:

  • the modulus \(p\) must be huge, in order to prevent discrete log attacks
  • test that \(Q_x\) isn’t 0 to avoid forcing \(K = 0\)
  • \(p-1\) must have a large prime factor \(q\) to prevent attack by Pohlig-Hellman computation
  • the base must be a generator of \(q\) to avoid partition attacks on \(Q_r\)
  • base must equal \(S^x \text{mod } p\) to prevent attack by single discrete log computation
  • a one-wat hash of \(K\) must be used to prevent narrowing attacks (what are those??)
  • the protocol must be aborted if \(K\) has a small order to avoid subgroup confinement attacks, aka small subgroup attacks

One interesting point that is mentioned is that while using a safe prime (\(p = 2q + 1\), where \(q\) is prime) with a base \(g\) that is a primitive root of \(p\) is recommended for DH exchange, in order to prevent discrete log attacks, this is not a necessary constraint (it is more than sufficient). While safe primes are good for security purposes, they are very computationally expensive, and values of \(g\) that are generators of very large subgroups can work as well.

Discrete log attacks

The security of DH type schemes depends on the assumption that exponentiation is a one-way function.

A discrete log computation inverts an exponentiation modulo \(p\) to reveal the exponent, and ultimately the password. The security of this protocol depends on the assumption that this computation is practically impossible, but the actual difficulty of this problem depends on the size and character of \(p\).

These days, 3072 bit primes are recommended to avoid discrete logs mod p, or 256-383 bits for elliptic curve implementations.

Partition attacks

It is possible for exchanged, encrypted exponentials to leak information about the password \(S\). Leaking even a single bit of such information can be really bad if that bit is able to be used to partition a password dictionary (or possibly, the search space) into possible and impossible candidates.

For example, if leaking 1 bit per attack run of the protocol decreases the search space by half each run, the search space is cut by a factor of \(2^20\) over 30 runs, which is insane.

Small subgroup attacks

An attacker who knows the structure of \(G_{p-1}\) might be able to force the value of \(K\) to be confined to a small subgroup, which would allow a guessing or brute force attack on \(p\).

The goal of a subgroup confinement attack on a DH exchange is to confine \(K\) to a predictable and small group of values, by causing at least one of the parties to use a number of a small order \(t\) as the base of exponentiation.

All operations in \(\mathbb{Z}_p^*\) are done modulo \(p\). (Really, there is only one allowed operation, which is multiplication mod \(p\), since exponentiation is just repeated multiplication). Group axioms tell us that multiplying any two elements of \(\mathbb{Z}_p^*\) mod \(p\) yields another element of \(\mathbb{Z}_p^*\). Since \(p\) is prime, we are guaranteed the existence of an element which, when multiplied by itself repeatedly, produces all group elements – this is known as a generator, denoted \(g\).

All subgroups of a cyclic group are cyclic (really, this is common sense). Lagrange’s theorem tells us that the order of a subgroup divides the order of the group and also that the order of each element (that is, the number of elements its powers generate) divides the order of the group. Another particularly important property (property F6 in (Van Oorschot 2021)) is that for any generator \(g\) of a cyclic group \(G_n\), and any divisor \(d\) of \(n\), \(h = g^{n/d}\) produces an element of order \(d\).

A small subgroup attack proceeds in the following way: we let \(p = Rq + 1\), where q is a safe prime, and let \(g\) be a generator for \(\mathbb{Z}_p^*\). If R is large and has a small divisor \(d\) (or many), then \(b = g^{(p-1)/d}\) has order \(d\), by property F6. In this case, a middle-person attacker can intercept the exponentials \(g^a\) and \(g^b\) and raise both to the power \((p-1)/d\) prior to retransmitting them. The resulting shared key is then \(K = (g^{(p-1)/d})^{ab} = b^{ab}\). But as we established before, \(b\) has order \(d\) (which is a small divisor!) so \(K\) only has \(d\) possible values.

Typically, each party will test that \(x^q = 1 \pmod{p}\), where \(x\) is the received value (exponential) they received from the other party. If this is true, then \(x\) was a member of the subgroup \(G_q\) (I think, anyway).

Authentication Protocols and Key Establishment (Van Oorschot 2021)

Definitions

  • A protocol involves an exchange of messages between two parties; a cryptographic protocol involves cryptographic techniques
  • Entity authentication is a process to verify the identity of the communicating party
  • An *authentication protocol” is a cryptographic protocol that provides entity authentication, authenticated key establishment, or both
  • unilateral authentication is when one party authenticates itself to another; very common (server will prove its identity to the client)
  • mutual authentication is when each party proves its identity to the other party; not as common (for example, it’s supported in TLS, but not many people actually use it)
  • Key establishment is a means by which two end-parties arrange a shared secret (usually a symmetric key) for use in securing subsequent communications. Such keys used for short periods of time are known as session keys, data keys (used for encrypting data rather than managing other keys), or ephemeral keys
  • key transport is when one party unilaterally chooses the symmetric key and transfers it to the other
  • key agreement is when the shared key is created as a function of values contributed by both parties; this is commonly done by some variation of a DH exchange authenticated by long-term keys. Deterministic derivation of session keys from a long-term key is BAD because compromise of the long term key puts all session keys at risk (i.e. it violates forward secrecy)
  • authenticated key establishment is when entity authentication and key establishment are integrated into the same protocol; this is necessary to make sure that the key is shared with the same party that was authenticated earlier (i.e. to avoid middle-person attacks)
  • key management involves establishing shared keys, securing them in transit and in storage, and for public keys, establishing trust in them and maintaining their integrity and authenticity. Keys used for securing data at rest must also have some kind of backup/recovery method in case the keys are lost (e.g. due to hardware failure or something)
  • a proof of knowledge is convincing evidence of knowing the secret that does not involve revealing the secret itself.

Relevant types of attacks

  • replay attack: reusing a previously captured message in a later protocol run
  • reflection attack: replaying a captured message to the originating party
  • relay attack: forwarding a message in real time from a distinct protocol run
  • interleaving attack: weaving together messages from distinct concurrent protocol runs
  • middle-person attack: exploiting use of a proxy between two end-parties
  • dictionary attack: using a heuristically prioritized list in a guessing attack
  • forward search attack: feeding guesses into a one-way function and seeking output matches
  • pre-capture attack: extracting client OTPs by social engineering, for future use

Time-variant parameters (aka nonces)

A common threat model for cryptographic protocols is that all messages pass through an attacker-controlled point.

A lot of attacks on crytographic protocols involve reusing messages from ongoing or previous protocol runs. Defenses involve cryptographically binding messages within a protocol run using time variant parameters. These can be helpful in a few ways:

  • providing messages with uniqueness or timeliness/freshness properties
  • cryptographically binding messages from one protocol run to each other, to distinguish different protocol runs from each other

Basic types of time-variant parameters, each of which is also known as a nonce:

  • random numbers: used in challenge-response protocols to provide freshness guarantees, chain protocol messages together, and provide evidence that a far-end party has corrected computed a session key; also used as confounders to stop certain types of attacks. These are expected to be unpredictable, never intentionally reused, and sufficiently long that it is extremely unlikely that they will inadvertently be reused by an honest party.
  • sequence numbers: these provide message uniqueness (unpredictability is not always necessary) - this is used to rule out message replay
  • timestamps - these give timeliness without the challenge part of challenge-response, and they help enforce constraints in time-bounded protocols (e.g. Kerberos). These require synchronized clocks.

Basic (textbook) Diffie-Hellman key agreement

System parameters: a large prime \(p\) and a generator \(g\) (where the group is \(\mathbb{Z}^*_p\))

  1. A chooses a random private key \(a\) and sends B \(g^a \pmod{p}\)
  2. B chooses a random private key \(b\) and computes \(K = (g^a)^b \pmod{p}\)
  3. B sends A \(g^b \pmod{p}\)
  4. A computes \(K = (g^b)^a \pmod{p}\)

Note: this is not actually authenticated and is subject to middle-person attacks - authenticated DH is provided by the Station-to-Station (STS) protocol, which requires a PKI.

Key authentication properties and goals

Basic requirements for a session key include freshness (the key must not be reused from a previous session), sufficient length, randomness, and both parties should know who the key is shared with.

A protocol provides forward secrecy if disclosure of long-term secrets does not compromise the secrecy of session keys from earlier runs. This is provided when old session keys cannot be reconstructed from long-term keys alone, and when session keys are ephemeral (i.e. they are deleted at the end of the session)

A key-establishment protocol provides known-key security if compromise of session keys does not put future key management at risk – that is, compromised session keys should not allow later impersonation or compromise of long-term keys or future session keys.

When a session key is meant for use in a real-time communication, the liveness property is desired - entity authentication and key establishment done in one integrated protocol provides the assurance that the identifies far-end party is the one that is actually involved in the protocol and participating at the present instant.

Key use confirmation involves providing assurance that a party actually possessed the correct session key or data key.

Implicit key authentication is key establishment whereby the scope of who could potentially have key access is narrowed down to one previously identified party, but it’s unconfirmed whether or not they actually possess it. Once this possession is confirmed through key use confirmation, we have explicit key authentication (which is probably what we want in authenticated key exchange, though implicit key confirmation still counts).

Password-authenticated key exchange (PAKE)

Password-authenticated key exchange (PAKE) protocols use weak secrets (i.e. passwords) to establish authenticated session keys. Password-based protocols often convert passwords into symmetric keys using a key derivation function, but this isn’t ideal for two reasons:

  1. Protocol data visible to an attacker might allow testing individual password guesses if it can serve as verifiable text
  2. User-chosen passwords are generally weak and are often either predictable (through using a dictionary) or within a search space that is small enough to be exhaustively searchable.

PAKE protocols aim to resist offline-guessing attacks by avoiding protocol data that can be used as verifiable text.

A dictionary attack refers to a method that steps through a list of password candidates, ordered in decreasing probability (expectation) of success. An offline-dictionary attack does not involve any per-guess interaction with a legitimate verifier, and therefore incorrect guesses go unnoticed.

Partition attacks

Partition attacks are possible when there is a data field in a protocol message that leaks information which allows a partition of a list of password candidate guesses into two disjoint sets: possible passwords and eliminated passwords. (This data field would be known as partitioning text.) If the partition is of roughly equal size, then a dictionary of \(2^n\) entries is cut down to \(2^{n-1}\) entries.

If each protocol run randomizes the data in such a way that the dictionary candidates are randomly distributed, would reduce the remaining dictionary again by half, and so on. Each protocol run leaks information about the secret. This attack strategy appears regularly in cryptography.

Forward search attacks

Testing passwords (or weak secrets) is often possible as a result of recognizable formats. For example if there is a known text field or a field with a known structure, this can be used as a verifier in a dictionary or brute force search attack. The standard defense against this is to insert a field for a random number \(r\), which is known as a confounder. This prevents attacks because an attacker now needs to guess the correct random number in order to proceed with their exhaustive search attack. This is analogous to password salting. 4

SoK: Password Authenticated Key Exchange

PAKE protocols are now being adopted in three main areas of application: credential recovery (such as in iCloud, 1Password, and ProtonMail), device pairing (such as in e-passports and WPA3), and end-to-end (E2E) secure channels (such as in BlackBerry messenger) (Hao and Oorschot 2022). (Hao and Oorschot 2022) suggests that the desire to adopt these protocols led to several attempts at standardization, most of which went wrong (due to security flaws in the standardization candidates). For instance, between 2000 and 2008 IEEE formed a working group to attempt to select PAKE protocols for standardization. Unfortunately, almost all of the candidate protocols were found to be broken, even after several attempts at revision. The standard that was created has since been withdrawn.

A PAKE protocol can either be balanced or augmented. Balanced PAKE protocols assume that the two parties wishing to establish a key share a password (or password-derived secret). The problem with using such protocols in a client-server environment is that storing the secret on the server leaves it open to being stolen to impersonate the client. Augmented PAKES are designed to address this, and the approach chosen is generally to have the server not actually store the secret, but store some kind of one-way transformation of itinstead (such as a one-way hash.)

According to (Hao and Oorschot 2022), PAKE protocols can be categorized into five classes. The first two classes are derived based on how the passwords are used in the design: Class 1 consists of protocols that use the password as an encryption key and Class 2 consists of protocols that use the password as an input string to derive a generator. Class 3, 4, 5 all use the password as an exponent in multiplicative groups or as a scalar in additive groups. Class 3 protocols rely on a trusted setup, Class 4 protocols (well I guess protocol singular, since there is only one) are a form of a secure two-party computation problem, and Class 5 protocols use the password to derive the exponent for the verification stage of Diffie-Hellman key exchange.

Balanced and augmented protocols

A balanced PAKE protocol assumes that the two parties share a secret. Typical requirements are:

  1. Resisting offline password guessing attacks
  2. Limiting online attacks to one password guess per protocol execution
  3. Ensuring session key security
  4. Providing forward secrecy.

The problem is that using balanced PAKE protocols in client-server settings can be problematic, since if the secret is stolen from the server, it can be used to impersonate the client. Therefore, a fifth requirement is “server compromise resistance”.

FIDO2 Authentication Framework and Standard

Security Keys paper (Lang et al. 2017)

Context

The context here is that these were invented to get away from using one-time passwords (OTPs). One time passcodes are vulnerable to phishing and middle-person attacks and have some usability drawbacks, such as requiring the user to manually copy codes from one device to another.

The Universal Second Factor (U2F) protocol was initially developed by Google to improve the experience of employees who needed to use hardware tokens as a second factor of authentication (Lang et al. 2017). After internal testing and deployment, Google shipped support for the protocol in their browser and created an industry alliance to standardize the design and convince more vendors to implement it in their products.

Threat Model

Security keys try to defend against:

  • web attackers (entities who control malicious websites)
  • related-site attackers (entities who try to reuse stolen credentials from one site on other sites)
  • network attackers (adversaries that can intercept and modify traffic between the user and the legitimate site)
  • malware attackers (adversaries that can compromise users’ computers and run arbitrary software with arbitrary privileges)

Attack consequences:

  • Session duplication: an attacker is able to steal credentials that allow them to access the user’s account from any computer and at any time. Credentials could include cookies or passwords, assuming the cookie doesn’t expire or the password doesn’t change.
  • Session riding happens when the attacker can only access or modify the user’s account when the user is actively using their computer.

Design goals

  • Easy for users - it must be difficult to use Security Keys incorrectly or insecurely
  • Easy for Developers - It should be easy for devs to integrate Security Keys into their website through simple APIs
  • Privacy - Security Keys shouldn’t allow tracking of any kind, and if a security key is lost, it should be difficult for an attacker to get any useful information from it
  • Security - Security keys should protect users against password reuse, phishing, and man-in-the-middle attacks

System operations

  • Registration: The security key generates a fresh asymmetric key pair and returns the public key. This public key is then associated with the user account.
  • Authentication: The security key tests for user presence and exercises its private key to provide a response. The server can verify that this response is valid, and therefore authenticate the user.
Registration Procedure

Here are some definitions that are useful for understanding the protocol:

  • A web origin is a (scheme, host, port) triplet that is used to uniquely identify services running on the web. This triplet is derived from the URI of the service. The scheme is (usually, but not always) the protocol used to fetch resources, the host is the fully qualified domain name, and port is the port on which the accessed service is running (we use the default port for the specified scheme if no port is explicitly given in the URI) (Van Oorschot 2021).
  • A key handle, in the context of this protocol, is like an index for looking up a private key that is stored in a database. Storing a key handle creates an index into the database table, and retrieving a key handle looks up the private key stored at the given index. However, literally using a database-like indexing implementation for key handles would create a predictable index, which is bad for security and privacy reasons, so the Security Keys implementation uses a form of key wrapping (encrypting a cryptographic key with another, usually symmetric key) to create the key handle (Lang et al. 2017).
  • The TLS channel ID mentioned in (Lang et al. 2017) seems to be referring to the Token Binding that was later standardized in RFC 8471 (Popov et al. 2018). To establish such a Token Binding, a client generates a public-private key pair for each server it communicates with. During the first communication, the client provides the public key to the server and proves to the server that it knows the private key. A Token Binding ID (TB ID) is then created, which can be used over multiple different sessions. Later on, the client can send what (Popov et al. 2018) calls a “security token” containing the TB ID to the server, which will reject the security token if the ID within it does not match the TB ID it previously established with the client. This allows the server to detect middle-person attacks on TLS (Lang et al. 2017).
  • The attestation certificate mentioned in (Lang et al. 2017) refers to a certificate embedded in each Security Key that allows servers to identify the type and batch of a device. This allows a server to choose to only accept certain certain models of Security Keys or to revoke models that are known to be flawed or compromised. Typically, devices uses batch attestation, meaning that an entire batch of Security Keys will share an attestation certificate. This is for privacy reasons – it prevents devices from being uniquely identifiable via the attestation certificate.

I will now present a detailed explanation of the U2F registration operation, as described in the Security Keys implementation and Chrome web browser API presented in (Lang et al. 2017). I will explain the operations happening at multiple layers of abstraction, including everything between the browser API layer and the level of individual operations performed in the cryptographic protocol. I will refer to the web server (relying party) as the server and to the web browser (client) as the browser. A diagram summarizing this explanation can be found in Figure 1.

  1. The server requests to register a new Security Key by using the browser API u2f.register(), which accepts two parameters: a random challenge and a list of currently registered key handles. Both the challenge and the list of key handles are sent to the browser.
  2. The browser verifies that the Security Key has not already been registered by checking the list of key handles (I am unsure of how this process happens).
  3. The browser creates a data structure called the “Client Data”. To do this, it binds together the server-provided challenge, the type of request (register or authenticate; in this case, the type is register), and the TLS channel ID.
  4. The browser sends a register command to the Security Key. This command takes two parameters, which (Lang et al. 2017) refers to as the application parameter (this is the web origin of the server) and the challenge parameter (this is a hash of the Client Data). For clarity and consistency, I will refer to these as the web origin and hash(Client Data), respectively.
  5. The Security Key generates a new public-private key pair \((k_{pub}, k_{priv})\), which it associates with the browser. The Security Key performs an operation called store which creates a key handle \(H_k\) from the web origin and \(k_{priv}\) using key wrapping. Here are some details of the store operation:
    1. The web origin is encrypted with a symmetric key that is both unique to the Security Key and only known by the Security Key. This key is denoted \(K_{app}\) in (Lang et al. 2017) and the result of this encryption is denoted \(app'\).
    2. \(k_{priv}\) and \(app'\) are interleaved together and the result is known as the plaintext.
    3. The plaintext is encrypted with the wrapping key \(k_{wrap}\), which is a second symmetric key that is both unique to the Security Key and only known by the Security Key. The result of this encryption is the handle \(H_k\).
  6. The Security Key concatenates the public key \(k_{pub}\), the key handle \(H_k\), hash(Client Data) and the web origin. These are signed with the device’s attestation private key, \({Priv}_{attest}\). This signature is denoted \(s\).
  7. The Security Key outputs a Registration Message back to the browser. This message includes \(k_{pub}\), \(H_k\), the Security Key’s attestation certificate, and \(s\).
  8. The browser sends the Registration Message and the Client Data to the server.
  9. The server verifies the signature \(s\) and makes sure that the Client Data matches its own view of the protocol.
  10. The server verifies the attestation certificate to make sure that it is trusted (and by extension, checks that the Security Key is allowed to be used).
  11. The server stores \(H_k\) and \(k_{pub}\) and associates them with the registering user’s account.
Figure 1: Security Keys Registration Protocol Diagram
Authentication Operation
  1. The relying party (the website) sends the desired key’s handle and a challenge to the web browser.
  2. The browser generates the client data and sends a hash of the client data along with the key handle and the web origin to the Security Key
  3. If the security Key doesn’t recognize the web handle, or doesn’t agree that it is associated with the web origin that requested the signature, it rejects the request. Otherwise, it produces a signature of the client data.
  4. The Security Key signs two other attributes: whether the Test of User Presence (TUP) succeeded, and a counter value. The counter value is a 32 bit value that is incremented with every signature the Key performs; it allows the server to detect (but NOT prevent) potential duplication of the a Security Key, e.g. when the counter value appears to decrease from one signature to the next.
Misc stuff + notes
  • counter: if there is a compromise and the security key is somehow cloned, the counter of the number of times the signature was used will be different on the two tokens. This is a detection, not a prevention device, and the rule is that the counters must always be increasing.
  • the channel ID is the browser’s view of the TLS public key; the signed channel ID in the response is compared by the server to what it sees in the TLS layer. It’s meant to prevent a MiTM attack on TLS during the registration phase.

A Formal Analysis of the FIDO U2F protocol (Feng et al. 2021)

Introduction

The goal of the FIDO suite of protocols is to allow users to log into remote services with a local, trusted authenticator. (An example of a local, trusted authenticator might be a fingerprint scanner on a smartphone).

The original FIDO protocol suite contains two sets of specifications: Universal Authentication Framework (UAF) and Universal Second Factor (U2F). UAF replaces password authentication, whereas U2F adds a second factor.

Lowe’s Taxonomy of Authentication Properties

These properties are used to precisely formalize authentication properties in such a way that they can be directly modelled in formal methods.

Multiple levels of authentication, from A’s point of view, between an initiator A and a responder B:

  1. Aliveness: Whenever A completes a run of the protocol, the aliveness property ensures that B previously has been running the protocol, though not necessarily with A
  2. Weak agreement: Whenever A completes a run of the protocol, the weak agreement property ensures that B has previously been running the protocol with A, though not necessarily with the same data
  3. Non-injective agreement on data items ds: Whenever A completes a run of the protocol, the non-injective agreement property ensures that B has previously been running the protocol with A. Also, A and B have agreed on the data values in ds.
  4. Injective agreement on data items ds: Whenever A completes a run of the protocol, the injective agreement property ensures that B has previously been running the protocol with A, A and B have agreed on the data values in ds, and each run of the protocol corresponds to a unique run of B. This helps to prevent relay attacks.

UAF Security Goals

  • Strong User Authentication: Authenticate (i.e. recognize) a users and/or device to a Relying Party with high cryptographic strength.

  • DoS Resistance: be resilient to Denial of Service Attacks (i.e. prevent attackers from inserting invalid information for a legitimate user for the next login phase, since this will prevent the legitimate user from being able to log in successfully again in the future)

  • Forgery Resistance: be resilient to Forgery Attacks (i.e. Impersonation Attacks). This means preventing attackers from attempting to modify intercepted communications to masquerade as the legitimate user and log into the system.

  • Parallel Session Resistance: Be resilient to Parallel Session Attacks. These attacks occur when without knowing a user’s authentication credential, an attacker can masquerade as the legitimate user by creating a valid authentication message out of some eavesdropped communication between the user and the server.

  • Forwarding Resistance: be resilient to Forwarding and Replay attacks. These happen when an attacker that has intercepted previous communications can impersonate the legal users to authenticate to the system. The attacker can replay or forward the intercepted messages.

  • Verifier Leak Resilience: Be resilient to leaks from other relying parties (i.e. nothing that a verifier could possibly leak should be able to help an attacker impersonate a user to another relying party)

  • User consent: Notify the user before a relationship to a new relying party is established (requiring explicit consent)

  • Transaction Non-Repudiation: Provide strong cryptographic non-repudiation for secure transactions.

  • Unlinkability: Protect the Protocol conversation such that any two relying parties cannot link the conversation to one user.

Bluetooth

Bluetooth notes

Introduction to Bluetooth and its Pairing Protocols

The Bluetooth protocol is used for short-range wireless communications between a central device (usually the more powerful device) and a peripheral (usually a lower-powered device) (van Oorschot 2026). In order for two devices to communicate with each other via Bluetooth, they must first participate in device discovery, in which the initiating device sends out inquiry messages. Devices that are available for communications with the initiating device (that is, devices that have been put into discoverable mode) send inquiry responses containing their Bluetooth address back to the initiating device (van Oorschot 2026; Wu et al. 2024). Once two devices have decided to communicate with each other, they must pair with each other. Device pairing is the process by which a shared key between the central device and the peripheral is determined. This key is called the long-term key and is used as a basis for encrypting future communications (data exchange) between the two devices. This encryption is typically done using 128-bit key AES-CCM (van Oorschot 2026). When two devices store the shared key in memory, they are called bonded5 devices. The Bluetooth standard is managed by the Bluetooth special interest group (SIG).

Bluetooth pairing in Bluetooth Low Energy (BLE) and Bluetooth Classic (BC) uses one of four different association models for authentication. These models are determined based on the advertised input and output capabilities of the pairing devices (van Oorschot 2026). The Just Works association model (JW) is used when at least one of the pairing devices lacks both keypad input and display output capabilities. In this mode, no authentication is performed before pairing. The Numeric Comparison mode (NC) is used when both devices have a display as well as the ability to accept YES or NO input from the user. In this mode, the user is asked to verify that the six-digit numbers displayed on both devices are identical in order to authenticate the match. The Passkey Entry mode (PE) is used in two scenarios. In the first scenario, one device has a keypad but no display, and the second device only has a display. In this scenario, the device with a display outputs a secret 6-digit number that the user must input into the second device’s keypad. In the second scenario, both devices have a keypad but no display. In this case, the user must choose a secret 6-digit number and input it into both devices. In this case, security depends on whether the user-chosen secret is truly secret. Lastly, the Out-of-Band mode (OOB) is used when an out-of-band method is available to transfer some secret value between the two devices. The Bluetooth specification has largely left this method up to implementation by individual vendors (van Oorschot 2026).

The different association models have different underlying authentication protocols that share beginning and ending stages. Each method has a different stage in the middle of the protocol. Notably, JW uses the same protocol as NC, but rather than displaying two numbers for the user and waiting for confirmation of a match, the protocol simply assumes that the six-digit numbers on each device match each other.

The protocols for both NC and PE involve commitments to nonces. The general idea behind these commitments is that they are meant to ensure that each device selects their nonces independently. If an attacker is allowed to choose their nonce with prior knowledge of the other nonce, it can enable middle-person attacks on the protocol (see Example 14.6 in (van Oorschot 2026)).

Bluetooth communication sessions

  • Bluetooth has a packet-based communications architecture
  • A Bluetooth device address (BD_ADDR) is a globally unique 48-bit identifier (equal in length to a MAC address) that is intended for use exclusively in the context of Bluetooth.

Bluetooth communication sessions proceed in three stages:

  1. Device Discovery: The initiating device sends out inquiry messages. Devices wishing to be found get put into discovery mode and respond with their BD_ADDR; an initiator must know a device’s BD_ADDR to establish a connection to it.
  2. Device pairing: This establishes a shared key between devices, used as the basis for data encryption and (in BC) device authentication.
  3. Data exchange: This is encrypted using 128 bit AES-CCM

Bluetooth stacks/versions

  • Both Bluetooth stacks support legacy protocols and algorithms, which is bad for security reasons.

The KNOB attack on Bluetooth

The Key Negotiation of Bluetooth (KNOB) attack allows a third party to force two or more devices to agree on an encryption key that only has one byte of entropy (Antonioli, Tippenhauer, and Rasmussen 2019). This is possible because the Bluetooth specification required devices to support encryption keys with entropy ranging from one to sixteen bytes (or, at the very least, most manufacturers interpreted the standard that way). This means that the KNOB attack exploits a Bluetooth design flaw, not a Bluetooth implementation flaw, and at the time of writing of (Antonioli, Tippenhauer, and Rasmussen 2019), the attack was effective on any standards-compliant Bluetooth firmware.

One of the problems that enables the KNOB attack is that the entropy negotiation is performed over an unencrypted and unauthenticated channel. This attack is possible under two different attacker models: the remote attacker and the firmware attacker. A remote attacker controls a device that can inject, block, and manipulate messages that are transmitted over the physical layer. A firmware attacker has access to a victim’s Bluetooth chip through backdoors or other compromising techniques (Antonioli, Tippenhauer, and Rasmussen 2019).

In the case of a remote attacker (Charlie), the attack happens as follows (details from (Antonioli, Tippenhauer, and Rasmussen 2019)):

  1. Alice authenticates that Bob possesses the correct link key.
  2. Alice requests to initiate Bluetooth link layer encryption.
  3. Bob accepts to initiate link layer encryption.
  4. Alice proposes 16 bytes of entropy, but Charlie intercepts this and substitutes 16 with 1.
  5. Bob accepts 1 byte.
  6. Charlie intercepts the acceptance message and sends a 1 byte proposal message to Alice instead.
  7. Alice accepts 1 byte.
  8. Charlie drops the acceptance message, so that it never reaches Bob.
  9. Alice and Bob compute the same combined key, which only has one byte of entropy.
  10. Charlie is able to brute force the key and decrypt all communications.

In the case of a firmware attacker, the attack is much less complicated because the attacker does not need to intercept messages. They can simply change a few bits in the entropy proposal message of one of the two parties to propose a single bit of entropy.

(Antonioli, Tippenhauer, and Rasmussen 2019) proposes a few mitigation strategies for this attack. One of them is to mandate an entropy floor beneath which proposals will be rejected, and to make that floor significantly higher than one byte. Another is to simply encrypt the key negotiation, which would be a great solution if it didn’t break backwards compatibility. Another solution mentioned in this paper is to provide the security at the application layer instead, but I dislike the fact that this was proposed as a solution because it basically amounts to saying that Bluetooth is fundamentally broken and that no one should trust it. (Which might be true, but we should still continue to try to fix it, right? If we never tried to fix broken things, nothing would ever improve…)

Memory Safety

A Primer on Memory and Memory Errors

Memory safety vulnerabilities have been a topic of concern for over 50 years. The first public discussion of the topic was in 1972, during the Computer Security Technology Planning Study Panel. Additionally, the Morris Worm shut down the Internet in 1988, showing the scale of harm possible through the exploitation of buffer overflow vulnerabilities (Veen et al. 2012). However, according to a technical report published by Google in 2024, memory errors still comprise approximately 70% of severe vulnerabilities in C/C++ codebases (Rebert and Kern 2024). The fact that the prevalence of this issue has remained high, even after 50 years of research, suggests that the underlying problem is both important and difficult to solve.

To understand memory errors, it is important to understand how memory works, how the C language interacts with memory, and the things that can go wrong when C programs misuse memory. Whenever a new process is created, the operating system assigns to it a unique virtual address space that contains the memory state of the running program (Arpaci-Dusseau and Arpaci-Dusseau 2023; Van Oorschot 2021). This is commonly split into five segments:

  1. the code segment, also known as the text segment, where program instructions live, which should be read-only memory;
  2. the heap segment, which contains dynamically allocated data, such as dynamic data structures and calls to malloc();
  3. the stack segment, which contains function call information such as local variables, function arguments, return addresses, and call frames;
  4. the data segment, which contains initialized global data;
  5. and lastly, the block storage segment (BSS), which contains uninitialized global data.

C and C++ allow the programmer to directly manipulate memory by using raw pointers, which are variables that store memory addresses. The value at the addressed location could be data or executable code (Oorschot 2023). One of the consequences of this is that attackers can exploit flaws in running C programs to overwrite program code, hijack program control flow (typically the goal here is to inject shellcode), corrupt data variables, or leak information (e.g. secrets such as cryptographic keys) (Szekeres et al. 2013). The most common attacks on memory involve interfering with the stack or heap segments.

Strings and array structures in C consist of pointers to contiguous zones of memory. In the case of strings, which C does not officially support, the end of the string is marked with a NUL byte. Many C library functions for working with strings are unsafe and do not do any bounds checking. The inconsistencies between how different library functions deal with strings and how different people think about strings leads to a variety of off-by-one errors. For example, the function strlen(src) returns the number of bytes in src, excluding the terminating NUL byte, whereas the function strcopy(dest, src) copies all bytes of the src string, plus one extra byte for the terminating NUL byte. If the programmer decides to check that the length of src is less than or equal to the size of the destination buffer without adding an extra byte as padding, this will result in corrupting an extra byte of memory (Oorschot 2023).

Two major categories of memory errors are spatial errors and temporal errors. Spatial safety errors involve accessing memory in an address or range that should not be allowed. The off-by-one memory error discussed above is an example of a spatial safety error, as are buffer overflows and wild pointer dereferencing errors. Temporal safety errors involve accessing memory in ranges that were allowed during an earlier point in the program execution, but that should no longer be accessed at the current point in program execution. These include errors related to using dangling pointers, which are pointers to objects in memory that has already been deallocated. Two examples are use-after-free errors, which involve dereferencing a dangling pointer, and double-free errors, which can either create new dangling pointers or corrupt a storage allocator’s internal data structures through freeing an object that has already been freed.

Memory Safety and Type Safety

According to (Oorschot 2023), there are four levels of memory safety, each of which aims to eliminate certain classes of memory errors:

  1. L1 safety, or fundamental memory safety, aims to eliminate spatial safety errors and temporal safety errors. Much of this can be supported through bounds checking and object validity checks.
  2. L2 saftey, or clean memory safety, aims to eliminate information leaks and undefined behaviour related to uninitialized variables.
  3. L3 safety aims to eliminate memory leaks.
  4. L4 safety aims to elimate security issues related to data races, which can occur when shared memory is read and written to concurrently.

These four categories can be used to assess the memory safety properties of different programming languages. A separate but adjacent topic is type safety. A language is type-safe if it can promise that its runtime operations will not silently go wrong (Oorschot 2023). Specifically, this means that:

  • the integrity of abstractions defined through the language is enforced at runtime (this includes data types, operations, object boundaries, allowed methods, etc.);
  • the language has a specification that fully defines program behaviour, thereby eliminating undefined behaviour;
  • the language guarantees that no undetected errors can occur at run-time.

Type-safe languages typically rely on both run-time and compile-time checks to prevent errors. C is not type-safe because it fails to check object boundaries, supports unions, and allows both casting between pointer types and casting between integers and pointers (Oorschot 2023).

The key idea here is that unsafe languages, such as C, place the burden of ensuring that things do not go wrong on the programmer, whereas safe languages take up the burden of ensuring program integrity themselves.

Safe Coding and Safe Abstractions

Since Google has a large codebase of C++ code, most of which contains severe vulnerabilities, engineers at the company have put a lot of effort into finding ways to eliminate memory errors. The methodology they came up with to achieve this is called Safe Coding, which considers unsafe coding constructs to be hazardous by default (i.e. regardless of whether or not they actually cause a vulnerability in the specified code) and aims to remove these unsafe constructs from the day-to-day work of developers. The main idea of this approach is that code must be safe by default, and unsafe code must be marked as unsafe and manually reviewed by experts before it can go into production. Additionally, unsafe code should be encapsulated by what Google refers to as “safe abstractions” (Rebert and Kern 2024).

In my opinion, the idea of “safe abstractions” is the most important idea in Google’s technical report. The idea is summarized by the following principle in the report: “Uses of unsafe constructs should be encapsulated in demonstrably-safe APIs” (Rebert and Kern 2024). (I did notice that they do not use the word “must” here, which to me suggests that they believe that there may be cases where this is either undesirable, impossible, or both. But maybe I just spend too much time reading RFCs.) The idea is that it should be possible to write modules for performing unsafe actions (e.g. heap memory allocation/deallocation) that are proven to be safe for any well-typed code that calls them. This idea seems to be borrowed from the Rust community, which has a similar idea of soundness: a module containing blocks of unsafe code (which must be explicitly marked as such in Rust) is sound if a program that combines that module with arbitrary safe Rust code cannot result in undefined behaviour (Rebert and Kern 2024).

Google first developed this approach to get rid of injection vulnerabilities in their web-facing code. According to their report, they went from finding dozens of XSS vulnerabilities in their web frontends (e.g. Gmail) on a yearly basis to having near-zero yearly XSS vulnerability findings after they refactored their code to use safe abstractions. These abstractions were things like type-safe wrappers around API calls, custom HTML types with attached safety contracts, and safe HTML templating systems (Rebert and Kern 2024).

Rust

Why Rust?

The Rust programming language was designed from the ground up to succeed where C and C++ failed. The appeal of systems-level languages like C or C++ is that they provide an expressive syntax for writing programs that interface with hardware and allow programmers to have fine-grained control over memory allocation. The flexibility provided by these languages is what allows programmers to optimize the speed or memory usage of their software, which is important when working on embedded systems (which are limited in memory) or on high-performance applications (which have a requirement for speed). While high level languages such as Python or Java offer strong memory safety, this comes at the cost of programmer control and significant runtime overhead (Jung et al. 2021).

Many problems with the C language come from its lack of type safety (it allows type punning and arbitrary type casting of pointers, for instance), its support of raw pointers and pointer arithmetic (i.e. the ability to directly modify variables that contain a plain memory address), and its support for write-capable aliases (i.e. multiple pointers to the same object that can each modify its value). Rust disallows these behaviours by default. Safe Rust avoids the first problem through use of a strong static type system, avoids the second problem through the use of smart pointers, and avoids the third problem through the use of an ownership and borrowing system that only allows one write-capable reference to have access to an object at any given time (Oorschot 2023). Many development teams for core software such as web browsers (e.g. Firefox, Chrome) or operating systems (e.g. Windows, Linux) are either writing new code in Rust or investigating the possibility of doing so as a result (Rivera et al. 2021).

The Rust language has become so popular in part because it manages to provide both safety guarantees and control over resources (such as memory) without incurring significant overhead. To accomplish this, Rust relies on a few techniques, such as the following:

  1. Enforcing a series of rules that are statically verified by the Rust type checker at compile time (Jung et al. 2021).
  2. Implementing static dynamic memory management through the use of automatically inserted code at runtime (Oorschot 2023).
  3. Making use of a conservative type system (i.e. a type checker that will never accept a program that is not well defined, but may reject some benign programs) instead than a complete one in order to avoid the overhead of more-or-less implementing a formal theorem prover in Rust (which would be required if Rust were to correctly classify all programs) (Jung et al. 2021; Rivera et al. 2021).

Of course, there is no free lunch, and all of this safety comes at the cost of some amount of functionality.6 To alleviate this problem, Rust provides an “unsafe” mode, where actions that would typically be prohibited by the type checker (such as use of raw pointers or multiple aliases) are explicitly allowed, but the programmer must take responsibility for the safety (or lack thereof) of the block of unsafe code. The idea is that programmers should be able to implement most functionality in safe Rust, which does not need to be scrutinized for safety (since the type checker will catch any errors), leaving only a few blocks of unsafe code to be manually scrutinized during code review. The Rust community also encourages programmers to encapsulate such code within “safe APIs” or “safe abstractions.” We discuss this idea further in Section 5.3.

Ownership, Borrowing, and Lifetimes

The main difference between Rust and most other programming languages is Rust’s adoption of an ownership type system, which places restrictions on the ability of aliases to mutate the objects to which they refer. While this idea is not new (it is known in the academic literature as an affine or substructural type system), Rust does introduce two new ideas to this system: the concept of borrowing and the concept of lifetimes.

In Rust, variables are immutable by default. Creation of a mutable variable requires an explicit declaration using the keyword mut, such as let mut a = 1. In this example, the use of the let keyword indicates that the value 1 should be bound to the variable a. Therefore, a now owns this instance of 1, meaning that it is the only entity allowed to alter the value of the object (Oorschot 2023).

Since a is an integer, any attempts to point another variable to the value of a will result in its value being copied to the new variable. However, if a were a string, and one were to write the statement let b = a, ownership of the string value would be moved to b, and the string would no longer be accessible through a (Oorschot 2023).

When a programmer wants to refer to some variable, the concept of borrowing comes into play. In Rust, the & operator is called the borrow operator, which allows shared read access to a variable. Multiple different & references to the same variable are allowed to coexist. In contrast, the &mut operator creates what is known as a mutable borrow. That is, an &mut reference allows write access to the variable, but does not allow the simultaneous existence of any other reference that can either read or write to the variable. In this case, ownership of the variable is temporarily moved to the reference (Oorschot 2023).

This strict ownership discipline allows the Rust compiler to infer the lifetime of a reference, which is the amount of time the reference has ownership of a value before it needs to give it back to the original variable. Since Rust has the ability to know the lifetimes of references in advance, and can also verify when variables go out of scope, the Rust compiler is able to determine when memory is no longer in use and deallocate it by inserting destructor calls, similar to what happens in C++ (Jung et al. 2021).

Safe Abstractions, Redux (+ a note on unsafe Rust)

In my previous reflection, I discussed how I believe that the concept of “safe abstractions” is the most important idea in Google’s technical report on memory safety (Rebert and Kern 2024). The idea is that while we can’t avoid using dangerous tools to implement functionality, once the functionality has been implemented, it should only be accessed in demonstrably safe ways. While this is a guideline for humans and not really something that can be enforced using technology, it is a valuable mindset to have in any technical organization because it is a practice that significantly reduces the number of errors made by developers. First of all, it encourages developers to use existing safe APIs whenever possible rather than reinventing the wheel and writing their own unsafe code. This indirectly promotes code reuse and code standardization. Additionally, if writing new unsafe code is required, it incentivizes packaging it nicely in a safe API so that other developers within the organization can use it. Ideally, as the number of available, vetted safe APIs increases, the amount of memory errors should decrease, and it should become easier to find the root cause of the errors that do slip through.

Having this cultural view of how unsafe code should be used also makes it significantly easier for an organization to set clear rules about the use of unsafe code within its codebase. For example, during class we had a discussion about how junior developers and interns might potentially be barred from writing unsafe code, unsafe code might be restricted to certain use cases, and there might be a more stringent process for review of unsafe code. Eric additionally mentioned that he has seen cases where use of unsafe code must explicitly be justified and documented via comments in the codebase.

However, advocating for safe abstractions isn’t solely useful as an intervention that can improve the security posture of development organizations – it’s also an important technical concept at the core of Rust language development. The running theme seems to be to protect the programmer from doing terrible things by wrapping functionality in abstractions.

The simplest example of this is the smart pointer.7 Rather than providing the programmer with the raw address to the first byte of an object (for example, a string), Rust creates a pointer to an internal structure it manages which contains metadata about the object, and it is this structure that contains a pointer to the object’s location in memory. The result is a safe implementation of strings that the user can simply use without worrying about trying to detect exactly where it begins and ends in memory. Yes, the abstraction has some amount of cost in terms of memory, but it is likely negligible.

Additionally, there is a lot of functionality we would expect from a programming language’s standard library that is impossible to implement in safe Rust. Examples include data structures such as doubly linked lists and constructs for writing concurrent programs such as mutexes (Jung et al. 2021). These are implemented in unsafe Rust, but then provided to the user through an interface that should guarantee to the end-programmer that as long as their code passes all type checks, the program should have no undefined behaviour.

The creators of Galeed (Rivera et al. 2021), a defence for hardening applications that mix Rust with unsafe languages, take the concept of a safe abstraction to the next level. One of the reasons why a programmer may want to use unsafe Rust is to interact with other languages using the Rust Foreign Function Interface (FFI). This allows large systems to incrementally replace pieces of their codebase with Rust code, which will then link to the rest of the (likely C or C++) code. Unfortunately, this allows attackers to potentially manipulate Rust-allocated memory through the flaws present in the code written in the unsafe language, since all parts of the program will share a process and associated memory space.

Part of the solution that Galeed offers to this program is a sanitization mechanism that involves passing “pseudo-pointers” to the unsafe language instead of pointers to Rust memory. Galeed keeps track of the mappings between the real pointers and the pseudo-pointers, and whenever the unsafe language attempts to dereference a Rust pointer, it is caught by an API that allows Rust to check whether the access request is valid and dereference the pointer itself. Again, this is an example of an abstraction that is meant to keep the programmer safe from producing memory errors.

Fuzzing

A Review of Fuzzing Tools and Methods (Fell)

Introduction

Fuzzing is a commonly used automated dynamic analysis technique for finding software vulnerabilities. This generally consists of repeatedly giving a program invalid input and monitoring it to see whether a bug that caused a program crash or hang is triggered. Fuzzing is desirable because each bug discovered through this process comes with a test case (or “witness”) that causes the bug and proves that it can actually be triggered. In practice, lots of serious, high profile memory corruption vulnerabilities are discovered through fuzzing.

Successful fuzzing requires some kind of instrumentation to be added to the target program. At a bare minimum, there should be some way of detecting when the program crashes and which test case caused the program to crash. More advanced instrumentation can be used to measure code coverage, detect subtle forms of memory corruption or errors that don’t cause crashes, or more. Instrumentation slows the target program down, so its important to consider what information is actually needed in order to navigate the tradeoff between speed and better instrumentation.

One of the goals of successfully fuzzing an application is to maximize code coverage in order to make sure as many bugs as possible are found. There are three approaches to measuring code coverage:

  • Line coverage keeps track of which individual lines of source code have been executed. This is a very, very crude measure. For example, it might mark an if statement as “executed” even if only one of the conditions has been tested.
  • Branch coverage keeps track of which branches have been taken for each conditional jump in the program.
  • Path coverage keeps track of which different paths have been taken through the program; that is, which sequences of lines and branches have been executed and in which order.

Most fuzzers are either file format fuzzers or protocol fuzzers. File format fuzzers are used for fuzzing any application that can take a file as input, whereas protocol fuzzers are used to fuzz clients and servers that communicate over a network.

Test case generation

Mutation fuzzing works by starting with a set of valid input samples and repeatedly modifying or corrupting them to produce new test cases. Mutation methods include things like randomly flipping bits, deleting sections of the test case, or splicing different test cases together. In this case, the fuzzer has no specific knowledge of the program being fuzzed or of the correct input syntax or formats. This is also known as dumb fuzzing.

Generation fuzzing creates test cases based on some kind of model that describes a valid input, such as a grammar or input format specification. This is sometimes referred to as smart fuzzing and generally leads to better code coverage and deeper testing of the program.

Evolutionary fuzzing creates new test cases based on the response of the target program to previous test cases. The idea is that test cases are supposed to evolve towards a common goal. Evolutionary fuzzing can be divided into three common approaches:

  • Coverage-based evolutionary fuzzing aims to evolve new test cases that result in new lines, branches, or paths being executed in the target program; test cases that exercise new code are prioritized over those that don’t.
  • Taint-based evolutionary fuzzing aims to evolve test cases that will execute specific known dangerous code paths, which have typically been found through a prior taint analysis. The goal is to generate test cases that will propagate user-input into specific known target functions in hope of causing edge cases that will lead to discovering vulnerabilities.
  • Symbolic-assisted evolutionary fuzzing aims to generate test cases that improve code coverage by leveraging a dynamic symbolic execution engine to make changes to the code. These will be changes that are known to result in the execution of specific uncovered paths in the target program.

The Art, Science, and Engineering of Fuzzing: A Survey (Manès et al.)

Fuzzing refers to the process of repeatedly running a program with generated inputs that may be syntactically or semantically malformed. Attackers regularly use fuzzing for exploit generation and penetration testing. Defenders also use fuzzing to try to discover vulnerabilities before the attackers do.

The term “fuzz” was originally coined by Barton P. Miller to refer to a program that “generates a stream of random inputs to be consumed by a target program”. However, this concept has significantly broadened over the years. This paper defines fuzzing as “the action of running a Program Under Test (PUT) with ‘fuzz inputs’”. A fuzz input is an input that the PUT may not be expecting. That is, it is an input that the PUT might process incorrectly, which could trigger a behaviour that is unintended by the PUT developer.

Definitions

Fuzzing is the execution of the PUT using input(s) sampled from an input space (the “fuzz input space”) that extends outside of the expected input space of the PUT. While it is common for the fuzz input space to contained the expected input space, this isn’t quite necessary; it’s enough for the fuzz input space to contain inputs that are not in the expected input space. In practice, fuzzing runs for multiple iterations and the sampling process isn’t necessarily randomized.

Fuzz-testing is a form of software-testing technique that uses fuzzing; in this paper, it is defined to be software testing using fuzzing techniques where the goal is to find security-related bugs. That is, fuzz-testing is the use of fuzzing to detect whether a PUT violates a security policy.

A fuzzer is a program that performs fuzz-testing on a PUT.

A fuzz campaign is a specific execution of a fuzzer on a PUT with a specific security policy.

A bug oracle is a program, perhaps as part of a fuzzer, that determines whether a given execution of a PUT violates a specific security policy.

A fuzz algorithm is an algorithm implemented by a specific fuzzer. Almost all such algorithms depend on some parameters other than the PUT or the path to the PUT. A fuzz configuration of a fuzz algorithm comprises the parameter values that control the fuzz algorithm.

A seed is a (usually well-structured) input to the PUT, which is used to generate test cases by modifying it. Fuzzers typically maintain a collection of seeds, and some fuzzers update the collection of seeds as the fuzz campaign progresses. This collection is called a seed pool.

A black-box fuzzer can only observe the input/output behaviours of the PUT, treating it like a black box. In software testing, black-box testing is also called IO-driven or data-driven test. Most traditional fuzzers fall into this category.

A white-box fuzzer generates test cases by analyzing the internals of the PUT and the information gathered while executing the PUT. This allows white-box fuzzers to systematically explore the state space of the PUT. These fuzzers typically have much higher overhead than black-box fuzzers.

A grey-box fuzzer is able to obtain some information about the internals of the PUT or its execution. It doesn’t reason about the full semantics of the PUT, but it might perform static analysis on the PUT or gather dynamic information about its executions (e.g. code coverage). Grey-box fuzzing relies on approximated, imperfect information in order to gain speed and test more inputs.

Both white and grey-box fuzzers can add instrumentation to a PUT in order to gather execution feedback or to fuzz the memory contents at runtime; the amount of information collected determines the colour of the fuzzer.

Static instrumentation occurs before the PUT is run and is performed at compile time on either source code or intermediate code. Dynamic instrumentation happens while the program is running. While it has higher overhead than static instrumentation, it also offers more flexibility in that it can easily instrument dynamically linked libraries.

References

Antonioli, Daniele, Nils Ole Tippenhauer, and Kasper Rasmussen. 2019. “The KNOB is broken: exploiting low entropy in the encryption key negotiation of bluetooth BR/EDR.” In Proceedings of the 28th USENIX Conference on Security Symposium, 1047–61.
Arpaci-Dusseau, Remzi H., and Andrea C. Arpaci-Dusseau. 2023. Operating Systems: Three Easy Pieces. 1.10 ed. Arpaci-Dusseau Books.
Feng, Haonan, Hui Li, Xuesong Pan, and Ziming Zhao. 2021. “A Formal Analysis of the FIDO UAF Protocol.” In Network and Distributed Systems Security (NDSS) Symposium 2021.
Hao, Feng, and Paul C. van Oorschot. 2022. “SoK: Password-Authenticated Key Exchange – Theory, Practice, Standardization and Real-World Lessons.” In Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, 697–711. ASIA CCS ’22.
Jablon, David. 1996. “Strong Password-Only Authenticated Key Exchange.” Computer Communications Review 26 (5): 5–26.
Jung, Ralf, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. 2021. “Safe systems programming in Rust.” Communications of the ACM 64 (4): 144–52.
Lang, Juan, Alexei Czeskis, Dirk Balfanz, Marius Schilder, and Sampath Srinivas. 2017. “Security Keys: Practical Cryptographic Second Factors for the Modern Web.” In Financial Cryptography and Data Security, 422–40.
Oorschot, Paul C. van. 2023. “Memory errors and memory safety in C, Java and Rust.” Lecture notes.
Popov, Andrei, Magnus Nyström, Dirk Balfanz, and Jeff Hodges. 2018. “The Token Binding Protocol Version 1.0.” Request for Comments. RFC 8471; RFC Editor. https://www.rfc-editor.org/info/rfc8471.
Rebert, Alex, and Christoph Kern. 2024. “Secure by Design: Google’s Perspective on Memory Safety.” Google Security Engineering.
Rivera, Elijah, Samuel Mergendahl, Howard Shrobe, Hamed Okhravi, and Nathan Burow. 2021. “Keeping Safe Rust Safe with Galeed.” In Proceedings of the 37th Annual Computer Security Applications Conference, 824–36.
Szekeres, Laszlo, Mathias Payer, Tao Wei, and Dawn Song. 2013. “SoK: Eternal War in Memory.” In Proceedings of the 2013 IEEE Symposium on Security and Privacy, 48–62.
Van Oorschot, Paul C. 2021. Computer Security and the Internet: Tools and Jewels from Malware to Bitcoin. Springer.
van Oorschot, Paul C. 2026. “Chapter 14: Cryptographic systems in practice.” In Textbook of Applied Cryptography. Draft book manuscript. https://sites.google.com/view/textbook-appliedcrypto/home.
Veen, Victor van der, Nitish dutt-Sharma, Lorenzo Cavallaro, and Herbert Bos. 2012. “Memory Errors: The Past, the Present, and the Future.” In Research in Attacks, Intrusions, and Defenses, 86–106.
Wu, Jianliang, Ruoyu Wu, Dongyan Xu, Dave Jing Tian, and Antonio Bianchi. 2024. “SoK: The Long Journey of Exploiting and Defending the Legacy of King Harald Bluetooth.” In 2024 IEEE Symposium on Security and Privacy (SP), 2847–2280.

Footnotes

  1. The key is “hashed” here for general security hygiene, since typically we do not want to use the generated key directly, but instead use a key derivation function (KDF) on the generated output. The “\(h\)” here could really be replaced by any KDF.↩︎

  2. The reason why Bob sends both numbers here is so that Alice can verify that she is talking to the same person she sent her earlier message to and not to some new person sending her a number… typically, in cryptographic protocols we want to chain messages in this way (or in a similar way).↩︎

  3. Question: If they didn’t build \(K\) using random info from both sides, would this still work???↩︎

  4. NTS: review what password salting actually is.↩︎

  5. We colloquially say “paired” devices when we really mean “bonded” devices, which makes the terminology mildly confusing.↩︎

  6. It also comes at the cost of a higher learning curve for new programmers, but honestly, considering that it is very easy to write vulnerable C code if you don’t know what you’re doing (and my guess is that most people don’t), and considering that finding the source of memory errors in large codebases (let alone fixing them) is a massive nightmare, maybe it is a good idea for the programming language to explicitly force its users to know what they are doing. ↩︎

  7. Yes, I do realize that Rust didn’t invent this one, but I am trying to make a point here.↩︎