I have been participated with team 3xpl0it0l0gy, with my dudes in VinUniversity, and I have solved every crypto challenge in the CTF :D. Actually, now I am learning more rev/pwn for next CTFs, and also preparation for big competitions this year. But anyways, just continue with what I am good at… :D

For the shake of “save the time”, I will skip:

Dynastic (Very easy): Children’s Caesar :D
Makeshift (Very easy): ??? It’s just roll the cipher and u got the plaintext.
Primary Knowledge (Very easy): RSA with a single prime, simple $\phi = n - 1$ and then apply your RSA :(.

Iced TEA (Easy)

With this challenge, basically we need to write a decryption function for a given implementation of Tiny Encryption Algorithm (TEA).

import os
from secret import FLAG
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from enum import Enum

class Mode(Enum):
    ECB = 0x01
    CBC = 0x02

class Cipher:
    def __init__(self, key, iv=None):
        self.BLOCK_SIZE = 64
        self.KEY = [b2l(key[i:i+self.BLOCK_SIZE//16]) for i in range(0, len(key), self.BLOCK_SIZE//16)]
        self.DELTA = 0x9e3779b9
        self.IV = iv
        if self.IV:
            self.mode = Mode.CBC
        else:
            self.mode = Mode.ECB
    
    def _xor(self, a, b):
        return b''.join(bytes([_a ^ _b]) for _a, _b in zip(a, b))

    def encrypt(self, msg):
        msg = pad(msg, self.BLOCK_SIZE//8)
        blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]
        
        ct = b''
        print(self.mode)
        if self.mode == Mode.ECB:
            for pt in blocks:
                ct += self.encrypt_block(pt)
        elif self.mode == Mode.CBC:
            X = self.IV
            for pt in blocks:
                enc_block = self.encrypt_block(self._xor(X, pt))
                ct += enc_block
                X = enc_block
        return ct

    def encrypt_block(self, msg):
        m0 = b2l(msg[:4])
        m1 = b2l(msg[4:])
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1
        s = 0
        for i in range(32):
            s += self.DELTA
            m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
        m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1  
        return l2b(m)

You can search the Wikipedia page of TEA, and it should contain all you need. The only tricky part is this implementation has an & bitmask, but it’s nothing.

def decrypt_block(self, msg):
    m0 = b2l(msg[:4])
    m1 = b2l(msg[4:])
    msk = (1 << (self.BLOCK_SIZE//2)) - 1
    K = self.KEY
    s = (self.DELTA << 5) & msk
    for i in range(32):
        m1 -= ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
        m1 &= msk
        m0 -= ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
        m0 &= msk
        s -= self.DELTA
    return l2b((m0 << (self.BLOCK_SIZE//2)) + m1)

HTB{th1s_1s_th3_t1ny_3ncryp710n_4lg0r1thm_____y0u_m1ght_h4v3_4lr34dy_s7umbl3d_up0n_1t_1f_y0u_d0_r3v3rs1ng}

Yes I do some reverse but I don’t know it…

Blunt (Easy)

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256

from secret import FLAG

import random

p = getPrime(32)
print(f'p = 0x{p:x}')

g = random.randint(1, p-1)
print(f'g = 0x{g:x}')

a = random.randint(1, p-1)
b = random.randint(1, p-1)

A, B = pow(g, a, p), pow(g, b, p)

print(f'A = 0x{A:x}')
print(f'B = 0x{B:x}')

C = pow(A, b, p)
assert C == pow(B, a, p)

# now use it as shared secret
hash = sha256()
hash.update(long_to_bytes(C))

key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(f'ciphertext = {encrypted}')

This challenge is just baby Diffie-Hellman Key Exchange on prime modulo. With a 32-bit prime, it’s fairly small and you can do tool like SageMath discrete_log() to solve.

p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'
a = discrete_log(Mod(A, p), Mod(g, p)) # remember to wrap your stuff in Mod(p)
b = discrete_log(Mod(B, p), Mod(g, p))
C = Mod(A, p)^b
print(C)

# just get the flag :)
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256

hash = sha256()
hash.update(long_to_bytes(int(C)))
key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)
cipher.decrypt(ciphertext)

HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}

Arranged (Medium)

Ok~~, the first challenge that I really faced some struggles in solving it.

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

from secret import FLAG, p, b, priv_a, priv_b

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

A = G * priv_a
B = G * priv_b

print(A)
print(B)

C = priv_a * B

assert C == priv_b * A

# now use it as shared secret
secret = C[0]

hash = sha256()
hash.update(long_to_bytes(secret))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(encrypted)

The challenge performs an Elliptic Curve Diffie-Hellman Key Exchange, and from what I thought, this curve should not be a hard curve to solve the discrete logarithm. However, you can see that we are given an Elliptic Curve $E: y^2 = x^3 + Ax + B$ ; however, we do not know either the prime finite field, and also $b$ in the curve parameters.

Let’s step a step back. We are given three points: $G(x_G, y_G), A(x_A, y_A), B(x_B, y_B)$ lie on the curve (and indeedly, satisfy the equation of the curve).

Take $G$ and $A$ as an example:

\begin{cases} {y_G}^2 \equiv {x_G}^3 + Ax_G + B \pmod{p} \\ {y_A}^2 \equiv {x_A}^3 + Ax_A + B \pmod{p} \\ \end{cases}

Even we don’t know the prime finite field yet, we can still calculate:

\begin{cases} B_G \equiv {y_G}^2 - {x_G}^3 - Ax_G \\ B_A \equiv {y_A}^2 - {x_A}^3 - Ax_A \\ \end{cases}

Then, $B_G - B_A = k*p$ , as they are congruence under modulo $p$ . We can factorize this number here for a hope of $p$ . But we apply this strategy for another time, says, on $G$ and $B$ , then we will have a pairs of $kp$ and $k'p$ . Take GCD of these two and we should have our $p$ back :D

From this point, we can easily calculate $B$ back based on any of the above equations. And other steps, I will let discrete_log() do it job again :D

from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

x1 = 926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367
y1 = 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253
x2 = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997
y2 = 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
x3 = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734
y3 = 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865

b1 = y1^2 - x1^3 - 726*x1
b2 = y2^2 - x2^3 - 726*x2
# print(b1-b2)
b3 = y3^2 - x3^3 - 726*x3
# print(b2-b3)

# recalculate curve params
p = gcd(b1-b2, b1-b3)
b = b1 % p

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)
A = E(6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997, 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696)
B = E(4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734, 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865)

a = G.discrete_log(A) 
# a = 4
C = a * B
secret = C[0]
hash = sha256()
hash.update(long_to_bytes(int(secret)))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)
c= b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'
print(cipher.decrypt(c))

HTB{0rD3r_mUsT_b3_prEs3RveD_!!@!}

Partial Tenacity (Medium)

from secret import FLAG
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

class RSACipher:
    def __init__(self, bits):
        self.key = RSA.generate(bits)
        self.cipher = PKCS1_OAEP.new(self.key)
    
    def encrypt(self, m):
        return self.cipher.encrypt(m)

    def decrypt(self, c):
        return self.cipher.decrypt(c)

cipher = RSACipher(1024)

enc_flag = cipher.encrypt(FLAG)
print(cipher.key.p)
print(cipher.key.q)
print(cipher.key.e)
with open('output.txt', 'w') as f:
    f.write(f'n = {cipher.key.n}\n')
    f.write(f'ct = {enc_flag.hex()}\n')
    f.write(f'p = {str(cipher.key.p)[::2]}\n')
    f.write(f'q = {str(cipher.key.q)[1::2]}')

In this challenge, we know the number $n$ ( $e$ is default as 0x10001), and “partial” version of $p$ and $q$ :

01x5x1x4x4x1x4x7x3x3x5x7x1x3x6x1x5x2x9x8x5x2x1x6x9x8x0x3x9x7x5x2x5x5x9x1x3x0x5x8x7x5x0x9x4x2x8x8x7x3x8x8x2x0x6x9x9x0x6x9x2x7x1x6x7x4x0x2x2x1x6x7x9x0x2x6x4x3
0x1x5x6x2x4x3x4x2x0x0x5x7x7x4x1x6x6x5x2x5x0x2x4x6x0x8x0x6x7x4x2x6x5x5x7x0x9x3x5x6x7x3x9x2x6x5x2x7x2x3x1x7x5x3x0x1x6x1x5x4x2x2x3x8x4x5x0x8x2x7x4x2x6x9x3x0x5x

This is quite the same technique as mentioned in this paper about partial bit of $p$ and $q$ . Instead of brute-forcing the bit of $p$ and $q$ , we will bruteforce the digits of $p$ and $q$ . We can make this work because, considering the last $k$ digits of $p$ and $q$ as $p_k$ and $q_k$ , this must hold:

p_k * q_k \equiv n \pmod{10^k}

n = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
p = 151441473357136152985216980397525591305875094288738820699069271674022167902643
q = 15624342005774166525024608067426557093567392652723175301615422384508274269305
str_p = str(p)
str_q = str(q)
str_n = str(n)
p_slots = ['x'] * len(str_p) * 2
q_slots = ['x'] * len(str_q) * 2

for i in range(len(str_p)):
    p_slots[i * 2] = str_p[i]

for i in range(len(str_q)):
    q_slots[i * 2 + 1] = str_q[i]

q_slots.append('x')
q_slots = ['0'] + q_slots
p_slots.pop()
p_slots = ['0'] + p_slots

def check_suitable(p_slots, q_slots, index):
    # print(index)
    # take last `index` digits of p_slots, q_slots
    # print(p_slots[-index:], q_slots[-index:])
    p = int(''.join(p_slots[-index:]))
    q = int(''.join(q_slots[-index:]))
    # take last 2*index digits of n
    str_n_tmp = str_n[(-index):]
    # print(p, q, n, p*q)
    # print("depth", index)
    # print(str(p*q)[-(index):], str(n))
    str_pq = str(p*q)[-index:]
    if str_pq in str_n_tmp:
        # print("Found suitable p, q")
        return True
    return False

print(''.join(p_slots))
print(''.join(q_slots))
LEN = len(p_slots)

def search(p_slots, q_slots, index):
    if index < 2: 
        print("start with 2")
        return
    if index >= LEN: 
    #    print(''.join(p_slots))
    #    print(''.join(q_slots))
        int_p = int(''.join(p_slots))
        int_q = int(''.join(q_slots))
        if int_p * int_q == n:
            print("sol", int_p, int_q)
            return
        return 
    for digit_p in range(10):
        for digit_q in range(10):
            p_slots[-index] = str(digit_p)
            q_slots[-index+1] = str(digit_q)
            if check_suitable(p_slots, q_slots, index):
                p = int(''.join(p_slots[-index:]))
                q = int(''.join(q_slots[-index:]))
                # take last 2*index digits of n
                n = int(str_n[(-index):])
                print("partial p", p)
                print("partial q", q)
                print(n, p*q)
                # print("depth", index)
                # print(str(p*q)[-(index):], str(n))
                str_pq = str(p*q)[-index:]
                search(p_slots, q_slots, index+2)
            p_slots[-index] = 'x'
            q_slots[-index+1] = 'x'
    return

search(p_slots, q_slots, 2)

Actually, my script will crash, but in the error line it will show you the $q$ . Take this number and then you will have p = n // q. The left-over is just the matter of plugging the library in :)

HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}

Permuted (Hard)

In this challenge, we received the source as an implementation of the Permutation Group, as well as the exponent function of the Permutation Group. Just a little bit recap, with a generator $G$ , the multiplicative group of $G$ is an cyclic group, which has a finite order.

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

from hashlib import sha256
from random import shuffle

from secret import a, b, FLAG

class Permutation:
    def __init__(self, mapping):
        self.length = len(mapping)

        assert set(mapping) == set(range(self.length))     # ensure it contains all numbers from 0 to length-1, with no repetitions
        self.mapping = list(mapping)

    def __call__(self, *args, **kwargs):
        idx, *_ = args
        assert idx in range(self.length)
        return self.mapping[idx]

    def __mul__(self, other):
        ans = []

        for i in range(self.length):
            ans.append(self(other(i)))

        return Permutation(ans)

    def __pow__(self, power, modulo=None):
        ans = Permutation.identity(self.length)
        ctr = self

        while power > 0:
            if power % 2 == 1:
                ans *= ctr
            ctr *= ctr
            power //= 2

        return ans

    def __str__(self):
        return str(self.mapping)

    def identity(length):
        return Permutation(range(length))


x = list(range(50_000))
shuffle(x)

g = Permutation(x)
print('g =', g)

A = g**a
print('A =', A)
B = g**b
print('B =', B)

C = A**b
assert C.mapping == (B**a).mapping

sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)

hash = sha256()
hash.update(sec)

key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"

cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print('c =', encrypted)

Compute the order

In this, they perform a similar Diffie-Hellman Key Exchange on the Multiplicative Permutation Group. Actually, we can easily compute the order of the multiplicative permutation group of a known generator $G$ , by converting the elements into disjoint cycles. Then you can take the length of each disjoint cycles and compute the Least Common Multiplier of them to find the order of the group! Detail explaination is in here.

def cycles(perm):
    remain = set(perm)
    result = []
    while len(remain) > 0:
        n = remain.pop()
        cycle = [n]
        while True:
            n = perm[n]
            if n not in remain:
                break
            remain.remove(n)
            cycle.append(n)
        result.append(cycle)
    # print(result)
    list_res = []
    for res in result:
        list_res.append(len(res))
    result = 1
    for i in list_res:
        result = result*i//GCD(result, i)
    return result

What’s next?

With the order computed, we can use Pohlig-Hellman Algorithm to break the Discrete Logarithm of the group. Luckily, the order of the group generated by the provided order 839949590738986464 is fairly easy to crack (because its factors are so smalll~~)

Here is my solution for the challenge. The value of $G, A, B$ are removed because it’s so big :) You can install from other archives.

# use the class Permutation from the source
def brute(g, a, order=None):
    if order is None:
        return
    for i in range(order):
        if (g**i).mapping == a.mapping:
            return i
    return None

def pohlig_hellman(g, a):
    order_g = cycles(g.mapping)
    factors = factorint(order_g)
    X = []
    a_ = []
    for q, e in zip(factors.keys(), factors.values()): 
        a_.append(q**e)
        A = g**((order_g // q**e))
        B = a**((order_g // q**e))
        res = brute(A, B, cycles(A.mapping))
        X.append(res)
    res = crt(a_, X)
    return int(res[0])
g = ...
A = ...
perm_G = Permutation(g)
perm_A = Permutation(A)
a = pohlig_hellman(perm_G, perm_A)

# compute back the flag, via the C.
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

from hashlib import sha256
from random import shuffle
a = 83994959073898646
perm_B = Permutation(B)
C = perm_B**a 
sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)
sha256_hash = sha256()
sha256_hash.update(sec)

key = sha256_hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"
cipher = AES.new(key, AES.MODE_CBC, iv)
c = b'\x89\xba1J\x9c\xfd\xe8\xd0\xe5A*\xa0\rq?!wg\xb0\x85\xeb\xce\x9f\x06\xcbG\x84O\xed\xdb\xcd\xc2\x188\x0cT\xa0\xaaH\x0c\x9e9\xe7\x9d@R\x9b\xbd'
decrypted = cipher.decrypt(c)
print(decrypted)

HTB{w3lL_n0T_aLl_gRoUpS_aRe_eQUaL_!!}

Tsayaki (Hard)

from tea import Cipher as TEA
# from secret import IV, FLAG
IV = b'\x00'*8
FLAG = 'flag{test_flag}'
import os

ROUNDS = 10

def show_menu():
    print("""
============================================================================================
|| I made this decryption oracle in which I let users choose their own decryption keys.   ||
|| I think that it's secure as the tea cipher doesn't produce collisions (?) ... Right?   ||
|| If you manage to prove me wrong 10 times, you get a special gift.                      ||
============================================================================================
""")

def run():
    show_menu()
 
    server_message = os.urandom(20)
    print(f'Here is my special message: {server_message.hex()}')
    
    used_keys = []
    ciphertexts = []
    for i in range(ROUNDS):
        print(f'Round {i+1}/10')
        try:
            ct = bytes.fromhex(input('Enter your target ciphertext (in hex) : '))
            assert ct not in ciphertexts

            for j in range(4):
                key = bytes.fromhex(input(f'[{i+1}/{j+1}] Enter your encryption key (in hex) : '))
                assert len(key) == 16 and key not in used_keys
                used_keys.append(key)
                cipher = TEA(key, IV) # don't know IV 
                enc = cipher.encrypt(server_message)
                if enc != ct:
                    print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')
                    exit()
        except:
            print('Nope.')
            exit()
            
        ciphertexts.append(ct)

    print(f'Wait, really? {FLAG}')


if __name__ == '__main__':
    run()

In this challenge, we can see two points:

The IV is static, as it is imported from the secret module.
To pass each round, we have to send a 4 different keys for Tiny Encryption Algorithm, but must return in a same single ciphertext.

For the 1st part, actually it is fairly easy to do. From the CBC design, we have that:

C_1 = E(P_1 \oplus IV)

For $C_1, P_1$ are the first block of the ciphertext and plaintext. As we know the ciphertext (we choose it), and the plaintext (from decryption function that we implemented from Iced TEA), we can recover the IV:

IV = D(C_1) \oplus P_1

Done. Then for the 2nd quest, from the Wikipedia page of Tiny Encryption Algorithm, we know that the key is actually just 126-bit, not 128-bit. This is because we can flip both the most-significant-bit of K[0] and K[1], or K[2] and K[3], or both these 4 bits but the key is still equivalent. There is a paper about this, which you can refer to. Link. From this, we have 4 keys!

# from secret import FLAG
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b, size as size_int
from enum import Enum
import copy
from pwn import *

def extract_iv(enc, dec, key):
    cipher = Cipher(bytes.fromhex(key))
    enc = enc[:16]
    dec = dec[:16]
    # print(enc, dec)
    enc = bytes.fromhex(enc)
    dec = bytes.fromhex(dec)
    decrypted_enc = cipher.decrypt_block(enc)
    extracted_iv = xor(dec, decrypted_enc)
    print("extracted iv:", extracted_iv.hex()) 

IV = bytes.fromhex("0dddd2773cf4b908")
r = remote("94.237.63.46", 48008)

def related_keys(original_key):
    k = [b2l(original_key[i:i+64//16]) for i in range(0, len(original_key), 64//16)]
    keys = []
    keys.append(original_key)
    # flip k0 and k1 
    related_key1 = copy.deepcopy(k)
    related_key1[0] ^= (1 << 31)
    related_key1[1] ^= (1 << 31)
    keys.append(b''.join(l2b(related_key1[i]) for i in range(4)))
    # flip k2 and k3
    related_key2 = copy.deepcopy(k)
    related_key2[2] ^= (1 << 31)
    related_key2[3] ^= (1 << 31)
    keys.append(b''.join(l2b(related_key2[i]) for i in range(4)))
    # flip all 
    related_key3 = copy.deepcopy(k)
    related_key3[0] ^= (1 << 31)
    related_key3[1] ^= (1 << 31)
    related_key3[2] ^= (1 << 31)
    related_key3[3] ^= (1 << 31)
    keys.append(b''.join(l2b(related_key3[i]) for i in range(4)))
    return keys

class Mode(Enum):
    ECB = 0x01
    CBC = 0x02

class Cipher:
    # Use the file from Iced TEA

def generate_solution(target_plaintext):
    key = os.urandom(16)
    cipher = Cipher(key, IV)
    enc = cipher.encrypt(target_plaintext)
    keys = related_keys(key)
    return enc, keys

def main():
    print(r.recvuntil(b'Here is my special message: ').decode())
    target_plaintext = bytes.fromhex(r.recvline().strip().decode())
    for i in range(10):
        enc, keys = generate_solution(target_plaintext)
        print(r.recvuntil(b'Enter your target ciphertext (in hex) : ').decode())
        r.sendline(enc.hex())
        for i in range(4):
            print(r.recvuntil(f'your encryption key (in hex) : ').decode())
            r.sendline(keys[i].hex().encode())
    r.interactive()

main()

HTB{th1s_4tt4ck_m4k3s_T34_1n4ppr0pr14t3_f0r_h4sh1ng!}

ROT128 (Insane)

Okay, the final challenge! This is the challenge that took me most of the time (Mostly because I did not think of the right tool…)

import random, os, signal
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l
from secret import FLAG
FLAG = 'fake_flag'
ROUNDS = 3
USED_STATES = []
_ROL_ = lambda x, i : ((x << i) | (x >> (N-i))) & (2**N - 1)
N = 128

def handler(signum, frame):
    print("\n\nToo slow, don't try to do sneaky things.")
    exit()

def validate_state(state):
    if not all(0 < s < 2**N-1 for s in user_state[-2:]) or not all(0 <= s < N for s in user_state[:4]):
        print('Please, make sure your input satisfies the upper and lower bounds.')
        return False
    
    if sorted(state[:4]) in USED_STATES:
        print('You cannot reuse the same state')
        return False
    
    if sum(user_state[:4]) < 2:
        print('We have to deal with some edge cases...')
        return False

    return True

class HashRoll:
    def __init__(self):
        self.reset_state()

    def hash_step(self, i):
        r1, r2 = self.state[2*i], self.state[2*i+1]
        return _ROL_(self.state[-2], r1) ^ _ROL_(self.state[-1], r2)

    def update_state(self, state=None):
        if not state:
            self.state = [0] * 6
            self.state[:4] = [random.randint(0, N) for _ in range(4)]
            self.state[-2:] = [random.randint(0, 2**N) for _ in range(2)]
        else:
            self.state = state
    
    def reset_state(self):
        self.update_state()

    def digest(self, buffer):
        buffer = int.from_bytes(buffer, byteorder='big')
        m1 = buffer >> N
        m2 = buffer & (2**N - 1)
        self.h = b''
        for i in range(2):
            self.h += int.to_bytes(self.hash_step(i) ^ (m1 if not i else m2), length=N//8, byteorder='big')
        return self.h


print('Can you test my hash function for second preimage resistance? You get to select the state and I get to choose the message ... Good luck!')

hashfunc = HashRoll()

for _ in range(ROUNDS):
    print(f'ROUND {_+1}/{ROUNDS}!')
    server_msg = os.urandom(32)
    hashfunc.reset_state()
    server_hash = hashfunc.digest(server_msg)
    print(hashfunc.state)
    print(f'You know H({server_msg.hex()}) = {server_hash.hex()}')
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(2)
    user_state = input('Send your hash function state (format: a,b,c,d,e,f) :: ').split(',')
    try:
        user_state = list(map(int, user_state))
        if not validate_state(user_state):
            print("The state is not valid! Try again.")
            exit()
        hashfunc.update_state(user_state)
        if hashfunc.digest(server_msg) == server_hash:
            print(f'Moving on to the next round!')
            USED_STATES.append(sorted(user_state[:4]))
        else:
            print('Not today.')
            exit()
    except:
        print("The hash function's state must be all integers.")
        exit()
    finally:
       signal.alarm(0)

print(f'Uhm... how did you do that? I thought I had cryptanalyzed it enough ... {FLAG}')

In this hash function, we have a state $S$ where:

S[0], S[1], S[2], S[3] are integers in range [0, 127).
S[4], S[5] are 128-bit integers.

These states are randomized every time we run the digest() function of the hash function. The digest module takes a 32 bytes (256-bit) message $M$ , and split into two 128-bit halves $M_0$ and $M_1$ . The hash of the message is computed as:

\begin{cases} H_0 = M_0 \oplus (ROL(S_4, S_0) \oplus ROL(S_5, S_1)) \\ H_1 = M_1 \oplus (ROL(S_4, S_2) \oplus ROL(S_5, S_3)) \end{cases}

Then the total hash $H$ is the concatenation of these two $H_0$ and $H_1$ . $H = H_0 || H_1$ . The ROL is the bit left rotation function of 128-bit number, as defined in the source code.

To find a second pre-image that can produce the same hash as the original state, we have to find a tuple S' that holds two above equations. Also, we are restricted to not use the states of first 4 $S_0, S_1, S_2, S_3$ twice.

At the first look, I have tried lots of way to brute force the value… However, it seems not very successfully. But, I find one interesting finding: We can preset any 2 of the first 4 states, and then it seems that there are plenty of second pre-images that we can find.

Which means that, if I can write a brute-force tool good enough, then I can solve the challenge :D Actually, at the moment I write this writeup, I do not know why it is this case. I guess that it is just the nature of this hash function XD.

Also, thanks Giapppp so much for hinting me it is z3-solver is the tool I need :) After knowing this is z3, what you need is just applying the stuff I found… xDDDDD

from pwn import *
from z3 import *
import re 
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l
hex_pattern = re.compile(r'[0-9a-f]+')
N = 128
def solution(x0, x1):
    X0 = BitVecVal(x0, N)  
    X1 = BitVecVal(x1, N) 

    # Define the variables
    s0 = BitVecVal(127, N)
    s1 = BitVecVal(127, N)
    s2 = Int('s2')
    s3 = Int('s3')
    s4 = BitVec('s4', N)
    s5 = BitVec('s5', N)

    # Create a solver
    s = Solver()

    # Add the constraints
    s.add(RotateLeft(s4, s0) ^ RotateLeft(s5, s1) == X0)
    s.add(RotateLeft(s4, Int2BV(s2, N)) ^ RotateLeft(s5, Int2BV(s3, N)) == X1)

    # Add the range constraints
    s.add(s0 > 0, s0 < 128)
    s.add(s1 > 0, s1 < 128)
    s.add(s2 > 0, s2 < 128)
    s.add(s3 > 0, s3 < 128)
    # s.add(And(s4 > 0, s4 < 2**N - 1))
    # s.add(And(s5 > 0, s5 < 2**N - 1))

    # Check if a solution exists
    if s.check() == sat:
        m = s.model()
        return [127, 127, m[s2].as_long(), m[s3].as_long(), m[s4].as_long(), m[s5].as_long()]
    return None

p = remote("94.237.49.182", 44115)
for i in range(3):
    response = p.recvuntil(b":: ")
    response = response.decode()
    hex_string = hex_pattern.findall(response)
    res = []
    for i in range(len(hex_string)):
        if len(hex_string[i]) == 64:
            res.append(bytes.fromhex(hex_string[i]))
    m, h = res
    m0, m1 = m[:16], m[16:]
    h0, h1 = h[:16], h[16:]
    x0 = b2l(m0) ^ b2l(h0)
    x1 = b2l(m1) ^ b2l(h1)
    sol = solution(x0, x1)
    p.sendline(",".join(map(str, sol)).encode())

p.interactive()

HTB{k33p_r0t4t1ng_4nd_r0t4t1ng_4nd_x0r1ng_4nd_r0t4t1ng!}

Disclaimer: I am pretty sure that the last challenge ROT128 had another solution (which may be the intended solution). I am just a script kiddie so… :(

HTB Cyber Apocalypse 2024 - Writeup (Crypto)

Table of contents: