シェル芸botで急にtextimgが動かなくなったやつ

なんか急にシェル芸botでtextimgが動かなくなったというお便りが寄せられた

シェル芸bot、textimgが動かなくなっちゃったっぽい？ https://t.co/z1AeskfYki

— まーた (@ma_tw) May 4, 2022

心当たりはあって、最近シェル芸botで使っているDocker Imageのベースイメージをubuntu 22.04にアップグレードした。タイミングをみるとこれが疑わしい。なんかシェル芸botを実行するときはコンテナランタイムとしてgVisorを使っていた気がするからそのあたりの噛み合わせかな、と思った。

TLのシェル芸人の皆様方が調査してくださる

runtime/cgo: pthread_create failed: Operation not permitted
SIGABRT: abort
PC=0x7faf529eea7c m=0 sigcode=18446744073709551610

goroutine 0 [idle]:
runtime: unknown pc 0x7faf529eea7c
stack: frame={sp:0x7ffcf035cf40, fp:0x0} stack=[0x7ffcefb5e498,0x7ffcf035d4d0)
0x00007ffcf035ce40: https://t.co/w8FAb9ZgPy

— シェル芸bot (@minyoruminyon) May 4, 2022

#シェル芸
: webshでも同じエラーが出ているみたいhttps://t.co/JAO4iqsff8 pic.twitter.com/aEi6fSve8p

— *1 (@Sheeeeepla) May 4, 2022

webshというのは@jiro_saburomaruさん作のシェル芸botのWebインタフェースで、これはシェル芸botと同じDocker Imageを使ってるけど、実行しているホストとかは別物なので、やっぱりDocker Imageが悪いっぽい。webshのリポジトリはよくできていて、同バックエンドが構築されているかとかも書いてあるので見に行くとgVisorとかはつかってなさそう。じゃあgVisorは関係ないか

一方ローカル環境にdocker pull theoldmoon0602/shellgeibot して実験してみるとこちらは問題なく成功する。なるほど……。

エラーメッセージでぐぐってみると どうもOSの対応していないシステムコールを呼ぼうとしたっぽい？ ということがわかる。

ホストOSの更新が必要かな〜と思いながら、一応gVisor外してみるかとシェル芸botの実行環境に潜ったら、記憶とは裏腹にgVisor入ってなかった。そうなんだ……

なんとなくgVisorいれて、コンテナランタイムを指定して実行したらtextimg動いた。やった〜 じゃあこれでいっかということで、シェル芸botの設定ファイルをちょっといじって再起動したら動いた

なんか知らないけどちゃんと設定ファイルからコンテナランタイムを指定できるようになっていて偉い

https://t.co/vtqKzp1kUX pic.twitter.com/CiNmsscPZw

— シェル芸bot (@minyoruminyon) May 4, 2022

gVisor、一回入れた記憶はあるんだけど、なんで外したんだっけ……？　ということを思い出せません。 次は思い出せないまでも記録には残しておこうと思ってこのエントリを書いてる

---

どうもこういう感じなのかな……。なんとなく問題は解消したので深堀していないけど、なにがおきていたのかは知れたら楽しいので教えてください

シェル芸botのtextimgの問題、どうもglibc2.34が怪しい(Ubuntu 22.04のglibcは2.35)

— くおん (@qwertanus) May 4, 2022

*1:🐑++

slide attack - Plaid CTF 2022 choreography upsolve

こういう典型っぽいのでも意外と知らないのはいくらでもあるんだなと言うことでupsolveです。こういうのってどこで学ぶんですかね。知識を体系的に獲得していないとこういうところでボロが出る……。

問題概要

• 2種類のブロック暗号のロジックencrypt1, encrypt2 があります。ブロック長は32bitで鍵の長さも32bit。２つの暗号化ロジックは共通のSBoxを用いています
• ある秘密の鍵key を使って任意の平文をencrypt1、encrypt2 で暗号化できるオラクルがそれぞれ500回まで利用できます
• key を当てるのが今回の目的です

暗号化ロジックは以下の通り。それぞれの暗号化ロジックは非常に単純ですが、ラウンド数が尋常じゃない回数あって入力を工夫したりして直接暗号鍵を求めることは難しそうです。 また、ロジックをよく見るとラウンド鍵が奇数ラウンドと偶数ラウンドで別れていることがわかります。

ROUNDS = 2**22 + 2

def encrypt1(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS):
        a ^= sbox[b ^ k[(2*i)&3]]
        c ^= sbox[d ^ k[(2*i+1)&3]]
        a,b,c,d = b,c,d,a
    return bytes([a,b,c,d])

def encrypt2(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS)[::-1]:
        b,c,d,a = a,b,c,d
        c ^= sbox[d ^ k[(2*i)&3]]
        a ^= sbox[b ^ k[(2*i+1)&3]]
    return bytes([a,b,c,d])

スライド攻撃（slide attack）

今回の問題設定のように複数ラウンドで同じラウンド鍵が使われている時、スライド攻撃によってラウンド鍵を求めることができるかもしれません。

スライド攻撃のアイデアは非常に単純です。

まず、今回の問題設定は一旦忘れて、より単純なブロック暗号のモデルを考えます。今回考える暗号方式では、全てのラウンドで同じラウンド関数を用い、暗号化であるとします（lはラウンド数）。つまり、メッセージをラウンド関数にかける処理をと書いて、暗号化は です。

この時、ラウンド関数を一回だけ適用したメッセージを と書くとして をslid pair*1と呼びますが、このようなペアをもし知っていればという式からラウンド鍵を求められます。

当然そのようなペアを意図的に手に入れることは多くの場合難しいでしょうが、もし暗号化オラクルがあるなどの状況でknown-plaintextとそれに対応するciphertextのペアをいくつも手に入れられる場合、偶然その集合の中にはslid pairになるような組み合わせが存在するかもしれません。ブロック長をbitとしてbirthday boundを考えると、個のペアが存在すれば1つはslid pairが存在することが期待できます。そして、任意のペアとがslid pairかどうかは、と仮定して算出した鍵とと仮定して算出した鍵が一致しているかどうかで確かめられます（一致していればslid pair）。

したがってスライド攻撃は（最もナイーブには）

• 各ラウンドで同じラウンド鍵が用いられるブロック暗号において
• 暗号化オラクルを有している時
• ブロック長に対しておよその探索でラウンド鍵を求めることができる攻撃

と言えそうです。もし鍵長がブロック長と同じなら、鍵を全探索するとの空間を探索することになりますからそれに比べると遥かに効率の良い*2攻撃と言えます。

2k-DES構造のブロック暗号に対するスライド攻撃

本題からは少しずれますがこちらも合わせて書いておきます。これまでは非常に単純な、各ラウンドで同じラウンド関数が用いられるようなケースを考えていましたが、例えば（今回の問題のように）奇数ラウンドと偶数ラウンドで異なる鍵が用いられるようなブロック暗号に対してはどのようにアプローチすると良いのでしょうか。一つの方針としては、のようなslid pairを探すことが考えられます。2ラウンド程度の処理であればそれぞれのラウンド鍵を求めることは造作もない、という場合であればこの攻撃は非常に単純明快で同様に効果的と言えそうです。一方、それが難しい場合にも（ブロック暗号の構造次第ではあるものの）工夫すれば効率的にスライド攻撃が可能であるということだったので紹介します。

今回取り上げるのは2k-DESと呼ばれるラウンド鍵が2種類のDESの亜種です。DESはfeistel構造と呼ばれる構成になっていて、これはブロックを半分に分けて左半分を、右半分をと置き、をラウンド関数として

と表せます。DESの場合は特に です。

この時というslid pairを考えることができます。記法としてはこれまで通りで、は適当な差分です*3。

を暗号化するとどうなるかを考えてみると、がなければとなりますがいまはがあるのでとなり、同様に *4となるところが となり、どんどん差分が伝搬していきます。最終的に得られたに対応する暗号文をとすると、 に対応する暗号文は *5となります。

この時、 が成立することからslid pairかどうかを判定でき、 からの具体的な値がわかるので、ラウンド鍵を求めることができます。

今回の問題の場合

さてでは早速スライド攻撃をやってみましょう！　今回はブロック長が32bitなので、およそ個程度の平文と暗号文のペアがあればスライド攻撃が適用できそうです！　それでは65535回クエリを……

……今回の問題設定では500回までしかクエリを投げられないということでした。500個のペアではslid pairが存在する確率は65536個の場合に比べて著しく低いので、これで問題が解けることは期待できそうにありません。更に工夫が必要になりそうです。

この工夫は天才的なひらめきをするか、全ての考えられる組み合わせをやってみるか、問題設定から感じ取る必要があるのですが、 としてみます。ここでです。

この時次の関係が成り立ちます。なぜこうなるかまで逐一説明したかったのですが（私が）却って混乱するので気になる場合は自分で追いかけてみてください。

この場合はが成り立っていればslid pairと判断でき、slid pairが得られればを全探索しながらうまく一致する鍵を探せば が求まり、よりを全探索してkey全体を求めることができます。

今回はの値はによって決まっているので、slid pairが存在するにはの組み合わせが偶然いい感じになればよく、birthday boundは ということになりそうです。これなら500回もクエリできれば十分そうに見えます。

exploit

でき上がったものがこちら

from ptrlib import Socket, chunks
from tqdm import tqdm
import secrets

ROUNDS = 2**22 + 2

sbox = [109, 86, 136, 240, 199, 237, 30, 94, 134, 162, 49, 78, 111, 172, 214, 117, 90, 226, 171, 105, 248, 216, 48, 196, 130, 203, 179, 223, 12, 123, 228, 96, 225, 113, 168, 5, 208, 124, 146, 184, 206, 77, 72, 155, 191, 83, 142, 197, 144, 218, 255, 39, 236, 221, 251, 102, 207, 57, 15, 159, 98, 80, 145, 22, 235, 63, 125, 120, 245, 198, 10, 233, 56, 92, 99, 55, 187, 43, 25, 210, 153, 101, 44, 252, 93, 82, 182, 9, 36, 247, 129, 3, 84, 74, 128, 69, 20, 246, 141, 2, 41, 169, 59, 217, 137, 95, 189, 138, 116, 7, 180, 60, 18, 238, 73, 133, 121, 62, 87, 40, 213, 37, 33, 122, 200, 192, 118, 205, 135, 53, 58, 89, 201, 21, 193, 149, 8, 112, 81, 243, 131, 158, 188, 154, 211, 147, 164, 195, 181, 222, 178, 67, 76, 115, 150, 127, 103, 254, 1, 249, 186, 88, 177, 61, 14, 152, 106, 161, 229, 70, 160, 175, 29, 224, 66, 38, 91, 79, 185, 114, 190, 6, 110, 194, 250, 119, 0, 230, 176, 51, 104, 219, 215, 151, 75, 13, 23, 165, 11, 139, 42, 167, 52, 85, 156, 253, 163, 19, 35, 140, 107, 31, 143, 166, 32, 47, 132, 239, 234, 71, 241, 157, 170, 64, 100, 16, 97, 227, 204, 34, 4, 50, 126, 209, 174, 46, 45, 28, 232, 24, 212, 244, 220, 173, 17, 54, 231, 108, 65, 202, 27, 68, 26, 183, 148, 242]
inv = {v:i for i,v in enumerate(sbox)}


def encrypt1(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS):
        a ^= sbox[b ^ k[(2*i)&3]]
        c ^= sbox[d ^ k[(2*i+1)&3]]
        a,b,c,d = b,c,d,a
    return bytes([a,b,c,d])

def encrypt1_reduced(k, plaintext):
    a,b,c,d = plaintext
    order = 0
    for i in range(ROUNDS):
        a ^= sbox[b ^ k[(2*i)&3]]
        c ^= sbox[d ^ k[(2*i+1)&3]]
        a,b,c,d = b,c,d,a
        key = bytes([a,b,c,d])
        if key == plaintext:
            order = i + 1
            break
    else:
        raise ValueError("ha?")

    for i in range(ROUNDS % order):
        a ^= sbox[b ^ k[(2*i)&3]]
        c ^= sbox[d ^ k[(2*i+1)&3]]
        a,b,c,d = b,c,d,a

    return bytes([a,b,c,d])

def encrypt2(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS)[::-1]:
        b,c,d,a = a,b,c,d
        c ^= sbox[d ^ k[(2*i)&3]]
        a ^= sbox[b ^ k[(2*i+1)&3]]
    return bytes([a,b,c,d])

def encrypt2_reduced(k, plaintext):
    a,b,c,d = plaintext
    order = 0
    for i in range(ROUNDS)[::-1]:
        b,c,d,a = a,b,c,d
        c ^= sbox[d ^ k[(2*i)&3]]
        a ^= sbox[b ^ k[(2*i+1)&3]]
        key = bytes([a,b,c,d])
        order += 1
        if key == plaintext:
            break
    else:
        raise ValueError("ha?")

    for i in range(ROUNDS % order)[::-1]:
        b,c,d,a = a,b,c,d
        c ^= sbox[d ^ k[(2*i)&3]]
        a ^= sbox[b ^ k[(2*i+1)&3]]

    return bytes([a,b,c,d])

N = 500
def main():
    sock = Socket("localhost", 9999)

    # fix b, d
    B, D = secrets.token_bytes(2)

    query1 = set()
    while len(query1) != N:
        a, c = secrets.token_bytes(2)
        query1.add(bytes([a, B, c, D]))
    query1 = list(query1)

    query2 = set()
    while len(query2) != N:
        a, c = secrets.token_bytes(2)
        query2.add(bytes([c, D, a, B]))  # twist
    query2 = list(query2)

    sock.recvuntil("ENCRYPT 1")
    sock.sendlineafter("hex): ", b"".join(query1).hex())

    sock.recvuntil("ENCRYPT 2")
    sock.sendlineafter("hex): ", b"".join(query2).hex())

    res = bytes.fromhex(sock.recvlineafter("result:").decode().strip())
    res = chunks(res, 4)
    res1 = res[:N]
    res2 = res[N:]

    # search slid pair
    for i in tqdm(range(len(res1))):
        a, b, c, d = query1[i]
        x, y, z, w = res1[i]
        for j in range(len(res2)):
            a_, b_, c_, d_ = query2[j]
            x_, y_, z_, w_ = res2[j]

            if y_ == w and w_ == y:
                print("[+] slid pair is found")

                for t in tqdm(range(256)):
                    k0 = inv[c_ ^ t ^ a] ^ b
                    k1 = inv[a_ ^ t ^ c] ^ d

                    k0_ = inv[x ^ t ^ z_] ^ y
                    k1_ = inv[z ^ t ^ x_] ^ w
                    if k0 == k0_ and k1 == k1_:
                        print("[+] delta is found")

                        for k2 in tqdm(range(256)):
                            k3 = t ^ k2
                            key = bytes([k0, k1, k2, k3])

                            if encrypt1_reduced(key, query1[i]) == res1[i]:
                                print("k2, k3 are found")
                                print("key is: {}".format(key.hex()))

                                sock.sendlineafter("hex): ", key.hex())
                                sock.interactive()
                                quit()


if __name__ == '__main__':
    main()

まとめ

ブロック暗号でラウンド鍵が使い回されている場合に誕生日攻撃によって任意のラウンド数だけずれた平文と暗号文のペア、slid pairを発見することによって任意のラウンドだけが適用されたペアを発見し攻撃するというスライド攻撃の原理を紹介し、応用としてPlaid CTF 2022で出題されてchoreographyという問題を解いてきました。いかがでしたか？　私はこんなの解けるわけないだろと思いましたが、本番で意外と14solves もあるんですよね。嘘だろ！ それでpressureが18solvesということは、CTF界隈の暗号屋は大別して何でも解ける層と何も解けない層に分類されることがわかりますね。そこそこの問題だけ解けるという存在は意外とレアなのか……？

スライド攻撃についてここがわからなかった / スライド攻撃のことをお前は何もわかっとらん。教えたるから正座せんかい / choreographyはこう考えるとわかりやすいです / 〇〇についても知りたいですなどの声をお待ちしております

参考文献

• slide attackについて： https://www.researchgate.net/publication/2630852_Advanced_Slide_Attacks
• choreographyの作問者writeup： choreography intended solution · GitHub

*1:slideのtypoではなく"slid pair"で正しいです。slidはslideの過去分詞形

*2:なんかもうちょっと言い方あるだろという気がします。なんていうべきなんですか

*3:文章中に明に登場しないので適当なと言っていますが実際にははともともxorを取られる都合上 です

*4:ここで使われる鍵はであることに注意

*5:ブロック暗号の総ラウンド数が偶数の場合

Plaid CTF 2022 pressure writeup

この土日はPlaid CTF 2022に出ていました。久しぶりにかなり頑張って張り付いた結果一問解くことができたのでwriteupです。

Plaid CTFは歴史ある高難易度CTFとして知られていて問題を解けて嬉しい。

overview

ed25519を用いた一種のDiffie Hellman鍵共有のようなプロトコルが実装されています。pynaclを使った実装になっていて丁寧だけど読みづらい。

from nacl.bindings.crypto_scalarmult import (
  crypto_scalarmult_ed25519_noclamp,
  crypto_scalarmult_ed25519_base_noclamp,
)
from nacl.bindings.crypto_core import (
  crypto_core_ed25519_scalar_mul,
  crypto_core_ed25519_scalar_reduce,
  crypto_core_ed25519_is_valid_point,
  crypto_core_ed25519_NONREDUCEDSCALARBYTES,
  crypto_core_ed25519_BYTES
)
import struct
import os
import ast
import hashlib
import random

def sha512(b):
  return hashlib.sha512(b).digest()

CONST = 4096

SECRET_LEN = int(random.randint(128, 256))
SECRET = [random.randint(1, 255) for i in range(SECRET_LEN)]

with open('flag', 'r') as f:
  FLAG = f.read()

def hsh(s):
  h = sha512(s)
  assert len(h) == crypto_core_ed25519_NONREDUCEDSCALARBYTES
  return crypto_scalarmult_ed25519_base_noclamp(crypto_core_ed25519_scalar_reduce(h))


def generate_secret_set(r):
  s = set()
  for (i, c) in enumerate(SECRET):
    s.add(hsh(bytes(str(i + 25037 * r * c).strip('L').encode('utf-8'))))
  return s


def genr():
  i = 0
  while i == 0:
    i, = struct.unpack('<I', os.urandom(4))
  return i


def handle_client1():
  print("Let's see if we share anything! You be the initiator this time.")
  r = genr()
  s = generate_secret_set(r)
  for k in range(1, CONST):
    s.add(hsh(bytes(str(k + CONST * (r % k)).strip('L').encode('utf-8'))))
  b = crypto_core_ed25519_scalar_reduce(os.urandom(crypto_core_ed25519_NONREDUCEDSCALARBYTES))
  server_s = set(crypto_scalarmult_ed25519_noclamp(b, e) for e in s)

  client_s = set()
  print("Send your data!")
  got = ast.literal_eval(input())
  for e in got:
    if not crypto_core_ed25519_is_valid_point(e):
      print("Bad client!")
      exit()

    client_s.add(e)

  server_combined_client = set(
    crypto_scalarmult_ed25519_noclamp(b, e) for e in client_s
  )

  client_resp1 = [e for e in server_combined_client]
  client_resp2 = [e for e in server_s]
  random.shuffle(client_resp1)
  random.shuffle(client_resp2)
  print(repr(client_resp1))
  print(repr(client_resp2))

  return r, s

def handle_client2(r, s):
  print("Let's see if we share anything! I'll be the initiator this time.")
  b = crypto_core_ed25519_scalar_reduce(os.urandom(crypto_core_ed25519_NONREDUCEDSCALARBYTES))
  server_s = set(crypto_scalarmult_ed25519_noclamp(b, e) for e in s)
  to_client = [e for e in server_s]
  random.shuffle(to_client)
  print(repr(to_client))

  client_s = set()
  print("Send client points: ")
  got = ast.literal_eval(input())
  for e in got:
    if not crypto_core_ed25519_is_valid_point(e):
      print("Bad client!")
      exit()

    client_s.add(e)

  masked_s = set()
  print("Send masked server points: ")
  got = ast.literal_eval(input())
  for e in got:
    if not crypto_core_ed25519_is_valid_point(e):
      print("Bad client!")
      exit()

    masked_s.add(e)

  if len(masked_s) != len(server_s):
    print("Bad client!")
    exit()

  if masked_s & server_s:
    print("Bad client!")
    exit()

  masked_c = set(crypto_scalarmult_ed25519_noclamp(b, e) for e in client_s)
  if masked_c == masked_s:
    print(FLAG)
  else:
    print("Aw, we don't share anything.")

def main():
  r, s = handle_client1()
  handle_client2(r, s)

if __name__ == "__main__":
  main()

は32bit（！）の乱数で、は

という集合です。最初にed25519上の点の集合を送り、その後256bit程度の乱数を用いた と 、 がもらえます。 となるような点の集合を求めることができればフラグを取得できます。ただしかつである必要があります。

方針

最終的な目的を達成するためにはの具体的な値を知ることが不可欠なので、まずはを求めたいというのが自然な発送に見えます。そしてが4バイトと小さいことから、まずはを求め、その後をを用いて算出することになりそうです。

rを求める

を求めるためにはとをうまく使う必要がありそうです。

のうちの部分はが用いられていて未知の値はだけで、未知と言っても候補の列挙が十分できる程度なのでこれが使えそうです。具体的にはから複数のについての剰余を求めて中国剰余定理でを復元できます。

たとえばこちら側でを用意しておけば、がに含まれていればであり、がに含まれていればであるということがわかるといった具合です。

ただし、たとえばとしても返ってきたでは未知数が掛けられていてどちらがでどちらがに相当するのかはわからなくなっています。2通り程度なら両方のパターンを試すこともできますが、全ての剰余についてそれをやっていては32bitの全探索をやっているのと同じです。

そこでと送った点の集合との対応を探す必要があります。ここで、仮にの場合の点に対応するがわかっているとすると、 であることからに一致する点があればそれがであると判断することができます。

の全ての点についてその点がであると仮定して上記のようにとを求め、もしどちらかが内に存在すれば、仮定が正しいと判断することができ、を見つけ出すことができます。がわかれば、同じ要領で対応付けを行うことでの点との点の対応を求めることができます。

あとはの点のうちに含まれるものからがわかるので、を計算することができます。の計算には比較的大きい剰余が３つもあれば十分です。

points = [
    hsh(str(1 + CONST*0).encode()),
    hsh(str(2 + CONST*0).encode()),
    hsh(str(2 + CONST*1).encode()),
]

for k in [4091, 4093, 4905]:
    for rem in range(k):
        points.append(hsh(str(k + CONST*rem).encode()))

sock.sendlineafter("data!\n", repr(points))  # Aを送っている

xs = ast.literal_eval(sock.recvline().decode())  # {b*P | P in A}
ys = set(ast.literal_eval(sock.recvline().decode())) # {b*P | P in s}

inv = crypto_core_ed25519_scalar_invert(h_int(str(1 + 4096*0).encode()))
k_0 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*0).encode()))
k_1 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*1).encode()))

pairs = []
P1_idx = None
for i, P1 in enumerate(xs):
    bX = crypto_scalarmult_ed25519_noclamp(k_0, P1)
    bY = crypto_scalarmult_ed25519_noclamp(k_1, P1)

    if not (bX in ys or bY in ys):
        continue

    # bXあるいはbYが見つかったということは仮定が正しく、P1を見つけることができた
    P1_idx = i

    # get r mod k
    for k in [4091, 4093, 4095]:
        for rem in range(k):
            krem = crypto_core_ed25519_scalar_mul(
                inv,
                h_int(str(k + CONST*rem).encode()),
            )
            bkremG = crypto_scalarmult_ed25519_noclamp(krem, P1)
            if bkremG in ys:
                pairs.append((rem, k))
                break
assert len(pairs) == 3
r, _ = crt(pairs)
print("[+] found r: {}".format(r))

sを求める

で、もさほど大きくないので、同じ要領で候補を全てから計算してそれがに含まれるかどうかを見れば候補が正しいかどうかを判定できます。

# calculate s
s = []
for i in range(256):
    for c in range(1, 256):
        k = crypto_core_ed25519_scalar_mul(
            inv,
            h_int(str(i + 25037*r*c).encode()),
        )
        bkG = crypto_scalarmult_ed25519_noclamp(k, P1)
        if bkG in ys:
            s.append(hsh(str(i + 25037*r*c).encode()))

for k in range(1, CONST):
    key = crypto_core_ed25519_scalar_mul(
        inv,
        h_int(str(k + CONST * (r % k)).encode()),
    )
    kG = crypto_scalarmult_ed25519_noclamp(key, P1)
    if kG in ys:
        s.append(hsh(str(k + CONST * (r % k)).encode()))

assert len(s) == len(ys)
print("[+] found s")

送るべきB, Cを求める

かつ, であるようなを求めます。とできれば一番楽ですが、これは禁じられているので、かわりにとすればいいです。

exploit

完成したexploitがこちらになります。libsodiumの演算で点を定数倍するときのint -> bytesの変換に自身がなかったのでcrypto_core_ed25519_addを使っているのがおちゃめポイントです

from nacl.bindings.crypto_scalarmult import (
  crypto_scalarmult_ed25519_noclamp,
  crypto_scalarmult_ed25519_base_noclamp,
)
from nacl.bindings.crypto_core import (
  crypto_core_ed25519_add,
  crypto_core_ed25519_scalar_mul,
  crypto_core_ed25519_scalar_reduce,
  crypto_core_ed25519_scalar_invert,
  crypto_core_ed25519_is_valid_point,
  crypto_core_ed25519_NONREDUCEDSCALARBYTES,
  crypto_core_ed25519_BYTES
)
import hashlib
import struct
import os
from ptrlib import Socket, Process, crt
import ast

CONST = 4096

def sha512(b):
  return hashlib.sha512(b).digest()

def hsh(s):
  h = sha512(s)
  assert len(h) == crypto_core_ed25519_NONREDUCEDSCALARBYTES
  return crypto_scalarmult_ed25519_base_noclamp(crypto_core_ed25519_scalar_reduce(h))

def h_int(s):
  h = sha512(s)
  assert len(h) == crypto_core_ed25519_NONREDUCEDSCALARBYTES
  return crypto_core_ed25519_scalar_reduce(h)


# -- main
sock = Socket("nc pressure.chal.pwni.ng 1337")
p = Process(["bash", "-c", sock.recvline().decode()])
sock.sendline(p.recvlineafter("hashcash token: "))
p.close()
# sock = Socket("nc localhost 9999")

points = [
    hsh(str(1 + CONST*0).encode()),
    hsh(str(2 + CONST*0).encode()),
    hsh(str(2 + CONST*1).encode()),
]
for k in [4091, 4093, 4905]:
    for rem in range(k):
        points.append(hsh(str(k + CONST*rem).encode()))

sock.sendlineafter("data!\n", repr(points))

xs = ast.literal_eval(sock.recvline().decode())
ys = set(ast.literal_eval(sock.recvline().decode()))

inv = crypto_core_ed25519_scalar_invert(h_int(str(1 + 4096*0).encode()))
k_0 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*0).encode()))
k_1 = crypto_core_ed25519_scalar_mul(inv, h_int(str(2 + 4096*1).encode()))

pairs = []
hG_idx = None
for i, hG in enumerate(xs):
    # assume hG as b*h(1)*G
    bk0G = crypto_scalarmult_ed25519_noclamp(k_0, hG)
    bk1G = crypto_scalarmult_ed25519_noclamp(k_1, hG)

    if not (bk0G in ys or bk1G in ys):
        continue
    # base is found
    hG_idx = i

    # get r mod k
    for k in [4091, 4093, 4095]:
        for rem in range(k):
            krem = crypto_core_ed25519_scalar_mul(
                inv,
                h_int(str(k + CONST*rem).encode()),
            )
            bkremG = crypto_scalarmult_ed25519_noclamp(krem, hG)
            if bkremG in ys:
                pairs.append((rem, k))
                break
assert len(pairs) == 3
r, _ = crt(pairs)
print("[+] found r: {}".format(r))

hG = xs[hG_idx]

# calculate s
s = []
for k in range(1, CONST):
    key = crypto_core_ed25519_scalar_mul(
        inv,
        h_int(str(k + CONST * (r % k)).encode()),
    )
    kG = crypto_scalarmult_ed25519_noclamp(key, hG)
    if kG in ys:
        s.append(hsh(str(k + CONST * (r % k)).encode()))


for i in range(256):
    for c in range(1, 256):
        k = crypto_core_ed25519_scalar_mul(
            inv,
            h_int(str(i + 25037*r*c).encode()),
        )
        bkG = crypto_scalarmult_ed25519_noclamp(k, hG)
        if bkG in ys:
            s.append(hsh(str(i + 25037*r*c).encode()))
assert len(s) == len(ys)
print("[+] found s")


# handle_client2
sock.recvlineafter("this time.")
b_server_s = ast.literal_eval(sock.recvline().decode())

sock.sendlineafter("client points: \n", repr([crypto_core_ed25519_add(e, e) for e in s]))  # 2*s
# masked_c = b*2*s
sock.sendlineafter("masked server points: \n", repr([crypto_core_ed25519_add(e, e) for e in b_server_s]))  # b*s + b*s = 2b*s

sock.interactive()

感想

主にpynaclとlibsodiumのAPIについての情報が少なかったこと、変数の命名に失敗して*1で時間を取られて結局4時間〜5時間くらい掛けました。もっと整ってたら半分の時間で解けたはず……。序盤はlibsodiumがわかりづらすぎてブチ切れてたけど終わってみたら面白かったです

*1:渡されたスクリプトの命名が悪いんですけど