I participated in TetCTF as a member of Super Guesser.

I was first to [solve all three crypto challenges]. Our team finished 2nd place :)

unimplemented (1st solve)

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081 from collections import namedtuplefrom Crypto.Util.number import getPrimeimport random Complex = namedtuple("Complex", ["re", "im"])  def complex_mult(c1, c2, modulus):    return Complex(        (c1.re * c2.re - c1.im * c2.im) % modulus,  # real part        (c1.re * c2.im + c1.im * c2.re) % modulus,  # image part    )  def complex_pow(c, exp, modulus):    result = Complex(1, 0)    while exp > 0:        if exp & 1:            result = complex_mult(result, c, modulus)        c = complex_mult(c, c, modulus)        exp >>= 1    return result  def generate_key_pair(nbits):    while True:        p = getPrime((nbits + 3) // 4)        q = getPrime((nbits + 3) // 4)        n = (p ** 2) * (q ** 2)        if n.bit_length() == nbits:            return (p, q), n  def pad(data, length):    assert len(data) < length    pad_length = length - len(data) - 1    pad_data = bytes(random.choices(range(1, 256), k=pad_length))    sep = b'\x00'    return pad_data + sep + data  def unpad(data):    assert b"\x00" in data, "incorrect padding"    return data.split(b"\x00", 1)  def encrypt(public_key, plaintext):    n = public_key    plaintext = pad(plaintext, 2 * ((n.bit_length() - 1) // 8))    m = Complex(        int.from_bytes(plaintext[:len(plaintext) // 2], "big"),        int.from_bytes(plaintext[len(plaintext) // 2:], "big")    )    c = complex_pow(m, 65537, n)    return (c.re.to_bytes((n.bit_length() + 7) // 8, "big")            + c.im.to_bytes((n.bit_length() + 7) // 8, "big"))  def decrypt(private_key, ciphertext):    # TODO    raise Exception("unimplemented")  def main():    private_key, public_key = generate_key_pair(2021)    from secret import flag     print("private_key =", private_key)    print("public_key =", public_key)    print("ciphertext =", encrypt(public_key, flag))  if __name__ == '__main__':    main() # Output:# private_key = (128329415694646850105527417663220454989310213490980740842294900866469518550360977403743209328130516433033852724185671092403884337579882897537139175073013,#                119773890850600188123646882522766760423725010264224559311769920026142724028924588464361802945459257237815241227422748585976629359167921441645714382651911)# public_key = 236252683050532196983825794701514768601125614979892312308283919527619033977486749228418695923608569040825653688303374445536392159719426640289893369552258923597180869981053519695297428186215135878525530974780390951763007339139013157234202093279764459949020588291928614938201565110828675907781512603972957429701280916745719458738970910789383870206038035515777549907045905872280803964436193687072794878040018900969772972761081589529671158140590712503582004892067155769362463889653489918914397872964087471457070748108694165412065471040954221707557816986272311750297566993468288899523479556822418109112211944932649# ciphertext = b'\x00h\xbe\x94\x8c\xcd\xdd\x04\x80\xf4\x9d\t\xd8\x8dO\x08\xf1\xd1\xc4\xb9\xa06\xe7\xe3\xb6\xc3\x01+\xa9\xf2\xb9\xe8\x8d\xe6\xc9\x0c_#\x93\x11\xad\x0f\x90\xd3\x0b6\xb0n\x13\xea~"V6\xdbA&\x87\xfe\xa3C\xcb\x16\xae\xd9\x83\xdbU\xc6\x06\xcd\x9a\x94\xa9\xce\x15{d\x95s\xc2\xfb\x90q\xe7\x02\xa2\x081:_C\xc68\x00y\x7fj4@\xd2\xcdE\x06\x943\xbe\xbcC3\xca\x91\xb4\x0e}C\xab\xff?X\xc30u\x069:Dc\xb5\xdc\x9b0%\x98\xbd\xd9\x13\xc0\x02w\xc5\xe5:\xca\xcf\x0c\xab\xc2\x9b}\xab\xd0\xcc\xbc\x0f\x9e9\t\xf7M\xb3\xed\x86\xb5E\x8b\xbc4\xfaH\x9b4\x1c\xc4\xab\xc0\xaf\x8a5XcX\x19K\xed\x19\xe1\x1c\xd0\x1e\x97c\x9fF:L\x9d\x90p\x99\xb8\xde\xcblM\xb3\x80sSL\xe1\xa4\xd6,\x81\xd6\x9c\xf1\xbb\x9c)\xf03\x155\xc0\xd5v\x13\xd6#\xb7\x19\xdea%\xce<\x1c\xf7\xf2!;\xc1\xd7w\xd1\xc8\x8d/\xaew\xa1\x1d\xc5(\xc8\x9d\x82v\xf6j\x90A,e\xbd\xa7]\x10\x8f\xe5\xe7\x93}:\xdf1~\xec\xd0-o\r\x96\xe4\x03\xb9E\x9fdF\xc3\xf8L\xa0\xda\xf0E[\xf7\x02\xef|*\x08\x8a5pI&\xa9i\x0fZ\xa8\xb3H\xed\xe8v\xc4H\xff\xdb\xcb\x00\xf1\xae\x9bO\x18\xd5\xd8&p\xf5\xf6\xe9\xf1\x1brs\xc2\r\xceZ\xd0\xb24\x97+\x98b\x0e\xbb\xb8.\x8dT\xe4"\xad\xe4\xa3f\xd0M\xbf\xafX\xbb"[\x99\xdap\xa5\xcfT2Wx\x87M\x7f\x99!>B[Q\x04\xf6\x03\xbc\x84\xf4\xdfj\xdd1^I\x1a\x05\x81\x91\xde9Mf*\x8e\x8d\xe64\xf8\x93\x99&yP\xcd\x00!\x82\xab\xbcy\xed\xf1\x13\xd3\x81\xeaz\xbbP>\x9a2\x8c\x08\x0es\xbc\xa9\xf6\xa3\x8c\xb0\xb9t\xd9?\x06@\xc9\x90\xb7\xa7<\x85\xeb\x1a\x88#\x1c\xc3 \xec\xc7\x94d\x99\xd6\x8e>\x06\xf8Y\xf4\x19\xcaI/hy\x18\x8e\x0e8\xf8\r\xbb\xf6\x11\xb9\x8dCWB6 ' Colored by Color Scripter cs

Introduction

We are given all the key values and the ciphertext, so we just need to work on the decryption algorithm.

Our encryption is a very RSA-like algorithm, with multiplication defined as complex multiplication, with the Re/Im values taken modulo $n$.

Strategy

Let's think about how RSA decryption works first, and start from there. Denote $n=pq$ with $p, q$ primes.

We know that $\text{gcd}(a, p) = 1$ implies $a^{p-1} \equiv 1 \pmod{p}$. We know that $\text{gcd}(a, q) = 1$ implies $a^{q-1} \equiv 1 \pmod{q}$.

Therefore, we see that with $\text{gcd}(a, p)=1$ and $\text{gcd}(a, q)=1$, we have $a^{(p-1)(q-1)} \equiv 1 \pmod{pq}$.

This is because $a^{(p-1)(q-1)}$ must be $1$ modulo each $p, q$, so we may apply Chinese Remainder Theorem.

Now, with the encryption exponent $e$, we can get decryption exponent by taking modulo inverse mod $(p-1)(q-1)$.

This problem should not be so different. We'll denote $a \equiv b \pmod{n}$ if $a, b$ has same Re/Im values $\pmod{n}$.

We should find a function $f$ that guarantees $a^{f(p)} \equiv 1 \pmod{p^2}$ if $\text{gcd}(a, p) = 1$, and $a^{f(q)} \equiv 1 \pmod{q^2}$ if $\text{gcd}(a, q) = 1$.

• Immediate Question : What does $\text{gcd}$ mean in this setting? I'll explain this later.

Anyways, if we find such $f$, we know $a^{f(p)f(q)} \equiv 1 \pmod{p^2q^2}$ must hold for the same reason.

We can then find the modular inverse of $e = 65537$ mod $f(p)f(q)$ and get the decryption exponent.

For now, let's just hope that we have $\text{gcd}(a, p) = \text{gcd}(a, q) = 1$ for our ciphertext. (whatever that gcd means)

Now we have to find what the function $f$ is all about. There are at least 5 ways to do this. (I used Method 2.)

Finish

• Method 1. We simply read the code of unevaluated.
• It's easy to see that "unevaluated" challenge gives us some discrete logarithm problem.
• If we read it more carefully, we see that $g = (re, im)^{24}$ precisely has order $pqr = p(p-1)(p+1)/24$.
• Therefore, we can see that $(re, im)$ has an order that divides $p(p-1)(p+1)$.
• We can now guess that $f(p) = p^3 - p$ should work, and it indeed does. Done :)
• Method 2. We run some tests for small $p$, and guess our way to find $f$.
• Let's just fix some small primes $p$ and see when $a^{???} \equiv 1 \pmod{p^2}$.
• Let's look at the minimum exponent that satisfies the modulo equation. It can be seen that it is a divisor of $p(p-1)(p+1)$.
• Therefore, we can now guess that $f(p) = p^3 - p$ should work, and it indeed does. Done :)
• Method 3. We actually do some mathematics to find our answer.
• We define $\text{gcd}(a+bi, p)$ as $\text{gcd}(a^2+ b^2, p)$. This is highly motivated by the norm map.
• We first claim that for odd primes $p$ and $\text{gcd}(a+bi, p)=1$, $(a+bi)^{p^2-1} \equiv 1 \pmod{p}$.
• Case 1. $p \equiv 3 \pmod{4}$.
• This is the easy case, as our complex numbers can be now viewed as elements of $\mathbb{F}_{p^2}$.
• Since the multiplicative group of this extension field has $p^2-1$ elements, we are now done.
• Case 2. $p \equiv 1 \pmod{4}$.
• We prove that $(a+bi)^{p-1} \equiv 1 \pmod{p}$. This is enough to prove our result.
• Denote $(a+bi)^{p-1} \equiv c + di \pmod{p}$, and note that $(a-bi)^{p-1} \equiv c - di \pmod{p}$ by taking conjugates.
• Now we take an $x$ such that $x^2 \equiv -1 \pmod{p}$. We can now substitute $i$ as $x$ without an issue.
• This shows $1 \equiv (a+bx)^{p-1} \equiv c+ dx \pmod{p}$, and $1 \equiv (a-bx)^{p-1} \equiv c - dx \pmod{p}$.
• Combining these two equations directly gives us $c = 1$, and $d = 0$. Note that $x$ is nonzero.
• Note that $a+bx$ being nonzero $\pmod{p}$ is equivalent to $\text{gcd}(a^2 + b^2, p) = 1$.
• Now we prove the main result : $(a+bi)^{p^3 - p} \equiv 1 \pmod{p^2}$ if $\text{gcd}(a+bi, p) = 1$.
• We know that $(a+bi)^{p^2-1} \equiv 1 \pmod{p}$, so we can write $(a+bi)^{p^2-1} \equiv 1 + pc \pmod{p^2}$ for some complex number $c$.
• Now we directly use Binomial Theorem to get $(a+bi)^{p^3-p} \equiv (1+pc)^p \equiv 1 \pmod{p^2}$. Done.
• This shows that we can use $f(p) = p^3-p$, with proof. It should work. Done :)
• Method 4. Google with keywords "Gaussian Integers" and "RSA"
• This leads to various resources, such as https://www.diva-portal.org/smash/get/diva2:1170568/FULLTEXT01.pdf
• Method 5. Lagrange's Theorem
• We start by defining $\text{gcd}(a+bi, p) = \text{gcd}(a^2 +b^2, p)$, just like in Method 3.
• It's not hard to prove that the elements with $\text{gcd}(a^2+b^2, p)=1$ form a multiplicative group.
• Here, we look at elements $a+bi$ in $\pmod{p^2}$. Therefore, there are at most $p^4$ elements.
• If we count the number of elements with $\text{gcd}(a^2 + b^2, p)=1$, we can use that as $f(p)$, by Lagrange's Theorem.
• In other words, we use that $a^{|G|} = e$ for all finite groups $G$, identity element $e$, and element $a \in G$.
• Case 1. $p \equiv 3 \pmod{4}$.
• For $\text{gcd}(a^2+b^2,p) \neq 1$, we need both $a, b$ to be multiples of $p$. There are $p^2$ such elements.
• Therefore, we may take $f(p) = p^4 - p^2$ in this case. Done!
• Case 2. $p \equiv 1 \pmod{4}$.
• We only need to look at $0 \le a, b < p$ and multiply by $p^2$ in the end.
• If $a=0$, only $b=0$ satisfies $\text{gcd}(a^2+b^2,p) \neq 1$. If $1 \le a < p$, there are $2$ such $b$s.
• Therefore, there are $p^2-1-2(p-1) = (p-1)^2$ solutions. Multiplying by $p^2$, we have $f(p) = p^2(p-1)^2$.
• Since casework is boring, we just take the LCM of the two expressions and select $f(p) = p^2(p-1)^2(p+1)$. Done.
• Looking at the flag, the mentions of "counting" seems to imply that this method is the intended solution.

I wish (at least) Method 1 was blocked by allowing contestants to see "unevaluated" only after solving this challenge. :(

 1234567891011121314151617181920212223 private_key = (128329415694646850105527417663220454989310213490980740842294900866469518550360977403743209328130516433033852724185671092403884337579882897537139175073013,               119773890850600188123646882522766760423725010264224559311769920026142724028924588464361802945459257237815241227422748585976629359167921441645714382651911)public_key = 236252683050532196983825794701514768601125614979892312308283919527619033977486749228418695923608569040825653688303374445536392159719426640289893369552258923597180869981053519695297428186215135878525530974780390951763007339139013157234202093279764459949020588291928614938201565110828675907781512603972957429701280916745719458738970910789383870206038035515777549907045905872280803964436193687072794878040018900969772972761081589529671158140590712503582004892067155769362463889653489918914397872964087471457070748108694165412065471040954221707557816986272311750297566993468288899523479556822418109112211944932649ciphertext = b'\x00h\xbe\x94\x8c\xcd\xdd\x04\x80\xf4\x9d\t\xd8\x8dO\x08\xf1\xd1\xc4\xb9\xa06\xe7\xe3\xb6\xc3\x01+\xa9\xf2\xb9\xe8\x8d\xe6\xc9\x0c_#\x93\x11\xad\x0f\x90\xd3\x0b6\xb0n\x13\xea~"V6\xdbA&\x87\xfe\xa3C\xcb\x16\xae\xd9\x83\xdbU\xc6\x06\xcd\x9a\x94\xa9\xce\x15{d\x95s\xc2\xfb\x90q\xe7\x02\xa2\x081:_C\xc68\x00y\x7fj4@\xd2\xcdE\x06\x943\xbe\xbcC3\xca\x91\xb4\x0e}C\xab\xff?X\xc30u\x069:Dc\xb5\xdc\x9b0%\x98\xbd\xd9\x13\xc0\x02w\xc5\xe5:\xca\xcf\x0c\xab\xc2\x9b}\xab\xd0\xcc\xbc\x0f\x9e9\t\xf7M\xb3\xed\x86\xb5E\x8b\xbc4\xfaH\x9b4\x1c\xc4\xab\xc0\xaf\x8a5XcX\x19K\xed\x19\xe1\x1c\xd0\x1e\x97c\x9fF:L\x9d\x90p\x99\xb8\xde\xcblM\xb3\x80sSL\xe1\xa4\xd6,\x81\xd6\x9c\xf1\xbb\x9c)\xf03\x155\xc0\xd5v\x13\xd6#\xb7\x19\xdea%\xce<\x1c\xf7\xf2!;\xc1\xd7w\xd1\xc8\x8d/\xaew\xa1\x1d\xc5(\xc8\x9d\x82v\xf6j\x90A,e\xbd\xa7]\x10\x8f\xe5\xe7\x93}:\xdf1~\xec\xd0-o\r\x96\xe4\x03\xb9E\x9fdF\xc3\xf8L\xa0\xda\xf0E[\xf7\x02\xef|*\x08\x8a5pI&\xa9i\x0fZ\xa8\xb3H\xed\xe8v\xc4H\xff\xdb\xcb\x00\xf1\xae\x9bO\x18\xd5\xd8&p\xf5\xf6\xe9\xf1\x1brs\xc2\r\xceZ\xd0\xb24\x97+\x98b\x0e\xbb\xb8.\x8dT\xe4"\xad\xe4\xa3f\xd0M\xbf\xafX\xbb"[\x99\xdap\xa5\xcfT2Wx\x87M\x7f\x99!>B[Q\x04\xf6\x03\xbc\x84\xf4\xdfj\xdd1^I\x1a\x05\x81\x91\xde9Mf*\x8e\x8d\xe64\xf8\x93\x99&yP\xcd\x00!\x82\xab\xbcy\xed\xf1\x13\xd3\x81\xeaz\xbbP>\x9a2\x8c\x08\x0es\xbc\xa9\xf6\xa3\x8c\xb0\xb9t\xd9?\x06@\xc9\x90\xb7\xa7<\x85\xeb\x1a\x88#\x1c\xc3 \xec\xc7\x94d\x99\xd6\x8e>\x06\xf8Y\xf4\x19\xcaI/hy\x18\x8e\x0e8\xf8\r\xbb\xf6\x11\xb9\x8dCWB6 ' p = private_keyq = private_keyn = public_keye = 65537 v = (p ** 3 - p) * (q ** 3 - q)d = inverse(e, v)  re = bytes_to_long(ciphertext[ : len(ciphertext) // 2])im = bytes_to_long(ciphertext[len(ciphertext) // 2 : ]) ctxt = Complex(re, im) ptxt = complex_pow(ctxt, d, n) print(long_to_bytes(ptxt.re) + long_to_bytes(ptxt.im)) # TetCTF{c0unt1ng_1s_n0t_4lw4ys_34sy-vina:*100*48012023578024#}Colored by Color Scripter cs

uncollidable (4th solve)

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136 import jsonimport osfrom hashlib import sha256from typing import Callable, Dict H: Callable[[bytes], bytes] = lambda s: sha256(s).digest()  def get_mac(key: bytes, data: bytes) -> bytes:    """Just a MAC generation function similar to HMAC.    Reference link: https://en.wikipedia.org/wiki/HMAC#Implementation    """    if len(key) >= 32:        key = H(key)     if len(key) < 32:        key += b"\x00" * (32 - len(key))     inner_pad = bytearray(32)    outer_pad = bytearray(32)    for i in range(32):        inner_pad[i] = key[i] ^ 0x20        outer_pad[i] = key[i] ^ 0x21     return H(outer_pad + H(inner_pad + data))  class SecureStorage:    """Changes on data stored in this storage can be detected :) """     def __init__(self, debug=False):        self.keys: Dict[str, bytes] = {}  # key ID -> key        self.data: Dict[bytes, bytes] = {}  # MAC -> data        self.debug = debug        if debug:            # when debug mode is on, unique arguments to store_data will be            # logged.            self.store_data_args = set()     def generate_key(self, key_id: str) -> None:        """Generate a new key."""        if key_id in self.keys:            raise Exception("duplicated key id")        self.keys[key_id] = os.urandom(32)     def import_key(self, key_id: str, key: bytes) -> None:        """Import an external key."""        if key_id in self.keys:            raise Exception("duplicated key id")        self.keys[key_id] = key     def store_data(self, key_id: str, data: bytes) -> bytes:        """Store data and return a MAC that can be used to retrieve the data        later."""        if key_id not in self.keys:            raise Exception("key not found")         key = self.keys[key_id]        if self.debug:            self.store_data_args.add((key, data))         mac = get_mac(key, data)        if mac in self.data:            raise Exception("data already stored")         self.data[mac] = data        return mac     def retrieve_data(self, key_id: str, mac: bytes) -> bytes:        """Retrieve data previously stored with store_data."""        if key_id not in self.keys:            raise Exception("key not found")        if mac not in self.data:            raise Exception("data not found")         key = self.keys[key_id]        data = self.data[mac]        if get_mac(key, data) != mac:            raise Exception("data has been tampered")        return data     def report_bug(self) -> int:        """Claim your bounty here :) """        if self.debug:            # check for a massive collision bug            if len(self.store_data_args) >= 10 and len(self.data) == 1:                # check if collisions happened through different key sizes                key_lengths = [len(key) for (key, _) in self.store_data_args]                if min(key_lengths) < 32 <= max(key_lengths):                    # Congrats :)                    from secret import flag                    return int.from_bytes(flag, "big")        return 0  def main():    ss = SecureStorage(debug=True)    for _ in range(100):        try:            request = json.loads(input())             if request["action"] == "generate_key":                key_id = request["key_id"]                ss.generate_key(key_id)                print(json.dumps({}))             if request["action"] == "import_key":                key_id = request["key_id"]                key = bytes.fromhex(request["key"])                ss.import_key(key_id, key)                print(json.dumps({}))             elif request["action"] == "store_data":                key_id = request["key_id"]                data = bytes.fromhex(request["data"])                mac = ss.store_data(key_id, data)                print(json.dumps({"mac": mac.hex()}))             elif request["action"] == "retrieve_data":                key_id = request["key_id"]                mac = bytes.fromhex(request["mac"])                data = ss.retrieve_data(key_id, mac)                print(json.dumps({"data": data.hex()}))             elif request["action"] == "report_bug":                print(json.dumps({"bounty": ss.report_bug()}))         except EOFError:            break        except Exception as err:            print(json.dumps({"error": str(err)}))  if __name__ == '__main__':    main() Colored by Color Scripter cs

Introduction

We basically need a big collision of the MAC - 10 (key, data) values that map to a single MAC value.

We also need to use at least one key with length less than 32, and at least one key with length no less than 32 as well.

Strategy & Finish

Let's actually look at the MAC code. We see that some preparation are done to make the key exactly 32 bytes.

If the length is at least 32 bytes, we apply SHA256. If not, we append some zeros at the end to make it 32 bytes.

We immediately get some collision cooking - a key full of zeros will lead to a same MAC if the key length is less than 32 bytes.

Of course, this is easily generalizable - if the "final" 32 byte key ends with a lot of zeros, we get a lot of collisions!

This is extremely suspicious - we just need a key that is at least 32 bytes to go along with it.

This means we need a 32 byte value with SHA256 ending with a lot of zeros - 9 bytes of it, to be exact.

Now this is a problem that I have seen before - DragonCTF's bitflip2. SHA256 ending with a lot of zeros leads us to bitcoin PoW.

We can find a bunch of values with SHA256 ending with 8 bytes worth of zeros in bitcoin.

Luckily, the value we (Perfect Guesser) used at the time to solve bitflip2 already had 9 bytes of zeros in the end in the SHA256.

This solves the problem. This was a very good review exercise for me :)

 12345678910111213141516171819202122232425262728293031323334353637383940414243 HOST = "139.162.5.141"PORT = 5555 r = remote(HOST, PORT) key_id = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"] print(long_to_bytes(61342502866914327869718742967850222962760441300896006743258488289386736694996435440480147718715690291226752007898889408599107845232272253))tt = '294724a63e0fda8c731d9612b0a8e8b9bc0ec087ca9920c8488c5dd1df94ebff'tt = bytes.fromhex(tt) data = "1234" for i in range(0, 10):    key = '294724a63e0fda8c731d9612b0a8e8b9bc0ec087ca9920c8488c5dd1df94ebff'    if i >= 1:        key = bytes.fromhex(sha256(bytes.fromhex(key)).hexdigest())        key = key[:-i]        key = key.hex()    request = {        "action": "import_key",        "key_id": key_id[i],        "key": key    }    r.sendline(json.dumps(request))    print(r.readline())    request = {        "action": "store_data",        "key_id": key_id[i],        "data": data    }    r.sendline(json.dumps(request))    print(r.readline()) request = {    "action": "report_bug"} r.sendline(json.dumps(request)) print(r.readline()) # TetCTF{HM4C_c4n_b3_m1sus3d-viettel:*100*718395803842748#}Colored by Color Scripter cs

unevaluated (1st solve)

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 from collections import namedtuplefrom Crypto.Util.number import getPrime, isPrime, getRandomRange Complex = namedtuple("Complex", ["re", "im"])  def complex_mult(c1, c2, modulus):    return Complex(        (c1.re * c2.re - c1.im * c2.im) % modulus,  # real part        (c1.re * c2.im + c1.im * c2.re) % modulus,  # image part    )  def complex_pow(c, exp, modulus):    result = Complex(1, 0)    while exp > 0:        if exp & 1:            result = complex_mult(result, c, modulus)        c = complex_mult(c, c, modulus)        exp >>= 1    return result  class ComplexDiffieHellman:    @staticmethod    def generate_params(prime_length):        # Warning: this may take some time :)        while True:            p = getPrime(prime_length)            if p % 4 == 3:                if p % 3 == 2:                    q = (p - 1) // 2                    r = (p + 1) // 12                    if isPrime(q) and isPrime(r):                        break                else:                    q = (p - 1) // 6                    r = (p + 1) // 4                    if isPrime(q) and isPrime(r):                        break        n = p ** 2        order = p * q * r        while True:            re = getRandomRange(1, n)            im = getRandomRange(1, n)            g = complex_pow(Complex(re, im), 24, n)            if (                    complex_pow(g, order, n) == Complex(1, 0)                    and complex_pow(g, order // p, n) != Complex(1, 0)                    and complex_pow(g, order // q, n) != Complex(1, 0)                    and complex_pow(g, order // r, n) != Complex(1, 0)            ):                return g, order, n     def __init__(self, params=None, prime_length=128, debug=False):        if not debug:            raise Exception("security unevaluated")        if params is None:            params = ComplexDiffieHellman.generate_params(prime_length)        self.g, self.order, self.n = params     def get_public_key(self, private_key):        return complex_pow(self.g, private_key, self.n)     def get_shared_secret(self, private_key, other_public_key):        return complex_pow(other_public_key, private_key, self.n)  def main():    from os import urandom    private_key = urandom(32)    k = int.from_bytes(private_key, "big")     cdh = ComplexDiffieHellman(debug=True)    print("g =", cdh.g)    print("order =", cdh.order)    print("n =", cdh.n)    print("public_key =", cdh.get_public_key(k))     # Solve the discrete logarithm problem if you want the flag :)    from secret import flag    from Crypto.Cipher import AES    if len(flag) % 16 != 0:        flag += b"\x00" * (16 - len(flag) % 16)    print("encrypted_flag = ",          AES.new(private_key, AES.MODE_ECB).encrypt(flag))  if __name__ == "__main__":    main() # Output:# g = Complex(re=20878314020629522511110696411629430299663617500650083274468525283663940214962,#             im=16739915489749335460111660035712237713219278122190661324570170645550234520364)# order = 364822540633315669941067187619936391080373745485429146147669403317263780363306505857156064209602926535333071909491# n = 42481052689091692859661163257336968116308378645346086679008747728668973847769# public_key = Complex(re=11048898386036746197306883207419421777457078734258168057000593553461884996107,#                      im=34230477038891719323025391618998268890391645779869016241994899690290519616973)# encrypted_flag = b'\'{\xda\xec\xe9\xa4\xc1b\x96\x9a\x8b\x92\x85\xb6&p\xe6W\x8axC)\xa7\x0f(N\xa1\x0b\x05\x19@L9!\xb7\x9e3\xbc\x99\xf0\x8f\xb3\xacZ:\xb3\x1c\xb9\xb7;\xc7\x8a:\xb7\x10\xbd\x07"\xad\xc5\x84' Colored by Color Scripter cs

Introduction

We are given the same setup from "unimplemented". We are solving $g^x \equiv target \pmod{n}$ given $g, target, n$.

We also know that the order of $g$ is $order = p \cdot q \cdot r = p(p-1)(p+1)/24$, where $p, q, r$ are all primes.

We now have to solve a discrete logarithm problem to get a private key, which is used to encrypt our flag using AES.

Strategy

First, some basic steps. From $n = p^2$, we can directly calculate the value of $p$.

From the parameter generation process, we can also calculate $q, r$.

I actually computed $p$ by $\text{gcd}(n, order)$, and factorized $qr = order/ p$ using alpetron.

UPD: This is why my values of $q, r$ in this writeup and solution code is swapped instead of the original $q, r$ given in the code.

Anyway, we now know $p, q, r$ and can focus on our task, the discrete logarithm.

• Idea 1. The flaw in parameter generation.
• There is actually a very important flaw in parameter generation.
• Note that $p, q, r$ are around 128 bits. Therefore, the order $pqr$ is around $128 \cdot 3 = 384$ bits.
• However, the private key used in the AES and the discrete logarithm problem is 32 bytes, i.e. $256$ bits.
• Pohlig-Hellman style thinking shows we can compute $x \pmod{p}$, $x \pmod{q}$, $x \pmod{r}$ separately.
• Because $x$ is $256$ bits, we can simply solve two of these three problems and combine using CRT!!
• Idea 2. The (multiplicative) norm map $N(a+bi) = a^2 + b^2$.
• Note : I proved stuff for "unimplemented" (i.e. Method 3) after I solved all three challenges. However, the proof ideas are used here.
• The norm map allows us to move from weird complex number stuff to values in $\pmod{p}$, where we are more comfortable.
• Maybe this idea reminds us of MOV attack? I don't know. Anyways, let's finish the problem.

Finish

Let's first look at $x \pmod{r}$. We note that $r|(p-1)$, so norm map will work nicely here.

• We want $(g^{pq})^x \equiv target^{pq} \pmod{n}$, so $N(g^{pq})^x \equiv N(target^{pq}) \pmod{p}$.
• If we calculate $N(g^{pq})$ and $N(target^{pq})$ we get values that are nonzero, and also not equal to $1$.
• This is expected to happen, since $pq$ is relatively prime to $p-1$ and $g$ has high order.
• Therefore, we can solve the discrete logarithm problem in $\mathbb{F}_p$ to get information on $x$.
• We also see that (with Sage) $N(g^{pq})$ has order $r$ in $\mathbb{F}_p$. Therefore, we get the entire $x \pmod{r}$ here.

Next, we'll look at $x \pmod{p}$. If we get this, we'll solve the problem.

• We want $(g^{qr})^x \equiv target^{qr} \pmod{n}$. Note that $24qr \equiv 0 \pmod{p^2-1}$.
• Here, the $24$ comes from the fact that $g$ is actually defined as $(re, im)^{24}$ for some $re, im$.
• This shows that, from proof in Method 3 above, we must have $g^{qr} \equiv target^{qr} \equiv 1 \pmod{p}$.
• Therefore, we have $N(g^{qr}) \equiv N(target^{qr}) \equiv 1 \pmod{p}$ as well.
• However, computation shows us that $N(g^{qr}) , N(target^{qr})$ are not $1 \pmod{p^2}$. This is not unexpected.
• We can now solve $x \pmod{p}$ with $N(g^{qr})^x \equiv N(target^{qr}) \pmod{p^2}$.
• We simply note that $(1+pa)^x \equiv 1 +pax \pmod{p^2}$ using Binomial Theorem.
• Write $N(g^{qr}) \equiv 1 +pa \pmod{p^2}$ and $N(target^{qr}) \equiv 1 + pb \pmod{p^2}$, where $a, b$ are nonzero $\pmod{p}$.
• We now have, simply, $ax \equiv b \pmod{p}$. This can be solved with modular inverse.
• This looks quite like the Paillier Cryptosystem (which I learned by solving zer0ptsCTF Dirty Laundry) so that's cool.

When I first solved this problem, I found most of these insight by experiments.

I did think of the norm map first, solved $\pmod{r}$ part based on it, and was quite surprised when $N(g^{qr})$ was $1 \pmod{p}$.

Then I realized that I could use Binomial Theorem to solve the challenge. Looking back on "unimplemented" during write-up, I found out that most of my "surprises" during the solve was not actually surprising facts :) This is a very nice challenge, so thanks to ndh.

UPD: After some discussion with ndh in the CryptoHack server, it turns out I overcomplicated this problem a bit.

We can just solve for $N(g)^x \equiv N(target) \pmod{p^2}$ and solve the discrete logarithm problem here. :P

UPD: After even more discussion, it turns out that the above discrete logarithm in $\pmod{p^2}$ is not that easy.

Refer to the CryptoHack discord, or the writeup by Mystiz here, and TheBlueFlame121 here for more details. Highly suggest you read them.

These two writeups linked above have some important facts about discrete logarithm calculation in Sage in general. :)

In CryptoHack discord #ctf-challenges, $\$\$in has a summarization on this subject, and there are even more discussions with smart people!

UPD: CryptoHack discord #ctf-challenges has a very in-depth analysis and discussion on this challenge, a must read.

UPD: CryptoHack has posted a solid review on these challenges. See https://blog.cryptohack.org/tetctf-2021

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 def norm(x):    return x.re * x.re + x.im * x.im  g = Complex(re=20878314020629522511110696411629430299663617500650083274468525283663940214962,            im=16739915489749335460111660035712237713219278122190661324570170645550234520364)order = 364822540633315669941067187619936391080373745485429146147669403317263780363306505857156064209602926535333071909491n = 42481052689091692859661163257336968116308378645346086679008747728668973847769public_key = Complex(re=11048898386036746197306883207419421777457078734258168057000593553461884996107,                     im=34230477038891719323025391618998268890391645779869016241994899690290519616973)encrypted_flag = b'\'{\xda\xec\xe9\xa4\xc1b\x96\x9a\x8b\x92\x85\xb6&p\xe6W\x8axC)\xa7\x0f(N\xa1\x0b\x05\x19@L9!\xb7\x9e3\xbc\x99\xf0\x8f\xb3\xacZ:\xb3\x1c\xb9\xb7;\xc7\x8a:\xb7\x10\xbd\x07"\xad\xc5\x84' p = 206109322179011817882783419945552366363q = 17175776848250984823565284995462697197r = 103054661089505908941391709972776183181 # solve for mod pp_g = complex_pow(g, q * r, n)p_enc = complex_pow(public_key, q * r, n) # norm : a^2 + b^2c_1 = norm(p_g) % (p * p)c_2 = norm(p_enc) % (p * p) c_1 = (c_1 - 1) // pc_2 = (c_2 - 1) // p val_p = (c_2 * inverse(c_1, p)) % p  # solve for mod rr_g = complex_pow(g, p * q, n)r_enc = complex_pow(public_key, p * q, n)print(norm(r_g) % p, norm(r_enc) % p) '''p = 206109322179011817882783419945552366363g = GF(p)(176015758946526802279559144270141551487) # r_genc = GF(p)(28369875517706698292997652748535456248) # r_encprint(g.multiplicative_order()) # this equals rprint(enc.log(g)) # 26176203815975575469683683780455489251''' val_r = 26176203815975575469683683780455489251val_tot, pr = CRT(val_p, p, val_r, r) for i in range(0, 100):    private_key = long_to_bytes(val_tot + i * pr)    flag = AES.new(private_key, AES.MODE_ECB).decrypt(encrypted_flag)    if b"TetCTF" in flag:        print(flag)        break # TetCTF{h0m0m0rph1sm_1s_0ur_fr13nd-mobi:*100*231199111007#}Colored by Color Scripter cs

#### '수학 > 암호론 및 CTF' 카테고리의 다른 글

 0x41 CTF SPN Writeup  (0) 2021.01.31 2021.01.20 2021.01.03 2020.12.07 2020.10.18 2020.10.18
1. 알큼 2021.01.03 09:00

그는 신인가?