# 2020程安 Crypto筆記01 (LFSR.HASH)
###### tags: `程式安全` `crypto`

## LFSR (Linear Feedback Shift Register)
- 給定一個initial state, 經過線性運算之後得到的結果成為下一輪的msb,並將lsb shift出作為output
- [Example](https://github.com/oalieno/Crypto-Course/tree/master/LFSR/Known-Plaintext-Attack)

> 1. init state = **s** = [s2, s1, s0] = [1, 0, 0]
> 2. feedback = **p** = [p2. p1, p0] = [0, 1, 1]
> 3. 線性運算
s[n+1] = s[n]*p[2] ^ s[n-1]*p[1] ^ s[n-2]*p[0]

    Note:
        XOR = ADD (mod 2)
        MUL = AND 

- source code

    # generate.py
    import random
    from functools import reduce

    class LFSR:
        def __init__(self, init, feedback):
            self.state = init
            self.feedback = feedback
        @classmethod
        def random(cls, size):
            init = [random.choice([0, 1]) for i in range(size)] # 隨機生成init state s [s0, s1, ..., sn-1]
            feedback = [random.choice([0, 1]) for i in range(size)] # 隨機生成feedback p [p0, p1, ..., sn-1]
            return cls(init, feedback)
        def getbit(self): # 生成新bit
            nextbit = reduce(lambda x, y: x ^ y, [i & j for i, j in zip(self.state, self.feedback)]) 
            #  sn = s[0]*p0 + s[1]*p1 + ... + s[n-1]*pn-1
            self.state = self.state[1:] + [nextbit] # 2nd s = [s1, s2, ..., sn-1, sn]
            return nextbit
        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)])

    FLAG = open('./flag', 'rb').read()
    assert FLAG.startswith(b'CTF{')

    lfsr = LFSR.random(16) # 生成16bit的state & feedback
    key = b''.join([lfsr.getbyte() for i in range(len(FLAG))]) # 產生長度跟FLAG一樣的key
    print(f'enc = {xor(FLAG, key).hex()}')

- output

    #output.txt
    enc = d0aa72cef8dab5baac

- Solve
:::info
想法
1. 已知init state(**s**)跟feedback(**p**)皆為**16bits**
2. 已知FLAG前四個字元是'CTF{'
FLAG ^ key = enc --> enc ^ FLAG = key
故可以獲得key的前四個字元 = 4byte * 8 = **32bits**
3. 已知的32bit key其實就是s0, ..., s31
4. 2m bit的key可以回推m bit的feedback (解聯立)
--> **berlekamp massey algo.**
:::

        #solve.sage
        from sage.matrix.berlekamp_massey import berlekamp_massey

        class LFSR:
            def __init__(self, init, feedback):
                self.state = init
                self.feedback = feedback
            @classmethod
            def random(cls, size):
                init = [random.choice([0, 1]) for i in range(size)]
                feedback = [random.choice([0, 1]) for i in range(size)]
                return cls(init, feedback)
            def getbit(self):
                nextbit = reduce(lambda x, y: x ^^ y, [int(i) & int(j) for i, j in zip(self.state, self.feedback)])
                self.state = self.state[1:] + [nextbit]
                return nextbit
            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 bytes2bits(x):
            return [int(i) for i in f'{int.from_bytes(x, "big"):0{len(x) * 8}b}']

        # recover feedback coefficients
        enc = bytes.fromhex('d0aa72cef8dab5baac') # FLAG跟KEY都有9個bytes
        key = xor(enc[:4], b'CTF{') # 還原key的前32bit
        s = [GF(2)(i) for i in bytes2bits(key)]
        feedback = berlekamp_massey(s).list() # 還原 [p0, p1,..., p15] 
                                              # Note: (x^2+ 2*x +3).list() = [3, 2, 1] (升冪)
        feedback = feedback[:-1] # 去掉x最高次的係數
        feedback = ([0] * 16 + feedback[:-1])[-16:] # 如果不夠前面補0

        # generate xor key to decrypt
        lfsr = LFSR(bytes2bits(key)[16:], feedback) # 由s16~s31計算接下來的state
        key = b''.join([lfsr.getbyte() for _ in range(5)]) # 計算剩下來的5byte key
        plain = xor(enc[4:], key) # 計算剩下5byte FLAG
        print(b'CTF{' + plain)

# todo
from sage.matrix.berlekamp_massey import berlekamp_massey as bp

def xor_every_bit(a, b):
	res = []
	for x,y in zip(a,b):
		res.append(x^y)
	return res
	
def byte2bit(byte_stream):
	bits_str = ''.join(format(byte, '08b') for byte in byte_stream)
	bits = [int(i) for i in bits_str]
	return bits

def solve_feedback(key_list):
    feedback = bp(key_list).list()
    return feedback[::-1]
	 
enc = 'd0aa72cef8dab5baac' # 9bytes： FLAG.key 都是9bytes
FLAG = b'CTF{'

# cal key_bit as list
enc = bytes.fromhex(enc)
key = xor_every_bit(enc[:4], FLAG)
key_bit = byte2bit(key)

p = solve_feedback(key_bit)
p = p[:-1]
p = [0]*(16-len(p)) + p

## HW1 COR
- 一層LFSR不夠,那就兩層吧XD
- 再不夠就三層(X
- [Ex](https://edu-ctf.csie.org/challenges/COR/generate.py)
1. LFSR(第一層)

    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
            # nextbit = ((s0&p0 ^ s1&p1) ^ ...) ^ ...
            # state每次拿掉LSB,shift right 1 bit並在MSB補上nextbit

2. MYLFSR(第二層)

    class MYLFSR:
    # input一個list,每個list都有2bytes(16bit),將其每個element都轉成bit array
    # 初始化l1, l2, l3的init跟feedback值
    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}'])
        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}'])
    
    # 取得nextbit x1,x2,x3, 再進行第二層LFSR 
    def getbit(self):
        x1 = self.l1.getbit()
        x2 = self.l2.getbit()
        x3 = self.l3.getbit()
        return (x1 & x2) ^ ((not x1) & x3)
    # 取得output
    def getbyte(self):
        b = 0
        for i in range(8):
            b = (b << 1) + self.getbit()
        return bytes([b])

    FLAG = open('./flag', 'rb').read()
    assert len(FLAG) == 12 # FLAG lenth = 12
    assert FLAG.startswith(b'FLAG{')
    assert FLAG.endswith(b'}') # FLAG = 'FLAG{xxxxxx}'
    FLAG = FLAG[5:-1] # FLAG = 'xxxxxx'

    lfsr = MYLFSR([FLAG[0:2], FLAG[2:4], FLAG[4:6]])
    print([lfsr.getbit() for _ in range(100)])

- Summery

    把input拆成三份R1, R2, R3,分別做lfsr得到x1, x2, x3
    for i in range(100):
        output[i] = (x1 & x2) ^ ((~x1) & x3)

- 想法:雖然多了一層,但還是可以用correlation attack處理
- Correlation Attack
- 建立一個x1.x2.x3.output的table
`ex: output = (x1&x2) ^ ((~x1)&x3)`
> x1 : 0.5
> x2 : 0.75
> x3 : 0.75

| x1 | x2 | x3 | output |
| --- | --- | --- | ------ |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

- 因此可以先嘗試用暴力枚舉R3,如果R3產生的x3跟output的相似度**接近0.75**,就有可能是正確的R3,同理可以暴力枚舉R2,找出可能的R2

        # cal similarity between 2 lists
        def correlation(a,b):
            cnt = 0
            for i, j in zip(a,b):
                if (i == j):
                    cnt += 1
            return cnt
            
        # brute force R3 (by cmp x3 with output)
        for R3 in list(product([0,1], repeat=16)): #產生所有可能性                     R3 = [R3[i] for i in range(16)]
            lfsr = MYLFSR([[0]*16, [0]*16, R3])
            x3 = []
            for i in range(100):
                x3.append(lfsr.l3.getbit())
            if (correlation(x3, output) >= 70): #概率訂為70%
                print(f'R3 : {R3}')
                R3_ = chr(int('0b' + ''.join([str(i) for i in R3[:8]]), 2)) + chr(int('0b' + ''.join([str(i) for i in R3[8:]]), 2))
                print(f'R3_ : {R3_}')

- 最後再爆破R1,利用R2跟R3算出out跟題目給的output做比較

    for i in printable:
        for j in printable:
            FLAG = bytes(i.encode()) + bytes(j.encode())
            lfsr = MYLFSR([FLAG, R2_.encode(), R3_.encode()])
            x1 = [lfsr.l1.getbit() for _ in range(100)]
            x2 = [lfsr.l2.getbit() for _ in range(100)]
            x3 = [lfsr.l3.getbit() for _ in range(100)]
            out = [((x1[i] & x2[i]) ^ ((not x1[i]) & x3[i])) for i in range(100)]
            if correlation(out, output) == 100:
                print('FLAG{' + FLAG.decode() + 'uihj' + '}')

## Hash
### Hash: 不可逆的單向函式,將任意長度資料轉換成固定長度資料(大集合mapping到小集合)
### Collision:
- 因為hash是大集合mapping到小集合,所以理論上如果資料夠多,產生的hash value會重複
> i.e. ∃ p1, p2 ∈ P ,
> s.t. H(p1) = H(p2) = q ∈ Q

- 現在很多hash function是基於Merkle–Damgård構造的演算法
> ex. SHA1. md5. SHA256


- Hash function的特點是
1. 給一個p,很容易推算出唯一的q (q = H(p))
2. 但如果給一個q,要逆推回p卻很難,更不用說要找到有同hash值的p1,p2

        因此要算出p的方法只有兩種
        [法I] 暴力破解  >> need time
        [法II] 對所有可能值做Hash,建立一個對應的table >> need space
        --> 有沒有更快又省空間的辦法...?

### 彩虹表: 用空間換取時間
:::info
對於Q = H( P ),另外建立一個algo. R, s.t P = R( Q )
由p0開始建立一個hash chain
∀ i < n, H(pi) = qi, R(qi) = pi+1, n取決於想要換多少時間
並記錄下每個(p0, pn)
ex. **p0** -> q0 -> p1 -> q1 -> p2 ... -> qn-1 -> **pn**

if給一個q想要找p
1. 首先比對有沒有pn = R(q)
2. 如果有,則p = pn-1 (因為H(pn-1) = q)
   如果沒有,則繼續比對pn-1是否=R(qn-1) = R(H(pn-1)) = R(H(R(q)))
3. 如果有,則p = pn-2
   沒有則以此類推

:::

### Length Extension Attack (長度擴展攻擊)
- Ex. MD5
1. 把message分成好幾個message block B0-Bm,每個block 512bit(64byte)
2. 如果最後一個block長度不足448(56byte),就加上'1+n個0'補足到448,而最後512-448=64bit(8byte)則是放message長度

            ex. secret + msg = 50byte
                --> little endian = 0x3200000000000000
            --> 50byte + 48bit(10...0) + 64bit(0x320...0)                     ```
        4. 每個block再分成16個32bit的組M0-M15
        5. 利用一個固定的128bit初始化向量,從B0開始進行計算,計算結果作為下一輪的向量,重複至Bm
        ![](https://i.imgur.com/FcYLn6p.png =500x300)
        
- **M**essage **A**uthentication **C**odes (**MACs**)
    - 用來驗證messge真實性
        - server會把一個只有server知道的secret跟需要驗證的messge進行字串串接,再用MD5或是SHA1等Merkle damgård結構的hash function取其hash值
    - 當攻擊者知道hash(secret||msg)以及secret長度時,就可以輕鬆推算出hash(secret||msg||padding||append||new_padding)
        > padding包含填充為448bit所需以及代表長度的64bit
        > append是攻擊者想要知道其hash值的new_msg
        > ||: 字串串接
        - 自己寫一個將hash(secret||msg||padding)作為hash(==new_msg||new_padding)的初始化向量的Hash運算,就可以得到在原本系統上secret||msg||padding||new_msg||new_padding的hash值囉

# old init vector(fixed)
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476

## for example (from CTF problem) ##
md5(secret + msg + padding) = '571580b26c65f306376d4f64e53cb5c7'

# new init vector #
# (manage by the md5 value previous)
A = 0xb2801557
B = 0x06f3656c
C = 0x644f6d37
D = 0xc7b53ce5

new_md5(new_msg + padding) = '79717e731df8699d1476fab654763560'
# new_md5(new_msg + padding) is as same as
# md5(secret + msg + padding + new_msg + new_padding)

- 好用的工具
    - [HashPump](https://github.com/bwall/HashPump)

## Block Cipher
- input固定長度: 把原始data切成好幾個固定長度的block進行加密,如果最後切完不足block size就補padding上去
- output固定長度: 把每個block各自用private key加密,得到的output也是固定長度
- private key常見為16byte,但也有24/32
- 
### AES
- 依加密方式區分成好幾種模式
    1. ECB: 最簡單的方式,各個block各自做加密,彼此間不相干擾
        `問題: 同樣的明文會產生同樣的密文`
        ![](https://i.imgur.com/Ay30QY4.png =300x200)

    2. CBC: 
        - 加密: 產生一個init vector(iv),從第一個block(b0)開始,先將iv跟b0做XOR再跟private key進行加密,產生的結果作為下一個block(b1)的iv
        ![](https://i.imgur.com/ZxeSy3F.png =300x200)
        - 解密: 從最後一個block的密文開始,先解密之後再跟前一個block的密文做XOR得到原始data

Ci = Ek(Pi XOR Ci-1)
Pi = Dk(Ci) XOR Ci-1

            - 好處: 解密可所有block平行計算


    3. CTR
        - 加密:初始化一個counter,第一個block將counter加密之後跟明文做xor, 第二個block將counter+1加密之後跟明文做xor,以此類推
            `init counter: F0F1F2F3 F4F5F6F7 F8F9FAFB FCFDFEFF`
            - 好處:可以平行計算,因為block之間無關,且解決ECB相同明文會產生相同密文的問題
            - 缺點: 如果攻擊者竄改密文,使用者解密之後無法察覺是否被竄改,依然無法解決完整性校驗的問題
    4. GCM (GMAC + CTR Mode)
        1. GMAC
        利用Galois Field(GF)乘法來計算msg的MAC,當private key為128bit時,密文以128bit為單位分組
            > Mh代表對密文做GF乘法乘上H
            > XOR相當於GF(2^128)中的加法

MAC = ((c0*H + c1) *H + c2) *H ...
= c0*H^n + c1*H^n-1 + ... + cn-1*H mod2^128

            ![](https://i.imgur.com/Nabq970.png)
        
        2. GCM
        先執行CTR之後再進行GMAC已產生一個tag(MAC值)
        ![](https://i.imgur.com/sgL0DlW.png)
            > h = Ek(ctr+0)
            > A = 附加消息
            > C = c0 + c1 + c2 + ... + cn-3
            > L = A的bit length + C的bit length
            > h = Ek(Jo)
                

MAC(Tag) = (((A*H +c0) *H + c1) *H +... + L) *H + h (mod 2^128)
= A*H^n + c0*H^n-1 + c1*H^n-2 + ... + cn-3*H^2 + L*H + h (mod 2^128)

            
### 相關的攻擊方式
#### Cut & Paste 攻擊 (ECB)
#### Prepend Oracle 攻擊 (ECB)
#### Bit Flipping(位元翻轉)攻擊 (CBC)
#### Padding Oracle 攻擊 (CBC)
- 使用CBC模式 + PKCS#7(一種padding格式)
    - Recall CBC

Ci = Ek(Pi XOR Ci-1)
Pi = Dk(Ci) XOR Ci-1

        由bit flipping攻擊,只要動了某個block的密文的第#個byte,就會影響到其他block的第#個byte 
        
    - PKCS#7 = PKCS#5:
        - 如果需要padding 1byte就用0x01填充
          如果需要padding 2byte就用0x02填充
          以此類推...
          > EX 以一個block 16byte為例
          > 明文 : ABCDEFGHIJ --> 10byte
          > + padding : ABCDEFGHIJ + '\x06' * 6

- 原理: 
    解密之後看最後一個byte就可以知道有#byte的padding,往回推#byte就能推算明文最後一個byte在哪 
    - 但如果解密之後padding格式錯誤,通常sever會用某種方式告訴使用者padding錯誤
    > Ex
    > 解密之後的明文 : ...\x03\x05\x03
    > 最後一個byte為0x03,此時往前3byte比對發現有不是0x03的byte
    > 噴padding錯誤
- 攻擊者只知道密文&解密之後是否padding正確,就可以暴力破解明文,**因為padding錯誤的機率其實很高**,因此只要能夠找到符合的基本上就是正確答案

recall
Ci = Ek(Pi XOR Ci-1)
Pi = Dk(Ci) XOR Ci-1

    :::info
    1. 假設明文的最後一個byte是padding 0x01
    2. 由`Pi = Dk(Ci) ^ Ci-1`可知`Dk(Ci) ^ Ci-1 == 0x01`
       雖然Dk(Ci)未知
       但可以藉由偽造`Ci-1`的最後一個byte( = 0-256)來讓server告訴我們
       當最後一byte = 0x01時, `Ci-1'`有沒有解
    3. 假設存在一個`Ci-1`,使得`Dk(Ci) = 0x01 ^ Ci-1'`,則

Pi = Dk(Ci) ^ Ci-1(原本的密文)
= (0x01 ^ Ci-1') ^ Ci-1

    4. 如果不存在,則假設明文最後1 byte是0x02
    :::
    
- 因此攻擊流程大概是
    1. 算明文的最後一個byte(可能為0x1-0xf = Pi')
        > 偽造Ci-1的最後一個byte為Ci-1',爆破找出可能的Pi'值
        > 如果是可能的值就會padding正確
        > 則Pi = Pi' ^ Ci-1 ^ Ci-1'

# 算last byte
for j in range(16):
for k in range(256):
c = cipher[(b_num-1) * 16:b_num * 16] #target block
c_prev = cipher[(b_num - 2) * 16 : (b_num - 1) * 16] #input vector
if (k != c_prev[-1]):
my_c = iv + cipher[:15] + bytes([k]) + c
if (oracle(my_c)): #check padding correction
print(f'ans : {k}')