HackTheBox Crypto 隨筆 4/20

, , , , ,

Before all

感覺今天晚上可以去開箱HARD的Crypto玩…
就先隨便丟點owob

Secure Signing

server.py 

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
from hashlib import sha256
from secret import FLAG

WELCOME_MSG = """
Welcome to my Super Secure Signing service which uses unbreakable hash function.
We combine your Cipher with our secure key to make sure that it is more secure than it should be.
"""


def menu():
    print("1 - Sign Your Message")
    print("2 - Verify Your Message")
    print("3 - Exit")


def xor(a, b):
    return bytes([i ^ j for i, j in zip(a, b)])


def H(m):
    return sha256(m).digest()


def main():
    print(WELCOME_MSG)

    while True:
        try:
            menu()
            choice = int(input("> "))
        except:
            print("Try again.")
            continue

        if choice == 1:
            message = input("Enter your message: ").encode()
            hsh = H(xor(message, FLAG))
            print(f"Hash: {hsh.hex()}")
        elif choice == 2:
            message = input("Enter your message: ").encode()
            hsh = input("Enter your hash: ")
            if H(xor(message, FLAG)).hex() == hsh:
                print("[+] Signature Validated!\n")
            else:
                print(f"[!] Invalid Signature!\n")
        else:
            print("Good Bye")
            exit(0)


if __name__ == "__main__":
    main()

觀察一下，會發現xor函數會根據長度比較小的資料進行xor，所以可以確認長度後在本地自己枚舉hash值找一樣的:D。

exp.py 

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
from pwn import *
from tqdm import *
from hashlib import *


flag=b''

r=remote('83.136.255.150', 30584)

def oracle(x):
    r.recv()
    r.sendline(b'1')
    r.recv()
    r.sendline(x)
    return r.recvline()[:-1].replace(b'Enter your message: ', b'').replace(b'Hash: ', b'')

# bruteforce flag length

past=b''
flag_length=0

for i in trange(1, 101):
    cur=oracle(b'\x00'*i)
    #print(cur)
    if cur==past:
        flag_length=i-1
        info(f"Flag length found:{flag_length}")
        break
    past=cur

# exploit
    
for i in range(1, flag_length+1):
    cur=oracle(flag+b'\x00')
    for c in string.printable:
        if cur==sha256(b'\x00'*(i-1)+c.encode()).hexdigest().encode():
            flag=flag+c.encode()
            info(f"Current:{flag.decode()}")
            break

Remeeting The Wheel

source.py

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
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes as l2b
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import FLAG
from hashlib import sha256

class RSAGen:
    def __init__(self, bits):
        self.bits = bits
    
    def keygen(self):
        p = getPrime(self.bits//2)
        q = getPrime(self.bits//2)
        self.n = p*q
        self.e = 0x10001
        phi = (p-1)*(q-1)
        self.d = pow(self.e, -1, phi)
        return (self.n, self.e), (p, q, phi, self.d)

    def encrypt(self, m):
        return pow(m, self.e, self.n)
    
    def decrypt(self, c):
        return pow(c, self.d, self.n)

class AESGen:
    def __init__(self, size):
        key1 = randint(1 << size, 1 << (size+1))
        key2 = randint(1 << size, 1 << (size+1))
        self.k = key1 * key2
        assert 40 <= self.k.bit_length() <= 42
        self.KEY = sha256(str(self.k).encode()).digest()

    def encrypt(self, m):
        cipher = AES.new(self.KEY, AES.MODE_ECB)
        enc_secret = cipher.encrypt(pad(m, 16))
        return enc_secret

def main():
    rsa = RSAGen(1024)
    aes = AESGen(20)
    pubkey, _ = rsa.keygen()
    enc_aes_key = l2b(rsa.encrypt(aes.k))
    enc_secret = aes.encrypt(FLAG)

    with open('output.txt', 'w') as f:
        f.write("Bob :: Hi Alice, here is my public key:\n")
        f.write(f"({pubkey[0]}, {pubkey[1]})\n")
        f.write("Alice :: Hi Bob, here is my encrypted AES key, don't forget to sha256-hash it!\n")
        f.write(f"Encrypted AES Key = {enc_aes_key.hex()}\n")
        f.write("Bob :: Got it, here is the encrypted secret you requested:\n")
        f.write(f"Encrypted Secret = {enc_secret.hex()}")


if __name__ == '__main__':
    main()

output.txt

1
2
3
4
5
6
Bob :: Hi Alice, here is my public key:
(72741423208033405403492275698762968936514657314823442485453559870105200118330405900858299998747406127848670334407387228444029070060538220448699667905891284937839901536444798774307744865631349770845980738192442639071823803272283670943732769371979418893953521892212745135191661138195973757608889180051128601323, 65537)
Alice :: Hi Bob, here is my encrypted AES key, don't forget to sha256-hash it!
Encrypted AES Key = 4da0230d2b8b46e3a7065f32c46df019739cc002a208cc37767a82c3e94edfc3440fa4b24a32274e35d5ddceaa33505c4f2a57281c3a5d6d4db3a0dbdbb30dbf373241319ce4a7fdd1780b6bafc86e37d283c9f9787c567434e2fc29c988fb05fd411fe4453ea40eb45fc41a423839b485e238dd2530fba284e9b07a0bba6546
Bob :: Got it, here is the encrypted secret you requested:
Encrypted Secret = ce8f36aa844ab00319bcd4f86460a10d77492c060b2c2a91615f4cd1f2d0702e76b68f1ec0f11d15704ba52c5dacc60018d5ed87368464acd030ce6230efdbff7b18cba72ccaa9455a6fe6021b908dd1

看起來不能直接暴力…
想一下，會發現只要枚舉介於 $2^{20}$ ~ $2^{21}$ 的數字之e次方mod n，然後透過枚舉其中一個數來尋找另一個(模逆元)就能在正常時間複雜度下完成。
就是 Meet in the Middle(?)
source.py 

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
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from tqdm import *

n, e=72741423208033405403492275698762968936514657314823442485453559870105200118330405900858299998747406127848670334407387228444029070060538220448699667905891284937839901536444798774307744865631349770845980738192442639071823803272283670943732769371979418893953521892212745135191661138195973757608889180051128601323, 65537

key=int('4da0230d2b8b46e3a7065f32c46df019739cc002a208cc37767a82c3e94edfc3440fa4b24a32274e35d5ddceaa33505c4f2a57281c3a5d6d4db3a0dbdbb30dbf373241319ce4a7fdd1780b6bafc86e37d283c9f9787c567434e2fc29c988fb05fd411fe4453ea40eb45fc41a423839b485e238dd2530fba284e9b07a0bba6546', 16)
enc=bytes.fromhex('ce8f36aa844ab00319bcd4f86460a10d77492c060b2c2a91615f4cd1f2d0702e76b68f1ec0f11d15704ba52c5dacc60018d5ed87368464acd030ce6230efdbff7b18cba72ccaa9455a6fe6021b908dd1')
def decrypt(key, m):
    key=sha256(str(key).encode()).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    enc_secret = cipher.decrypt(m)
    return enc_secret

def RSAkey(x):
    return pow(x, e, n)

pool={1}
table={0:0}
key1, key2=0, 0

for i in trange(2**20, 2**21):
    pool.add(RSAkey(i))
    table[RSAkey(i)]=i

for i in tqdm(pool):
#    print(i)
    if (key*inverse(i, n))%n in pool:
        key1=table[i]
        key2=table[(key*inverse(i, n))%n]
        break

print(decrypt(key1*key2, enc))

Quadratic Points

server.py 

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
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG
from utils import EllipticCurve, find_valid_quadratic_coefficients

import sys
import signal


def get_input_with_timeout(prompt, timeout):
    def alarm_handler(signum, frame):
        print("\nTime limit exceeded. Exiting...")
        sys.exit()

    signal.signal(signal.SIGALRM, alarm_handler)
    signal.alarm(timeout)

    try:
        input_data = input(prompt).strip()
        return int(input_data)
    except KeyboardInterrupt:
        pass
    finally:
        signal.alarm(0)  # Disable the alarm

    return None


for i in range(7):
    x1, x2 = find_valid_quadratic_coefficients()
    print(f'Hello Cryptographer, please enter the coefficients of the quadratic equation to proceed, hint: a*x^2 + b*x + c == 0, x = {x1}\n')

    ai = get_input_with_timeout("a: ", 2)
    bi = get_input_with_timeout("b: ", 2)
    ci = get_input_with_timeout("c: ", 2)

    res = ai * x1 ** 2 + bi * x1 + ci
    res *= 10 ** 13  # did you think I would be that careless?

    if int(res) != 0 or any(i == 0 or abs(i) > 60 for i in [ai, bi, ci]):
        print("Nope!")
        exit()

print("You passed the first test, now onto the second\n")

p = getPrime(40)
E = EllipticCurve(p, [bi, ci])
G = E.random_point()
flag = bytes_to_long(FLAG)
Gn = E.mul(flag, G)

print(f"G = {G.xy()}")
print(f"Gn = {Gn.xy()}")
print(f"p = {E.p}")

第一關要解二次函數，其實我不太確定在三個數字都<60的Case求高精度要怎麼做，但我就直接暴力😀(清澈的眼神)
exp.py 

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
from pwn import *
from time import sleep
import os

r=remote('94.237.49.182',51308)
def solve(x):
    for i in range(-60, 61):
        for j in range(-60, 61):
            for k in range(-60, 61):
                if int(10**13*(i*x**2+j*x+k)) ==0 :
                    return i, j, k

for i in range(7):
    x=r.recvline()
#    print(x)
    x=x.split(b' x = ')[1].replace(b'\n', b'').replace(b'a: ', b'')
    print(x)
    x=float(x)
    a, b, c=solve(x)
    r.recv()
    r.sendline(str(a).encode())
    r.recv()
    r.sendline(str(b).encode())
    r.recv()
    r.sendline(str(c).encode())

log=r.recvlines(5)
os.system(f'echo "{b} {c}" >> log.txt')
for i in range(2, 5):
    os.system(f'echo "{log[i].decode()}" >> log.txt')

再來是ECC的部分，因為flag不只40 bytes所以先用exp.py抓好幾個紀錄。
run.py 

1
2
3
import os
for i in range(30):
    os.system('python3 exp.py')

最後根據log.txt，因為每個數都很小，利可以直接用sage math的discrete_log求解，再CRT回去就可以。
solve.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
ords=[]
logs=[]
f=open('log.txt', 'r')
for _ in range(20):
    x=f.readline()[:-1].split(' ')
    a, b=int(x[0]), int(x[1])
    print(a, b)
    for i in range(3):
        exec(f.readline()[:-1])
    E = EllipticCurve(GF(p), [a, b])
    G=E(G)
    Gn=E(Gn)
    logs.append(discrete_log(Gn, G, G.order(), operation='+'))
    ords.append(G.order())
    print(long_to_bytes(int(crt(logs, ords))))

image