たのしいXOR暗号入門

xorCipher.md

たのしいXOR暗号入門

What is This ?

IGGG Advent Calender 2015のために書いた記事です。
常設CTFで遊んでたらXOR暗号を解読する問題が出て、地味に大変だったのでまとめました。

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つがわかっています

1. 元の平文は英語の文章になっている
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"

解けた！

おわりに

試行錯誤してやってみました。 実際はこんなにすんなりいってません。 なので解けたときはうれしかったー

おしまい