Talk To Echo

Echo is lonely and would like to talk

nc challs.bcactf.com 31755

Here’s the source code:

1
from random import randint
2
from time import sleep
3
from Crypto.Hash import SHA256
4
from Crypto.Cipher import AES
5
from Crypto.Util.Padding import pad
6
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
7
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
8
n = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
9
G = (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
10

11
def add(p, q):
12
    if p == (0, 0):
13
        return q
14
    if q == (0, 0):
15
        return p
16
    if p[0] == q[0] and p[1] != q[1]:
17
        return (0, 0)
18
    if p != q:
19
        l = ((q[1] - p[1]) * pow(q[0] - p[0], -1, n)) % n
20
    else:
21
        if p[1] == 0:
22
            return (0, 0)
23
        l = ((3 * p[0] * p[0] + a) * pow(2 * p[1], -1, n)) % n
24
    x = (l * l - p[0] - q[0]) % n
25
    y = (l * (p[0] - x) - p[1]) % n
26
    return (x, y)
27

28
def mul(k, p):
29
    q = (0, 0)
30
    while k > 0:
31
        if k & 1:
32
            q = add(q, p)
33
        p = add(p, p)
34
        k >>= 1
35
    return q
36

37
priv = randint(1, n - 1)
38
pub = mul(priv, G)
39

40
def enc(m, key=0):
41
    if key == 0:
42
        r = randint(1, n - 1)
43
        R = mul(r, G)
44
        K = mul(r, pub)
45
    else:
46
        R = None
47
        K = key
48
    h = SHA256.new()
49
    h.update(str(K[0]).encode())
50
    k = h.digest()[:16]
51
    cipher = AES.new(k, AES.MODE_ECB)
52
    if R:
53
        return (R, cipher.encrypt(pad(m, 16)))
54
    return cipher.encrypt(pad(m, 16))
55

56
print("Hi! I'm Echo!")
57
print("Just a second, I just received a message... give me a bit as I read it...")
58
print(f"*mumbles* {enc(open("flag.txt", "rb").read())} *mumbles* ah interesting")
59
while True:
60
    print("Talk to me! Let's use Diffie-Hellman Key Exchange to stay secure.")
61
    print("Here is my public key:")
62
    print(pub)
63
    print("Please send me a point.")
64
    x = int(input("x: "))
65
    y = int(input("y: "))
66
    rA = (x, y)
67
    assert rA != (0, 0)
68
    K = mul(priv, rA)
69
    print(enc(b"Hey there! Thanks for talking to me :)", K))
70
    h = input("Want to speak again? (y/n)")
71
    if h.lower() != "y":
72
        break

This implementation of ECDH (Elliptic Curve Diffie-Hellman Key Exchange) is vulnerable to what is known as an Invalid Curve Attack. This site explains it great.

The reason this works is because this server uses a Weierstrass curve, and therefore doesn’t utilize a in its point calculations. Additionally, the server does not check if the user-inputted point is on the server’s curve.

Hence, we can use a different curve (specially selected — read the site linked above about the attack), and the point calculations will calculate a valid point on our chosen curve.

The one key difference between the solve for this challenge and standard invalid curve attacks is that we cannot take the discrete log of the point the server provides — instead, we have to brute force the point. Therefore, we have to ensure that the chosen prime factor of the our chosen curve’s order is small enough to brute force. 2**20 is definitely small enough, which is why I only used primes less than that. Also, choosing the largest prime possible at each stage allows us to more efficiently determine the private key.

Besdies that, this is a pretty standard implementation of the invalid curve attack in sage:

1
from random import randint
2
from time import sleep
3
from Crypto.Hash import SHA256
4
from Crypto.Cipher import AES
5
from Crypto.Util.Padding import pad
6
from Crypto.Util.number import *
7
from pwn import *
8
from tqdm import trange
9

10
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
11
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
12
n = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
13
E = EllipticCurve(GF(n), [a, b])
14
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
15

16
def add(p, q):
17
    if p == (0, 0):
18
        return q
19
    if q == (0, 0):
20
        return p
21
    if p[0] == q[0] and p[1] != q[1]:
22
        return (0, 0)
23
    if p != q:
24
        l = ((q[1] - p[1]) * pow(q[0] - p[0], -1, n)) % n
25
    else:
26
        if p[1] == 0:
27
            return (0, 0)
28
        l = ((3 * p[0] * p[0] + a) * pow(2 * p[1], -1, n)) % n
29
    x = (l * l - p[0] - q[0]) % n
30
    y = (l * (p[0] - x) - p[1]) % n
31
    return (x, y)
32

33
def mul(k, p):
34
    q = (0, 0)
35
    while k > 0:
36
        if k & 1:
37
            q = add(q, p)
38
        p = add(p, p)
39
        k >>= 1
40
    return q
41

42
def enc(m, key=0):
43
    if key == 0:
44
        r = randint(1, n - 1)
45
        R = mul(r, G)
46
        K = mul(r, pub)
47
    else:
48
        R = None
49
        K = key
50
    h = SHA256.new()
51
    h.update(str(K[0]).encode())
52
    k = h.digest()[:16]
53
    cipher = AES.new(k, AES.MODE_ECB)
54
    if R:
55
        return (R, cipher.encrypt(pad(m, 16)))
56
    return cipher.encrypt(pad(m, 16))
57

58
p = remote('challs.bcactf.com', '31755')
59

60
res = p.recvuntil(b'stay secure.\n').decode('ascii').split('*mumbles* ')[1][:-1]
61
R, flagct = eval(res)
62
R = E(R[0], R[1])
63

64
p.recvuntil(b'public key:\n')
65
pub = eval(p.recvline().decode('ascii')[:-1])
66
pub = E(pub[0], pub[1])
67

68
dlogs = []
69
primes = []
70
msg = b"Hey there! Thanks for talking to me :)"
71
tot = 1
72
while tot < n:
73
    p.recvrepeat(float(0.1))
74

75
    # NOTE: choose curve
76
    b = randint(1, n)
77
    E2 = EllipticCurve(GF(n), [a, b])
78
    order = E2.order()
79
    print(f'order: {order}')
80

81
    # NOTE: choose factor of order
82
    prime = None
83
    for i in trange(2**20, 0, -1):
84
        if order % i == 0:
85
            if not isPrime(i):
86
                continue
87
            prime = i
88
            break
89
    if prime != None and prime > 2**10:
90
        print(f'chose {prime}')
91

92
        # NOTE: send point
93
        P = E2.gen(0)*int(order / prime)
94
        point = P.xy()
95
        print(f'point: {point}')
96
        p.sendline(str(point[0]).encode())
97
        p.recvrepeat(float(0.1))
98
        p.sendline(str(point[1]).encode())
99

100
        ct = eval(p.recvline().decode('ascii'))
101

102
        test = P
103
        for i in trange(2, prime + 1):
104
            test = test + P
105
            try:
106
                K = test.xy()
107
            except:
108
                continue
109
            c = enc(msg, K)
110
            if c == ct:
111
                dlogs.append(pow(i, 2, prime))
112
                primes.append(prime)
113
                break
114
    else:
115
        p.sendline(b'1')
116
        p.recvrepeat(float(0.1))
117
        p.sendline(b'1')
118

119

120
    print(dlogs)
121
    print(primes)
122

123
    p.recvrepeat(float(0.1))
124
    p.sendline(b'y')
125
    tot = 1
126
    for _ in primes:
127
        tot *= _
128
    print(tot)
129
    print(n)
130

131
priv = CRT_list(dlogs, primes)
132
print(priv)
133
print(tot)
134
print(n)
135
priv = mod(priv, tot).sqrt(extend=False, all=True)
136
print(len(priv))
137
for k in trange(len(priv)):
138
    K = R*priv[k]
139
    # print(K)
140
    h = SHA256.new()
141
    h.update(str(K.xy()[0]).encode())
142
    k = h.digest()[:16]
143
    cipher = AES.new(k, AES.MODE_ECB)
144
    flag = cipher.decrypt(flagct)
145
    if b'bcactf' in flag:
146
        print(flag)
147
        break

1
bcactf{3ChO_iS_NOW_8OtH_lOnEly_anD_bR0keN_cdccd6d49c3418}