N1CTF 2019 Crypto Writeup(+1) Crypto道場四[6/100]

どうも。duckです。
N1CTFも解いてました。

Cryptoが2題あったなか1題だけ解けた（悔しい）のでWriteup書きます。

Part3-BabyRSA
なんでPart3なんだとかツッコミはいろいろあるけど解いていきましょう。
配られたファイルはこちら。

暗号化
Dropbox - BabyRSA.py - Simplify your life
暗号文
Dropbox - flag.enc - Simplify your life

短いので暗号化のpythonファイルははっちゃいます。

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
    while m:
        padding = random.randint(0, 2**1000) ** 2
        message = padding << 1 + m % 2
        cipher = pow(message, e, N)
        f.write(hex(cipher)+'\n')
        m /= 2

平文bitを下から順に1bitずつパディング入れながら暗号化してるだけですね。
Nがめちゃでかいのと、パディングもめちゃでかいのでこれどーすんのって感じです。

Crypto問題は困ったら（というかいつもだいたい）紙に起こしてみるようにしてます。
ということで数式になおしちゃうぞ☆。

とおく。

なので結局
です。
重要なのがmは0or1ということです。

んんん？
mが0の時は大変なことが起きますね。

はい。平方剰余です。
平方剰余の相互法則がありますから

を満たすが存在するかはすぐに判定できます。

つまり今回はが平方剰余であるかどうかを調べるとが0か1か判定できます。
計算にはSagemathを使いました。
コードはどっかに消えてしまったので見つかれば載せます。
すべてのchipherに対して平方剰余だったら0平方剰余でなかったら1を出力する用にfor文回すとかだったと思います。
下位ビットから求まっていくことに注意すれば解けました。

flag:N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}

フラッグのjacobiはヤコビ記号のことです。平方剰余の時に出てきます。
ついでにいうとヤコビ記号の拡張としてルジャンドル記号もいます。たしか。

TMCTF2019 Writeup Wildcard 100

どうも。duckです。
TMCTFやりました。

ぱっと見Cryptoがなくてテンション下がりましたが１題解けたのでWriteup書きます。

・Wildcard 100
配られたのは3と6の手書き画像が３万個くらいあるファイル。
Dropbox - data.zip - Simplify your life
こんなん。

３と６の狂気

問題文によると、
１．3と6の画像を分ける。
２．そのあとそれぞれのユニークなファイルを数える。
３．flagはTMCTF{3の画像の数_6の画像の数}

としろとのことなのでやりました。
MISCとかに近い感じですね。

１.3と6を分ける
人力で分けるのはつらすぎるので、問題文に書いてある通りクラスタリングアルゴリズムを使います。
まあ端的に言えば機械学習です。
いい感じのサイトを見つけたのでコードを使わせていただく。
scikit-learnで国旗画像をクラスタリングして似ているものを探す │ Web備忘録
modifyしたやつ。

import os
import shutil
import numpy as np
from PIL import Image
from skimage import data
from sklearn.cluster import KMeans

# 1. RGBに変換して保存する
for path in os.listdir('./data'):
    img = Image.open(f'./data/{path}')
    img = img.convert('RGB')
    img.save(f'./convert/{path}')

# 2. 3次元配列の画像データを2次元配列のデータに変換
array=np.array([path for path in os.listdir('./convert')])
feature = np.array([data.imread('./convert/'+path) for path in array])
feature = feature.reshape(len(feature), -1).astype(np.float64)

# 3. 学習(2種類のグループにクラスタリングする)
model = KMeans(n_clusters=2).fit(feature)

# 4. 学習結果のラベル
labels = model.labels_

# 5. 学習結果(クラスタリング結果の表示 + ラベルごとにフォルダ分け)
for label, path in zip(labels, os.listdir('./convert')):
    os.makedirs(f"./cluster/{label}", exist_ok=True)
    shutil.copyfile(f"./data/{path}",f"./cluster/{label}/{path}")
    print(label, path)

ちなみにこれサーキットラーンっていうライブラリ使ってます。
あとはてテンサーフローとかも有名ですよね。

まあそれはさておき、これで3と6のデータをよりわけることができましたとさ。
3が16768個で6が17254個でした。
はじめてやったけど教師なし学習ってこんなにきれいに分けられるのね。少しビビった。

２．ユニークなファイルを数える
どうすんだこれ。
バイナリで比較すりゃいいかと思って↓のコード書いた。

import numpy as np

def openread(path):
    a = open(path,"rb")
    img = a.read()
    a.close()
    return img

path='./0'
array=np.array([openread(path) for path in os.listdir(path)])
set = set(array)
print(len(set))

結果的にはこれでできてなかった。
phoenixによると、バイナリが違うのに画像として同じファイルが3の画像に一個あったらしいので
それを考慮して
flag:TMCTF{14962_347}

正直作問ミスかと思いました。phoenixがいてよかった。
引き続きN1CTFのWriteupも書かなきゃ。（終了まであと２時間あるけど諦め体制）

SECCON Beginners CTF 2018 Crypto Writeup(+2) Crypto道場②[4/100]

どうも。duckです。
happy!解くのは明日にさせてください。
昨日上げようとしてたやつ先にあげちゃいます。

1.[Warmup] Veni, vidi, vici
fileが３つあったらしい。

#part1
Gur svefg cneg bs gur synt vf: pgs4o{a0zber

#part2
Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u

#part3
{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥

part1,2はceaser暗号なので昔作ったpythonファイルにぶち込むとすぐ答えが出た。
(そのうちgitにあげる予定)

part3は自力で反転した。

flag:ctf4b{n0more_cLass!cal_cRypt0graphy}

2.RSA is Power

次のファイルが渡されたらしい。

RSA暗号ですね。

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

Nの桁数を数えてみたら77桁だった。bit数に換算すると

256bitとNが非常に小さいので素因数分解攻撃が有効である。

from Crypto.Util.number import long_to_bytes

def gcd(a,b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

#ax+by=gcd(a,b)の解[x,y]
def extend_gcd(a,b):
    k_list=[]
    while b != gcd(a,b):
        r = a % b
        k_list.append((a - r) // b)
        a = b
        b = r
    k_list.reverse()
    y = 1
    x = 0
    for k in k_list:
        temp_y = y
        y = x - k * temp_y
        x = temp_y
    return [x,y]

N = 97139961312384239075080721131188244842051515305572003521287545456189235939577
E = 65537
C = 77361455127455996572404451221401510145575776233122006907198858022042920987316

p=299681192390656691733849646142066664329
q=324144336644773773047359441106332937713
phi=(p - 1)*(q - 1)

d = int(extend_gcd(phi,E)[1]) % phi
print(long_to_bytes(pow(C,d,N)))

simpyを使ってたけど、素因数分解が1日たっても終わらない。
仕方ないのでsagemath入れたら数分で解けた。素晴らしい。

ctf4b{5imple_rs4_1s_3asy_f0r_u}

でたぞい！

TWCTF 5TH 2019 Crypto Writeup(+1) Crypto道場③[5/100] happy!

どうも。duckです。
TWCTF Happy!のwriteup書きます。

flag.enc
Dropbox - flag.enc - Simplify your life
happy
Dropbox - happy - Simplify your life
pub.key
Dropbox - pub.key - Simplify your life
Gemfile
Dropbox - pub.key - Simplify your life
Gemfile.lock
Dropbox - Gemfile.lock - Simplify your life

おいおいGemfileなんて知らねえよって人は、bundllerでぐぐるといいです。
gem installしてもいいけど。

バイナリファイルが読めないので、以下のコードをhappyファイルの適当な場所にはりつけて
実行します。

def show_key()
        puts "n"
        puts @attr[:n]
        puts "e"
        puts @attr[:e]
        puts "p"
        puts @attr[:p]
        puts "q"
        puts @attr[:q]
        puts "d1"
        puts @attr[:d1]
        puts "d2"
        puts @attr[:d2]
        puts "cf"
        puts @attr[:cf]
end

pubkey = Key.import(File.binread("pub.key"))
pubkey.show_key()

Nとeは公開鍵だから当然としてcfも見れます。
これも公開鍵なんかなあと思ってたんですが、ほかの方のwriteup読むとどうやら見せちゃいけないやつらしいですね。
ほうほう。

コード読むと

で、pとqは700bit以上の整数らしいです。
Nとcfわかってるんだからbit数を数えればk求まるんじゃね？
(cfはだからだいたいくらいのbit数になる。)

というわけで数えたら、
N:2200とか
cf:1500くらい
だったので、kは2です。

ここでcfにkをぶち込むと

でした。
なんだこれオイラーの定理使えるじゃん。
（オイラーのトーシェント関数とかで調べて。オイラーの定理って名前の定理は死ぬほどあるので探すの大変です多分。）

つまりこれが成り立ちます。

本番はここでギブアップ。
この先はcoppersmith's の定理を使うらしいです。

定理は書くのめんどうなので引用先をご覧ください。
要約すると
となる解（mod bじゃないのに注意）はある条件を満たしているときはすぐ求まるよということ。
しかもbがわからなくても大丈夫という意味不明さ。すうがくすごい。

今回は



であり、
とするとこの定理が使える条件を満たします。

あっさり出ているはの値をぶち込んでおけばいいです。
よく考えるとわかります。

sagemathのsmall_root関数を使うとめでたくpが出ます。正確には候補ですが。
あとはからさくっとqを計算して
pとqがわかったら復号関数にぶち込みましょう。

わたしはgenerate_key(k,bits)関数の中のpとqを求めたやつにして、keyをつくって
そのkey とflag.encをprivate_decrypt(str, pad = true)にぶん投げて復号してもらいました。

flag = File.binread("flag.enc")
#第一引数は意味なし　k=2
key = Key.generate_key(1, 2)
File.binwrite("answer", key.private_decrypt(flag))

TWCTF{I_m_not_sad__I_m_happy_always}
解けた。

なんかtexの使い方忘れすぎてる。
modが斜体だし、cfはfにしか-1かかってないし。
どうやるんだっけね。気持ち悪い。
今度調べときます。

今日はN1CTFやるぞ。

引用：
TokyoWesterns CTF 5th 2019: Happy! (Crypto, 242 pts, 36 solves) | void main

TWCTF 5TH 2019 Crypto Writeup(+2) Crypto道場[2/100]

おひさしぶりです。duckです。
最近全くCTFをやっていないのでCrypto道場と題してCrypt100題解くまで頑張る会やります。
解説は最小限にするので、わからないところはコメントいただければ気が付き次第対応します。
応援よろしく！

さて記念すべき最初の問題は
今週末に行われたTWCTFから2題解いたのでそこから。

１．real-baby-rsa
　与えられたのはcodeとoutputファイル。

flag = 'TWCTF{CENSORED}'
# Public Parameters
N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537

# Encrypt the flag!
for char in flag:
    print(pow(ord(char), e, N))

output
Dropbox - output - Simplify your life
code
Dropbox - problem.py - Simplify your life

flagとして使われる文字列を推測してencryptしてoutputファイルの中身と比較するだけ。

flag = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}'

# Public Parameters
N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537

enc=[]
ans=""
for char in flag:
    enc.append(str(pow(ord(char), e, N)) + "\n")

with open("output", mode='r') as f:
        lines=f.readlines()
        for line in lines:
            k=0
            for encnum in enc:
                if encnum == line:
                    ans = ans + flag[k]
                    break
                k=k+1

print (ans)

flag：TWCTF{padding_is_important}

2. simple_logic
codeとoutputファイルが配布。
code
Dropbox - encrypt.rb - Simplify your life
output
Dropbox - output - Simplify your life

code:
　message + key
　message XOR keyを765回繰り返す暗号化方式。
output:
　暗号化されたflagと平文と暗号文のペア６つが与えられる。どれも同じkeyで暗号化されたものと推測される。
（出なきゃ解けない）

指針：
keyは下位ビットから順番に決めていけることに気が付いたので、4bitずつ＊32回でkeyを復元。
key復元の際には与えられたペアの暗号化が正しく行えるかどうかを用いた。

require 'securerandom'
require 'openssl'

ROUNDS = 765
BITS = 128
PAIRS = 6

def encrypt(msg, key)
    enc = msg
    mask = (1 << BITS) - 1
    ROUNDS.times do
        enc = (enc + key) & mask
        enc = enc ^ key
    end
    enc
end

def decrypt(msg, key)
    enc = msg
    mask = (1 << BITS) - 1
    ROUNDS.times do
        enc = enc ^ key
        enc = (enc - key) & mask
    end
    enc
end

#4bitずつ下位ビットを埋めていく再帰的運用
def DecideLowestBit(relowbitkey,lowestbit)
    #encrypt(plain_example[i])=enc_exsample[i]
    plain_example=[0x29abc13947b5373b86a1dc1d423807a,0xeeb83b72d3336a80a853bf9c61d6f254,0x7a0e5ffc7208f978b81475201fbeb3a0,
    0xc464714f5cdce458f32608f8b5e2002e,0xf944aaccf6779a65e8ba74795da3c41d,0x552682756304d662fa18e624b09b2ac5]
    enc_exsample=[0xb36b6b62a7e685bd1158744662c5d04a,0x614d86b5b6653cdc8f33368c41e99254,0x292a7ff7f12b4e21db00e593246be5a0,
    0x64f930da37d494c634fa22a609342ffe,0xaa3825e62d053fb0eb8e7e2621dabfe7,0xf2ffdf4beb933681844c70190ecf60bf]
    ans_low_key=[]

    maxloop=2 ** 4
    for loop in 1..maxloop do
        #決定した下位ビット＋未決定の上位ビット
        templowbitkey=relowbitkey | (loop << (lowestbit - 4))
        mask=(1 << lowestbit) - 1
        for pair in 0..(PAIRS - 1) do
            lowplain=plain_example[pair] & mask
            lowenc=enc_exsample[pair] & mask
            if (encrypt(lowplain,templowbitkey)) & mask != lowenc then
                break
            end
        end
        if pair == (PAIRS - 1) then
            ans_low_key.push(templowbitkey)
        end
    end
    return ans_low_key
end

def CalcKey
    key_array=[0]
    for loop in 1..32 do
        temp_array=[]
        key_array.each do |lowkey|
            decide_array=DecideLowestBit(lowkey,4*loop)
            decide_array.each do |decidekey|
                temp_array.push(decidekey)
            end
        end
        key_array=temp_array
    end
    return key_array
end

key_array=CalcKey()
encrypt_flag=0x43713622de24d04b9c05395bb753d437
key_array.each do |key|
    puts "ans %x" % decrypt(encrypt_flag,key)
end

flag:TWCTF{ade4850ad48b8d21fa7dae86b842466d}

phoenixの途中の記事が気になって夜も眠れない。

chickが送るBeginners CTF 2019 Dump(Misc)の解説

はじめまして、chickです。
DumpのWriteUpを書きます。

(ほぼ)ワンライナーなので参考にはなりにくいかも...

DLしたdumpファイルをWiresharkなどで開くと、こんな感じになる。
ざっと見た感じ、ICMP,TCP,HTTPのパケットしかないようなので、適当にHTTPパケットに目星をつけた。
とりあえず抽出したらWebshellでhexdumpを投げてるっぽいので、戻りパケットのHTMLファイルをエクスポート(追跡->HTTPストリーム->保存)する。

中を見たら8進数3文字区切りの文字列が出てきたので、読めるようにしていく。

cat dump_export | sed 1,17d | head -n -2 | tr " " "\n" | sed s/^/0/g | while read line; do printf %x\\n $line; done | sed /^.$/i0 | tr -d "\n" | xxd -r -p > bin_export
これでフラグが入っているファイルが復元できるので、小分けにして解説していきます。

cat dump_export <- エクスポートしたファイルをcatする。これをしないと何も始まらない。

sed 1,17d <- 1〜17行目がHTMLのタグとかヘッダ情報で邪魔だったので消す。

head -n -2 <- 末尾2行もタグの括りで邪魔だったので消す。

tr " " "\n" <- 16進数に変換するときにスペース区切りだと都合が悪いので改行させる。

sed s/^/0/g <- 3文字区切りだと16進数に変換するときに都合が悪かったので行頭に0を追加する。

while read line; do printf %x\\n $line; done <- printfコマンドで1行ずつ16進数に変換していく。

sed /^.$/i0 <- 16進数に変換したときに先頭に0を足してくれなかったので足す。

tr -d "\n" <- バイナリ的に改行が邪魔なので消す。

xxd -r -p > bin_export <- 16進数のバイナリをファイルに復元する

fileコマンドで見たらgzipだったので展開したらtarアーカイブファイルが出てきたので展開
ファイルの展開まで1行で書くなら、
cat dump_export | sed 1,17d | head -n -2 | tr " " "\n" | sed s/^/0/g | while read line; do printf %x\\n $line; done | sed /^.$/i0 | tr -d "\n" | xxd -r -p > bin_export && tar -zxf bin_export

画像ファイルが出てくるので、開いてみるとFlagが出てきた。
いつかtcpdumpコマンドとsed,awkあたりでダンプファイルのエクスポートまでワンライナーで書きたい。

duckが送るBeginners CTF 2019 Leakage(Reversing)の解説

お久しぶりです。duckです。
今回はLeakageの解説になります。なりますが、あんまりよくはわかってないです。よくわからないけど分岐で張ってたら解けました。
まあ書いていきましょう。前回が難易度高かったので、なるべく優しく書きます。

ファイルをDLしたら、tar.gzファイルなので　”tar -zxvf　ファイル名”で解凍します。
（→[Linux]ファイルの圧縮、解凍方法 - Qiita)

謎のファイルleakageがゲットできたと思います。
謎なのでfileコマンドをうってみましょう。　

leakage

と、このようにどんなfileかがわかってしまう優れものコマンドです。fileえらい！
いろいろ書いてありますが、1行目にだけ注目しましょう。ELFって書いてあります。なんかこれはWindowsでいうexeファイルのようなもので、つまりは実行ファイルらしいです。へー。そうなのか。
じゃあ実行しよう。実行は"./leakage"でできます。
怒られます。許可がありませんとかでます。
なのでchmodコマンドで許可します。
"chmod 774 leakage"か"chmod a+x leakage"とかでいけるでしょう。たぶん。
(→chmod コマンド - Qiita)

さて実行できるようになったので、実行してみましょう。
”./leakage”！！！怒られます。なんなんだまったく。

angry

どうやら./leakage flagという感じで打ち込めよばーか。ということらしいです。
flag知らんがな。それを知りたいんだよ。
というわけで、なんとか"falcon"で手を打ってもらえないか聞いてみます。

falcon

ダメでした。ですよね。

まあつまりこのプログラムからFLAGを取り出せればいいんでしょう。がんばるぞい。
というわけで、アセンブリ見た。
（→アセンブリに触れてみよう - Qiita）
まずはGUIで見たいのでIDAで見てみた。（初心者が雑に紹介するCTF ～bin編～ - Qiita）

IDA

ふむ。まったくわからん。
どこで分岐するのかだけはわかった。引用したサイトにも書いてあるが、IDAはメモリの書き換えができない？らしいので分岐を見るためだけに使うことにした。

ということでここからはgdbというLinuxに標準で搭載せれているデバッガを使っていく。こいつはメモリ書き換えもできる。レジスタ書き換えもできる。えらい。
噂によるとcmpとtestという命令 が分岐をつかさどるといっても過言ではないようだ。
(正確には分岐に使われるフラグを書き換える人たち。分岐の操作はjzとかjeが行うらしい→インラインアセンブラで学ぶアセンブリ言語 第3回 (1/3)：CodeZine（コードジン）)
上の画像にもtest命令があるが、これはフェイクだ。
eaxレジスタを書き換えて、無理やり条件を満たさせてみたところ（やり方は後で）correctとでた。
それだけである。FLAGは教えてもらえない。悲しい。

ずいぶん遠回りしたが、次のステップに進もう。ぼんやりアセンブリを見てると怪しい関数がいることに気が付く。
そうis_correctだ。明らかにこいつが、FLAGと入力との比較を行っている関数だろう。
こいつを見る。

書くのに飽きてきたので明日続きを書く。
gdbについては
gdbの使い方のメモ - ももいろテクノロジー
のページを参考にさせていただいた。