Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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", ""))
@elliptic-shiho

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2016

Writeup: Breaking Ed25519 with same random key.

Trivial algebraic practice.

Mon Apr 18 09:11:09 JST 2016 ~/ctf/sctf-2016-q1/crypto40/ed25519 Battery 0: Full, 100%
> time python solve.py 
[28104680254895858602950095340273610962152604410683289209133586156927824858805L, 47318893950578276168317079672385112889584626339324959120861701577279184447848L] 3056024505099303091264038272914434090600937271399321803322554667848809587426 13397442584040240938586667532063254484324168699882605334802284616584255557111053955417396865311479649066713941214800499812450892230427570948701676049481822
[28104680254895858602950095340273610962152604410683289209133586156927824858805L, 47318893950578276168317079672385112889584626339324959120861701577279184447848L] 1975756995894560183473395863515241874506266339720132698812345799672898628901 7960866852339352189900001165174010281146836611057896297646402284319532015956538563906002724988794309980855750528647709587915541142579171768379987340263132
117 117
Flag is sctf{aCmaUba1kuLbg8Jso1lL3YG9u58RxZeh3rgj2nyLneh12Mf7NAvaREdBikQrkpWSa3UT15wUmunsrceSa3CUCQ==}

real    0m0.910s
user    0m0.901s
sys     0m0.008s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.