OverTheWireAdvent Santa’s Signature

• Tags: crypto
• Points: 174
• Solves: 77

Can you forge Santa’s signature?

Author: semchapeu

#!/usr/bin/env python3
import Crypto
from Crypto.PublicKey import RSA
import sys

try:
        with open("key",'r') as f:
                key = RSA.importKey(f.read())
except:
        rng = Crypto.Random.new().read
        key = RSA.generate(4096, rng)
        with open("key",'w') as f:
                f.write(key.exportKey().decode("utf-8"))

def h2i(h):
        try:
                return int(h,16)
        except Exception:
                print("Couldn't hex decode",flush=True)
                sys.exit()

header = \
"""Dear Santa,
Last christmas you gave me your public key,
to confirm it really is you please sign three
different messages with your private key.

Here is the public key you gave me:"""
print(header,flush=True)
print(key.publickey().exportKey().decode("utf-8"),flush=True)
ms = []

for i in range(1,4):
        m = h2i(input("Message %d you signed (hex encoded):" % i))
        if m in ms:
                print("I said different messages!",flush=True)
                sys.exit()
        s = [h2i(input("Signature %d:" % i))]
        if not key.verify(m,s):
                print("Looks like you aren't Santa after all!",flush=True)
                sys.exit()
        ms.append(m)

print("Hello Santa, here is your flag:",flush=True)
with open("flag",'r') as flag:
        print(flag.read(),flush=True)

---

Solution

Summary

It is difficult to compute RSA signature from RSA message without private key, but it is easy to compute message from signature with public key, since it is the RSA encryption operation. Thus we can compute RSA (message, signature) pairs as many times as we like.

Details

The program (running in the server) gives us a public key, and requests to give three (message, signature) pair generated with the corresponding private key.

Dear Santa,
Last christmas you gave me your public key,
to confirm it really is you please sign three
different messages with your private key.

Here is the public key you gave me:
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAmBtNAPIrIVzU2eK/W6gu
vYS3HNj8TiP3vvoVgt6IjMz6oldASBagsESrOm8+voCRaO+p+t/irOgK5bLQjY44
tzKI09vCMKkraagoPJtCupsUtHMA2UAVWuxihWh2tE1rYNhC63nHNRxAo5ViE6Pk
KALtYzNgAmNqT0SsblyJTL+xhoalCNZg/rfSHOf6lrYmUD/4DJgsAsZyhFYqUnMN
mYrIW5sbJZmtTm2Kpc/24xRSLycQSj9SKmws/GZCg/kXBy+LzP4zsOloiLRpVp6b
LyJ1XR708xnd/RuGgKvxp+NYpl7mmbKUIbowRKM4XjuMulIveA94+Y+KsFQJ/eSk
g58pKZ7ks6sHC6y3ogq8fxRSxeSUQiePaQNDZ6OwFRluhfDR90WMIeVPXE/NLV9L
O6fYeVNIMqZ67PtYHrxUcyworYx7+3QXcrAuvcnBCYP6zyvaXmWuhx0zcM2Xilta
29Is50peYYDe77prTCBYmiWj3q2/+LVOO5Oee9qTq9/XKBG0hcra/NO+x/mCu6CT
fZmga+uqHmenpL3swsrrIKn6WpHCGIDYxhLe+ZvZYUuFbigIdPLMnDIaUnMwiSlI
gvekuR774wustEz8kmEZz0KA/TKXGimw2StBqfU7q5d+7qpUdRRigjWGG32Csmby
IiUfTTa3tLq2zsoLOR+rEl0CAwEAAQ==
-----END PUBLIC KEY-----
Message 1 you signed (hex encoded):
Signature 1:
Looks like you aren't Santa after all!

It seemed to be difficult to recover secret key from the given public key. (FYI, you can use RsaCtfTool to find a weak key.)

Then we think the other way round: RSA signature algorithm is equivalent to RSA encryption algorithm, as follows:

• RSA sign = RSA decrypt: sign(Message, privkey) <-> (Message, decrypt(Message, privkey))
• RSA verify = RSA encrypt: verify((Message, Signature), pubkey) <-> Message == encrypt(Signature, pubkey)

So, we can create 3 different signatures first, and then compute message from the signatures, to create (message, signature) pair.

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from pwn import *
from base64 import b64decode

#p = process('./santas_signature.py')
p = remote('3.93.128.89', 1219)

p.recvuntil(b'Here is the public key you gave me:\n')
keybytes = p.recvuntil(b'-----END PUBLIC KEY-----')
key = RSA.importKey(keybytes)

plaintexts = [b'1', b'2', b'3'] # whatever

for plaintext in plaintexts:
    # message: ciphertext
    (ciphertext,) = key.encrypt(plaintext, 32)
    p.sendlineafter(':', ciphertext.hex())
    # signature: plaintext
    p.sendlineafter(':', plaintext.hex())

p.stream()

by Fukutomo

Additional Note

• RSA signature usage note: The vulnerability in this challenge indicates that the RSA signature algorithm should not be directly applied to the raw message. Instead, we should use
• Duality of signature / encryption: RSA uses the same algorithm for; this is not generalised to other public key encryption, e.g. ECC/ECDSA.