Question

One mechanism for resisting "replay" attacks in password authentication is to use one-time passwords: A list of passwords is prepared, and once password \([N]\) has been accepted, the server decrements \(N\) and prompts for password \([N-1]\) next time. At \(N=0\) a new list is needed. Outline a mechanism by which the user and server need only remember one master password \(m p\) and have available locally a way to compute password \([N]=f(m p, N)\). Hint: Let \(g\) be an appropriate one-way function (e.g., MD5) and let password \([N]=g^{N}(m p)=g\), applied \(N\) times to \(m p .\) Explain why knowing password \([N]\) doesn't help reveal password \([N-1]\).

Short answer

Use a one-way function \(g\) to compute \(password[N] = g^N(m p)\). Knowing \(password[N]\) does not help in computing \(password[N-1]\) due to the one-way nature of \(g\).

Step-by-step solution

Understanding one-way functions

One-way functions are cryptographic functions that are easy to compute but hard to invert. This means if you know the output, it is computationally infeasible to determine the input. In this example, the one-way function is denoted as \(g\).

Define the master password

The master password \(m p\) is a secret password known only to the user and server. This will be the starting point for generating a list of passwords.

Initialize password generation

Given the master password \(m p\), the user and server can compute the first password in the sequence using the one-way function \(f(m p, N) = g^N(m p)\). For example, \(g^N(m p)\) means applying the function \(g\) to \(m p\) a total of \(N\) times.

Computing password \( [N] \)

To find password \([N]\), apply the one-way function \(g\) to the master password \(N\) times. Mathematically, this is written as \(password[N] = g^N(m p)\).

Computing password \([N-1]\)

To find the next password in the sequence, apply the one-way function one fewer time: \(password[N-1] = g^{N-1}(m p)\).

Security analysis

Knowing password \([N]\) does not reveal password \([N-1]\) because to find \(password[N-1]\) from \(password[N]\), one would need to invert the one-way function \(g\), which is computationally infeasible by design. Hence, even if an attacker captures password \([N]\), they cannot compute previous passwords.

Resetting the list

When the counter \(N\) reaches 0, a new list of passwords needs to be generated. This can be done by reinitializing the master password and computing again as needed using the same process.

Key concepts

Password Authentication

Password authentication is the process of verifying that a user is who they claim to be, based on a password. In most cases, a user's password is checked against a stored password. The challenge is to ensure both security and usability. For enhanced security, one-time passwords (OTPs) can be used. OTPs are temporary passwords that are valid for only one login session or transaction. This makes them resistant to interception and replay attacks.

Replay Attacks

A replay attack occurs when an attacker captures a valid data transmission, such as a password or token, and retransmits it to gain unauthorized access. OTPs greatly mitigate this risk because they become invalid once they have been used. So, even if an attacker intercepts a one-time password, they can't reuse it in future attempts.

One-way Functions

One-way functions play a crucial role in generating secure passwords. These are cryptographic functions that are easy to compute in one direction but nearly impossible to reverse. In the context of OTP generation, a one-way function, such as MD5, is applied multiple times to a master password. For instance, if the master password is `mp` and the function is represented as `g`, then the OTP for step `N` can be written mathematically as `g^N(mp)`, meaning that the function `g` is applied `N` times to the master password.

Cryptographic Security

Cryptographic security ensures that information cannot be accessed or altered by unauthorized parties. Using cryptographic techniques, like one-way functions, in password generation enhances security. Notably, knowing the OTP for a particular step does not help an attacker determine previous or future passwords. This is due to the computational difficulty of reversing one-way functions, making it infeasible to derive the master password or other OTPs from the captured password. Cryptographic security thus provides robust defense mechanisms against various threats, including replay attacks and unauthorized access.