Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

Padding Oracle Attack 分かりやすく解説したい

Padding Oracle Attack, AESを使うCTF問題で一番難しいのではないのでしょうか。僕もこれがあるせいでAES問題に強い苦手意識がありました。僕と同じような方も、この記事で得意になってくれると嬉しいです！Padding Oracle Attackが理解できると、どんなAES問題も強気で解きにいけると思います！



AESとは

いつもの。

暗号利用モード - Wikipedia

ブロック暗号の代表格ですね。あまり言うと違うよとお叱りを受けそうなのですが、DESに脆弱性が発見されてからAESが主流となり推奨されているといった感じです。

ブロック暗号とは、平文をN文字ずつ分けそれぞれ暗号化するような感じです。AESでは16文字ごと分けています。その暗号化の方式はいくつかあり、AESではECB, CBC, CFBモードなどがあります。



AESのCBCモードとは

暗号化

f:id:partender810:20210524231113p:plain
暗号化方式

平文を16文字ずつに分け、各ブロックをkeyというバイト列によって暗号化します。自分の理解ではkeyの値を知っていたとしてもどのように暗号化されるかは分からないです。pythonのpycryptodomeモジュールでは簡単にできますが、まあできないもんとしていても大丈夫だと思います。

keyとは別にivというバイト列も用意します。平文の第1ブロックをivとxorし、その値をkeyによって暗号化したのが暗号文の第1ブロックになります。続いて、平文の第2ブロックとivではなく暗号文の第1ブロックとxorしたのをkeyによって暗号化したのが暗号文の第2ブロックとなります。

以降は [平文の第kブロック] xor [暗号文の第k-1ブロック] -> (key) -> [暗号文の第kブロック] となります。

これがAESのCBCモードです。CTFでは他にECBモードが良く使われます。ECBは平文をただkeyによって暗号化するだけなので、同じ平文ブロックがあると同じ暗号文ブロックになるという欠点があります。その点、CBCモードは前の暗号文ブロック(もしくはiv)とxorするので、同じ平文ブロックがあっても異なる暗号文ブロックになります。


復号

f:id:partender810:20210524231143p:plain
復号方式

復号方式は、暗号化方式の手順を逆にしたものです。

まず第1暗号文ブロックをkeyによってdecryptし、ivとxorしたのが第1平文ブロックです。以降はkeyによってdecryptするのは同じですが、xorするのはその一つ前の暗号文ブロックとです。

CBCモードの暗号化/復号方式はこんな感じです。不慣れな方はじっくり勉強しましょう！
CBCモードのCTF問題で、Padding Oracle Attackを使わないものですが、これが分かるとよりこの攻撃が理解しやすくなると思います！

ångstromCTF 2021 writeup - Attack All Around



Padding方式 PKCS #7とは

AESでは、ある平文を暗号化する際に平文を16文字ずつ分けますが、その平文の長さが16の倍数でない時はどうなるのでしょうか。答えは平文の後ろに詰め物をして強引に16の倍数にします。この詰め物をパディングといいます。

ではPKCS #7がどのようにパディングしているかというと、パディングしている長さを値としてパディングします。はい、よく分からないですよね。具体例を出しましょう。

b"0123456789abcde" という平文を暗号化したいと思います。長さが15なので16の倍数にするには1つパディングする必要があります。その場合、PKCS #7方式では「b"0123456789abcde\x01"」となります。1つパディングするのでb"\x01"が1つあります。

では、b"0123456789abcd" という平文を暗号化したい場合のパディングは、どうなるのでしょうか。答えは「b"0123456789abcd\x02\x02"」です。2つパディングするのでb"\x02"が2つあります。

こんな感じで、3個のパディングはb"\x03\x03\x03", 11個パディングするにはb"0x0b"×11となります。このようにパディングがどれだけされているかがパディング値で分かるようになっています。これでどこまでが平文でどれが詰め物かが分かるようになりますね。

pythonのpycryptodomeでは、Crypto.Cipher モジュールにpad関数が実装されています。pad(byte列, 1ブロックの長さ(=基本16) )とするとPKCS #7方式でパディングしてくれます。style = で指定するパターンもあります。

加えて、unpad関数も実装されています。pad関数と同様に、unpad(byte列, 16)でパディングを消してくれます。ここで重要なのが、unpad関数は第一引数のbyte列がこのPKCS #7方式でパディングしていない場合、エラーを吐きます。まず一番後ろの1byteを見て、b"\x01" ~ b"\x10"でないならエラー吐きますし、そうであってもその長さ分同じものが続いていないとエラーを吐きます。

エラーを吐く例

  • b"abcdefghijklmnop"
  • b"abcdefghijklmno\x02"
  • b"abcdefghijkl\x04\x04\x03\x03"
  • b"abcdefghijkl\x04\x03\x04\x04"

エラーを吐かない例

  • b"abcdefghijklmn\x02\x02"
  • b"abcdefghijklmnop" + b"\x10"×16
  • b"abcdefghijklm\x03\x02\x01" -> パディングが1つとして扱われる

このunpad関数でのパディングが上手くいかなかった時のエラー、これを通信相手に教えてしまうとPadding Oracle Attackが出来てしまう環境となってしまいます。次の節で具体的に解説していきます！



用意した自作サーバ

GitHub - ksbowler/PaddingOracleAttack

こちらのgithubにも載せていますが、公開サーバーだけ載せますね。

import socketserver
import socket, os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad,unpad
from binascii import unhexlify, hexlify
from secret import FLAG, MSG
import base64

key = os.urandom(16)
iv = os.urandom(16)


def encrypt_data(data):
    pt = pad(data.encode(),16,style='pkcs7')
    cipher = AES.new(key, AES.MODE_CBC,iv)
    enc = cipher.encrypt(pt)
    return enc.hex()

def decrypt_data(encryptedParams):
    assert len(encryptedParams) >= 32
    IV = encryptedParams[:32]
    data = encryptedParams[32:]
    cipher = AES.new(key, AES.MODE_CBC,unhexlify(IV))
    paddedParams = cipher.decrypt( unhexlify(data))
    pt = unpad(paddedParams,16,style='pkcs7')
    return pt

def send_msg(s, msg):
    enc = msg.encode()
    s.send(enc)

def main(s):
    wlcm_msg = "Welcome to practice for Padding Oracle Attack\n"
    send_msg(s, wlcm_msg)
    msg = base64.b64encode(MSG.encode()).decode()
    send_msg(s, "Guest ciphertext: " + encrypt_data(msg)+'\n')
    IV = hexlify(iv).decode()
    send_msg(s, "IV : "+IV+"\n")
    while True:
        #任意の暗号文を復号できる
        send_msg(s, 'What ciphertext do you want to decrypt? (hex): ')
        ct = s.recv(4096).decode().strip()
        try:
            check = decrypt_data(ct)
            send_msg(s, "check you can login\n")
            #print("check :",check)
        except Exception as e:
            send_msg(s, str(e) + '\n')
            continue

        try:
            pt = base64.b64decode(check).decode()
            if pt[:25] == MSG[:25]:
                send_msg(s, "You can login!\n")
                if pt[25:] == "admin":
                    clear_msg = "OK! You are admin! Here is flag\n"
                    send_msg(s, clear_msg)
                    send_msg(s, FLAG+"\n")
                else:
                    guest_msg = "However, because you are not admin, we can not send you flag\n"
                    send_msg(s, guest_msg)
            else:
                invalid_msg = "We can not recognize your input for our service\n"
                send_msg(s, invalid_msg)
        except Exception as e:
            send_msg(s, str(e) + '\n')

class TaskHandler(socketserver.BaseRequestHandler):
    def handle(self):
        main(self.request)

if __name__ == '__main__':
    socketserver.ThreadingTCPServer.allow_reuse_address = True
    server = socketserver.ThreadingTCPServer(('0.0.0.0', 3000), TaskHandler)
    server.serve_forever()

流れとしては、

  1. 変数MSGにある文字列をbase64で暗号化し、AESのCBCモードで暗号化したものが送られる。
  2. この暗号化に使われたIVが送られる。
  3. 任意の文字列を復号してくれる。IVも自身で決められる。
    3-a. 復号時に失敗すると、エラー文が送られる。
    3-b. 復号しbase64decodeしたものと、変数MSGの前25文字と比較する。
    　3-b-1. 合致し且つ残りが"admin"だとflagがゲット。 (目標はここ)
    　3-b-2. 合致するが残りが"admin"でないと、loginできないと言われる。
    　3-b-3. 合致しないと認識できないと言われる。

この3-aが脆弱性なんです。次節で説明していきますね。



平文を手に入れる Decryption Attack

それでは本題の攻撃アルゴリズムについて書いていきます。
Padding Oracle Attackを簡単に言うと、暗号文ブロックc_iをkeyによってdecryptionした値Dec(c_i)が分かれば、そこから貰った暗号文ブロックc(i-1)とxorすれば平文ブロックp_iが分かるし、任意の平文ブロックp_iに対する暗号文ブロックc(i-1)をxorすることで作成できます。だからDec(c_i)を求めようという感じです。

githubにも載せているスライドに合わせて進めていきます。

この問題の目的は上記の3-b-1になることです。そのためにはまず、変数MSGがどんな文字列が分からないといけません。変数MSGがbase64 encodeされた値がCBCモードで暗号化されています。その暗号文から元の平文を求めていくのがDecryption Attackです。

まずは、平文の最終ブロックを求めていきます。今回は暗号文が16進数で96桁なので3blocksあります。なのでp3を求めていきます。

p3 = Dec(c3) xor c2 という式で復号されます。ここでDecとはkeyによって復号された値です。p3を求める前にこのDec(c3)を求めます(スライドではc2となっています)。

f:id:partender810:20210530145112p:plain
こんな感じ

本問のサーバは復号文は教えてくれませんし、Dec(c3)の値も教えてくれません。しかし、復号時にPaddingがきちんとされてないとエラー文を送ってくれます。それを使ってDec(c3)を求めます。

c2の16bytesを全てb"\x00"にして送ります。理由は後述します。そこから最後1byteを0x00から0xffまで全て試します。そうすると、一回だけPadding incorrectと出ない時があります。復号されたp3の最後1byteがb"\x01"となった時ですね。そうなった時に何を送ったかを覚えておきます。例えばそれが"f6"だったとします。そうなると、Dec(c3)の最後1byteが、0xf6 xor 0x01 = 0xf7であることが分かります！

f:id:partender810:20210530151438p:plain
こうしてDecの最後1byteが分かる

次に、Dec(c3)の最後2byte目を求めます。次はp3の最後2byteをb"\x02\x02"となるようにしたいです。まず、p3の下位1byteをb"\x02"にするには、0xf7 xor 0x02 = 0xf5をc2の下位1byteとします。そして、c2の下位2byte目を0x00から0xffまで全て試して、padding incorrectが出ないものを見つけます。先と同様にDec(c3)の2byte目を求めます。

f:id:partender810:20210530153619p:plain
Dec(c3)の下位2byteを求める図

ここまで来るとお分かりでしょうが、次はDec(c3)の下位3byte目を求めます。下位2bytesをb"\x03\x03"になるようc2の下位2bytesを調整し、c3の下位3byte目をbrute forceします。

f:id:partender810:20210530154809p:plain
c2の下位2bytesを調整するときの図

これを繰り返していくと、Dec(c3)の16bytes全て求めることが出来ます。そこからp3は簡単に分かります。1. で貰ったMSGの暗号文と求めたDec(c3)より、p3 = Dec(c3) xor c2の式に当てはめるとp3が求められましたね。

f:id:partender810:20210530155437p:plain
平文の最終ブロックが求められた

本問では、以下のような平文となりました。

m = b'PWd1ZXN0\x08\x08\x08\x08\x08\x08\x08\x08'

base64decodeすると、"=guest"となりました。文字列になったことから正しく動作していることが分かりますね。

先程少し触れた「c2の16bytesを全てb"\x00"にする」理由ですが、もらったc2の上位15bytesをそのまま使うとpadding incorrectと言われない時が二回ある可能性があります。平文のpaddingとごっちゃになってしまう場合に注意です。

f:id:partender810:20210530160203p:plain
元の平文のパディングと被る

f:id:partender810:20210530160300p:plain
本来はこれの一回だけincorrectと言われないようにしたい

p3が求められたので、次はp2を求めていきます。サーバに送る暗号文はIVとc1, c2とし、c3は送りません。c2を最終ブロックとすることで、p2のpaddingがどうか先程と同じようにしてDec(c2)→p2を求めていきます。

以上を繰り返して、平文全てを求めます。平文の先頭ブロックを求める時はIVを変えていきます。やり方は上のと変わりません。

b'bTF6MHIzX2xvZ2luX3NlcnZpY2U6IElEPWd1ZXN0\x08\x08\x08\x08\x08\x08\x08\x08'
base64 decode : b'm1z0r3_login_service: ID=guest'

IDがguestではloginできませんね。adminにしてloginできるように、Encryption Attackを行いましょう。

任意の平文に対する暗号文を手に入れる Encryption Attack

Decryption Attackは複雑で難しいと思いますが、これが理解できればEncryption Attackは大して難しくありません。やっていることはDecryption Attackとさほど変わりません。

Encryption Attackは、padding incorrectを教えてくれる時に、復号したら欲しい平文となる暗号文を作ることが出来る攻撃です。
本問では、b'm1z0r3_login_service: ID=admin'をbase64 encodeした平文、つまり「b'bTF6MHIzX2xvZ2luX3NlcnZpY2U6IElEPWFkbWlu\x08\x08\x08\x08\x08\x08\x08\x08'」が欲しいです。これの暗号文を作っていきましょう。

Encryption Attackの手順は、初めにDecryption Attackと同じようにDec(c_i)を求めます。c3はMSGの暗号文と変える必要はありません。そのDec(c3)を求めたら、b'PWFkbWlu\x08\x08\x08\x08\x08\x08\x08\x08'とxorした値をc2とします。c2とDec(c3)をxorしたらこの欲しい平文になりますよね。

f:id:partender810:20210530164707p:plain
欲しい平文に対して…

f:id:partender810:20210530164908p:plain
強引に暗号文を作っちゃう！

では、次にこの新しいc2のDec(c2)を求めるためにc1をいじくります。Decryption Attackと同じようにしてOKです。Dec(c2)が求まったら、欲しい平文の後ろから2つ目とブロックとxorしてそれをc1とします。同じようにしてIVも求めます。

IVとc1~c3を送ると、それが欲しい平文と復号されるので、adminとしてloginが出来てflagが手に入りました！

f:id:partender810:20210530165348p:plain
mission complete

m1z0r3{Padding_Oracle_Attack_is_so_difficult}



おわりに

githubにsolver.pyと公開サーバのserver.pyと作問者しか見られないsecret.py, そして解説資料のpdfを載せています。そちらもご覧ください。

GitHub - ksbowler/PaddingOracleAttack

Padding Oracle Attackを使う問題は多くはないですが、理解できるとほとんどのAES問題は解けると思います。はじめにも書きましたが、私もこれがあるからAES問題は好きではなかったのですが、分かると楽しくなりました！

crypto問題面白いけど実生活に活きることあるのだろうか、と考えながらCTFを解いているこの頃…。解けると楽しいんだよなぁ。でもタスクもある…。と苛まれている次第です。ご査収ください。



参考文献

cpawCTF level3 Common World ○○○○○○の定理じゃないの？

ちょっと納得いかなかったので共有。

問題文

Cpaw君は,以下の公開鍵を用いて暗号化された暗号文Cを受け取りました．しかしCpaw君は秘密鍵を忘れてしまいました.Cpaw君のために暗号文を解読してあげましょう.

(e, N) = (11, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)

暗号文: 80265690974140286785447882525076768851800986505783169077080797677035805215248640465159446426193422263912423067392651719120282968933314718780685629466284745121303594495759721471318134122366715904

これは…？

フラグは以下のシンタックスです.
cpaw{復号した値}

※復号した値はそのままで良いですが，実は意味があります，余力がある人は考えてみてください.

「これは…？」をクリックするとhint.txtが貰える。

Cpaw君は自力では解けないのでRSA暗号のプロに尋ねるとヒントをくれました.

(e, N) = (13, 236934049743116267137999082243372631809789567482083918717832642810097363305512293474568071369055296264199854438630820352634325357252399203160052660683745421710174826323192475870497319105418435646820494864987787286941817224659073497212768480618387152477878449603008187097148599534206055318807657902493850180695091646575878916531742076951110529004783428260456713315007812112632429296257313525506207087475539303737022587194108436132757979273391594299137176227924904126161234005321583720836733205639052615538054399452669637400105028428545751844036229657412844469034970807562336527158965779903175305550570647732255961850364080642984562893392375273054434538280546913977098212083374336482279710348958536764229803743404325258229707314844255917497531735251105389366176228741806064378293682890877558325834873371615135474627913981994123692172918524625407966731238257519603614744577)

暗号文: 14451037575679461333658489727928902053807202350950440400755535465672646289383249206721118279217195146247129636809289035793102103248547070620691905918862697416910065303500798664102685376006097589955370023822867897020714767877873664

クレーム

解法はCommon Modulus Attackをやるらしい。

e1=11, e2 = 13とすると、e1×6+e2×(-5)=1となる。問題文にある暗号文をc1, hint.txtにある方をc2とすると、m = c16 × c2-5 mod n で求まるとのこと。me1×6+e2×(-5) = m1 となりますからね。

ただCommon Modulus Attackが成立する条件は、「同じnと異なるeで同じ平文mを暗号化してはいけない」だ。hint.txtには同じ平文をeで暗号化したとは一言も言ってない。これをエスパーしろというのは酷では？

まあ、level2までのCrypto問題もそこまで難しい問題ではなかったから比較的簡単なCMAを扱ったというのは分からんでもないが、ちょっとなぁ。問題名も確かに…。うーん。

別解？

クレームをつけた理由として、Common Modulus Attackを使わずに解いたからがあげられる。

カーマイケルの定理を使った。この記事がわかりやすい。

p - 1 ≡ 0 (mod e) のときの RSA 復号方法 | y011d4.log

そもそもnは素因数分解可能でありそれで簡単に解けるかと思いきや、eとφ(n)が互いに素でない。Seccon Beginnersでも同様の問題があり、それを引っ張り出してきた。どうでもいいけど毎回beginnerのスペルが怪しい。engineerやpioneerにつられてbegineerと書きたくなる。

SECCON Beginners CTF 2021 Crypto writeup - Attack All Around

ここで腹が立ったのが、φ(n)がe2=13の倍数でもあったこと。hint.txtの暗号文を復号すれば何かヒントがもらえると思い込んでいたのでつらかった。

L = 3φ(n)/e とすれば後は記事通り。2じゃダメだった。

e=11なので11種類の平文が出てくる。かなり短い平文を発見したので提出したらcorrectだった。

from Crypto.Util.number import *
import math

n = (中略)
p = pow(2,607)-1
assert n%p == 0
q = n//p
e = 11
c = (中略)
phi = (((p-1)*(q-1))//(math.gcd(p-1,q-1)))
# カーマイケルの定理
d = inverse(e,phi//e)
m = pow(c,d,n)
L = pow(3,phi//e,n)
for i in range(e):
    mm = (pow(L,i)*m)%n
    print("cpaw{"+str(mm)+"}")
    
# Common Modulus Attack
ee = 13
cc = (中略)

s1 = 6
s2 = -5
cc_inv = inverse(cc,n)
M = (pow(c,s1,n)*pow(cc_inv,-s2,n))%n
print("cpaw{"+str(M)+"}")

cpaw{424311244315114354}

これが何かの意味を持つとのことで16進数ぽいとエスパーしたが11がある時点でダメ。これらしい。

ポリュビオスの暗号表 - Wikipedia

"RSAISEASY"となるようだが、カーマイケルの定理を使っている時点でどこがEASYやとまた怒る。

これだけ言ってますが、常設CTFには感謝してます。良い勉強になっています。

SECCON Beginners CTF 2021 Crypto writeup

Beginnerの範囲が広い。

SECCON Beginners

Result

f:id:partender810:20210523145854p:plain
まあまあいい結果ではないでしょうか

Writeup

simple_RSA

Let's encrypt it with RSA!
ファイル：simple_RSA.tar.gz

忘れない内に

$ tar -zvxf xxx.tar.gz

e=3と小さいです。me < n であるLow Public Exponent Attackだろうとエスパーし、cのe乗根を取るとあったのであとはlong_to_bytesして終了です。

import gmpy2
from Crypto.Util.number import *
n = (中略)
e = 3
c = (中略)
m,ch = gmpy2.iroot(c,3)
assert ch
print(long_to_bytes(int(m)))

ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

Logical_SEESAW

We have an innovative seesaw!
ファイル：Logical_SEESAW.tar.gz

flag[i]=0なら、key[i]がなんであろうと0になります。16回行って毎回0になっているところはflag[i] = 0, そうでないならflag[i] = 1として最後long_to_bytesすればOKです。

cipher = (中略)
cip = [[] for _ in range(len(cipher[0]))]


for j in range(len(cipher)):
    for i in range(len(cipher[j])):
        cip[i].append(cipher[j][i])
m = ""
for c in cip:
    if c.count("1") > 0: m += "1"
    else: m += "0"
print(long_to_bytes(int(m,2)))

ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM

Github Flavored Markdown
Google Facebook Microsoft
And...?
ファイル：gfm.tar.gz

enc = key × M × key (全て行列)であり、enc, keyが与えられているのであとはsageに逆行列や行列積を計算させればOKです。行列積なので掛ける順番に気を付けましょう。

key × M × key = enc
key × M × key × key_inv = enc × key_inv 
key × M = enc × key_inv 
key_inv × key × M = key_inv × enc × key_inv 
M = key_inv × enc × key_inv 
SIZE = 8
p = random_prime(2^128)
MS = MatrixSpace(GF(p), SIZE)

M = copy(MS.zero())
key = matrix( (中略) )
enc = matrix( (中略) )

key_inv = key.inverse()

d = enc*key_inv
p = 331941721759386740446055265418196301559
m = key_inv*d
for i in range(8):
    for j in range(8):
        print(chr(m[i,j]%p),end="")

ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Imaginary

虚数は好きですか？
接続方法: nc imaginary.quals.beginners.seccon.jp 1337
ファイル：app.py

AESのECBモードなのである平文に対して毎回同じ暗号文になります。

pythonの辞書型に対して、"1337i" in self.numbersがtrueになるのは、self.numbersのkeyに"1337i"が含まれている必要があります。

しかし、このサーバは"(自然数) + (自然数)i"とself.numbersのkeyを決めるので、「1337i"」の暗号文は簡単に作れそうですが、「"1337i"」の暗号文は無理そうです。なので、ちょうど「"」で平文ブロックが終わるものと、「1337i"」から始まる平文ブロックを暗号化してもらい、あとはそれら二つを合成して、「{xxx "1337i": xxx}」となる暗号文を生成します。

具体的には、step1を「1337i"」から始まる平文ブロックの暗号文を得る、step2を「"」で終わる平文ブロックの暗号文を得るとすると、

step1
re = 123, im = 456 をsaveする
re = 1, im = 1337 をsaveする
Export

step2 re = 1234, im = 4567 をsaveする
re = 1, im = 1337 をsaveする
Export

となります。あとはstep2で得られた暗号文の先頭64bytesとstep1で得られた暗号文の64bytes以降を足したものをImportすればflagが手に入ります。

json.loadsとかでエラー吐かないように平文を気を付けないといけなかったのが難しいですね。

ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

Field_trip

Someone is getting ready for a field trip.
ファイル：Field_trip.tar.gz

先に言うと、チームメイトが惜しいところまで解いて自分が修正してみたら、終了1分前flagが手に入りましたあぶね～～～～～。

Merkle-Hellman knapsack暗号であろうと目を付け、ググるとこのサイトが。

PlaidCTF CTF 2015: Lazy - うさぎ小屋

このサイトに載っているsolver丸パクリです。細かい手法は一切分かりません。

本当のBeginnersはこのソースコードみてナップザック暗号だ！となるのすら難しいと思います。経験がものを言いますね。

b = pub_key
n = len(b)

c = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756


MULTIPLIER = 100
B = matrix(ZZ, n + 1, n + 1)
B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b))
B.set_block(n, 0, MULTIPLIER * matrix([ - c ]))
B.set_block(0, 1, 2 * identity_matrix(n))
B.set_block(n, 1, matrix([ -1 ] * n))
#print '[*] basis: B =', B

# LLL algorithm
for x in B.LLL():
    if x[0] == 0 and all(x_i in [-1, +1] for x_i in x[1 :]):
        print('[*] found: x =', x)

        # decode x
        m = 0
        flag = ""
        for x_i in (x[1 :]):
            m *= 2
            m += int(x_i == +1)
        print('[*] plaintext: m =', m)
        while m > 0:
            flag += chr(m%256)
            m //=256
        print(flag[::-1])

チームメイトはこのサイトを参考にしてsolverを作ったとのことですが、私はある程度自分でやってしまい、それが原因で上手くいきませんでした。まずはsolverパクろう(教訓)

終了5分前、どうやっても復号できないとチームメイトからslackが来て、その復号文を2進数にして逆順にするとflagが出てきた！急いでsubmitしようとしたらloginしろと言われ焦る。これほどブラウザにパスワードを記憶させててよかったことはありませんでした(笑)

ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

p-8RSA

It looks someone is encrypting it with RSA.
ファイル：p-8RSA.tar.gz

これ本当にbeginnerか？？？

まず、qを素数生成して8ずつ小さくしていき、それが素数且つe=17とφ(n)が互いに素でないなら鍵生成を終了します。

後半部分はともかく、とりあえず素因数分解します。factorDBでは上手くいきませんでしたが、自作のフェルマー法で素因数分解できました。

さあ、eとφ(n)が互いに素でない場合はどうしましょう。とりあえずググって見つけたサイトのアルゴリズムをそのままパクるとflagが出ました。

RSA Risk: When e and PHI share the same factor

これはgoogle力がものを言いました。phi = φ(n)/eとすると、gphi mod N != 1となるgを見つけ、d = e^-1 mod phiとなるdを使って、m = cd mod N を計算します。適切なgだと、gmが元の平文になるとのことです。gはbrute forceします。eとφ(n)が互いに素ではないと、違う平文でも同じ暗号文になってしまうので、得られた平文もどきから頑張って元の平文を手に入れるようなイメージしか湧きませんでした。

def algo1(p,q,e,gg):
    phi = ((p-1)*(q-1))//e
    while True:
        ge = pow(gg,phi,p*q)
        if ge != 1: return ge
        gg += 1
        

n = (中略)
e = 17
c = (中略)
tmp, ch = gmpy2.iroot(n,2)

tmp = int(tmp)-1 #tmpが最初偶数だったため

while True:
    if n%tmp == 0:
        p = tmp
        q = n//p
        print(p)
        print(q)
        assert n==p*q
        phi = ((p-1)*(q-1))//e
        d = inverse(17,phi)
        print("d:",d)
        m = pow(c,d,n)
        l = 1
        fin = True
        while fin:
            mm = m*l
            mes = long_to_bytes(mm%n)
            if b"ctf4b" in mes:
                print(mes)
                fin = False
            l *= algo1(p,q,e,l)
            l %= n
    
    tmp -= 2

ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}

picoGym cryptography writeup

f:id:partender810:20210519205717p:plain

常設CTFは本当にありがたい。

picoCTF 2021で出題された問題のwriteupはこちらから

picoCTF 2021 writeup - Attack All Around

  • Mod 26 10pt
  • Mind your Ps and Qs 20pt
  • Easy Peasy 40pt
  • New Caesar 60pt
  • Mini RSA 70pt
  • Dachshund Attacks 80pt
  • No Padding, No Problem 90pt
  • It's Not My Fault 1 100pt
  • Play Nice 110pt
  • Double DES 120pt
  • Compress and Attack 130pt
  • Scrambled: RSA 140pt
  • It is my Birthday 2 170pt
  • Pixelated 200pt
  • New Vignere 300pt

は上のサイトから見てください！

今回は問題文、与えられたファイルなど省略しています。ご了承ください。
こちらから参照していただければ！

picoCTF

solved

The Numbers 50pt

1 -> A, 2 -> B, ... 26 -> Z と変換すればOKです。

PICOCTF{THENUMBERSMASON}

Easy1 100pt

table.txtはVigenere暗号の変換表のようですね。

Vigenère cipher - Wikipedia

decoder ↓ CyberChef

picoCTF{CRYPTOISFUN}

13 100pt

rot13ですね。13文字アルファベットをシフトさせます。

rot13.com

picoCTF{not_too_bad_of_a_problem}

caesar 100pt

もらったciphertextをrot13しても文章にはなりません。自分でrot1~25を作り、文章になるやつを探します。

def rotate(enc,cnt):
    x = ord("a")
    ret = ""
    for i in range(len(enc)):
        c = ord(enc[i])
        n = c-x
        ret += chr(((n+cnt)%26)+x)
    return ret


enc = "gvswwmrkxlivyfmgsrhnrisegl"
for i in range(26):
    dec = rotate(enc,i)
    print("picoCTF{"+dec+"}")

picoCTF{gvswwmrkxlivyfmgsrhnrisegl}
picoCTF{hwtxxnslymjwzgnhtsiosjtfhm}
picoCTF{ixuyyotmznkxahoiutjptkugin}
picoCTF{jyvzzpunaolybipjvukqulvhjo}
picoCTF{kzwaaqvobpmzcjqkwvlrvmwikp}
picoCTF{laxbbrwpcqnadkrlxwmswnxjlq}
picoCTF{mbyccsxqdrobelsmyxntxoykmr}
picoCTF{nczddtyrespcfmtnzyouypzlns}
picoCTF{odaeeuzsftqdgnuoazpvzqamot}
picoCTF{pebffvatgurehovpbaqwarbnpu}
picoCTF{qfcggwbuhvsfipwqcbrxbscoqv}
picoCTF{rgdhhxcviwtgjqxrdcsyctdprw}
picoCTF{sheiiydwjxuhkrysedtzdueqsx}
picoCTF{tifjjzexkyvilsztfeuaevfrty}
picoCTF{ujgkkafylzwjmtaugfvbfwgsuz}
picoCTF{vkhllbgzmaxknubvhgwcgxhtva}
picoCTF{wlimmchanbylovcwihxdhyiuwb}
picoCTF{xmjnndiboczmpwdxjiyeizjvxc}
picoCTF{ynkooejcpdanqxeykjzfjakwyd}
picoCTF{zolppfkdqeboryfzlkagkblxze}
picoCTF{apmqqglerfcpszgamlbhlcmyaf}
picoCTF{bqnrrhmfsgdqtahbnmcimdnzbg}
picoCTF{crossingtherubicondjneoach}
picoCTF{dspttjohuifsvcjdpoekofpbdi}
picoCTF{etquukpivjgtwdkeqpflpgqcej}
picoCTF{furvvlqjwkhuxelfrqgmqhrdfk}

picoCTF{crossingtherubicondjneoach}

spelling-quiz 100pt

alphabet = list('abcdefghijklmnopqrstuvwxyz')
random.shuffle(shuffled := alphabet[:])
dictionary = dict(zip(alphabet, shuffled))

これから小文字アルファベットを別の小文字アルファベットに変換しているようです。要は換字式暗号ですね。study-guideをquipquipに投げ変換してもらいます。全部投げると多いと怒られる(フリーズする)ので、適度に入れます。"h"の頻度が少ないので気をつけてください。

それから対応表を作ってflag.txtのを復号する。

https://www.quipqiup.com/

picoCTF{perhaps_the_dog_jumped_over_was_just_tired}

XtraORdinary 150pt

この問題面白かった。

まずflagとkeyをxorし、その後random_strs[0~9]とxorを最大(28 + 26 + 24 + 22 + 1)回行います。しかし、同じものをk回xorしたとしても、k%2回xorした値と等しくなります。xorの特性ですね。もし、aとrandom_str[0]が2k回xorしてたら、計算結果はaと同値です。2k+1回だったら1回xorしたのと同値です。つまり、random_strsの1つに対して、それとxorするかしないかの2通りしかなく、random_strsにはb"ever"が多く同一のを無視すると5種類しかないので、25 = 32通り試して上手くいくのを探します。

32通り試した後、出てくるのはflagとkeyのxorした値だけで、これでは上手くいったか、32通りの内どれが答えか分かりません。そこで、flag形式のb"picoCTF{"とxorさせます。keyの長さは分かりませんが、flagよりも短く長さを越えたら最初に戻るというようなrotateがされているので、keyの長さが7以下であれば解けそうです。この問題は他にヒントが無いのでkey長は7以下で一周して周期が分かるように設定されているはずとエスパーします。

ct = "57657535570c1e1c612b3468106a18492140662d2f5967442a2960684d28017931617b1f3637"
ct = long_to_bytes(int(ct,16))
rev = [b'break it', b'ever',b'and you will never', b'is absolutely impenetrable', b'my encryption method']
for i in tqdm(range(32)):
    for j in range(5):
        if i & (1 << j):
            ct = decrypt(ct, rev[j])
    flag = b"picoCTF{"
    print(i)
    k = b""
    key = []
    for j in range(8):
        tmp = ct[j]^flag[j]
        print(tmp)
        if tmp in key: print("plural key!")
        key.append(tmp)
        k += long_to_bytes(tmp)

65
102
114
105
99
97
33
65

となる時がありました。エスパー通り、keyの周期が見えました。

picoCTF{w41t_s0_1_d1dnt_1nv3nt_x0r???}

triple-secure 150pt

n1, n2, n3の内二つ選んで最大公約数を取るとp, q, rになり素因数分解ができいつものRSA方式に落とし込めます。

nxの秘密鍵をdxとすると、暗号化とは逆にd3->d2->d1の順で復号すればOKです。

p = math.gcd(n1,n2)
r = math.gcd(n3,n2)
q = math.gcd(n1,n3)

phi1 = (p-1)*(q-1)
phi2 = (p-1)*(r-1)
phi3 = (r-1)*(q-1)

d1 = inverse(e,phi1)
d2 = inverse(e,phi2)
d3 = inverse(e,phi3)

c = pow(c,d3,q*r)
c = pow(c,d2,p*r)
c = pow(c,d1,q*p)
print(long_to_bytes(c))

picoCTF{1_gu3ss_tr1pl3_rs4_1snt_tr1pl3_s3cur3!!!!!!}

la cifra de 200pt

ncして得られる暗号文はどうやら換字式暗号のようです。全く読めない英文ならほぼ間違いなく換字式暗号です。quipquipに投げて終了です。と思ったら復号されない。　　

flagになりそうな"pohzCZK{m311a50_0x_a1rn3x3_h1ah3x6kp60egf}"の部分が全くもってうまく復号されません。"pohzCZK"が"picoCTF"になるならzで矛盾します。

dcodeのcipher identifier など使いましたが分からず、結局他の方のwriteupを見ました。

picoCTF 2019 la cifra de - Points: 200 - Qiita

vigenere暗号なんて分かるか！！！とも思いましたが、"pohzCZK"が"picoCTF"になることから1, 5文字目は平文と暗号文が変わらないことから4文字keyのvigenereとエスパーできる方もいるかもしれませんね。

picoCTF{b311a50_0r_v1gn3r3_c1ph3r6fe60eaa}

Tapping 200pt

ncしてもらえる暗号文は明らかにモールス信号ですね。初めての方はこういうものかと覚えてください。CyerChefなどのMorse Decoderに任せましょう。

CyberChef

PICOCTF{M0RS3C0D31SFUN1261438181}

Flags 200pt

一度m1z0r3の勉強会でやったことある問題でした。

問題画像には正方形の旗があり、1つの旗が1文字になり"{"の文字より前の7文字は"PICOCTF"となりそうです。

「alphabet flag」と画像検索すると一発です。code flagというものらしいですね。大体のサイトではここまで復号できると思います。

"PICOCTF{F?AG?AND?TUFF}"

LとSが入るのだろうと提出してみるとincorrect。ちょっと悩んでみると、leetでは？となった。

Leet - Wikipedia

数字のflag codeでいいものはありませんでした。エスパー能力向上問題ですね。

PICOCTF{F1AG5AND5TUFF}

Mr-Worldwide 200pt

もらったmessage.txtを見ると、どうやら座標のようですね。

地理座標系 - Wikipedia

google map検索でこのまま検索するとその座標が表す位置にピンを置いてくれます。

f:id:partender810:20210519144840p:plain
こんな感じ

座標を全て調べた結果がこちらです。

  • Nakanocho, Kamigyo Ward, Kyoto, 602-0958
  • Odesa, Odessa Oblast, Ukraine, 65000
  • Dayton, OH 45402, United States
  • Hoca Paşa, 34110 Fatih/İstanbul, Turkey
  • Hazza' Bin Zayed the First St - Al Manhal - Abu Dhabi - United Arab Emirates
  • 50480 Kuala Lumpur, Federal Territory of Kuala Lumpur, Malaysia
  • _
  • Kirkos, Addis Ababa, Ethiopia
  • Av Nueva Loja, Loja, Ecuador
  • Martelaarsgracht 5, 1012 TN Amsterdam, Netherlands
  • 188 vida activa, Sleepy Hollow, NY 10591, United States
  • Kodiak, AK 99615, United States
  • Faculty Of Engineering, Al Azaritah WA Ash Shatebi, Qism Bab Sharqi, Alexandria Governorate, Egypt

ここから都市名か国名かの頭文字を抜き取ってflagにするんだろうけど、探すの面倒だな…。でも何度やってもincorrect。大文字にしてなかったりそもそも抜き取るアルファベットが違うあんどあり、諦めて他の方のwriteupをみました。解く方向性は分かったからいいよね。

picoCTF{KODIAK_ALASKA}

rsa-pop-quiz 200pt

server connect問題かと思いきや同じ問題を解くわけじゃないので、別にターミナル開いてそこでpythonなど起動させ計算させましょう。ただ、このserverは時間が経つと切れてしまうので気を付けてください。繋ぎ直しても問題が変わることはないのでどこかにメモしておきましょう。

  1. p, qからnを求める。計算：n = p×q
  2. p, nからqを求める。計算：q = n/p (pythonだとn//p)
  3. nからp, qを求める。計算：しないで"N"を送る。次の問題に進んでくれる。
  4. p, qからφ(n)を求める。計算：φ(n) = (p-1)×(q-1)
  5. plaintext, e, nからciphertextを求める。計算：ciphertext = pow(plaintext, e, n)
  6. ciphertext, e, nからplaintextを求める。計算：しないで"N"を送る。次の問題に進んでくれる。
  7. p, q, eからdを求める。計算：d = inverse(e,(p-1)×(q-1) )
  8. p, ciphertext, e, nからplaintextを求める。計算：q = n//p, d = inverse(e,(p-1)×(q-1) ), plaintext = pow(ciphertext, d, n)

最後まで解くと以下のような文章が送られてきます。

If you convert the last plaintext to a hex number, then ascii, you'll find what you need! ;)

最後に求めたplaintextをlong_to_bytesするとflagになりました。

picoCTF{wA8_th4t$_ill3aGal..ode01e4bb}

college-rowing-team 250pt

この問題、Håstad's broadcast attackを使う問題です。初めてこの攻撃を扱う問題に触れました(自分で作ったことはあるけれど)。

この攻撃は中国剰余定理を用いてme を求めていきます。必要なのは公開鍵eの値と同じ数だけ異なるnがあり、暗号化する平文mとeは同値である必要があります。

中国の剰余定理 - Wikipedia

今回はe=3です。そして、flagの暗号文が3つあると成立します。

flag<n より flag3 < n1n2n3

flag3 > max(n1,n2,n3)

ここでn1で割ると余りがc1、n2で割ると余りがc2、n3で割ると余りがc3となる整数xを求めていきます。また、元々の暗号化方式より、xはflag3にも当てはまります。中国剰余定理では、n1n2n3以下ではこの解は1つしかありません。先の式で flag3 < n1n2n3 ということが分かっています。なので、このxを求めたらflag3と同値で3乗根を取れば平文となります。

flag3 < n1n2n3 となる必要があるので、異なるnがe個必要なんです。

中国剰余定理はsympyで実装されています。

今回はflagの他に3つの文章の暗号文が3つずつ渡されています。この12個の暗号文の内、3つがflagの暗号文なのでbrute forceして見つけていきます。

from sympy.ntheory.modular import *
import itertools
import gmpy2
from Crypto.Util.number import *

f = open("encrypted-message.txt")
a = f.readlines()
n_list = []
c_list = []
for i in range(0,len(a),4):
    n_list.append(int(a[i].split()[-1]))
    c_list.append(int(a[i+2].split()[-1]))

tmp = [i for i in range(len(n_list))]
for lis in itertools.combinations(tmp,3): # 0~11の内3つ選ぶのをbrute force
    candi = list(lis)
    m3,n = crt([n_list[candi[0]],n_list[candi[1]],n_list[candi[2]]],[c_list[candi[0]],c_list[candi[1]],c_list[candi[2]]]) #中国剰余定理
    m, ch = gmpy2.iroot(int(m3),3) # 3乗根が存在するか確認
    if ch: print(long_to_bytes(int(m))) #存在したら出力。flagと他の文章も出力される。

picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}

waves over lambda 300pt

今度は換字式暗号でした、良かった。quipquipに投げましょう。

frequency_is_c_over_lambda_agflcgtyue

miniRSA 300pt

このレベルが300pt!?となりました。e=3と小さく、me < nであるようなので、暗号文cの3乗根とってlong_to_bytesすればOKです。

import gmpy2
from Crypto.Util.number import *

f = open("ciphertext")
a = f.readlines()
n = int(a[1].split()[-1])
e = 3
c = int(a[-1].split()[-1])
m, ch = gmpy2.iroot(c,3)
assert ch
print(long_to_bytes(int(m)))

picoCTF{n33d_a_lArg3r_e_d0cd6eae}

b00tl3gRSA2 400pt

eがいつもの65537に比べ非常に大きいです。これはWiener's Attackですね。eが大きいと相対的にdが小さくなることで求められる攻撃ですが、細かい仕組みは未だに理解していません。eが大きいと出来る攻撃程度の理解でも良いと思います(自分の保身のため)。

GitHub - pablocelayes/rsa-wiener-attack: A Python implementation of the Wiener attack on RSA public-key encryption scheme.

AES-ABC 400pt

AESのECBモードで暗号化しています。それについて学びましょう。

暗号利用モード - Wikipedia

このwikiにも

ECBモードの欠点は、同じ鍵を用いた場合には、同じ平文ブロックを暗号化した結果の暗号文ブロックが常に同じとなることである。このため、データのパターンを隠蔽することができない。メッセージの機密性の保持には向かず、暗号化プロトコルにおける使用は推奨されない。同じ入力に対して常に同じ出力を返すことから、ECBモードは反射攻撃に対しても脆弱である。

ECBモードにおいてデータのパターンがどの程度残されるかを、ビットマップ画像の暗号化を用いて説明する。各々のピクセルの色情報を暗号化しても、暗号化処理後の画像にはピクセルごとの色情報のパターンが残留している。

とあるように、画像をECBモードで暗号化してもうっすら見えてしまうという欠点があります(wikiでのペンギンの絵、分かりやすい)。今回はそれを使います、つまり復号する必要はありません。

aes-abc.pyを見ると、16bytes毎読み取り一つ前のblockの値と足して25616 を越えるならそれで割った余りとするようにしていきます。なので、solverではその逆を行い復元していきます。

solverが上手くいかなかったのでこちらを参考にしました。

picoctf2019 writeup - ふるつき

f = open("body.enc.ppm","rb")
a0 = f.readline()
a1 = f.readline()
a2 = f.readline()
header = a0 + a1 + a2 #ppmファイルは最初3行がheaderとなり必要な値

block = []
while True:
    data = int.from_bytes(f.read(16),"big") #16bytesずつ読み込む
    if data == 0:
        break
    block.append(long_to_bytes(data))

blocks = []
blocks.append(block[0])

for i in range(1,len(block)):
    if i%10000 == 0: print(i)
    t = block[i]
    t = bytes_to_long(t)
    t1 = bytes_to_long(block[i-1])
    ans = (t-t1)
    if ans < 0: ans += UMAX
    ans = long_to_bytes(ans)
    while len(ans) % 16 != 0:
        ans = b"\0" + ans
    blocks.append(ans)


ct = b"".join(blocks)
with open("flag.ppm","wb") as fw:
    fw.write(header)
    fw.write(ct)

f:id:partender810:20210519205459p:plain
うっすら読める

picoCTF{d0Nt_r0ll_yoUr_0wN_aES}

b00tl3gRSA3 450pt

今度はeの値が普通ですが、nが簡単に素因数分解できました。しかし素数が3つ以上あるmultiple primes RSAですね。細かいことはオイラーの定理を用いて考えるのですが、ざっくり言うとφ(n) = (素数1 - 1)×(素数2 - 1) × ... ×(素数k - 1) です。あとはいつも通りに秘密鍵dを求めて終了です。

phi = 1
for pp in p: phi *= (pp-1) #pというリストにnの素因数を入れている
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

john_pollard 500pt

証明書と言えばopenssl。opensslと言えばコマンドが難しい。

OpenSSLコマンドの備忘録 - Qiita

$ openssl x509 -text -in cert -noout
Certificate:
    Data:
        Version: 1 (0x0)
        Serial Number: 12345 (0x3039)
        Signature Algorithm: md2WithRSAEncryption
        Issuer: CN = PicoCTF
        Validity
            Not Before: Jul  8 07:21:18 2019 GMT
            Not After : Jun 26 17:34:38 2019 GMT
        Subject: OU = PicoCTF, O = PicoCTF, L = PicoCTF, ST = PicoCTF, C = US, CN = PicoCTF
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                RSA Public-Key: (53 bit)
                Modulus: 4966306421059967 (0x11a4d45212b17f)
                Exponent: 65537 (0x10001)
    Signature Algorithm: md2WithRSAEncryption
         07:6a:5d:61:32:c1:9e:05:bd:eb:77:f3:aa:fb:bb:83:82:eb:
         9e:a2:93:af:0c:2f:3a:e2:1a:e9:74:6b:9b:82:d8:ef:fe:1a:
         c8:b2:98:7b:16:dc:4c:d8:1e:2b:92:4c:80:78:85:7b:d3:cc:
         b7:d4:72:29:94:22:eb:bb:11:5d:b2:9a:af:7c:6b:cb:b0:2c:
         a7:91:87:ec:63:bd:22:e8:8f:dd:38:0e:a5:e1:0a:bf:35:d9:
         a4:3c:3c:7b:79:da:8e:4f:fc:ca:e2:38:67:45:a7:de:6e:a2:
         6e:71:71:47:f0:09:3e:1b:a0:12:35:15:a1:29:f1:59:25:35:
         a3:e4:2a:32:4c:c2:2e:b4:b5:3d:94:38:93:5e:78:37:ac:35:
         35:06:15:e0:d3:87:a2:d6:3b:c0:7f:45:2b:b6:97:8e:03:a8:
         d4:c9:e0:8b:68:a0:c5:45:ba:ce:9b:7e:71:23:bf:6b:db:cc:
         8e:f2:78:35:50:0c:d3:45:c9:6f:90:e4:6d:6f:c2:cc:c7:0e:
         de:fa:f7:48:9e:d0:46:a9:fe:d3:db:93:cb:9f:f3:32:70:63:
         cf:bc:d5:f2:22:c4:f3:be:f6:3f:31:75:c9:1e:70:2a:a4:8e:
         43:96:ac:33:6d:11:f3:ab:5e:bf:4b:55:8b:bf:38:38:3e:c1:
         25:9a:fd:5f

真ん中付近にある”Modulus: 4966306421059967”を素因数分解してヒントの通りにflagを作ればOKです。

picoCTF{73176001,67867967}

unsolved

  • corrupt-key-1

以下のコマンドで秘密鍵を確認できる。

$ openssl rsa -text < private.key
RSA Private-Key: (1024 bit, 2 primes)
modulus:
    00:b8:cb:1c:ca:99:b6:ac:41:87:6c:18:84:57:32:
    a5:cb:fc:87:5d:f3:46:ee:90:02:ce:60:85:08:b5:
    fc:f6:b6:0a:5a:c7:72:2a:2d:64:ef:74:e1:44:3a:
    33:8e:70:a7:3e:63:a3:03:f3:ac:9a:df:19:85:95:
    69:9f:6e:9f:30:c0:09:d2:19:c7:d9:8c:4e:c8:42:
    03:61:08:34:02:9c:79:56:7e:fc:08:f6:6b:4b:c3:
    f5:64:bf:b5:71:54:6a:06:b7:e4:8f:b3:5b:b9:cc:
    ea:9a:2c:d4:43:49:f8:29:24:20:78:df:a6:4d:52:
    59:27:bf:d5:5d:09:9c:02:4f
publicExponent: 65537 (0x10001)
privateExponent: 0
prime1:
    00:e7:00:56:8f:f5:06:bd:58:92:af:92:59:21:25:
    e0:6c:be:9b:d4:5d:fe:af:e9:31:a3:33:c1:34:63:
    02:3d:4f:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00
prime2: 0
exponent1: 0
exponent2: 0
coefficient: 0
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIHeAgEAAoGBALjLHMqZtqxBh2wYhFcypcv8h13zRu6QAs5ghQi1/Pa2ClrHciot
ZO904UQ6M45wpz5jowPzrJrfGYWVaZ9unzDACdIZx9mMTshCA2EINAKceVZ+/Aj2
a0vD9WS/tXFUaga35I+zW7nM6pos1ENJ+CkkIHjfpk1SWSe/1V0JnAJPAgMBAAEC
AQACQQDnAFaP9Qa9WJKvklkhJeBsvpvUXf6v6TGjM8E0YwI9TwAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAgEAAgEAAgEAAgEA
-----END RSA PRIVATE KEY-----

nと素数pの上位半分bitsが分かるので、Coppersmithの定理を使うのだろう。ももテクさんの記事を丸パクリしたけど出来ない。となると分からない。

SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー

  • corrupt-key-2
  • Clouds

Cloudsはwriteupありましたが理解できず。writerはある論文を読んだとのことですが、「この論文を完全に理解できるほど賢くなかった」と言ってます。いやこの問題解けるんだから充分賢いよ。

CTFtime.org / picoCTF 2021 / Clouds / Writeup

AtCoder 入水しました！

初めて色変記事というものを書いていきます。多くの方に読んでもらえたらと思っています！特に入水を目指している方向けになればいいなと思っています！

f:id:partender810:20210517123732p:plain
ユーザ名の色変わったらしばらく見ていたいものである

f:id:partender810:20210517124035p:plain
初めて2年半で入水しました！

では、今までのことをつらつら書いていきます。最初は競プロをするまでのことを書くので、始めてからを知りたい方は読み飛ばして下さい。

AtCoderを始める前

高校生まで

プログラミングの「プ」の字も知らない。パソコンと言えば親に隠れてゲームの攻略法(ワザップとか)を調べる手段に過ぎない。それか情報の授業で触る程度。

今や中学生高校生がAtCoderをやっているのが珍しくなく、自分よりも全然rateが高い方を見るとすげえなぁって言葉しか出ない。例えまだ入水していない学生さんでもやってるだけですごいと本当に思う。

大学学部生時代 プログラミングと出会う

1年次に初めてプログラミングというものを知る。最初はC言語で、Hello worldってどの目線で言ってんねん、for文ってなんやと思っていました。プログラミングって新しそうっていう薄っぺらい知識から親は知らないだろうと話してみたら、なんと親父が知っていた。高校生の時も勉強を父から教わっていて、大学生になってもそれは変わらずC言語を教えてもらっていました(参考にならなくてすみません)。それから授業の中でも好きな方になっていきました。

2年次に挫折を味わう。Java言語の授業に遭遇するのである。オブジェクト指向ってなんやねん！！！そしてソフトウェア開発？的なグループワークでチェスを作る課題が一切分からず、他のチームメイトが99%行い自分は何もできないんだと悟る。
他にも2年次にはアルゴリズムの授業があり、ソートについてや最短経路探索、幅優先深さ優先などなど競プロにかなり役立つものばかりでしたが、当時の私はそんなに理解できていませんでした。

3年次は好転します。C言語の授業で競プロのようなオンラインジャッジシステムにグループで提出しろというのが毎週ありました。3人グループで自分以外女子、しかも二人とも可愛い。頑張らないわけがありません。積極的に課題に取り組み好感度爆上げ作戦を実行します。おかげでプログラミングの経験値は稼げました(他は察しろ)。

4年次、今の研究室に配属するとみんなpythonを使っていました。授業でpythonを扱ったことが無いので、なんでみんな知っているのか&よく使われているんだ、と壁を感じました。少し勉強したら使い方も分かり、今では本当によく使っています。でも、4年生になりたての時は授業で使ったことない言語を普通に使いこなしている先輩&同期が遠く見えました。

AtCoderを始めてみた

そんなこんなで大学院生になりました。やっと競プロを始めます。
競プロを始める前のプログラミングとの関わりとしては

といった感じです。

これからは下の図に沿って書いていきます。

f:id:partender810:20210517131546p:plain
全5部作

灰色期

昨年度同期みんなpythonを知っていてビビり散らかした経験から、他にも言語学んでおかねばとフリーランスの友達にどんな言語を学ぶと将来活きるか聞いたところ、golangとかいいかもねと言われ勉強します。ただ勉強するだけじゃつまらない上にできているかどうか分からないので、競技プログラミングをチュートリアルとしようと思いアカウントを作りました。コンテストには出ず、過去問をいくつか解いていました。灰色ではなく黒色期ですね(笑)

そこから問題を解いていくうちに、実際に自分はどれだけできるのだろうと気になりコンテストに2回出ます。最初はまさかのAGC。よく知らないまま参加したのでいつもより難しすぎる！！！となります。ただ初めて出たのでrateは少し上がります。2回目はちゃんとABCに出ます。その時の記憶が無いのですが、なんと1100パフォ。提出履歴観たらpythonで出してる。GO言語の勉強どこ行った(おそらくいい成績出したくて慣れてるpythonでやったのでしょう)。

そこから留学準備の為半年間お休みします。この時期のTOEFL勉強きつかった。よかったらその時の記事もあるので読んでみてください。

復帰後はGO言語でコンテストには出て、特にこれといって精進はしていなかったです。競プロのための勉強はしたくなかった…。1ヶ月しかいなかった留学中もやっており、その期間で入茶しました。

茶色期

帰国後、一番の転機が訪れます。研究室の新入生に黄coderがいたのです。茶色になりたてからするととても遠い存在ではありますが、彼に教えてもらう気満々でいたことは確かです。そして、緑coderもいました。彼とはいいライバルが続いております。

まだGO言語を使っており、灰色期に比べ反省や復習をよくした記憶です。挑んだけど解けなかった問題であったり、どうしてもO(N), O(N logN)に落とし込めない問題など、実装はともかくACへのプロセスは理解するようにしていました。それもこれも彼の指導ですね。

そしてコンテストもよほどのことが無い限り参加していました。上級者が身近にいるのは本当にありがたく、未熟者からすると解説を読んでも分からない近いできないということはよくありました。また解説にはないやりやすい方法など彼に聞いて教えてもらっていました。

一度、ABC-Eまでコンテスト中に解け、終了後FもACできた時がありました。5月過ぎの伸びているところです。それから緑にならいけるのでは？とモチベーションが上がりました。

そして、とうとう親父も競プロを始めました。親父はc++を使っており、同じアルゴリズムでもc++の方が断然速いことを目の当たりにした結果、GO言語を学びたいという初心を捨てrateを上げたいと目標を変えます。c++に完全移行した日あたりで入緑しました。

入緑後、即停滞期

この時期の停滞期は妥当と思っていました。まだまだ不慣れなc++の扱いであったり、緑になる目標が達成されたので上を目指す意識が低かったです。それでも色落ちした時は悔しかったですね。

ここらへんの時期から彼や、他の競プロerの勧めもあり、ちゃんと精進するようになりました。よく使っていたのはこのサイトですね。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

夏休み中や、ちょっと空いた時など解いていました。ワーシャルフロイド法やUnion-find、いもす法など知らないアルゴリズムが多かったので勉強になりました。今までろくに勉強してなかった分ですね。

また、競プロ用のアカウント(@ks37814026)を作って多くの競プロerの方と繋がれるようにしました。その方たちが詰まったところや良い問題などを共有して下さるので、勉強するのに困らなかったです！ 今もそのアカウントは続けているのですが、CTFの宣伝が多いですね(笑)

そして、精進の成果が出てきたのは肌寒くなった頃でした。

入水できるかも期

ある程度のアルゴリズムを覚え実装もできるようになると、だんだんrateが上がってきました。ABCではDが安定して解けるようになり自信も付いてきました。また、この時期からARCの頻度も増えてきてよく参加していました。ABCよりrateが上がる確率や幅が大きいことが多かったのでできるだけ出るようにしてました(ダメだった時の影響も大きいけど)。なので、ABC-Dが解けそうになってきた方はARCをお勧めします！

また速解きができるよう、スニペットが載っているサイトをブックマークしていました。他にも自作のライブラリなどを持っていると実装がすぐできると思います！特に数学的な問題はgoogleに頼る方がいいですね。

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita

巡回セールスマン問題をビットDPで解く (C++) - Qoosky

中には素因数は何種類あるか？って問題で2つ目のサイトをそのままコピペして最後だけ変えれば即ACという時もありました。コンテスト中は理解は後回しで、終わってから理解でも良いのかなと思っています(ペナ吐いたら考え物だけど)。

あと有難かったものとして、解けなかった問題の類題を彼が教えてくれる時がありました。リベンジという面でモチベにもなりますし純粋に経験値を多く得られます。上級者の知り合いを作るのが一番良い手かもしれません。

この時期はコンテスト参加すればほぼ毎回highestを更新していました。

この頃、鬼滅の刃は全く知らないのですがコンテスト前に紅蓮華を聞いて強くなれる理由を知ってました！(笑) しかし入水目前でまたしても停滞期が…

第二停滞期

この頃の心の叫びです。

色変前はよくあること、水パフォが全く出ないってことはないからいずれなるだろう、と思うようにしました。rateは下がってはいたのですが、大きく下がりはしなかったのでまだよかったです。

しかし、状況打破のためにこのようなことを始めました。

これは今でも続けています。思い立った時にやるよりかは、毎日少しでも競プロに触れることでアルゴリズムや実装法など忘れにくくなります。毎日時間を取るのは難しいですが、実装しなくても問題を考えることが重要だと思います。おそらくこのレベルになると、頭に浮かんだ方法を考える方が、それを実装する世にも遥かに難しいからです。私は毎日家に引きこもっているので時間は簡単に作れるのですが、そうでない方で停滞している方は是非やってみてください！

最近はこれをよくやっています。★4,5あたりは解けなくて解説を読むことが多いですが、よくある解法を頭に落とし込めるのは良い経験になります。

atcoder.jp

その結果もあって、週末二つのコンテスト(ABC, ARC)で150以上も上がり入水できました！ この日は誕生日でもあったのでWでお祝いでした！

個人的なコンテストの挑み方

コンテスト前

  • ルーティンを大事にする。コンテスト中は音楽を聴きながらやっているのですが、好きな音楽を最初にかける。紅蓮華効果は絶大だった(rate下がったらやめた)。
  • エディタの準備を怠らない。提出する時にそのコンテスト用のディレクトリにすぐアクセスできるようにしておく。
  • 好きなものを食べる！(揚げ物食べた日の調子はすごくいい)

コンテスト中

  • 時間的計算量をまず考える。N=105 だったらO(N), O(N logN)で解けるからその方法を考える。N = 1018ならO(1)で解ける。などなど
  • Nosubを考えない。考えると集中できなくなる。

コンテスト後

  • twitterで他の方の解説や解法を確認する

さいごに

ここまで読んでくださった方、ありがとうございます。もしよろしければ是非感想をリプなりしていただけると嬉しいです。色変記事書くのは初めてなので、こういった情報もあると良いよなどあれば是非教えてください！

入水が目標だったので入青は今のところあまり考えてないのですが、もっとモチベが上がれば頑張ってみようと思います。入青出来た際にはまた記事を書こうと思うので読んでいただければと思います！

dctf 2021 writeup

初心者用といいながら、ちゃんと難しいCTFでした。

dCTF

Result

f:id:partender810:20210517104257p:plain
Ranking

f:id:partender810:20210517104401p:plain
solves

Writeup

Misc

Encrypted the flag 100pt

Decrypted flag is not in exact format.
ファイル： EncryptedTheFlagIHave.png

f:id:partender810:20210516140325p:plain
EncryptedTheFlagIHave.png

5文字目と最後の文字(記号？)が"{}" に対応してそうです。このフォントを調べていくとこれがヒットしました。「alphabet font」でググって、根気強く探して見つかりました。

Languages in Star Wars - Wikipedia

dctf{mastercodebreaker}

Dragon 100pt

Hiding in plain sight.
ファイル：dragon.png

f:id:partender810:20210516141027p:plain
dragon.png

背景の白色部分に白文字が隠されているのか…？と色々調べましたが、各色を透過させたら出てきました。

WEBブラウザ上で簡単に透過PNG画像を作成できるツール | 無料で画像を加工できるサイト PEKO STEP

f:id:partender810:20210516141233p:plain
こんな感じ

dctf{N0w_Y0u_s3e_m3}

Don't let it run 100pt

PDF documents can contain unusual objects within.
ファイル：dragon.pdf

PDFを開いてプロパティを確認しますが特には分からず。困った時はstringsコマンド。

$ strings dragon.pdf

(中略)

/Type /Action
/S /JavaScript
/JS <766172205F3078346163393D5B2736363361435968594B272C273971776147474F272C276C6F67272C273150744366746D272C27313036387552596D7154272C27646374667B7064665F316E6A33637433647D272C273736383537376A6868736272272C2737313733343268417A4F4F51272C27373232353133504158436268272C2738333339383950514B697469272C27313434373836335256636E546F272C2731323533353356746B585547275D3B2866756E6374696F6E285F30783362316636622C5F3078316164386237297B766172205F30783536366565323D5F3078353334373B7768696C652821215B5D297B7472797B766172205F30783237353061353D7061727365496E74285F307835363665653228307831366529292B2D7061727365496E74285F307835363665653228307831366429292B7061727365496E74285F307835363665653228307831366329292B2D7061727365496E74285F307835363665653228307831373329292A2D7061727365496E74285F307835363665653228307831373129292B7061727365496E74285F307835363665653228307831373229292A2D7061727365496E74285F307835363665653228307831366129292B7061727365496E74285F307835363665653228307831366629292A7061727365496E74285F307835363665653228307831373529292B2D7061727365496E74285F307835363665653228307831373029293B6966285F30783237353061353D3D3D5F307831616438623729627265616B3B656C7365205F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D6361746368285F3078353736346134297B5F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D7D7D285F3078346163392C3078386439376629293B66756E6374696F6E205F30786128297B766172205F30783363366432303D5F3078353334373B636F6E736F6C655B5F3078336336643230283078313734295D285F307833633664323028307831366229293B7D76617220613D27626B706F646E746A636F7073796D6C78656977686F6E7374796B787372707A79272C623D2765787262737071717573746E7A717269756C697A70656565787771736F666D77273B5F30786228612C62293B66756E6374696F6E205F307835333437285F30783337646533352C5F3078313961633236297B5F30783337646533353D5F30783337646533352D30783136613B766172205F30783461633965613D5F3078346163395B5F30783337646533355D3B72657475726E205F30783461633965613B7D66756E6374696F6E205F307862285F30783339623365652C5F3078666165353433297B766172205F30783235393932333D5F30783339623365652B5F30786661653534333B5F30786128293B7D0A>
endobj

(中略)

変な16進数ありますね。でかい数字はとりあえずlong_to_bytes()

>>> x = 0x766172205F3078346163393D5B2736363361435968594B272C273971776147474F272C276C6F67272C273150744366746D272C27313036387552596D7154272C27646374667B7064665F316E6A33637433647D272C273736383537376A6868736272272C2737313733343268417A4F4F51272C27373232353133504158436268272C2738333339383950514B697469272C27313434373836335256636E546F272C2731323533353356746B585547275D3B2866756E6374696F6E285F30783362316636622C5F3078316164386237297B766172205F30783536366565323D5F3078353334373B7768696C652821215B5D297B7472797B766172205F30783237353061353D7061727365496E74285F307835363665653228307831366529292B2D7061727365496E74285F307835363665653228307831366429292B7061727365496E74285F307835363665653228307831366329292B2D7061727365496E74285F307835363665653228307831373329292A2D7061727365496E74285F307835363665653228307831373129292B7061727365496E74285F307835363665653228307831373229292A2D7061727365496E74285F307835363665653228307831366129292B7061727365496E74285F307835363665653228307831366629292A7061727365496E74285F307835363665653228307831373529292B2D7061727365496E74285F307835363665653228307831373029293B6966285F30783237353061353D3D3D5F307831616438623729627265616B3B656C7365205F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D6361746368285F3078353736346134297B5F30783362316636625B2770757368275D285F30783362316636625B277368696674275D2829293B7D7D7D285F3078346163392C3078386439376629293B66756E6374696F6E205F30786128297B766172205F30783363366432303D5F3078353334373B636F6E736F6C655B5F3078336336643230283078313734295D285F307833633664323028307831366229293B7D76617220613D27626B706F646E746A636F7073796D6C78656977686F6E7374796B787372707A79272C623D2765787262737071717573746E7A717269756C697A70656565787771736F666D77273B5F30786228612C62293B66756E6374696F6E205F307835333437285F30783337646533352C5F3078313961633236297B5F30783337646533353D5F30783337646533352D30783136613B766172205F30783461633965613D5F3078346163395B5F30783337646533355D3B72657475726E205F30783461633965613B7D66756E6374696F6E205F307862285F30783339623365652C5F3078666165353433297B766172205F30783235393932333D5F30783339623365652B5F30786661653534333B5F30786128293B7D0A
>>> long_to_bytes(x)
b"var _0x4ac9=['663aCYhYK','9qwaGGO','log','1PtCftm','1068uRYmqT','dctf{pdf_1nj3ct3d}','768577jhhsbr','717342hAzOOQ','722513PAXCbh','833989PQKiti','1447863RVcnTo','125353VtkXUG'];(function(_0x3b1f6b,_0x1ad8b7){var _0x566ee2=_0x5347;while(!![]){try{var _0x2750a5=parseInt(_0x566ee2(0x16e))+-parseInt(_0x566ee2(0x16d))+parseInt(_0x566ee2(0x16c))+-parseInt(_0x566ee2(0x173))*-parseInt(_0x566ee2(0x171))+parseInt(_0x566ee2(0x172))*-parseInt(_0x566ee2(0x16a))+parseInt(_0x566ee2(0x16f))*parseInt(_0x566ee2(0x175))+-parseInt(_0x566ee2(0x170));if(_0x2750a5===_0x1ad8b7)break;else _0x3b1f6b['push'](_0x3b1f6b['shift']());}catch(_0x5764a4){_0x3b1f6b['push'](_0x3b1f6b['shift']());}}}(_0x4ac9,0x8d97f));function _0xa(){var _0x3c6d20=_0x5347;console[_0x3c6d20(0x174)](_0x3c6d20(0x16b));}var a='bkpodntjcopsymlxeiwhonstykxsrpzy',b='exrbspqqustnzqriulizpeeexwqsofmw';_0xb(a,b);function _0x5347(_0x37de35,_0x19ac26){_0x37de35=_0x37de35-0x16a;var _0x4ac9ea=_0x4ac9[_0x37de35];return _0x4ac9ea;}function _0xb(_0x39b3ee,_0xfae543){var _0x259923=_0x39b3ee+_0xfae543;_0xa();}\n"

見つかりました

dctf{pdf_1nj3ct3d}

Powerpoint programming 200pt

A login page in powerpoint should be good enough, right?
Flag is not in format. DCTF{ALL_CAPS_LETTERS_OR_NUMBERS}
ファイル：chall.ppsx

開くとパワポのスライドショーが始まります。WaniCTFでも似たようなのがありました。

$ mv chall.ppsx chall.ppt

これで開くと、どうやらアニメーションでflagを出すようです。プレビューで見れなかったので、アニメーションウインドウから頑張って読みます。

f:id:partender810:20210516142802p:plain
Rectangle xx をクリックすると該当ボタンの左の稲妻マークが光る

これで一つ一つflagを確認していきました。

DCTF{PPT_1SNT_V3RY_S3CUR3_1S_1T}

Crypto

Julius' ancient 100pt

I found this Ancient Roman papyrus. Could you decypher it for me?
ファイル：flag.txt

rq7t{7vH_rFH_vI6_pHH1_qI67}

dctf -> rq7t になっているようです。t->7以外は12文字シフトさせているようです。"abc-xyz0123456789"とすれば、tを12文字シフトすると7になります。あとは大文字アルファベットですね。"A-Za-z0-9"でシフトすればOKです。

dctf{th3_d13_h4s_b33n_c4st}

Just Take Your Time 200pt

Let's go. In and out. 2 second adventure.
nc dctf-chall-just-take-your-time.westeurope.azurecontainer.io 9999
Hint : While this may not be pwn, its tools may still be quite handy.
ファイル：just-take-your-time.py

まずはかけ算をやれと言われるので普通に掛け算をして積を送ります。

次に、DES3で暗号化されたものを渡されるので復号したものを送ります。ここで3回までチャンスがあります。keyはその時のUNIXTIMEなので掛け算が終わった後すぐUNIXTIMEを取り復号していきます。うまくkeyが設定されると16進数の平文が手に入りそれを送るとflagが手に入ります。

HOST, PORT = "dctf-chall-just-take-your-time.westeurope.azurecontainer.io", 9999
s, f = sock(HOST, PORT)
read_until(f)
recv_m = read_until(f).split()
x = int(recv_m[0])*int(recv_m[2])
s.send(str(x).encode()+b"\n")
tim = int(time()) #UNIXTIMEの取得
print(read_until(f))
enc = read_until(f).strip()
print(enc)
print("time: ",tim)
for _ in range(3):
    key = str(tim).zfill(16).encode("utf-8") #keyの設定
    cipher = DES3.new(key, DES3.MODE_CFB, b"00000000")
    pt = cipher.decrypt(long_to_bytes(int(enc,16)))
    s.send(pt+b"\n")
    recv_m = read_until(f).strip()
    if "guess" in recv_m:
        #はずれ
        tim += 1
    else:
        #あたり
        break 
while True: print(read_until(f))

dctf{1t_0n1y_t0Ok_2_d4y5...}

A Simple SP Box 300pt

It's just a simple SP-box, 150 tries should be enough for you.
nc dctf1-chall-sp-box.westeurope.azurecontainer.io 8888
ファイル：sp_box.py

sp_box.pyを読んでいきます。まずflagの暗号文を送り、任意の平文を暗号化してくれるようです。

では暗号化アルゴリズムを見ていきます。

まず、roundsを決定します。flagの長さによって決まります。

rounds = int(2 * ceil(log(len(message), 2)))

次に変換表を作ります。変数ALPHABETには、大文字小文字アルファベットと数字、いくつかの記号が入っており合計78文字です。これをシャッフルし元あった場所と比較して変換表を生成します。

そして平文から変換表により文字を置き換え、次に順番を変えます。暗号文を前半後半に分け、[後半の0文字目], [前半の0文字目], [後半の1文字目], [前半の1文字目],...という風にします。これをrounds回行いますが、順番変えは最終roundは行いません。

解法として、まずALPHABETの文字を一文字ずつ暗号化してもらいます。暗号化の制限は150回なので回数は大丈夫です。暗号化の際に平文長が奇数だと後ろに"_"(アンダースコア)が付きます。"a", "b"を送ると、2文字の暗号文が返ってきます。どちらも先頭文字は一致するので"_"の暗号文だと分かります。しかし、平文長が1(2)だとroundsは2になります。なので先頭文字は"_"を2回変換させたもの、もう一文字は送った文字を2回変換させたものとなります。ここで1回変換させた文字は知る必要がありません。roundsはかならず偶数になるからです。

あとはdecrypt関数を作り、全ての文字を2回変換させた文字から暗号文をflagに戻していきます。ここで、変換表は一つのループになるまでサーバに繋ぎ直します("a"->"b"->"a"とならない)。その方がやりやすいためです。その確率は1/78なので、結構待つ必要があります。

def decrypt(enc,table):
    message = list(enc)
    pt = list(enc)
    rounds = int(2 * ceil(log(len(message), 2)))
    for r in range(rounds-1,-1,-1):
        if r < rounds-1:
            ppt = ["a" for _ in range(len(pt))]
            for j in range(len(pt)):
                if j%2 == 0:
                    ppt[j] = pt[len(pt)//2+j//2]
                else:
                    ppt[j] = pt[j//2]
            
            pt = ppt
        ppt = []
        for j in range(len(pt)):
            ppt.append(table[pt[j]])
        pt = ppt
    return ''.join(pt)


ALPHABET = ascii_letters + digits + "_!@#$%.'\"+:;<=}{"
l = len(ALPHABET)
#HOSTはIPアドレスでも可
HOST, PORT = "dctf1-chall-sp-box.westeurope.azurecontainer.io", 8888
while True:
    s, f = sock(HOST, PORT)
    read_until(f)
    enc = read_until(f).strip()
    b1 = []
    bef = "a"
    #b1.append(bef)
    for i in tqdm(range(l//2)):
        read_until(f,"> ")
        s.send(bef.encode()+b"\n")
        read_until(f)
        recv_m = read_until(f).strip()
        b1.append(recv_m[-1])
        bef = b1[-1]

    
    print("b1")
    print(b1)
    if len(list(set(b1))) != l//2:
        print("NG b1 :",len(list(set(b1))))
        s.close()
        continue
    if b1[-1] != "a":
        print("NG b1 because the last is not a")
        s.close()
        continue

    b2 = []
    for x in ALPHABET:
        if x in b1: continue
        bef = x
        print("b2",x)
        break
    for i in tqdm(range(l//2)):
        #bef = b2[-1]
        read_until(f,"> ")
        s.send(bef.encode()+b"\n")
        read_until(f)
        recv_m = read_until(f).strip()
        b2.append(recv_m[-1])
        bef = b2[-1]

    
    print("b2")
    print(b2)
    if len(list(set(b2))) != l//2:
        print("NG b2 :",len(list(set(b2))))
        s.close()
        continue

    rev_table = {}
    for j in range(len(b2)):
        rev_table[b1[j]] = b2[j]
        rev_table[b2[j]] = b1[(j+1)%len(b1)]
    table = {}
    for k,v in rev_table.items():
        table[v] = k
    print(decrypt(enc,table))

    s.close()
    break

たまに上手くいきました。

dctf{S0_y0u_f0und_th3_cycl3s_in_th3_s_b0x}

This one is really basic 300pt

The answer to life, the universe, and everything.
ファイル：cipher.txt

中を見るとbase64のようです。復号してみるとまた同じような文字構成に加えて語尾が"="です。無限にdecryptして、"dctf{"が出てきたら終了です。得点の割には簡単でした。

import base64
f = open("cipher.txt","rb")
a = f.readline().strip()
while True:
    a = base64.b64decode(a)
    if b"dctf{" in a:
        print(a)
        break

dctf{Th1s_l00ks_4_lot_sm4ll3r_th4n_1t_d1d}

Problems & Solver

GitHub - ksbowler/dctf_2021

DawgCTF 2021 writeup

解けそうで解けなくて、解法見て解けるか！！！ってなった。

DawgCTF 2021

Results

f:id:partender810:20210509134630p:plain
久しぶりの2桁順位！

f:id:partender810:20210509134723p:plain
あと数問解きたかった

Writeup

Misc

DawgCTF Discord 5pt

Please join the DawgCTF Discord using the link below:

https://discord.gg/TbJQXJb6

You can use it for discussing challenges, getting assistance from challenge authors, and networking with our sponsors! The flag for this challenge is located in the #flags channel.

開催前からflagが見えてた…。

DawgCTF{3nj0y_th3_c0mp3t1t10n!}

Two Truths and a Fib 100pt

Can you catch the fibber?
nc umbccd.io 6000

3つの数字が渡されて、その内一つだけあるフィボナッチ数を答えればOKです。

時間制限があるので、毎回フィボナッチ数列を計算してる暇はありません。サーバに繋ぐ前に計算しておきましょう。

def fibo(n):
    fib = [0,1]
    for i in range(2,n):
        x = fib[i-1] + fib[i-2]
        fib.append(x)

    return fib

fib = fibo(10000)
#print(fib)
#HOSTはIPアドレスでも可
HOST, PORT = "umbccd.io", 6000
s, f = sock(HOST, PORT)
for _ in range(10): print(read_until(f))
cnt = 0
for i in range(100):
    recv_m = read_until(f).split()
    #print(recv_m)
    a = int(recv_m[0][1:-1])
    b = int(recv_m[1][:-1])
    c = int(recv_m[2][:-1])
    #print(a,b,c)
    #print(read_until(f,">> "))
    if a in fib: s.send(str(a).encode()+b"\n")
    elif b in fib: s.send(str(b).encode()+b"\n")
    else: s.send(str(c).encode()+b"\n")
    for _ in range(2): read_until(f)
    cnt += 1
    print(cnt)

while True: print(read_until(f))

DawgCTF{jU$T_l1k3_w3lc0me_w33k}

Crypto

Really Secure Altgorithm 150pt

I like my e's like I like my trucks: big and obnoxious
ファイル：reallysecure.txt

n: 1063494238636905330671898279123020701722241177838742822812173978727720269828464796177466331816675300997219760473399150899338190503499441304612339501295713174906319744094945565844664372365921409430229356934682156557249826723147031652843433859344718768493183522524995480377138743798310313783408725321419870843554822150601536373735923419276343616677440442774544203945706641152517137477442684440329779076981535293867470891276594740058202983415251883426242386508849130959905432961654910957147313116759921173654729071152981682554792584462863534617943384988632032130835087976957452863581161399454295389753849954195624356779281196493728732643445649356033158461867533398892265000228558146288424480232820613034689816560319929705959290376265550914058448343308161173100473161643834475548888676356572581129193395124610558172636505697071928778350452726229098387020587814634712035171712313035012109421792643188405752849278190287414108308734638519593282032082768153331276317440224645157072560878195004847185217741752846484430459047014205368551175641186962966731731946128786111994668528579102737764964521437485037695161775036622411218739549286577109028626220150452705854596994751235894610227300222070678106023292138580496517177268042770934391185798181598618563332872419401223903806812404310665174941843727792999745655534108889130325189241267039092501129173520194489329592776789648244263220437261594447066833175026748830694496235756029688061559449109400248449366143822446893851310444152168531390880512280359096438303124398155397910138799660941243464476642041104225318910175143988510614445494598098558426300612294667831401095538851181871031466580808942102239297182977785401087460226345045290147371931284725756179151791539310603340196586480494033673522637677423221202352493653286430691931273676649062037570851083535722738207802574643773975006788646467981693396925922930573766914743566111012462215653872417726475122775377641591778444141816733462035690735543990556767891443301312941168828619850007793197693295002346977318117653857994731382292035666024397790972920502626243999541832942059274728220802530163223188484361653845185336386588669397688474323385816925410493569923865462650449548121898936835205060632513390578074550881170405889665319159308800795056447244869407145217360018494614236328487464266591617854909647808315406639117270321158016494893469025866752746911948790708005075752364953010067274475470453957941422189404716860354111166203043679764568407375052809648827400302926099178569
e: 322080206518256091443899533297838582806903462189212623492459529527398362853578807723331748892091281476489691674322396825893568981731186597175657851460964692083587224231830304595753200276915353388440323973696723177120007866661510911934423352216586106031397002127519163858107192766128665700540985814443511274004469695128927172454976219787146706562954392698315026949257322529441349029783228167181158744356828575460114272675952388130344874175195393881248661753342888300368969470477541152888408256683251028110005741172636776279619483668723660512026112365800539035538500635904281702733475127339140385714006560153071610279780303018848372325359598739283968138816333125764253403325773002607652913882484078902775827169048401031393263955166695217841400017855979724317225872294531492451624247032809524082714281043873127461832051383511298796820369453358960824162684362741938604084210435623099328622028419710290325683380378726085007158903982932912214314158223921219724759717266136246703830446993309980595073110001804483058339461412460693911416430728558495048873597685942089531373734578638349738930086910038003088294940942692030998047041393152747526278088574238755027474019265539054527491401757165011505470582647900401492273402847703170162847259159161319094910753659832147964969052296859561769298825881593753592121708897035728873795159475926749806998737812501868665513946666352941497086651818553871606417281352599234688183547212675353626023151426982640664474136377374110023532481101565870359846621748326349516467938614155834462639061592390266451169971250010491497379073868786106821570448253182042906240682833067783409574735400739329311810053094530811477002973464432651755811246151509011287858077298295987954915889199100328695730233096226912526329144478198121096489396083876129542516602969866961376423685647767885680559757094208574124411496017291060228388949556065235333802142865557844913535276572535282671404020237763405558477020152910105019008364237315330047605257380696367871417207254833979064342650664181309067142909106945469319731754805506564282047041605728503555870882010025649797753726253285119740979484849951129514070748168270413416940958393138417596025358589062839735425553556206423183484639265605269615685651949641759227283257819425264608389110223455267792764547470141745830149226062457331548317230637497633273069300415564503833751637575125936072041989787691982221885384446295804003751739608564016981200019839941768866474797817202494560129096305497153712068566001154013937
c: 329889278578044016824313741527705229624826354380113199851837764563746872233807021113693371778072747023303193661391256917654673579748983619101229337776995574989101525295578632981918777232038222679949264372167418981038519164359046193397794833575692294838270919137212503594644756884879905102382013616716795766055806380675079122193261937202152727372307035197702671407008933906723580158843896939160889881874945976423829414877735269690727711347872615864084627631956403177338185780100778564548976884299086453421725163428017908949325966904530291069025584097022695816511626589485257615664532774194555809017763622197728156453680059300808277471558450818004384751746190317910501772671219117514746584045928056487904112720801176609889740173288130073788687010544220250814378467249611243953690831406523455960639957029937819775398561228599467536715020954136970283137688613486109370883547218314163119613810764259334933209435078926856747403933578685724271075988136268967520808025339001863614193092075106995811355116213778057037256625729238040020810096266917394213617319914026291093309897483557317625696133298013326746629673265558468135602690674704939910172338556035967840157228859997765219241095551758253889312610691956445984657535082546460420349808372702307807697037778668585720318640246334216650054353036505301550387620089144331383076791604944171531121861009872807022569971425034887955393207445086587528972631782104261610625226982484798915695532492666822649105680868782554501246818156815043534857204078057748607289822387462529373683511672270708474273078574153649263666927268413520984191265086647728912692418609093325194826161869428270138209430215739290181617579745939639392608498596400274014103435747462262045586624613109970954762445247628187031774393639286689201449970646288560996969456145518290732375783779950601901268751888374247634804346090070762202809312421725537938059723148831745384765961875359917754708570262909323774973728101735046489385116839098154905761289565030660932858839402457684704605894701939226586411257561719440368089980555960049063794123068432799043630558103308335378100690170353973384441557259766075780510887009923794374174414344793891145106172614982174022423725641446878993111773629101974963001417653742183922637679467704643683488299451383820099923197374567580088833681469257525555566554059017269673597621231456370183587051700138951722854738823417346171701112221512801669470086625272428387110466009926633732340715338158014022960380535876415340423270463298180055

eが大きいのでWiener's Attackですね。

あれ？出ない…。

他のWiener用のプログラムをいくつか試してみましたがダメ…。ダメ元でnをfactorDBに投げると平方数だったことが判明。あとはφ(n)の計算に気を付ければOKです。

φ(n) = φ(p2) = p×(p-1) (=n-p)

φ(n)とはnと互いに素になる自然数n以下の個数になります。今回はn=p×qではなく、n=p×pです。p2に互いに素にならないのはpの倍数だけでその個数はp個です。故にφ(n)=p×(p-1)です。

p = (省略)

assert p*p == n

phi = p*(p-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

DawgCTF{sm@ll_d_b1g_dr3am5}

The Obligatory RSA Challenge 200pt

Would you believe last year someone complained because we didn't have any RSA challenges?
ファイル：rsa.txt

n = 475949103910858550021125990924158849158697270648919661828320221786290971910801162715741857913263841305791340620183586047714776121441772996725204443295179887266030140253810088374694440549840736495636788558700921470022460434066253254392608133925706614740652788148941399543678467908310542011120056872547434605870421155328267921959528599997665673446885264987610889953501339256839810594999040236799426397622242067047880689646122710665080146992099282095339487080392261213074797358333223941498774483959648045020851532992076627047052728717413962993083433168342883663806239435330220440022810109411458433074000776611396383445744445358833608257489996609945267087162284574007467260111258273237340835062232433554776646683627730708184859379487925275044556485814813002091723278950093183542623267574653922976836227138288597533966685659873510636714530467992896001651744874195741686965980241950250826962186888426335553052644834563667046655173614036106867858602780687612991191030530253828632354662026863532605714273940100720042141793891322151633985026545935269398026536029250450509019273191619994794225225837195941413997081931530563686314944827757612844439598729054246326818359094052377829969668199706378215473562124250809041972492524806233512261976041
e = 65537
c = 402152770613351738677048755708324474554170176764376236321890073753918413309501149040535095814748232081435325267703210634002909644227960630174709988528642707754801508241021668904011536073077213912653767687757898322382171898337974911700337832550299932085103965369544431307577718773533194882182023481111058393084914882624811257799702110086578537559675833661097129217671283819819802719020785020449340858391080587707215652771744641811550418602816414116540750903339669304799230376985830812200326676840611164703480548721567059811144937314764079780635943387160912954258110357655610465371113884532394048454506662310124118115282815379922723111955622863507979527460353779351769204461491799016534724821436662464400182076767643570270346372132221638470790194373337215168535861219992353368908816850146790012604023887493693793270280077392301335013736929937492555191042177475011094313978657365706039774511145223613781837484571546154539993982179172011867034689022507760853121804219571982660393205589671062476958539437099789304135763092469236641459611160765143625998223459045923936551054351546033776966693997323972592968414107451804594097481574453747907874383069514662912314790514989026350766602740419907710031860078783498791071782013064557781230616536

情報がこれしかないのでとりあえずnを素因数分解してみます。これも平方数でした。先の問題と同じですね。

先の問題、他にも方法があったのかな？

DawgCTF{wh0_n33ds_Q_@nyw@y}

TrashChain 250pt

It seems that my problems with hashing just keep multiplying...
nc umbccd.io 3100
ファイル：trashchain.py

chains[0]に値1つ、chains[1]に値4つ入れるとします。それぞれ、v0, v11, v12, v13, v14とすると以下の式が成り立つ時、Hash値が同じになりFLAGがもらえます。

(v0+1)B mod A = (v11+1)B × (v12+2)B × (v13+3)B × (v14+4)B mod A

ここで左辺を24 = 16になるようv0を調整します。右辺を2×2×2×2になるようv1*を調整します。まず左辺について考えていきましょう。

16φ(A)+1 = 16 mod A がオイラーの定理より成り立ちます。k×B = 1 mod φ(A)とすると、
16kB = 16 mod A となります。故に、(v0+1) = 16k mod Aなのでv0を求められました。

v1*に関しても、2φ(A)+1 = 2 mod A を利用して求めます。

ここでtrashchain.pyの48行目のif文より、v0がどのv1*よりも大きい場合弾かれてしまいます。なので、弾かれたら24 → 34と変えそのif文が通るまで試して終了です。

A = 340282366920938460843936948965011886881
B = 127605873542257115442148455720344860097
a1 = 18446744073709551533
a2 = A//a1
assert a1*a2 == A
phia = (a1-1)*(a2-1)
k = inverse(B,phia)
#HOSTはIPアドレスでも可
cnt = 2
while True:
    HOST, PORT = "umbccd.io", 3100
    s, f = sock(HOST, PORT)
    for _ in range(8): print(read_until(f))

    #phase1
    print(read_until(f))
    print(read_until(f,"> "))
    x = cnt**4
    t = pow(x,k,A)
    t -= 1
    s.send(str(t).encode()+b"\n")
    t += 1
    assert pow(t,B,A) == x

    print(read_until(f,"> "))
    s.send(b"done\n")

    #phase2
    print(read_until(f))
    temp = pow(cnt,k,A)
    for i in range(4):
        temp -= 1
        print(read_until(f,"> "))
        s.send(str(temp).encode()+b"\n")

    print(read_until(f,"> "))
    s.send(b"done\n")
    recv_m = read_until(f).split()
    print(recv_m)
    if "smallest" in recv_m:
        s.close()
        cnt += 1
    else:
        break 

while True: print(read_until(f))

DawgCTF{We1rd_RSA_2nd_Pre1m4g3_th1ng}

Unsolved

チャレンジしたけど解けなかった問題をご紹介します。

Crypto

cookin the ramen 50pt

Apparently we made cookin the books too hard, here's some ramen to boil as a warmup: .--- ...- ...- . ....- ...- ... ..--- .. .-. .-- --. -.-. .-- -.- -.-- -. -... ..--- ..-. -.-. ...- ...-- ..- --. .--- ... ..- .. --.. -.-. .... -- ...- -.- . ..- -- - . -. ...- -. ..-. --- -.-- --.. - .-.. .--- --.. --. --. ...-- ... -.-. -.- ..... .--- ..- --- -. -.- -..- -.- --.. -.- ...- ..- .-- - -.. .--- -... .... ..-. --. --.. -.- -..- .. --.. .-- ...- ... -- ...-- --.- --. ..-. ... .-- --- .--. .--- .....

恐らくモールス信号なのでしょう。

JVVE4VS2IRWGCWKYNB2FCV3UGJSUIZCHMVKEUMTENVNFOYZTLJZGG3SCK5JUONKXKZKVUWTDJBHFGZKXIZWVSM3QGFSWOPJ5

ここから分からん…。

結果、モールス信号 → Base32 → Base64 → Base58でした。こんな複雑なのに200以上のsolves…。

What the Flip?! 300pt

Hackers have locked you out of your account! Fortunately their netcat server has a vulnerability.
nc umbccd.io 3000
This netcat server is username and password protected. The admin login is known but forbidden. Any other login entered gives a cipher.

AESのCBCモードでの暗号化/復号です。

まず任意の文字列を暗号化してくれますが、"admin&password=goBigDawgs123"が含まれる文字列だけは暗号化してくれません。

次に、任意の文字列を復号してくれます。unhexlifyされるよう16進数で送る必要があります。復号後、平文に"admin&password=goBigDawgs123"が含まれていたらflagを表示してくれます。

CBCモードなのでPadding Oracle Attackなのかなといつものサイトで勉強。CTF4年目にしてようやく理解できた気がする。けどまあ、今回は復号後の平文を教えてくれないから無理かな？

p1 = "admin&password=g", p2 = "oBigDawgs123\x04\x04\x04\x04"としてenc(p2)を求めれば行けそうでした。p1に対するc1が分かれば、enc(p2) = c1p2で求まります。しかし、サーバに文字列を送る際に上手くいっていないようで(str->bytesで送っているので、もともとbytesは上手く送れない？)、FLAGは手に入りませんでした。考え方は合っていそうなのに。

keyとiv, randomと言っているのに毎回同じ値になっているのも気になる。

この問題のwriteupを探しています！みつけたら教えてください。

What the Flip?! - CTFs

byte flipping attackを利用して暗号文を作るようです。先頭16文字を犠牲にして後ろ28文字を"admin&password=goBigDawgs123"にします。

"admin&parsword=goBigDawgs123" で暗号化してもらい、得られた暗号文の"r"の16bytes前の部分をord("r")とord("s")でxorします。そうすると、rだった部分がsになり、flagがもらえます。

Problems&solver

GitHub - ksbowler/DawgCTF_2021