# HITCON CTF 2024 Writeup
## Hyper512
* Source:

import secrets
from hashlib import sha256

MASK1 = 0x6D6AC812F52A212D5A0B9F3117801FD5
MASK2 = 0xD736F40E0DED96B603F62CBE394FEF3D
MASK3 = 0xA55746EF3955B07595ABC13B9EBEED6B
MASK4 = 0xD670201BAC7515352A273372B2A95B23


class LFSR:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        b = self.state & 1
        self.state = (self.state >> 1) | (
            ((self.state & self.mask).bit_count() & 1) << (self.n - 1)
        )
        return b


class Cipher:
    def __init__(self, key: int):
        self.lfsr1 = LFSR(128, key, MASK1)
        key >>= 128
        self.lfsr2 = LFSR(128, key, MASK2)
        key >>= 128
        self.lfsr3 = LFSR(128, key, MASK3)
        key >>= 128
        self.lfsr4 = LFSR(128, key, MASK4)

    def bit(self):
        x = self.lfsr1() ^ self.lfsr1() ^ self.lfsr1()
        y = self.lfsr2()
        z = self.lfsr3() ^ self.lfsr3() ^ self.lfsr3() ^ self.lfsr3()
        w = self.lfsr4() ^ self.lfsr4()
        return (
            sha256(str((3 * x + 1 * y + 4 * z + 2 * w + 3142)).encode()).digest()[0] & 1
        )

    def stream(self):
        while True:
            b = 0
            for i in reversed(range(8)):
                b |= self.bit() << i
            yield b

    def encrypt(self, pt: bytes):
        return bytes([x ^ y for x, y in zip(pt, self.stream())])

    def decrypt(self, ct: bytes):
        return self.encrypt(ct)


if __name__ == "__main__":
    with open("flag.txt", "rb") as f:
        flag = f.read().strip()
    key = secrets.randbits(512)
    cipher = Cipher(key)
    gift = cipher.encrypt(b"\x00" * 2**12)
    print(gift.hex())
    ct = cipher.encrypt(flag)
    print(ct.hex())


# a790f917b594f5751b83a7b901f87680093b2eab35e375b2045b1cbba9052c431d7a21da43c3d52cebb583b67c5a4eb99a2e882fea0e1800a1993fcaafba4ce517bdf6c80ad8d1b5737ed80777ee581a21182bfc387f63841555652bbce45d6262c4f767c4faf7c5ad5b60c0c4253b316485e3a91ebc6d5a75dd940a935f3967a91812e75968c8b3f3bd0ce983dbc1f2166c063cb175b5447e76de7237aec59c33713e19defa2d75759e6f8175308e72618d7ade2deaf43c2c47f8eabcfaa39a471069979f0fb175a555c7f8369df7fda8181924e7eb3ef87f14336783e95fcac285902c14c3af485809d4139ac34ac5233c9a4e1e30873e3a5479e38496319b8f9e9f803b1fa73f75660278ac3c3c482a1943a40374f77767892b3a4bee959cd9100434d05a1b8f846429e4c80b040b2636fe8d7a4c8843c0ec8d74a1b145de81a87077b092d083388236c9b60dbbf7495d618855354f5c612be152cbaf41a56f7c7b452d8343f00c06baeaf7de5146366fb3b5ebc68ee3c2e6eef46a7e5306c2acc613afcf55a85ef319bb4c1333b5c057a1282abad88f23a1b216205791ca250dc3054df98412e5abf00578806d632577f98645de35d6f98dcc67795d45abbeac3db7c02e55c6b01375ca7fb4f74ea5c68e5539996de57b1282cce2e1775bffa5bc5d3a033f161572c979a92d83a8ec0c3b938d1c91983a1b14124a49ef893ea4685c9796a3c8b9dcf396b8c63b736de9f87ab57ede64ddd16430f53d7a8c1f91bab1976694e72f92d133264d41ce40f4806c0c57902d05d0660388805bf890fa3740ce87833a0fc2e23b52e816af7d2cc2661543d23ed33a1fc01d5d58fcb2db1e75790a6b06cc1f8921d94cefb2c1bc7c4415442a979b30ffbb0e8390c8e6bc6a3076777959522ea7d053d81671de01fd123d11960250ac517004afa1b375ea5cafe60bb5bdb8fef151a1dc068494a582616fa0460ff03f98e9c867edec107cdbdee478b42182cd598ebba1e01e992bf6e83009c4db6d28e63ed3b5b7944c64976a81c187b4a8c0423bb805ec61bb6f138afc4f146628e55486d3d6949554a7af3eeaec1376b8af320a20035bedff56d358345a85beca00c13fbf1e14e760503270294e3f4f8a330016a77f72fc5ca1c6401707337e334a191fca7fef47e61a9f750dd00200170b06887a866175a87c2e566591e1cf147f41a7dd837d9e045c62f8fb8f0bc6ee983dc6409ec2bf13f133e6bcf1ad904318d029e381f5c48613cb6f49f999a3c13850101bfaa39e6754636e7108485572b46cd140a034fa1d37d4d6b12fad7445dc8310173110a8b8cb3b4cd520593f9e6cd26e83f6a4d8319d59b3b576be8c46c223229f37e72eb6cc83bd9e66576dbfb7a9078c03af211276f35c27d6d3c570438126df32ae9dd13f0f8e8809ae0949c7fe897b87b5e311950147e9f16a88b14bc60ab2ca34ce6b249dd26f224a896f01a6c4adea6bfd33f96f030d52eb6676ba26c09b49119fee3e77191cd282387059ba2883de8c017ba67fe40cd16cd38486237930dd8dc7efb0513c68c3d4335b81201693e6ac148c9afb9c02096f0467f4f3c96841d37a0c23a252d5752f60af0ad3db8f15b48819effd7f4af27a60c966f49a0946cb878c50e640a560ad974ea3b577f76e15b4cc0743f28d4a81f7556715fb159504c904a8cd3635c49fba984e8b8880023813ee6d0ef04a4a778fbbd2c1b8862b69f31e5f4ef35d4e0a71dfeb519e3b3a1e672c31e4dfa5b09459b169aec350280cf65decb8c9e0726ac030b9b3aa91e236010742f63f8fc8d8f3de7aa013b198768c100ca1823a6146932e91c4c916cc614645a870ecd6833428df94c3a55c8a7244a8d61fb703175313456e3dabf8f580057e72a3057a3551ba7d572d336586ca7c237259ddbfe786a626c8060b586e8c42b9598ba82a5945af032ef0f22bcf93e45f56f7bf4b7bce735b24a37cdd5d1c7400e96a4de3a533dba8178f4329d1be4d3f2d99147da8d35607d2e4f823459a0595833b2adf0ee55ddf0c358bc4bfbc83d4b9bed97e5521fac784423e28dd5df72c9c271580a86e2a1d3ab599310e6d605fa56a7d797b6ed36be3d0579da2913e4eb7d7f97d094ee970aefabbb0d79d304fde0b70cb48e531298c9a5f8d84d132f301521367740d0b83e99aa40338fb22c6ad0c947e1c7f3e48ed8fb3bb00396af0c0eab9dfcb260432036724926aab9fb8c34894e44676fffe08ecb63d24abc796e20a67519ab9922e933e993644d75ea8f7ab6e7bdc4748012e67631f2f5bae6f4a81b07fd58d9d29d604499bd44aa9ed7c039769558e4e8ccab170f1974e5fcb54a5cb17e3d6b7d98cdb4730701a8975f6f26c4185b08bf9aa90cbb1c2d9bf3b720eec7b27417400ae302563cf53e0201bf81a88aaa5006b57941e29ba47491407c81dc007668bfb7885cf930d0cfd38c17758e779b9469d41a494511f1b738a2da86e975dc07ac9eb6f7342e1655091f8834f590e2630528a8feabcfdaee1d2cf4f49d5cf48392395238836dfbb6835afa5508678735b12d7cfded20d4242589b5c025f062a81aedd608a11f52dfecd02bd58c6d3233104a2b97b4c6b7f5059c0ecc8bf91da32a3915c593aa24b6a9e20bcfd48f982e00a91a6198074deeffbf22a6b56346d9895b5354091482d0776c37175144ca38f6002be755737c1233185a10251463e711435bf6c1034285497650c583ff370bee675a1653076ce4215dcf6b74019925dcd99194a0b46413e7201a69acee4975026f05daf95943ff27f13ce9017bfa964ef416ab7f1f109b5007e6b1ff82c277ebcc421cdfcead5e72d1d0c18a2cd132238128d8f4c2d17f123b04cc4af68b75379e80471b868875bd05c7ef6f4d194793260fc4442f41b5d40190b7e5c911448ddbd532ae9aa0fd6dc8d63b973188c40d88ccecbcdf995e935dacd7e50c7a16a66c60b65f72107c863ac6d60a3bdce99d06f56387c3498cfaca6b7ab688b364955b11d5d7ef05225b65181f58d582883b349ecc842ae14c8ffb1051e2c5332039a066497c780cdf039c66a2dba90e890b77620dc7e829e223fdf7e96505693cd70fb0431327825721061aa1b67c2438504a25e6d10b7938015e0be2be1ab80496ea28e7bd7ee2a931338cdb8e6c0766eac7a6489f3fc90b298bd3033d711bb7ec95d910834b7ec6935be420c52b6fa94045030ea92cbb9f708c7dc8288965b1e3683d1058f9c5a0d3aabc6b415a8fb5fdd98670d2e49958848010ce5bd297ad7870c36d2d5a1d92807ce0dafb1de6b9e50548af121865635534ecc1a5cb4c26f4af5f8ea19d2bc4315b23ef4531c39439801f9790293c79d3215f7f4de25516a78b1cf04bdce06e46b9a238b75104f5a6c79d3a73d5decb2f88af74a42cae3dc8a0a58dab27b81f496e0aca9cd820e4c92de8bfd3481567f83cd0b203875babd18ca99272d431dab864e19748a05f0414a8ee400d943e891f08336592d9a1a732d7d6cdb99bfa9b0f5ad49052004b3289a9e6f1a363e4a34c15accd1d63673a6ed5bf672fb24a184794980af075bf448e4f58426f1094583ac8ea39da417376687e6fa449344131f2ce38768a335df1e9008675ef1c40cfb7c0f1873086d4ee255fe0e3cca5bd34c15e44ccc377979d1005b33bc389eaaad1f892a1dd3cdfc014d315f52efcf95142cf2fcee6bfb40872ce8fd412fc0fa0b0be59813d9f587d961aa2a9eaf15eb0bf78dca8e6a64543cc423bea182e9326d20f07746f89ce30cadaf1fa17176bb00d92031ab4e3ab8d23b2bbf6683e360508e394ac542a45efc3a997f6f7909383e0dbde3042e2ec6eeca4a58bb15901b7fe20f93c5ce879dbda27ed660884aac5c61c0014894507b64aae26027e1976af5e0b7c585ce27737a6095d81fa069768c12dadd97810d362fb99f795e78553deff6112ea30176e1fd4798f7791e64144927a3051d3aa5356d803e2e04cecf1524400b87f1e2ae0f379f8acb0080d4b6caf9560ae295667eee6f8ecececd710d2043482ffb3186de3cd2b972d20dafcc2f0064142aa37a5ad5e8308c4dd3dde87e50a2cf7b2be60c0649bb7a8b50a3bb1a20e35f043fa8e65ab90cb7b0517210ffa3f6cf0c2714d1ddc9d9aa2710cfc7a6d03208f5e569998fcfa0c8599ab8e633619546c6793a232debddcae6847a20e2085a15a58dfe7879c32cea344f650382b568b773ecd696ce9a8bee6d971fe8545a4d8cbcec2ab8689fe33932ad7bdf68255775e06498d9f414a5494111b73997b5759824569dc7fd8fbc80f0ab6551bc0679690fd2dbfa6a76d5d17ddae2a5261b65c1dfe41eabee7124c11843f700d27d71316d39553edb793b70a73c1feb04ce2e920fc45214b187c1e6bc5c1814bb0b94ee8268cb326e60e7b00084ceb31c5a80cdae587d8fe5fdd1c22a8a493b7ae9ef22d09f2cc4282106a216134dd41ef89ab1b8174b82ff8ed9a288381d7e8248975cf5b12e97266e329c7752ea0e8eccad671dce399cd295b4462fd0866946c8e7bb75c6e2885a4ef62288737bff25a2c641948edf21115d3fbee53f1d6df6db7134c3517f93fc0f912fada2d2aa9df19496f881ed126bf22de27c41d3be11a4824be52c9efa4cc7157ef829b2e514c59e3b85639cf0a2c55c4e48c679eeb40f8d123edc138da02a75c82f3e9d06060b122fa23a3ddcc6cfa9229e2617b1d0d06e1be4f70389a210ddaa3fde718a3155bdb54b75cc0a9bfd939bf80260436c6f10296e273e2b9e8b8001b88a955ea6bc087007636269b9abdf075e9c71f291c3e3221d8c297b88d193e5a26fb1740b95af9f2ce3088bffac2f5aaf63370c1bcb77c3fafc7e7e0bc7a5d41de637536d87dc000d774af7f977a9688540ceb2068381eb9cd1bb2e51590534f66e7ba134bcbcddbdf62c2cf80c162f7c4ea57af6fe4fd83734d6161f77354a394125e37034ffb41c3ada3a48d15d4d97318b9fa67a98d930869fcf7aa39aabf4be7bda632d50253607ffdc7ba31c1a5dd48e9eb828ad8aa329e0d29118a402e0e2bdf460dc1926ffe4d3437133554d836c43c0a8170ba329157c31ebae1ba3c0e40c98180ffdc4dfd9435f607f972c909b324208193d8490ac26284e2f84fdba129b508eb818c36fe49d2181bce213c13917821ef3882e73c878e77a0f25792539f432c4987d4c02f35aa2b1cda09f8aba341809941dd804fc287ed59a477c610b883188cf2fdfd1c51f2fd3fbbda72fdc5257ae1d769bd71bc7048c899cc185de7bd849cfa732f3bf9b010e207f203dddcba1e855285233625e0e06676f68ef3e2acd77eb2dde1044f2f40e210d0ee1b1690710bbefdc2bddd78972eff559401c3e8dd095064cc61f10dd8e214e2d8a019d0686e9199c6fd79dd1928cf3cd8676e3f35221bec1b1c5a4d20b7b981e7508898cf682501446ebd9a542575b94ce7ca94d45f19d5ca7a426a4909da30092ab5716c4da1feee7e9a6990e1da86cb838fd392a25c1c3b6fa8e9a830f91b46805efc04eec66dee65642d0310a94ec194d5e8a6459f29e5fead9665387fce109f99cb687a461b2466045f47392a881903a051076ccbd37afdfe5a85a9d89e1e97fcc2279e54e6ffc7d66509fd0f5cb5af4b70fadcd584b1c86cc61b2b7d7565c11f32131291670167f79d6ef60b15f9598aa5a806dba706203a2e699740314ac47868628576308162f9eb930cf49b345865ca50eb1b3ca1abae9d776e19a313a9d2badd28fd907080bce17a671025ca2280fd754
# 16c63370ac3860ec7eb12f9ec357d462f8513ee887cd86481b521b2bd7995d8abecd595e2ef6fc554cb04d813848b19c06290f0818274303842e68fdc280f1fec612826f

### **LFSR** là gì?
* **[LFSR](https://en.wikipedia.org/wiki/Linear-feedback_shift_register)** (~Linear Feedback Shift Register~) là một loại mạch điện tử đặc biệt được sử dụng trong các ứng dụng như mã hóa, tạo số ngẫu nhiên, và kiểm tra lỗi. LFSR là một thanh ghi dịch mà trong đó đầu vào của mỗi bit được xác định bởi một hàm tuyến tính của các bit khác trong thanh ghi.
* **Cấu trúc cơ bản của LFSR:**
Thanh ghi dịch (Shift Register): Đây là một dãy các bit có thể dịch sang phải hoặc trái.
Hàm phản hồi tuyến tính (Linear Feedback): Là hàm toán học xác định bit mới sẽ được thêm vào thanh ghi sau mỗi lần dịch. Hàm này thường là phép XOR của một số bit trong thanh ghi.
* **Hoạt động của LFSR:**
1. Khởi tạo: LFSR được khởi tạo với một giá trị ban đầu, thường gọi là "seed".
2. Dịch: Tại mỗi bước, toàn bộ các bit trong thanh ghi dịch sang một vị trí.
3. Phản hồi: Bit mới nhất được tạo ra bằng cách thực hiện phép XOR trên một số bit trong thanh ghi (theo định nghĩa của hàm phản hồi).
4. Chu kỳ: LFSR tiếp tục dịch và tạo bit mới cho đến khi trở về giá trị ban đầu hoặc đạt đến một trạng thái nào đó, tạo thành một chu kỳ.
* **Ứng dụng:**
Mã hóa: LFSR được sử dụng trong mã hóa dòng (stream cipher) để tạo ra chuỗi bit giả ngẫu nhiên.
Tạo số ngẫu nhiên: Do tính chất chu kỳ và khả năng tạo ra chuỗi bit có vẻ ngẫu nhiên, LFSR thường được sử dụng trong việc tạo số giả ngẫu nhiên.
Kiểm tra lỗi: LFSR cũng được sử dụng trong các mạch kiểm tra lỗi như CRC (Cyclic Redundancy Check).
* **Ví dụ**:

Cho seed = 01101001

Ta sẽ chọn 3 vị trí trong seed trên: Vị trí thứ 2, 5, và 7. 
Những vị trí này được gọi là tap. Như vậy, rõ ràng output sẽ phụ thuộc vào tap.

Ta XOR những bit của seed ở những tap:
seed[2] xor seed[5] xor seed[7] = 1 xor 1 xor 0 = 0

Sau đó ta đưa bit 0 này lên đầu seed, bỏ đi bit cuối. Đây là output
của chúng ta : 00110100

Ta lại có thể tiếp tục thực hiện thuật toán nếu ta không ưng ý với output.

* Đọc thêm tại :
https://codelearn.io/sharing/stream-cipher-lfsr
https://www.youtube.com/watch?v=Ks1pw1X22y4
https://www.youtube.com/watch?v=SVyTSfeO2do
### Giải.
* Với **LFSR** của bài này, chia làm 2 phần:
* 1 là `Combined generators` hay `linear`: tính toán trên 1 phương trình tuyến tính nào đó.
* 2 là `Fillter Generator`: tính toán trên 1 phương trình không tuyến tính, hay là các phép toán Boolean 
* Để giải quyết bài này thì dùng [Fast Correlation Attack](https://en.wikipedia.org/wiki/Correlation_attack)
* Đọc thêm về nó tại [đây](https://iacr.org/archive/fse2011/67330055/67330055.pdf)
* Dựa vào đoạn code này thì mình đi xây dựng bảng chân trị và tìm dạng chuẩn tắc đại số của nó.
* Code gen bảng chân trị:

from Crypto.Util.number import *
from pwn import * 
from gmpy2 import * 
import math
from tqdm import tqdm
from sympy.ntheory.modular import crt
from sympy.ntheory.residue_ntheory import discrete_log
import secrets
import os
import secrets
from hashlib import sha256

def bit(x,y,z,w):
    return (
    sha256(str((3 * x + 1 * y + 4 * z + 2 * w + 3142)).encode()).digest()[0] & 1
)

print("-"*45)
print("|   x   |   y   |   z   |   w   | f(x,y,z,w)|")
for x in range(0,2):
    for y in range(0,2):
        for z in range(0,2):
            for w in range(0,2):
                print("|  ",x,"  |  ",y,"  |  ",z,"  |  ",w,"  |    ",bit(x,y,z,w),"    |")
print("-"*45)

* Bảng chân trị:

| x | y | z | w | f(x,y,z,w) |
|:-------- |:--------:|:--------:|:--------:| --------:|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |

* Dạng chuẩn tắc đại số : $f(x,y,z,w)=xyz+xyw+xzw+yw+y+z$
* Dựa vào bảng chân trị trên , ta thấy xác suất để $f(a) = a$ cho 4 giá trị là:
* $Probability (x) = 0,5$
* $Probability (y) = 0,625$
* $Probability (z) = 0,625$
* $Probability (w) = 0,375$
* Với **Fast Correlation Attack** thì việc recover lại từng phần tử sẽ khả quan khi $Prob>0,5$. $Prob<=0,5$ thì hên xui. Vậy tức là ở bài này thì ra sẽ recover được $y,z$ hay là $key_2,key_3$ trước.
* Đối với [paper này](https://iacr.org/archive/fse2011/67330055/67330055.pdf) thì thuật toán `Fast Correlation Attack` sẽ tính toán giá trị $p*$ gọi là xác suất đúng tại từng vị trí, rồi làm theo 2 thuật toán theo paper trên là **Algorithm A** và **Algorithm B**.
* **Algorithm B**:
* 1. Tính $p_i*$ với mỗi $keystream_i$ tương ứng dựa trên số lượng phương trình thỏa mãn.
* 2. Đảo ngược tất cả các $keystream_i$ nếu $p_i*$ < $p_{thr}$. Với $p_{thr}$ ở một ngưỡng nhất định nào đó.
* 3. Dừng lại tới khi hệ phương trình tuyến tính của mình giải được.
* Sau khi tìm được $key_2,key_3$ thì hãy xem bảng chân trị khi $y,z = 1$.
*
| x | y | z | w | f(x,y,z,w) |
|:---|:---:|:---:|:---:|-----------:|
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |

* Để lại cột $x,w$:
*
| x | w | f(x,w) |
|:---|:---:|---:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

* Bây giờ dạng chuẩn tắc đại số $f(x,w) = x + w$ .
* $x,w$ hay là $key_1,key_4$ tìm giống như trên.
* **Script**:

from sage.all import *
from sage.matrix.berlekamp_massey import berlekamp_massey
import secrets, random, sys
from hashlib import sha256
from sage.crypto.boolean_function import BooleanFunction
from functools import lru_cache
from tqdm import tqdm, trange
from chall import MASK1, MASK2, MASK3, MASK4, LFSR, Cipher
from binteger import Bin

F2 = GF(2)
PR = PolynomialRing(F2, "x")
x = PR.gen()

output_file = "output.txt" if len(sys.argv) < 2 else sys.argv[1]


stream = Bin(bytes.fromhex("a790f917b594f5751b83a7b901f87680093b2eab35e375b2045b1cbba9052c431d7a21da43c3d52cebb583b67c5a4eb99a2e882fea0e1800a1993fcaafba4ce517bdf6c80ad8d1b5737ed80777ee581a21182bfc387f63841555652bbce45d6262c4f767c4faf7c5ad5b60c0c4253b316485e3a91ebc6d5a75dd940a935f3967a91812e75968c8b3f3bd0ce983dbc1f2166c063cb175b5447e76de7237aec59c33713e19defa2d75759e6f8175308e72618d7ade2deaf43c2c47f8eabcfaa39a471069979f0fb175a555c7f8369df7fda8181924e7eb3ef87f14336783e95fcac285902c14c3af485809d4139ac34ac5233c9a4e1e30873e3a5479e38496319b8f9e9f803b1fa73f75660278ac3c3c482a1943a40374f77767892b3a4bee959cd9100434d05a1b8f846429e4c80b040b2636fe8d7a4c8843c0ec8d74a1b145de81a87077b092d083388236c9b60dbbf7495d618855354f5c612be152cbaf41a56f7c7b452d8343f00c06baeaf7de5146366fb3b5ebc68ee3c2e6eef46a7e5306c2acc613afcf55a85ef319bb4c1333b5c057a1282abad88f23a1b216205791ca250dc3054df98412e5abf00578806d632577f98645de35d6f98dcc67795d45abbeac3db7c02e55c6b01375ca7fb4f74ea5c68e5539996de57b1282cce2e1775bffa5bc5d3a033f161572c979a92d83a8ec0c3b938d1c91983a1b14124a49ef893ea4685c9796a3c8b9dcf396b8c63b736de9f87ab57ede64ddd16430f53d7a8c1f91bab1976694e72f92d133264d41ce40f4806c0c57902d05d0660388805bf890fa3740ce87833a0fc2e23b52e816af7d2cc2661543d23ed33a1fc01d5d58fcb2db1e75790a6b06cc1f8921d94cefb2c1bc7c4415442a979b30ffbb0e8390c8e6bc6a3076777959522ea7d053d81671de01fd123d11960250ac517004afa1b375ea5cafe60bb5bdb8fef151a1dc068494a582616fa0460ff03f98e9c867edec107cdbdee478b42182cd598ebba1e01e992bf6e83009c4db6d28e63ed3b5b7944c64976a81c187b4a8c0423bb805ec61bb6f138afc4f146628e55486d3d6949554a7af3eeaec1376b8af320a20035bedff56d358345a85beca00c13fbf1e14e760503270294e3f4f8a330016a77f72fc5ca1c6401707337e334a191fca7fef47e61a9f750dd00200170b06887a866175a87c2e566591e1cf147f41a7dd837d9e045c62f8fb8f0bc6ee983dc6409ec2bf13f133e6bcf1ad904318d029e381f5c48613cb6f49f999a3c13850101bfaa39e6754636e7108485572b46cd140a034fa1d37d4d6b12fad7445dc8310173110a8b8cb3b4cd520593f9e6cd26e83f6a4d8319d59b3b576be8c46c223229f37e72eb6cc83bd9e66576dbfb7a9078c03af211276f35c27d6d3c570438126df32ae9dd13f0f8e8809ae0949c7fe897b87b5e311950147e9f16a88b14bc60ab2ca34ce6b249dd26f224a896f01a6c4adea6bfd33f96f030d52eb6676ba26c09b49119fee3e77191cd282387059ba2883de8c017ba67fe40cd16cd38486237930dd8dc7efb0513c68c3d4335b81201693e6ac148c9afb9c02096f0467f4f3c96841d37a0c23a252d5752f60af0ad3db8f15b48819effd7f4af27a60c966f49a0946cb878c50e640a560ad974ea3b577f76e15b4cc0743f28d4a81f7556715fb159504c904a8cd3635c49fba984e8b8880023813ee6d0ef04a4a778fbbd2c1b8862b69f31e5f4ef35d4e0a71dfeb519e3b3a1e672c31e4dfa5b09459b169aec350280cf65decb8c9e0726ac030b9b3aa91e236010742f63f8fc8d8f3de7aa013b198768c100ca1823a6146932e91c4c916cc614645a870ecd6833428df94c3a55c8a7244a8d61fb703175313456e3dabf8f580057e72a3057a3551ba7d572d336586ca7c237259ddbfe786a626c8060b586e8c42b9598ba82a5945af032ef0f22bcf93e45f56f7bf4b7bce735b24a37cdd5d1c7400e96a4de3a533dba8178f4329d1be4d3f2d99147da8d35607d2e4f823459a0595833b2adf0ee55ddf0c358bc4bfbc83d4b9bed97e5521fac784423e28dd5df72c9c271580a86e2a1d3ab599310e6d605fa56a7d797b6ed36be3d0579da2913e4eb7d7f97d094ee970aefabbb0d79d304fde0b70cb48e531298c9a5f8d84d132f301521367740d0b83e99aa40338fb22c6ad0c947e1c7f3e48ed8fb3bb00396af0c0eab9dfcb260432036724926aab9fb8c34894e44676fffe08ecb63d24abc796e20a67519ab9922e933e993644d75ea8f7ab6e7bdc4748012e67631f2f5bae6f4a81b07fd58d9d29d604499bd44aa9ed7c039769558e4e8ccab170f1974e5fcb54a5cb17e3d6b7d98cdb4730701a8975f6f26c4185b08bf9aa90cbb1c2d9bf3b720eec7b27417400ae302563cf53e0201bf81a88aaa5006b57941e29ba47491407c81dc007668bfb7885cf930d0cfd38c17758e779b9469d41a494511f1b738a2da86e975dc07ac9eb6f7342e1655091f8834f590e2630528a8feabcfdaee1d2cf4f49d5cf48392395238836dfbb6835afa5508678735b12d7cfded20d4242589b5c025f062a81aedd608a11f52dfecd02bd58c6d3233104a2b97b4c6b7f5059c0ecc8bf91da32a3915c593aa24b6a9e20bcfd48f982e00a91a6198074deeffbf22a6b56346d9895b5354091482d0776c37175144ca38f6002be755737c1233185a10251463e711435bf6c1034285497650c583ff370bee675a1653076ce4215dcf6b74019925dcd99194a0b46413e7201a69acee4975026f05daf95943ff27f13ce9017bfa964ef416ab7f1f109b5007e6b1ff82c277ebcc421cdfcead5e72d1d0c18a2cd132238128d8f4c2d17f123b04cc4af68b75379e80471b868875bd05c7ef6f4d194793260fc4442f41b5d40190b7e5c911448ddbd532ae9aa0fd6dc8d63b973188c40d88ccecbcdf995e935dacd7e50c7a16a66c60b65f72107c863ac6d60a3bdce99d06f56387c3498cfaca6b7ab688b364955b11d5d7ef05225b65181f58d582883b349ecc842ae14c8ffb1051e2c5332039a066497c780cdf039c66a2dba90e890b77620dc7e829e223fdf7e96505693cd70fb0431327825721061aa1b67c2438504a25e6d10b7938015e0be2be1ab80496ea28e7bd7ee2a931338cdb8e6c0766eac7a6489f3fc90b298bd3033d711bb7ec95d910834b7ec6935be420c52b6fa94045030ea92cbb9f708c7dc8288965b1e3683d1058f9c5a0d3aabc6b415a8fb5fdd98670d2e49958848010ce5bd297ad7870c36d2d5a1d92807ce0dafb1de6b9e50548af121865635534ecc1a5cb4c26f4af5f8ea19d2bc4315b23ef4531c39439801f9790293c79d3215f7f4de25516a78b1cf04bdce06e46b9a238b75104f5a6c79d3a73d5decb2f88af74a42cae3dc8a0a58dab27b81f496e0aca9cd820e4c92de8bfd3481567f83cd0b203875babd18ca99272d431dab864e19748a05f0414a8ee400d943e891f08336592d9a1a732d7d6cdb99bfa9b0f5ad49052004b3289a9e6f1a363e4a34c15accd1d63673a6ed5bf672fb24a184794980af075bf448e4f58426f1094583ac8ea39da417376687e6fa449344131f2ce38768a335df1e9008675ef1c40cfb7c0f1873086d4ee255fe0e3cca5bd34c15e44ccc377979d1005b33bc389eaaad1f892a1dd3cdfc014d315f52efcf95142cf2fcee6bfb40872ce8fd412fc0fa0b0be59813d9f587d961aa2a9eaf15eb0bf78dca8e6a64543cc423bea182e9326d20f07746f89ce30cadaf1fa17176bb00d92031ab4e3ab8d23b2bbf6683e360508e394ac542a45efc3a997f6f7909383e0dbde3042e2ec6eeca4a58bb15901b7fe20f93c5ce879dbda27ed660884aac5c61c0014894507b64aae26027e1976af5e0b7c585ce27737a6095d81fa069768c12dadd97810d362fb99f795e78553deff6112ea30176e1fd4798f7791e64144927a3051d3aa5356d803e2e04cecf1524400b87f1e2ae0f379f8acb0080d4b6caf9560ae295667eee6f8ecececd710d2043482ffb3186de3cd2b972d20dafcc2f0064142aa37a5ad5e8308c4dd3dde87e50a2cf7b2be60c0649bb7a8b50a3bb1a20e35f043fa8e65ab90cb7b0517210ffa3f6cf0c2714d1ddc9d9aa2710cfc7a6d03208f5e569998fcfa0c8599ab8e633619546c6793a232debddcae6847a20e2085a15a58dfe7879c32cea344f650382b568b773ecd696ce9a8bee6d971fe8545a4d8cbcec2ab8689fe33932ad7bdf68255775e06498d9f414a5494111b73997b5759824569dc7fd8fbc80f0ab6551bc0679690fd2dbfa6a76d5d17ddae2a5261b65c1dfe41eabee7124c11843f700d27d71316d39553edb793b70a73c1feb04ce2e920fc45214b187c1e6bc5c1814bb0b94ee8268cb326e60e7b00084ceb31c5a80cdae587d8fe5fdd1c22a8a493b7ae9ef22d09f2cc4282106a216134dd41ef89ab1b8174b82ff8ed9a288381d7e8248975cf5b12e97266e329c7752ea0e8eccad671dce399cd295b4462fd0866946c8e7bb75c6e2885a4ef62288737bff25a2c641948edf21115d3fbee53f1d6df6db7134c3517f93fc0f912fada2d2aa9df19496f881ed126bf22de27c41d3be11a4824be52c9efa4cc7157ef829b2e514c59e3b85639cf0a2c55c4e48c679eeb40f8d123edc138da02a75c82f3e9d06060b122fa23a3ddcc6cfa9229e2617b1d0d06e1be4f70389a210ddaa3fde718a3155bdb54b75cc0a9bfd939bf80260436c6f10296e273e2b9e8b8001b88a955ea6bc087007636269b9abdf075e9c71f291c3e3221d8c297b88d193e5a26fb1740b95af9f2ce3088bffac2f5aaf63370c1bcb77c3fafc7e7e0bc7a5d41de637536d87dc000d774af7f977a9688540ceb2068381eb9cd1bb2e51590534f66e7ba134bcbcddbdf62c2cf80c162f7c4ea57af6fe4fd83734d6161f77354a394125e37034ffb41c3ada3a48d15d4d97318b9fa67a98d930869fcf7aa39aabf4be7bda632d50253607ffdc7ba31c1a5dd48e9eb828ad8aa329e0d29118a402e0e2bdf460dc1926ffe4d3437133554d836c43c0a8170ba329157c31ebae1ba3c0e40c98180ffdc4dfd9435f607f972c909b324208193d8490ac26284e2f84fdba129b508eb818c36fe49d2181bce213c13917821ef3882e73c878e77a0f25792539f432c4987d4c02f35aa2b1cda09f8aba341809941dd804fc287ed59a477c610b883188cf2fdfd1c51f2fd3fbbda72fdc5257ae1d769bd71bc7048c899cc185de7bd849cfa732f3bf9b010e207f203dddcba1e855285233625e0e06676f68ef3e2acd77eb2dde1044f2f40e210d0ee1b1690710bbefdc2bddd78972eff559401c3e8dd095064cc61f10dd8e214e2d8a019d0686e9199c6fd79dd1928cf3cd8676e3f35221bec1b1c5a4d20b7b981e7508898cf682501446ebd9a542575b94ce7ca94d45f19d5ca7a426a4909da30092ab5716c4da1feee7e9a6990e1da86cb838fd392a25c1c3b6fa8e9a830f91b46805efc04eec66dee65642d0310a94ec194d5e8a6459f29e5fead9665387fce109f99cb687a461b2466045f47392a881903a051076ccbd37afdfe5a85a9d89e1e97fcc2279e54e6ffc7d66509fd0f5cb5af4b70fadcd584b1c86cc61b2b7d7565c11f32131291670167f79d6ef60b15f9598aa5a806dba706203a2e699740314ac47868628576308162f9eb930cf49b345865ca50eb1b3ca1abae9d776e19a313a9d2badd28fd907080bce17a671025ca2280fd754")).list
flag_ct = Bin(bytes.fromhex("16c63370ac3860ec7eb12f9ec357d462f8513ee887cd86481b521b2bd7995d8abecd595e2ef6fc554cb04d813848b19c06290f0818274303842e68fdc280f1fec612826f")).list

m = len(stream)


def mask_to_poly(mask, n):
    return PR(list(map(int, f"{mask:0{n}b}"[::-1]))) + x**n


def poly_to_eq(poly):
    return [i for i, v in enumerate(poly) if v]


def poly_to_mask(poly):
    return int(poly.change_ring(ZZ)(2) - 2 ** poly.degree())


def vec_to_state(v):
    return int("".join(map(str, v[::-1])), 2)


@lru_cache
def S(p, t):
    if t == 1:
        return p
    return p * S(p, t - 1) + (1 - p) * (1 - S(p, t - 1))


def find_square_eqs(eq, length):
    # find related equations by squaring
    # i.e. a[k]=a[k+3]+a[k+4] -> a[k]=a[k+6]+a[k+8]
    assert eq[0] == 0, "eq must start with 0 (constant term)"
    eqs = [eq]
    cur_eq = eq
    while True:
        if cur_eq[-1] * 2 >= length:
            break
        squared_eq = [2 * x for x in cur_eq]
        eqs.append(squared_eq)
        cur_eq = squared_eq
    return eqs


def build_equations(eqs, length):
    # given a list of base equations, build all possible equations by shifting
    # and return a list of related equations (by index) for each position
    pos_eqs = [[] for _ in range(length)]
    new_eqs = []
    for eq in tqdm(eqs, "Build equations"):
        assert eq[0] == 0, "eq must start with 0 (constant term)"
        for shift in range(length - max(eq)):
            eq_index = len(new_eqs)
            new_eqs.append(eq)
            for pos in eq:
                pos_eqs[pos].append(eq_index)
            eq = [x + 1 for x in eq]
    return new_eqs, pos_eqs




def p_star_fn(p, m, h, s):
    p1 = p * s**h * (1 - s) ** (m - h)
    p2 = (1 - p) * s ** (m - h) * (1 - s) ** h
    return p1 / (p1 + p2)


def find_candidates(eqs, pos_eqs, stream, p_corr):
    # find candidate positions for noise estimation
    # given equations and related equations for each position
    # as well as the stream and the correlation probability
    length = len(stream)
    t = len(eqs[0])
    s = S(p_corr, t)
    candidates = []  # list of (p_star, pos)
    for pos in trange(length, desc="Find candidates"):
        h = 0  # number of satisfied equations at position pos
        for eq_index in pos_eqs[pos]:
            eq = eqs[eq_index]
            tmp = 0
            for i in eq:
                tmp ^= stream[i]
            h += tmp == 0
        m = len(pos_eqs[pos])
        p1 = p_corr * s**h * (1 - s) ** (m - h)
        p2 = (1 - p_corr) * s ** (m - h) * (1 - s) ** h
        p_star = p1 / (p1 + p2)
        candidates.append((p_star, pos))
    candidates.sort(reverse=True)
    return candidates


def get_linsys(feedback_poly, length):
    n = feedback_poly.degree()
    M = companion_matrix(feedback_poly, "bottom")
    # 1 ....
    #   1...
    #.....1
    # a1 a2 a3 ..
    Mn = M**n
    rows = []
    I = matrix.identity(n)
    for i in trange(length // n + 1, desc="Get linear system"):
        rows.extend(I.rows())
        I *= Mn
    return rows


def take_linear_system(linsys, candidates, stream, to_take):
    mat = matrix(GF(2), [linsys[pos] for _, pos in candidates[:to_take]])
    target = []
    for p_star, pos in candidates[:to_take]:
        target.append(stream[pos])
    return mat, vector(GF(2), target)


def solve_fca(feedback_poly, eq, prob, stream):
    stream = stream[:]  # copy
    n = feedback_poly.degree()
    
    m = len(stream)
    t = len(eq)
    print(f"{S(prob, t) = }")
    eqs = find_square_eqs(eq, m)
    print(eqs)
    eqs, pos_eqs = build_equations(eqs, m)
  
    linsys = get_linsys(feedback_poly, m)
    candidates = find_candidates(eqs, pos_eqs, stream, prob)
    for it in range(100):
        p_thr = candidates[-m // 32][0]
        for p_star, pos in candidates:
            if p_star <= p_thr:
                stream[pos] = 1 - stream[pos]
        candidates = find_candidates(eqs, pos_eqs, stream, prob)

        if it >= 5:
            mat, target = take_linear_system(linsys, candidates, stream, 2 * n)
            try:
                return mat.solve_right(target)
            except ValueError:
                continue


f1 = mask_to_poly(MASK1, 128)
f2 = mask_to_poly(MASK2, 128)
f3 = mask_to_poly(MASK3, 128)
f4 = mask_to_poly(MASK4, 128)

g2 = x**612 + x**421 + 1

g3 = x**518 + x**475 + 1


assert g2 % f2 == 0
assert g3 % f3 == 0

key2 = solve_fca(f2, poly_to_eq(g2), 5 / 8, stream)
key3 = solve_fca(f3, poly_to_eq(g3), 5 / 8, stream)
print(key2 , key3)
k2 = vec_to_state(key2)
k3 = vec_to_state(key3)
print(f"{k2 = :#x}")
print(f"{k3 = :#x}")
lfsr2 = LFSR(128, k2, MASK2)
lfsr3 = LFSR(128, k3, MASK3)  # 4x of the original
stream2 = [lfsr2() for _ in range(m)]
stream3 = [lfsr3() for _ in range(m)]
print(
    "correlation stream ~ stream2",
    len([1 for x, y in zip(stream, stream2) if x != y]) / m,
)  # 3/8
print(
    "correlation stream ~ stream3",
    len([1 for x, y in zip(stream, stream3) if x != y]) / m,
)  # 3/8


# when y == z == 1, the output is x ^ w, which is linear
# so we a treat it as a 256-bit LFSR

lfsr1tmp = LFSR(128, 48763, MASK1)
lfsr4tmp = LFSR(128, 48763, MASK4)


def combined():
    x = lfsr1tmp() ^ lfsr1tmp() ^ lfsr1tmp()
    w = lfsr4tmp() ^ lfsr4tmp()
    return x ^ w


f1_cube = (companion_matrix(f1, "bottom") ** 3).charpoly()
f14 = berlekamp_massey([F2(combined()) for _ in range(2048)])

assert f14 == f1_cube * f4
linsys_14 = get_linsys(f14, m)

lhs = []
rhs = []
for i in range(m):
    s, s2, s3 = stream[i], stream2[i], stream3[i]
    if s2 == s3 == 1:
        lhs.append(linsys_14[i])
        rhs.append(s)
        if len(lhs) >= 256 + 10:
            break
key14 = matrix(F2, lhs).solve_right(vector(F2, rhs))
mask14 = poly_to_mask(f14)
k14 = vec_to_state(key14)
print(f"{k14 = :#x}")
lfsr14 = LFSR(256, k14, mask14)
stream14 = [lfsr14() for _ in range(m)]
for i in range(m):
    s, s2, s3, s14 = stream[i], stream2[i], stream3[i], stream14[i]
    if s2 == s3 == 1:
        assert s14 == s, "?????"

# then solve a linear system to get the initial states of LFSR1 and LFSR4 from their XOR

M1 = companion_matrix(f1_cube, "bottom")
M4 = companion_matrix(f4, "bottom")
T = F2**256
s1_0_sym = matrix(T.gens()[:128])
s4_0_sym = matrix(T.gens()[128:])
s1_1_sym = M1**128 * s1_0_sym
s4_1_sym = M4**128 * s4_0_sym
sol = (
    (s1_0_sym + s4_0_sym)
    .stack(s1_1_sym + s4_1_sym)
    .solve_right(vector(F2, stream14[:256]))
)
key1 = list(sol[:128])
key4 = list(sol[128:])
k1 = vec_to_state(key1)
k4 = vec_to_state(key4)
print(f"{k1 = :#x}")
print(f"{k4 = :#x}")
lfsr1 = LFSR(128, k1, poly_to_mask(f1_cube))
lfsr4 = LFSR(128, k4, MASK4)
stream1 = [lfsr1() for _ in range(m)]
stream4 = [lfsr4() for _ in range(m)]


def mix(x, y, z, w):
    return sha256(str((3 * x + 1 * y + 4 * z + 2 * w + 3142)).encode()).digest()[0] & 1


rec = [mix(x, y, z, w) for x, y, z, w in zip(stream1, stream2, stream3, stream4)]
assert rec == stream
for i in range(len(flag_ct)):
    flag_ct[i] ^= mix(lfsr1(), lfsr2(), lfsr3(), lfsr4())

print(Bin(flag_ct).bytes)
# hitcon{larger_states_is_still_no_match_of_fast_correlation_attacks!}