[Crypto] Secret Base MK II

crypto/Secret Base MK II

Description:

I have again protected my secret base with the ultra-secure Robust Skulking Approach and the X’treme Obfuscation Routine but with an upgraded security system! This time you really cannot find my secret base!

nc chall.25.cuhkctf.org 25058

Attachment Script:

 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


from Crypto.Util.number import getPrime
from Crypto.Random.random import randint
from math import gcd

p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
e = phi
while gcd(e, phi) != 1:
    e = randint(2, phi - 1)
    if e % 2 == 0:
        e += 1
d = pow(e, -1, phi)

def encrypt(m):
    return pow(m, e, n)

def decrypt(c):
    return pow(c, d, n)

def main():
    flag = open("flag.txt", "rb").read().strip()
    secret_base = int.from_bytes(flag, "big")
    assert 0 < secret_base < n
    c = encrypt(secret_base) # The unknown base of RSA is a secret base, right? :3
    s = set([c, n - c]) # UwU
    print(f"n: {n}")
    print(f"c: {c}")

    while True:
        c1 = int(input("c1: "))
        assert 1 < c1 < n, "u h4cker!"
        assert c1 not in s, ":<"
        s.add(c1)
        
        c2 = int(input("c2: "))
        assert 1 < c2 < n, "u h4cker!"
        assert c2 not in s, ":<"
        s.add(c2)

        m1 = decrypt(c1)
        m2 = decrypt(c2)
        
        print(f"m: {m1 ^ m2}")


if __name__ == "__main__":
    main()

In this challenge, we got the source code of the remote service. The challenge is a RSA oracle which enable we to decrypt a pair of ciphertext (c1, c2) but only return the XOR of their plaintext dec(c1) XOR dec(c2).

There are some ciphertexts are prohibited to submit, for example:

c
n-c
1

The operation that the script do:

The flag is encrypted as c = m^e mod n where m is the flag.
And gave the n and c.
Then required two ciphertexts c1 and c2.
Return dec(c1) XOR dec(c2).
And maintains a forbidden set s with c, n-c.
Finally add your ciphertext into the forbidden.

Acttack flow

First choose c1 = n-1 and some random c2 = k where gcd(k,n) = 1.
Then we know decrypt(n-1) = (n-1)^d ≡ n-1 (mod n)
Next, the oracle return (n-1) XOR decrypt(k)
So that we can know decrypt(k) = oracle_output XOR (n-1)

As we know decrypt(k), Then decrypt(n-k) = n - decrypt(k) Thus, we can choose the c1, c2

c1 = n-k
c2 = (n-k) * c^(-1) mod n

For c2: decrypt(c2) = decrypt((n-k) * c^(-1)) = decrypt(n-k) * decrypt(c^(-1)) = (n - decrypt(k)) * m^(-1) mod n

The return: decrypt(c1) XOR decrypt(c2)

So that:

1
2


oracle_output = (n - decrypt(k)) XOR ((n - decrypt(k)) * m^(-1))
              = (n - decrypt(k)) * (1 XOR m^(-1))

As we know decrypt(k), we can solve for m^(-1) and compute m = (m^(-1))^(-1) mod n.

The Solution Script

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137


#!/usr/bin/env python3

from pwn import remote
import re
import random
from math import gcd

HOST = "chall.25.cuhkctf.org"
PORT = 25058

def parse_int(line: bytes) -> int:
    m = re.search(rb":\s*([0-9]+)", line)
    if not m:
        raise ValueError(f"Failed to parse integer from: {line!r}")
    return int(m.group(1))

def inv_mod(a: int, n: int) -> int:
    # Python 3.8+: pow handles modular inverse with negative exponent
    try:
        return pow(a, -1, n)
    except ValueError:
        # Fallback EEA if needed
        t, newt = 0, 1
        r, newr = n, a % n
        while newr != 0:
            q = r // newr
            t, newt = newt, t - q * newt
            r, newr = newr, r - q * newr
        if r != 1:
            raise ValueError("inverse does not exist")
        if t < 0:
            t += n
        return t

def recv_header(io):
    # Robustly find n and c
    n = c = None
    for _ in range(6):
        line = io.recvline()
        if b"n:" in line:
            n = parse_int(line)
        elif b"c:" in line:
            c = parse_int(line)
        if n is not None and c is not None:
            break
    if n is None or c is None:
        raise RuntimeError("Failed to read n/c")
    return n, c

def ask_pair(io, c1: int, c2: int) -> int:
    io.recvuntil(b"c1: ")
    io.sendline(str(c1).encode())
    io.recvuntil(b"c2: ")
    io.sendline(str(c2).encode())
    line = io.recvline()
    while b"m:" not in line:
        line = io.recvline()
    return parse_int(line)

def main():
    io = remote(HOST, PORT)
    n, c = recv_header(io)

    # Quick sanity: need c invertible mod n; if not, we could factor n from gcd(c, n).
    g = gcd(c, n)
    if g != 1:
        print(f"[!] gcd(c, n) = {g} > 1 (n is factorable). This instance is degenerate.")
        io.close()
        return

    inv_c = inv_mod(c, n)

    # Forbidden initial set on the server: {c, n-c}
    forb = {c, (n - c) % n}

    # Also avoid 0,1,n-1 (1 is outright disallowed; n-1 we will use explicitly)
    forb |= {0, 1}

    # Round 1: choose k
    while True:
        k = random.randrange(2, n - 1)
        if k in forb:
            continue
        if gcd(k, n) != 1:
            continue
        k2 = (n - k) % n  # -k mod n
        if k2 in forb or k2 == 0 or k2 == 1:
            continue
        # Build the Round 2 second element now to ensure it won't be forbidden later
        k2_cinv = (k2 * inv_c) % n
        # All must be distinct and allowed by server assertions
        cand = {k, k2, k2_cinv, n - 1}
        if len(cand) != 4:
            continue
        if any(x <= 1 or x >= n for x in cand):
            continue
        if any(x in forb for x in {k, k2, k2_cinv}):
            continue
        # Also ensure k2_cinv won’t accidentally collide with k or n-1 (already checked distinctness though)
        break

    # ----- Round 1: (n-1, k)
    o1 = ask_pair(io, n - 1, k)
    # d odd => dec(n-1) = n-1, so dec(k) = o1 XOR (n-1)
    dec_k = o1 ^ (n - 1)

    # dec(k2) = -dec(k) mod n
    dec_k2 = (n - dec_k) % n

    # ----- Round 2: (k2, k2 * c^{-1})
    o2 = ask_pair(io, k2, (k2 * inv_c) % n)
    # p = dec(k2) * m^{-1} (mod n)
    p = o2 ^ dec_k2

    # m^{-1} = p * inv(dec(k2)) mod n
    if gcd(dec_k2, n) != 1:
        # Extremely unlikely if gcd(k, n)=1
        raise RuntimeError("dec(k2) not invertible mod n; try again.")
    m_inv = (p * inv_mod(dec_k2, n)) % n

    # m = inv(m^{-1}) mod n
    if gcd(m_inv, n) != 1:
        raise RuntimeError("m_inv not invertible mod n; instance is degenerate.")
    m = inv_mod(m_inv, n)

    # Convert to bytes
    blen = (m.bit_length() + 7) // 8
    flag = m.to_bytes(blen, "big").lstrip(b"\x00")
    try:
        print(flag.decode())
    except UnicodeDecodeError:
        print(flag)

    io.close()

if __name__ == "__main__":
    main()

flag: cuhk25ctf{d0_you_l1ke_the_s3cret_b4s3_50ng_in_MKI_0r_MKII_m0r3?}