redpwnCTF 2021 - crypto challenges
- Author: willwam845
- Date:
brief and rushed writeups to all the crypto challenges from redpwnctf 2021
scissor
1import random
2
3key = random.randint(0, 25)
4alphabet = 'abcdefghijklmnopqrstuvwxyz'
5shifted = alphabet[key:] + alphabet[:key]
6dictionary = dict(zip(alphabet, shifted))
7
8print(''.join([
9 dictionary[c]
10 if c in dictionary
11 else c
12 for c in input()
13]))
14
15# output: egddagzp_ftue_rxms_iuft_rxms_radymf
the script implements a cipher (which is caesar cipher).
the keyspace is incredibly small, so we can just bruteforce the key, either using the provided script, or just using something else like cyberchef’s rot13 decryptor and trying all possible keys. we can see one of these gives us a clearly readable flag.
flag: flag{surround_this_flag_with_flag_format}
warmup
n: 228430203128652625114739053365339856393
e: 65537
c: 126721104148692049427127809839057445790
we get what appears to be a set of rsa parameters, along with a ciphertext that we presumably have to decrypt.
the modulus n in this case is very small, and can be easily factored using something like alpertron. we then retrieve the prime factors, calculate the private key, and decrypt the message.
1from Crypto.Util.number import long_to_bytes
2
3n = 228430203128652625114739053365339856393
4e = 65537
5c = 126721104148692049427127809839057445790
6p = 12546190522253739887
7q = 18207136478875858439
8d = pow(e, -1, (p-1) * (q-1))
9pt = pow(c, d, n)
10print(long_to_bytes(pt))
flag: flag{68ab82df34}
round-the-bases
we get given a file with what looks like random data. judging from the title, we can guess that it is probably a base challenge. cyberchef is once again a great tool for this, allowing us to quickly try different combinations of bases together and seeing their result. other than that, there isn’t really much to this challenge, just keep trying combinations of bases, judging based on the number of unique characters in their output.
flag: flag{w0w_th4t_w4s_4ll_wr4pp3d_up}
blecc
p = 17459102747413984477
a = 2
b = 3
G = (15579091807671783999, 4313814846862507155)
Q = (8859996588597792495, 2628834476186361781)
d = ???
Can you help me find `d`?
Decode it as a string and wrap in flag format.
we get given a file that seems to be parameters for an ecdh exchange. our goal is to work out the private key d given curve parameters, as well as a generator point G and curve point Q, where Q = G * d. this requires solving the discrete log problem.
sage is a very useful tool for this, as it supports elliptic curves, and we just have to provide parameters.
1p = 17459102747413984477
2a = 2
3b = 3
4E = EllipticCurve(GF(p), [a,b])
5G = E(15579091807671783999, 4313814846862507155)
6Q = E(8859996588597792495, 2628834476186361781)
if we print the order of the generator G using G.order(), we see that it is 17459102747134002790. this number is quite smooth, having many small factors, and when the order of the generator is smooth, the discrete log problem becomes easy to solve. sage can again, conveniently, do most of the work for us.
1p = 17459102747413984477
2a = 2
3b = 3
4E = EllipticCurve(GF(p), [a,b])
5G = E(15579091807671783999, 4313814846862507155)
6Q = E(8859996588597792495, 2628834476186361781)
7print(G.discrete_log(Q))
giving us the result: 7868191182322623331. converting this into a byte string gives us the flag.
flag: flag{m1n1_3cc}
yahtzee
1#!/usr/local/bin/python
2
3from Crypto.Cipher import AES
4from Crypto.Util.number import long_to_bytes
5from random import randint
6from binascii import hexlify
7
8with open('flag.txt','r') as f:
9 flag = f.read().strip()
10
11with open('keyfile','rb') as f:
12 key = f.read()
13 assert len(key)==32
14
15'''
16Pseudorandom number generators are weak!
17True randomness comes from phyisical objects, like dice!
18'''
19class TrueRNG:
20
21 @staticmethod
22 def die():
23 return randint(1, 6)
24
25 @staticmethod
26 def yahtzee(N):
27 dice = [TrueRNG.die() for n in range(N)]
28 return sum(dice)
29
30 def __init__(self, num_dice):
31 self.rolls = num_dice
32
33 def next(self):
34 return TrueRNG.yahtzee(self.rolls)
35
36def encrypt(message, key, true_rng):
37 nonce = true_rng.next()
38 cipher = AES.new(key, AES.MODE_CTR, nonce = long_to_bytes(nonce))
39 return cipher.encrypt(message)
40
41'''
42Stick the flag in a random quote!
43'''
44def random_message():
45 NUM_QUOTES = 25
46 quote_idx = randint(0,NUM_QUOTES-1)
47 with open('quotes.txt','r') as f:
48 for idx, line in enumerate(f):
49 if idx == quote_idx:
50 quote = line.strip().split()
51 break
52 quote.insert(randint(0, len(quote)), flag)
53 return ' '.join(quote)
54
55banner = '''
56============================================================================
57= Welcome to the yahtzee message encryption service. =
58= We use top-of-the-line TRUE random number generators... dice in a cup! =
59============================================================================
60Would you like some samples?
61'''
62prompt = "Would you like some more samples, or are you ready to 'quit'?\n"
63
64if __name__ == '__main__':
65 NUM_DICE = 2
66 true_rng = TrueRNG(NUM_DICE)
67 inp = input(banner)
68 while 'quit' not in inp.lower():
69 message = random_message().encode()
70 encrypted = encrypt(message, key, true_rng)
71 print('Ciphertext:', hexlify(encrypted).decode())
72 inp = input(prompt)
we get access to a server that gives us encryptions of random quotes with the flag stuck in the middle somewhere using AES-CTR mode.
there are two main vulnerabilities here.
firstly, the cipher gets reset each time, leaving the implementation open to things like nonce reuse attacks, as the keystream will be the same if this is the case
secondly, the random number generator used is very insecure, as there are only 11 possible outputs. since this is used to generate nonces for the AES-CTR mode, we can perform the nonce reuse attack mentioned above.
if we get many ciphertexts from the server, and then see which ones appear to have reused nonces as well as the same plaintext (by looking at the similarity in them), then we can identify where the flag was placed in each of the ciphertexts and crib drag with known flag format.
i have grabbed some ciphertexts which appear to share a nonce and plaintext, apart from the flag position being changed.
341f317e1dccabae6f2636d571a5c3e24dd358fb0c30989c7c536c857b0c08e29443ced90e02b9d38cb0d22ebb72e8a0abcd1aeab495d149a33d67759a23dd0f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dccabae6f2636d571a5c3e24dd358fb0c30989c7c546c937d0e4baaad789b8f016da5e4bef6d029bb68cf9aea901dc7eaaaf707ed2879328b23d30f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dccabae6f2636d571b4caa347c903f6730ed881286d749a7f0748b1ad41e0e1465ca5feebf49a27c471e5e5b49f02d0fab3fa56ed2879328b23d30f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dc3b4ef7f3567c90e8592f354ed47f6492bdfc3035c4fad291b0fb0c25fd6c3555ba2acacec822ec471e5e5b49f02d0fab3fa56ed2879328b23d30f24f913c16a5472f0595628ba3389a19983124a0dfe7e4af9e0
341f317e1dccabae6f2636d571a5c3e24dd358fb0c30989c7c536c857b0c08e29a4edc9e1757b4e2f7a482369367f9b6f99805d4bda1be12921e21749e05d44729ea5392575f58c146183da47498a19783124a0dfe7e4af9e0
comparing all of the ciphertexts against each other, we can guess at what point the flag starts at, as it will be different to all the other ciphertexts. in this way, we can recover a partial keystream, and then we can guess the rest to hopefully get the flag. we can again use cyberchef for this. basically, take where the ciphertext differs from the rest, xor that with flag{ as our known plaintext, and place the result into the keystream at the appropriate place
we recover the following keystream: 0000000000a5d88e184e000000d2a6c220b2000000000000003200f21a750000f22fafbe
xoring that with each of the plaintexts, we can recover slight chunks of the flag.
- 2nd ct: _W41t at index 3
- 3rd ct: _ther at index 8, _nO_3 at index 15
- 4th ct nO_3n at index 16, 0py} at index 23
our partial flag is then: flag{??_W41t_ther??_nO_3n??0py}
then, we can repeat the process above which we used to recover the partial keystream again, knowing more details of the flag.
flag: flag{0h_W41t_ther3s_nO_3ntr0py}
scrambled-elgs
1#!/usr/bin/env sage
2import secrets
3import json
4from Crypto.Util.number import bytes_to_long, long_to_bytes
5from sage.combinat import permutation
6
7n = 25_000
8Sn = SymmetricGroup(n)
9
10def pad(M):
11 padding = long_to_bytes(secrets.randbelow(factorial(n)))
12 padded = padding[:-len(M)] + M
13 return bytes_to_long(padded)
14
15#Prepare the flag
16with open('flag.txt','r') as flag:
17 M = flag.read().strip().encode()
18m = Sn(permutation.from_rank(n,pad(M)))
19
20#Scramble the elgs
21g = Sn.random_element()
22a = secrets.randbelow(int(g.order()))
23h = g^a
24pub = (g, h)
25
26#Encrypt using scrambled elgs
27g, h = pub
28k = secrets.randbelow(n)
29t1 = g^k
30t2 = m*h^k
31ct = (t1,t2)
32
33#Provide public key and ciphertext
34with open('output.json','w') as f:
35 json.dump({'g':str(g),'h':str(h),'t1':str(t1),'t2':str(t2)}, f)
for this challenge, we get a secret message m, which is then encrypted using the elgamal cryptosystem in a symmetric group.
the private key k is very small, and can be bruteforced.
1import json
2import sage.combinat.permutation as permutation
3
4n = 25_000
5Sn = SymmetricGroup(n)
6
7a = json.loads(open("output.json").read())
8g = Sn(a["g"])
9h = Sn(a["h"])
10t1 = Sn(a["t1"])
11t2 = Sn(a["t2"])
12
13
14for i in range(25000):
15 if g^i == t1:
16 print(i)
after this, we can recover m by dividing t2 by h^k
1k = 3245
2assert g^k == t1
3i = h^k
4t3 = t2/i
5m = Sn(t3)
and then recover the original M by getting the rank of m
1M = permutation.from_permutation_group_element(m)
2print(hex(M.rank()))
flag: flag{1_w1ll_n0t_34t_th3m_s4m_1_4m}
Keeper of the Flag
1#!/usr/local/bin/python3
2
3from Crypto.Util.number import *
4from Crypto.PublicKey import DSA
5from random import *
6from hashlib import sha1
7
8rot = randint(2, 2 ** 160 - 1)
9chop = getPrime(159)
10
11def H(s):
12 x = bytes_to_long(sha1(s).digest())
13 return pow(x, rot, chop)
14
15
16L, N = 1024, 160
17dsakey = DSA.generate(1024)
18p = dsakey.p
19q = dsakey.q
20h = randint(2, p - 2)
21g = pow(h, (p - 1) // q, p)
22if g == 1:
23 print("oops")
24 exit(1)
25
26print(p)
27print(q)
28print(g)
29
30x = randint(1, q - 1)
31y = pow(g, x, p)
32
33print(y)
34
35
36def verify(r, s, m):
37 if not (0 < r and r < q and 0 < s and s < q):
38 return False
39 w = pow(s, q - 2, q)
40 u1 = (H(m) * w) % q
41 u2 = (r * w) % q
42 v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
43 return v == r
44
45
46pad = randint(1, 2 ** 160)
47signed = []
48for i in range(2):
49 print("what would you like me to sign? in hex, please")
50 m = bytes.fromhex(input())
51 if m == b'give flag' or m == b'give me all your money':
52 print("haha nice try...")
53 exit()
54 if m in signed:
55 print("i already signed that!")
56 exit()
57 signed.append(m)
58 k = (H(m) + pad + i) % q
59 if k < 1:
60 exit()
61 r = pow(g, k, p) % q
62 if r == 0:
63 exit()
64 s = (pow(k, q - 2, q) * (H(m) + x * r)) % q
65 if s == 0:
66 exit()
67 print(H(m))
68 print(r)
69 print(s)
70
71print("ok im done for now")
72print("you visit the flag keeper...")
73print("for flag, you must bring me signed message:")
74print("'give flag':" + str(H(b"give flag")))
75
76r1 = int(input())
77s1 = int(input())
78if verify(r1, s1, b"give flag"):
79 print(open("flag.txt").readline())
80else:
81 print("sorry")
in this challenge we get to sign 2 messages using DSA. our goal is to then generate a valud signature for the message give flag
the vulnerability here is the nonce generation. we see the nonces are generated by a function:
1def H(s):
2 x = bytes_to_long(sha1(s).digest())
3 return pow(x, rot, chop)
4
5#...
6
7k = (H(m) + pad + i) % q
pad, rot and chop are all hidden, however we do get the value of $H(m)$. notice that since pad remains constant, we can form a relation between two nonces.
initially, we got the difference of the two nonces to be 1 by using the two sha1 colliding pdfs from here, meaning that $H(m)$ will be the same, and the $i$ will be the only difference. then, we can just perform the related nonce attack, first recovering the nonce and then the private key.
1k = (h2 - s2 - h1 * r2 / r1) / (s2 - s1 * r2 / r1)
2x = (s1 * k) / r1 - (h1 / r1)
flag: flag{here_it_is_a8036d2f57ec7cecf8acc2fe6d330a71}
quaternion-revenge
1#!/usr/bin/env sage
2from Crypto.Util.number import getPrime, bytes_to_long
3import secrets
4
5with open('flag.txt','r') as flagfile:
6 flag = flagfile.read().strip()
7
8with open('secret.txt','rb') as secret:
9 M = secret.read().strip()
10m = bytes_to_long(M)
11
12p = getPrime(512)
13q = getPrime(512)
14n = p * q
15e = 65537
16Q.<i,j,k> = QuaternionAlgebra(-p,-q)
17
18#randomize M per-instance
19m ^^= secrets.randbelow(n)
20
21#prepare leaks
22n = n
23l = m.bit_length()
24c1 = pow(m,e,p)
25c2 = pow(m,e,q)
26
27#reveal leaks
28print('n:',n)
29print('l:',l)
30print('c1:',c1)
31print('c2:',c2)
32
33#Present challenge
34try:
35 print("Calculate the left quaternion isomorphism of m:")
36 inp = input('>>> ').strip()
37 assert all([x in '1234567890 ijk*+' for x in inp])
38 if eval(inp)==m:
39 print(flag)
40 else:
41 print('Wrong!')
42except AssertionError:
43 print("Invalid characters.")
44except Exception:
45 print("Error.")
in this challenge we have to - wait hang on, just got a message that this was a troll challenge and you can just send i to get the flag.
huh.
flag: flag{00p5_1_l13d_r0fl}
retrosign
1#!/usr/local/bin/python
2
3from Crypto.Util.number import getPrime, bytes_to_long
4from Crypto.Hash import SHA256
5from binascii import unhexlify
6from secrets import randbelow
7
8with open('flag.txt','r') as f:
9 flag = f.read().strip()
10
11def sha256(val):
12 h = SHA256.new()
13 h.update(val)
14 return h.digest()
15
16def execute(cmd):
17 if cmd == "sice_deets":
18 print(flag)
19 elif cmd == "bad_signature":
20 print("INTRUSION DETECTED!")
21 else:
22 print("Command unknown.")
23
24def authorize_command(cmd, sig):
25 assert len(sig) == 128*2
26 a = bytes_to_long(sig[:128])
27 b = bytes_to_long(sig[128:])
28 if (a**2 + k*b**2) % n == bytes_to_long(sha256(cmd)):
29 execute(cmd.decode())
30 else:
31 execute("bad_signature")
32
33p = getPrime(512)
34q = getPrime(512)
35n = p * q
36k = randbelow(n)
37def interact():
38 print("===============================================================================")
39 print("This mainframe is protected with state-of-the-art intrusion detection software.")
40 print("All commands are passed through a signature-based filter.")
41 print("===============================================================================")
42 print("The following configuration is in place:")
43 print(f"n = {n};\nk = {k};")
44 print("Server configured.")
45 cmd = input(">>> ").strip().lower().encode()
46 sig = unhexlify(input("$$$ "))
47 authorize_command(cmd, sig)
48 print("Connection closed.")
49
50if __name__ == "__main__":
51 try:
52 interact()
53 except:
54 print("An error has occurred.")
in this challenge, we are given an implementation of some signature scheme, whose hardness depends on the problem of integer factorization. our goal is to find a pair of numbers, a and b, and given parameters k and n that satisfy the equation $a^{2} + k*b^{2} \equiv H(m) \mod n$
this isn’t feasible due to taking square roots being mod n very difficult without knowing the factorization of n.
after doing a bit of research, i found the scheme implemented: it’s the ong-schnorr-shamir signature scheme. conveniently, we also found a paper that breaks this scheme, so it’s implementing time… or maybe not
after doing a bit more osint, we found another ctf challenge that has used this signature scheme before, and a writeup for the challenge here. conveniently, it has an implementation of the paper for us!
so, we steal their implementation and get the flag.
flag: flag{w0w_th4t_s1gn4tur3_w4s_pr3tty_r3tr0}
osint is just that op