Home ACSC 2024 crypto jenga
Post
Cancel

ACSC 2024 crypto jenga

Posted Apr 2, 2024
By
24 min read

Jenga

この問題はAESをベースにした問題で変更点は2点あります。

  • ShiftRowsがhoriという関数に、MixColumnsがvertという関数に対応しています。（内容の差異は後で）
  • 更に奇数ラウンドではhoriのみ使われ、逆に偶数ラウンドではvertが使われます。

AESの攻撃って

基本的にいろいろありますが、代表的なものとして、線形解読法(linear cryptanalysis)や差分解読法(different cryptanalysis)、SboxをAffineとしてlinearととらえるものがありますよね。

この問題では、AESで解析でよく用いられているsquare attackというものを用いて攻撃を行います。

注意としてこの問題では3×3の行列やアルゴリズムが異なるものを扱っている都合、AESとは一部攻撃方法が異なる部分があります。

各関数について

hori

AESで言うとShiftRowsにあたる部分で、数式では$HORI$として、逆関数を$HORI\_INV$としておきます。

horiは水平に3回行いますが簡略化のため1行のみ記載しています。

\(HORI(x) = (4*x_0\oplus 2*x_1\oplus x_2,x_0\oplus 4*x_1\oplus 2*x_2,2*x_0\oplus x_1\oplus4*x_2)\)​

さらに、\

\(\begin{eqnarray*}HORI(x\oplus y)&= (4*(x_0\oplus y_0)\oplus2*(x_1\oplus y_1)\oplus(x_2\oplus y_2),\\ &(x_0\oplus y_0)\oplus4*(x_1\oplus y_1)\oplus2*(x_2\oplus y_2),\\ &2*(x_0\oplus y_0)\oplus(x_1\oplus y_1)\oplus4*(x_2\oplus y_2) \\ &=((4*x_0\oplus2*x_1\oplus x_2)\oplus (4*y_0\oplus2*y_1\oplus y_2),\\ &\ \ \ \ (x_0\oplus4*x_1\oplus2*x_2) \oplus (y_0\oplus4*y_1\oplus2*y_2),\\ &\ \ \ \ (2*x_0\oplus x_1\oplus4*x_2)\oplus(2*y_0\oplus y_1\oplus4*y_2))\\ &=HORI(x)\oplus HORI(y)\end{eqnarray*}\)​

という分配則も成り立ちます。

vert

AESで言うとMixColumnsにあたる部分で、数式では$VERT$とし、逆関数を$VERT\_INV$としておきます。

今回の関数において、vertは垂直に3回行いますが計算内容はhoriと同じため省略します。また分配則も成立します。

xor

AESで言うとAddRoundKeyにあたる部分で、数式では$i$ roundのxorを$XOR_i$とし、逆関数を$XOR_i\_INV$としておきます。

sbox

AESで言うとSubBytesにあたる部分で、数式では$sbox$、逆関数を$sbox\_INV$とします。

Square attack

1byteだけ変えた入力を繰り返し行い出力の関係性を見ることで鍵を求めてみようというものです。

round 1

1roundだけ見ていきます。入力として、緑の部分だけ変えて、後は固定の値を与えるとします。

具体的には[bytes([i])+b"\x00"*8 for i in range(256)]みたいな感じです。

結果として、下の図のように変化させた部分が緑の部分へ影響を及ぼしていることがわかります。ただ、このうち6つ分の値は影響を受けず固定なため白にしています。

ここでわかっている部分や計算可能な部分を青で塗りつぶします。

image-20240403031500873

horiとsboxは逆関数が存在することで結果的には全ての状態の値がわかります。ということはxorの値もわかるので1roundは簡単に鍵が求まるということになります。

式で表せばこんな感じになります。

\[SBOX(XOR_1(HORI(input)))=output \Leftrightarrow XOR_1(HORI(input)) = SBOX\\_INV(output)\]

Round 2

次に2roundを見ていきます。入力は1roundと同様に緑の部分だけ変えて、後は固定の値を与えた結果、以下のようなものを得られます。

image-20240403031350981

同様にわかっている部分を青で埋めていきます。

image-20240403031435648

というわけで、1roundと比較してすべての状態がわかるわけではないとことになっています。

ただ、緑色の部分がわかると仮定し、その時青色で表現します。この場合はどうだろう。

image-20240403031525258

結果的に、1roundと同じよう計算していけば2Rのカギもわかりそうですね。

ただ問題は仮定の部分で、

  • 青の部分の値の固定をどうするのか…

こんな時は2つの入力を使って解決します。便宜上、入力を$input_1,input_2$とし、出力を$output_1,output_2$とします。

この時すべての状態で$input_1,input_2$のXORと、$output_1,output_2$のXORを取ります。

すると、2R後のxorが互いに打ち消すので1RのSBOX後まで計算が可能になり、青の部分が鍵の影響を受けずに計算可能になります。更に、1Rのhoriの後の状態を$input’$、1RのSBOX後の状態を$output’$​とします。

1つの場所に注目し式で表すと$SBOX(input_1’ \oplus KEY_1) \oplus SBOX(input_2’ \oplus KEY_1) = output_1’ \oplus output_2’$となりそれぞれのbytesごろに探索すれば鍵が求まります。

Round 3

影響が2回被る部分を赤で示しています。ここまでくるとちょっときついですね…

少し、工夫をすると1round分削減できます。

image-20240403031653438

具体的には今まで入力として与えていたものはinput=\x01+\x00*8みたいなものでした。これに$HORI\_INV(input)$としたものを与えると1Rのhoriにて1つの値にのみ影響を与えることができます。これにより1Rのsbox直後の値が1つのみにとどまるので2roundと同じ攻撃が起こなうことができます。

image-20240403031732436

Round 4

今回はRound 3で行ったテクニックは用いず考察していきます。Round 2では白の部分を1つの入力用いて固定していました。これを拡張する方向性で考えていきます。具体的には2Rのsbox直後まではinputの緑によって制御されるということ。それ以降は緑が重複するため制御は厳しそうです。なので、これらをうまく制御して計算途中はわからないが計算結果をわかればよいという方向性で2Rのsbox直後まで求めていきます。

image-20240403032050478

具体的には以下の式を考えます。 \(\oplus_{0\leq i \leq 255} SBOX(XOR_2(VERT(SBOX(XOR_1(HORI(input_i))))))\)

とはいっても長いので1つずつ見ていきます。

  1. 1Rのinputの時の緑(左上のみ)

    $\oplus_{0\leq i \leq 255} input_i = 0$になります

  2. 1Rのhori直後の緑(上段のみで左からインデックスを$0\leq j \leq 2$​とします) 分配則と1.より$\oplus_{0\leq i \leq 255} HORI(input) = 0$​​になります。

  3. 2.と1RのKEYを偶数回XORすることになるので$\oplus_{0\leq i \leq 255} XOR_1(input) = 0$になります。

  4. 3.において緑の場所に出現している値は256個あるため、$\oplus_{0\leq i \leq 255} SBOX(input) = 0$になります。

同様の議論を省略しますが、2Rの結果が0になるということと分配則を用いることで3Rのxor直後まで行うことができ、またそれまですべての入力に対してxorを取った値は0になる部分を青で示します。

逆に、output側から逆算できる部分を水色で示すと、以下になります。

image-20240403032024849

式として以下の形になります。

\[\oplus_{0\leq i \leq 255} SBOX\_INV(VERT\_INV(XOR_4\_INV(SBOX\_INV(output_i)))) = 0\]

一度、$SBOX\_INV(VERT\_INV(XOR_4\_INV(SBOX\_INV(output_i))))$に関して考えてみます。

$SBOX\_INV(output_i))$は確実に値がわかるので$SBOX\_INV(output_i))=output’$としておきます。

\[\begin{eqnarray*} SBOX\_INV(VERT\_INV(XOR_4\_INV(output'))) &=SBOX\_INV(VERT\_INV(output' \oplus KEY_4))\\ &= SBOX\_INV(VERT\_INV(output') \oplus VERT\_INV(KEY_4)) \end{eqnarray*}\]

$VERT\_INV(output’)$は計算可能だが、$VERT\_INV(KEY_4)$は計算できないためこれの計算結果を$KEY_4’$と置くと

$\oplus_{0\leq i \leq 255}　SBOX\_INV(VERT\_INV(output’) \oplus KEY_4’)$となり$SBOX\_INV$はそれぞれの値に対して演算を行うことを考慮すれば、$KEY_4’$のそれぞれの値をブルートフォースで求めればよいことになります。その求めた結果から$KEY_4$を復元することができますが、いくつかの候補があるためどの鍵があっているのか最終的にテストする必要があります。

Round 5

round5は以下のようになるがround2,4のテクニックを組み合わせることで解決できます。

image-20240403032336798

このようになり、解決可能へ…

image-20240403032345630

やったね

最終的なスクリプトは以下のようになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

from Jenga import *
from ptrlib import *
import re
from itertools import product
import functools

def hori_inv_ret(b):
    for i in range(0, 9, 3):
        x, y, z = b[i:i+3]
        b[i:i+3] = (
            gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
            gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
            gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
        )
    return b
def vert_inv_ret(b):
    for i in range(3):
        x, y, z = b[i], b[i + 3], b[i + 6]
        b[i], b[i + 3], b[i + 6] = (
            gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
            gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
            gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
        )
    return b

def hori(b):
    for i in range(0, 9, 3):
        x, y, z = b[i:i+3]
        b[i:i+3] = (
            gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
            gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
            gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
        )
    return b
    
def sbox_inv(b):
    for i in range(9):
        b[i] = SBOX_inv[b[i]]
    return b

def recover_key(last_key):
    last_key = last_key[::-1]
    for i in range(36):
        last_key.append(SBOX_inv[last_key[i]]^last_key[i+1])
    return last_key[::-1][:9]

# prepare
pts = [bytes(hori_inv_ret(list(bytes([i])+b"\x00"*8))).hex() for i in range(256)]
regex = re.compile("[0-9a-f]{18}")
last_key = [[] for i in range(9)]

io = remote("nc jenga.chal.2024.ctf.acsc.asia 39425")
# io = process(["python3","task.py"])

io.sendline("\n".join(pts))
print("SENDED")
ret = regex.findall(io.recvuntil(b"pt? ").decode())
TEST = ret[0] 
AIM  = ret[-1]

known_part = [hori_inv_ret(sbox_inv(vert_inv_ret(list(bytes.fromhex(ct))))) for ct in ret[:-1]]
print("RECVED")


last_key = []
for index in range(9):
    ret = []
    for i in range(256):
        if functools.reduce(lambda x, y: x ^ y, [SBOX_inv[ct[index]^i] for ct in known_part])==0:
            ret.append(i)
    last_key.append(ret)
# recover_last key
for cand in product(*last_key):
    test_key = recover_key(hori(list(cand)))
    if Jenga(test_key).encrypt(b"\x00"*9).hex() == TEST:
        a = Jenga(test_key).decrypt(bytes.fromhex(AIM)).hex()
        print(a)
        io.sendline(a)
        io.sh()
        print("found")
        break

# ACSC{b40a78c51c581b7478e910df9ede1f50c036eb60a1fcd9b4146c5f92c6fdd348}

最後に

この問題を作成したRBTree (@RBTree_)さんと、攻撃概要を書いていただいたrkm0959 (@rkm0959)さんに感謝します。大変参考になりました。

Appendix

Round 1

1

工事中

Round 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

from Jenga import *
from ptrlib import *
from itertools import product
from kanonlib.Util import bxor


def hori_inv_ret(b):
    for i in range(0, 9, 3):
        x, y, z = b[i:i+3]
        b[i:i+3] = (
            gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
            gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
            gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
        )
    return b
def vert_inv_ret(b):
    for i in range(3):
        x, y, z = b[i], b[i + 3], b[i + 6]
        b[i], b[i + 3], b[i + 6] = (
            gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
            gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
            gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
        )
    return b

def hori(b):
    for i in range(0, 9, 3):
        x, y, z = b[i:i+3]
        b[i:i+3] = (
            gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
            gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
            gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
        )
    return b

def vert(b):
    for i in range(3):
        x, y, z = b[i], b[i + 3], b[i + 6]
        b[i], b[i + 3], b[i + 6] = (
            gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
            gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
            gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
        )
    return b
    

def sbox_inv(b):
    for i in range(9):
        b[i] = SBOX_inv[b[i]]
    return b


def recover_key(last_key):
    last_key = last_key[::-1]
    for i in range(9):
        last_key.append(SBOX_inv[last_key[i]]^last_key[i+1])
    return last_key[::-1]

key = os.urandom(9)
jenga = Jenga(key)

pt = os.urandom(9)
pt2 = os.urandom(9)

ct1_base = jenga.encrypt_test(pt,2)
ct1 = sbox_inv(hori_inv_ret(list(ct1_base)))
ct2 = jenga.encrypt_test(pt2,2)
ct2 = sbox_inv(hori_inv_ret(list(ct2)))

pt1 = hori(list(pt))
pt2 = hori(list(pt2))
XCT = vert_inv_ret(list(bxor(ct2,ct1)))
cands = []
for i in range(9):
    cand = []
    for k in range(256):
        if SBOX[pt1[i]^k]^SBOX[pt2[i]^k] == XCT[i]:
            cand.append(k)
    cands.append(cand)

for cand_key in product(*cands):
    # exit()
    if Jenga(cand_key).encrypt_test(pt,2) == ct1_base:
        print(cand_key)
    
    if list(cand_key) == list(key):
        print("KK")
        exit()

Round 3

1

工事中

Round 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

from Jenga import *
from ptrlib import *
import re
from itertools import product
import functools

def hori_inv_ret(b):
    for i in range(0, 9, 3):
        x, y, z = b[i:i+3]
        b[i:i+3] = (
            gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
            gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
            gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
        )
    return b
def vert_inv_ret(b):
    for i in range(3):
        x, y, z = b[i], b[i + 3], b[i + 6]
        b[i], b[i + 3], b[i + 6] = (
            gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
            gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
            gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
        )
    return b

def hori(b):
    for i in range(0, 9, 3):
        x, y, z = b[i:i+3]
        b[i:i+3] = (
            gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
            gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
            gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
        )
    return b

def vert(b):
    for i in range(3):
        x, y, z = b[i], b[i + 3], b[i + 6]
        b[i], b[i + 3], b[i + 6] = (
            gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
            gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
            gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
        )
    return b

def sbox_inv(b):
    for i in range(9):
        b[i] = SBOX_inv[b[i]]
    return b

def recover_key(last_key):
    last_key = last_key[::-1]
    for i in range(27):
        last_key.append(SBOX_inv[last_key[i]]^last_key[i+1])
    return last_key[::-1][:9]

ROUND = 4

KEY = os.urandom(9)
jenga = Jenga(KEY)
AIM_pt = os.urandom(9)
AIM_ct = jenga.encrypt_test(AIM_pt,ROUND)


# prepare
pts = [bytes([i])+b"\x00"*8 for i in range(256)]

cts = [jenga.encrypt_test(pt,ROUND) for pt in pts]
TEST = cts[0] 
known_part = [vert_inv_ret(sbox_inv(hori_inv_ret(list(ct)))) for ct in cts]

last_key = []
for index in range(9):
    ret = []
    for i in range(256):
        if functools.reduce(lambda x, y: x ^ y, [SBOX_inv[ct[index]^i] for ct in known_part])==0:
            ret.append(i)
    last_key.append(ret)
print(last_key)
# recover_last key
for cand in product(*last_key):
    test_key = recover_key(vert(list(cand)))
    if Jenga(test_key).encrypt_test(b"\x00"*9,ROUND) == TEST:
        print(list(test_key) == list(KEY))
        print("found")
        break

Round 5

jenga_test.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

SBOX = [
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
]
SBOX_inv = [
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
]

def gf_mul(a, b):
    v = 0
    for i in range(8):
        v <<= 1
        if v & 0x100:
            v ^= 0x11b

        if (b >> (7 - i)) & 1:
            v ^= a
    return v

ROUND = 5

class Jenga:
    
    def __init__(self, key: bytes):
        assert len(key) == 9
        subkeys = list(key)

        for i in range( 9 * (ROUND - 1) ):
            subkeys.append(SBOX[subkeys[-9] ^ subkeys[-1]])
        
        self.subkeys = [ subkeys[i:i+9] for i in range(0, 9 * ROUND, 9) ]
    
    @staticmethod
    def hori(b):
        for i in range(0, 9, 3):
            x, y, z = b[i:i+3]
            b[i:i+3] = (
                gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
                gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
                gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
            )
    
    @staticmethod
    def vert(b):
        for i in range(3):
            x, y, z = b[i], b[i + 3], b[i + 6]
            b[i], b[i + 3], b[i + 6] = (
                gf_mul(x, 4) ^ gf_mul(y, 2) ^ z,
                gf_mul(y, 4) ^ gf_mul(z, 2) ^ x,
                gf_mul(z, 4) ^ gf_mul(x, 2) ^ y,
            )

    @staticmethod
    def hori_inv(b):
        for i in range(0, 9, 3):
            x, y, z = b[i:i+3]
            b[i:i+3] = (
                gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
                gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
                gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
            )
    
    @staticmethod
    def vert_inv(b):
        for i in range(3):
            x, y, z = b[i], b[i + 3], b[i + 6]
            b[i], b[i + 3], b[i + 6] = (
                gf_mul(x, 0x9e) ^ gf_mul(y, 0x4f),
                gf_mul(y, 0x9e) ^ gf_mul(z, 0x4f),
                gf_mul(z, 0x9e) ^ gf_mul(x, 0x4f),
            )
    
    def xor(self, b, rnd):
        for i in range(9):
            b[i] ^= self.subkeys[rnd][i]
    
    @staticmethod
    def sbox(b):
        for i in range(9):
            b[i] = SBOX[b[i]]
    
    @staticmethod
    def sbox_inv(b):
        for i in range(9):
            b[i] = SBOX_inv[b[i]]

    def encrypt(self, block: bytes):
        b = list(block)
        for rnd in range(ROUND + 1):
            self.vert(b) if rnd % 2 else self.hori(b)
            if rnd == ROUND:
                break
            self.xor(b, rnd)
            self.sbox(b)
            break
        return bytes(b)
    
    def encrypt_test(self, block: bytes, ROUND: int):
        b = list(block)
        for rnd in range(ROUND + 1):
            self.vert(b) if rnd % 2 else self.hori(b)
            if rnd == ROUND:
                break
            self.xor(b, rnd)
            self.sbox(b)
        return bytes(b)

    def decrypt(self, block: bytes):
        b = list(block)
        for rnd in reversed(range(ROUND + 1)):
            self.vert_inv(b) if rnd % 2 else self.hori_inv(b)
            if rnd == 0:
                break
            self.sbox_inv(b)
            self.xor(b, rnd - 1)
        return bytes(b)

if __name__ == "__main__":
    import os
    for _ in range(10):
        key = os.urandom(9)
        cipher = Jenga(key)

        for _ in range(100):
            pt = os.urandom(9)
            assert cipher.decrypt(cipher.encrypt(pt)) == pt
            assert cipher.encrypt(cipher.decrypt(pt)) == pt
writeup
writeup
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents