Attack All Around

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

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