Aero CTF 2021 | phoenix - crypto-writeup-public

#!/usr/bin/env sage

p = 2
F = GF(p)
P.<x> = PolynomialRing(F)


class Cipher:
    def __init__(self, size, params):
        self.size = size
        self.params = params

    def sequence(self, key):
        while True:
            key = key * self.params[0]
            yield key + self.params[1]

    def encrypt(self, key, data, strength):
        for value, pbit in zip(self.sequence(key), data):
            xbit = sum(value[i] for i in range(0, strength, 2))
            ybit = mul(value[i] for i in range(1, strength, 2))
            
            yield int(pbit) ^^ int(xbit) ^^ int(ybit)


def main():
    size = 256
    length = 1024
    strength = 10

    q = P.irreducible_element(size, 'minimal_weight')
    R.<x> = P.quo(q)

    key, a, b = [R.random_element() for _ in range(3)]

    with open('flag.txt', 'rb') as file:
        flag = file.read().strip()

    message = int.from_bytes(flag, 'big')
    assert message.bit_length() < size
    plaintext = list(map(int, bin(message)[2:]))
    padding = [0] * (length - len(plaintext))

    cipher = Cipher(size, [a, b])
    ciphertext = list(cipher.encrypt(key, padding + plaintext, strength))
    result = int(''.join(map(str, ciphertext)), 2)

    print(a)
    print(b)
    print(result)


if __name__ == '__main__':
    main()

$P: GF(2)\lbrack x \rbrack$

$q:$ $P$ 上の既約多項式

$R: P/q$ という剰余環 ... つまり $R$ の元 $r$ は $deg(r) < deg(q)$ となるはず（？）

手元で実験した

sage: p = 2 
....: F = GF(p) 
....: P.<x> = PolynomialRing(F) 
....: size = 10 
....: q = P.irreducible_element(size, 'minimal_weight') 
....: R.<x> = P.quo(q) 
....:                                                                                                                                                                                        
sage: q                                                                                                                                                                                      
x^10 + x^3 + 1
sage: R                                                                                                                                                                                      
Univariate Quotient Polynomial Ring in x over Finite Field of size 2 with modulus x^10 + x^3 + 1
sage: R.random_element()                                                                                                                                                                     
x^9 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + 1
sage: R.random_element()                                                                                                                                                                     
x^9 + x^6 + x^5 + x + 1

$key, a, b \in R$

平文は256bitの数値を01に直した形の配列 $\lbrack m_0, m_1, \dots, m_{255} \rbrack$ で与えられて、暗号化は次のように行われる

$s_i = as_{i-1} = a^{i+1}key$

$k_i = s_i + b$

(なんか $s_0$ の扱い難しい）

として、暗号化は↓として行われる（ $k_i$ は255次の多項式で、そのうち下から10次までを使う、ということ）

$c_i = m_i \oplus \left(\sum_{j=0}^{5} {k_i}_{2j} \right) \oplus \left( \prod_{j=0}^{5} {k_i}_{2j + 1} \right) = m_i \oplus x_i \oplus y_i$

そして、 $a, b$ が与えられるので未知数は $key$

考察

暗号化のうち、 product をとっているが、ここはすべてのbitが1でない限り0になる（5bitあるから、 $31/32$ は0になる）
平文の最初が少しわかっているとき、 $key$ が復元できるという問題？
- ただ、使われているのは $k_i$ の10次までなので、 $key$ 全体を復元するのはできなさそう
- $a$ 倍されて $b$ 足されることを考えてうまく一部だけでも復元できるのだろうか
padding が平文の先頭につけられているので、 $m_0, ...$ しばらくは平文は0であることがわかっている
$c_i, m_i$ がそれぞれわかっている時、 $k_i$ の取りうる値はどのようになるか
- $c_i = m_i$ のとき
- $c_i \ne m_i$ のとき
$k_i$ の10次までの値がわかっているとして、 $k_{i+1}$ の値はどのくらいわかるか
- $a$ 倍したタイミングでかなりダイナミックにbitの移動が起こってそう
$q$ がminimal_weight なので $a,b$ の値がどうこう、という話になる？

writeup

読みぬけ

$result$ が1023bitの値で、平文は $256$ bit以下であることがわかっているので、padded な平文の先頭 $1023 - 256 = 767$ bitは0
$y_i$ は $31/32$ で0なので（ここまでは考えていた）先頭760bit程度では $c_i = x_i = \sum_{j=0}^{5} k_{2j}$ という仮定を置けそう

Solution

未知数 $key$ は $256$ bitの値なので、256個の式があれば全bitを復元できる（！）
- そして今 $760$ bit程度はわかっているので、 $y_i$ がすべて0になるように祈りつつ適当に256個の式をもってくればいいはず
結局 $a, b$ の影響はどうやって消せばいいんだろう
- $key$ を256個の未知係数をもつ多項式とおいて $s_i = a^{i}key + b$ と書くだけでよいのでは
- - 結局これでも $s_i$ の0,2,4,6,8 bit目のsumをどう扱うかという話になる
これは ISD Attack というらしい（どこを指してそう言ってるのかわかってないが……）

実装途中まで（解けてない）

class Cipher:
    def __init__(self, size, params):
        self.size = size
        self.params = params

    def sequence(self, key):
        while True:
            key = key * self.params[0]
            yield key + self.params[1]

    def encrypt(self, key, data, strength):
        for value, pbit in zip(self.sequence(key), data):
            xbit = sum(value[i] for i in range(0, strength, 2))
            ybit = mul(value[i] for i in range(1, strength, 2))
            
            yield int(pbit) ^^ int(xbit) ^^ int(ybit)


p = 2
F = GF(p)
P.<x> = PolynomialRing(F)
size = 32
length = 128
strength = 10

q = P.irreducible_element(size, 'minimal_weight')
R.<x> = P.quo(q)
key, a, b = [R.random_element() for _ in range(3)]

message = randint(2, 1<<size)
plaintext = list(map(int, bin(message)[2:]))
padding = [0] * (length - len(plaintext))

cipher = Cipher(size, [a, b])
ciphertext = list(cipher.encrypt(key, padding + plaintext, strength))
result = int(''.join(map(str, ciphertext)), 2)

key_, a_, b_ = key, a, b

def solve(result, a, b, n):
    p = 2
    F = GF(p)
    P.<x> = PolynomialRing(F)

    PR = PolynomialRing(F, ["k{}".format(i) for i in range(size)])
    q = P.irreducible_element(size, 'minimal_weight')
    QR.<x> = PR[x].quo(q)
    key = sum([x^i*k for i, k in enumerate(PR.gens())])

    resultbits = Integer(result).bits()[:length-size]
    result = [(i,bit) for i, bit in enumerate(resultbits)]

    keys = []
    for i in range(length - size):
        k = key*a^(i+1) + b
        keys.append(sum([k[j] for j in range(0, 10, 2) ]))

    keypolys = []
    for _ in range(n):
        import random
        random.shuffle(result)

        polys = []
        for r in result[:size]:
            i, x = r
            polys.append( keys[i] - x )


        I = Ideal(polys)
        G = I.groebner_basis()
        keybits = [k.constant_coefficient() for k in G][::-1]
        keypoly = QR(keybits)
        keypolys.append(keypoly)
    return keypolys
keypolys = solve(result, a, b, 10)
print(key_)
for p in keypolys:
    print(p)