CIS 5357 - Network Security - Fall 2004

Homework assignment

Goal of Assignment:

Implement a strong password authentication protocol called SRP (Secure Remote Password), a proposed Internet Standard:

Technical White Paper: Thomas Wu, The Secure Remote Password Protocol.
Internet Engineering Task Force (IETF), Request for Comments RFC2945.
SRP compared to some other authentication protocols: SRP Competitive Analysis. (The analysis is made by the SRP proponents, at Stanford University.)
SRP site at Stanford.

Motivation:

Strong authentication is an issue still largely unaddressed some widely deployed authentication systems, including SSH.
SRP is one of many protocols that have been proposed. It promises to provide a mechanism that:

remains password-based, eliminating the need for secure storage of secret or private keys.

protects passwords against off-line dictionary attacks.
protects systems against simultaneous server-database compromise and eavesdropping attacks.
provides forward security.

This set of features is probably the most expansive one might ask of a password-based protocol. In particular, as any protocol based on passwords, it is still vulnerable to:

on-line attacks, which are however easy to prevent against by adding time-outs after a few unsuccessful failures, and actively monitoring security operations (such as multiple failed login attempts) do detect such attacks.
compromise of the server database, followed by an exhaustive search of passwords + salt combinations. This can only be ammeliorated by the implementation of measures such as user education that lead to the choice of better passwords and frequently changed passwords, or by the use of other methods such as cryptographic tokens and/or biometric mechanisms.

Recipe for Success:

Start working on the assignment as soon as possible. Give yourself enough time.
Start by reading the SRP white paper. Make sure you understand the protocol thoroughly, by drawing diagrams of the messages, making sure you understand what cryptographic primitives (Diffie-Hellman, symmetric encryption, hashes) are being used.
Follow up by familiarizing yourself with the Java security classes, and with the BigInteger class. Investigate the Java Cryptographic Extension.
Code some of the "workhorse" classes, such as SHA_Interleaves, and make sure you know how to encrypt and decrypt correctly -- that entails learning how to initialize the algorithms with keys and the proper mode. The code examples in the JCE will help here.
Download the code for the exercise (from the main course webpage), run the demo and read the documentation.
Start programming.
Test your code carefully.
Be honest and work individually. Do not share your code.

Recipe(s) for Failure:

Do not study carefully the protocol, skim it or ask a friend a couple of questions and assume to have understood it.
Download the existing code and try to hack your way to somewhere.
Wait until the last few days to start. You will probably need a considerable amount of time to become familiar with the APIs. It is better taking it in a little at a time, and build momentum over several weeks.
Cheat. Share your code.

Detailed Description of the assignment:

The purpose of this assignment is to implement a secure remote password protocol. You are provided with Java implementations of the basic server and client functionality. This server and client programs are extensible, i.e., their functionality is implemented through the use of protocol classes. If you provide the client or server with different protocol class implementations, the behavior of the client and server will change.

The provided capability of the client/server is as such:

Users are authenticated based on sending their name and password in the clear. This is checked against the server's database, which stores password hashes.
If authentication succeeds, the server allows the user to type messages to the server. The server echoes your messages. This data is sent between you and the server in the clear.

You must modify the behavior of the protocol such that:

Users are authenticated based on the SRP protocol. The server will store not salts and hashes, but the password-based public key of each user, as described in the SRP protocol.
If authentication succeeds, the server allows the user to type messages to the server. The messages must be sent/received in encrypted format.

In order to be fair to your work, each part will be graded independently, as follows:

If authentication is implemented correctly: 60% of the grade.
If encryption is implemented correctly: 30% of the grade
Documentation: 10%

Specifications:

The SRP protocol has two phases:

1) Key agreement phase

2) Authentication phase, based on the common key agreed in (1).

The picture below describes the two messages that constitute the first phase. Each server maintains a database of user entries, which are triples of:

A username;
A verifier, which is essentially a number in the interval [2, p - 2], where p is a very large prime. The value of p is part of the public specification of the system.
A salt;

Of these, the salt is generated at random when the server first establishes the user entry. The verifier is provided by the user and is a one-way function of the username, the "raw" password, and the salt. (Since the raw password is never used directly for purposes of authentication, this protocol is secure against off-line dictionary attacks if the salt is unknown.) The verifier is computed (by Alice) as follows:

The username (say, "Alice") is represented as a byte array (using the byte values of ASCII characters). For instance, you could have the byte array <Alice>. We will use <username> for the byte representation of an arbitrary user's name.
This value <username> is hashed using the function SHA-1 to obtain a hashed identity HID.
This value is prefixed by the byte representation of the salt value (which Bob gives to Alice) and postfixed with the byte corresponding to ASCII character ":" + the byte representation of the user's password (which should not include the character ":"):

<salt> | HID | <:> | <raw password>, where | represents string concatenation.

The hash function SHA-1 is applied to the above to obtain

X = SHA-1( <salt> | HID | <:> | <raw password>).

The value X is then interpreted as an integer, using the following convention: If an array of bytes has bytes [b₀, b₁, b₂, ..., b_n], then it represents the integer 256ⁿ *b₀ + 256^n-1 * b₁ + ... + b_n, where the individual bytes b_k are naturally identified with the numbers in the interval [0, 255].
The verifier is finally computed as v = g^X mod p, where 'mod' indicates modular arithmetic. Alice gives this value 'v' to Bob, but not her password. Here, 'g' is also a number in the interval [2, p -2], and is part of the system's public specification.

One of the reasons why Java is used in this class (as opposed to C/C++) is that it has native support for arbitrary-precision arithmetic (i.e., arithmetic operations involving very large numbers). Please refer to the class BigInteger.

When Alice needs to identify herself with Bob, she engages in the following protocol:

Alice and Bob exchange the key agreement messages in the SRP protocol.

Alice and Bob exchange the key agreement messages in the SRP protocol.

The challenge values A and B are computed using specific algorithms:

Alice chooses a random value 'a' in the interval [2, p - 2] and computes A = g^a mod p.
Bob computes a random value 'b' in the same interval and computes B = (v + g^b) mod p.

This phase is completed with the generation of the common session key K_AB from the shared values. On her side, Alice computes:

S = (B - v) ^{( a + u x )} mod p,

while Bob computes:

S = (A v^u) ^b mod p.

Here the value u is an unsigned, 32-bit value obtaining from the first 4 bytes of the value SHA-1(B) -- using our previously described convention to convert between integers and byte arrays.

It is not hard to check that both values of S resulting from these different computations are equal. Bob and Alice must use different ways to compute S because Alice knows the value 'a' and Bob the value 'b', but not conversely. Only Alice or Bob may compute S as one needs to know at least one of these two values to execute either algorithm. The result is that S is a shared, secret value.

From S, the common key is derived by computing a function called SHA_Interleaves(). This function is essentially SHA-1 (which results in a 160-bit output), interleaved to obtain a 320-bit output:

K = K_AB= SHA_Interleaves(S).

After the common key is computed, Alice and Bob can authenticate each other:

Alice and Bob authenticate their common key exchanging messages

After this, they use the shared K to encrypt and authenticate messages back and forth.

In your implementation the messages will be encrypted with 112-bit triple-DES-ede in CBC mode, and authenticated with HmacSHA1 using a 128-bit key.
The steps are as follows:

Initialize the cipher using DESede with PKCS5 padding. You can give it any size byte buffer to encrypt. The output will be of byte size a multiple of 8.
Compute the HmacSHA1 using the hmac key. Attach to the end of your encryption.
On the other end, yo can check the Hmac first, and if it succeeds, you can decrypt (after truncating the buffer to eliminate the trailing Hmac value.

In other words, you will use the bytes b[0] through b[23] of the shared key K as a key K1 encryption, and bytes b[24] through b[40] of K as a key K2 for authentication. You will use the encrypt-then-authenticate paradigm, i.e., you will first CBC-encrypt all messages, then process the encrypted message through the MAC to get an authentication tag that is attached to the end of the message.

To finalize the specification of the assignment, you need the description of the SHA_Interleaves() function. It is as such:

Start with a byte array T = {T[0], T[1], T[2], ..., T[n]}. First shrink T, if needed, by removing any zero bytes in the first positions. In other words, T[0] should not equal the byte 0. Then make sure that T does not have an odd number of bytes, by dropping an extra byte at the beginning. Split T into two byte arrays alternating the indices.

E = T[0] | T[2] | T[4] | ...

F = T[1] | T[3] | T[5] | ...

Both E and F should be exactly half the length of T. Hash each one with regular SHA-1, i.e.

G = SHA-1(E)

H = SHA-1(F)

Then interleave the two hashes back together to form the output, i.e.

     result = G[0] | H[0] | G[1] | H[1] | ... | G[19] | H[19]

   The result will be 40 bytes (320 bits) long.

Final Observations:

Your client implementation will be tested against the server reference implementation, i.e., mine.   So IT IS ABSOLUTELY IMPORTANT THAT YOU IMPLEMENT YOUR EXTENSIONS according strictly to the specifications outlined here and in the remaining documentation. EVEN IF your implementation is correct (in the sense that your client and server are compatible and implement the full functionality), if it is incompatible with the specification, it can only receive a maximum of 85% of the grade (if either client or server is non-compliant) or 75% (if both non-compliant). This compliance will be measure independently for encryption and authentication.