Mixed signal

files

main.py

​x
from Crypto.Util.number import *

def mix(data):
    b = len(data)*8
    m = bytes_to_long(data)
    c = 0
    for _ in range(b//2):
        if (m >> _) & 1:
            c ^= m >> (b//2) << _
    return c

flag = open("flag.txt", "rb").read()
print(mix(flag))

output.txt

xxxxxxxxxx
6942898839970185178260073539872686823033540616179568772534193638792863984577319801408327713407779249828819087800803420064518242859606213564691040797518

Phân tích

Bài này là một trong những bài mà mình thấy nó mô tả 1 tính chất khá là "đặc sản" của Crypto, đó là: "Đi vào thì dễ mà đi ra thì khó :v". Tuy chỉ dùng 1 vòng for và 1 lần if , bài này đã đánh bại kha khá không ít các bạn thí sinh, duy nhất chỉ có đúng 1 bạn giải được 😗

Để hiểu về bài này trước hết mình phải đi qua một khái niệm tưởng như không liên quan mà lại rất cần thiết để giải bài này: Đó chính là hiểu về đa thức trong GF(2).

đa thức trong GF(2)

Bình thường ta hay làm quen với đa thức sẽ có dạng là

với $a_0,a_1,...$$a_0, a_1, ...$ là các hệ số trong $\mathbb{R}$$\R$ hay trong $\mathbb{C}$$\C$.

Tuy nhiên, có 1 loại đa thức hơi đặc biệt một chút, đó là đa thức với các hệ số chỉ có 0 và 1, ví dụ như là $1x^3+0x^2+1x^1+0x^0$$1x^3 + 0x^2 + 1x^1 + 0x^0$ chẳng hạn. Cách cộng và nhân của chúng nó cũng khá là dị với ảo :33

Khi mình cộng chúng, thì việc cộng xảy ra như bình thường, giống như chúng ta cộng 2 đa thức với các hệ số là số nguyên vậy,

tuy nhiên thì sau khi cộng mình sẽ mod 2 tất cả các hệ số đó và rút ra được kết quả 😗

Tương tự với phép nhân cũng vậy:

Điều thú vị là, nếu chúng ta viết đa thức kiểu trên dưới dạng 1 số nhị phân, bằng cách viết các hệ số từ số mũ cao hơn đến thấp hơn, theo thứ tự từ trái sang phải, ví dụ như thế này:

• $x^3+x^2+1$$x^3 + x^2 + 1$ thì thành $1101$$1101$.
• $x^2+x$$x^2 + x$ thì thành $101$$101$.

Thì việc chúng ta XOR và left shift các số ở vế phải có mối liên hệ mật thiết đến việc nhân và cộng đa thức trong GF(2) đó (ngạc nhiên chưaaa)

Cộng 2 đa thức và XOR

Có 1 điều khá là trùng hợp, đó là khi chúng ta XOR 2 số bất kì, thì khi viết quá trình này ở dạng nhị phân, nó giống hệt như là khi mình cộng 2 đa thức trong GF(2) vậy :v

Lí do điều này xảy ra là bởi vì XOR nó cho ra output y hệt như là khi chúng ta dùng phép cộng mod 2 vậy.

(nguồn: https://www.youtube.com/watch?v=tNnaEyWxsEI)

Nhân với $x^n$$x^n$ = shift LEFT n bits

Có lẽ cái tên đã nói lên tất cả nhỉ. Khi mình nhân 1 đa thức bất kì với $x^n$$x^n$ với $n$$n$ là số nguyên dương bất kì, thì kết quả giống như khi mình shift 1 số sang trái n bits vậy ~.~

XOR + SHIFT LEFT = f(x)*g(x) trong gf(2)

Vì $g(x)$$g(x)$ là một đa thức trong GF(2), nên nó không chứa các hệ số nào khác ngoài 0 và 1, vì vậy có thể viết được dưới dạng $x^a+x^b+\mathbf{\cdot }\mathbf{\cdot }\mathbf{\cdot }$$x^a + x^b + \vdot\vdot\vdot$.

Điều này dẫn đến việc $f(x)g(x)$$f(x)g(x)$ có thể được viết thành như sau:

Trong đó phép nhân với $x^n$$x^n$ có thể được biểu diễn thành việc mình shift 1 số sang trái n bits, còn phép cộng thì được biểu diễn bằng việc mình XOR 2 số.

code tính f(x)*g(x)

Nếu viết $g(x)$$g(x)$ dưới dạng số nhị phân, thì $a,b,\mathbf{\cdot }\mathbf{\cdot }\mathbf{\cdot }$$a, b, \vdot\vdot\vdot$ sẽ tương đương với các vị trí bit trong $g$$g$ = 1. Như vậy, chúng ta có thể suy ra 1 thuật toán mà sẽ tính XOR của tất cả các giá trị f << i khi mà bit thứ i của g = 1. Và từ đó chúng ta có 1 đoạn code như sau:

xxxxxxxxxx
from Crypto.Util.number import *

def mul_in_gf2(f, g):
    b  = len(bin(g)[2:])  # b = số bit của g
    fg = 0
    for i in range(b):    # Xét từ x^0 -> x^(b-1) của g(x)
        if (g >> i) & 1:  # nếu bit thứ i của g = 1 <=> hệ số của x^i trong f(x) = 1 
            fg ^= f << i  # fg += f(x) * x^i
    return fg

Nếu ta thay g bằng m và f bằng m >> (b/2) và xét i chạy từ 0 tới b/2, với m là giá trị của flag và b là số bit của m, bùmmm, chúng ta sẽ có challenge này :33

xxxxxxxxxx
from Crypto.Util.number import *

def mix(data):
    b = len(data)*8
    m = bytes_to_long(data)
    c = 0
    for _ in range(b//2):
        if (m >> _) & 1:
            c ^= m >> (b//2) << _
    return c

flag = open("flag.txt", "rb").read()
print(mix(flag))

Nói cách khác, việc của code challenge này làm là bẻ đôi flag ra làm 2 nửa, coi 2 nửa là 2 đa thức $f(x)$$f(x)$ và $g(x)$$g(x)$, và kết quả của hàm mix thực ra là tính $f(x)g(x)$$f(x)g(x)$.

Cách giải

Như vậy, để "unmix" cái đống data này chúng ta cần tìm tất cả các divisors của $f(x)g(x)$$f(x)g(x)$ và hi vọng f(x) bé nhỏ của chúng ta cũng nằm trong đó. Bằng cách xét những divisors nào của output có các bit của BKSEC{ ở trong đó, chúng ta có thể loại kha khá divisors không liên quan và tìm ra được 1/2 của flag và suy ra được nửa còn lại bằng cách chia $f(x)g(x)$$f(x)g(x)$ với $f(x)$$f(x)$.

May thay sage có hàm divisor và có cách để tạo đa thức trong GF(2) dễ ơi là dễ (hoặc các bạn có thể như mình và viết 400 dòng code C++ để giải bài này =v), chúng ta có thể giải bài này trong 1 nốt nhạc 😗

xxxxxxxxxx
from Crypto.Util.number import *

# Get bit array out of output
c = Integer(open("output.txt", "r").read()).bits()
P.<x> = PolynomialRing(GF(2))

# Convert bit array to polynomial in GF(2)
f = 0
for i, bit in enumerate(c):
    f += x**i * bit

# Loop through divisors d of f
for d in divisors(f):
    # Convert polynomial to bitstring
    lBin = ''.join(str(coefficient) for coefficient in d)[::-1]
    
    # If the bits of BKSEC{ is in the bitstring
    if bin(bytes_to_long(b'BKSEC'))[2:] in lBin:
        # Calculate f/d and convert it to bitstring
        rBin = ''.join(str(c) for c in (f//d))[::-1]

        # Padding because leading 0s might be missing when converting from bitstring to polynomial :)
        if len(rBin) % 4 != 0:
            rBin = rBin.zfill((len(rBin) // 4 + 1) * 4)

        # Print result
        print(long_to_bytes(int(lBin + rBin, 2)))

Flag

xxxxxxxxxx
BKSEC{f@CT0R1nG-P0lyN0m1aL-15-th3-K3y-t0-UnMiX-tH15-wH0L3-m355}