---
# System prepended metadata

title: HW1
tags: [資訊安全實務]

---

---
tags: 資訊安全實務
---
#  HW1

## Padding
這題一個block的size是16 bytes，使用的padding是長度不是16的倍數的話會在後面補0x80跟0x00，padding後的第一個byte為0x80，後面全完0x00，而且這題的block cypher用的是CBC，配合上他檢查padding是否正確的格式後，要解出第一個block可以利用已知的iv一個byte慢慢暴力搜索後丟回去解密看padding是否正確，步驟分成
1. 要搜尋最後一個byte明文時，假設解密後的padding正確，表示解密後明文為0x80，接下來只要讓iv最後一個byte xor 0x80在xor我們暴力搜尋找到的數字就可得到正確的明文
2. 要搜尋接下來的bytes，要先讓剛剛找到的明文變成0x00，讓明文去xor 0x00後(實際上等於不用做xor)後得出來的結果再去xor原本的iv
3. 在暴力搜索我們現在要找的那個byte，若padding正確的話表示解密後的明文為0x80，之後的步驟同1
4. 一直做到搜完一個block後，就把找到的明文當作要解下一個block的iv，然後一直重複就能夠解出flag
5. FLAG = FLAG{31a7f10f1317f622}

code如下：
```python!
from pwn import *

def xor(a: bytes, b: bytes):
    result = bytes([(x ^ y) for x,y in zip(a,b)])
    return result

def find_flag(cypher: bytes):
    r.sendlineafter("cipher = ",cypher.hex())
    response = r.recvline().strip()
    if (response == b'YESSSSSSSS'):
        return True
    elif (response == b'NOOOOOOOOO'):
        return False

r = process("./server.py")
#r = remote("140.112.31.97",30000)
r.recvuntil("cipher = ")
flag = str(r.recvline().strip())
flag_hex = flag.split("b'")[1][:-1]
flag_byte = bytes.fromhex(flag_hex)
#block 16byte
block = 16
flag_plaintexts = b''
for i in range(0, len(flag_byte) - block, block): #blocks
    iv, cypher = flag_byte[i:i + block], flag_byte[i + block:i + block + block]
    iv_array = bytearray(iv)
    flag_plaintexts_block = b''
    for j in range(len(iv)): #1 block
        is_0x80 = False
        iv_array_temp = iv_array.copy()
        for k in range(256): # 1 byte
            iv_array_temp[len(iv) - j - 1] = k
            if find_flag(bytes(iv_array_temp) + cypher) == True:
                plain = (0x80) ^ k ^ iv[len(iv) - j - 1]
                flag_plaintexts_block = bytes([plain]) + flag_plaintexts_block[is_0x80:]
                iv_array[len(iv) - j - 1:] = bytearray((xor(iv[len(iv) - j - 1:] , flag_plaintexts_block)))
                print(flag_plaintexts_block)
                if k ==  iv[len(iv) - j - 1]:
                   is_0x80 = True
                else:
                    break
    flag_plaintexts = flag_plaintexts + flag_plaintexts_block
for i in range(len(flag_plaintexts)):
    if (flag_plaintexts[i] == 0x80):
        print(f'flag = {flag_plaintexts[:i].decode()}')
        break
r.close()
```
---

## LFSR
這題我的解題思路就是用投影片上面提到的分別爆搜LFSR1、LFSR2、LFSR3這三個，這三個都是2bytes的data，所以如果直接爆搜的話時間會花太久，因此我就拿很多不同的FLAG來去做加密後來看這三個跟最後的output相等的機率各有幾%
* LFSR1大約在47%到50幾%這之間
* LFSR2大概>=65%
* LFSR3大概>=68%
* FLAG = FLAG{dfuihj}

當然因為我的樣本數不夠多所以若這組數字找不到我就會再慢慢把機率下調去找，找flag的步驟如下
* 尋找LFSR3
    * 用兩個迴圈窮(2 bytes)舉所有在1 byte內printable的字元
    * 用窮舉的data去做LFSR的演算法，用LFSR3的feedback
    * 做完後跟我們已知道flag的output去做對比，若相等的機率大於68%的話就當作這個是flag的候選
* LFSR2跟LFSR1的部分基本一樣，就是將feedback及機率的部分修改一下就可以
* 最後將所有的LFSR候選拿去做MYLFSR後，看有沒有跟已知的output完全相等的，若有就代表這組合是flag

因為用原本的47%、65%及68%這組合我找不到flag，所以我就將L1先從47%慢慢下調1%，最後找到45%時就找到FLAG了，我心中下調的方法如下
* 一開始若L1設47%時找不到就慢慢下調1%，若調到40%還沒找到就換成L2
* L2同上，若調到60%還沒找到就換調L3
* L3下調同L2
* 最後在下條L1的機率時就找到了FLAG，若是上面的調整方法最後條完都還沒找到...，那我可能就會去找其他方法XD

code如下：
```python!
#!/usr/bin/env python3
from functools import reduce
import string

class LFSR:
    def __init__(self, init, feedback):
        self.state = init
        self.feedback = feedback
    def getbit(self):
        nextbit = reduce(lambda x, y: x ^ y, [i & j for i, j in zip(self.state, self.feedback)])
        self.state = self.state[1:] + [nextbit]
        return nextbit

class MYLFSR:
    def __init__(self, inits):
        inits = [[int(i) for i in f"{int.from_bytes(init, 'big'):016b}"] for init in inits]
        self.l1 = LFSR(inits[0], [int(i) for i in f'{39989:016b}']) #將 39989 轉成16bits 2進制
        self.l2 = LFSR(inits[1], [int(i) for i in f'{40111:016b}'])
        self.l3 = LFSR(inits[2], [int(i) for i in f'{52453:016b}'])
    def getbit(self):
        x1 = self.l1.getbit()
        x2 = self.l2.getbit()
        x3 = self.l3.getbit()
        return [x1, x2, x3, (x1 & x2) ^ ((not x1) & x3)]
    def getbyte(self):
        b = 0
        for i in range(8):
            b = (b << 1) + self.getbit()
        return bytes([b])

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

def match_bytes(a, b):
    if (len(a) == len(b)):
        counts = 0
        for i,j in zip(a,b):
            if (i == j):
                counts += 1
        return counts / len(a)
    return 0.0

def find_lfsr_candidate(equal_percent, flag_opt, feedback):
    lfsr_candidate = []
    for byte_1 in string.printable:
        for byte_2 in string.printable:
            FLAG_TRY = byte_1.encode() + byte_2.encode()
            lfsr = LFSR([int(i) for i in f"{int.from_bytes(FLAG_TRY, 'big'):016b}"], [int(i) for i in f'{feedback:016b}'])
            lfsr_opt = [lfsr.getbit() for _ in range(100)]
            percent = match_bytes(lfsr_opt, flag_opt)
            if (percent >= equal_percent):
                lfsr_candidate.append(FLAG_TRY)    
    return lfsr_candidate

flag_opt = [1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1]

#f1 0.47 f2 0.65 f3 0.68
#找lfsr3
lfsr3_candidate = find_lfsr_candidate(0.68, flag_opt, 52453)
#找lfsr2
lfsr2_candidate = find_lfsr_candidate(0.65, flag_opt, 40111)
#找lfsr1
lfsr1_candidate = find_lfsr_candidate(0.45, flag_opt, 39989)


isFlag = False
for i in lfsr3_candidate:
    for j in lfsr2_candidate:
        for k in lfsr1_candidate:
            lfsr = MYLFSR([k, j, i])
            lfsr_opt = [lfsr.getbit()[3] for _ in range(100)]
            percent = match_bytes(lfsr_opt, flag_opt)
            if int(percent) == 1:
                FLAG = k+j+i
                FLAG = "FLAG{" + FLAG.decode() + "}"
                print(f'flag = {FLAG}')
                isFlag = True
                break
        if isFlag is True:
            break
    if isFlag is True:
        break
```