This weekend was the Boston Key Party Ctf. There were a bunch of challenge, and my team did pretty well (top 10) even though we didn't have a lot of our regulars. Two of the problems involved signing a string "There is no need to be upset" using Elgamal signing.
The TLDR version is both failed in the duplicate checks.
Both problems required "proof of work" prior to the signing test:
- Server reads 9 bytes of random data and generates a base64 encoded version
- Sever sends the base64 to client (12 bytes)
- Client adds up to 8 bytes
- Server then verifies first 12 are the ones it sent
- Server computes SHA1 hash of all 20 bytes
- Hash must end with 24 bits of 0 to pass
Once you passed the proof of work you had to send the message ("There is no need to be upset") and signature (r and s). The format of the message and signature was json with Wood Island, and asn1 with Orient Heights. If the signature passed you were rewarded with the key.
Along with the server script and the key information, we were given a collection of valid signatures, lest we had to brute force up to a 1024 bit private key. However, even though the message that the server wanted was in the example signatures, the server checked that we weren't sending a duplicate signature.
Here in lies the flaw we used. Wood Island used the python json library to decode the string into a dict and the duplicate check was a simple "user_dict in list" check. Adding a field to the json was enough to pass the check. Orient Heights just compared the binary ASN1 encoding; once again adding a field caused it to fail.
Now for how you are supposed to solve them... Looking at the list of signatures, we noticed that there was a few that used the same value for r. Elgamal signing has a known issue that if you use the same value for r (really the random k), then you can compute the private key using Linear Congruence. There's a nice question and answer on cryto.stackexchange on how to do it. Of course I wasn't quite up to speed on my Linear Congruence, so I found a helpful page on how to solve them.
#!/usr/bin/python
from dsa_key import *
import dsa
import hashlib
from dsa_prime import *
from dsa import elgamal_verify as verify
import code
import json
DUPLICATES = open('sigs.txt', 'r').read().split('\n')[:-1]
DUPLICATES = map(json.loads, DUPLICATES)
#Read the signatures
with open("sigs.txt", "rb") as f:
lines = f.read().split('\n')[:-1]
d = map(lambda v: json.loads(v, encoding="utf8"), lines)
# Find only have valid
#working = [i for i in d if verify(**i)]
# I saved them off in a single json file to make things faster
working = json.load(open("working"))
d = working
# expected value
expected = "There is no need to be upset"
# The function to convert a string message into the hash for signing
hash_val = lambda m: int(hashlib.sha384(m.encode("utf8")).hexdigest(), 16)
e_hash = hash_val(expected)
r_list = [ i["r"] for i in working ]
dup_r = [ i for i in r_list if r_list.count(i)>1][0]
dups = [ i for i in working if i["r"]==dup_r]
import gmpy
from gmpy import mpz
from gmpy import gcd
g = mpz(GENERATOR)
p = mpz(SAFEPRIME)
s = [ mpz(i["s"]) for i in dups ]
r = [ mpz(i["r"]) for i in dups ]
m = [ mpz(hash_val(i["m"])) for i in dups ]
# SOLVING k(s[0] - s[1]) = (m[0] - m[1]) mod p-1
# ka = side2 mod p-1
a = s[0] - s[1]
side2 = m[0] - m[1]
num = gcd(a, p-1)
num = int(num)
print num
k_ = gmpy.divm(side2/num, a/num, (p-1)/num)
for i in range(0,num):
k = k_ + (i*(p-1)/num)
r_ = pow(g, k, p)
if r_ == r[0]:
print "FOUND K"
break
# solve xr = (m0 - ks0) mod p -1
side2 = m[0] - k * s[0]
num = int(gcd(r[0], p-1))
x_ = gmpy.divm(side2/num, r[0]/num, (p-1)/num)
for i in range(0, num):
x = x_ + (i*(p-1)/num)
y = pow(g, x, p)
if y == PUBKEY:
print "FOUND x"
break
def sign(m_str):
if type(m_str) in [str, unicode]:
m = hash_val(m_str)
else:
m = m_str
k = 55
r = pow(g, k, p)
s = gmpy.divm(m - x*r, k, p-1)
return {"s": s, "r":r, "m":m_str}