Last update: Fri Feb 21 14:34:39 EST 2025

Introduction

Computer security is about keeping computers, their programs, and the data they manage “safe.” Specifically, this means safeguarding three areas: confidentiality, integrity, and availability. These three are known as the CIA Triad (no relation to the Central Intelligence Agency).

Confidentiality

Confidentiality ensures that information is protected from unauthorized access, allowing only authorized users to view or modify it. Privacy gives individuals control over their personal data, focusing on how it is collected and shared. Privacy is a reason for confidentiality. Someone being able to access a protected file containing your medical records without proper access rights is a violation of confidentiality. Anonymity hides a person’s identity, even if their actions are visible. Secrecy involves the deliberate concealment of information for security or strategic reasons.

A data breach occurs when unauthorized individuals access sensitive data due to hacking, malware, or poor security controls. This can expose personal, financial, or corporate information, leading to identity theft or financial loss. Data exfiltration is the unauthorized transfer of stolen data from a system, often as part of a breach. Attackers use malware, phishing, or compromised credentials to extract information for fraud or sale.

Integrity

Integrity refers to the trustworthiness of a system. This means that everything is as you expect it to be: users are not imposters and processes are running correctly.

• Data integrity means that the data in a system has not been corrupted.

• Origin integrity means that the person or system sending a message or creating a file truly is that person and not an imposter. Authentication techniques can address this issue.

• Recipient integrity means that the person or system receiving a message truly is that person and not an imposter.

• System integrity means that the entire computing system is working properly; that it has not been damaged or subverted. Processes are running the way they are supposed to.

Maintaining integrity means not just defending against intruders that want to modify a program or masquerade as others but also protecting the system against against accidental damage, such as from user or programmer errors.

Availability

Availability means that the system is available for use and performs properly. A denial of service (DoS) attack may not steal data or damage any files but may cause a system to become unresponsive.

Security is difficult. Software is incredibly complex. Large systems may comprise tens or hundreds of millions of lines of code. Systems as a whole are also complex. We may have a mix of cloud and local resources, third-party libraries, and multiple administrators. If security was easy, we would not have massive security breaches year after year. Microsoft wouldn’t have monthly security updates. There are no magic solutions … but there is a lot that can be done to mitigate the risk of attacks and their resultant damage.

We saw that computer security addressed three areas of concern. The design of security systems also has three goals.

Prevention

Prevention means preventing attackers from violating established security policies. It means that we can implement mechanisms into our hardware, operating systems, and application software that users cannot override – either maliciously or accidentally. Examples of prevention include enforcing access control rules for files and authenticating users with passwords.

Detection

Detection detects and reports security attacks. It is particularly important when prevention mechanisms fail. It is useful because it can identify weaknesses with certain prevention mechanisms. Even if prevention mechanisms are successful, detection mechanisms are useful to let you know that attempted attacks are taking place. An example of detection is notifying an administrator that a new user has been added to the system. Another example is being notified that there have been several consecutive unsuccessful attempts to log in.

Recovery

If a system is compromised, we need to stop the attack and repair any damage to ensure that the system can continue to run correctly and the integrity of data is preserved. Recovery includes forensics, the study of identifying what happened and what was damaged so we can fix it. An example of recovery is restoration from backups.

Security engineering involves implementing mechanisms and defining policies to protect a system’s components. Like other engineering disciplines, it requires trade-offs between security and usability. The most secure system would be completely isolated, housed in a shielded room with restricted access, and running fully audited software—but such a setup is impractical for everyday computing. Users need connectivity, mobility, and interaction with the world, which introduces risks. Even in a highly secure environment, concerns remain: monitoring access, verifying software integrity, and preventing insider threats or coercion. Effective security design requires understanding potential attackers and their threats, balancing protection with functionality.

Risk analysis evaluates the likelihood and impact of an attack, identifying who may be affected and the worst possible consequences. A threat model visually maps data flows, highlighting points where information enters, exits, or moves between subsystems. This helps prioritize security efforts by identifying the most vulnerable areas in a system.

Secure systems consist of policies and mechanisms working together to enforce security. A policy defines what is or isn’t allowed, such as requiring users to log in with a password. Mechanisms are the technical implementations that enforce these policies. For example, a login system that prompts for credentials, verifies them against stored records, and grants access only if authentication succeeds ensures that the policy is followed. Effective security requires both well-defined policies and robust mechanisms to enforce them.

Key Cybersecurity Concepts

Understanding how attacks occur requires familiarity with key terms that describe weaknesses, threats, and attack methods. The following definitions explain fundamental concepts related to system security and cyber threats.

Vulnerability

A vulnerability is a weakness in a system, software, or network that can be exploited by an attacker. Vulnerabilities can arise from software bugs, misconfigurations, or weak security practices.

Example: An outdated web server with an unpatched security flaw that allows unauthorized access.

Exploit

An exploit is a technique, tool, or piece of code designed to take advantage of a vulnerability. Exploits can be automated scripts, malware, or sophisticated attack methods used to gain unauthorized access or control over a system.

Example: A hacker uses a known buffer overflow exploit to crash a system and execute malicious code.

Attack

An attack is a deliberate attempt to compromise a system’s security, often with the goal of stealing data, disrupting services, or gaining unauthorized control. Attacks can be carried out manually by skilled hackers or through automated tools.

Example: A phishing attack that tricks users into revealing their login credentials.

Attack Vector

An attack vector is the method or pathway an attacker uses to deliver an exploit and gain access to a system. Attack vectors can be technical (such as software vulnerabilities) or social (such as phishing).

Example: A malicious email attachment that installs malware when opened.

Attack Surface

An attack surface represents the total number of possible entry points that an attacker can target. A larger attack surface increases the risk of security breaches, as more vulnerabilities may be exposed.

Example: A company’s attack surface includes its public website, employee email accounts, remote access systems, and IoT devices.

Threat

A threat is any potential danger that could exploit a vulnerability to cause harm. Threats can originate from malicious actors, software bugs, or natural disasters that disrupt security.

Example: A ransomware threat that encrypts critical files and demands payment for their release.

Threat Actor

A threat actor is the entity responsible for carrying out an attack. Threat actors include hackers, cybercriminal groups, nation-state attackers, and even insiders with malicious intent.

Example: The Lazarus Group, a North Korean cyber-espionage team responsible for various high-profile attacks.

Threat categories

Threats fall into four broad categories:

Disclosure: Unauthorized access to data, which covers exposure, interception, interference, and intrusion. This includes stealing data, improperly making data available to others, or snooping on the flow of data.

Deception: Accepting false data as true. This includes masquerading, which is posing as an authorized entity; substitution or insertion of includes the injection of false data or modification of existing data; repudiation, where someone falsely denies receiving or originating data.

Disruption: Some change that interrupts or prevents the correct operation of the system. This can include maliciously changing the logic of a program, a human error that disables a system, an electrical outage, or a failure in the system due to a bug. It can also refer to any obstruction that hinders the functioning of the system.

Usurpation: Unauthorized control of some part of a system. This includes theft of service as well as any misuse of the system such as tampering or actions that result in the violation of system privileges.

Network threats

The Internet increases opportunities for attackers. The core protocols of the Internet were designed with decentralization, openness, and interoperability in mind rather than security. Anyone can join the Internet and send messages … and untrustworthy entities can provide routing services. It allows bad actors to hide and to attack from a distance. It also allows attackers to amass asymmetric force: harnessing more resources to attack than the victim has for defense. Even small groups of attackers are capable of mounting Distributed Denial of Service (DDoS) attacks that can overwhelm large companies or government agencies by assembling a botnet of tens or hundreds of thousands of compromised computers.

Threat actors

Adversaries can range from lone hackers to industrial spies, terrorists, and intelligence agencies. We can consider two dimensions: skill and focus.

Regarding focus, attacks are either opportunistic or targeted.

Opportunistic attacks are those where the attacker is not out to get you specifically but casts a wide net, trying many systems in the hope of finding a few that have a particular vulnerability that can be exploited. Targeted attacks are those where the attacker targets you specifically.

In the dimension of skill, the term script kiddies is used to refer to attackers who lack the skills to craft their own exploits but download malware toolkits to try to find vulnerabilities (e.g., systems with poor or default passwords, hackable cameras). They can still cause substantial damage.

Advanced persistent threats (APT) are highly-skilled, well-funded, and determined (hence, persistent) attackers. They can craft their own exploits, pay millions of dollars for others, and may carry out complex, multi-stage attacks.

Trusted computing base

The Trusted Computing Base (TCB) consists of the hardware, software, and firmware that enforce a system’s security policies. If the TCB is compromised, you lose assurance that any part of the system remains secure. For example, if an attacker modifies the operating system to ignore file access permissions, applications running on the system can no longer be trusted to enforce security rules. A compromised TCB can allow unauthorized access, privilege escalation, or persistent backdoors, making security controls ineffective.

The computing supply chain is crucial to TCB security, as modern systems rely on globally sourced and third-party components – both hardware and software. A compromised supply chain—whether through malicious firmware, counterfeit hardware, or backdoored software—can introduce vulnerabilities before a system is even deployed. Examples include the SolarWinds breach and hardware-level implants, which demonstrated how attackers can infiltrate systems at a fundamental level. If an attacker compromises the supply chain, even secure software running on top of the system cannot be trusted. To prevent such risks, organizations implement secure sourcing, vendor audits, firmware integrity checks, and hardware attestation to ensure the trustworthiness of the computing infrastructure.

Cryptography

Cryptography deals with encrypting plaintext using a cipher, also known as an encryption algorithm, to create ciphertext, which is unintelligible to anyone unless they can decrypt the ciphertext. It is a tool that helps build protocols that address:

Authentication

Showing that the user really is that user.

Integrity:

Validating that the message has not been modified.

Nonrepudiation:

Binding the origin of a message to a user so that she cannot deny creating it.

Confidentiality:

Hiding the contents of a message.

A secret cipher is one where the workings of the cipher must be kept secret. There is no reliance on any key and the secrecy of the cipher is crucial to the value of the algorithm. This has obvious flaws: people in the know leaking the secret, designers coming up with a poor algorithm, and reverse engineering. Schneier’s Law (not a real law), named after Bruce Schneier, a cryptographer and security professional, suggests that anyone can invent a cipher that they will not be able to break, but that doesn’t mean it’s a good one.

For any serious use of encryption, we use well-tested, non-secret algorithms that rely on secret keys. A key is a parameter to a cipher that alters the resulting ciphertext. Knowledge of the key is needed to decrypt the ciphertext. Kerckhoffs’s Principle states that a cryptosystem should be secure even if everything about the system, except the key, is public knowledge. We expect algorithms to be publicly known and all security to rest entirely on the secrecy of the key.

A symmetric encryption algorithm uses the same secret key for encryption and decryption.

An alternative to symmetric ciphers are asymmetric ciphers. An asymmetric, or public key cipher uses two related keys. Data encrypted with one key can only be decrypted with the other key.

Properties of good ciphers

These are the key properties we expect for a cipher to be strong:

1. For a cipher to be considered good, ciphertext should be indistinguishable from random values.
2. Given ciphertext, there should be no way to extract the original plaintext or the key that was used to create it except by of enumerating over all possible keys. This is called a brute-force attack.
3. The keys used for encryption should be large enough that a brute force attack is not feasible. Each additional bit in a key doubles the number of possible keys and hence doubles the search time.

Stating that the ciphertext should be indistinguishable from random values implies high entropy. Shannon entropy measures the randomness in a system. It quantifies the unpredictability of cryptographic keys and messages, with higher entropy indicating more randomness. Low entropy would allow an attacker to find patterns or some correlation to the original content.

We expect these properties for a cipher to be useful:

1. The secrecy of the cipher should be entirely in the key (Kerckoffs’s principle) – we expect knowledge of the algorithm to be public.

2. Encryption and decryption should be efficient: we want to encourage the use of secure cryptography where it is needed and not have people avoid it because it slows down data access.

3. Keys and algorithms should be as simple as possible and operate on any data:

   • There shouldn’t be restrictions on the values of keys, the data that could be encrypted, or how to do the encryption
   • Restrictions on keys make searches easier and will require longer keys.
   • Complex algorithms will increase the likelihood of implementation errors.
   • Restrictions on what can be encrypted will encourage people to not use the algorithm.

4. The size of the ciphertext should be the same size as the plaintext.

   • You don’t want your effective bandwidth cut in half because the ciphertext is 2x the size of plaintext.
   • However, sometimes we might need to pad the data but that’s a small number of bytes regardless of the input size.

5. The algorithm has been extensively analyzed

   • We don’t want the latest – we want an algorithm that has been studied carefully for years by many experts.

In addition to formulating the measurement of entropy, Claude Shannon posited that a strong cipher should, ideally, have the confusion and diffusion as goals in its operation.

Confusion means that there is no direct correlation between a bit of the key and the resulting ciphertext. Every bit of ciphertext will be impacted by multiple bits of the key. An attacker will not be able to find a connection between a bit of the key and a bit of the ciphertext. This is important in not giving the cryptanalyst hints on what certain bits of the key might be and thus limit the set of possible keys. Confusion hides the relationship between the key and ciphertext

Diffusion is the property where the plaintext information is spread throughout the cipher so that a change in one bit of plaintext will change, on average, half of the bits in the ciphertext. Diffusion tries to make the relationship between the plaintext and ciphertext as complicated as possible.

Classic cryptography

Monoalphabetic substitution ciphers

The earliest form of cryptography was the monoalphabetic substitution cipher. In this cipher, each character of plaintext is substituted with a character of ciphertext based on a substitution alphabet (a lookup table). The simplest of these is the Caesar cipher, known as a shift cipher, in which a plaintext character is replaced with a character that is n positions away in the alphabet. The key is the simply the the shift value: the number n. Substitution ciphers are vulnerable to frequency analysis attacks, in which an analyst analyzes letter frequencies in ciphertext and substitutes characters with those that occur with the same frequency in natural language text (e.g., if “x” occurs 12% of the time, it’s likely to really be an “e” since “e” occurs in English text approximately 12% of the time while “x” occurs only 0.1% of the time).

Polyalphabetic substitution ciphers

Polyalphabetic substitution ciphers were designed to increase resiliency against frequency analysis attacks. Instead of using a single plaintext to ciphertext mapping for the entire message, the substitution alphabet may change periodically. Leon Battista Alberti is credited with creating the first polyalphabetic substitution cipher. In the Alberti cipher (essentially a secret decoder ring), the substitution alphabet changes every n characters as the ring is rotated one position every n characters.

The Vigenère cipher is a grid of Caesar ciphers that uses a repeating key. A repeating key is a key that repeats itself for as long as the message. Each character of the key determines which Caesar cipher (which row of the grid) will be used for the next character of plaintext. The position of the plaintext character identifies the column of the grid. These algorithms are still vulnerable to frequency analysis attacks but require substantially more plaintext since one needs to deduce the key length (or the frequency at which the substitution alphabet changes) and then effectively decode multiple monoalphabetic substitution ciphers.

One-time Pads

The one-time pad is the only provably secure cipher. It uses a random key that is as long as the plaintext. Each character of plaintext is permuted by a character of ciphertext (e.g., add the characters modulo the size of the alphabet or, in the case of binary data, exclusive-or the next byte of the text with the next byte of the key). The reason this cryptosystem is not particularly useful is because the key has to be as long as the message, so transporting the key securely becomes a problem. The challenge of sending a message securely is now replaced with the challenge of sending the key securely. The position in the key (pad) must by synchronized at all times. Error recovery from unsynchronized keys is not possible. Finally, for the cipher to be secure, a key must be composed of truly random characters, not ones derived by an algorithmic pseudorandom number generator. The key can never be reused.

The one-time pad provides perfect secrecy (not to be confused with forward secrecy, also called perfect forward secrecy, which will be discussed later), which means that the ciphertext conveys no information about the content of the plaintext. It has been proved that perfect secrecy can be achieved only if there are as many possible keys as the plaintext, meaning the key has to be as long as the message. Watch this video for an explanation of perfect secrecy.

Stream ciphers

A stream cipher simulates a one-time pad by using a keystream generator to create a set of key bytes that is as long as the message. A keystream generator is a pseudorandom number generator that is seeded, or initialized, with a key that drives the output of all the bytes that the generator spits out. The keystream generator is fully deterministic: the same key will produce the same stream of output bytes each time. Because of this, receivers only need to have the key to be able to decipher a message. However, because the keystream generator does not generate true random numbers, the stream cipher is not a true substitute for a one-time pad. Its strength rests on the strength of the key. A keystream generator will, at some point, will reach an internal state that is identical to some previous internal state and produce output that is a repetition of previous output. This also limits the security of a stream cipher but the repetition may not occur for a long time, so stream ciphers can still be useful for many purposes.

Rotor machines

A rotor machine is an electromechanical device that implements a polyalphabetic substitution cipher. It uses a set of disks (rotors), each of which implements a substitution cipher. The rotors rotate with each character in the style of an odometer: after a complete rotation of one rotor, the next rotor advances one position. Each successive character gets a new substitution alphabet applied to it. The multi-rotor mechanism allows for a huge number of substitution alphabets to be employed before they start repeating when the rotors all reach their starting position. The number of alphabets is c^r, where c is the number of characters in the alphabet and r is the number of rotors.

Transposition ciphers

Instead of substituting one character of plaintext for a character of ciphertext, a transposition cipher scrambles the position of the plaintext characters. Decryption is the knowledge of how to unscramble them.

A scytale, also known as a staff cipher, is an ancient implementation of a transposition cipher where text written along a strip of paper is wrapped around a rod and the resulting sequences of text are read horizontally. This is equivalent to entering characters in a two-dimensional matrix horizontally and reading them vertically. Because the number of characters might not be a multiple of the width of the matrix, extra characters might need to be added at the end. This is called padding and is essential for block ciphers, which encrypt chunks of data at a time.

Block ciphers

Most modern ciphers are block ciphers, meaning that they encrypt a chunk of bits, or block, of plaintext at a time. The same key is used to encrypt each successive block of plaintext.

AES and DES are two popular symmetric block ciphers. Symmetric block ciphers are usually implemented as iterative ciphers. The encryption of each block of plaintext iterates over several rounds. Each round uses a subkey, which is a key generated from the main key via a specific set of bit replications, inversions, and transpositions. The subkey is also known as a round key since it is applied to only one round, or iteration. This subkey determines what happens to the block of plaintext as it goes through a substitution-permutation (SP) network. The SP network, guided by the subkey, flips some bits by doing a substitution, which is a table lookup of an input bit pattern to get an output bit pattern and a permutation, which is a scrambling of bits in a specific order. The output bytes are fed into the next round, which applies a substitution-permutation step onto a different subkey. The process continues for several rounds (16 rounds for DES, 10–14 rounds for AES). and the resulting bytes are the ciphertext for the input block.

The iteration through multiple SP steps creates confusion and diffusion. Confusion means that it is extremely difficult to find any correlation between a bit of the ciphertext with any part of the key or the plaintext. A core component of block ciphers is the s-box, which converts n input bits to m output bits, usually via a table lookup. The purpose of the s-box is to add confusion by altering the relationship between the input and output bits.

Diffusion means that any changes to the plaintext are distributed (diffused) throughout the ciphertext so that, on average, half of the bits of the ciphertext would change if even one bit of plaintext is changed.

Feistel ciphers

A Feistel cipher is a form of block cipher that uses a variation of the SP network where a block plaintext is split into two parts. The substitution-permutation round is applied to only one part. That output is then XORed with the other part and the two halves are swapped. At each round, half of the input block remains unchanged. DES, the Data Encryption Standard, is an example of a Feistel cipher. AES, the Advanced Encryption Standard, is not.

DES

Two popular symmetric block ciphers are DES, the Data Encryption Standard, and AES, the Advanced Encryption Standard. DES was adopted as a federal standard in 1976 and is a block cipher based on the Feistel cipher that encrypts 64-bit blocks using a 56-bit key.

DES has been shown to have some minor weaknesses against cryptanalysis. Key can be recovered using 2⁴⁷ chosen plaintexts or 2⁴³ known plaintexts. Note that this is not a practical amount of data to get for a real attack. The real weakness of DES is not the algorithm but but its 56-bit key. An exhaustive search requires 2⁵⁵ iterations on average (we assume that, on average, the plaintext is recovered halfway through the search). This was a lot for computers in the 1970s but is not much of a challenge for today’s dedicated hardware or distributed efforts.

Triple-DES

Triple-DES (3DES) solves the key size problem of DES and allows DES to use keys up to 168 bits. It does this by applying three layers of encryption:

1. C' = Encrypt M with key K₁
2. C'' = Decrypt C' with key K₂
3. C = Encrypt C'' with key K₃

If K₁, K₂, and K₃ are identical, we have the original DES algorithm since the decryption in the second step cancels out the encryption in the first step. If K₁ and K₃ are the same, we effectively have a 112-bit key and if all three keys are different, we have a 168-bit key.

Cryptanalysis is not effective with 3DES: the three layers of encryption use 48 rounds instead of 16 making it infeasible to reconstruct the substitutions and permutations that take place. A 168-bit key is too long for a brute-force attack. However, DES is relatively slow compared with other symmetric ciphers, such as AES. It was designed with hardware encryption in mind. 3DES is, of course, three times slower than DES.

AES

AES, the Advanced Encryption Standard, was designed as a successor to DES and became a federal government standard in 2002. It uses a larger block size than DES: 128 bits versus DES’s 64 bits and supports larger key sizes: 128, 192, and 256 bits. Even 128 bits is complex enough to prevent brute-force searches.

No significant academic attacks have been found thus far beyond brute force search. AES is also typically 5–10 times faster in software than 3DES.

Block cipher modes

Electronic Code Book (ECB)

When data is encrypted with a block cipher, it is broken into blocks and each block is encrypted separately. This leads to two problems.

1. If different encrypted messages contain the same substrings and use the same key, an intruder can deduce that it is the same data.

2. Secondly, a malicious party can delete, add, or replace blocks (perhaps with blocks that were captured from previous messages).

This basic form of a block cipher is called an electronic code book (ECB). Think of the code book as a database of encrypted content. You can look up a block of plaintext and find the corresponding ciphertext. This is not feasible to implement for arbitrary messages but refers to the historic use of codebooks to convert plaintext messages to ciphertext.

Cipher Block Chaining (CBC)

Cipher block chaining (CBC) addresses these problems. Every block of data is still encrypted with the same key. However, prior to being encrypted, the data block is exclusive-ORed with the previous block of ciphertext. The receiver does the process in reverse: a block of received data is decrypted and then exclusive-ored with the previously-received block of ciphertext to obtain the original data. The very first block is exclusive-ored with a random initialization vector, which must be transmitted to the remote side.

Note that CBC does not make the encryption more secure; it simply makes the result of each block of data dependent on all previous previous blocks. Because of the random initialization vector, even identical content would appear different in ciphertext. An attacker would not be able to tell if any two blocks of ciphertext refer to identical blocks of plaintext. Because of the chaining, even identical blocks in the same ciphertext will appear vastly different. Moreover, because of this blocks cannot be meaningfully inserted, swapped, or deleted in the message stream without the decryption failing (producing random-looking garbage).

Counter mode (CTR)

Counter mode (CTR) also addresses these problems but in a different way. The ciphertext of each block is a function of its position in the message. Encryption starts with a message counter. The counter is incremented for each block of input. Only the counter is encrypted. The resulting ciphertext is then exclusive-ORed with the corresponding block of plaintext, producing a block of message ciphertext. To decrypt, the receiver does the same thing and needs to know the starting value of the counter as well as the key.

An advantage of CTR mode is that each block has no dependance on other blocks and encryption on multiple blocks can be done in parallel.

Cryptanalysis

The goal of cryptanalysis is break codes. Most often, it is to identify some non-random behavior of an algorithm that will give the analyst an advantage over an exhaustive search of the key space.

Differential cryptanalysis seeks to identify non-random behavior by examining how changes in plaintext input affect changes in the output ciphertext. It tries to find whether certain bit patterns are unlikely for certain keys or whether the change in plaintext results in likely changes in the output.

Linear cryptanalysis tries to create equations that attempt to predict the relationships between ciphertext, plaintext, and the key. An equation will never be equivalent to a cipher but any correlation of bit patterns give the analyst an advantage.

Neither of these methods will break a code directly but may help find keys or data that are more likely are that are unlikely. It reduces the keys that need to be searched.

Public key cryptography

Public key algorithm, also known as asymmetric ciphers, use one key for encryption and another key for decryption. One of these keys is kept private (known only to the creator) and is known as the private key. The corresponding key is generally made visible to others and is known as the public key.

Anything encrypted with the private key can only be decrypted with the public key. This is the basis for digital signatures. Anything that is encrypted with a public key can be encrypted only with the corresponding private key. This is the basis for authentication and covert communication.

Public and private keys are related but, given one of the keys, there is no feasible way of computing the other. They are based on trapdoor functions, which are one-way functions: there is no known way to compute the inverse unless you have extra data: the other key.

RSA public key cryptography

The RSA algorithm is the most popular algorithm for asymmetric cryptography. Its security is based on the difficulty of finding the factors of the product of two large prime numbers. Unlike symmetric ciphers, RSA encryption is a matter of performing arithmetic on large numbers. It is also a block cipher and plaintext is converted to ciphertext by the formula:

c = m^e mod n

Where m is a block of plaintext, e is the encryption key, and n is an agreed-upon modulus that is the product of two primes. To decrypt the ciphertext, you need the decryption key, d:

m = c^d mod n

Given the ciphertext c, e, and n, there is no efficient way to compute the inverse to obtain m. Should an attacker find a way to factor n into its two prime factors, however, the attacker would be able to reconstruct the encryption and decryption keys, e and d.

Elliptic curve cryptography (ECC)

Elliptic curve cryptography (ECC) is a more recent public key algorithm that is an alternative to RSA. It is based on finding points along a prescribed elliptic curve, which is an equation of the form:

y² = x³ + ax + b

Contrary to its name, elliptic curves have nothing to do with ellipses or conic sections and look like bumpy lines. With elliptic curves, multiplying a point on a given elliptic curve by a number will produce another point on the curve. However, given that result, it is difficult to find what number was used. The security in ECC rests not our inability to factor numbers but our inability to perform discrete logarithms in a finite field.

The RSA algorithm is still the most widely used public key algorithm, but ECC has some advantages:

• ECC can use far shorter keys for the same degree of security. Security comparable to 256 bit AES encryption requires a 512-bit ECC key but a 15,360-bit RSA key

• ECC requires less CPU consumption and uses less memory than RSA. It is faster for encryption (including signature generation) than RSA but slower for decryption.

• Generating ECC keys is faster than RSA (but much slower than AES, where a key is just a random number).

On the downside, ECC is more complex to implement and decryption is slower than with RSA. As a standard, ECC was also tainted because the NSA inserted weaknesses into the ECC random number generator that effectively created a backdoor for decrypting content. This has been remedied and ECC is generally considered the preferred choice over RSA for most applications.

If you are interested, see here for a somewhat easy-to-understand tutorial on ECC.

Quantum computing

Quantum computers are a markedly different form computer. Conventional computers store and process information that is represented in bits, with each bit having a distinct value of 0 or 1. Quantum computers use the principles of quantum mechanics, which include superposition and entanglement. Instead of working with bits, quantum computers operate on qubits, which can hold values of “0” and “1” simultaneously via superposiion. The superpositions of qubits can be entangled with other objects so that their final outcomes will be mathematically related. A single operation can be carried out on 2ⁿ values simultaneously, where n is the number of qubits in the computer.

While practical quantum computers don’t exist, it’s predicted that certain problems may be solved exponentially faster than with conventional computers. Shor’s algorithm, for instance, will be able to find the prime factors of large integers and compute discrete logarithms far more efficiently than is currently possible.

So far, quantum computers are very much in their infancy, and it is not clear when – or if – large-scale quantum computers that are capable of solving useful problems will be built. It is unlikely that they will be built in the next several years but we expect that they will be built eventually. Shor’s algorithm will be able to crack public-key based systems such as RSA, Elliptic Curve Cryptography, and Diffie-Hellman key exchange. In 2016, the NSA called for a migration to “post-quantum cryptographic algorithms” and has currently narrowed down the submissions to 26 candidates. The goal is to find useful trapdoor functions that do not rely on multiplying large primes, computing exponents, any other mechanisms that can be attacked by quantum computation. If you are interested in these, you can read the NSA’s report.

Symmetric cryptosystems, such as AES, are not particularly vulnerable to quantum computing since they rely on moving and flipping bits rather than applying mathematical functions on the data. The best potential attacks come via Grover’s algorithm, which yields only a quadratic rather than an exponential speedup in key searches. This will reduce the effective strength of a key by a factor of two. For instance, a 128-bit key will have the strength of a 64-bit key on a conventional computer. It is easy enough to use a sufficiently long key (256-bit AES keys are currently recommended) so that quantum computing poses no threat to symmetric algorithms.

Secure communication

Symmetric cryptography

Communicating securely with symmetric cryptography is easy. All communicating parties must share the same secret key. Plaintext is encrypted with the secret key to create ciphertext and then transmitted or stored. It can be decrypted by anyone who has the secret key.

Asymmetric cryptography

Communicating securely with asymmetric cryptography is a bit different. Anything encrypted with one key can be decrypted only by the other related key. For Alice to encrypt a message for Bob, she encrypts it with Bob’s public key. Only Bob has the corresponding key that can decrypt the message: Bob’s private key.

Hybrid cryptography

Asymmetric cryptography alleviates the problem of transmitting a key over an unsecure channel. However, it is considerably slower than symmetric cryptography. AES, for example, is approximately 1,500 times faster for decryption than RSA and 40 times faster for encryption. AES is also much faster than ECC. Key generation is also far slower with RSA or ECC than it is with symmetric algorithms, where the key is just a random number rather than a set of carefully chosen numbers with specific properties. Moreover, certain keys with RSA may be weaker than others.

Because of these factors, RSA and ECC are never used to encrypt large chunks of information. Instead, it is common to use hybrid cryptography, where a public key algorithm is used to encrypt a randomly-generated key that will encrypt the message with a symmetric algorithm. This randomly-generated key is called a session key, since it is generally used for one communication session and then discarded.

Key Exchange

The biggest problem with symmetric cryptography is key distribution. For Alice and Bob to communicate, they must share a secret key that no adversaries can get. However, Alice cannot send the key to Bob since it would be visible to adversaries. She cannot encrypt it because Alice and Bob do not share a key yet.

Diffie-Hellman key exchange

The Diffie-Hellman key exchange algorithm allows two parties to establish a common key without disclosing any information that would allow any other party to compute the same key. Each party generates a private key and a public key. Despite their name, these are not encryption keys; they are just numbers. Diffie-Hellman does not implement public key cryptography. Alice can compute a common key using her private key and Bob’s public key. Bob can compute the same common key by using his private key and Alice’s public key.

Diffie-Hellman uses the one-way function a^bmod c. Its one-wayness is due to our inability to compute the inverse: a discrete logarithm. Anyone may see Alice and Bob’s public keys but will be unable to compute their common key. Although Diffie-Hellman is not a public key encryption algorithm, it behaves like one in the sense that it allows us to exchange keys without having to use a trusted third party.

Key exchange using public key cryptography

With public key cryptography, there generally isn’t a need for key exchange. As long as both sides can get each other’s public keys from a trusted source, they can encrypt messages using those keys. However, we rarely use public key cryptography for large messages. It can, however, be used to transmit a session key. This use of public key cryptography to transmit a session key that will be used to apply symmetric cryptography to messages is called hybrid cryptography. For Alice to send a key to Bob:

1. Alice generates a random session key.
2. She encrypts it with Bob’s public key & sends it to Bob.
3. Bob decrypts the message using his private key and now has the session key.

Bob is the only one who has Bob’s private key to be able to decrypt that message and extract the session key. A problem with this is that anybody can do this. Charles can generate a random session key, encrypt it with Bob’s public key, and send it to Bob. For Bob to be convinced that it came from Alice, she can encrypt it with her private key (this is signing the message).

1. Alice generates a random session key.
2. She signs it by encrypting the key with her private key.
3. She encrypts the result with Bob’s public key & sends it to Bob.
4. Bob decrypts the message using his private key.
5. Bob decrypts the resulting message with Alice’s public key and gets the session key.

If anybody other than Alice created the message, the result that Bob gets by decrypting it with Alice’s public key will not result in a valid key for anyone. We can enhance the protocol by using a standalone signature (encrypted hash) so Bob can identify a valid key from a bogus one.

Forward secrecy and key types

If an attacker steals Bob’s private key, they will be able to decrypt old session keys. This is because, at the start of every communication session with Bob, the session key is typically encrypted using Bob’s public key. Once the attacker has Bob’s private key, they can retroactively decrypt these session keys and access past communications.

Forward Secrecy

Forward secrecy, also known as perfect forward secrecy (PFS), ensures that the compromise of a long-term key (e.g., Bob’s private key) does not compromise past session keys. This means there is no secret that, if stolen, allows an attacker to decrypt multiple past messages.

Forward secrecy is valuable for communication sessions but not for stored encrypted documents. In communications, the goal is to prevent an attacker from retroactively decrypting old conversations, even if they later obtain a user’s private key. However, encrypted documents must remain decryptable by the legitimate user, which requires reliance on a long-term key.

Diffie-Hellman and Forward Secrecy

Diffie-Hellman key exchange enables forward secrecy by allowing Alice and Bob to generate temporary (ephemeral) key pairs for each session. The process works as follows:

1. Alice and Bob each generate a new public-private key pair and exchange their public keys.
2. Using their own private key and the received public key, they compute a shared secret.
3. This shared secret is used to encrypt their communication for that session.
4. For the next session, they generate new key pairs and derive a new shared secret.

Since a new set of keys is used for every session, even if an attacker later compromises Bob’s private key, they cannot decrypt past messages because those sessions used different keys.

In contrast, encrypting a session key with a long-term key (such as Bob’s public key in an RSA-based system) does not provide forward secrecy. If an attacker gains access to Bob’s private key, they can decrypt all past session keys and decrypt old communications.

Types of Cryptographic Keys

Long-Term Keys

These keys persist across multiple sessions and are used for authentication, identity verification, and encrypting stored data. Examples include RSA or ECC private keys used to create digital signatures and digital certificates.

• Ephemeral Keys: These are temporary, single-use keys generated for a session and discarded afterward. Diffie-Hellman and Elliptic Curve Diffie-Hellman are examples used to achieve forward secrecy.
• Session Keys: These are symmetric encryption keys used for a single communication session. They are often derived from ephemeral key exchanges and are used to encrypt messages between parties for the duration of the session.

Ephemeral keys are discarded as soon as a session key is established. Session keys can be discarded when the communication session ends.

Diffie-Hellman is particularly useful for achieving forward secrecy because it allows efficient on-the-fly key pair generation. While RSA or ECC keys could theoretically be used for ephemeral key exchange, key generation for RSA and ECC is computationally expensive. As a result, RSA and ECC keys are typically used as long-term keys (e.g., for authentication and digital signatures) rather than for generating new session keys dynamically.

Message Integrity

One-way and Trapdoor Functions

A one-way function is easy to compute but infeasible to invert. Given an output, finding the original input is computationally impractical. These functions are the foundation of cryptographic hash functions (e.g., SHA-256), which ensure data integrity, password security, and digital signatures.

A trapdoor function is a one-way function with a secret trapdoor that allows efficient inversion. These functions are fundamental to public-key cryptography, including Diffie-Hellman, RSA, and ECC, enabling secure encryption, decryption, and digital signatures.

One-way functions secure hash-based applications, while trapdoor functions enable asymmetric encryption.

Hash functions

A particularly important class of one-way functions is the cryptographic hash function. These functions produce a fixed-size output, regardless of the input size, making them invaluable in various applications. In general computing, hash functions are often used to build hash tables, enabling O(1) key lookups.

However, cryptographic hash functions differ from standard hash functions in that they generate significantly longer outputs—typically 224, 256, 384, or 512 bits. Strong cryptographic hash functions, such as SHA-2 and SHA-3 families, must exhibit several essential properties:

1. Fixed-Length Output – Like all hash functions, cryptographic hash functions take an input of arbitrary length and produce a fixed-size output.

2. Deterministic – They always produce the same hash for the same input, ensuring consistency

3. Pre-image Resistance (Hiding) – Given a hash value H, it should be computationally infeasible to determine the original input M such that H = hash(M).

4. Avalanche Effect – The output of a hash function should not give any information about any part of the input. Small changes in the input should result in significantly different hash outputs, preventing any predictable relationship between input and output. For example, changing a byte in the message should result in a completely different hash result, with no ability to predict which bits would flip. The avalanche effect is the rsult of good diffusion.

5. Collision Resistance – While hash collisions must theoretically exist (due to the pigeonhole principle), it should be infeasible to find two distinct inputs that produce the same hash. Likewise (see item 4, above), modifying a message should alter the hash in an unpredictable way.

6. Efficient – Hash functions should be computationally efficient, allowing rapid generation of hashes for applications like message integrity verification without excessive overhead.

Cryptographic hash functions form the foundation of message authentication codes (MACs) and digital signatures, playing a crucial role in ensuring data integrity and authentication.

Due to their properties, we can be highly confident that even the smallest modification to a message will produce a completely different hash. However, the “holy grail” for an attacker is finding a way to create a different, but useful, message that hashes to the same value as a legitimate one. Such an attack could allow message substitution, potentially leading to serious consequences—such as redirecting a financial transaction.

Finding a collision for a specific, known message (pre-image attack) is significantly harder than finding any two different messages that hash to the same value (collision attack). The birthday paradox explains why: the probability of finding any collision is approximately proportional to the square root of the total number of possible hashes. As a result, the security strength of a hash function against brute-force collision attacks is roughly half the number of bits in the hash output. For example, a 256-bit hash function provides approximately 128-bit security against such attacks.

Common cryptographic hash functions include:

• SHA-1 (160-bit output) – now considered weak due to known vulnerabilities.
• SHA-2 (e.g., SHA-256, SHA-512) – widely used and considered secure.
• SHA-3 (e.g., SHA3–256, SHA3–512) – designed as a secure alternative to SHA-2.

Message Authentication Codes (MACs)

A cryptographic hash function helps ensure message integrity by acting as a checksum, allowing detection of any modifications to a message. If a message is altered, its hash will change. However, standard hashes alone do not provide authentication—an attacker could modify both the message and its hash without detection. To address this, we use a cryptographic hash that incorporates a secret key, creating a message authentication code (MAC). Only those who possess the key can generate or verify a valid MAC.

There are two main types of MACs: hash-based and block cipher-based.

Hash-Based MAC (HMAC):
An HMAC transforms a cryptographic hash function (e.g., SHA-256) into a MAC by incorporating a secret key. The message and key are processed together, ensuring that only someone with the correct key can generate or verify the MAC. Without knowledge of the key, an attacker cannot forge a valid MAC, even if they can see previous message-MAC pairs.

Block Cipher-Based MAC (CBC-MAC):
Cipher Block Chaining (CBC) mode ensures that each encrypted block depends on all previous blocks. CBC-MAC leverages this by initializing encryption with a zero initialization vector (IV), encrypting the message in CBC mode, and using only the final encrypted block as the MAC. Any modification to the message propagates through the encryption process, altering the final block and invalidating the MAC.

While CBC-MAC produces a fixed-length result similar to a hash function, it relies on symmetric encryption rather than a hash function for security. Unlike HMAC, its security depends on the underlying block cipher and requires careful handling to prevent certain attacks (e.g., misuse with variable-length messages).

Digital signatures

Message authentication codes (MACs) rely on a shared secret key, meaning that anyone with the key can generate or verify a MAC. However, this does not guarantee that the original author of the message was the one who signed it—any key holder can modify and re-sign the message.

Digital signatures provide stronger guarantees than MACs:

1. Only the original signer can generate a valid signature, but anyone can verify it.
2. Signatures are message-specific—copying a signature to a different message invalidates it.
3. Forgery is infeasible, even if an attacker has seen numerous signed messages.

A digital signature system consists of three fundamental operations:

1. Key generation: {private_key, verification_key } := gen_keys(keysize)
   Generates a key pair: a private key for signing and a public verification key for validation.
2. Signing: signature := sign(message, private_key)
   Creates a digital signature using the private key.
3. Validation: isvalid := verify(message, signature, verification_key)
   Checks whether a signature is valid using the public verification key.

Signing hashes instead of messages

Since cryptographic hashes are designed to be collision-resistant, it is common practice to sign the hash of a message rather than the message itself. This approach ensures that:

• The signature is small and fixed in size, regardless of message length.
• The signature is efficient to compute and verify.
• It integrates seamlessly into data structures that need them.
• It creates minimal transmission or storage overhead.

There are several commonly used digital signature algorithms:

DSA, the Digital Signature Algorithm

The current NIST standard, based on the difficulty of computing discrete logarithms.

ECDSA, Elliptic Curve Digital Signature Algorithm

A variant of DSA that uses elliptic curve cryptography (ECC), providing equivalent security with smaller key sizes than traditional DSA.

Public key cryptographic algorithms

Uses RSA encryption principles to sign message hashes. Unlike DSA and ECDSA, which are dedicated signature schemes, RSA is a general-purpose public-key cryptosystem that can be used for both encryption and signing.

All these algorithms use public and private key pairs.

We previously saw how public-key cryptography allows encryption:

• Alice encrypts a message with Bob’s public key, ensuring that only Bob can decrypt it with his private key.

Digital signatures work in a similar way, but in reverse:

• Alice “encrypts” (signs) a message hash using her private key.
• Anyone with Alice’s public key can decrypt and verify the signature, confirming that the message was signed by Alice.

Instead of encrypting the entire message, most digital signature algorithms apply a hash function first, then sign the hash using a trapdoor function (such as modular exponentiation in RSA or ECC operations in ECDSA). This ensures that only the signer can generate a valid signature, but anyone can verify it using the public key.

Unlike MACs, digital signatures provide non-repudiation—proof that a specific entity signed a message. Alice cannot deny creating a signature, as only her private key could have produced it.

Both MACs and digital signatures provide message integrity, ensuring that the message has not been altered. However, digital signatures go further by allowing anyone to verify authenticity without requiring a shared secret key.

Covert and authenticated messaging

We ignored the encryption of a message in the preceding discussion; our interest was assuring integrity. However, there are times when we may want to keep the message secret and validate that it has not been modified. Doing this involves sending a signature of the message along with the encrypted message.

A basic way for Alice to send a signed and encrypted message to Bob is for her to use hybrid cryptography and:

1. Create a signature of the message. This is a hash of the message encrypted with her private key.
2. Create a session key for encrypting the message. This is a throw-away key that will not be needed beyond the communication session.
3. Encrypt the message using the session key. She will use a fast symmetric algorithm to encrypt this message.
4. Package up the session key for Bob: she encrypts it with Bob’s public key. Since only Bob has the corresponding private key, only Bob will be able to decrypt the session key.
5. She sends Bob: the encrypted message, encrypted session key, and signature.

Anonymous identities

A signature verification key (e.g., a public key) can be treated as an identity. You possess the corresponding private key and therefore only you can create valid signatures that can be verified with the public key. This identity is anonymous; it is just a bunch of bits. There is nothing that identifies you as the holder of the key. You can simply assert your identity by being the sole person who can generate valid signatures.

Since you can generate an arbitrary number of key pairs, you can create a new identity at any time and create as many different identities as you want. When you no longer need an identity, you can discard your private key for that corresponding public key.

Identity binding: digital certificates

While public keys provide a mechanism for asserting integrity via digital signatures, they are themselves anonymous. We’ve discussed a scenario where Alice uses Bob’s public key but never explained how she can assert that the key really belongs to Bob and was not planted by an adversary. Some form of identity binding of the public key must be implemented for you to know that you really have my public key instead of someone else’s. How does Alice really know that she has Bob’s public key?

X.509 digital certificates provide a way to do this. A certificate is a data structure that contains user information (called a distinguished name) and the user’s public key. This data structure also contains a signature of the certification authority. The signature is created by taking a hash of the rest of the data in the structure and encrypting it with the private key of the certification authority. The certification authority (CA) is responsible for setting policies of how they validate the identity of the person who presents the public key for encapsulation in a certificate.

To validate a certificate, you would hash all the certificate data except for the signature. Then you would decrypt the signature using the public key of the issuer. If the two values match, then you know that the certificate data has not been modified since it has been signed. The challenge is how to get the public key of the issuer. Public keys are stored in certificates, so the issuer would have a certificate containing its public key. This certificate can be signed by yet another issuer. This kind of process is called certificate chaining. For example, Alice can have a certificate issued by the Rutgers CS Department. The Rutgers CS Department’s certificate may be issued by Rutgers University. Rutgers University’s certificate could be issued by the State of New Jersey Certification Authority, and so on. At the very top level, we will have a certificate that is not signed by any higher-level certification authority. A certification authority that is not underneath any other CA is called a root CA. In practice, this type of chaining is rarely used. More commonly, there are hundreds of autonomous certification authorities acting as root CAs that issue certificates to companies, users, and services. The certificates for many of the trusted root CAs are preloaded into operating systems or, in some cases, browsers. See here for Microsoft’s trusted root certificate participants and here for Apple’s trusted root certificates.

Every certificate has an expiration time (often a year or more in the future). This provides some assurance that even if there is a concerted attack to find a corresponding private key to the public key in the certificate, such a key will not be found until long after the certificate expires. There might be cases where a private key might be leaked or the owner may no longer be trustworthy (for example, an employee leaves a company). In this case, a certificate can be revoked. Each CA publishes a certificate revocation list, or CRL, containing lists of certificates that they have previously issued that should no longer be considered valid. To prevent spoofing the CRL, the list is, of course, signed by the CA. Each certificate contains information on where to obtain revocation information.

The challenge with CRLs is that not everyone may check the certificate revocation list in a timely manner and some systems may accept a certificate not knowing that it was revoked. Some systems, particularly embedded systems, may not even be configured to handle CRLs.

Code signing - protecting code integrity

We have seen how hash functions are used for message integrity through message authentication codes (MACs) (which rely on a shared key) and digital signatures (which use public and private keys). The same cryptographic principles apply to code signing, a process that ensures software has not been modified since it was created by the developer.

Code signing protects against tampered or malicious software. It allows operating systems to verify software authenticity, detect unauthorized modifications, and prevent execution of compromised applications—all without requiring users to manually inspect their downloads.

Signing software allows it to be downloaded from untrusted sources or distributed over untrusted channels while still ensuring it has not been altered. It also enables the detection of malware that may have modified software after installation.

Modern operating systems such as Microsoft Windows, Apple macOS, iOS, and Android extensively use code signing to validate software authenticity and integrity.

Code signing process

1. Key Pair Generation – The software publisher generates a public/private key pair.
2. Certificate Issuance – The public key is included in a digital certificate, typically issued by a Certificate Authority (CA) that verifies the publisher’s identity.
3. Hash Generation – The publisher computes a cryptographic hash of the software.
4. Signature Creation – The hash is encrypted with the private key, producing a digital signature.
5. Attaching the Signature – The signature and the certificate are embedded in the software package to allow verification.

Code verification process

1. Certificate Validation – Before installation, the system checks the certificate’s validity by ensuring it was issued by a trusted CA and has not been revoked or expired.
2. Hash Computation – The system generates a new hash from the downloaded software.
3. Signature Decryption – The digital signature is decrypted using the publisher’s public key, revealing the original hash.
4. Integrity Check – The system compares the decrypted hash with the newly computed hash. If they match, the software is authentic and unmodified. If they do not match, this indicates tampering or corruption, and the software may be rejected as untrusted.

Some signed software, particularly system-critical applications, also supports per-page hashing. In demand paging, an operating system loads only the necessary portions (pages) of a program into memory as needed rather than loading the entire executable at once. Instead of verifying a large file before execution, per-page hashing allows each 4KB page to be individually validated upon loading. This ensures integrity at runtime, helping detect in-memory modifications or tampering even after installation.

Authentication

Authentication is the process of verifying that a user’s claimed identity is legitimate.

It is important to distinguish authentication from identification:

• Identification is the act of claiming an identity (e.g., entering a username or presenting an ID).
• Authentication is the process of proving that the claimed identity is valid (e.g., by providing a correct password, fingerprint, or security token).

Authorization is a separate process that determines what actions or resources an authenticated user is permitted to access.

Authentication factors

The three factors of authentication are:

1. something you have – a physical object, such as a key, smart card, or security token.
2. something you know – a secret, such as a password, PIN, or security answer.
3. something you are – a biological trait, such as a fingerprint, retina scan, or facial recognition.

Using multi-factor authentication (MFA) enhances security by requiring authentication from two or more different factors. This ensures that even if one factor is compromised, unauthorized access remains difficult.

Importantly, MFA requires factors from different categories. Using two passwords or two security questions does not qualify as multi-factor authentication because both fall under “Something You Know.”

Combined authentication and key exchange protocols

Key exchange and authentication using a trusted third party

When two parties want to communicate securely using symmetric encryption, they need to share a common key. There are three primary ways to achieve this:

1. Pre-shared Key Exchange – The key is exchanged outside the network using a secure method, such as reading it over the phone or physically delivering it on a flash drive.
2. Public Key Cryptography – The key is securely exchanged using asymmetric encryption (e.g., RSA or Diffie-Hellman).
3. Trusted Third Party (TTP) Key Exchange – A centralized authority manages and distributes keys to authenticated users.

A trusted third party (TTP) is a system that securely holds each participant’s secret key. In this model, Alice and the TTP (Trent) share Alice’s secret key. Likewise, Bob and Trent share Bob’s secret key.

The simplest way of using a trusted third party is to ask it to come up with a session key and send it to the parties that wish to communicate. For example:

1. Alice requests a session key from Trent to communicate with Bob. This request is encrypted with Alice’s secret key, ensuring that Trent knows it came from Alice.
2. Trent generates a random session key and encrypts it into two messages: One copy is encrypted with Alice’s secret key. Another copy is encrypted with Bob’s secret key.
3. Trent sends both encrypted versions to Alice. Alice decrypts her copy to obtain the session key. She then forwards the encrypted session key meant for Bob to Bob.
4. Bob decrypts his copy using his secret key. Now both Alice and Bob share the session key for secure communication.

This simple scheme is vulnerable to replay attacks. An eavesdropper, Eve, can record messages from Alice to Bob and replay them at a later time. Eve might not be able to decode the messages but she can confuse Bob by sending him seemingly valid encrypted messages.

The second problem is that Alice sends Trent an encrypted session key but Trent has no idea that Alice is requesting to communicate with him. While Trent authenticated Alice (simply by being able to decrypt her request) and authorized her to talk with Bob (by generating the session key), that information has not been conveyed to Bob. This problem can be solved by having Trent package information about the other party within the encrypted messages that contain the session key.

Needham-Schroeder: nonces

The Needham-Schroeder protocol improves the basic key exchange protocol by adding nonces to messages. A nonce is simply a random string – a random bunch of bits that are used to prevent replay attacks.

Step 1. Alice Requests a Session Key from Trent

Alice sends a request to Trent (the TTP), asking to establish communication with Bob. She includes a random nonce (N_A) to ensure freshness of the message. Note that this request does not need to be encrypted

Step 2. Trent Responds with a Secure Session Key

Trent generates a random session key (K_AB) for Alice and Bob and sends Alice the following, encrypted with Alice’s secret key:

• Alice’s ID
• Bob’s ID
• Alice’s nonce, N_A
• the session key, K_AB
• a ticket: a message encrypted for Bob that contains Alice’s ID and the same session key (K_AB)

This entire message from Trent is encrypted with Alice’s secret key.

Step 3. Alice Validates the Message and Forwards the Ticket to Bob

Alice decrypts Trent’s response using her secret key and verifies that the nonce matches her original request, ensuring it’s not a replay attack.

She then forwards the ticket (which is encrypted for Bob and unreadable to her) to Bob.

Step 4: Bob Validates the Ticket and Extracts the Session Key

Bob decrypts the ticket using his secret key and learns:

• The session key (K_AB).
• That he is communicating with Alice, as her ID is in the ticket.
• That the session key was generated by Trent, since only Trent knows Bob’s secret key and could have created the ticket.

Step 5: Bob Authenticates Alice

Bob now needs to confirm that Alice actually has the session key. He does this by sending Alice a challenge-response authentication:

1. Bob generates a random nonce (N_B), encrypts it with the session key (K_AB), and sends it to Alice.
2. Alice decrypts the nonce, subtracts 1, then encrypts the result with K_AB and sends it back to Bob.
3. Bob verifies that the returned value is (N_B - 1), proving that Alice knows the session key.

At this point, both Alice and Bob have authenticated each other and share a secure session key for further communication.

Denning-Sacco Modification: Using Timestamps to Prevent Key Replay Attacks

A major flaw in the Needham-Schroeder protocol is its vulnerability to key replay attacks. This occurs when an attacker, Eve, captures a valid ticket. (the message from Trent that is encrypted for Bob and contains the session key) and replays it later to impersonate Alice.

How the Attack Works:

Step 1. Alice initiates a communication session with Bob by sending a ticket encrypted for Bob.

Step 2. The ticket contains:

• Alice’s ID
• Session key (K_AB)

Step 3. If Eve manages to capture and later decrypt the session key (perhaps through cryptanalysis or a key compromise), she can replay the ticket to Bob.

Step 4. Since Bob has no way to distinguish between an old ticket and a new one, he accepts the session key and proceeds with authentication.

Step 5. Eve, now in possession of K_AB, successfully authenticates as Alice and communicates with Bob, who mistakenly believes he is talking to Alice.

To mitigate this attack, Denning & Sacco proposed a simple but effective fix: include a timestamp inside the ticket when it is generated by Trent (the trusted third party):

• When Trent creates the ticket that Alice will later forward to Bob, he encrypts it using Bob’s secret key and includes:

• Alice’s ID

• Session key (K_AB)

• A timestamp (T_A)

• When Bob receives the ticket, he checks the timestamp. If the timestamp is too old (e.g., outside an acceptable time window), Bob rejects the ticket, assuming it is a replay attack. If the timestamp is recent, Bob proceeds with authentication.

This fix works because old tickets cannot be reused – a previously captured ticket after the time window has expired.

Otway-Rees Protocol: Session IDs Instead of Timestamps

One challenge with the Denning-Sacco modification is that it relies on synchronized clocks across all entities. If Bob’s clock is significantly out of sync with Trent’s, he might:

• Falsely accept an old ticket, leading to a replay attack.
• Falsely reject a valid ticket, disrupting communication.

An attacker (Eve) could manipulate time synchronization by:

• Injecting fake NTP (Network Time Protocol) responses to mislead Bob’s system clock.
• Generating fake GPS signals to deceive devices relying on GPS for time synchronization.

Since time synchronization itself introduces vulnerabilities, the Otway-Rees protocol replaces timestamps with session IDs to prevent replay attacks without relying on clocks.

The steps in this protocol are:

Step 1: Alice Initiates a Communication Request

Alice sends a message to Bob that includes:

• A unique session ID (S) to track this exchange.
• Both Alice’s and Bob’s IDs (to establish who is communicating).
• A message encrypted with Alice’s secret key, containing:
  • Alice’s and Bob’s IDs.
  • A random nonce, r₁.
  • The session ID (S) (ensuring it matches throughout the exchange).

Step 2: Bob Forwards the Request to Trent (Trusted Third Party)

Bob receives Alice’s message and sends Trent:

• Alice’s original message.
• A message encrypted with Bob’s secret key, containing:
  • Alice’s and Bob’s IDs** (confirming he agrees to communicate with Alice).
  • A random nonce, r₂.
  • The same session ID (S).

Now, Trent sees the same session ID in both encrypted messages, proving:

• Alice initiated the request to talk to Bob.
• Bob agrees to talk to Alice.
• It really is Bob because Bob was able to create a message containing the session ID and encrypt it with his secret key.

Step 3: Trent Generates and Distributes the Session Key

Once Trent verifies the request, he:

• Generates a random session key (K_AB) for Alice and Bob.
• Encrypts K_AB along with Alice’s nonce, r₁, for Alice using Alice’s secret key.
• Encrypts K_AB along with Bob’s nonce, r₂, for Bob using Bob’s secret key.
• Sends both encrypted session keys to Bob, along with the session ID (S).

Bob then forwards Alice’s encrypted key to her.

The Otway-Rees protocol is secure because:

• It prevents replay attacks: Even if an attacker replays an old message, the session ID must match in all encrypted exchanges.
• Does not require synchronized clocks: Eliminates the risk of time-based attacks.
• Ensures mutual agreement: Trent confirms that both Alice and Bob want to communicate.
• Incorporates nonces: Trent’s response includes nonces to prevent an attacker from injecting old session keys (even if they are cracked). The use of nonces ensures that there is no replay attack on Trent’s response even if an attacker sends a message to Bob with a new session ID and old encrypted session keys (that were cracked by the attacker).

Kerberos

Kerberos is a trusted authentication, authorization, and key exchange protocol that uses symmetric cryptography. It is based on the Needham-Schroeder protocol, incorporating the Denning-Sacco modification (timestamps) to prevent replay attacks.

When Alice wants to communicate securely with Bob (who may be another user or a service), she must first request access from Kerberos. If authorized, Kerberos provides her with two encrypted messages:

1. A message encrypted with Alice’s secret key, containing:
   • A session key (K_AB) for secure communication with Bob.
2. A ticket encrypted with Bob’s secret key (which Alice cannot read), containing:
   • The same session key (K_AB).

Alice forwards the ticket to Bob. When Bob decrypts it using his secret key, he:

• Confirms that Kerberos issued the ticket since only Kerberos knows his secret key.
• Obtains K_AB, which he shares with Alice.

Now that both Alice and Bob have the session key, they can securely communicate by encrypting messages using K_AB.

Preventing Replay Attacks: Mutual Authentication

To ensure that Alice is legitimate, she must prove she can extract the session key sent by Kerberos. She does this by:

1. Generating a new timestamp (T_A).
2. Encrypting T_A with K_AB and sending it to Bob.

Bob verifies that the timestamp is recent and then authenticates himself to Alice by:

1. Incrementing T_A by 1.
2. Encrypting the modified value with K_AB and sending it back to Alice.

Since only Bob could have decrypted T_A and modified it, Alice knows she is talking to the real Bob.

Avoiding frequent password prompts

Without optimization, Alice would need to enter her password every time she requests a service, since her secret key is needed to decrypt the session key for each request. Caching her key in a file would be a security risk.

To solve this, Kerberos is divided into two components:

1. Authentication Server (AS):

• Handles initial user authentication.
• Issues a session key for Alice to communicate with the Ticket Granting Server (TGS).
• This session key can be cached, avoiding repeated password entry.

1. Ticket Granting Server (TGS):

• Handles requests for services (e.g., accessing Bob’s server).
• Issues a new session key for Alice’s communication with the specific service.
• Provides a ticket, which Alice presents to the service instead of entering credentials again.

Authentication Protocols

In the next family of protocols, we will look at mechanisms that focus only on authentication and not key exchange.

Public key authentication

Public key authentication is based on the use of nonces (random values) to verify that a party possesses a specific private key—without ever revealing that key. This process is conceptually similar to the challenge-response mechanism used in the Needham-Schroeder protocol.

If Alice wants to authenticate Bob, she must verify that Bob possesses his private key. Since private keys are never shared, Alice uses a challenge-response mechanism:

1. Alice generates a nonce (a random value) and sends it to Bob as a challenge.
2. Bob encrypts the nonce using his private key and sends the result back to Alice.
3. Alice decrypts Bob’s response using Bob’s public key:
   • If the decrypted value matches the original nonce, Alice confirms that Bob must have the corresponding private key.
   • Since only Bob should possess his private key, Alice can trust that she is communicating with the real Bob.

For mutual authentication, Bob must also verify Alice’s identity. Instead of each party individually initiating a challenge-response cycle, they can combine their authentication steps into a single exchange, making the process more efficient:

1. Alice and Bob generate their own nonces (N_A and N_B).
2. Alice sends Bob her nonce (N_A).
3. Bob encrypts N_A using his private key and also sends Alice his own nonce (N_B).
4. Alice decrypts Bob’s response using Bob’s public key. If the decrypted value matches N_A, Alice confirms Bob’s identity.
5. Alice encrypts N_B with her private key and sends it back to Bob.
6. Bob decrypts Alice’s response using Alice’s public key. If the decrypted value matches N_B, Bob confirms Alice’s identity.

At this point, both Alice and Bob have authenticated each other, completing mutual authentication in just one additional round-trip message instead of two separate exchanges.

Note that you can create variations of the protocol. For instance, Alice can send Bob her nonce encrypted with Bob’s public key so that only he can decode it.

Regardless of the variation, the idea is for one party to prove that they can use their private key (which nobody else has) to encode or decode something that the other party sends them.

Incorporating X.509 Certificates for Identity Verification

While public key authentication proves that an entity possesses a private key, it does not inherently verify the entity’s identity. An attacker could generate their own key pair and falsely claim to be Bob. To address this, X.509 certificates bind public keys to specific identities.

An X.509 certificate, issued by a trusted Certificate Authority (CA), contains:

• The entity’s public key.
• The entity’s identity (such as a domain name, email, or organizational details).
• The CA’s digital signature, proving the certificate’s authenticity.

Before using Bob’s public key, Alice can first request and verify Bob’s X.509 certificate, ensuring:

• The certificate is issued by a trusted CA.
• The certificate has not expired or been revoked.
• The entity information in the certificate matches Bob’s claimed identity.

If Bob’s certificate is valid, Alice can confidently use Bob’s public key, mitigating the risk of impersonation. This approach is widely used in TLS (Transport Layer Security) to secure web communications, where websites present certificates to allow users to verify their authenticity.

Password Authentication Protocol (PAP)

The most basic form of authentication relies on reusable passwords, known as the Password Authentication Protocol (PAP).

1. The system prompts the user to identify themselves (e.g., entering a login name).
2. The user enters their password.
3. If the password matches the one stored for that login, authentication is successful.

While simple, PAP is vulnerable to attacks such as password guessing, brute force, and credential leaks.

While simple, PAP is vulnerable to attacks such as password guessing, brute force, and credential leaks.

Password guessing defenses

To avoid having an adversary carry out a password-guessing attack, we need to make it not feasible to try a large number of passwords. A common approach is to rate-limit guesses. When the system detects an incorrect password, it will wait several seconds before allowing the user to try again. Linux, for example, waits about three seconds. After five bad guesses, it terminates and restarts the login process.

Another approach is to completely disallow password guessing after a certain number of failed attempts by locking the account. This is common for some web-based services, such as banks. However, the system has now been made vulnerable to a denial-of-service (DoS) attack. An attacker may not be able to take your money but may inconvenience you by disallowing you to access it as well.

Hashed passwords

A major weakness of the Password Authentication Protocol (PAP) is that if an attacker gains access to the password file, they obtain all user credentials. To mitigate this risk, systems store hashed passwords instead of plaintext passwords.

Instead of storing actual passwords, the system stores their cryptographic hashes, taking advantage of the one-way property of hash functions:

1. When a user enters a password, the system computes: hash(password).
2. The system compares the computed hash with the stored hash.
3. If they match, authentication is successful.

Since hashes cannot be reversed, an attacker who steals the password file cannot directly recover the original passwords—they must resort to brute-force or dictionary attacks:

1. Brute-Force Attacks: An attacker systematically tries every possible password until they find one that matches a stored hash.

2. Dictionary Attacks: Instead of trying all possible combinations, an attacker tests common passwords (e.g., dictionary words, known passwords, common letter-number substitutions).

3. Precomputed Hash Attacks (Rainbow Tables): Attackers can precompute hashes of millions of common passwords and store them in a lookup table. If a system-stored hash matches one in the table, the attacker immediately knows the corresponding password. This makes cracking many passwords at once much faster.

Salting to Prevent Precomputed Attacks

To prevent attackers from using precomputed hashes, systems introduce a random value called a “salt” when hashing passwords.

Before hashing, the system concatenates the password with a unique salt: hash(salt + password). The salt is stored in plaintext alongside the hashed password in the database (the password file). Even if two users have the same password, their hashes will be different due to different salts.

Why Salt is Effective:

• Defeats rainbow table attacks – Attackers would need to precompute an entire hash table for each possible salt value, making the approach infeasible.
• Prevents identical hashes for identical passwords – Even if multiple users have the same password, their stored hashes will be different, so an attacker cannot tell whether users share the same password.
• Forces attackers to crack passwords individually – Instead of applying a single precomputed attack to all users, an attacker must brute-force each password separately, increasing computational cost.

Spraying and Stuffing attacks

Password Spraying:

Password spraying is an attack where an attacker tries a small number of common passwords (e.g., “123456” or “password”) across a large number of accounts. Unlike brute force attacks that target a single account with multiple passwords, password spraying avoids detection by limiting the number of attempts per account, making it harder for security systems to flag the activity.

Credential Stuffing:

Credential stuffing is an attack where attackers use a large list of previously leaked or stolen username and password combinations to try logging into various systems. Since many users reuse passwords across multiple services, attackers rely on these credentials working for other accounts. Automated tools are often used to test the credentials on multiple platforms quickly.

Password recovery options

Passwords are bad. They are not incredibly secure. English text has a low entropy (approximately 1.2–1.5 bits per character) and are often easy to guess. Password files from some high-profile sites have been obtained to validate just how bad many people are at picking passwords. Over 90% of all user passwords sampled are on a list of the top 1,000 passwords. The most common password is password. People also tend to reuse passwords. If an attacker can get passwords from one place, there is a good chance that many will work with other services.

Despite many people picking bad passwords, people often forget them, especially when they are trying to be good and use different passwords for different accounts. There are several common ways of handling forgotten passwords, none of them great:

Email them:

This used to be a common solution and should be dying off. It requires that the server stores the password, which means it is not stored as a hash. This exposes the risk that anyone seeing your email will see your password.

Reset them:

This is more common but requires authenticating the requestor to avoid a denial of service attack. The common thing to do is to send a password reset link to an email address entered when the account was created. We again have the problem that if someone has access to your mail, they will have access to the password reset link and can create a new password for your account. In both these cases, we have the problem that users may no longer have the same email address. Think of the people who switched from Comcast to get Verizon FiOS and switched their comcast.net addresses to verizon.net (note: avoid using email addresses tied to services or locations that you might change).

Provide hints:

This is common for system logins (e.g. macOS and Windows). However, a good hint may weaken the password or may not help the user.

Ask questions:

It is common for sites to ask questions (“what was your favorite pet’s name?”, “what street did you live on when you were eight years old?”). The answers to many of these questions can often be found through a bit of searching or via social engineering. A more clever thing is to have unpredictable answers (“what was your favorite pet’s name?” “Osnu7$Qbv999”) but that requires storing answers somewhere.

Rely on users to write them down:

This is fine as long as the thread model is electronic-only and you don’t worry about someone physically searching for your passwords.

One-time Passwords (OTPs)

The other problem with reusable passwords is that if a network is insecure, an eavesdropper may sniff the password from the network. A potential intruder may also simply observe the user typing a password. To thwart this, we can turn to one-time passwords. If someone sees you type a password or gets it from the network stream, it won’t matter because that password will be useless for future logins.

There are three forms of one-time passwords:

1. Sequence-based. Each password is a function of the previous password. S/Key is an example of this.

2. Challenge-based. A password is a function of a challenge provided by the server. CHAP is an example of this.

3. Time-based or Sequence-based. Each password is a function of the time. TOTP and RSA’s SecurID are examples of this.

Sequence-based: S/Key

S/Key authentication is a one-time password (OTP) system that generates a sequence of passwords using a one-way function. Each password in the sequence is derived from the previous one, ensuring that passwords are used in reverse order for authentication.

1. A user or administrator selects an initial secret (the seed).
2. A one-way function f is repeatedly applied to generate a sequence of passwords: password[n] = f(password[n−1])
3. The system stores only the final computed password: password[N].
4. Each time the user authenticates, they provide the next password in the reverse sequence:
   • The first authentication uses password[N−1].
   • The second authentication uses password[N−2].
   • This continues until all passwords in the list are used.

Challenge-based: CHAP

The Challenge-Handshake Authentication Protocol (CHAP) is an authentication mechanism that allows a server to verify a user’s identity without transmitting the password over the network.

CHAP is based on a shared secret (essentially a password) that both the client and server know. Authentication follows these steps:

1. Challenge: The server generates a random nonce (a unique random value), called a challenge and sends it to the client.
2. Response: The client computes a hash of the shared secret combined with the nonce and sends the result back to the server.
3. Verification: The server performs the same hash calculation using its stored copy of the shared secret. If the computed hash matches the one sent by the client, authentication succeeds. Otherwise, authentication fails.

With CHAP:

• The password is never transmitted, only a hash of the password with a random challenge. An intruder that sees this hash cannot extract the original data.
• Since the challenge (nonce) changes for each authentication attempt, an attacker cannot reuse an old response.

Challenge-based: Passkeys

Passkey authentication is a modern implementation of public key authentication designed to eliminate the need for passwords. Instead of relying on traditional credentials, passkeys use cryptographic public-private key pairs to authenticate users securely.

Enrollment

1. The user logs into a service using a legacy authentication method (e.g., username-password, OTP, or SMS verification).
2. The user’s device generates a unique public-private key pair for that specific service.
3. The public key is sent to the service and stored with the user’s account, replacing the need for a password.
4. The private key remains securely stored on the user’s device.

Authentication (login)

1. The user provides their username to the service.
2. The server generates a random challenge (at least 16 bytes long) and sends it to the user.
3. The user’s device retrieves the private key associated with the service. This might use on-device biometric authentication (Face ID, Touch ID), a device PIN, or an on-device password. The user’s device then uses the private key to digitally sign the challenge.
4. The signed response is sent back to the service.
5. The service retrieves the user’s public key, which was stored during enrollment.
6. It verifies the digital signature against the challenge. If the signature is valid, the server confirms that the user possesses the corresponding private key and grants access.

Time-based: TOTP

TOTP (Time-based One-Time Password) is a widely used authentication method that generates a temporary code based on a shared secret key and the current time.

It applies an HMAC (Hash-based Message Authentication Code) function using the secret key and a time-based counter, typically in 30-second intervals. The server independently computes the expected OTP using the same key and time window, allowing authentication if the values match. Since TOTP codes expire quickly, they provide strong protection against replay attacks.

TOTP is often used as a second factor (proof that you have some device with the secret configured in it) in addition to a password. The protocol is widely supported by companies such as Amazon, Dropbox, WordPress, Microsoft, and Google.

Counter-based: HOTP

HOTP (HMAC-based One-Time Password) generates one-time passwords using a shared secret and an incrementing counter. It is essentially the same as TOTP except that it uses a counter instead of the current time.

Each time an authentication attempt is made, the counter advances on both the client and server to ensure the password is not reused.

Unlike TOTP, HOTP does not expire after a set time, making it more vulnerable to replay attacks but eliminating the need for time synchronization. It is defined in RFC 4226 and is commonly implemented in hardware tokens like YubiKey for MFA (Multi-Factor Authentication).

Since HOTP is not time-based, users can enter a code at any time before the next one is generated. However, it requires keeping counters synchronized between the client and the service.

Push notifications

Push notifications rely on sending a notification via phone-based SMS messaging (or sometimes email) to validate that a user is in possession of their device (the “something you have” factor). They are often used as a second factor in multi-factor authentication.

Second Factor Authentication with Push Notifications:

This method adds an additional layer of security by sending a push notification to the user’s registered device during login attempts. The user must approve the notification to complete authentication, ensuring that even if credentials are compromised, unauthorized access is prevented.

MFA Fatigue occurs when users are overwhelmed by frequent multi-factor authentication (MFA) requests, leading to careless behavior, such as approving authentication requests without proper verification. Attackers can exploit this by repeatedly sending prompts in hopes that the user will approve one out of frustration or by mistake, granting unauthorized access. This type of fatigue can weaken the security benefits of MFA.

Number Matching Authentication:

Number matching authentication is a technique where the user is presented with a randomly generated number on the device they are logging into, and they must confirm by entering the same number on their second factor device (e.g., mobile phone). This prevents unauthorized approval of login attempts, reducing phishing risks.

Risk-Based Authentication (RBA)

Risk-Based Authentication (RBA) is an adaptive security mechanism that dynamically adjusts authentication requirements based on the risk level of a login attempt. Instead of applying the same level of security for every login, RBA evaluates various factors to determine whether additional authentication steps are necessary.

These factors include geolocation, device and browser information, IP address reputation, and behavioral patterns such as the time and frequency of login attempts.

If a user logs in from a familiar device and location, standard authentication may be sufficient. However, if the system detects an unusual login, such as an attempt from a different country or an unfamiliar device, it may prompt the user for additional verification, such as multi-factor authentication (MFA) or email confirmation.

By adapting security measures based on context, RBA enhances account protection while minimizing unnecessary friction for legitimate users. It helps prevent unauthorized access by flagging risky logins and requiring additional verification only when needed. This approach balances security and user convenience, reducing the frequency of MFA prompts for low-risk users while ensuring stronger protections against suspicious login attempts. By intelligently assessing risk in real-time, RBA provides a more seamless yet secure authentication experience.

Adversary-in-the-Middle (AitM) Attacks

Authentication protocols can be vulnerable to Adversary-in-the-Middle (AitM) attacks, also commonly referred to as Man-in-the-Middle (MitM) attacks or Machine-in-the-Middle attacks.

In this attack, a malicious actor intercepts communication between two parties and impersonates each one to the other.

For example, Alice believes she is communicating with Bob, but in reality, she is talking to Mike, the attacker in the middle. At the same time, Mike is also communicating with Bob, relaying messages between them. This allows Mike to observe the conversation without raising suspicion. Once authentication is completed, Mike can either drop Alice and continue communicating directly with Bob while impersonating her or remain in the middle, eavesdropping and altering messages as needed.

Protocols resistant to AitM attacks use trusted key exchange mechanisms to establish an encrypted channel that prevents interception. For instance, in Kerberos, both Alice and Bob receive a session key that is encrypted specifically for each of them. Since the session key remains confidential, Mike cannot access it even if he intercepts their communication.

Public key cryptography, however, requires additional safeguards against AitM attacks. If Mike intercepts a key exchange, he can deceive Bob into thinking he is Alice. To prevent this, Alice must send Bob a signed session key during the key exchange. If Alice’s message is properly digitally signed, Mike will be unable to decrypt the session key or forge a new one, ensuring secure communication between Alice and Bob.

By using cryptographic techniques such as mutual authentication, digital signatures, and secure key exchanges, authentication protocols can effectively defend against Adversary-in-the-Middle attacks, ensuring that communication remains secure and tamper-proof.

Biometric authentication

Biometric authentication is the process of identifying a person based on their physical or behavioral characteristics as opposed to their ability to remember a password or their possession of some device. It is the third of the three factors of authentication: something you know, something you have, and something you are.

It is also fundamentally different than the other two factors because it does not deal with data that lends itself to exact comparisons. For instance, sensing the same fingerprint several times will not likely give you identical results each time. The orientation may differ, the pressure and angle of the finger may result in some parts of the fingerprint appearing in one sample but not the other, and dirt, oil, and humidity may alter the image. Biometric authentication relies on pattern recognition and thresholds: we have to determine whether two patterns are close enough to accept them as being the same.

A false acceptance rate (FAR) is when a pair of different biometric samples (e.g., fingerprints from two different people) is accepted as a match. A false rejection rate (FRR) is when a pair of identical biometric samples is rejected as a match. Based on the properties of the biometric data, the sensor, the feature extraction algorithms, and the comparison algorithms, each biometric device has a characteristic ROC (Receiver Operating Characteristic) curve. The name derives from early work on RADAR and maps the false acceptance versus false rejection rates for a given biometric authentication device. For password authentication, the “curve” would be a single point at the origin: no false accepts and no false rejects. For biometric authentication, which is based on thresholds that determine if the match is “close enough”, we have a curve.

At one end of the curve, we can have an incredibly low false acceptance rate (FAR). This is good as it means we will not have false matches: the enemy stays out. However, it also means the false reject rate (FRR) will be very high. If you think of a fingerprint biometric, the stringent comparison needed to yield a low FAR means that the algorithm will not be forgiving to a speck of dirt, light pressure, or a finger held at a different angle. We get high security at the expense of inconveniencing legitimate users, you may have to present their finger repeatedly for sensing, hoping that it will eventually be accepted.

At the other end of the curve, we have a very low false rejection rate (FRR). This is good since it provides convenience to legitimate users. Their biometric data will likely be accepted as legitimate, and they will not have to deal with the frustration of re-sensing their biometric, hoping that their finger is clean, not too greasy, not too dry, and pressed at the right angle with the correct pressure. The trade-off is that it’s more likely that another person’s biometric data will be considered close enough as well and accepted as legitimate.

Numerous biological components can be measured. They include fingerprints, irises, blood vessels on the retina, hand geometry, facial geometry, facial thermographs, and many others. Data such as signatures and voice can also be used, but these often vary significantly with one’s state of mind (your voice changes if you’re tired, ill, or angry). They are behavioral systems rather than purely physical systems, such as your iris patterns, length of your fingers, or fingerprints, and tend to have lower recognition rates. Other behavioral biometrics include keystroke dynamics, mouse use characteristics, gait analysis, and even cognitive tests.

Regardless of which biometric is used, the important thing to do to make it useful for authentication is to identify the elements that make it different. Most of us have swirls on our fingers. What makes fingerprints different from finger to finger are the various variations in those swirls: ridge endings, bifurcations, enclosures, and other elements beyond that of a gently sloping curve. These features are called minutia. The presence of minutia, their relative distances from each other and their relative positions can allow us to express the unique aspect of a fingerprint as a relatively compact stream of bits rather than a bitmap.

Two important elements of biometrics are robustness and distinctiveness. Robustness means that the biometric data will not change much over time. Your fingerprints will look mostly the same next year and the year after. Your fingers might grow fatter (or thinner) over the years and at some point in the future, you might need to re-register your hand geometry data.

Distinctiveness relates to the differences in the biometric pattern among the population. Distinctiveness is also affected by the precision of a sensor. A finger length sensor will not measure your finger length to the nanometer, so there will be quantized values in the measured data. Moreover, the measurements will need to account for normal hand swelling and shrinking based on temperature and humidity, making the data even less precise. Accounting for these factors, approximately one in a hundred people may have hand measurements similar to yours. A fingerprint sensor may typically detect 40–60 distinct features that can be used for comparing with other sensed fingerprints. An iris scan, on the other hand, will often capture over 250 distinct features, making it far more distinctive and more likely to identify a unique individual.

Some sensed data is difficult to normalize. Here, normalization refers to the ability to align different sensed data to some common orientation. For instance, identical fingers might be presented at different angles to the sensors. The comparison algorithm will have to account for possible rotation when comparing the two patterns. The inability to normalize data makes it difficult to perform efficient searches. There is no good way to search for a specific fingerprint short of performing a comparison against each stored pattern. Data such as iris scans lends itself to normalization, making it easier to find potentially matching patterns without going through an exhaustive search.

In general, the difficulty of normalization and the fact that no two measurements are ever likely to be the same makes biometric data not a good choice for identification. It is difficult, for example, to construct a system that will store hundreds of thousands of fingerprints and allow the user to identify and authenticate themselves by presenting their finger. Such a system will require an exhaustive search through the stored data and each comparison will itself be time-consuming as it will not be a simple bit-by-bit match test. Secondly, fingerprint data is not distinct enough for a population of that size. A more realistic system will use biometrics for verification and have users identify themselves through some other means (e.g., type their login name) and then present their biometric data. In this case, the software will only have to compare the pattern associated with that user.

The biometric authentication process comprises several steps:

1. Enrollment. Before any authentication can be performed, the system needs to store the user’s biometric data to later use it for comparison. The user will have to present the data to the sensor, distinctive features need to be extracted, and the resulting pattern stored. The system may also validate if the sensed data is of sufficiently high quality or ask the user to repeat the process several times to ensure consistency in the data.

2. Sensing. The biological component needs to be measured by presenting it to a sensor, a dedicated piece of hardware that can capture the data (e.g., a camera for iris recognition, a capacitive fingerprint sensor). The sensor captures the raw data (e.g., an image).

3. Feature extraction. This is a signal processing phase where the interesting and distinctive components are extracted from the raw sensed data to create a biometric pattern that can be used for matching. This process involves removing signal noise, discarding sensed data that is not distinctive or not useful for comparisons and determining whether the resulting values are of sufficiently good quality that it makes sense to use them for comparison. A barely-sensed fingerprint, for instance, may not present enough minutia to be considered useful.

4. Pattern matching. The extracted sample is now compared to the stored sample that was obtained during the enrollment phase. Features that match closely will have small distances. Given variations in measurements, it is unlikely that the distance will be zero, which would indicate a perfect match.

5. Decision. The “distance” between the sensed and stored samples is now evaluated to decide if the match is close enough. The decision determination decides whether the system favors more false rejects or more false accepts.

Security implications

Several security issues relate to biometric authentication.

Sensing

Unlike passwords or encryption keys, biometric systems require sensors to gather the data. The sensor, its connectors, the software that processes sensed data, and the entire software stack around it (operating system, firmware, libraries) must all be trusted and tamper-proof.

Secure communication and storage

The communication path after the data is captured and sensed must also be secure so that attackers will have no ability to replace a stored biometric pattern with one of their own.

Liveness

Much biometric data can be forged. Gummy fingerprints can copy real fingerprints, pictures of faces or eyes can fool cameras into believing they are looking at a real person, and recordings can be used for voice-based authentication systems.

Thresholds

Since biometric data relies on “close-enough” matches, you can never be sure of a certain match. You will need to determine what threshold is good enough and hope that you do not annoy legitimate users too much or make it too easy for the enemy to get authenticated.

Lack of compartmentalization

You have a finite set of biological characteristics to present. Fingerprints and iris scans are the most popular biometric sources. Unlike passwords, where you can have distinct passwords for each service, you cannot have this with biometric data.

Theft of biometric data

If someone steals your password, you can create a new one. If someone steals your fingerprint, you have nine fingerprints left and then none. If someone gets a picture of your iris, you have one more left. Once biometric data is compromised, it remains compromised.