昨年に引き続き今年も SECCON Beginners CTF で Crypto 問題を 4 問出題しました。 詳細な解き方等は皆さんの Writeup に任せることにして、ここでは解説とか出題意図とかの裏話的なところを書いていこうと思います。

[warmup] So Tired (115 pt, 192 solves)

Warmup 用の簡単な問題は前回の CTF で ROT13 とかをする問題を出してしまったため、早くもネタ切れ感が……。 BASE64 と zlib 圧縮が交互に 500 回ずつ掛かったテキストファイルが渡されるのでデコードしろという問題です。 暗号じゃないじゃんという声もあると思いますが、ガバガバのオレオレ暗号の一種ということで許してください。

作問の方針としては、解くときの方針が自明なこと、その一方であまり楽になりすぎないことを重視しています。 競技中に単一換字式暗号でも良かったかなあという気がしましたが、ツールを知っているかどうかの要素が強くなりすぎてしまいそうなのでこれくらいの物量感で良かったのかなと思います。

ちなみに最初は BASE64 を 500 回やろうとしたんですが、 1 回ごとにサイズが 4/3 倍になるのでファイルサイズが指数的に増加し大変なことになりました。 そういう理由で回数を稼ぐために zlib の圧縮を挟んでサイズを減らさざるを得ませんでした。 zlib を見抜けなかった人はごめんなさい。

Party (223 pt, 96 solves)

Shamir の秘密分散からマルチパーティ計算っぽいのが作れるというところから Party という名前を付けたまではよかったものの、結局いいのが思いつかなくてストレートな秘密の復元問題になりました。

今回出題したのは (3, n) しきい値法です。 $f(x)=ax^2+bx+c$ のパラメータ $a, b, c$ は $f(x)$ 上の異なる 3 点が定まらない限り決まらないという特徴を用いて秘密分散を行います。 $f(x)$ 上の異なる点(シェア) $(x, y)$ を 3 人以上で持っておき、そのうち 3 人が集まると $f(x)$ のパラメータを復元できて秘密が入手できるという形になります。 これは Shamir’s Secret Sharing として知られていて、暗号の教科書なんかにも載っている内容になります。

おまけ: パラメータ設定が下手くそである1人のシェアから $y \bmod x$ するだけで $c$ が出てしまっていたらしいです。秘密分散失敗。 皆さんはこういうことがないように秘密を分散しましょう。

配布ファイル

encrypt.py:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from flag import FLAG
from Crypto.Util.number import bytes_to_long, getRandomInteger, getPrime


def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i)
    return y


N = 512
M = 3
secret = bytes_to_long(FLAG)
assert(secret < 2**N)

coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]
party = [getRandomInteger(N) for i in range(M)]

val = map(lambda x: f(x, coeff), party)
output = list(zip(party, val))
print(output)

encrypted:

[(5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787, 222638290427721156440609599834544835128160823091076225790070665084076715023297095195684276322931921148857141465170916344422315100980924624012693522150607074944043048564215929798729234427365374901697953272928546220688006218875942373216634654077464666167179276898397564097622636986101121187280281132230947805911792158826522348799847505076755936308255744454313483999276893076685632006604872057110505842966189961880510223366337320981324768295629831215770023881406933), (3084167692493508694370768656017593556897608397019882419874114526720613431299295063010916541874875224502547262257703456540809557381959085686435851695644473, 81417930808196073362113286771400172654343924897160732604367319504584434535742174505598230276807701733034198071146409460616109362911964089058325415946974601249986915787912876210507003930105868259455525880086344632637548921395439909280293255987594999511137797363950241518786018566983048842381134109258365351677883243296407495683472736151029476826049882308535335861496696382332499282956993259186298172080816198388461095039401628146034873832017491510944472269823075), (6308915880693983347537927034524726131444757600419531883747894372607630008404089949147423643207810234587371577335307857430456574490695233644960831655305379, 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125)]

Go RSA (363 pt, 36 solves)

今回の RSA 基礎枠です。 シンプルにNを素因数分解するだけの問題は前回出題してしまったので、 RSA 自体ではなく RSA にまつわる簡単な数学的考察の部分を問題にしました。 入力する数値をいろいろ試して「あっ!」って気づいたら超簡単に解けるというのを目指してましたが、 36 チームしか解いてくれなくて結構失敗しました。

問題文で指示されたポートへ接続すると、最初に暗号化したフラグを表示した後に数値の入力待ち受け状態になります。

$ nc 133.242.17.175 1337
Encrypted flag is: 9318937226265478192755178713312038975429868363445779154366299612536115721174480901730463245127253720824167472659169499409491468372870163790683944856056031398812739882713640789613746095764262002592575923641408582807919511160401519689566302275297808818010790159566935603839732395360284095060920489430086771216248107035593834913415510780416030735126634877084728885852239333643086895188828770252169016490781222402581054585290355727713818683626867672469325986788851464050962553056460464987133152549531826555601775717448254078465693519415596689148599172506945961247665569726252066551881222295186069526874360633637572395629
> 1
1
> 2
11044711154156942936628504283605318005866009067378953774587158949421009526739920246982794435305060318752077000298792927032042143138703094748408434644847606687867707823640034592313384979994606505542565436735815486089101150275397964991631933612980842020057980357650690389822729896538207351147801905850253494060297169378923253050427030726809857698026367976546607051173397295225640512931992034915166365808254607953863666279753226477308772952202091429799439900986666869476291859112218999252665192285908036755759428600015810325898507302209220309383218290124682560000689411780239937152368733859609393009762058478036732356086
> -1
17745300090195534914495384552602537729846714732597883782355863614000129377360083415010438423936697586614236760655020429553274912327184172441551221204574848769878995056492940081131041900260019138035823040769486109250590400738400035502749222572514636974476147285393749080499675405074208815702961309973733361029896643147525233203163169287956424123255638120028201065728027464729194889897782855839830328840367489107336857418151351418255882733603237106700850937136511812539711515731735143935040614827260502363683879507983394883865214983286235682183930667773283970001754963413915269591882788127917923008642285960333346507522
The D was 2253869996349964640252980469290073150483605496652956110354917202846286478434248353549092717714406681889267235236467797665463179123418542981880042804932801946388646945240814093341696946423614131025377893271971594265863779174305230564793697128242242369585721806057914877795433084697769415473876587946066443340565029168768869652280561177843505229410514185762596214407160770670589734356570507600611103816862902665827167143167814775881599508595639111252333657731172017734831257408188765956506375677491342593237527775186477826409121224179816570688820537381353035880799602502891552511971085924250141236493307736537173823009

問題文等では入力する数値と出てくる数値の関連性は特に明記していませんが、問題名が RSA なことから暗号化か復号のどちらかの処理をしていると考えるのが妥当です。 さらにもしこれが復号処理だった場合、最初に表示される暗号化フラグを入れるだけで問題が終わってしまうので、暗号化をする処理だと考えられます。 また、 1 つ重要なポイントとして、負数の入力を受け付けていることが挙げられます。 この手の問題では入力値として何を受け付けるのかをしっかり確認しましょう。

次に、$-1$ を入れたときの挙動を考えてみます。 RSA の $e$ が奇数になる1ことを考えると、 \[ (-1)^e \equiv -1 \equiv N - 1 \pmod N \] となるので、出てくる値は $N-1$ となることがわかります。 $d$ の値は接続を切る時に表示されるので、$N-1$ が得られればあとは $ c^d \bmod N $ の要領で簡単に復号することができます。

ちなみに、「最初に出てきた暗号化フラグを使って 3 回以内の操作で何かをする」というミスリードを誘うために数値の入力受け付けを 3 回にしたところ、異なる 2 つの数値を暗号化して得られる値をうまく使って $N$ を算出されてしまいました。 どちらの解き方も今後の参考になると思うので確認しておくといいと思います。 $-1$ 解法はもっと気づかれると思ってたんですが、上がってくる Writeup が別解の方ばかりだったので意外と変な数値を入れる人はいなかったみたいです。 もっと evil な気持ちになりましょう。

Bit Flip (393 pt, 28 solves)

Crypto ジャンルのボス枠の問題です。 この辺の難易度の問題が解ければ普通の CTF に参加して暗号問題を開いても抵抗感無いだろう、というあたりを目安に作りました。

指定されたポートに繋ぐと以下のようにビットフリップした平文を暗号化した後の数値だけが表示されます。

$ nc 133.242.17.175 31337
8273148159667246239473812573128905861987382982503793924167947592693508705485522024530768011474754380163268280648634629026173338991076912595802191671767051596256864633707753583575542261662488649762924114342902103583274380940176336566070123254765423717315148734354040065839161657283103528662940671829126117083
$ nc 133.242.17.175 31337
58043339024566396812102147982997612647329123131650798170340802471246988715160593106930019302773055449456074111222795411286015638367596633582755713877219288283136732795476866219160425430211683831117319524203280764096864784538515769487010257802228563380284866654960467724073078385709646011024468713724985112048

この問題は「平文のどこかがビットフリップして暗号化されるときに平文を入手できるか?」という思考が問題の根本にあります。 実際のところこの問題は暗号文が 2 つあれば Franklin-Reiter Related Message Attack を使って、平文の差分を総当たりする方法で解くことができるという結果だったので今回出題してみました。

問題のポイントは 2 つです。 1 つ目は 2 つの平文の差がわかっていれば Franklin-Reiter Related Message Attack で解けるという点です。 これは RSA の典型的な脆弱性を調べると見つかると思います。 このままでは平文の 2 つ集めてもどうしようもありません。 2 つ目のポイントは、あり得る差分のパターン数は高々 RSA のビット数の 2 乗くらいしかないという点です。 あるビットを反転させるという操作は $2^n$ を足すか引くかのどちらかになるということを踏まえると、$2^a$ と $2^b$ をそれぞれ足すか引くかの 4 通り、$a, b$ の範囲は反転しうるビット数なので頑張れば全パターンを計算することができます。

実際の解き方については、Franklin-Reiter の方はももいろテクノロジーに記事(SageMathを使ってCoppersmith’s Attackをやってみる)があるのでそれをそのまま持ってくればよくて、あとは総当たりを書くだけになります。 また、総当たりを 1024 ビットすべてのビットに対して実行するとそこそこ時間がかかってしまうため、今回は下位の1/4ビットのみが反転するようにしました。 なんとなく制限を緩めてしまったおかげで、総当たりの代わりにShort pad attackから一発で差を出すという非想定解ができてしまいましたが、本来の解法と難易度はあまり変わってないので良しとします。

配布ファイル

server.py:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from Crypto.Util.number import bytes_to_long
import random

N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
e = 3
FLAG = bytes_to_long(open('flag', 'rb').read())

r = 1 << random.randrange(0, FLAG.bit_length() // 4)
C = pow(FLAG ^ r, e, N)

print(C)

まとめ

難易度的には易→中→中→難あたりを目指していましたが、解いた人数的には難が2つという構成になってしまいました。 前回と同程度の難易度を目指していても、基本的な問題は前回出してしまったのもあり、避けたら難しくなってしまったようです。


  1. $\phi(N)=(p-1)(q-1)$ より偶数なので $ed \equiv 1 \pmod{\phi(N)}$ を満たす $e, d$ は奇数である必要がある(偶数には逆元が存在しない)。 ↩︎