SECCON 2019 Online CTF Crazy Repetition of Codes write_up

SECCON 2019 Online CTF

Cryptoが3問出たので3問ときました。特にほか２つは言うことがないので、Crazy Repetition of Codes のwriteupを書きます。

問題概要

crc32 という符号化を int("1"*10000) 回かけたので、その値を求めてね！という問題です。

import os
from Crypto.Cipher import AES

def crc32(crc, data):
  crc = 0xFFFFFFFF ^ crc
  for c in data:
    crc = crc ^ ord(c)
    for i in range(8):
      crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1))
  return 0xFFFFFFFF ^ crc

key = b""

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "TSG")
assert(crc == 0xb09bc54f)
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "is")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "here")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "at")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "SECCON")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "CTF!")
key += crc.to_bytes(4, byteorder='big')

flag = os.environ['FLAG']
assert(len(flag) == 32)

aes = AES.new(key, AES.MODE_ECB)
encoded = aes.encrypt(flag)
assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')

ここで、crcを引き継いで使用していることがわかります。 crc のwikipediaを読んで頂くと、割り算のあまりを求めてるんだなぁという気持ちになると思います。

一つの文字の場合、例えばTの場合は 0x[ord('T')]000000 = 0x54000000 ([]の部分は置き換えてねという意味で使ってます)の余りを求める問題になります。

文字列の余りはどういうことかというと、例えば、TSGの場合は 0x[ord('T')]000000[ord('S')]000000[ord('G')]000000 の余りを求める問題になります。

crc を引き継いでいるので、二回ループを回ったときは TSGTSG、3回ループを回ったときには TSGTSGTSG のように、文字列そのものの長さが長くなっていくイメージです。

さて、愚直に計算すると 10^10000 の計算をしなければならなく、1秒あたりに10^10回計算できたとしても10^9990秒かかるので無理です。

色々考えると、以下の2つの手法を思いつきました。

状態遷移をグラフとみなして閉路検出する方法

crcの状態量は高々 0x100000000 = 2^32 個しかないので、1e10000 もループを回していいたら、必ずどこかで巡回するはず。状態遷移をグラフとみなして、閉路を検出したらあとは割り算して余りの個数分回せばいいので、テーブル作成で最大 2^32、余りの個数が最大で2^32-1回で合わせて 2^33-1 回の計算で間に合うはずです。 1e10000 よりだいぶ少なくなりましたね。

適当に実装したため、メモリ使用量がえぐぐて諦めました。冷静に考えて vector<bool> の最適化を考えればそれを使うべきでした。

kusanoさんがこの解き方です

qiita.com

繰り返し二乗法を使った方法

もし、この割り算の余りを求める処理を行列で表すことができれば繰り返し2乗法を使って、log(1e10000) = 23025 回くらいで計算を終わらせることができるはずです。残念ながら、割り算の余りの処理を行列にすることは失敗したのですが、近いアプローチには成功しました。

zlibの実装には、crc32_combine というものがあります。これはどういう関数なのかというと、 crc1 = crc32("ABC"), crc2 = crc32("DEFG") だとすると、 crc32_combine(crc1, crc2, len("DEFG")) を渡すと、結合して crc32("ABCDEFG") を求めてくれるという関数です。

ソースコードを読み解いていくと、実は crc2 は最後の最後にしか現れなくて、 crc1 をずらす処理にほんとどの行数がかけられています。

crc1 をずらしていくというのはどういうことかというと、 crc32("ABC") から crc32("ABC\0\0\0\0") を求めて、DEFG が入る隙間を用意してあげる処理のことです。

隙間を作ったら、crcの世界では足し算はxorで表現するので、 crc32("ABC\0\0\0\0") ^ crc32("DEFG") = crc32("ABCDEFG") が求まるということですね。

zlibの実装では、ここを行列の繰り返し二乗法を使って求めているので、O(log(文字列の長さ)) の時間がかかることが読み取れます。

このcombineを使って、

crc1 = crc32("TSG") # crc1 => "TSG"
crc2 = crc_combine(crc1, crc1, 3) #  crc2 => "TSGTSG"
crc4 = crc_combine(crc2, crc2, 6) # crc4 => "TSGTSGTSGTSG"

このように倍々に増やしていき、２進数表記で組み合わせれば求まります。たとえば 6( = 0b110) ならば、

crc6 = crc_combine(crc4, crc2, 6)

7( = 0b111) ならば、さらに1を加えて、

crc7 = crc_combine(crc6, crc1, 3)

のようにすれば求まりますね。ダブリングでもO(log(文字の長さ))なので、全体の計算量的にはcombineがlogであることを考慮して、、log(文字の長さ)^2 で、おおよそ10^10くらいです。ちょっと多いですがまあどうにかなるでしょう。

ちなみに実装が終わったタイミングで残り90分でした。死ぬかと思いました。(6並列で計算を回してギリギリ間に合いました。)

zlibのソースコードを参考にしつつ、K&R時代のC言語をC++に直しつつ、lengthは uint64_t に入らないのでboostのBintに直しつつで、こんな感じのコードになりました。

// reference: https://github.com/madler/zlib/blob/master/crc32.c

#include <string>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

constexpr int GF2_DIM = 32;

uint32_t gf2_matrix_times(const array<uint32_t, GF2_DIM>& mat, uint32_t vec)
{
    uint32_t sum;

    sum = 0;
    int i = 0;
    while (vec) {
        if (vec & 1)
            sum ^= mat[i];
        vec >>= 1;
        i++;
    }
    return sum;
}

void gf2_matrix_square(array<uint32_t, GF2_DIM>& square, const array<uint32_t, GF2_DIM>& mat)
{
    for (int n = 0; n < GF2_DIM; n++)
        square[n] = gf2_matrix_times(mat, mat[n]);
}

uint32_t crc32_combine(uint32_t crc1, uint32_t crc2, Bint len2){
    int n;
    unsigned long row;
    array<uint32_t, GF2_DIM> even;    /* even-power-of-two zeros operator */
    array<uint32_t, GF2_DIM> odd;   /* odd-power-of-two zeros operator */ 

    /* degenerate case (also disallow negative lengths) */
    if (len2 <= 0)
        return crc1;

    /* put operator for one zero bit in odd */
    odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
    row = 1;
    for (n = 1; n < GF2_DIM; n++) {
        odd[n] = row;
        row <<= 1;
    }

    /* put operator for two zero bits in even */
    gf2_matrix_square(even, odd);

    /* put operator for four zero bits in odd */
    gf2_matrix_square(odd, even);

    /* apply len2 zeros to crc1 (first square will put the operator for one
       zero byte, eight zero bits, in even) */
    do {
        /* apply zeros operator for this bit of len2 */
        gf2_matrix_square(even, odd);
        if (len2 & 1)
            crc1 = gf2_matrix_times(even, crc1);
        len2 >>= 1;

        /* if no more bits set, then done */
        if (len2 == 0)
            break;

        /* another iteration of the loop with odd and even swapped */
        gf2_matrix_square(odd, even);
        if (len2 & 1)
            crc1 = gf2_matrix_times(odd, crc1);
        len2 >>= 1;

        /* if no more bits set, then done */
    } while (len2 != 0);

    /* return combined crc */
    crc1 ^= crc2;
    return crc1;

}

uint32_t crc32(uint32_t crc, uint32_t data){
    crc = 0xFFFFFFFF ^ crc;
    crc = crc ^ data;
    for(unsigned int i=0;i<8;++i){
        crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1));
    }
    return 0xFFFFFFFF ^ crc;
}

uint32_t crc32_str(uint32_t crc, const string& data){
    for(char c: data){
        crc = crc32(crc, c);
    }
    return crc;
}

int main(int argc,char *argv[]){
    string S = argv[1];
    uint32_t crc = crc32_str(0, S);
    Bint length = S.length();
    string num = "";
    for(int i=0;i<10000;++i) num+="1";
    Bint n(num);
    uint32_t res = 0;
    while(n > 0){
        cerr << n << endl;
        if (n & 1) {
            res = crc32_combine(res, crc, length);
        }
        crc = crc32_combine(crc, crc, length);
        length <<= 1;
        n >>= 1;
    }
    cout << res << endl;
}

50分くらい実行したら、crcが求まるので、それをもとに key を求めて、AES_ECBのdecryptをするだけです。

import os
from Crypto.Cipher import AES
from binascii import unhexlify

key = b""

crc = 2962998607
assert(crc == 0xb09bc54f)
key += crc.to_bytes(4, byteorder='big')

crc = 3836056187
key += crc.to_bytes(4, byteorder='big')

crc = 2369777541
key += crc.to_bytes(4, byteorder='big')

crc = 3007692607
key += crc.to_bytes(4, byteorder='big')

crc = 1526093488
key += crc.to_bytes(4, byteorder='big')

crc = 3679021396
key += crc.to_bytes(4, byteorder='big')

# flag = os.environ['FLAG']
# assert(len(flag) == 32)

# encoded = aes.encrypt(flag)
# assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')
aes = AES.new(key, AES.MODE_ECB)
cipher = unhexlify(b"79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e")
print(aes.decrypt(cipher).decode())