CTF Team at the University of British Columbia

# [LINE CTF 2022] Crypto

27 Mar 2022 by - Kevin Liu

# ss-puzzle 

## Description

I had stored this FLAG securely in five separate locations. However, three of the shares were lost and one was partially broken. Can you restore flag?

Attachments: Share1, Share4, ss_puzzle.py

We’re given two raw files (Share1: 25243e2a3120271500000000000000002b0719073a0d2c2f0214251c09404813) and (Share4: 1d08081b2d1d12310331361e3319061c0607001b3a0f311f3933342926756706), along with the sharing scheme:

S = [None]*4
R = [None]*4
Share = [None]*5

S = FLAG[0:8]
S = FLAG[8:16]
S = FLAG[16:24]
S = FLAG[24:32]

# Ideally, R should be random stream. (Not hint)
R = FLAG[32:40]
R = FLAG[40:48]
R = FLAG[48:56]
R = FLAG[56:64]

Share = R            + xor(R, S) + xor(R, S) + xor(R,S)
Share = xor(R, S) + R            + xor(R, S) + xor(R,S)
Share = xor(R, S) + xor(R, S) + R            + xor(R,S)
Share = xor(R, S) + xor(R, S) + xor(R, S) + R
Share = xor(R, S) + xor(R, S) + xor(R, S) + xor(R,S)

# This share is partially broken.
Share = Share[0:8]   + b'\x00'*8       + Share[16:24] + Share[24:32]


## Solve

Luckily, we know that the flag format is LINECTF{, which corresponds to S.

From the first 8 bytes of Share, we can find R by performing xor(Share[:8], S). Similarly, knowing R, we can find S from the first 8 bytes of Share.

We can continue doing this until we find all 8-byte blocks:

s0 = b'LINECTF{'
r0 = xor(share1[0:8], s0)
s3 = xor(share4[0:8], r0)
r2 = xor(share1[16:24], s3)
s1 = xor(share4[16:24], r2)
r3 = xor(share4[24:], s0)
s2 = xor(share1[24:], r3)
r1 = xor(share4[8:16], s2)


Stitching the blocks together: LINECTF{Yeah_known_plaintext_is_important_in_xor_based_puzzle!!}

# X Factor 

## Description

Decrypt it!

Attachments: x_factor.md

I have generated a RSA-1024 key pair:
* public key exponent: 0x10001

Here are some known plain -> signature pairs I generated using my private key:
* 0x726fa7a7 -> 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb

**What is the signature of 0x686178656c696f6e?**

Take the least significant 16 bytes of the signature, encode them in lowercase hexadecimal and format it as LINECTF{sig_lowest_16_bytes_hex} to obtain the flag.
E.g. the last signature from the list above would become LINECTF{174c96f2c629afe74949d97918cbee4a}.


## Solve

I first skipped over the plaintext-signature pairs and tried to factor the modulus/find the private key (Alpertron ECM, Wiener’s attack), but unfortunately nothing came up.

Signing a message naively with RSA is raising the plaintext m to the private key d. In other words,

$m ^ d \equiv c \mod N$

Our goal is to find the value of

$(0x686178656c696f6e) ^ d \equiv c \mod N$

Usually this would require knowing the private key d, but notice that if:

$m_1 ^ d \equiv c_2 \mod N$ $m_2 ^ d \equiv c_1 \mod N$

Then,

$(m_1 \cdot m_2) ^ d \equiv c_1 \cdot c_2 \mod N$

So, we can try to express the value 0x686178656c696f6e as the product/division of the given plaintexts.

Looking closer at the values being signed:

• 0x945d86b04b2e7c7 factors as: [811, 947, 947, 947, 970111]
• 0x5de2 factors as: [2, 61, 197]
• 0xa16b201cdd42ad70da249 factors as: [970111, 2098711, 2098711, 2854343]
• 0x6d993121ed46b factors as: [947, 970111, 2098711]
• 0x726fa7a7 factors as: [61, 197, 197, 811]
• 0x31e828d97a0874cff factors as: [2098711, 2854343, 9605087]
• 0x904a515 factors as: [197, 811, 947]

And since 0x686178656c696f6e factors as: [2, 197, 947, 2098711, 9605087], our idea should likely work.

We can raise each value to a small negative or positive exponent, and see if the products match up to the target plaintext.

## Script

from factordb.factordb import FactorDB

e = 0x10001

q = []
...

'''
print out the factors of each plaintext
for i in range(len(q)):
f = FactorDB(q[i])
f.connect()
print(f"- {hex(q[i])} factors as: {f.get_factor_list()}")
'''

target = 0x686178656c696f6e
def recur(index, cur, sigs):
if index == len(q):
if abs(target - cur) < 10 ** 5:
print("Found: ", hex(sigs)[-32:])
return

for i in range(-3, 3):
recur(index + 1, cur * pow(q[index], i), sigs * pow(q[index], i, n) % n)

recur(0, 1, 1)



Flag: LINECTF{a049347a7db8226d496eb55c15b1d840}

# Baby crypto revisited 

## Description

Last time, our side-channel attack was quite easy. But our victim found out about our sneaky attack and increased the size of nonce. Fortunately, we could still capture the first half of the nonce, which is 64-bit this time. Now please help us to find out the encryption key again. The victim is using the secp160r1 curve. The following is the captured data: r, s, k, and hash respectively. Flag is LINECTF{}, e.g. LINECTF{0x1234}

The file contains 100 leaked signatures of the form:

0xe6b7c5a62d08e0216e1e7ed7948c96b74c0be9cd 0x49e1050393f885117de74e7a02d1091d67faa3d0 0xff07bbee67c3ab910000000000000000 0xe91f3200a87205d18a97bdf3bb3027c9f532c8a4
0x7e7b86c8624c9b597131bb883053b1856527a5ff 0x7787b9157fbbaf178ed091b23ce30b2e1ccf9abf 0x882f44f29c56aea60000000000000000 0x37c9f0d06570b0087430b9c66372e385839bb348
0x7951eb8b6ef6ebd080c0171252c53b40fd4ac3b5 0xe70efd784e8a5a35ebd875c4df23132324946e5f 0x842f1342234670730000000000000000 0x7635013447c4b0e7c637dde0b9f8f2eed2cda796


## Introduction

An important aspect of ECDSA is that the random nonce should always be secret and cryptographically random. In fact, attacks such as LadderLeak were able to recover the private key by repeatedly leaking less than one bit of the nonce. Trail of Bits has a nice post that explains how nonce biases can be exploited.

If you know the nonce of a given signature, where $H(m)$ is the hash of the message:

$s \equiv k^{-1}(H(m) + rd_a)$

You can rearrange the equation to solve for $d_a$, the private key:

$d_a \equiv r^{-1}(ks - H(m))$

The attack described in Biased Nonce Sense employs lattice to solve the hidden number problem, where you find a solution $x_1, x_2, … x_n, y$ to the linear equations:

$x_1 - t_1y + a_1 \equiv 0 \mod p$ $x_2 - t_2y + a_2 \equiv 0 \mod p$ $...$ $x_n - t_ny + a_n \equiv 0 \mod p$

ECDSA signatures also follow this structure:

$k_i - (s_i^{-1}r_i)d + (-s_i^{-1}h_i) \equiv 0 \mod n$

Since we’re given the first 64 bits of the nonce, we can write $k_i$ as $k_{ih} + k_{il}$, where $k_{il}$ represents the lower 64 bits and $k_{ih}$ the leaked nonce (i.e. 0x6c5c4d7eacb9103a0000000000000000)

So,

$k_l - (s_i^{-1}r_i)d + (k_h-s_i^{-1}h_i) \equiv 0 \mod n$

To solve the hidden number problem, we construct a lattice like shown, except with $(h_i s_i^{-1} - k_{ih})$ in the bottom row: Image Source: Trail of Bits

After LLL, the rows of the matrix should contain the lower 64 bits of the nonces $k_{1l}, k_{2l}, … k_{nl}$ that satisfy the above equations. Indeed, the second row produces: (1446378667213923537, 14375776078636111506, ... 18446744073709551616).

We can take any of these nonces and the corresponding signature to solve for the private key.

## Script

from Crypto.Util.number import *

with open('data.txt', 'r') as f:

# https://neuromancer.sk/std/secg/secp160r1
n = 0x0100000000000000000001f4c8f927aed3ca752257

sz = 100
B = 2 ** 64
sigs = [list(map(lambda a: int(a, 16), l.split())) for l in lines]

matrix = [ * (sz + 2) for _ in range(sz + 2)]

for i in range(sz):
matrix[i][i] = n

matrix[-2][-2] = B/n
matrix[-1][-1] = B

for i in range(sz):
r = sigs[i]
s = sigs[i]
k = sigs[i]
h = sigs[i]

matrix[-2][i] = r * inverse(s, n)
matrix[-1][i] = h * inverse(s, n) - k

m = Matrix(matrix)
m = m.LLL()

for r in m:
print(r)

# ^^ gives this (64-bit) nonce
k_lower = 1446378667213923537
r = sigs
s = sigs
k = sigs + k_lower
h = sigs

key = inverse(r, n) * (k * s - h) % n
print(hex(key))


Flag: LINECTF{0xd77d10fec685cbe16f64cba090db24d23b92f824}

The attack works even with only 2 signatures from the 100 provided!

# Forward-or 

## Description

I doubled the length of the key to make this cipher even more secure. Can you decrypt it?

Attachments: main.py, present.py, and output.txt

main.py:

class CTRMode():
def __init__(self, key, nonce=None):
self.key = key # 20bytes
self.cipher = DoubleRoundReducedPresent(key)
if None==nonce:
nonce = os.urandom(self.cipher.block_size//2)
self.nonce = nonce # 4bytes

def XorStream(self, data):
output = b""
counter = 0
for i in range(0, len(data), self.cipher.block_size):
keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big'))
if b""==keystream:
exit(1)

if len(data)<i+self.cipher.block_size:
block = data[i:len(data)]
block = data[i:i+self.cipher.block_size]
block = strxor(keystream[:len(block)], block)

output+=block
counter+=1
return output

def encrypt(self, plaintext):
return self.XorStream(plaintext)

def decrypt(self, ciphertext):
return self.XorStream(ciphertext)

class DoubleRoundReducedPresent():
def __init__(self, key):
self.block_size = 8
self.key_length = 160
self.round = 16
self.cipher0 = Present(key[0:10], self.round)
self.cipher1 = Present(key[10:20], self.round)

def encrypt(self, plaintext):
...
return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))

def decrypt(self, ciphertext):
...
return self.cipher0.decrypt(self.cipher1.decrypt(ciphertext))

if __name__ == "__main__":
...

if not re.fullmatch(r'[0-3]+', key):
exit(1)

key = key.encode('ascii')

flag = flag.encode('ascii')

plain = flag
cipher = CTRMode(key)
ciphertext = cipher.encrypt(plain)
nonce = cipher.nonce

print(ciphertext.hex())
print(nonce.hex())


present.py borrows the implementation from pypresent.py.

output.txt:

ciphertext_hex="3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0"
nonce_hex="32e10325"


## Introduction

First, note that the key is matched against the regex: [0-3]+, which means that the key only contains the digits 0 through 3. Since the key is 20 bytes, a brute-force would take around $4^{20} = 2^{40}$ tries, too slow considering that the cipher also needs to decrypt a message each time.

However, the DoubleRoundReducedPresent round reduced class immediately draws suspicion: it divides the key into two 10-byte pieces, and encrypts/decrypts a message sequentially.

This makes the cipher vulnerable to a meet-in-the-middle attack, the same principle that rendered Double DES insecure. Say that we know a single plaintext-ciphertext pair, encrypted by unknown keys $k_1$ and $k_2$:

Then,

$C = ENC_{k2}(ENC_{k1}(P))$ $DEC_{k2}(C) = ENC_{k1}(P)$

Instead of trying every combination of $(k_1, k_2)$, we can try all possible keys $k$, and calculate $DEC_{k}(C)$ and $ENC_{k}(P)$. If the decryption matches with a previous encryption, or vice versa, then we’ve found a potential pair of keys $(k_1, k_2)$. This attack would only take $4^{10} = 2^{20}$ operations since we’re brute-forcing all possible 10-byte keys.

## Solve

There’s one problem: we’re only given the ciphertext and nonce, not the corresponding plaintext. The CTRMODE generates a psuedo-random keystream by encrypting the nonce and counter. Afterward, it XORs the keystream with the plaintext to produce the ciphertext. We don’t know what $ENC(\text{nonce} + \text{counter})$ is, but we do know that the flag starts with LINECTF{!

So, we have a plaintext-ciphertext pair:

P = nonce + counter.to_bytes(4, 'big')
C = xor('LINECTF', ciphertext[:8])


Now, we can brute force all possible 10-byte keys.

## Script

from present import Present

...
ct = bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
nonce = bytes.fromhex("32e10325")

# take advantage of the known plaintext
counter = 0
plaintext = nonce + counter.to_bytes(4, 'big')

# data = block ^ keystream
# keystream = data ^ block
ciphertext = xor(b'LINECTF{', ct[:8])

pool_encrypted = {}
pool_decrypted = {}

# generate all 10-byte keys
possible = []
def recur(index, cur):
if index == 10:
possible.append(cur.encode('ascii'))
return

for i in range(4):
recur(index + 1, cur + str(i))

recur(0, "")

# meet-in-the-middle
cnt = 0
for cur in possible:
if cnt % 2 ** 16 == 0:
print("[x] Status: {cnt}")

cipher = Present(cur, 16)
encrypted = cipher.encrypt(plaintext)
decrypted = cipher.decrypt(ciphertext)

pool_decrypted[decrypted] = cur
pool_encrypted[encrypted] = cur

if encrypted in pool_decrypted:
print("Found!")
print("Encrypted key: ", cur)
print("Decrypted key: ", pool_decrypted[encrypted])

cnt += 1


The script spits out a single keypair, (3201323020, 2123003302).

After decryption, we get our flag: LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}.