On this page:
<day05>
5.1 What is the password for the first door?
<day05-setup>
<day05-hashcheck>
<day05-decrypt1>
<day05-decrypt2>
<day05-q1>
5.2 What is the password to the second door?
<day05-q2>
5.3 Extra Credit
5.3.1 Animated Password Hacking
<day05-animator>
5.3.2 Performance
<day05-benchmark>
5.4 Testing Day 5
<day05-test>
6.7

5 Day 5: Wargames-Style Password Hacking

Read the description of today’s puzzle. My input is simply cxdnnyjw, the ID of a door.

5.1 What is the password for the first door?

(require racket
         rackunit
         openssl/md5)
 
(define password-length 8)
(define input-string "cxdnnyjw")

Given a room abc we need to take the MD5 hashes of abc1, abc2, ... abcn, looking for hashes that start with five zeroes. When we find such a hash we need to pick out the “good part” to get the next character of the password. So first I define a function, interesting-hash?, to test whether the hash of a given string ("abc") and key (the number portion) is interesting. In part one of the problem the “good part” is the sixth character of the password, so my interesting-hash? function will default to the sixth function to select what part of the hash to return, but will allow the use of any other function with the #:good-part-picker keyword argument.

(define (interesting-hash? str key #:good-part-picker [good-part-picker sixth])
  (define hash-chars
    (string->list (md5 (open-input-string (string-append str key)))))
 
  (cond
    [(equal? '(#\0 #\0 #\0 #\0 #\0) (take hash-chars 5))
     (displayln (format "Found one: ~a resulted in ~a ..." key (take hash-chars 7)))
     (good-part-picker hash-chars)]
    [else #f]))

Now I can "decrypt" the password by iterating this interesting-hash? over the range of possible hashes to find all the password characters. My first try at a decrypt function was inefficient. It hung onto the results of every single hash in a giant ever-growing list, and would count the non-false values in that list after every single hash to see if it had accumulated enough to give the password. Since there might be hundreds of thousands of false values before it found the 8 non-false ones it needed, this approach took a length of time technically known as “forever.”

(define (decrypt-version1 str [hard-range 0])
  (define this-range (if (equal? 0 hard-range) (in-naturals) (in-range hard-range)))
  (define result
    (for/fold ([tried-hashes empty])
              ([n this-range]
               #:break (equal? password-length (count identity tried-hashes)))
      (cons (interesting-hash? str (number->string n)) tried-hashes)))
  (list->string (reverse result)))

In decrypt-version2, I took the more obvious approach of discarding the #f result of any non-interesting hash, which kept the list to no more than password-length items instead of hundreds of thousands.

Both of these functions accept an optional argument to specify an upper limit to the number of keys that would be tested: this was added to aid debugging and becnhmarking. In decrypt-version2 I also added an optional keyword argument, #:animator, which should bind to a function that takes a list of the password characters found so far and displays them in some marginally hackerish and theatrical style. More on this in a bit.

(define (decrypt-version2 str [hard-range 0] #:animator [status-animator void])
  (define this-range (if (equal? 0 hard-range) (in-naturals) (in-range hard-range)))
 
  (define result
    (for/fold ([found-chars empty])
              ([n this-range]
               #:break (equal? password-length (length found-chars)))
      (let ([next-result (interesting-hash? str (number->string n))])
        (and (equal? 0 (modulo n 5000)) (status-animator found-chars))
        (cond [(char? next-result) (cons next-result found-chars)]
              [else found-chars]))))
  (list->string (reverse result)))

You may have noticed that at the end of both of my decryptor functions so far, I (reverse result) before returning a value. In Racket (as in most LISP languages, from what I understand) a list such as (list 1 2 3) is technically a (cons 1 (list 2 3)) which in turn is technically (cons 1 (cons 2 (cons 3 null))). Thus, the most basic, idiomatic way to tack a single new item onto a list turns out to be (cons new-item old-list). If you wanted to put it at the end, I suppose the best way would be (append old-list (list new-item)). Which way results in faster execution time? I have no idea. I just know the way I chose is harder to read and therefore probably dumb.

Either way, I can now decrypt the password for the first door.

(define (q1 str)
  (decrypt-version2 str))

5.2 What is the password to the second door?

To solve part two of the problem, I must still trawl for MD5 hashes in the same way, looking for the ones that start with five zeroes — but the way I need to pick apart the “interesting” hashes has changed. The character I want is now the 7th character of the hash, and I use the 6th character of the hash to determine its position in the password.

Accordingly, within my decrypt-version3 function, I define a helper function two-part-picker that, given a list of characters, returns a new list: the first element is the integer equivalent of the sixth character (#\1 is ASCII 49, from which I subtract the constant 48 to get 1) and the second is the seventh character.

I can then pass this function into the interesting-hash? function with the #:good-part-picker keyword argument. As long as the result is not false, and the first element of the result is a number between 0 and password-length, and there isn’t an existing character in that spot, I slot the new character into the list of known characters.

(define (decrypt-version3 str [hard-range 0] #:animator [status-animator void])
  (define this-range (if (equal? 0 hard-range) (in-naturals) (in-range hard-range)))
 
  (define (two-part-picker x)
    (list (- (char->integer (sixth x)) 48) (seventh x)))
 
  (define result
    (for/fold ([found-chars (make-list password-length #f)])
              ([n this-range]
               #:break (equal? password-length (count identity found-chars)))
      (and (equal? 0 (modulo n 5000)) (status-animator found-chars))
      (let ([next-result (interesting-hash? str (number->string n)
                                            #:good-part-picker two-part-picker)])
        (cond [(and (not (false? next-result))
                    (member (first next-result) (range password-length))
                    (false? (list-ref found-chars (first next-result))))
               (define updated-found-chars
                   (list-set found-chars (first next-result) (second next-result)))
               (displayln (format "~s" updated-found-chars))
               updated-found-chars]
              [else found-chars]))))
  (list->string result))
 
(define (q2 str)
  (decrypt-version3 str))

5.3 Extra Credit

5.3.1 Animated Password Hacking

The puzzle says, “Be extra proud of your solution if it uses a cinematic ‘decrypting’ animation.” So I put forth a minimal effort at doing so — minimal, partly because displaying any output comes with a major performance penalty in Racket, even if you only display something every 5000 hashes or so. The performance hit is not as bad on the command line as opposed to the interactive REPL environment, but it’s still very noticeable.

The simple-animator function takes a list and pads it with #f elements until its length matches password-length, then replaces any #f with a random hexadecimal character, and prints the resulting string. This way it can work with the decryptor functions for both part 1 and part 2.

When using an animator function, the program prints out thousands of lines one after the other. A better way to do this would have been a single line of text that is continuously overwritten, but Racket does not have a clear, “built-in” way to overwrite a previously printed line of output. This is, I believe, definitely impossible in the REPL. It’s possible in a command-line environment but only using something like the charterm library, which only works on Unixy platforms. Writing a GUI version would allow for a pretty cool hackerly animation but I didn’t feel like going to that much trouble.

(define (simple-animator found-so-far)
  (define (supply-randchar chr)
    (if (false? chr)
        (number->string (random 16) 16)
        chr))
 
  (define padded
    (append found-so-far
            (make-list (- password-length (length found-so-far)) #f)))
 
  (write-string (list->string (map supply-randchar padded)))
  (newline))

5.3.2 Performance

As can perhaps guess, today’s problem turned out to be sort of computationally expensive. I soon became curious about how to improve performance. To start with, I wrote a benchmark function so I could measure performance more precisely.

(define (benchmark decryptor animator hashcount)
  (define start (current-inexact-milliseconds))
  (decryptor "abc" hashcount #:animator animator)
  (define end (current-inexact-milliseconds))
  (- end start))

To get the best performance out of Racket with reasonable effort, I compiled today’s code to a self-contained executable (using racket/base and importing only the modules I needed) on two different platforms and ran them to get some benchmarks:

Dell desktop, Windows 10, Intel i5-2400 @ 3.10GHz

Time

100,000 hashes, no printing
    (benchmark decrypt-version3 void 100000)

765ms

100,000 hashes, printing after each
    (benchmark decrypt-version3 simple-animator 100000)

3,717ms

Part Two complete solution, no animation
    (benchmark decrypt-version3 void)

186,452ms

 

 

Apple rMBP, macOS Sierra, Intel Core i5-5257U @ 2.70GHz

Time

100,000 hashes, no printing
    (benchmark decrypt-version3 void 100000)

482ms

100,000 hashes, printing after each
    (benchmark decrypt-version3 simple-animator 100000)

2,226ms

Part Two complete solution, no animation
    (benchmark decrypt-version3 void)

119,538ms

These results were derived using an earlier version of decrypt-version3 in which the status-animator is called after every hash, instead of every 5,000 hashes as shown in the latest version.

Overall the results are not nearly as fast as those obtained by people using other languages. You don’t use Racket when speed is critical. But even so, there are still probably ways I could have improved the speed of my solutions. The obvious first step that comes to mind is rewriting the program in Typed Racket.

5.4 Testing Day 5

(module+ test
  (check-equal? (q1 input-string) "f77a0e6e")
  (check-equal? (q2 input-string) "999828ec"))