Advent of Code 2016 - Day 14

Day 14: One-Time Pad

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

hashlibfunctools.lru_cacheregex

Problem Intro

We need to generate a one-time pad to communicate securely. The keys for the pad are generated by hashing a salt (our puzzle input) with an increasing integer index (starting from 0). The hash function is MD5.

A hash is a key only if it meets two conditions:

1. It contains three of the same character in a row (a triplet).
2. One of the next 1000 hashes contains five of that same character in a row.

We need to find the index that produces the 64th key.

Part 1

Given the actual salt in your puzzle input, what index produces your 64th one-time pad key?

This is a straightforward hashing problem. For each index, we generate an MD5 hash and check for a triplet. If we find one, we then check the next 1000 hashes for a sequence of five of the same character.

To make this efficient, I used a cache. Since we are repeatedly calculating hashes for overlapping ranges of indices, caching the results of the hash calculations significantly speeds up the process. I used functools.lru_cache for this purpose.

Here’s the main logic:

import hashlib
import functools
import re

# ...

def find_keys(salt, repeats=0):
    keys = []
    index = 0
    
    while len(keys) < KEYS_TO_FIND:
        to_hash = salt + str(index)
        hash_hex = hash_method(to_hash, repeats)
        
        if match := triple_chars_match.search(hash_hex):
            five_char_seq = 5*match.group()[0]
            for i in range(1, 1001):
                subsequent_hash = hash_method(salt+str(index+i), repeats)
                
                if five_char_seq in subsequent_hash:
                    keys.append(hash_hex)
                    break
            
        index += 1
    return index, keys

@functools.lru_cache(None)
def hash_method(to_hash, repeats):
    result = to_hash
    for _ in range(repeats+1):
        result = hashlib.md5(result.encode()).hexdigest()
    
    return result

The find_keys function iterates through indices, generates hashes, and checks for the key conditions. The hash_method is decorated with @functools.lru_cache(None), which caches the results of the hash calculations. The None argument for maxsize means the cache can grow without bound.

Part 2

To make the keys harder to crack, the hash function is modified. Instead of just hashing once, you hash 2016 additional times. That is, you hash the salt+index combination, then hash the result of that, and so on, for a total of 2017 hashes.

This is a simple modification to our existing solution. We can pass the number of repeats to our hash_method. The lru_cache will still work, but it will be caching the results of the stretched hashes.

I modified the find_keys and hash_method to accept a repeats parameter. For Part 2, we call find_keys with repeats=2016.

    index, keys = find_keys(salt, MD5_REPEATS)   
    logging.info("Part 2: 64th key produced at index %d", index-1)

Results

Here’s the output from the solution:

Part 1: 64th key produced at index 15167
Part 2: 64th key produced at index 19967
Execution time: 1.1523 seconds

‹›