---
tags: 資安實務 - write up
---
# Crypyto - write up
# Week1 - write up
## [Lab] Grams
### 題意
維吉尼亞加密
題目包含四個檔案
- ngrams.json 是解題時，需要用到的機率表
- output.txt 是已經加密過後的檔案
- solve.py 包含了解題時有用的function
- vigenere.py 是一隻加密的檔案，可以看出output.txt是由一段文字、flag加密而來的。
### 解題
```python=
import random
import json
import functools as fn
import numpy as np
import string
import hashlib
charset = string.ascii_lowercase+string.digits+',. '
charset_idmap = {e: i for i, e in enumerate(charset)}
ksz = 80
def decrypt(ctx, key):
N, ksz = len(charset), len(key)
return ''.join(charset[(c-key[i % ksz]) % N] for i, c in enumerate(ctx))
def toPrintable(data):
ul = ord('_')
data = bytes(c if 32 <= c < 127 else ul for c in data)
return data.decode('ascii')
with open('./output.txt') as f:
ctx = f.readline().strip()[4:]
enc = bytes.fromhex(f.readline().strip()[6:])
ctx = [charset_idmap[c] for c in ctx]
with open('./ngrams.json') as f:
ngrams = json.load(f)
@fn.lru_cache(10000)
def get_trigram(x):
x = ''.join(x)
y = ngrams.get(x)
if y is not None:
return y
ys = []
a, b = ngrams.get(x[:2]), ngrams.get(x[2:])
if a is not None and b is not None:
ys.append(a+b)
a, b = ngrams.get(x[:1]), ngrams.get(x[1:])
if a is not None and b is not None:
ys.append(a+b)
if len(ys):
return max(ys)
if any(c not in ngrams for c in x):
return -25
return sum(map(ngrams.get, x))
@fn.lru_cache(10000)
def fitness(a):
plain = decrypt(ctx, a)
tgs = zip(plain, plain[1:], plain[2:])
score = sum(get_trigram(tg) for tg in tgs)
return score
def initialize(size):
population = []
for i in range(size):
key = tuple(random.randrange(len(charset)) for _ in range(ksz))
population.append(key)
return population
def crossover(a, b, prob):
r = list(a)
for i in range(len(r)):
if random.random() < prob:
r[i] = b[i]
return tuple(r)
def mutate(a):
r = list(a)
i = random.randrange(len(a))
r[i] = random.randrange(len(charset))
return tuple(r)
#=======================#
keys = np.array(initialize(7000))
scores = np.array([])
for i in keys:
scores = np.append(scores, fitness(tuple(i)))
keys = keys[scores.argsort()[::-1]][:600]
for m in range(2000):
np.random.shuffle(keys)
for i in range(len(keys)//2):
child = np.array(crossover(keys[i*2], keys[i*2+1], 0.5))
keys = np.concatenate((keys, [child]))
np.random.shuffle(keys)
for i in range(len(keys[i])//2):
keys[i] = mutate(keys[i])
scores = np.array([])
for i in keys:
scores = np.append(scores, fitness(tuple(i)))
keys = keys[scores.argsort()[::-1]][:600]
scores = scores[scores.argsort()[::-1]][:600]
print(m, int(scores[0]), decrypt(ctx, keys[0]))
```
其中 key[0]為評分最高的key[0],
透過key將密文解密後，比對是否有錯誤，再微調key。
將key解出來後，做vigenere.py裡的逆運算，即可得到flag。
## [Lab] POA
> nc edu-ctf.csie.org 42070
### 題意
```python=
#!/usr/bin/env python3
import os
from Crypto.Cipher import AES
key = os.urandom(16)
with open('flag', 'rb') as f:
flag = f.read()
class PaddingError(Exception):
pass
def pad(data):
padlen = 16 - len(data) % 16
return data + int('1' + '0' * (padlen * 8 - 1), 2).to_bytes(padlen, 'big')
def unpad(data):
for i in range(len(data) - 1, len(data) - 1 - 16, -1):
if data[i] == 0x80:
return data[:i]
elif data[i] != 0x00:
raise PaddingError
raise PaddingError
def encrypt(plain):
# random iv
iv = os.urandom(16)
# encrypt
aes = AES.new(key, AES.MODE_CBC, iv)
cipher = aes.encrypt(pad(plain))
return iv + cipher
def decrypt(cipher):
# split iv, cipher
iv, cipher = cipher[:16], cipher[16:]
# decrypt
aes = AES.new(key, AES.MODE_CBC, iv)
plain = aes.decrypt(cipher)
return unpad(plain)
def main():
print(f'cipher = {encrypt(flag).hex()}')
while True:
try:
decrypt(bytes.fromhex(input('cipher = ')))
print('YESSSSSSSS')
except PaddingError:
print('NOOOOOOOOO')
except:
return
if __name__ == '__main__':
main()
```
透過觀察發現在41行題目使用encrypt function將flag加密, 且轉換成16進制。
在42行的while迴圈就開始解密，但是程式不會告訴使用者解密的結果，而是padding是否正確
pad function是在block後面加一個0x80，再補0到長度為16的倍數。
所以unpad function就是從最後面一個block往前找，找第一個0x80，如果都是0的話，就代表padding正確，如果到0x80有一個不是0的byte的話那就代表padding錯誤。
### 解題
```python=
from pwn import *
r = remote('edu-ctf.csie.org', 42070)
q = r.recvline()
cipher = bytes.fromhex(q.split(b' ')[-1][:-1].decode())
print(cipher)
def xor(a,b):
return bytes(i^j for i,j in zip(a,b))
for block in range(2):
ok = b''
for i in range(16):
for j in range(256):
c = b'\x00'*(15-i)+bytes([j^0x80])
if i == 15:
c = b'\x00'*16 + c
c += ok
c += cipher[16*block+16:16*block+32]
p = c.hex().encode()
r.sendlineafter(b'cipher = ', p)
q = r.recvline()
print(p)
if q != b'NOOOOOOOOO\n':
ok = bytes([j]) + ok
print(xor(cipher[:16*block+16][-i-1:], ok))
break
r.interactive()
```
先去訪問server得到flag的密文。
對block裡面的16個bytes去做迴圈，每次都爆搜256 bytes的IV。
IV得到之後就去加上一個cipher block，解密之後如果得到不是NOOOOOO的話，那就把回傳的j放在ok裡面。
最終得到 :
> FLAG{d9f37ffa479f47ff}
## [0x01] nLFSR
### 題意
```python=
#!/bin/env python3 -u
import os
state = int.from_bytes(os.urandom(8), 'little')
poly = 0xaa0d3a677e1be0bf
def step():
global state
out = state & 1
state >>= 1
if out:
state ^= poly
return out
def random():
for _ in range(42):
step()
return step()
money = 1.2
while money > 0:
y = random()
x = int(input('> '))
if x == y:
money += 0.02
else:
money -= 0.04
print(money)
if money > 2.4:
print("Here's your flag:")
with open('./flag.txt') as f:
print(f.read())
exit(0)
print('E( G_G)')
```
由題目定義的step()中可以發現，題目是將一串隨機生成的亂數，作為state，透過LFSR每次輸出1 bit，而我們可以透過跟伺服器玩64次，收集每次LFSR的結果，再利用poly，還原出state，以此預測接下來每次伺服器做LFSR的結果。
Note:題目所使用的是https://www.embeddedrelated.com/showarticle/1114.php
Golios的LFSR，做法與上課教的LFSR不太一樣，但結果會一樣。 在此副上參考連結。
### 解題
```python=
from pwn import *
from sage.all import *
def guessToGetAns(r):
money = 1.2
outputArray = []
for guess in range(64):
r.sendline("0")
output = r.recvline()
output = output.decode("utf-8")[2:-1]
output = float(output)
#print(output)
if output > money:
outputArray.append(0)
else:
outputArray.append(1)
money = output
return outputArray
poly = 0xaa0d3a677e1be0bf
print(bin(poly))
#F.<x> = PolynomialRing(GF(2))
#F = PolynomialRing(GF(2), 'x')
F,x = PolynomialRing(GF(2), 'x').objgen()
P = x ** 64
for i in range(64):
#P = P + x**i*int(bin(poly)[65-i])
P = P + x**i*int(bin(poly)[i+2])
print(P)
C = companion_matrix(P, format='bottom')
print(C)
#generate reverce matrix of Poly_function
sol_C = copy(C) #let sol_C same size with C
temp = C ** 42
sol_C[0] = temp[0]
#excute next 63 round
for i in range(63):
temp = C ** (43*(i+2)-1)
sol_C[i+1] = temp[0]
print(sol_C.rank())
sol_C_invert = sol_C.inverse()
#get input
r = remote('edu-ctf.csie.org', '42069')
ans = guessToGetAns(r)
#reverce seed
b = vector(ans)
#sol_C * x = b
#x = sol_C^-1 * b
sol_C_invert = sol_C.inverse()
x = sol_C_invert * b
#pridict
prid_rusult = []
for i in range(65, 300):
temp = C ** (43*i-1)
prid = temp * x
prid_rusult.append(prid[0])
print(prid_rusult)
for i in prid_rusult:
r.sendline(str(i))
output = r.recvline()
output = output.decode("utf-8")
print(output)
```
## 心路歷程...
第一次接觸Crypyto老實說真的是挫折連連，從環境的安裝，到有許多令人害怕的數學，尤其是第二周跟第三周的課程，老實說重看了好幾次，但還是聽不太懂，更不用說解題了，請助教手下留情> <
Note: 試了許多安裝Sage的方式，最後成功安裝是使用Conda建一個新的環境，並且環境要在Linux底下才能運行! 光環境就搞了兩三天，最後還是遇到友善的台大同學，才得以裝完。
感謝nagi199a同學的幫助。
# Week2 - write up
## 【Lab】: LSB (Write Up)
### 題意
> nc edu-ctf.csie.org 42071
題目將Flag, 做random paddin 將Flag填充的長一點, 接著完成加密後, 將密文output給我們
```python=
#!/usr/bin/env python3
import random
from Crypto.Util.number import *
FLAG = open('./flag', 'rb').read()
def pad(data, block_size):
padlen = block_size - len(data) - 2
if padlen < 8:
raise ValueError
return b'\x00' + bytes([random.randint(1, 255) for _ in range(padlen)]) + b'\x00' + data
def main():
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = inverse(e, (p - 1) * (q - 1))
m = bytes_to_long(pad(FLAG, 128))
c = pow(m, e, n)
print(f'n = {n}')
print(f'c = {c}')
while True:
c = int(input())
m = pow(c, d, n)
print(f'm % 3 = {m % 3}')
try:
main()
except:
...
```
### 解題
此題LAB, 並不是回傳LSB的結果, 因為LSB是mod2,而此題是mod3, 因此在解密上, 我們需要乘的是3的反元素
```python=
from pwn import *
from Crypto.Util.number import *
r = remote('edu-ctf.csie.org', 42071)
q = r.recvline()
n = int(q[4:])
q = r.recvline()
c = int(q[4:])
e = 65537
a = inverse(3, n)
m = 0
b = 0
i = 0
f = 0
while True:
r.sendline(str(pow(a, i*e, n)*c%n).encode())
q = r.recvline()
mm = (int(q.split()[-1])-(a*b)%n)%3
if mm==0:
f+=1
if f==10:
break
else:
f = 0
b = (a*b+mm)%n
m = 3**i*mm+m
i+=1
print(m)
print(long_to_bytes(m))
```
FLAG{fcf8ab2bc7b42bbd00e5be2b3d311ec6e8a89526}
## 【Lab】: Pohel
### 題意
題目包含兩個檔案, 分別為
> pohel.py
> output.txt
pohel為加密了Flag的程式, 而output則是輸出結果
根據觀察, 可以看到我們只要解出key, 就能用還原出flag
pohel.py
```python=
#!/bin/env python3
import gmpy2
import random
import hashlib
def gen():
while True:
p = [gmpy2.next_prime(random.randrange(1<<32)) for _ in range(16)]
o = 2
for pi in p:
o *= pi
n = o + 1
if gmpy2.is_prime(n):
g = 2
if pow(g, o // 2, n) == n - 1:
return g, n
def main():
g, n = gen()
k = random.randrange(n - 1)
c = pow(g, k, n)
with open('flag.txt', 'rb') as f:
flag = f.read()
k = hashlib.sha512(str(k).encode('ascii')).digest()
enc = bytes(ci ^ ki for ci, ki in zip(flag.ljust(len(k), b'\0'), k))
print('g =', g)
print('n =', n)
print('c =', c)
print('flag =', enc.hex())
if __name__ == '__main__':
main()
```
output.txt
```
g = 2
n = 22975024372641088191783192950030840455936651367831116706532074148973552639475113523713622342956112126457710740633725263638116108451282253328304547
c = 3391562491073162069780474526700107230909189849786338234577033763865425503028855096698198069367193995675035849507973902223745251492606324520756666
flag = c401549a04656914f9288164f6298ccc09771d8805db7248e3162b86237cefd2621df96509d8d9f32dbd2f56c6c41414971b990f31f80ced0cfe4eac89f55a93
```
### 解題
利用Pohlig-Hellman解出key
#### Pohlig-Hellman
是其中一種解離散對數的方式
假如我們今天要算g^x^ (mod p) = y, 求x
根據費馬小定理, 一定有個order p-1而假設p-1為p~1~ * p~2~ * ... * p~k~
設g~i~ = g^(p-1)/Pi^ 有 order P~i~ (因為Pi乘進去會消掉P~i~ ,所以成立)
因為g~i~有order P~i~所以mod p時, (g~i~)^x^ = (g~i~)^(xmodPi)^ = y^(p-1)/Pi^ = h~i~
接著利用BSGS 列出各個X~i~ = x (mod P~i~)
再利用中國餘式定理解出X
```python=
from sage.all import *
from sage.groups.generic import bsgs
import random
import hashlib
with open("output.txt") as f:
g = int(f.readline().split()[-1])
n = int(f.readline().split()[-1])
c = int(f.readline().split()[-1])
flag_encrypt = f.readline().split()[-1]
print("g = " + g)
print("n = " + n)
print("c = " + c)
print("flag_encrypt = " flag_encrtpt)
fac = factor(n-1)
for i in fac:
f_list.append(i)
for i in f_list:
x = pow(g, (n-1) // i, n)
#print(f"x = {x}")
g_list.append(x)
for i in f_list:
x = pow(c, (n-1)//fa_, n)
h_list.append(x)
for i in range(len(f_list)):
x = bsgs(gi[i], hi[i], (0, f_list[i]))
#print(f"x{i} = {x}")
x_list.append(x)
k = crt(x_list, f_list)
k = hashlib.sha512(str(k).encode('ascii')).digest()
flag = bytes(int(k_) ^ int(f_) for k_, f_ in zip(k, bytes.fromhex(flag_encrypt)))
print(flag)
```
Flag
> FLAG{0e8dc88cd3dc6717bf1e98126ccd295e559f9a03}
#### 心路歷程
要搞懂Pohlig-Hellman真的很辛苦，感謝Leon Wang在解題時，幫忙解惑Pohlig-Hellman的問題，還有參考她的課堂筆記。
# Week3 - write up
## 【Lab】: LEA (Write Up)
### 題意
> nc edu-ctf.csie.org 42073
```python=
#!/usr/bin/env python3
import os,random,sys,string
from math import sin
from secret import FLAG, SECRET_PASSWORD
from hashlib import sha256
USERS = {}
USERS[b'Admin'] = SECRET_PASSWORD
USERS[b'Guest'] = b'No FLAG'
def MyHash(s):
A = 0x464c4147
B = 0x7b754669
C = 0x6e645468
D = 0x65456173
E = 0x74657245
F = 0x6767217D
def G(X,Y,Z):
return (X ^ (~Z | ~Y) ^ Z) & 0xFFFFFFFF
def H(X,Y):
return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF
X = [int((0xFFFFFFFE) * sin(i)) & 0xFFFFFFFF for i in range(256)]
s_size = len(s)
s += bytes([0x80])
if len(s) % 128 > 120:
while len(s) % 128 != 0: s += bytes(1)
while len(s) % 128 < 120: s += bytes(1)
s += bytes.fromhex(hex(s_size * 8)[2:].rjust(16, '0'))
for i, b in enumerate(s):
k, l = int(b), i & 0x1f
A = (B + H(A + G(B,C,D) + X[k], l)) & 0xFFFFFFFF
B = (C + H(B + G(C,D,E) + X[k], l)) & 0xFFFFFFFF
C = (D + H(C + G(D,E,F) + X[k], l)) & 0xFFFFFFFF
D = (E + H(D + G(E,F,A) + X[k], l)) & 0xFFFFFFFF
E = (F + H(E + G(F,A,B) + X[k], l)) & 0xFFFFFFFF
F = (A + H(F + G(A,B,C) + X[k], l)) & 0xFFFFFFFF
return ''.join(map(lambda x : hex(x)[2:].rjust(8, '0'), [A, F, C, B, D, E]))
def verify(*stuff):
return MyHash(b'&&'.join(stuff)).encode()
def main():
username = input('Welcome to our system!\nPlease Input your username: ').encode()
if b'&' in username:
print('nope')
exit(-1)
if username in USERS:
password = USERS[username]
else:
password = input("Are you new here?\nLet's set a password: ").encode()
USERS[username] = password
print(f'Hello {username.decode()}')
session = bytes.hex(os.urandom(10)).encode()
print(f'Here is your session ID: {session.decode()}')
print(f'and your MAC(username&&password&&sessionID): {verify(username,password,session).decode()}')
while True:
mac, *sess, cmd = bytes.fromhex(input('\nWhat do you want to do? ')).split(b'&&')
if mac == verify(username,password,*sess,cmd) and session in sess[0]:
if cmd == b'flag':
if username == b'Admin':
print(FLAG)
return
else:
print('Permission denied')
elif cmd == b'exit':
print('exit')
break
else:
print('Unknown command.')
else:
print('Refused!')
print('See you next time.')
if __name__ == '__main__':
main()
```
### 解題
```python=
from pwn import *
import os, random, sys, string
from math import sin
from hashlib import sha256
import socketserver
import signal
def ExtendedMao(s, A, B, C, D, E, F):
def G(X, Y, Z):
return (X ^ (~Z | ~Y) ^ Z) & 0xFFFFFFFF
def M(X, Y):
return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF
X = [int((0xFFFFFFFE) * sin(i)) & 0xFFFFFFFF for i in range(256)]
s_size = len(s) + 128
s += bytes([0x80])
if len(s) % 128 > 120:
while len(s) % 128 != 0: s += bytes(1)
while len(s) % 128 < 120: s += bytes(1)
s += bytes.fromhex(hex(s_size * 8)[2:].rjust(16, '0'))
for i, b in enumerate(s):
k, l = int(b), i & 0x1f
A = (B + M(A + G(B, C, D) + X[k], l)) & 0xFFFFFFFF
B = (C + M(B + G(C, D, E) + X[k], l)) & 0xFFFFFFFF
C = (D + M(C + G(D, E, F) + X[k], l)) & 0xFFFFFFFF
D = (E + M(D + G(E, F, A) + X[k], l)) & 0xFFFFFFFF
E = (F + M(E + G(F, A, B) + X[k], l)) & 0xFFFFFFFF
F = (A + M(F + G(A, B, C) + X[k], l)) & 0xFFFFFFFF
return ''.join(map(lambda x : hex(x)[2:].rjust(8, '0'), [A, F, C, B, D, E]))
for i in range(20):
passlength = i
r = remote('edu-ctf.csie.org', 42073)
r.sendlineafter(b'username: ', b'Admin')
r.recvline()
session = r.recvline()
session = session.decode().split(': ')[1][:-1]
mac = r.recvline()
mac = mac.decode().split(': ')[1][:-1]
A = int(mac[:8], 16)
F = int(mac[8:16], 16)
C = int(mac[16:24], 16)
B = int(mac[24:32], 16)
D = int(mac[32:40], 16)
E = int(mac[40:], 16)
MAC = ExtendedMao(b'&&flag', A, B, C, D, E, F)
print(MAC)
def partofmao(s):
s_size = len(s)
print(s_size-29)
s += bytes([0x80])
if len(s) % 128 > 120:
while len(s) % 128 != 0: s += bytes(1)
while len(s) % 128 < 120: s += bytes(1)
s += bytes.fromhex(hex(s_size * 8)[2:].rjust(16, '0'))
return s
partofMessage = partofmao(b'&&'.join([b'Admin', b'a'*passlength, session.encode()]))
partofMessage = partofMessage[9 + passlength:]
p = MAC.encode() + b'&&' + partofMessage + b'&&flag'
print("p:", p)
r.sendlineafter(b'do? ', p.hex().encode())
q = r.recvline()
print("q:", q)
r.close()
```
在ExtendedMao()定義了要回傳給server的hash值
然後第15行的s_size就需要加上上一個byte的長度128。
註:****此題code, 來自講師上課Demo****
第30行的for迴圈，因為passlenth大於20，所以重複執行20次，先傳Admin過去，就會回傳一個session、一個mac，然後得到的hash就是上一個block出來的A、F、C、B、D、E，再傳進去第47行的ExtendedMao繼續算hash。
明文就變成原本的message加上padding，所以第50行的partofmao就是再做padding的動作然後回傳。
最後在第62行補上'&&flag'。
執行完為下圖 :
FLAG{c2adf08fdd2baa1e0b0b0caacdcda65c8f5bad36}
Sign in with Wallet
Connect another wallet