BSidesSF 2019 CTF|rsaos - crypto-writeup-public

#BSidesSF2019CTF

Location - rsaos-774c47ae.challenges.bsidessf.net:9999

言われた場所につなぐと、何やらCLIのようなシステムに接続できる。こういう時は ? や help を駆使するのが良いことになっているのでやると、helpが動く。

> help
Unprivileged commands:
    date                Get the date
    debug               Debug the OS.
    echo                Echo the arguments.
    enable              Enable all commands as privileged.
    exit                Exit the OS.
    foldhash            Get foldhash of first argument
    get-publickey       Retrieve the Public Key
    help                Get information about all commands.
    md5                 Get md5 of first argument

Privileged commands:
    get-flag            Get the flag.
    get-privatekey      Retrieve the Private Key
    security            Get information about security.

date, echo, exit, help あたりは普通で、md5 x は echo -n x | md5sum と等価 debug enable すると各コマンドの実行毎に次のようなデバッグ情報がプリントされる。

> echo hoge
DBG: CRC-32(0x84dedc52) SIG(0xcdf985b18364b36dfdf4af6f2a3ff21d12e740802013957d41b6fa06c61a54c627c81ea68ff3958603b43461e7ddb40e431a89f2aebc9e7ba1acad47135bb5dfc769346639bdb45734b22e08dbf6e82f1c2713acebe239e51979ea4bc9999bafbdba80fc6a28801e791ab16b5f04f7ab4209965468390c7b28c066c856f930d0)
hoge

foldhashはよくわからない。

> foldhash x
foldhash(x): 0xec8a96dfa02951d88bd8

help foldhashで説明を見ることができた。Shattered対策としてSHA-1の出力160bitを半分に割って、80bit同士のXORをとったものらしい。

FoldHash is a hash that was developed in response to the

Shattered attack on SHA-1. FoldHash provides 80 bits of security by use of

an exclusive-or operation on the output of the standard SHA-1 hash split in

two.

>>> from hashlib import sha1
>>> hash = sha1(b"x").digest()
>>> foldhash = int.from_bytes(hash[:10], "big") ^ int.from_bytes(hash[10:], "big")
>>> hex(foldhash)
'0xec8a96dfa02951d88bd8'

このfoldhashはPrivileged commandsを発行するために必要みたい。

> enable
enable <enable|disable>

    Enable/disable all commands as privileged.
    Once enabled, all commands will require privileged authentication.

> enable enable

> echo piyo
RSA(FoldHash) sig: piyo
Privileged command validation failed!

security の help

> help security
security

    Authentication and authorization for operations is provided by RSA signing.
    Unpriviliged commands are automatically signed by the client using the IEEE
    CRC-32 of the full command line.
    
    Privileged commands must be manually signed by RSA over the FoldHash of the
    full command line.  FoldHash is a hash that was developed in response to the
    Shattered attack on SHA-1.  FoldHash provides 80 bits of security by use of
    an exclusive-or operation on the output of the standard SHA-1 hash split in
    two.
    
    All RSA signing operations are unpadded signatures of the hash value in
    big endian order.  This avoids attacks where only bad sources of entropy are
    available.

get-publickeyは普通に鍵がもらえる。Nをfactordbに突っ込んでみたけど何もなし。

> get-publickey
Public key parameters:
N: 0xd888075370effdb016d85de8c894ee7ac2764527210d8ce1d8bd14a06c67de148b4680781366002f9649e3885e18ab950120c660970ab9a499ea74ea7aa38fe732940b5204300ef7b96a608efec1a74007a4b1d592cf9eb23890d8fa416202857d0e0f9ebad79324d03d09db0502ff4bae0b2dfc0b150ddea806a5ff24e2d32f
E: 0x10001

> echo x
DBG: CRC-32(0x412abc8a) SIG(0x2e8a4f5bddedf48909c051a84bc79674ef586a5bffc9e76c164a717f07679c530fb8a8f1a462ede360e4b8976a506dcd12da13cc38e69ab21b4644ba2d83915d48055343b1bab285afca768b7c146d6180aa9376a5f02743ac43b57d08dd48dcb5c7f0c57f6f04974666af4f60f84df36593869fdd2eff7903613f439b6894d5)
> md5 x
DBG: CRC-32(0xfa3ede62) SIG(0x23b26ab7d957f4a9414c9fde44f86e452aebbda17eb872a7f0cb21d1c14ff92dd9b3fed69db97a45266e7d7d3c5db1863a8da42a4a9181a796738482a6cd746cfd6f55edbfd2486ec9cb5fb842fd743d5547e715ee2d29e3110cab66c058888e3ac7ea75f6230d477add7d3963cc728a9207081d2febdeb949cb41b26f263e31)
md5(x): 0x9dd4e461268c8034f5c8564e155c67a6

>>> hex(binascii.crc32("md5 x".encode()))
'0xfa3ede62'
>>> hex(binascii.crc32("echo x".encode()))
'0x412abc8a'

残るはSIGだけど、これはRSAによる署名のことだと思う。つまり入力した $cmd$ に対して以下のような計算が行われている。

$h = hash(cmd)$

$sig = h^d \mod n$

本当にこうなっているかは、先程もらった公開鍵を使って確かめれば良い。例えばhelpを実行したときには次のようなCRC-32値とSIGを得る。↓は必要な情報だけを書いているのでちょっとはしょっている

> debug enable

> help
DBG: CRC-32(0x08875cac) SIG(0xbb24d11ceb950b21b938558e355a1921bf5eaf940c564c6314eeef60209476a4b268609afb8455ee02402935073dc5ad131cd7d3e27d4bf5ffc9afdd1b1b94ace31c0be45f682725ce22885cdf5144c660feb168b66ec9542ef007a5589d210694b5aa45734c9b52ddfa63ec27e08605ffae7969c93a4e4921a38be1f217e45b)
Unprivileged commands:
    date                Get the date
    debug               Debug the OS.
    echo                Echo the arguments.
    enable              Enable all commands as privileged.
    exit                Exit the OS.
    foldhash            Get foldhash of first argument
    get-publickey       Retrieve the Public Key
    help                Get information about all commands.
    md5                 Get md5 of first argument

Privileged commands:
    get-flag            Get the flag.
    get-privatekey      Retrieve the Private Key
    security            Get information about security.

> get-publickey
DBG: CRC-32(0x8731d92b) SIG(0x14f70ca0e44bd03ddb5c0d4f63b96f17c56b58574024efae1a0918c236475bfb75f39959cb1068b09f4b4f91d45db74205dc895c7ed647f4de5b26fb62970ea5152a56c6dfc86bda282b7db246b4af0d4232eb49317ce0e16f13a63330e12204a264236c18ad45130968752eb7cc353d3ceca2a8f2d8edaae17a87668f2c09ce)
Public key parameters:
N: 0xd888075370effdb016d85de8c894ee7ac2764527210d8ce1d8bd14a06c67de148b4680781366002f9649e3885e18ab950120c660970ab9a499ea74ea7aa38fe732940b5204300ef7b96a608efec1a74007a4b1d592cf9eb23890d8fa416202857d0e0f9ebad79324d03d09db0502ff4bae0b2dfc0b150ddea806a5ff24e2d32f
E: 0x10001

get-publickeyコマンドを使うとe, n を教えてもらえるので $sig = h^d \mod n$ に対して $sig^e \mod n = h \mod n$ となっているか計算してみる。ゴミみたいに見にくくなった

>>> sig = 0x14f70ca0e44bd03ddb5c0d4f63b96f17c56b58574024efae1a0918c236475bfb75f39959cb1068b09f4b4f91d45db74205dc895c7ed647f4de5b26fb62970ea5152a56c6dfc86bda282b7db246b4af0d4232eb49317ce0e16f13a63330e12204a264236c18ad45130968752eb7cc353d3ceca2a8f2d8edaae17a87668f2c09ce
>>> n = 0xd888075370effdb016d85de8c894ee7ac2764527210d8ce1d8bd14a06c67de148b4680781366002f9649e3885e18ab950120c660970ab9a499ea74ea7aa38fe732940b5204300ef7b96a608efec1a74007a4b1d592cf9eb23890d8fa416202857d0e0f9ebad79324d03d09db0502ff4bae0b2dfc0b150ddea806a5ff24e2d32f
>>> e = 0x10001
>>> hex(pow(sig, e, n))
'0x8731d92bL'

CRC-32(help) と一致した。どうやらSIGは $CRC32(cmd)^d \mod n$ という計算で得られる値のようだ

一方 get-flagを実行しようとすると次のように $(foldhash(cmd))^d \mod n$ の値を求められる。

> get-flag
RSA(FoldHash) sig: 
Privileged command validation failed!

---

このあと全然わからなくて、さらにwriteupを読んでもわからなかったんだけど、どうやらRSAの乗法準同型性を使うみたい。乗法準同型性は次のような性質を言う。

$c_1 \equiv m_1 ^e \mod N$

$c_2 \equiv m_2^e \mod N$

$c_1c_2 \equiv (m_1m_2)^e \mod N$

求めたいのは $(foldhash(getflag))^d \mod n$ なので $a_1 a_2 ... a_n = foldhash(getflag)$ と素因数分解して $a_1^d, a_2^d, ...$ を得ると、その総積は $(foldhash(getflag))^d$ とnを法として等しい

となると、 $a_i^d$ を求めたいが、debugコマンドで見れるコマンドラインのsignatureは $(CRC32(cmd))^d$ だった。つまり $a_i = CRC32(cmd)$ となるようなcmdを入力してやれば、得られるSIGは $a_i^d$ になっているはず。

というわけでやることは

foldhash(getflag)を求めてその結果を素因数分解し $a_1, a_2, ..., a_n$ を得る（このとき素因数分解した各値が4バイト以下になるようにしないとどうあがいても $a_i = crc32(x_i)$ となる $x_i$ は現れない
各 $a_i$ について、 $a_i = crc32(x_i)$ となるコマンド $x_i$ を探し、 $r_i = (crc32(x_i))^d$ を得る
getflagを実行しSIGを求められたら $\prod_i r_i \mod n$ を答える

長い道のりだった。このためにCRCの勉強しちゃったしptrlibにrev_crc32を入れる羽目になった

from ptrlib.crypto.crc import rev_crc32
from ptrlib.pwn.sock import Socket
from primefac import primefac
from binascii import crc32
from hashlib import sha1
import re
import random
import string


def foldhash(cmd):
    h = sha1(cmd.encode()).digest()
    return int.from_bytes(h[:10], "big") ^ int.from_bytes(h[10:], "big")


sock = Socket("localhost", 9999)

sock.recvuntil("> ")
sock.sendline("get-publickey")
sock.recvuntil("N: ")
n = int(sock.recvline().decode(), 16)

while True:
    command = "get-flag " + "".join(random.choices(string.ascii_letters, k=4))
    h = foldhash(command)
    xs = list(primefac(h))
    if all(x.bit_length() < 32 for x in xs):
        break

print(command)
print(xs)

sock.recvuntil("> ")
sock.sendline("debug enable")

getflag_sig = 1
for x in xs:
    y = rev_crc32(b"echo ", x)
    assert crc32(b"echo " + y) == x

    sock.recvuntil("> ")
    sock.sendline(b"echo " + y)
    line = sock.recvline().decode()
    crc = re.findall(r"CRC-32\((0x[a-f0-9]+)\)", line)
    sig = re.findall(r"SIG\((0x[a-f0-9]+)\)", line)
    assert int(crc[0], 16) == x
    getflag_sig = (getflag_sig * int(sig[0], 16)) % n

sock.recvuntil("> ")
sock.sendline(command)
sock.recvuntil("sig: ")
sock.sendline(hex(getflag_sig))
print(sock.recvline().decode())
sock.close()

[+] __init__: Successfully connected to localhost:9999
get-flag VsKY
[3, 569, 569, mpz(1031), mpz(35951), mpz(46301), mpz(614659)]
The flag is: CTF{ugh_math_is_so_hard}
[+] close: Connection to localhost:9999 closed