This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 83

Oblivious password authentication

Due: April 26
Points: 8

Write a system for password-based authentication that uses 1-2 Oblivious Transfer to check a hash of the password in an oblivious way, so that the server will not know what password was actually entered, only whether or not it was the correct password.

Oblivious equality check, with a small tweak

The key will be the oblivious equality check protocol we learned about in class (which in turn uses 1-2 OT), with one difference. Recall that to obliviously check equality of an \(n\)-bit string, Alice generates \(2n-1\) random nonces (one for each possible setting of each bit), and then XORs the choices corresponding to her actual bits together to get the last (non-random) nonce value. That way, if Bob gets the right values, when he XORs them together he'll get a 0.

The change you are going to make is that, instead of Bob getting 0 when he XORs the correct values, he should get a bit-string that is HALF 0 bits, and the other half will be a random nonce that he sends back to Alice. This way, Alice doesn't have to "take Bob's word for it" that he entered the password correctly; she just has to check the value he sends back to her. But if Bob doesn't end up with a string that starts with half 0 bits, he knows he hasn't entered the password correctly and so he aborts the process.

So instead of simply XORing the correct selection of \(n-1\) nonces to get the final one, Alice will XOR the correct \(n-1\) nonces with the expected final message to Bob, which consists of half 0 bits and then random bits. Alice also saves these random bits, so she can check them against whatever Bob sends back later on.

Hash, no salt

The oblivious equality check protocol requires both parties to agree to the length \(n\) ahead of time. This is hard to do with passphrases, but the solution is pretty simple: hash the actual passphrase using a cryptographic hash function.

For this problem, I want you to use the SHA-256 hash function, which produces 256-bit hash values. So you will actually be comparing length-256 bit strings.

(Note, in practice you would also want to salt the password by appending some random value before hashing, but we'll leave that for now. The password hash is never actually stored in a file anyway.)

Program behavior

Specifically, you will create two programs: a server, and a client. When I run the server program (Alice), it should do the following:

  1. Read in a password from the console
  2. Store a SHA-256 hash of the password
  3. Compute and save a 128-bit random "challenge" \(a\).
  4. Generate \(2*256 - 1 = 511\) random nonces and save them in a \(256 \times 2\) array. The final nonce is computes as the XOR of the bits according to the stored hash, XORed with a string of 128 0's followed by the saved challenge \(a\).
  5. Wait for a TCP connection on the port specified on the command-line
  6. Perform 256 1-2 Oblivious Transfers, in parallel, to send Bob one out of each pair of random nonces. (Note that this itself involves computing a public/private key pair, 512 more random nonces, and some XORs and decryptions.)
  7. Wait for Bob to do his computation and send back the challenge \(a'\).
  8. If the challenge sent back by Bob matches the stored value \(a\), print "ACCESS GRANTED" to the console and exit.
  9. If anything goes wrong, print "DENIED" to the console and exit.

When I run the client program (Bob), it should do the following:

  1. Read in a password from the console
  2. Store a SHA-256 hash of the password
  3. Connect to the server on the hostname and TCP port specified on the command-line
  4. Perform 256 1-2 Oblivious Transfers, in parallel, to receive the 256 nonces corresponding to the bits of the hash value computed on step (2).
  5. XOR these values to gether to get a result \(r\).
  6. If \(r\) starts with 128 0 bits, send the final (random) 128 bits back to Alice as the "challenge response", print "CORRECT" to the console, and exit.
  7. If \(r\) does not start with 128 0 bits, terminate the connection, print "INCORRECT" to the console, and exit.

Starter code

To help you get started on this exciting task, I've implemented the 1-2 Oblivious Transfer algorithm in Python and in Java. This should have all the crypto you need, but it doesn't actually do the network communication. Instead, the communication between Alice and Bob is done by writing files to the current directory and waiting for the user to hit ENTER in between each step. Note, it might be a good idea for you to start work on this in the same way, so you can get all the crypto working before you figure out network sockets and whatnot.