Proj 16: Existential Forgery Attack on RSA Signatures (15 pts. + 30 pts. extra credit)

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.

Saving a Screen Image (Image 16A)

Make sure you can see the hexadecimal value for n, as shown above.

Capture a full-screen image.

YOU MUST SUBMIT A FULL-SCREEN IMAGE FOR FULL CREDIT!

Save the image with the filename "YOUR NAME Proj 16a", replacing "YOUR NAME" with your real name.

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.

Saving a Screen Image (Image 16B)

Make sure you can see these two required items, as shown above:

Capture a full-screen image.

YOU MUST SUBMIT A FULL-SCREEN IMAGE FOR FULL CREDIT!

Save the image with the filename "YOUR NAME Proj 16b", replacing "YOUR NAME" with your real name.

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.

Saving a Screen Image (Image 16C)

Make sure you can see these four required items, as shown above:

Capture a full-screen image.

YOU MUST SUBMIT A FULL-SCREEN IMAGE FOR FULL CREDIT!

Save the image with the filename "YOUR NAME Proj 16c", replacing "YOUR NAME" with your real name.

Challenge 1: Sign with Your Name (10 pts. extra credit)

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 put your name on the WINNERS PAGE.

Your name like this:

594f55524e414d45

Message like this:

3ceafc6720f418f86b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920

Saving a Screen Image (Image 16D)

Save a whole-screen image of the winners page showing your name, as shown below, with the filename "YOUR NAME Proj 16d".

Challenge 2: Sign a Message Starting With Your Initials (20 pts. extra credit)

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

Saving a Screen Image (Image 16E)

Save a whole-screen image of the winners page showing your name, as shown below, with the filename "YOUR NAME Proj 16e".

Turning in your Project

Email the images to cnit.141@gmail.com with the subject line: Proj 14 from YOUR NAME.

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