ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

KOSENセキュリティコンテスト2018に参加しました

こんにちは. 阿南高専チーム「おのせんち」のVtuberおたく担当ykm_knです.

ツイはやってませんね.

 

ところで昼前にマイクラやってたらダイヤでました.

 

さて, 9/1 ~ 9/2 に行われた高専セキュリティコンテストに参加しました. 今年は日本からの参加でしたよ. 

TWCTFやctf4bと被ってたのが辛かったですね. 4bの方はCrypto講義が初開催ということだったのでそちらも行きたかったですね. どうやら楽しそうなことしていたっぽいですし.

 

 

さて, せっかくCTFに参加iしたのでWrite-upを残そうと思います. 

かなり雑なので読みたい人だけ読んでください.

 

 

 

CMA

Common Modulus Attack. やるだけ

 

c1 = m^e1 mod n; c2 = m^e2 mod n

であるとき

s*e1 + t*e2 = GCD(e1, e2) = x

となる(s, t)を見つけることができれば

c1^s * c2^t 

= m^{s*e1} * m^{t*e2}

= m^{s*e1 + t*e2}

= m^x (mod n)

というもの.

※ sかt, どちらかが負数になる場合はちゃんと逆元を考える必要がある.

s, tは拡張ユークリッドの互除法から導出できます.

 

今回はGCD(e1, e2) == 1 なのでそのまま出力すればよい. 

GCD(e1, e2) == 1を言及している人がいないのは悲しいなぁ. 

 

m^gcd < n を満たす最大の素数が13だったので,

GCD(e1, e2) == 13

になるようにしたら面白かったのかなと. (去年のCBCTFに同じ問題が出ましたが)

 

RSA?

べき計算がない世界がどうこう言ってたので除算してみたらフラグ出た.

確認してみると

c = m*e < N

でしたね.

inv_eを求めてc*inv_eする方法でも確認しました.

想定解通りに解いてもらうなら 

m*e > n

となるような e (ただしGCD(e, n) = 1) を選択する必要があったわけですね.

eが小さい時のべき乗計算 c = m*e < n の場合にcのe乗根でmが求まるのと同じです.

 

以下検証コードです.

from Crypto.Util.number import *
import gmpy
(n, e) = (746149315120445105644911779735002615257864427638948809430146775899763900845401478319781237412694334410613686368021055483040278357991481684487813129494944899522460397699493087246505218096960286204364461639918177320793843718724747574381859928496072509749639870292090503328557688115529251888351927498428567126853657063832878452773780418783149866919316163560203180423276894765325460041738451797385343149303272504850808939009366426995340204717301911359661640524141292447180118808883848024348018576236114084330353144353115672904820149103681022683146560799116848906807498625698939954475819479000937838859292276566046219449122782347075051511004009561691484747596362940386608213329221089677679229620860810111092211338341215804260360529582967128623164620534814690277276443932913145186024258511492440354889009304938979173562941458331119511296138076261503871542382962671556195928643434506282416038086486816450594938254170549974935406839221438655021923764949572023494832426904174630809785240917462806646302389526945618245684059655484996935724994381587851879888451272335891503968849596157334527192713715105054266039301159419016747298458532769985135446278269957364121043506362499497443274900182869320930776855669486054000707293632271709427175565301,825821)
c = 34196057544535966582914714160221953732017949669815971420694645835609518260754242418191180642793

m1 = c//e
assert m1*e % n == c
assert m1*e < n
print(long_to_bytes(m1))

inv_e = gmpy.invert(e, n)
m2 = c * inv_e % n
print(long_to_bytes(m2))

 

assert m1 == m2

上2つが250, 300なのは...

 

 

 

ここから先, 本当に覚えてなくてかなり雑なので感想まで読み飛ばしてください.

思い出したら書きます. 記憶力のNASA

  

- Binary

login

ltraceでstrcmpしてるのがわかったのでやるだけ

 

asmreading

gdbで処理追ってたら最後の方にフラグ書いてあった

 

 

simple_anti_debugging

ptraceのcallをnopで潰したけどダメだったので, 

is_correct_password の後のジャンプ命令をnopで潰したら出た.

 

 

# 感想

非常に楽しかったです. うまく言葉にできませんが.

Webできるようになりたいですね. 弊チーム誰もできないので.  

あとはCryptoがうーんというお気持ちでしたね. 作問が難しいのは僕も重々承知の上ですが, もう少し難しいのが欲しかったです!! 

 

f:id:ushiromiya3:20180901184053p:plain

:penguin: がついてるのはなんなんでしょうかね. わかりません.

 

 ごめんなさい. 本当に覚えてないんです(解法聞かれても困る).

 

チーム全員5年生なので来年はありませんが, 僕だけでも作問者として呼んでくれ~

 

最後にイカれたチームメンバーを紹介するぜ!!

無理やりチームに入れたものの予定が被って当日愛媛に行ったmikimiki と Zong!

1日目の夜から徳島を発ち初音ミクのライブに行ったykm_kn!

ykm_knの離脱後, 孤独に戦ったyamaneko!

以上だ!!