Hackvent 2019: Day 21

Challenge

HV19.21 Happy Christmas 256

Introduction
Santa has improved since the last Cryptmas and now he uses harder algorithms to secure the flag.

This is his public key:

X: 0xc58966d17da18c7f019c881e187c608fcb5010ef36fba4a199e7b382a088072f
Y: 0xd91b949eaf992c464d3e0d09c45b173b121d53097a9d47c25220c0b4beb943c

To make sure this is safe, he used the NIST P-256 standard.

But we are lucky and an Elve is our friend. We were able to gather some details from our whistleblower:

- Santa used a password and SHA256 for the private key (d)
- His password was leaked 10 years ago
- The password is length is the square root of 256
- The flag is encrypted with AES256
- The key for AES is derived with pbkdf2_hmac, salt: "TwoHundredFiftySix", iterations: 256*256*256

Phew - Santa seems to know his business - or can you still recover this flag?
Hy97Xwv97vpwGn21finVvZj5pK/BvBjscf6vffm1po0=

Solution

We review the clues the elves gave us and first start by trying to find Santa password that was leaked 10 years ago. We are looking for data breaches in 2009 so we look at a list of data breaches. We find that the rockyou breach was the biggest breach that year and that is password dumps are readily available (with usernames stripped out) so we download this dump. We also know that Santa's password is of length sqrt(256) = 16. There are roughly 118k passwords in the dump that meet the length requirement. Another clue tells us that the AES256 key can be derived with pbkdf2_hmac with the salt TwoHundredFiftySix and with 256*256*256 iterations. We also know that Santa's password is of length sqrt(256) = 16. We attempt to bruteforce the AES key but realise very quickly this is very slow and would take a long time. To be clear, it is quite feasible to crack the AES key this way over the course of say 48 hours but we want a faster solution. We also tried to guess that the password would contain the text 256 and used this to limit our bruteforce space for AES key cracking. This unfortunately failed but was a cool idea! (If only we used the word santa instead).

Instead, we look at Santa's private keys and notice how the corresponding private key is his password with SHA256 encryption. This is much, much faster to bruteforce as we can generate potential private keys and attempt to sign and verify a test message. If our verification is successful, we will have our original password which we can then use to decrypt the AES cipertext directly.

Putting all of this together we write our Python script:

# Hackvent 2019 - Day 21
# Mo Beigi (https://mobeigi.com)

import math
import hashlib
from fastecdsa import keys, ecdsa, curve, point
from Crypto.Cipher import AES

# P256 pub keys
X = 0xc58966d17da18c7f019c881e187c608fcb5010ef36fba4a199e7b382a088072f
Y = 0xd91b949eaf992c464d3e0d09c45b173b121d53097a9d47c25220c0b4beb943c
Q = point.Point(X, Y, curve=curve.P256)

# AES
aes_ciphertext = b'\x1f\x2f\x7b\x5f\x0b\xfd\xee\xfa\x70\x1a\x7d\xb5\x7e\x29\xd5\xbd\x98\xf9\xa4\xaf\xc1\xbc\x18\xec\x71\xfe\xaf\x7d\xf9\xb5\xa6\x8d'
rounds = 256*256*256
salt = bytes('TwoHundredFiftySix', encoding='UTF8')

# Loop through rockyou password dump
with open('rockyou.txt', 'r', encoding='UTF8', errors='ignore') as f:
    for password in f:
        password = password.rstrip() # Strip ending new lines
        
        # Enforce length restriction
        if len(password) == math.sqrt(256):
            # Create possible private key
            # d = SHA256(password)
            m = hashlib.sha256()
            m.update(bytes(password, encoding='UTF8'))
            d = m.digest()
            
            # Sign and verify test message
            message = 'test'
            r, s = ecdsa.sign(message, int.from_bytes(d, byteorder='big'), curve=curve.P256)
            valid = ecdsa.verify((r, s), message, Q, curve=curve.P256)
            
            if valid:
                print(f"Santa's pass is: {password}")
                
                # Derive AES key using password
                key = hashlib.pbkdf2_hmac('sha256', bytes(password, encoding='UTF8'), salt, rounds)
                
                # Decipher AES ciphertext using key
                decipher = AES.new(key, AES.MODE_ECB)
                
                print(f'Flag is: {decipher.decrypt(aes_ciphertext)}')
                raise SystemExit()

Running the above gives us Santa's password and our flag after 30 seconds:

Santa's pass is: santacomesatxmas
Flag is: b'HV19{sry_n0_crypt0mat_th1s_year}'

Flag:

HV19{sry_n0_crypt0mat_th1s_year}