IGGG Advent Calender 2015のために書いた記事です。
常設CTFで遊んでたらXOR暗号を解読する問題が出て、地味に大変だったのでまとめました。
XOR暗号とは、平文をバイナリデータと考えて、2進数の鍵とXORをとって暗号化する手法のコトです。
例えば、文字をASCIIコードに変換して考えるとして
- 平文: FLAG(01000110 01001100 01000001 01000111)
- 鍵: A(01000001)
とすると、暗号文は
F ⊕ A ++ L ⊕ A ++ A ⊕ A ++ G ⊕ A
=> 00000111 00001101 00000000 00000110
となります。
XORの重要な性質として、
- A ⊕ B ⊕ B = A
と言うものがある。
要するに鍵さへわかってしまえば、同じ処理をするだけで解けるのです。
この暗号で重要なのの1つに鍵長があります。
上の例の場合は1バイト(1文字)でやりましたが、これが長くなるについて難易度が上がってきます。
平文と同じ長さのモノが与えられた場合、解くのは非常に困難でしょう。
今回は以下のような16進数の暗号文が与えられた。
C5F84351BE3DBDB6A69CFE4519BE38B4EFA589AE5315A93FE9B1F78DF25741A73AB3B2F48FA70641FF3EE4E4A488A453...
これを復号してフラグを手に入れればよいらしいです。
今回はヒントとして以下の2つがわかっています
- 元の平文は英語の文章になっている
- 鍵長は10バイト前後
これらの情報より、まずは鍵長を推測してみました。
今回は解読するのにHaskellを利用します。
暗号文をemcasの正規表現置換なんかを駆使して、扱いやすいように変換しました。
input = [0xC5,0xF8,0x43,0x51,0xBE,0x3D,0xBD,0xB6,0xA6,0x9C,0xFE,0x45,0x19,0xBE,0x38,0xB4,0xEF,0xA5,0x89,0xAE,0x53,0x15,0xA9,0x3F,0xE9,0xB1,0xF7,0x8D,0xF2,0x57,0x41,0xA7,0x3A,0xB3,0xB2,0xF4,0x8F,0xA7,0x06,0x41,0xFF,0x3E,0xE4,0xE4,0xA4,0x88,0xA4,0x53...]::[Int]
GHCiでinput
何かと入力すれば、勝手に10進数に直ってくれます。
*Main> take 20 $ input
[197,248,67,81,190,61,189,182,166,156,254,69,25,190,56,180,239,165,137,174]
(take
は先頭のN個だけとってくれる関数)
ヒント1より平文が16進数で127より大きくなる文字は絶対にないことがわかっています。
要するに、鍵の同じ部分で暗号化してる暗号文字は127を境にきれいに分離されてるはずです。
以下のコードを実行して探ってみました。
*Main> take 20 $ map (input !!) $ takeWhile (< length input) [i*1 | i <- [0..]]
[197,248,67,81,190,61,189,182,166,156,254,69,25,190,56,180,239,165,137,174]
*Main> take 20 $ map (input !!) $ takeWhile (< length input) [i*2 | i <- [0..]]
[197,67,190,189,166,254,25,56,239,137,83,169,233,247,242,65,58,178,143,6]
*Main> take 20 $ map (input !!) $ takeWhile (< length input) [i*3 | i <- [0..]]
.
.
.
[197,81,189,156,25,180,137,21,233,141,65,179,143,65,228,136,17,231,182,86]
*Main> take 20 $ map (input !!) $ takeWhile (< length input) [i*8 | i <- [0..]]
[197,166,239,233,58,255,17,114,255,156,225,163,253,41,235,3,93,183,201,160]
*Main> take 20 $ map (input !!) $ takeWhile (< length input) [i*9 | i <- [0..]]
[197,156,137,141,143,136,182,200,156,211,219,203,207,217,221,200,201,210,217,208]
*Main> take 20 $ map (input !!) $ takeWhile (< length input) [i*10 | i <- [0..]]
[197,254,83,65,255,109,191,187,225,219,248,65,3,231,34,178,160,164,217,228]
ちなみに、Haskellの関数の意味は
map
: 引数の関数をリストの要素にそれぞれ適用したリストを返す(!!)
: リストの要素にインデックスでアクセスtakeWhile
: 述語が偽になるまでの要素のリストを返す
上のコードは単純にN個飛ばしで数字を集めてるだけです。
9個飛ばしで集めたときにキレイに128以上の数字が集まっています。
なので、鍵長を9
としてやってます。
次は実際にXORをとって文字となるかどうかを確認し、文字になる場合の数字だけを集めてみます。
文字の定義はこんな感じ
isChar c = elem c chars
where chars = ['A'..'Z'] ++ ['a'..'z'] ++ ['0'..'9'] ++ [',','.',' ',':']
10進数同士のXORをとりたいのですが、Haskellにはいい感じのが無いので、基数変換関数から定義しました。
dec2n :: Int -> Int -> [Int]
dec2n _ 0 = [0]
dec2n n d = reverse $ unfoldr
(\x -> if x <= 0 then Nothing else Just (x `mod` n, x `div` n)) d
n2dec :: Int -> [Int] -> Int
n2dec n = sum . zipWith (\a b -> a * b)(map (\x -> n^x) [0..]) . reverse
-- ビット長をそろえるための関数
putty :: Int -> [Int] -> [Int]
putty n = reverse . take n . (++ (repeat 0)) . reverse
で、XOR関数はこんな感じ
xor :: Int -> Int -> Int
xor a b = n2dec 2 $ zipWith xor2bit (to8bin a) (to8bin b)
where
xor2bit a b = (a + b) `mod` 2
to8bin = putty 8 . dec2n 2
で組み合わせて
serchKey :: Int -> Int -> Maybe Int
serchKey i key = if isChar $ chr (xor i key) then Just key else Nothing
で、こんな感じに実行してみる
*Main> mapMaybe (serchKey (input !! 0)) [0..255]
[128,129,130,131,132,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,156,157,159,160,161,162,163,164,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,188,189,191,229,233,235,240,241,242,243,244,245,246,247,252,253,255]
これは、暗号文の1つ目の数字でXORをとって、文字になる数字のリストです。
後は、同じ飛び数ずつで直積で畳み込んで候補を減らしてみます。
鍵長である9飛びだと他と比べられないので、5倍の45飛びでやってみます。
*Main> let solve = (\x -> mapMaybe (serchKey (input !! x)) [0..255])
*Main> take 5 $ reverse $ nub $ scanl intersect [0..255] $ map solve $ takeWhile (< length input) [i*45+0 | i <- [0..]]
[[188],[178,188],[176,178,188],[176,177,178,188,189,191],[168,176,177,178,188,189,191,233,235]]
*Main> take 5 $ reverse $ nub $ scanl intersect [0..255] $ map solve $ takeWhile (< length input) [i*45+1 | i <- [0..]]
[[],[151],[151,214],[151,212,214],[136,138,144,145,146,147,148,149,150,151,156,157,201,203,212,214]]
*Main> take 5 $ reverse $ nub $ scanl intersect [0..255] $ map solve $ takeWhile (< length input) [i*45+2 | i <- [0..]]
[[54],[32,33,54],[32,33,52,54],[0,1,16,17,18,20,21,22,26,27,32,33,48,49,50,52,53,54,58,59],[0,1,4,5,6,7,16,17,18,20,21,22,26,27,32,3336,37,38,39,48,49,50,52,53,54,58,59]]
ちなみに、Haskellの関数は意味は
tail
: リストの先頭以外を返すnub
: リストの要素の重複を無くすscanl
: 畳み込みの途中の要素をリストにして返すintersect
: 2つのリスト直積
(何故か)必ず1つに収束するわけではない感じですね。
これを考慮して、残ったやつを順に出力してみる。
solve n = last $ takeWhile (/= []) $ scanl intersect [0..255] input'
where
solve' = (\x -> mapMaybe (serchKey (input !! x)) [0..255])
input' = map solve' $ takeWhile (< length input) [x*72 + n | x <- [0..]]
*Main> map solve [0..(length input `div` 45)]
[[188],[149,151],[54],[35],[158],[91],[209],[215],[193],[188],[151],[54],[35,47,53,55,116,117,119],[136,137,139,158],[91],[199,209],[215],[150],[188],[151],[54],[35],[158],[91],[209],[215],[193],[188],[144],[54],[35],[158],[67],[203],[215],[149,212],[188],[151],[54],[35],[158],[91],[209],[215],[193],[188],[151],[54],[35],[158],[92],[209],[215],[193],[238],[210],[54],[35,52,53],[158],[91],[209],[200,202],[212,214],[188],[151],[54],[35,50,51],[158],[91],[209],[215],[193],[188],[149,151],[54],[35],[158],[91],[209],[215],[193],[188],[151],[54],[35,47,52,53,55,116,117,119],[186],[91]]
これより、鍵は[188,151,54,35,158,91,209,215,193]
だと推測できる。
実際に解いてみると...
*Main> let key = [188,151,54,35,158,91,209,215,193]
*Main> take 100 $ zipWith (\a b -> chr $ xor a b) input (cycle key)
"your flag is: ce8d59e67d8f61eab9abe5300bae53e43e2866ee\n\nDuring the early history of cryptography, tw"
解けた!
試行錯誤してやってみました。 実際はこんなにすんなりいってません。 なので解けたときはうれしかったー