ps. look out for all my other solutions for Advent of Code challenges here.
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 + String.Concat (what I used in Day 5) and BitConverter.ToString it was a no brainer to go with the latter as it proved to be over 10 times faster even with the additional 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.
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
– 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.
- 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
I specialise in rapidly transitioning teams to serverless and building production-ready services on AWS.
Are you struggling with serverless or need guidance on best practices? Do you want someone to review your architecture and help you avoid costly mistakes down the line? Whatever the case, I’m here to help.
Check out my new course, Complete Guide to AWS Step Functions. In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. Including basic concepts, HTTP and event triggers, activities, callbacks, nested workflows, design patterns and best practices.
Here is a complete list of all my posts on serverless and AWS Lambda. In the meantime, here are a few of my most popular blog posts.
- Lambda optimization tip – enable HTTP keep-alive
- You are thinking about serverless costs all wrong
- Many faced threats to Serverless security
- We can do better than percentile latencies
- I’m afraid you’re thinking about AWS Lambda cold starts all wrong
- Yubl’s road to Serverless
- AWS Lambda – should you have few monolithic functions or many single-purposed functions?
- AWS Lambda – compare coldstart time with different languages, memory and code sizes
- Guys, we’re doing pagination wrong