---
# System prepended metadata

title: HTB Cyber Apocalypse CTF 2024 (Crypto)

---

# HTB Cyber Apocalypse CTF 2024 (Crypto)

## Primary Knowledge (Solved)
> HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}

* RSA暗号。

~~~
n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215
~~~

~~~
import math
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

m = bytes_to_long(FLAG)

n = math.prod([getPrime(1024) for _ in range(2**0)])
e = 0x10001
c = pow(m, e, n)

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n')
    f.write(f'{e = }\n')
    f.write(f'{c = }\n')
~~~

* 暗号化のスクリプトをよく見ると、`n`を求めるときに素数が一つしか使われていない。
    * しばらく気づかなかった。やられた。
    * `phi` は単純に`n-1`となるので、`d`を求めて普通に復号してあげれば良い。

~~~
from Crypto.Util.number import long_to_bytes

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

phi = n - 1
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m))
~~~

~~~
mito@mito-Virtual-Machine:~/ctf/hackthebox-cyber-apocalypse-ctf-2024/crypto-primary-knowledge/crypto_primary_knowledge$ python3 solve.py 
b'HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}'
~~~
## Blunt (Solved)
> HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}

* AES暗号。

~~~
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{'
~~~

~~~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}')
~~~

* `C ≡ g ^ ab (mod p)` なので、`A` と `B` から `a` と `b` が求まればいけそう。


* `y ≡ g ^ x (mod p)` となる `x` を求めることを離散対数問題というらしい。
    * https://tex2e.github.io/blog/crypto/DLP
    * `y` を `A` に対応させれば、`a` が求まる。(`b` も同様。)

* スクリプトを書いて復号。
~~~
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

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{'

def babystep_giantstep(g, y, p):
    m = int((p-1)**0.5 + 0.5)
    
    table = {}
    gr = 1
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p

    gm = pow(g, -m, p)
    ygqm = y
    for q in range(m):
        if ygqm in table:
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p

    return None

a = babystep_giantstep(g, A, p)
b = babystep_giantstep(g, B, p)
print("a : {}".format(a))
print("b : {}".format(b))

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

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)

pt = cipher.decrypt(ciphertext)
print(pt)
~~~

~~~
mito@mito-Virtual-Machine:~/ctf/hackthebox-cyber-apocalypse-ctf-2024/crypto-blunt/challenge$ python3 solve.py 
a : 2766777741
b : 1913706799
b'HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}\x01'
~~~

* ちょっとごみ入っちゃっているのは、パディング消し忘れてたせい。

## Partial Tenacity (Solved)
> HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}

* RSAの鍵を求める問題。
* 説明むずい。イメージは虫食い算みたいな感じ。↓こんなやつの掛け算版。

![image](https://hackmd.io/_uploads/r1Mfi3hp6.png)

* n と p と q が与えられ、p と q に関して、どちらも10進数で与えられるが、下記のような感じとなっている。
    * n は p * q
    * p は先頭の文字から1文字飛ばし (12345 の場合、135)
    * q は2文字目から1文字飛ばし (12345 の場合、24)

* n の1の位は、p の 1の位と q の1の位を掛け算したものなので、「pの1の位とqの1の位の積」の 1の位が n の1の位と等しくなるようにqの1の位を選ぶ。
* 同じように、n の10の位は「pの1の位とqの10の位の積の1の位」「pの10の位とqの1の位の積の1の位」「pの1の位とqの1の位の積の10の位」「nの1の位を計算したときの繰り上がり」の4つの数字を足したものの1の位となるので、それを満たすようにpの10の位を選ぶ。
* みたいなことをずーーーーーーーーーーーーーーーーーーーーーーーーーーーーっとやっていくとpとqが求まるので、それを使ってRSAの鍵を作って復号する。

* もっと良い方法がありそうな気もするが、思いつかなかった。
* コードめっちゃ汚いけど許してください。
~~~
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes

ct = long_to_bytes(int('7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476', 16))

#Test
#n = '174803567'
#partial_p = '163'
#partial_q = '35'

n = '118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003'
partial_p = '151441473357136152985216980397525591305875094288738820699069271674022167902643'
partial_q = '15624342005774166525024608067426557093567392652723175301615422384508274269305'

arr_n = []
for i in range(len(n)):
    arr_n.append(int(n[i]))
arr_n.reverse()

arr_p = []
for i in range(len(partial_p)):
    arr_p.extend([int(partial_p[i]), 'x'])
arr_p = arr_p[:-1]
arr_p.reverse()

arr_q = []
for i in range(len(partial_q)):
    arr_q.extend([int(partial_q[i]), 'x'])
arr_q.reverse()
arr_q.append('x')

table_current = [['x' for i in range(len(arr_p))] for j in range(len(arr_q))]
table_moveup = [[0 for i in range(len(arr_p))] for j in range(len(arr_q))]
moveup = 0
target = []
previous_target = []

for pi in range(len(arr_p)):
    for qi in range(len(arr_q)):
        if(arr_p[pi] != 'x' and arr_q[qi] != 'x'):
            table_current[pi][qi] = (arr_p[pi] * arr_q[qi]) % 10
            table_moveup[pi][qi] = (arr_p[pi] * arr_q[qi]) // 10

for ni in range(len(arr_n)):
    for pi in range(len(arr_p)):
        for qi in range(len(arr_q)):
            if(pi + qi == ni):
                target.append([pi, qi])
    
    digit_current = 0
    update = []
    for item in target: # item : [pi, qi]
        tmp = table_current[item[0]][item[1]]
        if(tmp != 'x'):
            digit_current += table_current[item[0]][item[1]]
        else:
            update = item

    if(len(update) == 0):
        break

    x = 0
    for item in previous_target:
        digit_current += table_moveup[item[0]][item[1]]

    digit_current += moveup

    for i in range(10):
        if((digit_current + i) % 10 == arr_n[ni]):
            x = i

    table_current[update[0]][update[1]] = (digit_current + x) % 10
    table_moveup[update[0]][update[1]] = (digit_current + x) // 10

    candidate = []
    if(arr_p[update[0]] == 'x'):
        update.append('p')
        for i in range(10):
            if((i * arr_q[update[1]]) % 10 == x):
                candidate.append(i)
    elif(arr_q[update[1]] == 'x'):
        update.append('q')
        for i in range(10):
            if((i * arr_p[update[0]]) % 10 == x):
                candidate.append(i)
    else:
        print('something wrong.')
        exit()

    if(len(candidate) > 1):
        print('too many candidate is appear. it needs a recursive function.')
        exit()
    else:
        if(update[2] == 'p'):
            arr_p[update[0]] = candidate[0]
            for i in range(len(arr_q)):
                if(arr_q[i] != 'x'):
                    table_current[update[0]][i] = (arr_p[update[0]] * arr_q[i]) % 10
                    table_moveup[update[0]][i] = (arr_p[update[0]] * arr_q[i]) // 10
        else:
            arr_q[update[1]] = candidate[0]
            for i in range(len(arr_p)):
                if(arr_p[i] != 'x'):
                    table_current[i][update[1]] = (arr_p[i] * arr_q[update[1]]) % 10
                    table_moveup[i][update[1]] = (arr_p[i] * arr_q[update[1]]) // 10

    previous_target = target
    target = []
    moveup = (digit_current + x) // 10

arr_p.reverse()
arr_q.reverse()

p = ''
for i in arr_p:
    p += str(i)
q = ''
for i in arr_q:
    q += str(i)

print('p : {}'.format(p))
print('q : {}'.format(q))

n = int(n)
p = int(p)
q = int(q)

e = 65537
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
u = pow(p, -1, q)

component = (n, e, d, p, q, u)
key = RSA.construct(component)
cipher = PKCS1_OAEP.new(key)

pt = cipher.decrypt(ct)
print(pt)

~~~

~~~
mito@mito-Virtual-Machine:~/ctf/hackthebox-cyber-apocalypse-ctf-2024/crypto-partial-tenacity/crypto_partial_tenacity$ python3 solve.py 
p : 10541549431842783633587614316112542499895727166990860537947158205451961334065983715903944224868775308489240169949600619123741969714205272515647199022167453
q : 11254692541324720060752707148186767582750062945630785066774422168535575089335596479399029695524722638167959390210621853422825328846580189277644256392390351
b'HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}'
~~~

## Iced TEA (Solved)
> HTB{th1s_1s_th3_t1ny_3ncryp710n_4lg0r1thm_____y0u_m1ght_h4v3_4lr34dy_s7umbl3d_up0n_1t_1f_y0u_d0_r3v3rs1ng}

* 関数 `encrypt` で実行されることと逆のことをしてあげればよい。

~~~
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''
        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 decrypt(self, msg):
        blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]
        
        ct = b''
        if self.mode == Mode.ECB:
            for pt in blocks:
                ct += self.decrypt_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)

    def decrypt_block(self, msg):
        m0 = b2l(msg[:4])
        m1 = b2l(msg[4:])
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1

        s = self.DELTA * 32
        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
        
        m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1

        return l2b(m)

if __name__ == '__main__':
    KEY = l2b(int('850c1413787c389e0b34437a6828a1b2', 16))
    cipher = Cipher(KEY)
    ct = l2b(int('b36c62d96d9daaa90634242e1e6c76556d020de35f7a3b248ed71351cc3f3da97d4d8fd0ebc5c06a655eb57f2b250dcb2b39c8b2000297f635ce4a44110ec66596c50624d6ab582b2fd92228a21ad9eece4729e589aba644393f57736a0b870308ff00d778214f238056b8cf5721a843', 16))
    pt = cipher.decrypt(ct)
    print(pt)
~~~
