### EBCTF 2013 finals – Crypto 300

21 Aug 2013 @ 10:11 PM

Given challenge is an implementation of ECDSA, where we are given an implementation in python and a list of signed messages for level 0 access. Our aim is to create/forge a signed message with level 1 access. We can see from the source code that, there are 2 users with level 1 access. Cracking those MD5 hashes gives us the username as

Butler : 98c131f9fb31f732b136f87e64ff686a
Kevin : f1cd318e412b5f7226e5f377a9544ff7

Now our main protection comes into picture – ECDSA. As far as the algorithm parameters are concerned, we don’t have any parameters available (not even public params!!). Our first challenge will be to figure out the params.

Looking at the ecdsa.py we can verify that the curve we are dealing with is $y^2 = x^3 + ax + b \pmod p$. From service.py we can see that 3 points (G, Q and R) are given, which should be points on the curve. From these 3 point values, we can calculate p,a and b of the equation. ($a = p - 3$)

$y^2 = x^3 + ax + b \pmod p$

$y^2 = x^3 + (p-3)*x + b \pmod p$

$y^2 = x^3 -3x + b \pmod p$

substituting 3 points in the equation and solving:
$m = (Qy^2 - (Qx^3 - 3*Qx)) - (Gy^2 - (Gx^3 - 3*Gx))$

$n = (Qy^2 - (Qx^3 - 3*Qx)) - (Ry^2 - (Rx^3 - 3*Rx))$

$p = GCD(m, n)$

$b = Gy^2 - (Gx^3 - 3*Gx)$

calculating these equations with actual values will render these results

p = 89953523493328636138979614835438769105803101293517644103178299545319142490503
a = 89953523493328636138979614835438769105803101293517644103178299545319142490500
b = 28285296545714903834902884467158189217354728250629470479032309603102942404639

Now we have to calculate order(cardinality) of the curve, which can be done efficiently by Schoof–Elkies–Atkin point counting algorithm. Calculating q results in

q = 89953523493328636138979614835438769106005948670998555217484157791369906305783

Now we have all the public parameters.

From checking the implementation and some guess, we can figure out the vulnerability – that is reusing k while signing(PS3 hack 😉 ). ECDSA signature has two parts r and s. r is calculated as $r = k * g$ (x coordinate of point multiplication). So if k is same in different signatures, r will be also same. Now we have to find two instances in given signed messages, where r is same. We can get one pair as

Bushing wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xiKYZxm648bajMuJ9Dy1SyHEpu/MBHkViuCM4P9Fd78Q==
Hotz wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xCxqlIuZkMQDSpRWffZGG4NdkaOvAfttTtQuCaJZonxA==

Now we can calculate sk (secret multiplier) by following the attack specified in wiki (same attack is used in PS3 hack).

$s1 - s2 = modinv(k, order) * (hash1 - hash2) % order$

$k = (hash1 - hash2) * modinv(s1 - s2, order)$

$sk = (s1*k - hash1) * modinv(r, order)$

sk is calculated as

sk = 68503307448214310387573639006216872681840007669594105206515313184282784925849

Now its just the matter of signing a hash. We will just reuse the code from CTF.

```import string
import random
import hashlib
import ecdsa
import base64
import os

access = {"f56334fbe02eaa05218c31b01a80f2f6":0, "00b37cb56bb57705348610253b1b82e4":0,
"f2131629ea6c08f7f5f326d8bb6eb5fd":0, "6fa95b1427af77b3d769ae9cb853382f":0,
"58cd57027cf126fcc9bd93dea9d74c1a":0, "f1cd318e412b5f7226e5f377a9544ff7":1,
"98c131f9fb31f732b136f87e64ff686a":1, "6f3249aa304055d63828af3bfab778f6":2}

#our values
_p = 89953523493328636138979614835438769105803101293517644103178299545319142490503L
_b = 28285296545714903834902884467158189217354728250629470479032309603102942404639L
_q = 89953523493328636138979614835438769106005948670998555217484157791369906305783L
_sk = 68503307448214310387573639006216872681840007669594105206515313184282784925849L
ec = ecdsa.CurveFp( _p, _p-3, _b )

#some points that really should be on the curve we're going to use
_Gx = 0x337ef2115b4595fbd60e2ffb5ee6409463609e0e5a6611b105443e02cb82edd8L
_Gy = 0x1879b8d7a68a550f58166f0d6b4e86a0873d7b709e28ee318ddadd4ccf505e1aL

_Qx = 0x2a40fd522f73dc9f7c40b2420e39e62c5742ff2f11805a1577ed7f60153a0be1L
_Qy = 0x3085e99246006b71b4211eff47ff3efc0f93103ee7379dc3bcc6decdc46073a3L

_Rx = 0xbd0a442367bdc24cb09c49404e3d307ba99122e7b78e14f0d84870d0df97aa59L
_Ry = 0x22c88612db6b6af6f196cd815fc5f57fe871d3b6588b0c7a59e06cc759d736b2L

#check the curve is loaded ok
if not ec.contains_point(_Gx,_Gy):
exit()
if not ec.contains_point(_Qx,_Qy):
exit()
if not ec.contains_point(_Rx,_Ry):
exit()

g = ecdsa.Point( ec, _Gx, _Gy, _q )
seed = os.urandom(32)

#construct the server key material
server_public_key = ecdsa.Public_key( g, g * _sk)
server_secret_key = ecdsa.Private_key(server_public_key, _sk )

#some extended interfaces to Lis's ecdsa script
def sign(hashed_data, privkey):
h = int(hashed_data,16)
k = get_ephemeral_key()
signature  = privkey.sign( h, k )
return encode_signature(signature)

def encode_signature(signature):
rhex = "%064x" % signature.r
shex = "%064x" % signature.s
return base64.b64encode(rhex.decode('hex') + shex.decode('hex'))

def verify(signature, hashed_input, pubkey):
tmp = signature.replace("\n", "")
try:
tmp = base64.b64decode(tmp).encode('hex')
except:
return False
if len(tmp) != 128:
return False
sig = ecdsa.Signature(int(tmp[:64],16),int(tmp[64:],16))
h = int(hashed_input,16)
return pubkey.verifies(h, sig)

def get_ephemeral_key():
k = ""
while len(k) < 32:
k += hashlib.md5(seed + str(random.randint(0,255))).digest()
return int(k.encode('hex'),16)

#existing signature	for user level 0
token = 'f56334fbe02eaa05218c31b01a80f2f6'
sec_token = 'wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xCxqlIuZkMQDSpRWffZGG4NdkaOvAfttTtQuCaJZonxA=='

if verify(sec_token, token, server_public_key):
print "[*]verify good!"
print
#creating our signature for user level 1
name = 'Kevin'
token = 'f1cd318e412b5f7226e5f377a9544ff7'
sec_token = sign(token, server_secret_key)
print sec_token
print
#verifying
if verify(sec_token, token, server_public_key):
print "[*]verify good!"```

Finally we have to bruteforce md5 with a given prefix to get a hash which begins with 0000. Straight forward bruteforce 🙂

Posted By: Dan
Last Edit: 21 Aug 2013 @ 10:31 PM

EmailPermalink
Categories: CTF

### Responses to this post » (None)

Last 50 Posts
Back
Back
Change Theme...
• Users » 1
• Posts/Pages » 15
• Comments » 39
Change Theme...
• Void « Default
• Life
• Earth
• Wind
• Water
• Fire
• Light

#### About

No Child Pages.