a ctfer on the load

1
from Crypto.Util.number import bytes_to_long, long_to_bytes
2
from hashlib import sha256
3
from secret import sign
4

5
message1 = "The secp256r1 curve was used."
6
message2 = "k value may have been re-used."
7

8
message1 = bytes_to_long(sha256(message1.encode()).digest())
9
message2 = bytes_to_long(sha256(message2.encode()).digest())
10

11
r1, s1 = sign(message1)
12
r2, s2 = sign(message2)
13

14
print(f"r1: {r1}, s1: {s1}")
15
print(f"r2: {r2}, s2: {s2}")

1
from hashlib import sha256
2
from Crypto.Util.number import*
3

4
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
5

6
message1 = "The secp256r1 curve was used."
7
message2 = "k value may have been re-used."
8

9
r = 91684750294663587590699225454580710947373104789074350179443937301009206290695
10
s1 = 8734396013686485452502025686012376394264288962663555711176194873788392352477
11
s2 = 96254287552668750588265978919231985627964457792323178870952715849103024292631
12

13
H_m1 = bytes_to_long(sha256(message1.encode()).digest())
14
H_m2 = bytes_to_long(sha256(message2.encode()).digest())
15
print(f"H(m1) = {H_m1}")
16
print(f"H(m2) = {H_m2}")
17

18
diff_h = (H_m1 - H_m2) % n
19
diff_s = (s1 - s2) % n
20
inv_diff_s = inverse(diff_s, n)
21
k = (diff_h * inv_diff_s) % n
22
print(f"k = {k}")
23
r_inv = inverse(r, n)
24
d = ((s1 * k - H_m1) % n) * r_inv % n
25
print(f"Private key d = {d}")
26

27
k_inv = inverse(k, n)
28
computed_s1 = (k_inv * (H_m1 + d * r)) % n
29
computed_s2 = (k_inv * (H_m2 + d * r)) % n
30

31
print(long_to_bytes(d))

1
import re
2
with open("flag.txt") as f:
3
    flag = f.read()
4
assert re.fullmatch(r"gigem\{[a-z0-9_]{38}\}",flag)
5
flag_num = int.from_bytes(flag.encode(), 'big')
6
assert flag_num % 114093090821120352479644063983906458923779848139997892783140659734927967458173 == 58809011802516045741268578327158509054400633329629779038362406616616290661238

1
import string
2
import re
3
from sage.all import *
4

5
chrs = (string.ascii_letters + string.digits + "_").encode()
6
avg = sorted(chrs)[len(chrs) // 2] - 1
7
print(f"{avg = }")
8
print([x - avg for x in sorted(chrs)])  # within [-37, 37]
9

10
flaglen = 38
11
M = 114093090821120352479644063983906458923779848139997892783140659734927967458173
12
C = int.from_bytes(b"gigem{" + b"\x00" * flaglen + b"}", "big")
13
rem = 58809011802516045741268578327158509054400633329629779038362406616616290661238
14
C -= rem
15

16
P = PolynomialRing(ZZ, "ap", flaglen)
17
aps = P.gens()
18
aa = [ap + avg for ap in aps]
19
f = C + sum([a * 256**i for i, a in enumerate(aa)]) * 256
20
print(f)
21

22
L = matrix(f.coefficients()).T
23
L = block_matrix([[M, 0], [L, 1]])
24
bounds = [1] + [37] * flaglen + [1]
25
scale = [2**20 // i for i in bounds]
26
Q = diagonal_matrix(scale)
27
L *= Q
28
L = L.BKZ(block_size=25)
29
L /= Q
30

31

32
# not good enough
33
# for row in L:
34
#     if row[-1] < 0:
35
#         row = -row
36
#     if row[0] == 0 and row[-1] == 1:
37
#         print(row)
38
#         print(f(*row[1:-1]) % M == 0)
39
#         aa = [x + avg for x in row[1:-1]][::-1]
40
#         flag = b"gigem{" + bytes(aa) + b"}"
41
#
42
#         assert int.from_bytes(flag, "big") % M == rem
43
#         print(flag)
44
# exit()
45

46
from fpylll import IntegerMatrix, LLL
47
from fpylll.fplll.gso import MatGSO
48
from fpylll.fplll.enumeration import Enumeration
49

50
sols = []
51

52
L[:, 0] *= 2**10
53
A = IntegerMatrix.from_matrix(L.change_ring(ZZ))
54
LLL.reduction(A)
55
MG = MatGSO(A)
56
MG.update_gso()
57
sol_cnt = 10000
58
enum = Enumeration(MG, sol_cnt)
59
size = int(L.nrows())
60
bound = 37
61
answers = enum.enumerate(0, size, (size * bound**2), 0, pruning=None)
62
for _, s in answers:
63
    v = IntegerMatrix.from_iterable(1, A.nrows, map(int, s))
64
    sv = v * A
65

66
    if abs(sv[0, size - 1]) <= bound and sv[0, -1] in (-1, 1):
67
        print(sv)
68
        neg = sv[0, -1]
69
        sol = [neg * sv[0, i + 1] for i in range(flaglen)]
70
        assert f(*sol) % M == 0
71
        aa = [x + avg for x in sol][::-1]
72
        try:
73
            flag = b"gigem{" + bytes(aa) + b"}"
74
        except:
75
            continue
76
        assert int.from_bytes(flag, "big") % M == rem
77
        print(flag)
78

79
        try:
80
            if re.fullmatch(r"gigem{\w{38}}", flag.decode()):
81
                print("FOUND")
82
                break
83
        except UnicodeDecodeError:
84
            pass

1
from Crypto.Util.number import *
2
from sage.all import *
3
import re
4

5
def lattice_enumeration(L, bound, sol_cnt=1_000_000):
6
    from fpylll import IntegerMatrix, LLL
7
    from fpylll.fplll.gso import MatGSO
8
    from fpylll.fplll.enumeration import Enumeration
9
    A = IntegerMatrix.from_matrix(L)
10
    LLL.reduction(A)
11
    M_mat = MatGSO(A)
12
    M_mat.update_gso()
13
    size = int(L.nrows())
14
    enum = Enumeration(M_mat, sol_cnt)
15
    answers = enum.enumerate(0, size, (size * bound**2), 0, pruning=None)
16
    print(f'Got {len(answers)} answers')
17
    for _, s in answers:
18
        # print(len(answers))
19
        v = IntegerMatrix.from_iterable(1, A.nrows, map(int, s))
20
        sv = v * A
21
        if abs(sv[0, size - 1]) <= bound:
22
            yield sv[0]
23

24
M_val = 114093090821120352479644063983906458923779848139997892783140659734927967458173
25
R_val = 58809011802516045741268578327158509054400633329629779038362406616616290661238
26

27
C = bytes_to_long(b"gigem{" + bytes(38) + b"}")
28
a = 85
29

30
dim = 38
31

32
M_lattice = (identity_matrix(dim)
33
    .augment(vector([0]*dim))
34
    .augment(vector([256**i for i in range(dim, 0, -1)]))
35
    .stack(vector([-a]*dim + [1, C - R_val]))
36
    .stack(vector([0]*dim + [0, -M_val]))
37
)
38

39
found = False
40
for row in lattice_enumeration(M_lattice.change_ring(ZZ), 37, sol_cnt=500_000):
41
    for sign in [1, -1]:
42
        r = [sign * x for x in row]
43
        if r[-2:] != [1, 0]:
44
            continue
45
        try:
46

47
            candidate = b"gigem{" + bytes([x + a for x in r[:-2]]) + b"}"
48
            if re.fullmatch(r"[a-z0-9_]{38}", candidate.decode()[6:-1]):
49
                if int.from_bytes(candidate, 'big') % M_val == R_val:
50
                    found = True
51
                    print(candidate)
52
                    break
53
        except Exception:
54
            continue
55

56
    if found:
57
        break

1
SHA256_OID = (2, 16, 840, 1, 101, 3, 4, 2, 1)
2

3
class AlgorithmIdentifier(univ.Sequence):
4
    componentType = namedtype.NamedTypes(
5
        namedtype.NamedType('algorithm', univ.ObjectIdentifier()),
6
        namedtype.NamedType('parameters', univ.Null())
7
    )
8

9
class DigestInfo(univ.Sequence):
10
    componentType = namedtype.NamedTypes(
11
        namedtype.NamedType('digestAlgorithm', AlgorithmIdentifier()),
12
        namedtype.NamedType('digest', univ.OctetString())
13
    )
14

15
def get_digestinfo(hash_bytes):
16
    alg = AlgorithmIdentifier()
17
    alg['algorithm'] = SHA256_OID
18
    alg['parameters'] = univ.Null()
19
    di = DigestInfo()
20
    di['digestAlgorithm'] = alg
21
    di['digest'] = hash_bytes
22
    return encoder.encode(di)
23

24
def integer_cube_root(n: int) -> int:
25
    low = 0
26
    high = 1 << ((n.bit_length() + 2) // 3)
27
    while low < high:
28
        mid = (low + high) // 2
29
        if mid**3 < n:
30
            low = mid + 1
31
        else:
32
            high = mid
33
    if low**3 > n:
34
        low -= 1
35
    return low
36
# The Forgery Routin
37
def forge_signature():
38
    message = b"admin"
39
    h = hashlib.sha256(message).digest()
40
    t = get_digestinfo(h)
41
    minimal_prefix = b"\x00\x01\xff\x00" + t
42
    target_block = minimal_prefix.ljust(256, b"\x00")
43
    target_int = int.from_bytes(target_block, byteorder="big")
44
    s = integer_cube_root(target_int)
45
    while True:
46
        candidate = s**3
47
        candidate_bytes = candidate.to_bytes(256, byteorder="big")
48
        try:
49
            data_section = candidate_bytes[3:]
50
            sep_index = data_section.index(b"\x00")
51
            recovered = data_section[sep_index+1:]
52
        except Exception:
53
            recovered = b""
54
        if candidate_bytes.startswith(b"\x00\x01\xff\x00") and recovered.startswith(t):
55
            break
56
        s += 1
57

58
    forged_sig = s.to_bytes(256, byteorder="big")
59
    print("forged sing (b64):")
60
    print(base64.b64encode(forged_sig).decode())
61
    return forged_sig
62

63
if __name__ == "__main__":
64
    forge_signature()

1
from Crypto.Cipher import ARC4
2
import os
3
from string import printable
4
from random import choices
5

6
IV = ''.join(choices(printable,k=32)).encode()
7
for i in range(96):
8
    nonce = input("Give me a prefix (hex): ")
9
    try:
10
        nonce = bytes.fromhex(nonce)
11
    except:
12
        print("Make sure to send in hex.")
13
        exit()
14
    if len(nonce) + len(IV) > 256:
15
        print("Your prefix is too long.")
16
        exit()
17
    try:
18
        cipher = ARC4.new(nonce + IV)
19
    except:
20
        print("Could not create the cipher.")
21
        exit()
22

23
    pt = b"\0"
24
    ct = cipher.encrypt(pt)
25
    print(f"Your lucky number is {ord(ct)}")
26

27
guess = input("What was the IV(hex): ")
28
try:
29
    guess = bytes.fromhex(guess)
30
except:
31
    print("Make sure to send your guess for the IV in hex.")
32
    exit()
33
if IV == guess:
34
    with open("flag.txt","r") as f:
35
        FLAG = f.read()
36
        print(FLAG)
37
else:
38
    print(f"WRONG! IV was {IV.hex()}")

1
from pwn import *
2

3
context.log_level = "debug"
4
io = remote("tamuctf.com", 443, ssl=True, sni="tamuctf_rc4-prefix")
5
io.interactive(prompt="")

1
from Crypto.Cipher import ARC4
2
import random
3
from pwn import *
4
from collections import Counter
5

6

7
def key_schedule(key):
8
    S = list(range(256))
9
    j = 0
10
    for i in range(len(key)):
11
        j = (j + S[i] + key[i]) % 256
12
        S[i], S[j] = S[j], S[i]
13
    return S
14

15
def get_prefix(ind, known):
16
    while True:
17
        prefix = random.randbytes(256-32)
18
        key = prefix + known
19
        S = key_schedule(key)
20
        if (S[1] + S[S[1]])%256 == ind:
21
            return prefix
22

23
def oracle(prefix):
24
    io.sendline(prefix.hex())
25
    io.recvuntil(b'number is ')
26
    return int(io.recvline(keepends=False))
27

28
def Most_Common(lst):
29
    data = Counter(lst)
30
    return data.most_common(1)[0][0]
31

32
key = b'a'*32
33
known_key = b''
34
#context.log_level = "debug"
35

36
io = remote("tamuctf.com", 443, ssl=True, sni="tamuctf_rc4-prefix")
37
#io = process("python3 ./RC4_prefix.py", shell=True)
38

39

40
for i in range(32):
41
    results = []
42
    for _ in range(3):
43
        prefix = get_prefix(256-32 + i, known_key)
44
        leak = oracle(prefix)
45
        for j in range(256):
46
            S = key_schedule(prefix + known_key + bytes([j]))
47
            if S[(S[1] + S[S[1]])%256] == leak:
48
                results.append(j)
49
    known_key += bytes([Most_Common(results)])
50
    print(known_key)
51

52
print(known_key.hex())
53
io.sendline(known_key.hex())
54
io.interactive()