C 502: Existential Forgery Attack on RSA Signatures (10 pts + 20 extra)

What You Need

Purpose

Generating RSA Keys

Replace "YOURNAME" with your own name.

openssl genrsa -out YOURNAMEpkey.pem 512
cat YOURNAMEpkey.pem
openssl rsa -in YOURNAMEpkey.pem -text

Working with the Public Key

openssl rsa -in YOURNAMEpkey.pem -out YOURNAMEpublic.pem -pubout
cat YOURNAMEpublic.pem
openssl rsa -pubin -text < YOURNAMEpublic.pem 

Copying the Parameters

Understanding RSA Signatures

• Public key: n and e
• Private key: d

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

Replace "YOURNAME" with your own name.

python3
msg = b"Hello from YOURNAME"
xe = msg.hex()
print(xe)
print(len(xe))

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 38 bytes, so this message is OK.

Signing the Message

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

n = int("B6676AAD44AA71E8F5360A777F8C2C4FBA69AC5A7B36FD5436B03E6F629F02B9B2C5728F2EBD44D36FEFD75F609741E7D5A5FEA8D2D25AFAC80FB3969864C9F3",16)
e = int("010001", 16)
d = int("A863F4B19CD0957470DBC0F1ECC825283D79CCE9831292F029C4AEFEF956BE95CBFBCCE074966F17B877B765EFF54054A1439E5C0963767F297FF95F572EC291", 16)

x = int(xe, 16)
s = pow(x, d, n)
se = hex(s)
print(se)

Verifying the Signature

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("x':", xph)
print("msg from x'", bytearray.fromhex(xph[2:]))

Performing the Existential Forgery Attack

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:]
print("Trimmed hex string x:", xt)
xa = bytes.fromhex(xt)
plaintext = ""
for b in xa:
  if b < 128:
    c = chr(b)
  else:
    c = "*"
  plaintext += c

print("ASCII x':", plaintext)

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

xpn = pow(0xf, e, n)
xph = hex(xpn)
print("x':", xph)
print("x :", xh)

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 When you submit correct values, the flag will appear, covered by a green rectangle in the image below.

C 502.2: Sign a Message Starting With "ABC" (20 pts extra) Use the same key as in the previous challenge. Create a correctly signed message starting with "ABC" (3 characters) in the plaintext. Use the form below to get the flag. Signature like this: 4dfeeb2d92 Message like this: 594d01114e414d456b937a14fa0703df352b04f7d1e6a1e3bdd2e6f36e3da543800a6b07b3db36b372e934dfeeb2d920

Sources