HW3: SHA-1 Hash and Password Cracking

CS 493/693 Homework, Dr. Lawlor, 2006/02/06.  Due at 5pm on Monday, March 6.

I've started another strange network server process, listening on port 80 of the server "target.cs.uaf.edu".  Your assignment is to see firsthand how a restricted password can be recovered purely from its hash.

The server listening on port 80 of target.cs.uaf.edu is NOT a webserver.  Instead, it speaks the following very simple protocol:

  1. The server sends you a welcome string followed by a newline.
  2. You send the server your UAF email ID (like "ffosl") followed by a newline.
  3. You send the server the number of the problem you'd like to solve, followed by a newline.
  4. The server makes up a 'password', and tells you what kind of password it made and the SHA-1 hash of that password.
  5. You determine what the password is, and send it to the server followed by a newline.
  6. If you're right, the server prints "YES"; if not the server prints "NO".

Here's an example run. Things I typed in are in italic.

my_box> telnet target.cs.uaf.edu 80
Connected to target.cs.uaf.edu.
Escape character is '^]'.
Welcome to the CS 493/693 HW3 target.  Send your UAF email ID and a newline
Which problem would you like to solve (1-5)?
1     <- Each email and problem will have a different secret password
Problem 1: I'm thinking of a one-character printable ASCII password.
Password's SHA1 hash: d160e0986aca4714714a16f29ec605af90be704d
Please enter the password:
L     <- I cracked this with "brute.cpp" from the hash above
YES!  That's the password!  Problem complete.  Closing connection.
^]     <- That's "control-right bracket"
telnet> close
Connection closed.
I'll keep your highest grade--you can repeatedly attack the server as many times as you like.  Please do not denial-of-service the target, or try buffer overflows (but there shouldn't be any).

There are 5 problems:

  1. Problem 1: I'm thinking of a one-character printable ASCII password, like "x".
  2. Problem 2: I'm thinking of a four-digit numeric password, like "1776".
  3. Problem 3: I'm thinking of a three-character printable ASCII password, like "d&!".
  4. Problem 4: I'm thinking of an eight-digit numeric password, but the digits are in *strictly* increasing order, like "01256789".
  5. Problem 5: I'm thinking of a 10-character password consisting entirely of the lowercase characters 'f' and 'o', like "foofoofooo".

You should be able to do all 5 problems using just "telnet" run interactively. Unless you're really lucky, you'll almost certainly need to use the "brute.cpp" password-cracking code in the homework support directory (Directory, Zip, Tar-gzip). "brute.cpp" should build fine on Linux or Windows, but it takes the input hash on the command line. You can also read more about how the passwords are generated by reading the "grader.cpp" server (although the grader code is UNIX-specific).

Note that backspaces *look* like they work, but they actually don't! I recommend copy-and-pasting hashes and passwords.

The passwords are generated on the fly via a deterministic hash of your email address and a secret string (SECRET_BIAS in grader.cpp). This means you'll be asked for the same passwords each time you run, but it won't help to turn in your buddy's cracked passwords. If you're really dedicated, it's theoretically possible to recover the 16-digit SECRET_BIAS just by looking at the generated passwords--but as far as I can tell, it's computationally infeasible!

You should be able to bruteforce all of these passwords in about one second--if you think you need to search for hours, think harder about how you're generating the possible passwords. You don't need to turn anything in--I'll get your grade right out of the server logs!