Rating:
# Santa's Signature
## Task
The task seems obvious we need to forge Santa's RSA signature.
Quickly checking the thing via netcat gives the following result.
```shell
nc 3.93.128.89 1219
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-----
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-----
Message 1 you signed (hex encoded):AAAAAAAAA
Signature 1:AAAAAA
Looks like you aren't Santa after all!
```
We are given a public key and need to provide 3 messages together with 2 valid RSA signatures.
Obviously the private key was not given.
We are also given the python script used at the server side
```python
#!/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)
```
## Analysis
Checking the script reveals that pycrypto is used. The code receives a message and checks/verifys if the signature is correct. Textbook RSA is used and the pycrypto documentation of verify found here (https://www.dlitz.net/software/pycrypto/api/current/Crypto.PublicKey.RSA._RSAobj-class.html) states
>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.
Ok so now we need to digg deeper how we can exploit that.
Some good answers can be found in following stackexchange posts:
https://crypto.stackexchange.com/questions/20085/which-attacks-are-possible-against-raw-textbook-rsa
>Eve knows the signature of some messages; e.g. the signature of 0 is 0, the signature of 1 is 1, the signature of n−1 is n−1, the signature of kemodN is k for 0≤k<N. This could be a nuisance by itself, or could help attacks 1 and 2.
So we could go with 0,1 and n-1 as messages and signature.
>Textbook RSA signature scheme is not secure considering Existential Unforgability under Chosen Message Attack. e.g. if attacker A chooses random x ∈ {1,2,...,n-1} and computes y = xe mod n, then sets m = y, σm = x then σm is a valid signature on m under the public key (e,n). The forgery is on a random message.
So I chose to go with the second approach and present 3 "constructed" messages.
## Attack
So first we saved the public key into a file (pubkey.txt) and extracted n and e.
```shell
openssl rsa -inform PEM -pubin -in day19/pubkey.txt -text -noout
RSA Public-Key: (4096 bit)
Modulus:
00:bb:58:db:df:d1:99:95:68:7d:5c:fa:4e:1e:66:
9a:64:46:2b:6c:da:9a:e8:a3:1f:e0:4d:b5:d4:d6:
24:95:9c:ad:b9:10:50:cb:bd:73:38:8f:15:f4:ee:
e2:d7:60:b8:86:38:68:03:38:fc:26:75:e4:a4:5b:
ab:ef:0d:f3:3c:b8:a6:54:1f:c1:f8:a7:d0:ab:77:
e8:e5:8a:96:cd:58:62:d3:a2:ee:b8:2b:f2:1b:09:
16:48:ed:ca:da:c3:32:1f:72:12:2a:53:ca:97:25:
73:86:bf:fd:a9:e1:d1:da:06:c5:5c:ae:ac:a3:ca:
c7:5e:96:46:81:22:64:e5:38:a6:b9:8e:32:6f:e4:
cd:8e:97:e2:e2:ca:d0:23:27:a9:54:f0:a3:10:2b:
38:9f:e2:22:f7:8d:5c:fb:b2:96:db:04:9c:01:49:
3b:32:e3:04:c6:e2:ae:36:fb:ca:79:36:5d:85:07:
aa:fd:90:9d:d2:8b:5a:b1:c0:57:93:d1:a6:b0:1c:
74:79:50:73:1b:cf:fd:e0:79:be:f5:e8:25:79:0b:
b5:0e:a2:e7:fc:76:68:bd:a0:1c:c8:86:ea:8e:e9:
ee:07:f2:a8:33:be:83:21:28:e1:99:c6:91:ca:2a:
5a:7c:42:66:fa:ef:7f:8c:f1:c0:1b:ef:1d:2d:4b:
9c:5a:bf:b4:e0:3f:62:00:50:44:b7:95:c1:03:6b:
b7:59:a6:8b:e3:f7:8f:ee:14:79:99:1f:50:3b:11:
fc:62:29:69:b6:d7:d0:25:8f:fb:f0:05:e8:f8:62:
6d:10:24:c5:2c:9e:f3:47:23:f5:26:af:3d:a9:dc:
92:25:5b:a6:c7:06:66:28:fd:ec:13:b9:a8:8d:36:
f6:d3:7d:13:0c:5f:f6:ee:ff:af:31:55:6d:73:3c:
80:41:dc:9b:0c:7c:e3:f1:a8:a7:1e:7d:92:3f:7c:
93:4c:e9:e3:35:3b:86:5a:f2:1c:b3:74:1a:e1:bb:
fb:f1:ec:d3:98:ba:1f:a6:c6:4b:a1:16:dc:c7:91:
55:d9:85:ee:89:aa:3c:7b:30:ff:58:1b:88:3a:50:
d9:86:a4:62:a1:db:37:2c:df:31:ee:03:50:a3:cc:
c3:9b:06:34:67:9e:28:69:cd:9d:3e:02:14:af:50:
2f:9c:36:c4:19:da:b2:0b:22:51:22:b9:d6:90:b1:
4c:5d:dc:b6:18:92:d2:14:c9:3e:ae:cc:0e:44:a1:
2d:a2:30:a6:a9:02:32:75:6e:fe:e4:ce:09:e0:58:
55:37:25:6d:36:e3:dc:2d:f5:23:17:e7:b9:f9:5e:
44:fa:98:84:70:0b:02:9d:0d:64:f5:01:c6:64:0b:
95:c5:7f
Exponent: 65537 (0x10001)
```
This also shows that a keylength is good enough and simple bruteforcing the private key would not work.
With RSACtfTool (https://github.com/Ganapati/RsaCtfTool) we can even extract n and e nicely formatted.
```shell
./RsaCtfTool.py --dumpkey --key pubkey.txt
[*] n: 764309505636990757633885195426269377200893159032473594524427777589208386859369198337793979776360283940219097258292297229825495359288596352941643878314775107386154592931007406780194319473901088883341304454564213045041312703126354959960122202779815343426773286619828454710690050324159354012394136805678590433175427541436425419775496164091196119629606005322081131389926689699133246010048692194403769714218649309027800857269231221632342668415250150387144719977816560121463080121940072381067542506243809429842338218027169702473965752132491212589280850909325246564283620197006527722742537942878118985157343851762083942322571718342548882503645820569691741325998673691931421872363056438777196815793552061214918851019701408374409829733895222705639617316908330733856363017643246376845411113449176952432039791967618970434395872691385644622945697496362380594772525334652428513834915912553472257249326221476377602977430399496057037174335806663845067260392654735159232665772916537456137988845529834265955724868323389715459655296861179396765680282600838233730374347396310477185194413173148024402906787377482770814012496270581069060243549212392408630363990071065557518435346092026643766130797372615225486176564056580537697821520596658341129364030847
[*] e: 65537
```
So now we can do an ugly python hack to solve the problem:
```python
from pwn import *
c=remote('3.93.128.89',1219)
e=65537
x3=0x77737373656572727272206d61727363680a
x2=0x726f7361205363687765696e6368656e0a
x1=0x6f6c6c6120776f726c640a
n=764309505636990757633885195426269377200893159032473594524427777589208386859369198337793979776360283940219097258292297229825495359288596352941643878314775107386154592931007406780194319473901088883341304454564213045041312703126354959960122202779815343426773286619828454710690050324159354012394136805678590433175427541436425419775496164091196119629606005322081131389926689699133246010048692194403769714218649309027800857269231221632342668415250150387144719977816560121463080121940072381067542506243809429842338218027169702473965752132491212589280850909325246564283620197006527722742537942878118985157343851762083942322571718342548882503645820569691741325998673691931421872363056438777196815793552061214918851019701408374409829733895222705639617316908330733856363017643246376845411113449176952432039791967618970434395872691385644622945697496362380594772525334652428513834915912553472257249326221476377602977430399496057037174335806663845067260392654735159232665772916537456137988845529834265955724868323389715459655296861179396765680282600838233730374347396310477185194413173148024402906787377482770814012496270581069060243549212392408630363990071065557518435346092026643766130797372615225486176564056580537697821520596658341129364030847
y1=x1**e %n
y2=x2**e %n
y3=x3**e %n
c.recvuntil(':')
c.sendline(format(y1,'x'))
c.recvuntil(':')
c.sendline(format(x1,'x'))
c.recvuntil(':')
c.sendline(format(y2,'x'))
c.recvuntil(':')
c.sendline(format(x2,'x'))
c.recvuntil(':')
c.sendline(format(y3,'x'))
c.recvuntil(':')
c.sendline(format(x3,'x'))
c.interactive()
```
Simply calculate y `(y=x**e%n)` and send y as mesage and x as signature. x are just some random messages.
And we get the flag without using the edge cases I think the flag suggests.
The flag is **AOTW{RSA_3dg3_c4s3s_ftw}**.
