Foreword#
Participated in this CTF from the LiveOverflow video about this. Very interesting CTF but I only have enough time and effort to do Crypto and some Introduction to Web challenges, hence the low ranking.
Crypto challenges reuse ideas from Cryptohack, so nothing really special (if you have done the CryptoHack challenges with similar ideas that is).
Challenges#
Casino#
Challenge:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
FLAG = "CSCG{TEST}"
import random
rng = random.SystemRandom()
# Secure group from RFC 3526
prime = int("""
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
15728E5A 8AACAA68 FFFFFFFF FFFFFFFF""".replace('\n', '').replace(' ', ''),
16)
generator = 11
def play():
challenge = rng.randint(0, 1)
a, b, z = rng.randint(1, prime-1), rng.randint(1, prime-1), rng.randint(1, prime-1)
A, B, C, Z = pow(generator, a, prime), pow(generator, b, prime), pow(generator, a*b, prime), pow(generator, z, prime)
print(f"""Guess the random bit I have coosen!
Commitment: {A}, {B}, {C if challenge == 1 else Z}""")
guess = int(input("> ").strip())
if guess == challenge:
print(f"""Correct! My challenge was {challenge}
Proof: {a}, {b}""")
return 1
else:
print(f"""Wrong! My challenge was {challenge}
Proof: {a}, {b}""")
return -1
def main():
balance = 100
print(f"""Welcome to the first casino with fully provable randomness using cryptographically hard problems!
It uses the Decisional Diffie-Hellman Problem to provide a commitment, which can be verified by the player after the answer has been given.
Your balance is {balance} €.
Aquire 200 € to get one of our premium flags
""")
while True:
balance += play()
if balance <= 0:
exit(0)
if balance >= 200:
print(FLAG)
exit(0)
print(f"Your current balance is {balance} €\n")
if __name__ == '__main__':
main()
|
If anyone has taken a crypto course in university or read some book in cryptography, this is a classic example of Decisional Diffie Hellman.
Solving this is based on two things: Legendre Symbol and the fact that $a \times b$ is even $\frac{3}{4}$ of the time. The group we are working with is prime, hence we can use the Legendre symbol to work out the DDH problem. We will always have a $\frac{3}{4} - \frac{1}{2} = \frac{1}{4}$ advantage when we are guessing using Legendre symbol, hence the balance will increase.
Basically the guessing of the random bit is as follows. We will calculate the Legendre Symbol of the shares A, B, C. If the Legendre symbol of A or B is 1 (meaning either the exponent a or b is even), then we will guess 1 if the Legendre symbol of C is 1 (to leverage the $\frac{1}{4}$ advantage), otherwise 0. If neither Legendre Symbol is 1 then we guess at random.
Python Implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
from pwn import *
prime = int("""
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
15728E5A 8AACAA68 FFFFFFFF FFFFFFFF""".replace('\n', '').replace(' ', ''),
16)
def legendre_symbol(a, p):
return pow(a, (p - 1) // 2, p)
io = remote("828d5fe9c2e69524b850ab40-casino.challenge.master.cscg.live", 31337, ssl=True)
io.recvuntil(b"premium flags\n")
io.recvline()
for i in range(2000):
io.recvline()
commitment = io.recvline().decode().strip().split(": ")[1]
g_a, g_b, g_c = list(map(lambda x: int(x), commitment.split(", ")))
# Calculate Legendre Symbol
g_a_symbol = legendre_symbol(g_a, prime) == 1
g_b_symbol = legendre_symbol(g_b, prime) == 1
g_c_symbol = legendre_symbol(g_c, prime) == 1
if g_a_symbol or g_b_symbol:
if g_c_symbol:
io.sendline(b"1")
else:
io.sendline(b"0")
else:
io.sendline(str(random.choice([0, 1])).encode())
io.recvline()
io.recvline()
response = io.recvline().strip()
print(response)
if b"CSCG" in response:
break
io.recvline()
|
Existential#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
import ecdsa
import ecdsa.curves
import os
from hashlib import shake_128
BANNER = """
WELCOME to the demo version of sig1337nature.
Our signature signing is faster than anyone!
In our demo you can request up to 69 signatures!
To show how certain we are in our construction, we even included a bug bounty program.
"""
FLAG = "SOME_TEST_FLAG"
def efficient_k(msg):
# Make semi-deterministic to not exhaust the entropy pool too fast
return int.from_bytes(
shake_128(msg).digest(16) + os.urandom(16),
"big"
)
def read_hex(prompt):
try:
return bytes.fromhex(input(prompt + " (hex):"))
except ValueError:
raise ValueError("That's not valid hex. Learn to type.")
def sign_msg(priv_key):
msg = read_hex("Message")
if b"flag" in msg:
print("No way, jose!")
return
sig = priv_key.sign(msg, k=efficient_k(msg))
print("Signature (hex):", sig.hex())
def verify_msg(pub_key):
msg = read_hex("Message")
signature = read_hex("Signature")
try:
pub_key.verify(signature, msg)
print("Signature valid!")
if b"flag" in msg: # this will never happen
print("You won a bounty!")
print(FLAG)
except ecdsa.BadSignatureError:
print("Signature invalid!")
def main():
print(BANNER)
privkey = ecdsa.SigningKey.generate(curve=ecdsa.curves.BRAINPOOLP256r1)
pubkey = privkey.get_verifying_key()
for _ in range(69): # nice
print()
print("You can:")
print(" 1. Sign something")
print(" 2. Verify something")
choice = input("Choice >")
if choice == "1":
sign_msg(privkey)
else:
verify_msg(pubkey)
print()
print("Thanks for trying the demo! Buy the full license today!")
if __name__ == '__main__':
main()
|
This is the No Random, No Bias challenge from Cryptohack. This time we have some biased nonce $k$ in which we know the most significant bits. The code below is inspired from the following blog post by Kevin Liu, see the Baby crypto revisited challenge.
There is also this hurdle that we cannot get 3 signatures successfully, due to the way $k$ is generated. This is really annoying as we have to run the script multiple times to retrieve the 3 signatures just to derive the private key.
Sage implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
import ecdsa
from Crypto.Util.number import *
import ecdsa.curves
from hashlib import sha1, shake_128
from ecdsa.util import sigdecode_string
from pwn import *
import string
import random
def efficient_k(msg):
# Make semi-deterministic to not exhaust the entropy pool too fast
return int.from_bytes(
shake_128(msg).digest(16) + os.urandom(16),
"big"
)
# Generate a random hex string, don't know if it's needed but
def generate_random_string(length):
return ''.join(random.choices(string.hexdigits, k=length))
# https://neuromancer.sk/std/brainpool/brainpoolP256r1
n = 0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7
# 3 sigs is enough, see https://eprint.iacr.org/2019/023.pdf
sz = 3
B = 2 ^ 128
matrix = [[0] * (sz + 2) for _ in range(sz + 2)]
for i in range(sz):
matrix[i][i] = n
matrix[-2][-2] = B / n
matrix[-1][-1] = B
io = remote("417d699eb8a79e927090793e-existential.challenge.master.cscg.live", int(31337), ssl=True)
test = []
for i in range(sz):
io.recvuntil(b"Choice >")
io.sendline(b"1")
random_string = generate_random_string(10)
io.sendline(str(random_string).encode())
encoded_string = bytes.fromhex(random_string)
# Obtain the signature from the server
io.recvline()
io.recvline()
sig = io.recvline().decode().strip().split(":")[1]
r, s = sigdecode_string(bytes.fromhex(sig), n) # decode the signature
k = bytes_to_long(shake_128(encoded_string).digest(16)) * 2 ^ 128
h = bytes_to_long(sha1(encoded_string).digest())
test.append((r, s, k, h, encoded_string, sig))
matrix[-2][i] = r * inverse(s, n)
matrix[-1][i] = h * inverse(s, n) - k
m = Matrix(matrix)
m = m.LLL(early_red=True, use_siegel=True)
true_priv_key = None
true_pub_key = None
for row in m:
k_lower = row[0]
r = test[0][0]
s = test[0][1]
k = test[0][2] + k_lower
h = test[0][3]
test_str = test[0][4]
sig = bytes.fromhex(test[0][5])
key = inverse(r, n) * (k * s - h) % n
try:
priv_key = ecdsa.SigningKey.from_secret_exponent(key, ecdsa.curves.BRAINPOOLP256r1)
pub_key = priv_key.get_verifying_key()
if pub_key.verify(sig, test_str):
print("Here")
true_priv_key = priv_key
true_pub_key = pub_key
except Exception as e:
print(e)
# Submitting the flag
win = b"flagLMAO"
win_sig = true_priv_key.sign(win)
io.sendline(b"2")
io.sendline(win.hex().encode())
io.sendline(win_sig.hex().encode())
io.interactive()
|