4 bit key space is brute forceable so how about 48 bit key space?
flag is hackim19{decrypted flag}
16 bit plaintext: b'0467a52afa8f15cfb8f0ea40365a6692'
flag: b'04b34e5af4a1f5260f6043b8b9abb4f8'
from hashlib import md5 from binascii import hexlify, unhexlify from secret import key, flag BLOCK_LENGTH = 16 KEY_LENGTH = 3 ROUND_COUNT = 16 sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54, 217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107, 91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221, 63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81, 201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15, 151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119, 123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99, 82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129, 131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48, 97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125, 106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200, 70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153, 174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65, 176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83, 223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246, 169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117, 100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231, 0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222, 20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215, 50, 148, 159, 93, 80, 45, 17, 205, 95] p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14] def xor(a, b): return bytearray(map(lambda s: s[0] ^ s[1], zip(a, b))) def fun(key, pt): assert len(pt) == BLOCK_LENGTH assert len(key) == KEY_LENGTH key = bytearray(unhexlify(md5(key).hexdigest())) ct = bytearray(pt) for _ in range(ROUND_COUNT): ct = xor(ct, key) for i in range(BLOCK_LENGTH): ct[i] = sbox[ct[i]] nct = bytearray(BLOCK_LENGTH) for i in range(BLOCK_LENGTH): nct[i] = ct[p[i]] ct = nct return hexlify(ct) def toofun(key, pt): assert len(key) == 2 * KEY_LENGTH key1 = key[:KEY_LENGTH] key2 = key[KEY_LENGTH:] ct1 = unhexlify(fun(key1, pt)) ct2 = fun(key2, ct1) return ct2 print("16 bit plaintext: %s" % toofun(key, b"16 bit plaintext")) print("flag: %s" % toofun(key, flag))
ブロック暗号の問題。sboxという名前はDESなどでも使われる非線形の変換を行う機構だった気がする。というかこれ構造だけ見たら2-DESなのでは。
"16 bit plaintext"という文字とフラグをそれぞれ同じ鍵で暗号化したが手に入っている。
暗号化処理をEとして、toofun は k1, k2 = K, E(k2, E(k1, P)) をやっているだけ
本体のfunは↓のような処理が16回繰り返されている
……ということはC, P がわかっている状態ならKが復元できるのでは？？ と思ったけど暗号化処理が2ROUNDになってるのか。それぞれで鍵が異なっているので求められませんね……。
いやちょっとまってくださいよ、ある特定のバイトに対してXORされるKEYは畳み込んで K = K1K2K3^...^K16^...^K32 とできるんじゃないですか？ shufは一定の変換しかしないので。
これはだめですね。途中にS-BOXが挟まっていて非線形なのでKを線形に結合しても嘘になるだけか。
ところでKEYが6バイト、暗号化するときは3byteしかないんですがこれはどうですか？ 6バイトの総当り、248はできないにしても224ならできそうだよね。
----
調べてみたらmeet-in-the-middle attack、中間一致攻撃というのが使えるらしい。これは C = E(k2, E(k1, P)) となっていて、C, E 既知のときに使える攻撃で（おいおい今回のケースぴったりやんけ）本来なら len(k1||k2) について全探索しないといけないところを len(k1)について全探索するだけで良くなる。
理屈は簡単で、 kを全探索して D(k, C) と E(k, P) を全て求めておく。今求めたのは中間状態で、もしD(k_j, C) と E(k_i, P) が一致するようなk_i, k_j があれば、おそらくそれが k1, k2だろうというのが原理
----
pythonでsolverを書いていたけど遅くて使い物にならなかったのでやめてgoで書き直した。1minくらいで終わる
package main
import (
"crypto/md5"
"encoding/hex"
"fmt"
)
const (
BLOCK_LENGTH = 16
ROUND_COUNT = 16
)
var (
sbox = []byte{210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54,
217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107,
91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221,
63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81,
201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15,
151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119,
123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99,
82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129,
131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48,
97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125,
106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200,
70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153,
174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65,
176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83,
223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246,
169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117,
100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231,
0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222,
20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215,
50, 148, 159, 93, 80, 45, 17, 205, 95}
p = []int{3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14}
r_sbox []byte
r_p []int
)
func fun(key, plain []byte) []byte {
sum := md5.Sum(key)
cipher := make([]byte, BLOCK_LENGTH)
next := make([]byte, BLOCK_LENGTH)
copy(cipher, plain)
for j := 0; j < ROUND_COUNT; j++ {
for i := 0; i < BLOCK_LENGTH; i++ {
cipher[i] = sbox[cipher[i] ^ sum[i]]
}
for i := 0; i < BLOCK_LENGTH; i++ {
next[i] = cipher[p[i]]
}
copy(cipher, next)
}
return cipher
}
func defun(key, cipher []byte) []byte {
sum := md5.Sum(key)
plain := make([]byte, BLOCK_LENGTH)
prev := make([]byte, BLOCK_LENGTH)
copy(plain, cipher)
for j := 0; j < ROUND_COUNT; j++ {
for i := 0; i < BLOCK_LENGTH; i++ {
prev[i] = plain[r_p[i]]
}
copy(plain, prev)
for i := 0; i < BLOCK_LENGTH; i++ {
plain[i] = r_sbox[plain[i]] ^ sum[i]
}
}
return plain
}
func main() {
r_sbox = make([]byte, len(sbox))
for i, v := range sbox {
r_sbox[int(v)] = byte(i)
}
r_p = make([]int, len(p))
for i, v := range p {
r_p[v] = i
}
plain := []byte("16 bit plaintext")
ciphered, _ := hex.DecodeString("0467a52afa8f15cfb8f0ea40365a6692")
c_flag, _ := hex.DecodeString("04b34e5af4a1f5260f6043b8b9abb4f8")
table := make(map[string]([]byte), 256*256*256)
for k1 := 0; k1 < 256; k1++ {
for k2 := 0; k2 < 256; k2++ {
for k3 := 0; k3 < 256; k3++ {
k := []byte{byte(k1), byte(k2), byte(k3)}
r := string(fun(k, plain))
table[r] = k
}
}
fmt.Printf("%d/256\n", k1+1)
}
for k1 := 0; k1 < 256; k1++ {
for k2 := 0; k2 < 256; k2++ {
for k3 := 0; k3 < 256; k3++ {
k2 := []byte{byte(k1), byte(k2), byte(k3)}
r := string(defun(k2, ciphered))
k1, ok := table[r]
if ok {
m_flag := string(defun(k1, defun(k2, c_flag)))
fmt.Printf("keys: (%v, %v), flag: %v", k1, k2, m_flag)
}
}
}
fmt.Printf("%d/256\n", k1+1)
}
}
keys: ([162 119 181], [193 188 139]), flag: 1337_1n_m1ddl38f194
良問でした
