C 502: Existential Forgery Attack on RSA Signatures

What You Need

Any machine with Python 2.7 and openssl. I used a Mac. The easiest machine to set up is probably Kali or Ubuntu Linux.

Purpose

To learn how the Existential Forgery attack works against RSA signatures.

Generating RSA Keys

In a Terminal window, execute these commands to generate a private key, save it in a "YOURNAMEpkey.pem" file, view it, and parse it.

Replace "YOURNAME" with your own name.

openssl genrsa -out YOURNAMEpkey.pem
cat YOURNAMEpkey.pem
openssl asn1parse -in YOURNAMEpkey.pem
This reveals the RSA parameters, as labelled below in red.

Copying the Parameters

Copy the RSA parameters you generated into a text file so you can retrieve them later in the project.

Understanding RSA Signatures

If Bob wants to sign a message, he first generates an RSA key pair, including these values: Bob then writes a message x and calculates the signature s as shown below.

Anyone who receives the message can verify it using Bob's public key, as shown below.

If the result x' matches the original message x, the signature is valid.

Creating and Encoding a Message

In a Terminal window, execute these commands to create a message and display it in hexadecimal encoded form.

Replace "YOURNAME" with your own name.

python
msg = "Project 16 from YOURNAME"
xe = msg.encode("hex")
print xe
print len(xe)
Your encoded message appears, as highlighted in the image below, followed by its length.

Since we are using 512-bit RSA, the message must be 64 bytes or less. If it's too long, use a shorter version of your name.

In my example below, the length is 48 bytes, so this message is OK.

Signing the Message

In the Terminal running Python, execute these commands, replacing the hexadecimal values of n, d, and e with the values you generated above using openssl.

Notice the use of the "int" function to convert the hexadecimal strings to integers.

n = int("F78949DDF8808579FE5506052EB86995DF24FC03B40C7ECC1788E1FA4D174322F17BA15A5AC6005CA6150EE194D8E496EA4F0ACE06960ECD535297193EBD8BE3",16)
e = int("010001", 16)
d = int("3A8E387210C9DE494877B66FDD687459A6AAAA0EFA35867D23081764CD7DB63C83C80590713EEE185527E20CE473631E3FFA08CACCC462516A5BFB51F24541A1", 16)

x = int(xe, 16)
s = pow(x, d, n)
se = hex(s)
print se
Your signature appears as a long hexadecimal number, as shown below.

Verifying the Signature

In the Terminal running Python, execute these commands to verify the signature and print out the value of n you used.

Notice the stages of converting a numerical x' value back to readable text.

xpn = pow(s, e, n)
print "Numerical x':", xpn
xph = hex(xpn)
print "Hexadecimal string x':", xph
xpt = xph[2:-1]
print "Trimmed hex string x':", xpt
xpa = xpt.decode("hex")
print "ASCII x':", xpa

print "n in hex", hex(n)
The readable message is recovered, as shown below.

Performing the Existential Forgery Attack

In this attack, you choose a signature s and calculate the corresponding message x as shown below.

We'll use a signature of 0xf -- an unusual value starting with a lot of zeroes.

In the Terminal running Python, execute these commands to calculate x.

s = 0xf
xn = pow(s, e, n)
xh = hex(xn)
print "Hexadecimal string x:", xh
xt = xh[2:-1]
print "Trimmed hex string x:", xt
xa = xt.decode("hex")
print "ASCII x':", xa
The ASCII message is garbled nonsense, as shown below.

This attack won't fool a human who tries to read the message, but it might fool an automated system that merely validates the signature.

Verifying the Signature

In the Terminal running Python, execute these commands to verify the signature and print out the value of n you used.
xpn = pow(0xf, e, n)
xph = hex(xpn)
print "Hexadecimal string x':", xph
print "Hexadecimal string x :", xh

print "n in hex", hex(n)
The two hexadecimal "x" values match, as shown below.


C 501.1: Find four bytes (20 pts)

The flag is the four bytes redacted in the image above, in hex, like AABBCCDD

C 502.1: Sign with Your Name (10 pts)

My public key is below.
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAK2u1N6ZR6RiW1VXo+QynnveXCmCG7az
AhlXqCfBhcpNNDVBMjvm8cCjFrUdQUobbulGk/L6fImba1cHNF4zEKcCAwEAAQ==
-----END PUBLIC KEY-----
Convert your name to a number, as shown below.

Create a message that is correctly signed with your name as its signature.

Use the form below to get the flag.

Your name like this:

594f55524e414d45

Message like this:

3ceafc6720f418f86b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920


C 502.2: Sign a Message Starting With Your Initials (20 pts)

Use the same key as in the previous challenge.

Create a correctly signed message starting with your initials (3 characters) in the plaintext.

Use the form below to put your name on the WINNERS PAGE.

Signature like this:

4dfeeb2d92

Message like this:

594d01114e414d456b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920


Sources

The Padding Oracle Attack - why crypto is terrifying
Block cipher mode of operation - Wikipedia
PKCS #7: Cryptographic Message Syntax (section 10.3)


Posted 11-20-17 by Sam Bowne
Added to Crypto Hero 4-16-18 6:32 am
Ported to new scoring engine 7-8-19