Neoquest 2018：「飛行船？ あは！」

CTF NeoQuest 2018は最近終了しました。 カットの下で、飛行船、 ZeroNet 、フィードバック付きシフトレジスタ、および線形方程式系に関するタスクの2番目の部分の分析。



タスクでは、ZeroNetネットワーク上のサイトのアドレスが指定され、そこにチャットが展開されました。 なぜなら ZeroNetでは、サイトのコンテンツがローカルコンピューターにダウンロードされ、フォルダーをサイトでスクラブして、最初のキーとencrypted_storage.jsonを見つけました。

{ "encrypted_storage": [ { "secret_name": "SiteName", "secret_value": "84a303b9f188b0", "date_added": 1519915207692 }, { "secret_name": "SiteAddress", "secret_value": "e68cd4a46ee074121a040a6188d3f6d495f24480fc0e08b0d45d8fba875d9fd38e88", "date_added": 1519915235730 }, { "secret_name": "AdminUsername", "secret_value": "0d9ef480aa", "date_added": 1519915256867 }, { "secret_name": "AdminCert", "secret_value": "4b95e6dfd893b37293fe041188cd6d8da5af08d4fb80b0", "date_added": 1519915282130 }, { "secret_name": "SecondKey", "secret_value": "c73ab54b91c6099b0f0081ea9124e2f50e846f6fc674046b3b41a86048ae3e27b04d354c9b9786a158f9722821005362bcfae8d6c0a261addb0b2ef8e16fbdfc851b82e0829d", "date_added": 1519915320471 } ] }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どうやら、「secret_value」を解読する必要があります。 AdminUsernameの暗号文の長さが 5バイトであることに気付くかもしれません。 おそらく、平文は「admin」ですか？ これがガンマ暗号である場合、5バイトのガンマを取得し、それらが他の「秘密」に適合するかどうかを確認できます。 SiteNameの最初の5バイトを確認し、b "\ xe8Y \ x9aP5"を取得します。 結果はあまりありません...



また、サイトには次のようなページがあります。







つまずいたとき、暗号文の長さは平文の長さに等しく、暗号化と復号化はまったく同じ操作であることがわかります。 ゲーミングと非常に似ていますが、2番目の秘密を暗号化するために同じアルゴリズムが使用される可能性がありますか？



アルゴリズム自体は、 js / lfsr.jsファイルにあります 。 その中のガンマは関数によって生成されます

  function genKeyStream(key, iv, length) { var res = [] var state_len = bitLength(key) var state = iv.mod(bigInt(1).shiftLeft(state_len)) for (var i = 0; i < length; i++) { var next_byte = 0 for (var j = 0; j < 8; j++) { var next_bit = bitCount(state.and(key)) % 2 next_byte = (next_byte >>> 1) | (next_bit << 7) state = state.shiftRight(1).or(bigInt(next_bit).shiftLeft(state_len - 1)) } res.push(next_byte) } return res.reverse() }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これはフィードバックシフトレジスタです。 レジスタの長さはキーの長さと等しく、タップの位置はキーによって設定されます。 IVはキーの長さに合わせてカットされ、最初の塗りつぶしとして使用されます。 通常のフィードバックシフトレジスタとは対照的に、ここではガンマはレジスタの出力からではなく、入力から取得されます。



ガンマの最初のバイトが最後のバイトを暗号化することもわかりますFROM ... encrypted_storage.jsonに戻り、「admin」からガンマを取得し、 SiteNameの最後の5バイトを復号化します。「oChat」はまったく異なる結果です。 行SiteAddressの終わりを解読します-行に「1NeoChatZK4DxZJdg5WwocwxcUppA1eJgL」-サイトのアドレスが含まれていることがわかります。 この文字列の長さは34バイトです。 色域の最初の34バイト（272ビット）があります。

原則として、シフトレジスタを使用した暗号化は長い間強力であるとは考えられていませんでしたが、ガンマのごく一部しかまだそれを破ることができません...しかし、この暗号は「クラシック」とはわずかに異なります-ガンマはレジスタ入力から取得されます これを考えると、L = len（キー）の反復IVがシフトレジスタから完全に「絞り出され」、内部状態全体（レジスタの充填）がガンマの最後のLビットに等しくなることがわかります。 それから皆のために $$$i \ geq L$ 次の方程式を書くことができます。

$$

$$G_ {i-1} * K_ {L-1} + G_ {i-2} * K_ {L-2} + ... + G_ {i-L} * K_ {0} = G_i$$

ここで：

$$$G_i$ -i番目のガンマビット

$$$K_i$ -i番目のキービット

$$$L$ -キーの長さ

$$$*$ -論理AND

$$$+$ -排他的OR（XOR）

L個のそのような方程式のシステムを解くと、キーを見つけることができます。 そして、キーと内部状態（ガンマの最後のLビット）を知っていれば、必要なだけガンマを生成できます！ システムが最大で1つの解を持つには、少なくともL個の線形独立方程式が必要です。 つまり 右側に立つ $$$G_i$ のために $$$i \ in [L、2L-1]$ 。 したがって、キーの長さが以下の場合、問題を解決できます $$$272/2 = 136$ ビット。



それを解決するために、ガウス法に従ってシステムを解く関数を書く必要がありました。 見つかった既製の関数はすべて、実数または複素数の分野のすべてを解決し、ANDおよびXOR演算のセット（0、1）では解決しませんでした。 次に、Lの異なる値を調べました。システムがジョイントであることが判明した場合、そのようなキーによって生成される次のガンマビットが、私が知っているものと一致するかどうかをチェックしました。 の試合がありました $$$L = 128$ 。 数分後、キーがカウントされました！



実際、異なるLをソートすることはできませんでしたが、134個の未知数を含む134個の方程式のシステムをすぐに書き留めることができました。キーについては、最初の6ビットはゼロになります。