**ps. look out for all my other solutions for Advent of Code challenges here.**

## Day 14

See details of the challenge here.

Today’s challenge is very similar to that of Day 5, but the requirements for a valid hash value is different this time.

As before, we’ll start by defining a * hash* function that will accept a string and return its MD5 hash value represented as hexdecimal values. After comparing the performance of using

*+*

**String.format***(what I used in*

**String.Concat***Day 5*) and

*it was a no brainer to go with the latter as it proved to be over 10 times faster even with the additional*

**BitConverter.ToString***String.Replace*and

*String.ToLower*calls in this case.

Since part 2 requires us to add key stretching to the hash generation process, our * solve* function will take a hash function as argument.

A brute force approach would be to use * Seq.windowed 1001* to produce sliding windows of 1001 MD5 hashes so we can look for patterns where:

- the first hash has a sequence of 3, eg, “777”
- one of the next 1000 hash values has a sequence of 5 of that character, ie, “77777”

This naive approach took 10s to compute part 1, and over 9 mins for part 2. Most of the time were spent looking for sequences of 5, so an optimization here would be to find all sequences of 5 and storing their indices in a cache. This way, whenever you find a hash with a sequence of 3 – say “777” at index 18 – you can look up the cache for indices associated with “7” and see if there’s any index in the range of 19 – 1018.

This simple optimization took the run time for part 1 to around 300ms.

### Part 2

Of course, in order to make this process even more secure, you’ve also

implemented key stretching.

Key stretching forces attackers to spend more time generating hashes.

Unfortunately, it forces everyone else to spend more time, too.

To implement key stretching, whenever you generate a hash, before you use it,

you first find the MD5 hash of that hash, then the MD5 hash of that hash, and so

on, a total of 2016 additional hashings. Always use lowercase hexadecimal

representations of hashes.

For example, to find the stretched hash for index 0 and salt abc:

– Find the MD5 hash of abc0: 577571be4de9dcce85a041ba0410f29f.

– Then, find the MD5 hash of that hash: eec80a0c92dc8a0777c619d9bb51e910.

– Then, find the MD5 hash of that hash: 16062ce768787384c81fe17a7a60c7e3.

– …repeat many times…

– Then, find the MD5 hash of that hash: a107ff634856bb300138cac6568c0f24.

So, the stretched hash for index 0 in this situation is a107ff…. In the end,

you find the original hash (one use of MD5), then find the hash-of-the-previous-hash

2016 times, for a total of 2017 uses of MD5.

The rest of the process remains the same, but now the keys are entirely different.

Again for salt abc:

– The first triple (222, at index 5) has no matching 22222 in the next thousand

hashes.

– The second triple (eee, at index 10) hash a matching eeeee at index 89, and so

it is the first key.

– Eventually, index 22551 produces the 64th key (triple fff with matching fffff

at index 22859.

Given the actual salt in your puzzle input and using 2016 extra MD5 calls of key

stretching, what index now produces your 64th one-time pad key?

This implementation took around 2 mins to run, and most of the time are spent in generating the hash values (since they are 2016 times more expensive than previously).

I was able to shave 10s off the runtime by hand rolling the bytes-to-hexdecimal part of the * hash* function, but it’s still far from good enough really. So, please let me know in the comments any ideas you have on what we could try next.

## Links

- Day 14 challenge description
- Advent of Code 2015
- Solution for Day 13
- Solution for Day 5
- All my F# solutions for Advent of Code
- Github repo

Pingback: Advent of Code F# – Day 15 | theburningmonk.com