# 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}`