いつぞやぶりのBlogカテゴリーネタ。

えらくバランス良く解けたのと、初めてcryptoの問題を解けたのが嬉しい。

Safe Prime (crypto)

RSA暗号の脆弱性を突く問題。

リチェルカセキュリティのこちらの記事が非常に参考になった。

特に以下の式が便利。c, e, p, q, nが分かれば元のmが計算できるというのが1行で纏まってる。

print(long_to_bytes(pow(c, pow(e, -1, (p - 1) * (   (2*p + 1)    - 1)), n)).decode())

c, e, nは問題として提示されているので、p, qをなんとかしないといけない。

pは512ビット、qは2*p+1なので総当たりするのは無理があり、これがRSA暗号の強度の保証になっている模様。

　

で、解法としてはpとqに関連性がある所に着目。2次方程式の解の公式を引っ張り出してこれれば、実は割と簡単にp, qが導き出せることに気付ける。

以上、屁でもない計算量でmが導き出せる。

　

getRank (misc)

システム1位のスコアを叩き出すと報酬としてフラグが貰えるゲーム。

まともにゲームに付き合っている暇は無いので、なにはともあれスコアサーバーに直接スコアだけ送り付けられるようにする。

ゲームのランク確認ボタンの作りがこう↓

<button onclick="getRank()" class="bg-green-500 hover:bg-green-700 text-white font-bold py-2 px-4 rounded">
        Get Rank
      </button>

getRank関数を呼んでいる模様。getRank関数の作りはこう↓

 function getRank() {
        const rankElement = document.getElementById("rank");
        const messageElement = document.getElementById("message");

        fetch("/", {
          method: "POST",
          headers: {
            "Content-Type": "application/json",
          },
          body: JSON.stringify({ input: `${score}` }),
        })
          .then((response) => response.json())
          .then((data) => {
            rankElement.textContent = data.rank ?? "-1";
            messageElement.textContent =
              data.message ?? "Error occurred.";
          })
          .catch((error) => {
            rankElement.textContent = "-1";
            messageElement.textContent = "Error occurred.";
            console.error(error);
          });
      }

jsonでscoreを任意に指定してPOSTすればいけそうというのが分かる。私はChrome拡張の「Boomerang – SOAP & REST Client」というクライアントを使用。

続いて、送り付けるscoreについても検討が必要。

現在1位のスコアは10 ** 255点であり、これを超えないといけない。また、300文字以上の数字は受け付けてくれない。

更に、chall関数にある通り、

if (score > 10 ** 255) {
    // hmm...your score is too big?
    // you need a handicap!
    for (let i = 0; i < 100; i++) {
      score = Math.floor(score / 10);
    }
  }

提出したスコアが 10**255点を超えると超絶減点が自動でされる仕様。いやなんじゃそら（）

つまり、スコア減点機能も回避するか、減点されても尚10**255を超える必要がある。

ここで肝になるのが39行目、parseInt関数。

  let score = parseInt(input);

300文字制限はstring型のinputの時点で、10**255点制限はparseInt後に判定されることを利用する。

具体的な解法としては、parseIntの仕様を利用する。仕様はこちらのサイトに分かりやすく纏められている。

“0x”から入力を始めることで、parseIntは16進数とかも表現できる。で、300文字制限は16進の状態で判定され、10**255点制限はparseInt後の10進で判定される為、この仕様を使えば上記の制限を回避可能。

16進で300文字以下であり、かつ10進に変換後10**355より大きい数字は存在する。以上、要件に合う適当な16進の数字を入れてPOST、フラグゲット。

simpleoverflow (pwnable)

ctf4bおなじみ。

配列外にまでread関数が書き込んでいるのを用いて、int型のis_admin変数に1を格納するだけ。

大学1年の時に苦しめられたネタで今は楽しんでるというのは感慨深い。

まとめ

去年手も足も出なかったcryptoに進展があったのは喜ばしい。