Advent of Code F# – Day 14

Check out my new course Learn you some Lambda best practice for great good! and learn the best practices for performance, cost, security, resilience, observability and scalability.

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 + 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:

  1. the first hash has a sequence of 3, eg, “777”
  2. 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

Liked this article? Support me on Patreon and get direct help from me via a private Slack channel or 1-2-1 mentoring.
Subscribe to my newsletter


Hi, I’m Yan. I’m an AWS Serverless Hero and the author of Production-Ready Serverless.

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.

Hire me.


Check out my new podcast Real-World Serverless where I talk with engineers who are building amazing things with serverless technologies and discuss the real-world use cases and challenges they face. If you’re interested in what people are actually doing with serverless and what it’s really like to be working with serverless day-to-day, then this is the podcast for you.


Check out my new course, Learn you some Lambda best practice for great good! In this course, you will learn best practices for working with AWS Lambda in terms of performance, cost, security, scalability, resilience and observability. We will also cover latest features from re:Invent 2019 such as Provisioned Concurrency and Lambda Destinations. Enrol now and start learning!


Check out my video 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. There is something for everyone from beginners to more advanced users looking for design patterns and best practices. Enrol now and start learning!


Are you working with Serverless and looking for expert training to level-up your skills? Or are you looking for a solid foundation to start from? Look no further, register for my Production-Ready Serverless workshop to learn how to build production-grade Serverless applications!

Find a workshop near you