I took part in the OverTheWire Advent Bonanza 2019. All in all, the CTF was very pleasant because the challenges were interesting to solve, there was quite some time available as well (I spent about two weeks on and off on it) and I also managed to solve a few challenges as well.
The following write-up is about the challenge from day 19: santa's signature
Description
Can you forge Santa's signature?
Along with the IP address/port there was also the Python code running on the server given which made the challenge even easier to solve.
#!/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)
The public key that is presented by the server is as follows:
-----BEGIN PUBLIC KEY----- MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAu1jb39GZlWh9XPpOHmaa ZEYrbNqa6KMf4E211NYklZytuRBQy71zOI8V9O7i12C4hjhoAzj8JnXkpFur7w3z PLimVB/B+KfQq3fo5YqWzVhi06LuuCvyGwkWSO3K2sMyH3ISKlPKlyVzhr/9qeHR 2gbFXK6so8rHXpZGgSJk5TimuY4yb+TNjpfi4srQIyepVPCjECs4n+Ii941c+7KW 2wScAUk7MuMExuKuNvvKeTZdhQeq/ZCd0otascBXk9GmsBx0eVBzG8/94Hm+9egl eQu1DqLn/HZovaAcyIbqjunuB/KoM76DISjhmcaRyipafEJm+u9/jPHAG+8dLUuc Wr+04D9iAFBEt5XBA2u3WaaL4/eP7hR5mR9QOxH8YilpttfQJY/78AXo+GJtECTF LJ7zRyP1Jq89qdySJVumxwZmKP3sE7mojTb2030TDF/27v+vMVVtczyAQdybDHzj 8ainHn2SP3yTTOnjNTuGWvIcs3Qa4bv78ezTmLofpsZLoRbcx5FV2YXuiao8ezD/ WBuIOlDZhqRiods3LN8x7gNQo8zDmwY0Z54oac2dPgIUr1AvnDbEGdqyCyJRIrnW kLFMXdy2GJLSFMk+rswORKEtojCmqQIydW7+5M4J4FhVNyVtNuPcLfUjF+e5+V5E +piEcAsCnQ1k9QHGZAuVxX8CAwEAAQ== -----END PUBLIC KEY-----
Analysis
My first guess for this challenge was that this involves some "RSA exponent three attack" (https://www.johndcook.com/blog/2019/03/06/rsa-exponent-3/) but in fact it was actually even easier. RSA is prone to a lot of attacks if implemented and used "raw", i. e. textbook style. The crypto library used is https://github.com/dlitz/pycrypto, so I downloaded that library and looked at the verify function.
def verify(self, M, signature):
"""Verify the validity of an RSA signature.
:attention: this function performs the plain, primitive RSA encryption
(*textbook*). In real applications, you always need to use proper
cryptographic padding, and you should not directly verify data with
this method. Failure to do so may lead to security vulnerabilities.
It is recommended to use modules
`Crypto.Signature.PKCS1_PSS` or `Crypto.Signature.PKCS1_v1_5` instead.
"""
The function description confirms the suspicion that it is vulnerable which means that we are on the right track.
Verification in case of RSA works as follows:
If s^e mod n is equal to m mod n then the signature is valid (s is the signature, e is the public exponent, n is is the public modulus).
Solution
It is obvious that the equation is true for s = m = 0 and s = m = 1. However, we have to give three forged signatures and messages. But there is another special case s = -1 because the (-1)^e = -1 if e is odd. Since e = 65537, this is the case. However, the server does not accept -1 as a message:
Message 1 you signed (hex encoded):-1 Signature 1:-1 Looks like you aren't Santa after all!
This can be solved by calculating -1 mod n so that the message is positive. This can be calculated easily with a bit of Python:
>>> hex(pow(-1, e, n))
bb58dbdfd19995687d5cfa4e1e669a64462b6cda9ae8a31fe04db5d4d624959cadb91050cbbd73388f15f4eee2d760b88638680338fc2675e4a45babef0df33cb8a6541fc1f8a7d0ab77e8e58a96cd5862d3a2eeb82bf21b091648edcadac3321f72122a53ca97257386bffda9e1d1da06c55caeaca3cac75e9646812264e538a6b98e326fe4cd8e97e2e2cad02327a954f0a3102b389fe222f78d5cfbb296db049c01493b32e304c6e2ae36fbca79365d8507aafd909dd28b5ab1c05793d1a6b01c747950731bcffde079bef5e825790bb50ea2e7fc7668bda01cc886ea8ee9ee07f2a833be832128e199c691ca2a5a7c4266faef7f8cf1c01bef1d2d4b9c5abfb4e03f62005044b795c1036bb759a68be3f78fee1479991f503b11fc622969b6d7d0258ffbf005e8f8626d1024c52c9ef34723f526af3da9dc92255ba6c7066628fdec13b9a88d36f6d37d130c5ff6eeffaf31556d733c8041dc9b0c7ce3f1a8a71e7d923f7c934ce9e3353b865af21cb3741ae1bbfbf1ecd398ba1fa6c64ba116dcc79155d985ee89aa3c7b30ff581b883a50d986a462a1db372cdf31ee0350a3ccc39b0634679e2869cd9d3e0214af502f9c36c419dab20b225122b9d690b14c5ddcb61892d214c93eaecc0e44a12da230a6a90232756efee4ce09e0585537256d36e3dc2df52317e7b9f95e44fa9884700b029d0d64f501c6640b95c57e
Now that we have all three messages and signatures, the server gives us the flag: AOTW{RSA_3dg3_c4s3s_ftw}