sCTF 2016 Q1: Ed25519 Writeup
import hashlib | |
b = 256 | |
q = 2**255 - 19 | |
l = 2**252 + 27742317777372353535851937790883648493 | |
def H(m): | |
return hashlib.sha512(m).digest() | |
def expmod(b,e,m): | |
return pow(b, e, m) | |
def inv(x): | |
return expmod(x,q-2,q) | |
d = -121665 * inv(121666) | |
I = expmod(2,(q-1)/4,q) | |
def xrecover(y): | |
xx = (y*y-1) * inv(d*y*y+1) | |
x = expmod(xx,(q+3)/8,q) | |
if (x*x - xx) % q != 0: x = (x*I) % q | |
if x % 2 != 0: x = q-x | |
return x | |
By = 4 * inv(5) | |
Bx = xrecover(By) | |
B = [Bx % q,By % q] | |
def edwards(P,Q): | |
x1 = P[0] | |
y1 = P[1] | |
x2 = Q[0] | |
y2 = Q[1] | |
x3 = (x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2) | |
y3 = (y1*y2+x1*x2) * inv(1-d*x1*x2*y1*y2) | |
return [x3 % q,y3 % q] | |
def scalarmult(P,e): | |
if e == 0: | |
return [0, 1] | |
bits = map(int, bin(e)[2:])[::-1] | |
x = P | |
if bits[0]: | |
res = x | |
else: | |
res = [0, 1] | |
for cur in bits[1:]: | |
x = edwards(x, x) | |
if cur: | |
res = edwards(res, x) | |
return res | |
def encodeint(y): | |
bits = [(y >> i) & 1 for i in range(b)] | |
return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)]) | |
def encodepoint(P): | |
x = P[0] | |
y = P[1] | |
bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1] | |
return ''.join([chr(sum([bits[i * 8 + j] << j for j in range(8)])) for i in range(b/8)]) | |
def bit(h,i): | |
return (ord(h[i/8]) >> (i%8)) & 1 | |
def publickey(sk): | |
h = H(sk) | |
a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) | |
A = scalarmult(B,a) | |
return encodepoint(A) | |
def Hint(m): | |
h = H(m) | |
return sum(2**i * bit(h,i) for i in range(2*b)) | |
def signature(m,sk,pk): | |
h = H(sk) | |
a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) | |
r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m) | |
R = scalarmult(B,r) | |
S = (r + Hint(encodepoint(R) + pk + m) * a) % l | |
return encodepoint(R) + encodeint(S) | |
def isoncurve(P): | |
x = P[0] | |
y = P[1] | |
return (-x*x + y*y - 1 - d*x*x*y*y) % q == 0 | |
def decodeint(s): | |
return sum(2**i * bit(s,i) for i in range(0,b)) | |
def decodepoint(s): | |
y = sum(2**i * bit(s,i) for i in range(0,b-1)) | |
x = xrecover(y) | |
if x & 1 != bit(s,b-1): x = q-x | |
P = [x,y] | |
if not isoncurve(P): raise Exception("decoding point that is not on curve") | |
return P | |
def checkvalid(s,m,pk): | |
if len(s) != b/4: raise Exception("signature length is wrong") | |
if len(pk) != b/8: raise Exception("public-key length is wrong") | |
R = decodepoint(s[0:b/8]) | |
A = decodepoint(pk) | |
S = decodeint(s[b/8:b/4]) | |
h = Hint(encodepoint(R) + pk + m) | |
if scalarmult(B,S) != edwards(R,scalarmult(A,h)): | |
raise Exception("signature does not pass verification") |
import ed25519 | |
import gmpy | |
def modinv_p(a, p): | |
assert gmpy.is_prime(p) | |
return pow(a, p-2, p) | |
pk = "5bfcb1cd3938f3f6f3092da5f7d7a1bdb1d694a725d0585a99208787554e110d".decode("hex") | |
s1 = "68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de8e2224855125b1acbeab1468bf4860c1eeb05b6d2375e2214c55bdfe808a6c106".decode("hex") | |
m1 = "sctf.io" | |
s2 = "68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de825ad01a05a0cce69258d41d42ed046956e7d4586eb21ff031bf8ac03243d5e04".decode("hex") | |
m2 = "2016 Q1" | |
# check | |
ed25519.checkvalid(s1, m1, pk) | |
ed25519.checkvalid(s2, m2, pk) | |
P = ed25519.decodepoint(pk) | |
a = 0 | |
R1 = ed25519.decodepoint(s1[:ed25519.b/8]) | |
S1 = ed25519.decodeint(s1[ed25519.b/8:ed25519.b/4]) | |
h1 = ed25519.Hint(ed25519.encodepoint(R1) + pk + m1) | |
R2 = ed25519.decodepoint(s2[:ed25519.b/8]) | |
S2 = ed25519.decodeint(s2[ed25519.b/8:ed25519.b/4]) | |
h2 = ed25519.Hint(ed25519.encodepoint(R2) + pk + m2) | |
print R1, S1, h1 | |
print R2, S2, h2 | |
a = ((S1 - S2) * modinv_p(h1 - h2, ed25519.l)) % ed25519.l | |
r1 = (S1 - h1 * a) % ed25519.l | |
r2 = (S2 - h2 * a) % ed25519.l | |
print r1, r2 | |
f = "the flag" | |
r = r1 | |
R = ed25519.scalarmult(ed25519.B, r) | |
S = (r + ed25519.Hint(ed25519.encodepoint(R) + pk + f) * a) % ed25519.l | |
print "Flag is sctf{%s}" % ((ed25519.encodepoint(R) + ed25519.encodeint(S)).encode("base64").replace("\n", "")) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
Writeup: Breaking Ed25519 with same random key.
Trivial algebraic practice.