Business CTF 2022: Bleichenbacher's '06 RSA signature forgery - BBGun06

In this blog post, we'll discuss the solution to the easy difficulty crypto challenge BBGun06, which requires exploiting a deprecated RSA signature verification code using CVE-2006-4339.

Description 📄

We have received reports from CloudCompany that resources are involved in malicious activity similar to attempting unauthorised access to remote hosts on the Internet. We have since shut down the server and locked the SA. While we were trying to investigate what the entry point was, we discovered a phishing email from CloudCompany's IT department. You've since notified the vendor, and they've provided the source code of the email signing server for a security assessment. We've identified an outdated RSA verification code implementation, which we believe could be the cause of why the threat actors were able to impersonate the vendor. Can you replicate the attack and notify them of any possible misuse?

🎮 PLAY THE TRACK

The idea 💡

A digital signature is a type of electronic signature where a mathematical algorithm is routinely used to validate the authenticity and integrity of a message (such as an email, credit card transaction, or digital document). There are many popular external libraries used by developers to implement such security features in their applications, and I thought it would be interesting to investigate them. As I was reading up on new bugs in such libraries, I came across this

Loading Preview...

The application at-a-glance 🔍

When we try to connect to the tcp server with something like nc, an email appears with 2 hearers. 

┏━[~]
┗━━ ■ nc 0.0.0.0 1337
signature: 7685086f956ed78dacd1254a2b8f556ef3da0b7e382fcc27e59bf9cae46171a3f3f61052802f3fb87d210bd582d4f181a511a6bd62009198f7701e7a837ddd9784f0fd5d2f97153d64e92e099e693bec76a3a3ab9da58596aa74b897fdbe2856654628d6ae2bad744a8aa085f71afaf2a55bf6e0d739e4772b0874d60a98184f75651273780b135fbacf7c0ce3d7cbfa88e2942263caa5f4b0501bf70bb91338e375084ac399b157afe942984f759a5283f9d0a0d3bd32899baf4dbf0eece1de0fe4c0cc10212309ed0b77f1f7b9340e5d1090db1408564a8f8d622b1a498023db34bfe4e69598b3db551bde74b01ae32b38c2cdd4115d1def554af755634232
certificate:
-----BEGIN PUBLIC KEY-----
MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKCAQEAphfp+E9AeBWTLQs066Yq
I8uDFbwU3Tj3lnea4FjU7SF6+PEa9qeYvUqFRY57gtRm1kN6LG9XMPZHUOo8qqSq
rMVG715qMWYjUDu6zCBPV3c6WUDik1mNOg4kbO8r3OEb/vrP3lixV0icQM69rEgH
nQPIENnh6fGDM9oXEZy7xl4IKDhoFwp6V33KW0b+HQzxAz1Qe0sty7rZAnHZUvop
H07+KRgTqt2KOrf2HYF9qZHX1ybBB4qrOKQIn8IAs0ErRIGjjCqaDwYUwnz59sT8
qtgIJQoxOifIvLj0oX5aNdtpr2dfddk4RVttSgkYUb15VQlvXCWW60uOnMHA/ue+
4QIBAw==
-----END PUBLIC KEY-----
From: IT Department <it@cloudcompany.com>
To: j.smith@sheesh.gov.edu
Subject: Confirm your identity
...

The server asks us to enter a signature in hex. We can try to enter a random signature. A message appears that an error has occurred.

Enter the signature as hex: aaaa

An error occurred

At this point, we need to start looking at the source code to understand how things work.

Analyzing the source code 📖

There are 4 files available: server.py, encyrption.py, email.txt, logo.png. The email and logo are only used for the story, so we are going to focus on the other 2.

server.py

Looking at the server.py script, we see that the basic workflow is as follows:

1. An RSA object is created.

2. The phishing email is parsed.

3. The email headers are generated and added to the email.

4. The server asks for a valid signature. If the signature passes the tests, we get the flag.

This is translated into code:

   rsa = RSA(2048)

   user, data = parseEmail() 

   signature = rsa.sign(user)
   rsa.verify(user, signature)

   headers = generateHeaders(rsa, signature)

   valid_email = headers + data 
   sendMessage(s, valid_email + "\n\n")

   try: 
      forged_signature = receiveMessage(s, "Enter the signature as hex: ") 
      forged_signature = bytes.fromhex(forged_signature) 
   if not rsa.verify(user, forged_signature): 
      sendMessage(s, "Invalid signature") 
   if different(rsa, signature, forged_signature): 
      sendMessage(s, FLAG) 
   except: 
      sendMessage(s, "An error occurred") 

The objective of the challenge is pretty clear. Our goal is to find a way to forge a signature. To do that, we are going to focus on step 4.

encryption.py

Let's check out how the verification process works. If we look at the encryption.py script, we see that after decrypting the signature, the code uses a regex to check if the padding is correct.

   def verify(self, message, signature):
      keylength = len(long_to_bytes(self.n))
      decrypted = self.encrypt(signature)
      clearsig = decrypted.to_bytes(keylength, "big")

      r = re.compile(b'\x00\x01\xff+?\x00(.{15})(.{20})', re.DOTALL)
      m = r.match(clearsig)

      if not m:
         raise VerificationError('Verification failed')

      if m.group(1) != self.asn1:
         raise VerificationError('Verification failed')

      if m.group(2) != sha1(message).digest():
         raise VerificationError('Verification failed')

      return True

For the signature to be valid, the decrypted version must start with \x00\x01, continue with 1 or more \xff bytes, a \x00 byte, and finally the ANSI blob and the SHA1 hash of the signed message.

When testing how the regex works, we observe that after we craft a payload that passes the above checks and append random data, the verification process will succeed. An example of a payload would be:

00 01 FF FF ... FF FF 00 ASN HASH GARBAGE

The GARBAGE part will be crucial during the exploitation phase of this verification process. Also, something important to note is the public exponent. In our case it's e = 3. 

Searching for the bugs 👾

After analyzing the source code, it is possible to exploit the vulnerability, but a good strategy would be to search if something similar has been exploited before. If we google BBGun06 signature forgery, we will come across this

Loading Preview...

All you have to do is build a message, take the cube root of that figure, and round up. 

Exploitation 🔓

Connecting to the server

A pretty basic script for connecting to the server with pwntools:

if __name__ == '__main__':
    r = remote('0.0.0.0', 1337)
    pwn()

Getting the public key

When someone connects to the server, a signature and the public key are computed. To obtain the public key, we can use:

def getPublicKey(): 
   for _ in range(2): 
   r.recvline() 

   public_key = "" 
   for _ in range(9): 
      public_key += r.recvline().decode()

   key = RSA.import_key(public_key) 
   return key 

Forging the signature

To create a valid signature, as mentioned above, we need to find a plaintext whose cubic root passes all tests. For this purpose, we can first create a plaintext that satisfies the regex.

00 01 FF FF ... FF FF 00 ASN HASH

Using python: 

   block = b'\x00\x01\xff\x00' + ASN1 + sha1(message).digest()

After that, we can append random bytes so that the cubic root of the output does not change the important parts. 

   key_length = len(bin(n)) - 2 
   garbage = (((key_length + 7) // 8) - len(block)) * b'\xff'

Finally we can calculate the cubic root and send the signature to the server. The final function is: 

def forge_signature(message, n, e): 
   key_length = len(bin(n)) - 2
   block = b'\x00\x01\xff\x00' + ASN1 + sha1(message).digest()
   garbage = (((key_length + 7) // 8) - len(block)) * b'\xff'
   block += garbage

   pre_encryption = bytes_to_long(block)
   forged_sig = iroot(pre_encryption, e)[0]

   return long_to_bytes(forged_sig)

Remember that one of the reasons this attack works is that the exponent is very small. This gives us the ability to completely ignore the public key and the operation in .

Sending the signature

def sendForgedSignature(forged_signature): 
   forged_signature = forged_signature.hex().encode()   
   r.sendlineafter(b"Enter the signature as hex: ", forged_signature) 

Getting the flag

A final summary of everything said above:

1. We obtain the public key.

2. We forge the signature.

3. We send the forged signature and get the flag.

This summary can be represented by code using the pwn() function.

def pwn(): 
   public_key = getPublicKey() 
   n = public_key.n 
   e = public_key.e 
   user = b"IT Department <it@cloudcompany.com>"
   forged_signature = forge_signature(user, n, e) 
   assert verify(user, forged_signature, n, e)     
   sendForgedSignature(forged_signature) r.interactive()
   r.interactive()

The final script is:

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.PublicKey import RSA
from hashlib import sha1
from gmpy2 import iroot
from pwn import *
import re

ASN1 = b"\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14"


class CryptoError(Exception):
    """Base class for all exceptions in this module."""


class VerificationError(CryptoError):
    """Raised when verification fails."""


def getPublicKey():
    for _ in range(2):
        r.recvline()

    public_key = ""
    for _ in range(9):
        public_key += r.recvline().decode()

    key = RSA.import_key(public_key)
    return key


def forge_signature(message, n, e):
    key_length = len(bin(n)) - 2
    block = b'\x00\x01\xff\x00' + ASN1 + sha1(message).digest()
    garbage = (((key_length + 7) // 8) - len(block)) * b'\xff'
    block += garbage

    pre_encryption = bytes_to_long(block)
    forged_sig = iroot(pre_encryption, e)[0]

    return long_to_bytes(forged_sig)


def verify(message, signature, n, e):
    keylength = len(long_to_bytes(n))
    encrypted = bytes_to_long(signature)
    decrypted = pow(encrypted, e, n)
    clearsig = decrypted.to_bytes(keylength, "big")

    r = re.compile(b'\x00\x01\xff+?\x00(.{15})(.{20})', re.DOTALL)
    m = r.match(clearsig)

    if not m:
        raise VerificationError('Verification failed')

    if m.group(1) != ASN1:
        raise VerificationError('Verification failed')

    if m.group(2) != sha1(message).digest():
        raise VerificationError('Verification failed')

    return True


def sendForgedSignature(forged_signature):
    forged_signature = forged_signature.hex().encode()
    r.sendlineafter(b"Enter the signature as hex: ", forged_signature)


def pwn():
    public_key = getPublicKey()
    n = public_key.n
    e = public_key.e
    user = b"IT Department <it@cloudcompany.com>"
    forged_signature = forge_signature(user, n, e)
    assert verify(user, forged_signature, n, e)
    sendForgedSignature(forged_signature)
    r.interactive()


if __name__ == "__main__":
    r = remote('0.0.0.0', 1337)
    pwn()

Unintended solutions and patching 🧯

Last-minute changes

A patch for the challenge was released at CTF. Let's look at the differences between BBGun06 and BBGun06 Revenge (the patched version) and try to figure out what went wrong.
BBGun:

    try:
        forged_signature = receiveMessage(s, "Enter the signature as hex: ")
          forged_signature = bytes.fromhex(forged_signature)

          if not rsa.verify(user, forged_signature):
            sendMessage(s, "Invalid signature")

          if (forged_signature != signature[len("signature: "):]):
            sendMessage(s, FLAG)
    except:
        sendMessage(s, "An error occurred")

Where the signature is generated using:

def generateHeaders(rsa, user):
    signature = rsa.sign(user)
    rsa.verify(user, signature)
    signature = f"signature: {signature.hex()}\n"

In contrast BBGun06 Revenge:

    try:
        forged_signature = receiveMessage(s, "Enter the signature as hex: ")
          forged_signature = bytes.fromhex(forged_signature)

          if not rsa.verify(user, forged_signature):
            sendMessage(s, "Invalid signature")

          signature = signature[len("signature: "):].strip()
          if (forged_signature.hex() != signature):
            sendMessage(s, FLAG)
    except:
        sendMessage(s, "An error occurred")

In making some last-minute changes, I overlooked the type checking on the signature verification routine. This resulted in players being able to submit existing signatures from the email headers, bypass the verification process, and retrieve the flag. Thanks to Hilbert, I was able to quickly fix the bug during the CTF, and everything ran smoothly after that. Or did they?

Maths gone wrong

Unfortunately, I found another bug after the patch. I didn't know it during the CTF, but apparently in the patched version it was possible to send the already computed signature plus n (the public exponent) and get the flag. This is true, because if we look at the following lines of the revenge challenge:

          if not rsa.verify(user, forged_signature):
            sendMessage(s, "Invalid signature")

          signature = signature[len("signature: "):].strip()
          if (forged_signature.hex() != signature):
            sendMessage(s, FLAG)

The new payload signature + n would pass the first if statement since it would be reduced by n, so , and it would pass the second if statement because signature + n != signature. Lesson learned: don't change the source code 1 day before the CTF. And that’s a wrap for this challenge write-up!