ぺんぎんさんのおうち

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

zlibに対する攻撃(?)

あるCTFでこれを使った問題が出ていたので勉強のために.

 

zlibで圧縮したものを暗号化する場合, 平文と暗号文の長さが同じになるアルゴリズムを使うのは危ないよという話. 例えばAES-CTRとかRC4とか.

16bytes等のパディングをした方が良さそう.

 

基本的な内容は以下のサイトに書いてある.

www.sjoerdlangkemper.nl

要するに, 

data = zlib.compress(SECRET + your_input) 

 dataがわかるとき, 同じ文字列が複数回含まれるデータをzlib圧縮すると圧縮後のデータ数が小さくなるのを利用してSECRETが何かを推測することができる.

 

例えば

SECRET が "koresuki" であるとして

c1 = "koresuki" + "a" * 20

c2 = "koresuki" + "b" * 20

...

"koresuki" +  [a-z]を20回繰り返した文字列 を c1, c2, ...

それぞれ圧縮して長さを見てみると

"koresuki" + "i" * 20

のときだけ小さくなる.

 

最後の文字が "i" であることがわかったので, 次は

"koresuk" + "[a-z] + i" * 20

を試すと "ki" が得られる.

 

これを繰り返していくと SECRET を得ることができる.

 

 

以上を踏まえて検証してみた.

test

 

それぞれの文字を与えたときの圧縮後のデータ長を確認して最も小さいものを候補としている.

このコードだとSECRETに連続して同じ文字が使われている場合に対応できないので注意. 

 

実行結果は

[('a', 26), ('b', 26), ('c', 26), ('d', 26), ('e', 26)]
augimugi_suko

 1文字目が復元できていないが, SECRET = "secret_mugimugi_suko" となっていればちゃんと

[('m', 31), ('a', 32), ('b', 32), ('c', 32), ('d', 32)]
mugimugi_suko

:ok_hand:

むぎむぎすこだぞ

 

近況

ykm11.hatenablog.com

 

あ”ー あ"ー 

 

 

少し前に高専セキュリティコンテストに参加したり, 東京のマジカルミライに行ったりしました.

夏休みもあと半分ですね. 後期の授業は前期に比べてかなり楽(実習も受験もない)なので余裕ですね. ガハハw

友人と30日OS本の読書会をやったり, 最高の9月にしたいですね. 学会もあるので研究最優先ですが..

 

家もそろそろ本格的に探していきたいなぁと. 

 

 

ところで今日母が入院しました. 手術して1週間ほど入院するそうです.

 

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!

以上だ!!

 

 

Slack用にemojiを回転させたい

おさかな・‪‪とり組のゆうけむです.

 

いきなりですがemojiを回転させてSlackで使いたいじゃないですか.

これを 

f:id:ushiromiya3:20180830195337p:plain

 こう

f:id:ushiromiya3:20180830195400g:plain

 

寿司を

f:id:ushiromiya3:20180830210500p:plain

こう(元画像大きくて笑う)

f:id:ushiromiya3:20180830210534g:plain

f:id:ushiromiya3:20180830210738g:plain

 

 

bashコマンドを駆使して回転画像(gif)を作成するエントリもありましたが, 以前試してもうまく動いてくれなかったので自分でスクリプトを書きました.

 

処理の流れとしては

 

1. 入力画像をcv2で読み込んで 128 * 128 にリサイズ (Salckのemojiサイズ規定)

2. ある角度(angle * i; i = {0, 1, 2, ...})回転させた画像を配列imagesに格納

2.1 OpencvはBGR, PILはRGB形式で画像を表現するので変換しておく

2.2 透過画像だと透過部分が[0, 0, 0]で表示するときに真っ黒になるので[255, 255, 255]に変換

2.3 cv2で読み込んだ画像(配列)をPILオブジェクトとして再読み込み

3. 一定の角度回転された複数の画像がimagesに入っているのでそれらをGIFとして保存

 

# パラメータ

- img_file : 入力画像

- angle : 回転角度. 正数だと反時計, 負数だと時計周りに回転

- duration : 1周するまでの時間. 単位は [ms] なのでここを小さくするとより早く回転する.

 

for slack emoji

入力画像のサイズが(n, n)じゃないと見切れる部分が黒くなるのを確認しています.

いい感じに直してみてください.