Break textbook RSA signature.

Information

  • category : crypto
  • points : 174

Description

Can you forge Santa’s signature?

Service: nc 3.93.128.89 1219

File: santas_signature.py

Writeup

santas_signature.py :

#!/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)

Launch the script:

./santas_signature.py 
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-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAtdUNE3zx+oML4in19NmX
qz8u9qoYyM1ykqDibGVcEKMHhqRlCMbFEICxCaeknl7EniQY5m1Z8OtzCcNOsWTa
Dpbr4ofryuCnhVTXtbcQvMl0gmT9hNr3S7Sh1O66sA5G7YwRipab41Ri+tq6F32m
t1zCP5AUaoNcaXbH6mJJ+7KCWqqdHFZHcRdAYd/Q+qWxRm6JCp5/ghHWWH9B9msa
qpR+tUO6u6ur5epkwjFOErBb00+NT2KCcJlEw7Uzf9weHNid+yQcXR2biKpivNeE
dGNNkeLqg5oAv8Jgx8dBrETtU/rjj4gRIfo7W2gGnykry5yqDYt+45DHCeLJRXtJ
nYeaFVWmhmx6FlerFdADCz24oArgZhwWSnMgb4k2tOFflZnKr4lw0S46tObPxGrp
kL8HFlESdPw84BBJcj85tkn3uixH58PGi+4zdO0i5ZpVfIejSC/x0TNd2AHPYVt6
ZisvFSFwhedPnQfKMKS6zTgPFfC1vkQw6EAP/Q8vCMRDh4ErtZu//a6o/VWKNONk
FaTNqmi1wpl1p1KdIQUo25GKrx5ZhTNCWsVE7QcLvclaHCaCBCmNGkpxiKST+X9e
36CfPUj+1VAjp1YJHqEvgUk8s030n17cFnCAzexGAINDlmlKohOcqcm82z/OruhP
Ju4d3uGsgd6WSAF9pDMHdvkCAwEAAQ==
-----END PUBLIC KEY-----
Message 1 you signed (hex encoded):00
Signature 1:00
Traceback (most recent call last):
  File "./santas_signature.py", line 39, in <module>
    if not key.verify(m,s):
  File "/home/meowmeow/.local/lib/python3.8/site-packages/Crypto/PublicKey/RSA.py", line 369, in verify
    raise NotImplementedError("Use module Crypto.Signature.pkcs1_15 instead")
NotImplementedError: Use module Crypto.Signature.pkcs1_15 instead

Wow, error, why? Because I use pycryptodome since pycrypto is old, and in pycryptodome the function verify has been deprecated.

To test the program we can create a virtualenv and install pycrypto, however we don’t need to do that.

Let’s analyze what the script does:

  1. create/read RSA key.
  2. read three pairs of message/signature.
  3. check that the signatures are valid.

What could go wrong? well, if verify in pycryptodome has been deprecated there’s a reason. If we go to the official pycrypto documentation we can see the following line:

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.

Why is this insecure? simply because there’s no padding, and without knowing the private key we can try to create a valid signature.

In this case we need to find three valid signatures.

The first one that I found is:

message: 01
signature: 01

The signature is simply \(1\) since \(m^d \pmod n \equiv 1^d \pmod n \equiv 1 \pmod n\).

A trick I tried to submit is:

message: n + 1
signature: n + 1

Because this is equal as the the pair \(01, 01\). However the library (rightfully) refuses to sign a message greater than \(n\).

The other easy pair (message,signature) is:

message: 00
signature: 00

No need to explain why this works.

The latest signature is the following:

message: n - 1
signature: n - 1

This works because \((n - 1) \equiv -1 \pmod n\).

\((-1)^d \pmod n \equiv 1 \pmod n\) if \(d\) is even.

\((-1)^d \pmod n \equiv -1 \pmod n \equiv (n - 1) \pmod n\) if \(d\) is odd.

\(d\) is odd because is the multiplicative inverse of \(e \pmod{\varphi(n)})\), where \(\varphi(n) = (p-1) * (q-1)\) is even.

Another way was to choose a random signature and compute the message as:

\(m \equiv s^e \pmod n\).

Exploit

#!/usr/bin/env python
from Crypto.PublicKey import RSA
from pwn import remote, log

conn = remote('3.93.128.89', 1219)
conn.recvuntil(b'gave me:\n')
pubkey = RSA.import_key(conn.recvuntil(b'END PUBLIC KEY-----'))
mod = pubkey.n

msg_sig = [1, 1, 0, 0, mod - 1, mod - 1]
for ms in msg_sig:
    conn.sendline(hex(ms))
log.info(conn.recvall().decode())

Output:

Message 1 you signed (hex encoded):Signature 1:Message 2 you signed (hex encoded):Signature 2:Message 3 you signed (hex encoded):Signature 3:Hello Santa, here is your flag:
    AOTW{RSA_3dg3_c4s3s_ftw}

Flag

AOTW{RSA_3dg3_c4s3s_ftw}