# 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.
```shellnc 3.93.128.89 1219Dear Santa,Last christmas you gave me your public key,to confirm it really is you please sign threedifferent messages with your private key.
Here is the public key you gave me:-----BEGIN PUBLIC KEY-----MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAu1jb39GZlWh9XPpOHmaaZEYrbNqa6KMf4E211NYklZytuRBQy71zOI8V9O7i12C4hjhoAzj8JnXkpFur7w3zPLimVB/B+KfQq3fo5YqWzVhi06LuuCvyGwkWSO3K2sMyH3ISKlPKlyVzhr/9qeHR2gbFXK6so8rHXpZGgSJk5TimuY4yb+TNjpfi4srQIyepVPCjECs4n+Ii941c+7KW2wScAUk7MuMExuKuNvvKeTZdhQeq/ZCd0otascBXk9GmsBx0eVBzG8/94Hm+9egleQu1DqLn/HZovaAcyIbqjunuB/KoM76DISjhmcaRyipafEJm+u9/jPHAG+8dLUucWr+04D9iAFBEt5XBA2u3WaaL4/eP7hR5mR9QOxH8YilpttfQJY/78AXo+GJtECTFLJ7zRyP1Jq89qdySJVumxwZmKP3sE7mojTb2030TDF/27v+vMVVtczyAQdybDHzj8ainHn2SP3yTTOnjNTuGWvIcs3Qa4bv78ezTmLofpsZLoRbcx5FV2YXuiao8ezD/WBuIOlDZhqRiods3LN8x7gNQo8zDmwY0Z54oac2dPgIUr1AvnDbEGdqyCyJRIrnWkLFMXdy2GJLSFMk+rswORKEtojCmqQIydW7+5M4J4FhVNyVtNuPcLfUjF+e5+V5E+piEcAsCnQ1k9QHGZAuVxX8CAwEAAQ==-----END PUBLIC KEY-----Message 1 you signed (hex encoded):AAAAAAAAASignature 1:AAAAAALooks 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 python3import Cryptofrom Crypto.PublicKey import RSAimport 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 threedifferent 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.
```shellopenssl rsa -inform PEM -pubin -in day19/pubkey.txt -text -nooutRSA 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:7fExponent: 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:
```pythonfrom pwn import *
c=remote('3.93.128.89',1219)e=65537
x3=0x77737373656572727272206d61727363680ax2=0x726f7361205363687765696e6368656e0ax1=0x6f6c6c6120776f726c640a
n=764309505636990757633885195426269377200893159032473594524427777589208386859369198337793979776360283940219097258292297229825495359288596352941643878314775107386154592931007406780194319473901088883341304454564213045041312703126354959960122202779815343426773286619828454710690050324159354012394136805678590433175427541436425419775496164091196119629606005322081131389926689699133246010048692194403769714218649309027800857269231221632342668415250150387144719977816560121463080121940072381067542506243809429842338218027169702473965752132491212589280850909325246564283620197006527722742537942878118985157343851762083942322571718342548882503645820569691741325998673691931421872363056438777196815793552061214918851019701408374409829733895222705639617316908330733856363017643246376845411113449176952432039791967618970434395872691385644622945697496362380594772525334652428513834915912553472257249326221476377602977430399496057037174335806663845067260392654735159232665772916537456137988845529834265955724868323389715459655296861179396765680282600838233730374347396310477185194413173148024402906787377482770814012496270581069060243549212392408630363990071065557518435346092026643766130797372615225486176564056580537697821520596658341129364030847
y1=x1**e %ny2=x2**e %ny3=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}**.