この記事は、2020年6月13日に旧ブログに投稿したものです。
akictfのunreadable messageのwriteupです。
9人目の解答者である@deienuが私です。 2015年12月頃に解きました。
問題
https://github.com/akiym/akictf2013/blob/master/problem.md#42-unreadable-message
答え
you discovered my message! your flag is: brute_it_if_you_could_not_read
解説
gen_message.plのコードより、以下の三点が分かります。
- 実行には、PerlとImagerとM+ FONTSが必要である
gen_message.plは、変数$message（厳密には変数$messages）の文字列をモザイク化してunreadable_message.pngを作成する- 変数
$messageは書き換えられているため、推測する必要がある
ここで、変数$messageがa、aa、aab、aabaの場合の出力画像を見てみます。
aとaaより、aをモザイク化すると、0xffffff、0xaaaaaa、0xbfbfbfの一列になることが予想できます。
しかし、aabaより、bの後に来るaは別の色になっていることがわかります。最初のニ文字のaaは変化していません。
このことから、最初は二文字、その後は一文字ずつ、問題のモザイクピクセルと一致する組み合わせを総当りで試す方法を用いました。
流れとしては以下のとおりです。
- ASCIIの印字可能文字（95文字）で構成される2文字の全組み合わせ（95^2=9025通り）のモザイク画像を生成する
- 問題と一致するモザイクピクセルの画像を探す
- 導いた文字に加えて、ASCIIの印字可能文字（95文字）で構成される全組み合わせのモザイク画像を生成する
- 問題と一致するモザイクピクセルの画像を探す
- 手順3へ
まず、引数から任意のモザイク画像が生成できるようにgen_message.plを変更します。
後の作業で、文字列とモザイク画像の対応処理が必要なため、ファイル名を変数$messageにします。
*nix系では/がファイル名に使えないので、_slash_に置換しています。
1--- gen_message.pl.bak 2014-10-27 18:57:32.000000000 +0900
2+++ gen_message.pl 2020-05-27 00:47:12.886434067 +0900
3@@ -1,8 +1,10 @@
4 use strict;
5 use warnings;
6 use Imager;
7+use MIME::Base64;
8
9-my $message = 'CENSORED';
10+my $message = $ARGV[0];
11+(my $encoded_message = $message) =~ s/\//_slash_/g;
12
13 my @messages;
14 push @messages, $_ =~ /(.{71}|.+)/g for split /\n/, $message;
15@@ -34,10 +36,7 @@
16 );
17 $y += 20;
18 }
19-$img->write(
20- file => 'readable_message.png',
21-) or die $img->errstr;
22 $img->filter(type => 'mosaic', size => 6);
23 $img->write(
24- file => 'unreadable_message.png',
25+ file => "$encoded_message.png",
26 ) or die $img->errstr;
次に、ASCIIの印字可能文字（95文字）で構成される全組み合わせのモザイク画像を生成します。
1## gen.shとして保存
2for i in {32..126}; do
3 str=$(printf "\x$(printf "%x" $i)")
4 perl gen_message.pl "$1$str"
5done
生成された画像の中に、問題のモザイクピクセルと一致するものが含まれているはずです。
それを探すスクリプトを手っ取り早く作るために、あらかじめunreadable_message.pngを含むすべての画像からモザイクピクセルを抽出します。
ImageMagickが必要です。
1## prepare.shとして保存
2## 下部2pxのボーダーを消す
3mogrify -gravity south -chop x2 -- "$1"
4## 左右の余白を消す（参考：https://www.imagemagick.org/Usage/crop/#trim_oneside）
5mogrify -gravity East -background white -splice 5x0 -background black -splice 5x0 -- "$1"
6mogrify -trim +repage -- "$1"
7mogrify -gravity East -chop 5x0 -- "$1"
8mogrify -gravity West -background white -splice 5x0 -background black -splice 5x0 -- "$1"
9mogrify -trim +repage -- "$1"
10mogrify -gravity West -chop 5x0 -- "$1"
最初はニ文字を特定する必要があるため、二文字の組み合わせ（95^2=9025）ごとにgen.shを実行します。
1for i in {32..126}; do
2 str=$(printf "\x$(printf "%x" $i)")
3 bash gen.sh "$str"
4done
5## *.pngには問題の`unreadable_message.png`も含む
6bash prepare.sh '*.png'
そして、一致する画像ファイルを探します。 pillowライブラリが必要です。
1## check.pyとして保存
2from PIL import Image
3import glob
4import sys
5
6def getPixel(filename):
7 src = Image.open(filename)
8 data = src.getdata()
9 img_x, img_y = data.size
10 array = []
11 for x in range(0, img_x, 6):
12 for y in range(0, 18, 6):
13 try:
14 array.append(data.getpixel((x, y)))
15 except:
16 print("ERR: {}".format(filename), file=sys.stderr)
17
18 return array
19
20orig = getPixel('unreadable_message.png')
21for file in glob.glob("*.png"):
22 data = getPixel(file)
23 for pixel in range(0, len(data)):
24 if (orig[pixel] != data[pixel]):
25 break
26 if (pixel == len(data)-1):
27 print(file)
これを実行すると、yo.pngが出力されるので、最初の2文字はyoであることが分かりました。
1$ python check.py
2unreadable_message.png
3yo.png
4y.png
次に、3文字目を特定します。
1# gen.sh
2for i in {32..126}; do
3 str=$(printf "\x$(printf "%x" $i)")
4 perl gen_message.pl $1$str
5done
1$ bash ./gen.sh yo
2$ mv unreadable_message.png unreadable_message.png.bak
3$ bash ./prepare.sh
4$ mv unreadable_message.png.bak unreadable_message.png
5$ python check.py
6unreadable_message.png
7yo.png
8you.png
候補が複数出る場合は、意味が最も通る方を選びます。 これを繰り返すとフラグが得られます。
当時のコード
下記のコードは当時（2015年12月）のもの1です。count変数使ってなくね…？
当時はファイル名をbase64に変換していなかったので、*nix上ではパス区切りとして認識される/が含まれる文字は変換できませんでした。
また、NUMはlen(data)ですが、当時は手動で変更していました。
1import numpy as np
2import sys
3import scipy.io as sio
4
5sbox = (
6 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
7 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
8 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
9 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
10 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
11 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
12 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
13 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
14 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
15 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
16 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
17 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
18 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
19 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
20 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
21 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16)
22
23# shiftRowedされる前のインデックス番号を返す
24# shiftIndex: shiftRowされた後のインデックス番号
25def invShiftRowsIndex(shiftIndex):
26 '''
27 chiper = np.zeros((4, 4), dtype=np.int)
28 for j in range(4):
29 for k in range(4):
30 chiper[j][k] = 4 * j + k
31 chiper = np.transpose(chiper)
32 for i in range(4):
33 chiper[i] = np.roll(chiper[i], i)
34 invshiftrowed = chiper.flatten()
35 '''
36 # 結果は一定なので高速化のためにハードコード
37 invshiftrowed = [0 , 13, 10, 7 ,
38 4 , 1 , 14, 11,
39 8 , 5 , 2 , 15,
40 12, 9 , 6 , 3 ]
41 return invshiftrowed[shiftIndex]
42
43input = sio.loadmat("traces_fixed.mat")
44MAX_CIPHER = len(input['samples'])
45MAX_SAMPLE = len(input['samples'][0])
46
47powerdata = input['samples']
48cipher = [input['inout'][x][16:32] for x in range(MAX_CIPHER)]
49
50print(len(powerdata), len(cipher))
51assert len(powerdata) == len(cipher)
52
53estimatedkey = [None]*16
54
55for bnum in range(16):
56 soukan = [0 for i in range(256)]
57
58 # invShiftRowsの結果をAddRoundKeyで使うためここで宣言しておく
59 invIndex = invShiftRowsIndex(bnum)
60
61 # 鍵候補の決定
62 for kguess in range(256):
63 sys.stdout.write("\r{}: {}".format(invIndex, kguess))
64
65 humdis = np.zeros(MAX_CIPHER)
66 for times in range(MAX_CIPHER):
67 curCipher = cipher[times]
68
69 # AddRoundKey
70 addrounded = curCipher[invIndex] ^ kguess
71
72 # invSubBytes
73 roundKey = sbox.index(addrounded & 0xff)
74
75 humdis[times] = roundKey ^ curCipher[bnum]
76
77 numer = 0
78 denom1 = 0
79 denom2 = 0
80 meanh = np.mean(humdis, dtype=np.float64)
81 meant = np.mean(powerdata, axis=0, dtype=np.float64)
82
83 # 相関関数におけるΣ計算
84 for i in range(MAX_CIPHER):
85 diffh = humdis[i] - meanh
86 difft = powerdata[i] - meant
87
88 numer += diffh * difft
89 denom1 += diffh ** 2
90 denom2 += difft ** 2
91
92 soukan[kguess] = max(abs(numer / np.sqrt( denom1 * denom2 )))
93
94 guesskey = np.argmax(soukan)
95 estimatedkey[invIndex] = guesskey
96 print("\r{}: {:02x} ({})".format(invIndex, guesskey, soukan[guesskey]))
97
98print(list(map(hex, estimatedkey)))
このコードだけHDDに残っていた ↩︎