WebページのURLが与えられた。
Webページは、URLとSignatureの入力を受け付けるものだった。
また、問題文より、https://EVILCODE/ から始まるURLと対応する署名を入力して送信するとよさそうだった。
Webページのソースを見ると、公開鍵のデータがあった。
さらに、「署名を送信するとデバッグ情報が出る」というヒントをもとにとりあえず最初から入っていたURLとSignatureを送信してみると、ソースに以下が追加された。
An URL of a web page was given.
The web page had a form to enter URL and Signature.
The challenge description implied that we should enter an URL beginning with https://EVILCODE/ and corresponding signature.
The source of the page had the public key.
Also, seeing a hint "some debug information will appear after sending a signature", I sent the default URL and Signature.
This resulted in this added to the source code:
このことから、署名の検証は何らかのハッシュ値と「署名を復号」したデータの一部をstrcmp関数で比較することで行っているらしいことが読み取れた。
文字列を比較する関数で署名を検証するというのは、RACTF 2021のHotel Codeiforniaでも行われており、
比較するデータの早い位置に値0x00のバイトが現れるようにすればよさそうである。
まず、ここで使われている署名について調べるため、公開鍵のデータを
This implied that the verification is done by comparing some hash value and a part of the "decrypted signature" via the function strcmp.
Comparing signature via a function to compare strings was also done in Hotel Codeifornia (RACTF 2021).
It will be good to have bytes with the value 0x00 appear near the head of data to compare.
Firstly, to investigate the signature used here, I decoded the public key via
From Base64, To Hex, Parse ASN.1 hex string - CyberChef
その結果、rsaEncryptionという文字列、1個の大きい整数、1個の小さい整数が現れた。
RSAらしいこと、署名は公開されている情報で検証できるはずであることを考えると、
署名を「小さい整数」乗して「大きい整数」で割った余りがdecrypted_signatureになると予想できた。
また、512 - 64という添字から、計算結果は512バイトにエンコードされ、端から64バイト目から比較が開始されそうであることが読み取れた。
Signatureとして0x00 1バイトをBase64エンコードしたAA==を送信してみると、
There were a string rsaEncryption, a large integer, and a small integer were in the result.
Considering that RSA looks used, and that signatures should be able to be verified using only public information,
I guessed that the decrypted_signature is the signature to the (the small integer)-th power modulo (the large integer).
Also, the index 512 - 64 is implying that the calculation result is encoded to 512 bytes and the comparision begins from the 64th byte from the edge.
I tried sending AA==, which is Base64-encoded one byte of 0x00, as Signature, seeing this:
Error: Incorrect signature length (expected 512 bytes).
と出てきた。そこで、0x00を512バイト並べてBase64エンコードしたデータを、以下のようにCyberChefで作成した。
Seeing this, I created data by generating 512 bytes of 0x00 and encoding in Base64 via CyberChef in this way:
Pad lines, From Hex, To Base64 - CyberChef
これをSignatureとして送信すると、Error: Invalid signatureが2個出てきた。
以下のように最初のバイトのみ0x01にしたデータを送信すると、Error: Invalid signatureが1個になった。
Sending this as Signature, I saw two Error: Invalid signature.
Sending following data with replacing only the first byte to 0x01, only one Error: Invalid signature appeared.
Pad lines, Pad lines, From Hex, To Base64 - CyberChef
以下のように最後のバイトのみを0x01にしたデータを送信すると、またError: Invalid signatureが2個になった。
Sending following data with replacing only the last byte to 0x01, two Error: Invalid signature appeared again.
Pad lines, From Hex, To Base64 - CyberChef
以下のように最後のバイトを0x02にしたデータを送信すると、再びError: Invalid signatureは1個になった。
Sending following data with replacing only the last byte to 0x02, Error: Invalid signature became only one again.
Pad lines, From Hex, To Base64 - CyberChef
これらの観察結果から、署名の数値は上位がバイト列で先、下位がバイト列で後に来る形式で表現されており、 0と1は無効とみなされると推測できた。
そこで、計算結果のエンコードでは数値の上位と下位のどっちがバイト列で先に来るかわからないため、とりあえず計算結果の両側から64バイト目が0x00になる数値を以下のプログラムで探した。
From these findings, I guessed that the number used as the signature is encoded in a format in which the higher bytes comes to the head and the lower bytes comes to the tail, and that the numbers 0 and 1 are judged as invalid.
As I don't know which of the higher or lower bytes of the number comes first when encoding the calculation result,
I searched for a number such that both of the 64th byte from the head and from the tail becomes 0x00 in the calculation result using this program:
その結果、13426が条件を満たすことがわかった。
この数値を以下のRecipeで署名に変換した。
As a result, I found that the number 13426 satisfies the condition.
I converted this number to the signature using this Recipe:
結果は以下のものになった。
The result is:
なお、このRecipeは任意の整数を入力とし、それを今回の署名の形式に変換できる。この性質はまた後で用いる。
次に、何のハッシュ値が使われているかを調べる。
署名の検証で用いられていると推測される512 - 64という添字より、今回使われているハッシュは64バイトであると予想できる。
以下のサイトには、128桁(64バイト)のハッシュアルゴリズムとして、sha3-512、sha512、whirlpoolの3種類が載っていた。
Note that this Recipe can recive any integer as an input and encode the integer as a signature used here. I'll use this feature later.
Then, I investigated what hash value is used.
From the index 512 - 64, which looked used in the verification of the signature, I guessed that the hash value used here is 64 bytes long.
This page listed three hash algorithms sha3-512, sha512, and whirlpool that yields 128-digit (64-byte) hash values:
hashアルゴリズムとハッシュ値の長さ一覧（＋ハッシュ関数の基本と応用） - Qiita
URLはデフォルトの https://GOODCODE/ を用い、先ほどのRecipeを用いて数値2、3、4を署名の形式に変換して送信すると、
Webページのソースコードのstrcmp(...) =の後の数値はそれぞれ57、72、230となった。
さらに、以下のようにしてPythonのインタラクティブで署名2、3、4の復号結果の各バイトの差分を求めた。
With the default URL https://GOODCODE/, I sent numbers 2, 3, and 4 with converting to the format of Signature using the Recipe.
As a result, the number after strcmp(...) = in the page source becom 57, 72, and 230, respectively.
Also, I calculated the differences in the bytes in the results of decoding signatures 2, 3, and 4 using the interactive mode of Python in this way:
すると、x[63]が72 - 57、y[63]が230 - 57と一致した。
さらに、(e2 >> (63*8)) & 0xffの値は198、(e3 >> (63*8)) & 0xffの値は183であった。
ということは、下位から64バイト目の値が小さい方がstrcmpの返り値が大きくなっている。
よって、今回のstrcmpが一致しなかったバイトの値の差を返すと仮定すると、
比較されているハッシュ中のバイトの値は署名2や3の復号結果のバイトの値より大きく、198 + 57 = 0xffであることがわかる。
CyberChefで https://GOODCODE/ のハッシュ値を求めると、
SHA3 (Size: 512) の最初のバイトが0xffとなり、SHA-512やWhirlpoolでは最初や最後に0xffは現れなかった。
よって、今回の署名におけるハッシュには、SHA3-512が使われていると推測できる。
SHA3-512をプログラムから求める方法を探すと、以下のサイトを参考にPythonで求められそうであることがわかった。
As a result, x[63] became equal to 72 - 57, and y[63] became equal to 230 - 57.
Also, the value of (e2 >> (63*8)) & 0xff was 198 and the value of (e3 >> (63*8)) & 0xff was 183.
We can see that smaller value of the 64th byte from the lowest is yielding larger return value of strcmp.
Therefore, assuming that the function strcmp used here returns the difference of the mismatched byte,
the compared byte in the hash value is larger then the byte in the results of decoding signatures 2 and 3, and its value is 198 + 57 = 0xff.
Obtaining hash values for https://GOODCODE/ on CyberChef,
the first byte of SHA3 (Size: 512) became 0xff, and 0xff weren't in the first nor last bytes of SHA-512 and Whirlpool.
Therefore, I guessed that SHA3-512 is used for the hash in this signature.
Searching for a way to calculate SHA3-512 from programs, I found that Python should be useful, according to this page:
PythonでSHA-3を使おう | 三鷹台でひきこもるプログラマの日記
pip install pysha3 を実行した後以下のプログラムを実行することで、
https://EVILCODE/ から始まり、SHA3-512の先頭が0x00になる文字列を探した。
I executed this program on https://EVILCODE/ and the first byte of SHA3-512 becomes 0x00.
I activated virtualenv and executed a command pip install pysha3 to prepare for executing the program.
その結果、https://EVILCODE/Cd が条件を満たすことがわかった。
この文字列をURL、先ほど求めた署名をSignatureに入力して送信することで、flagが得られた。
As a result, I found that https://EVILCODE/Cd satisfies the condition.
I obtained the flag by sending this string as URL and the signature found before as Signature.