Advent of Code F# – Day 14

You can become a serverless blackbelt. Enrol to my 4-week online workshop Production-Ready Serverless and gain hands-on experience building something from scratch using serverless technologies. At the end of the workshop, you should have a broader view of the challenges you will face as your serverless architecture matures and expands. You should also have a firm grasp on when serverless is a good fit for your system as well as common pitfalls you need to avoid. Sign up now and get 15% discount with the code yanprs15!

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
– 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.



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 weekly newsletter

Hi, I’m Yan. I’m an AWS Serverless Hero and I help companies go faster for less by adopting serverless technologies successfully.

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.

Skill up your serverless game with this hands-on workshop.

My 4-week Production-Ready Serverless online workshop is back!

This course takes you through building a production-ready serverless web application from testing, deployment, security, all the way through to observability. The motivation for this course is to give you hands-on experience building something with serverless technologies while giving you a broader view of the challenges you will face as the architecture matures and expands.

We will start at the basics and give you a firm introduction to Lambda and all the relevant concepts and service features (including the latest announcements in 2020). And then gradually ramping up and cover a wide array of topics such as API security, testing strategies, CI/CD, secret management, and operational best practices for monitoring and troubleshooting.

If you enrol now you can also get 15% OFF with the promo code “yanprs15”.

Enrol now and SAVE 15%.

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!