好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

picoCTF2021 [Cryptography] writeup

CTF picoCTF

2021年3月16日~3月30日（日本時間では3月17日~3月31日）に開催された中高生向けのCTF大会、picoCTFの[Crypto]分野のwriteupです。
その他のジャンルについてはこちらを参照

tech.kusuwada.com

Mod 26

Cryptography can be easy, do you know what ROT13 is? cvpbPGS{arkg_gvzr_V'yy_gel_2_ebhaqf_bs_ebg13_Ncualgvd}

cvpbPGSがpicoCTFのはずなので、差分をとってみる。

c -> p  13
v -> i  13
p -> c  13
b -> o  13

ROT13だ。CyberChef使ってばかりも何なので、プログラム組んで解いてみる。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import string

alphabets = string.ascii_lowercase
enc = "cvpbPGS{arkg_gvzr_V'yy_gel_2_ebhaqf_bs_ebg13_Ncualgvd}"

for c in enc:
    if c.isupper():
        print(alphabets[(alphabets.index(c.lower())+13)%26].upper(), end="")
    elif c.islower():
        print(alphabets[(alphabets.index(c)+13)%26], end="")
    else:
        print(c, end="")

実行結果

$ python rot13.py 
picoCTF{next_time_I'll_try_2_rounds_of_rot13_Aphnytiq}

Mind your Ps and Qs

In RSA, a small e value can be problematic, but what about N? Can you decrypt this? values

valuesファイルが配布されます。

Decrypt my super sick RSA:
c: 8533139361076999596208540806559574687666062896040360148742851107661304651861689
n: 769457290801263793712740792519696786147248001937382943813345728685422050738403253
e: 65537

nが小さいので何らかの方法で因数分解できそう。
factordbでnを因数分解してもらうと、できた👍

p = 1617549722683965197900599011412144490161
q = 475693130177488446807040098678772442581573

これで解けそう。
RSAの基本公式より、

n = p * q
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, n)

p,qが判明したので、これを計算してあげるだけである。

from Crypto.Util.number import inverse
from Crypto.Util.number import long_to_bytes

c = 8533139361076999596208540806559574687666062896040360148742851107661304651861689
n = 769457290801263793712740792519696786147248001937382943813345728685422050738403253
e = 65537
p = 1617549722683965197900599011412144490161
q = 475693130177488446807040098678772442581573

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

実行結果

$ python rsa.py 
b'picoCTF{sma11_N_n0_g0od_45369387}'

Easy Peasy

A one-time pad is unbreakable, but can you manage to recover the flag? (Wrap with picoCTF{}) nc mercury.picoctf.net 36449 otp.py

otp.pyが配布される。ワンタイムパスワードに関する問題らしい。

#!/usr/bin/python3 -u
import os.path

KEY_FILE = "key"
KEY_LEN = 50000
FLAG_FILE = "flag"


def startup(key_location):
    flag = open(FLAG_FILE).read()
    kf = open(KEY_FILE, "rb").read()

    start = key_location
    stop = key_location + len(flag)

    key = kf[start:stop]
    key_location = stop

    result = list(map(lambda p, k: "{:02x}".format(ord(p) ^ k), flag, key))
    print("This is the encrypted flag!\n{}\n".format("".join(result)))

    return key_location

def encrypt(key_location):
    ui = input("What data would you like to encrypt? ").rstrip()
    if len(ui) == 0 or len(ui) > KEY_LEN:
        return -1

    start = key_location
    stop = key_location + len(ui)

    kf = open(KEY_FILE, "rb").read()

    if stop >= KEY_LEN:
        stop = stop % KEY_LEN
        key = kf[start:] + kf[:stop]
    else:
        key = kf[start:stop]
    key_location = stop

    result = list(map(lambda p, k: "{:02x}".format(ord(p) ^ k), ui, key))

    print("Here ya go!\n{}\n".format("".join(result)))

    return key_location


print("******************Welcome to our OTP implementation!******************")
c = startup(0)
while c >= 0:
    c = encrypt(c)

まずは試しにつないでみる。

$ nc mercury.picoctf.net 36449
******************Welcome to our OTP implementation!******************
This is the encrypted flag!
551257106e1a52095f654f510a6b4954026c1e0304394100043a1c5654505b6b

What data would you like to encrypt?

flagもkeyも固定なので、encrypted flagも固定。flagの長さは32文字のようだ。

最初のstartup呼び出しでは、keyをflagの長さぶん切り取って、key xor flagを1文字ずつ実行して16進にした値をつなげたものが返却される。key[0:len(flag)]がわかれば解けそう。

次の encrypt() 関数呼び出しでは、初回は len(flag) を引数に呼ばれ、入力した値 ui と key[len(flag):len(flag)+len(ui)] のxorが返却される。
一回 key_location を50000まで回して0に持ってきてから既知の文字列uiを入力すればkey[0:32]がわかりそう。

localで試しながらスクリプト作った。

from pwn import *

host = 'mercury.picoctf.net'
port = 36449
KEY_LEN = 50000
FLAG_LEN = 32

r = remote(host, port)
r.recvuntil(b'This is the encrypted flag!\n')
enc_flag = str(r.recvuntil(b'\n\n').strip())[2:-1]
r.recvuntil('What data would you like to encrypt?')
r.sendline(b'A'*(KEY_LEN-FLAG_LEN))
r.recvuntil('What data would you like to encrypt?')
r.sendline(b'A'*FLAG_LEN)
r.recvuntil(b' Here ya go!\n')
xor_key = str(r.recvuntil(b'\n\n').strip())[2:-1]

li_xor_key = [(i+j) for (i,j) in zip(xor_key[::2],xor_key[1::2])]
li_key = []
for h in li_xor_key:
    li_key.append(int(h,16) ^ ord('A'))

li_enc_flag = [(i+j) for (i,j) in zip(enc_flag[::2],enc_flag[1::2])]
flag = ''
for h in li_enc_flag:
    flag += chr(int(h,16) ^ li_key[len(flag)])
print('picoCTF{' + flag + '}')

実行結果

$ python solve.py 
[+] Opening connection to mercury.picoctf.net on port 36449: Done
picoCTF{75302b38697a8717f0faee9c0fd36a57}

New Caesar

We found a brand new type of encryption, can you break the secret code? (Wrap with picoCTF{}) mlnklfnknljflfjljnjijjmmjkmljnjhmhjgjnjjjmmkjjmijhmkjhjpmkmkmljkjijnjpmhmjjgjj new_caesar.py

new_caesar.py が配布されます。

import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]

def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))
        enc += ALPHABET[int(binary[:4], 2)]
        enc += ALPHABET[int(binary[4:], 2)]
    return enc

def shift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 + t2) % len(ALPHABET)]

flag = "redacted"
key = "redacted"
assert all([k in ALPHABET for k in key])
assert len(key) == 1

b16 = b16_encode(flag)
enc = ""
for i, c in enumerate(b16):
    enc += shift(c, key[i % len(key)])
print(enc)

key, flagが不明。keyは親切なassert文により、一文字の[a-p]のいずれかということがわかる。keyはたかだか16通りなので総当りして、意味のある文になるのを見つける。
b16_encodeは、chrをordで10進数に直し、更に2進数に直した上で、上位4bitと下位4bitに分割、それぞれをalphabet(a~p)に当てはめて出力している。これの逆をやれば良い。
ちょっと汚いけど、リバース処理をしたソルバ。

import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]

cipher = "mlnklfnknljflfjljnjijjmmjkmljnjhmhjgjnjjjmmkjjmijhmkjhjpmkmkmljkjijnjpmhmjjgjj"

def b16_decode(cipher):
    plain = ""
    li_c = [(i+j) for (i,j) in zip(cipher[::2],cipher[1::2])]
    for c in li_c:
        u = '{:08b}'.format(ALPHABET.index(c[0]))[4:]
        l = '{:08b}'.format(ALPHABET.index(c[1]))[4:]
        plain += chr(int(u+l,2))
    return plain

def reshift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 - t2) % len(ALPHABET)]

for key in ALPHABET:
    shifted = ''
    for i, c in enumerate(cipher):
        shifted += reshift(c, key[i % len(key)])
    flag = b16_decode(shifted)
    print('[' + key + ']: ', flag)

実行結果

$ python new_caesar_solve.py 
[a]:  ËÚµÚÛµÌËÇÊÈÊÊÊËÇÉ
[b]:  ºÉ¤Éʤ»º¶¹·¹¹¹º¶¸
[c]:  ©¸¸¹sy{vwªx©{u¥t{wz¨w¦u¨u}¨¨©xv{}¥§tw
[d]:  §§¨bhjefgjdcjfifddlgejlcf
[e]:  qQqWYTUVYSRYUXUSS[VTY[RU
[f]:  v`@`FHCDwEvHBrAHDGuDsBuBJuuvECHJrtAD
[g]:  et_tu?_5723f4e71a0736d3b1d19dde4279ac03
[h]:  TcNcd.N$&!"U#T& P/&"%S"Q S (SST#!&(PR/"
[i]:  CR=RS=DCOB@BBBCOA
[j]:  2A,AB
1?1112>0   ,32>
[k]:  !01ûñóþÿð!óý-üóÿò ÿ.ý ýõ  !ðþóõ-/üÿ
[l]:  /
/ ê
àâíîïâìëâîáîììäïíâäëî
[m]:  ùÙùßÑÜÝÞÑÛ
                ÚÑÝÐÝ
                     ÛÛÓÞÜÑÓ
ÚÝ
ÈèÎÀËÌÿÍþÀÊúÉÀÌÏýÌûÊýÊÂýýþÍËÀÂúüÉÌ
[o]:  íü×üý·×½¿º»î¼í¿¹é¸¿»¾ì»ê¹ì¹±ììí¼º¿±é븻
[p]:  ÜëÆëì¦Æ¬®©ªÝ«Ü®¨Ø§®ª­ÛªÙ¨Û¨ ÛÛÜ«©® ØÚ§ª

意味のある単語になってそうなのが、keyが g のときの [g]: et_tu?_5723f4e71a0736d3b1d19dde4279ac03 なので、これがflag👍

Mini RSA

What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let's decrypt this: ciphertext

ciphertextが配布される。

N: 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e: 3

ciphertext (c): 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808147276605782889813772992918898400408026067642464141885067379614918437023839625205930332182990301333585691581437573708925507991608699550931884734959475780164693178925308303420298715231388421829397209435815583140323329070684583974607064056215836529244330562254568162453025117819569708767522400676415959028292550922595255396203239357606521218664984826377129270592358124859832816717406984802489441913267065210674087743685058164539822623810831754845900660230416950321563523723959232766094292905543274107712867486590646161628402198049221567774173578088527367084843924843266361134842269034459560612360763383547251378793641304151038512392821572406034926965112582374825926358165795831789031647600129008730

これはRSA暗号運用でやってはいけない n のこと #ssmjp のその6「eの値が小さすぎてはいけない」の "Low Public Exponent Attack" である。

e と n が共に小さく、 𝑚^𝑒 < 𝑛 のとき、 𝑐 の 𝑒 乗根を計算することで m が求まる。

picoCTF2019 miniRSA の過去問と同じで解けるかと思ったが、問題文の通り一捻り入っており、

(M ** e) is just barely larger than N

なのでこのままでは解けなくなっている。ヒントの4番目

You shouldn't have to make too many guesses

より、ある程度のguessが必要だが現実的な範囲内、と解釈し、cの計算の時に c % nで切り捨てられている nの倍数を計算時に復元してあげ、復号可能な組み合わせを探索することにした。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import gmpy2

n =  1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3
c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808147276605782889813772992918898400408026067642464141885067379614918437023839625205930332182990301333585691581437573708925507991608699550931884734959475780164693178925308303420298715231388421829397209435815583140323329070684583974607064056215836529244330562254568162453025117819569708767522400676415959028292550922595255396203239357606521218664984826377129270592358124859832816717406984802489441913267065210674087743685058164539822623810831754845900660230416950321563523723959232766094292905543274107712867486590646161628402198049221567774173578088527367084843924843266361134842269034459560612360763383547251378793641304151038512392821572406034926965112582374825926358165795831789031647600129008730

for i in range(10000):
    m, result = gmpy2.iroot(c+(i*n),e)
    if result:
        if m != 0:
            print(i, m)
            flag = bytes.fromhex(hex(m)[2:]).decode('ascii')
            print(flag)
            break

実行結果

$ python solve.py 
3533 1787330808968142828287809319332701517353332911736848279839502759158602467824780424488141955644417387373185756944952906538004355347478978500948630620749868180414755933760446136287315896825929319145984883756667607031853695069891380871892213007874933611243319812691520078269033745367443951846845107464675742664639073699944730122897078891901
                                                                                                        picoCTF{e_sh0u1d_b3_lArg3r_85d643d5}

👍

Dachshund Attacks

What if d is too small? Connect with nc mercury.picoctf.net 41508.

とにかくつないでみます。

$ nc mercury.picoctf.net 41508
Welcome to my RSA challenge!
e: 63458624470386156423199696862715691746005286495177035863754366089698777299318622671955776832166561996487028576836275296828473787221224630401865168699170495906170394664528376603328875915311653590070297925006216643196099592649097569417988473722477290450955130205757857869218106735572396455690523746562814803639
n: 97807483679156830952001576069338044848573751890578981751395630650857242125950221541800541318350066009352637420474871672623840902303717522374833523687869560802474547587258429658520015256386251697808588427230746703472367977709085752287817924283025056084446572458095896504947243249318838874037315088150018375281
c: 19188349983181674122765689614690899046106601997947648515974422120904456042112060249708984127578921951839420538572002402631486156351179528859980307293384335039033842606145245719045986147929354476967608260628904602830624991975391112245381374362057168974196156767170757497771117035121126443104281870619505794183

問題文より、dが小さい(==eが大きすぎる)ようなので、RSA暗号運用でやってはいけない n のこと #ssmjp のその7、「eの値が大きすぎてはいけない」時に有効な攻撃手法、"Wiener's Attack" が使えそう。

攻撃用ツールがでているので、使わせていただく。

GitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSA

import owiener
from Crypto.Util.number import *

e = 63458624470386156423199696862715691746005286495177035863754366089698777299318622671955776832166561996487028576836275296828473787221224630401865168699170495906170394664528376603328875915311653590070297925006216643196099592649097569417988473722477290450955130205757857869218106735572396455690523746562814803639
n = 97807483679156830952001576069338044848573751890578981751395630650857242125950221541800541318350066009352637420474871672623840902303717522374833523687869560802474547587258429658520015256386251697808588427230746703472367977709085752287817924283025056084446572458095896504947243249318838874037315088150018375281
d = owiener.attack(e, n)

if d is None:
    print("Failed")
else:
    print("Hacked d={}".format(d))

c = 19188349983181674122765689614690899046106601997947648515974422120904456042112060249708984127578921951839420538572002402631486156351179528859980307293384335039033842606145245719045986147929354476967608260628904602830624991975391112245381374362057168974196156767170757497771117035121126443104281870619505794183

plain = pow(c, d, n)
print(long_to_bytes(plain).strip())

実行結果

$ python solve.py 
Hacked d=8887310671537384659350505188702976397498729476686166734463197515980194602759
b'picoCTF{proving_wiener_3899149}'

No Padding, No Problem

Oracles can be your best friend, they will decrypt anything, except the flag's ciphertext. How will you break it? Connect with nc mercury.picoctf.net 33780.

接続してみます。

$ nc mercury.picoctf.net 33780
Welcome to the Padding Oracle Challenge
This oracle will take anything you give it and decrypt using RSA. It will not accept the ciphertext with the secret message... Good Luck!


n: 92818125790034579085583141554617823947754060867969745983559586969503150349817557539980827025353896297343780354926462576209207010762025425960920745956154778671003744564424626743122907118859519391040509062892779169151856423724140455638833306780173960561444851289535919053593380854281948801039452696358736707013
e: 65537
ciphertext: 39527826033615636604377826200224335356922968612424458056710959461578917295429517530821840863546667608195994451057956761214834426050623612940649224551563577697550531963913509871008502677145726075318803941197166671453316623943703389697972759669869125172667054345332271775354684908948648930128632725252118117323


Give me ciphertext to decrypt:

接続するたびに、異なるn,e,ciphertextが提示されます。これ毎回同じplaintext(=flag)から生成されているとすると、

RSA暗号運用でやってはいけない n のこと #ssmjp その9 "同一の平文を異なる n で暗号化した暗号文を与えてはいけない" に引っかかりそう。

この場合、Hastad's Broadcast Attack というのが使えるらしい。

同一の m を異なる n で暗号化した c が e 個得られたとき、中国人剰余定理を用いて m が求まる

…と思ったけど、e = 65537 なので非現実的だな…。

それより、n,e,cのセットを貰ったあと、同じ鍵で任意の暗号文を平文にしてくれるらしい。こっちの機能が使えそう。
全く同じcを突っ込むと、もちろん復号してくれないのだけど、それ以外に特に制約はないので、RSAの公式

m = pow(c, d, n)

から、c+nを突っ込んでも同じmが得られそう。
一応スクリプトを書いた。

from Crypto.Util.number import long_to_bytes
from pwn import *

host = 'mercury.picoctf.net'
port = 33780

def send(c):
    res = r.recvuntil(b'Give me ciphertext to decrypt: ')
    r.sendline(str(c).encode())
    res = r.recvuntil(b'Here you go: ')
    res = r.recvuntil(b'\n').strip()
    return res

r = remote(host, port)
r.recvuntil(b'n: ')
n = int(r.recvuntil(b'\n').strip())
r.recvuntil(b'e: ')
e = int(r.recvuntil(b'\n').strip())
r.recvuntil(b'ciphertext: ')
c = int(r.recvuntil(b'\n').strip())
print(n, e, c)
print('--------------------------------------')

res = send(c+n)
print(long_to_bytes(int(res)))

実行結果

$ 
^[[Akusuwada:No Padding, No Problem natsumi$ python solve.py
[+] Opening connection to mercury.picoctf.net on port 33780: Done
109518059885033552790562268435982206543266166731365252202251314563817269394187246381176392363473112346214778117805371498300306389630701083953371010734102577662247836754468548509365694040151713642249987611083655169604762498687161237257932426159586509998449644952054725148808704237223400617493771353900541976951 65537 101430806542831798032101780918508154651301284806750043462363012657797834750624063481376305965685154508833264515157007939879333887917900866853476950463900654418415694562271714236554893364474200228076180246377476959814481445229836840237834569282604872292366556600533069961756257498269917040215526554174138912318
--------------------------------------
b'picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_0801973}'

Play Nice

Not all ancient ciphers were so bad... The flag is not in standard format. nc mercury.picoctf.net 33686 playfair.py

playfair.py が配布されます。

#!/usr/bin/python3 -u
import signal

SQUARE_SIZE = 6


def generate_square(alphabet):
    assert len(alphabet) == pow(SQUARE_SIZE, 2)
    matrix = []
    for i, letter in enumerate(alphabet):
        if i % SQUARE_SIZE == 0:
            row = []
        row.append(letter)
        if i % SQUARE_SIZE == (SQUARE_SIZE - 1):
            matrix.append(row)
    return matrix

def get_index(letter, matrix):
    for row in range(SQUARE_SIZE):
        for col in range(SQUARE_SIZE):
            if matrix[row][col] == letter:
                return (row, col)
    print("letter not found in matrix.")
    exit()

def encrypt_pair(pair, matrix):
    p1 = get_index(pair[0], matrix)
    p2 = get_index(pair[1], matrix)

    if p1[0] == p2[0]:
        return matrix[p1[0]][(p1[1] + 1)  % SQUARE_SIZE] + matrix[p2[0]][(p2[1] + 1)  % SQUARE_SIZE]
    elif p1[1] == p2[1]:
        return matrix[(p1[0] + 1)  % SQUARE_SIZE][p1[1]] + matrix[(p2[0] + 1)  % SQUARE_SIZE][p2[1]]
    else:
        return matrix[p1[0]][p2[1]] + matrix[p2[0]][p1[1]]

def encrypt_string(s, matrix):
    result = ""
    if len(s) % 2 == 0:
        plain = s
    else:
        plain = s + "v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp"[0]
    for i in range(0, len(plain), 2):
        result += encrypt_pair(plain[i:i + 2], matrix)
    return result

alphabet = open("key").read().rstrip()
m = generate_square(alphabet)
msg = open("msg").read().rstrip()
enc_msg = encrypt_string(msg, m)
print("Here is the alphabet: {}\nHere is the encrypted message: {}".format(alphabet, enc_msg))
signal.alarm(18)
resp = input("What is the plaintext message? ").rstrip()
if resp and resp == msg:
    print("Congratulations! Here's the flag: {}".format(open("flag").read()))

# https://en.wikipedia.org/wiki/Playfair_cipher

ヒントは無しだけど、配布コードの最後にリンクが。
つないで動かしてみます。

$ nc mercury.picoctf.net 33686
Here is the alphabet: v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp
Here is the encrypted message: 4celvfdkoq5a0dx7pr40ifzctd8488
What is the plaintext message?

何回つないでも同じなので値は固定っぽい。コードを読まないとこれだけでは全然わからない。
コードの最後にあったリンクを見てみると、Playfair cipher という暗号を使っているっぽい。

Playfair cipher - Wikipedia

onlineのdecoderはいくつか存在するけど、どれもKeyがalphabetオンリーで成り立つ5×5のものを想定されている。今回は数字も込みの6×6なので、オンラインデコーダーはあまり使えないっぽい。

与えられたkey(alphabet)から作成されたsquareはこちら

[['v', '6', '0', 'u', 'f', 'm'],
 ['k', '7', 'e', 'd', 'g', '4'],
 ['z', '1', '3', 'h', '2', 'o'],
 ['y', 'q', 'a', '9', 'i', 'b'],
 ['5', '8', 'n', 't', 'w', 'x'],
 ['l', 'r', 's', 'c', 'j', 'p']]

このマトリクスに、平文を先頭から2文字ずつ渡しencrypt_pairで暗号化しています。
このペアがどう変換されるかは、上記のwikipediaが図示してくれるのでこれがわかりやすい。
暗号の性質上、逆変換は対象性があってとても簡単。
indexを進めて計算するところのみ逆に戻してあげればOK。
もとのスクリプトの encrypt_pair を書き換えた decrypt_pair はこちら。

def decrypt_pair(pair, matrix):
    p1 = get_index(pair[0], matrix)
    p2 = get_index(pair[1], matrix)

    if p1[0] == p2[0]:  # same row
        return matrix[p1[0]][(p1[1] - 1)  % SQUARE_SIZE] + matrix[p2[0]][(p2[1] - 1)  % SQUARE_SIZE]
    elif p1[1] == p2[1]:  # same col
        return matrix[(p1[0] - 1)  % SQUARE_SIZE][p1[1]] + matrix[(p2[0] - 1)  % SQUARE_SIZE][p2[1]]
    else:  # not same row or col
        return matrix[p1[0]][p2[1]] + matrix[p2[0]][p1[1]]

※ +を-に変えただけ

これを

dec_msg = decrypt_string(enc_msg, m)
# decrypt_string は encrypt_string と全く同じ

に突っ込んであげると、decryptされた平文がでてきます。
実行結果

$ python solve.py 
Here is the alphabet: v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp
Here is the encrypted message: 4celvfdkoq5a0dx7pr40ifzctd8488
Here is the decrypted message: dpksmue41bnyue84jlem2jhl9ux755

あとは、サーバーに接続して、得られたdecrypted messageを入れるとflagがもらえました。

$ nc mercury.picoctf.net 33686
Here is the alphabet: v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp
Here is the encrypted message: 4celvfdkoq5a0dx7pr40ifzctd8488
What is the plaintext message? dpksmue41bnyue84jlem2jhl9ux755
Congratulations! Here's the flag: 3a64de31e7b5acb6c87ae45050e187ee

※この問題はflagフォーマットではなくこのままが正解。問題文に書いてあるとおり。

Pixelated

I have these 2 images, can you make a flag out of them? scrambled1.png scrambled2.png

2枚の画像が配布されます。

f:id:kusuwada:20210331114801p:plain f:id:kusuwada:20210331114801p:plain

ヒントでこのページに案内されます。

Visual cryptography - Wikipedia

なんか画像を重ね合わせたりするっぽい？Stegano問かな。
gimpなどの画像編集ツールでいじってみたけれど、それっぽいものは見つからず。なんか良いツールはないかな？

画像を重ねる系のツールはいくつかあるけども、stegsolve を使ってみると、ADD の重ね方でflagが出た🙌

f:id:kusuwada:20210331114903p:plain

ちなみにこの問題、めっちゃ詰まってていろいろ試したけど解けず、でも正解者数めっちゃ多くておかしいな？と思っていたら、途中で元ファイルを破壊して上書きしてしまっていたらしい…。
再度DLし直したら一瞬で解けて脱力なう。こういうこともある。

New Vignere

Another slight twist on a classic, see if you can recover the flag. (Wrap with picoCTF{}) eljodmjdjcnfcdmgbleojbgngojkkdpimebgeigpdkjpmgngpfpgelemjoglghjd new_vignere.py

new_vignere.py が配布されます。問題文からして、ヴィジュネル暗号の変形版とかかな？

import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]

def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))
        enc += ALPHABET[int(binary[:4], 2)]
        enc += ALPHABET[int(binary[4:], 2)]
    return enc

def shift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 + t2) % len(ALPHABET)]

flag = "redacted"
assert all([c in "abcdef0123456789" for c in flag])

key = "redacted"
assert all([k in ALPHABET for k in key]) and len(key) < 15

b16 = b16_encode(flag)
enc = ""
for i, c in enumerate(b16):
    enc += shift(c, key[i % len(key)])
print(enc)

逆算していけば解けそう…。と思ったけど、keyが抜かれています。keyは[a-p]の文字の組み合わせで15文字以下のようなので、総当たりかな。
ただ、

Wrap with picoCTF{}

と書いてあるので、flag formatによる確認はできなさそう。16**15は結構な計算量だ。困った。
とにかく総当たりの空間を狭めたいので、条件を絞れないか色々見てみます。

  • key は [a-p]の文字の組み合わせで15文字以下
  • flag は [abcdef0123456789]の組合せで32文字

というのに加えて、flagが全部上記の条件に当てはまる場合、b16()関数の出力は一定のパターンしか無い。観測してみます。

import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]

def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))
        #print('binary: ' + binary)
        enc += ALPHABET[int(binary[:4], 2)]
        #print(enc)
        enc += ALPHABET[int(binary[4:], 2)]
        #print(enc)
    return enc

flag = "abcdef0123456789"
for c in flag:
    b16 = b16_encode(c)
    dis = ord(b16[0]) - ord(b16[1])
    print('[plain]: ' + c + ', [b16]: ' + b16 + ', [dis]: ' + str(dis))

実行結果

$ python test_range.py 
[plain]: a, [b16]: gb, [dis]: 5
[plain]: b, [b16]: gc, [dis]: 4
[plain]: c, [b16]: gd, [dis]: 3
[plain]: d, [b16]: ge, [dis]: 2
[plain]: e, [b16]: gf, [dis]: 1
[plain]: f, [b16]: gg, [dis]: 0
[plain]: 0, [b16]: da, [dis]: 3
[plain]: 1, [b16]: db, [dis]: 2
[plain]: 2, [b16]: dc, [dis]: 1
[plain]: 3, [b16]: dd, [dis]: 0
[plain]: 4, [b16]: de, [dis]: -1
[plain]: 5, [b16]: df, [dis]: -2
[plain]: 6, [b16]: dg, [dis]: -3
[plain]: 7, [b16]: dh, [dis]: -4
[plain]: 8, [b16]: di, [dis]: -5
[plain]: 9, [b16]: dj, [dis]: -6

ということで、encを2文字ずつun-shiftした時は、上記のどれかに当てはまるはず。
1,3,5,...と奇数文字目はshiftした時に必ずgかdになるので、これをうまく使えそう。

encの奇数番の文字だけ抜き出してみると

ejdjjncmbejggjkpmbegdjmnppeejggj

g,dとの距離をそれぞれ計算すると

$ python odd.py 
e   j   d   j   j   n   c   m   b   e   j   g   g   j   k   p   m   b   e   g   d   j   m   n   p   p   e   e   j   g   g   j   
-02 003 -03 003 003 007 -04 006 -05 -02 003 000 000 003 004 009 006 -05 -02 000 -03 003 006 007 009 009 -02 -02 003 000 000 003 
001 006 000 006 006 010 -01 009 -02 001 006 003 003 006 007 012 009 -02 001 003 000 006 009 010 012 012 001 001 006 003 003 006

なんか9文字ずつ周期性がありそう。

e   j   d   j   j   n   c   m   b   
-02 003 -03 003 003 007 -04 006 -05
001 006 000 006 006 010 -01 009 -02 

e   j   g   g   j   k   p   m   b   
-02 003 000 000 003 004 009 006 -05 
001 006 003 003 006 007 012 009 -02 

e   g   d   j   m   n   p   p   e   
-02 000 -03 003 006 007 009 009 -02 
001 003 000 006 009 010 012 012 001 

e   j   g   g   j  
-02 003 000 000 003 
001 006 003 003 006

それぞれの周期での文字との距離のandを取ると

[1] [2] [3] [4] [5] [6] [7] [8] [9]
-02 003 000 003 006 007 012 009 -02
001

key長は15文字以下なので、何処かで折り返しが入っているはず(key長が奇数)。index[5]で鍵を折り返してみます。

[1] [6] [2] [7] [3] [8] [4] [9] [5]
-02 007 003 012 000 009 003 -02 006 
001

1番目は絞れてないけど、これをkeyに設定して復号してみます。

import string
import itertools
import base64

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]

enc = 'eljodmjdjcnfcdmgbleojbgngojkkdpimebgeigpdkjpmgngpfpgelemjoglghjd'
key_arr = [1,7,3,12,0,9,3,-2,6]

def b16_decode(b16):
    dec = ""
    for i in range(len(b16)//2):
        b1 = "{0:04b}".format(ALPHABET.index(b16[i*2]))
        b2 = "{0:04b}".format(ALPHABET.index(b16[i*2+1]))
        dec += chr(int(b1+b2, 2))
    return dec

def unshift(c, k):
    t2 = ord(k) - LOWERCASE_OFFSET
    shift = ALPHABET.index(c)
    t1 = shift - t2
    f = ALPHABET[t1 % len(ALPHABET)]
    return f

key = ''
for k in key_arr:
    key += ALPHABET[k % len(ALPHABET)]
print(key)

b16 = ''
for i, c in enumerate(enc):
    b16 += unshift(c, key[i % len(key)])
plain = b16_decode(b16)
if all([c in "abcdef0123456789" for c in plain]):
    print(plain)

実行結果

$ python solve.py 
bhdmajdog
4b3e1bc357ed090810131aec5ce5bb92

これをflagフォーマットでwrapすると通りました👍

Double DES

I wanted an encryption service that's more secure than regular DES, but not as slow as 3DES... The flag is not in standard format. nc mercury.picoctf.net 3620 ddes.py

ddes.pyが配布されます。

#!/usr/bin/python3 -u
from Crypto.Cipher import DES
import binascii
import itertools
import random
import string


def pad(msg):
    block_len = 8
    over = len(msg) % block_len
    pad = block_len - over
    return (msg + " " * pad).encode()

def generate_key():
    return pad("".join(random.choice(string.digits) for _ in range(6)))


FLAG = open("flag").read().rstrip()
KEY1 = generate_key()
KEY2 = generate_key()


def get_input():
    try:
        res = binascii.unhexlify(input("What data would you like to encrypt? ").rstrip()).decode()
    except:
        res = None
    return res

def double_encrypt(m):
    msg = pad(m)

    cipher1 = DES.new(KEY1, DES.MODE_ECB)
    enc_msg = cipher1.encrypt(msg)
    cipher2 = DES.new(KEY2, DES.MODE_ECB)
    return binascii.hexlify(cipher2.encrypt(enc_msg)).decode()


print("Here is the flag:")
print(double_encrypt(FLAG))

while True:
    inputs = get_input()
    if inputs:
        print(double_encrypt(inputs))
    else:
        print("Invalid input.")

つないでみると

$ nc mercury.picoctf.net 3620
Here is the flag:
25431a80dfd29c6a9774955a162a6212c705a56d2927aeee9b23379dfdb2ccd55f2b4c21dd15be40
What data would you like to encrypt?

コードから、最初に提示されるのは double_encrypt したflagのようです。
ここから、好きな入力を同じ方法で暗号化した結果を返してくれます。

padでは入力文字列がblock長8の倍数になっていなかった場合、blankでpaddingする処理。…と思ったけど、よく見たら8の倍数のときは8個の' 'でpaddingされるみたい。
毎回暗号化につかう2つのkeyは6桁の数値からランダムに生成されます。

ヒントは

How large is the keyspace?

お、これはbruteforceが示唆されている？
配布されたコードに itertools がimportされているのも怪しすぎる。
短いinputを候補のkeyで暗号化してみて、結果が一致したらそのkeyが正解、ということにならんだろうか。

まずはlocalで動かしてみます。
自分が好きに入力できる値は、16進数かつbinascii.hexlifyしたあとにutf-8 decodeできる文字列。最初にpaddingされる。
いろいろ試してみて、偶数個の数字なら受け付けられることがわかった。以降は一番単純な00を使っていますが、特にそれ以上の理由はないです。

愚直に行くと、KEY1, KEY2を総当りで試すことになるのだけど、この2つのKEYの組み合わせとなると 10^{12} 通りになるわけで、まぁ普通のマシンだと数日かかる。もっと？
せめて鍵1つ分の総当りで良ければ、 10^{6} とおり、だいぶ現実的になる。むしろ遅くても(PCスペックによるけど)数分で終わりそう。

なんとか鍵1個分の総当りにならないかなーと念じながらソースコードを眺めたり動かしたりしていると、この Double の間の状態ってどうなるんだっけ？というのが気になりだした。
自分で入力したらencryptしてくれる値については、平文も暗号文も持っていることになるので、KEY1で平文を暗号化したものと、KEY2で暗号文を復号したものが一緒になる KEY1, KEY2 の組合せを探せばよいのでは？
計算量は 10^{6} 、メモリもこれくらいなら耐えられそう。

ということで、実装してみます。
まずは検証のためにKEYが4桁で動くか確認。

#!/usr/bin/python3 -u
from Crypto.Cipher import DES
import binascii
import itertools
import random
import string

def pad(msg):
    block_len = 8
    over = len(msg) % block_len
    pad = block_len - over
    return (msg + " " * pad).encode()

def generate_key():
    return pad("".join(random.choice(string.digits) for _ in range(KEY_DIGIT)))

def get_input(plain):
    try:
        res = binascii.unhexlify(plain.rstrip()).decode()
    except:
        res = None
    return res

def double_encrypt(m):
    msg = pad(m)

    cipher1 = DES.new(KEY1, DES.MODE_ECB)
    enc_msg = cipher1.encrypt(msg)
    cipher2 = DES.new(KEY2, DES.MODE_ECB)
    return binascii.hexlify(cipher2.encrypt(enc_msg)).decode()
    
def double_decrypt(key1, key2, c):
    enc_msg = binascii.unhexlify(c.encode())
    cipher2 = DES.new(key2, DES.MODE_ECB)
    dec_cip = cipher2.decrypt(enc_msg)
    cipher1 = DES.new(key1, DES.MODE_ECB)
    return cipher1.decrypt(dec_cip)

def single_encrypt(key, m):
    msg = pad(m)

    cipher = DES.new(key, DES.MODE_ECB)
    return cipher.encrypt(msg)

def single_decrypt(key, c):
    enc_msg = binascii.unhexlify(c.encode())
    
    cipher = DES.new(key, DES.MODE_ECB)
    return cipher.decrypt(enc_msg)

MODE = 0  # 0: local, 1: server

if MODE == 0:
    KEY_DIGIT = 4
    FLAG = open("flag").read().rstrip()
    KEY1 = generate_key()
    KEY2 = generate_key()
    print(KEY1, KEY2)
    print("Here is the flag:")
    ENC_FLAG = double_encrypt(FLAG)
    print(ENC_FLAG)
    PLAIN_INPUT = '00'
    PLAIN_INPUT = get_input(PLAIN_INPUT)
    ENC_INPUT = double_encrypt(PLAIN_INPUT)
    print('enc input: ' + ENC_INPUT)

elif MODE == 1:
    KEY_DIGIT = 6
    ENC_FLAG = '949b664d8336dc2ca74e3c9f3aa60659f8c2b48b06c20278a2842cb3e45e1bfcbd5f4ad74f5fbb1a'
    PLAIN_INPUT = '00'
    PLAIN_INPUT = get_input(PLAIN_INPUT)
    ENC_INPUT = 'a1060458408d2378'

dec1_list = {}
enc1_list = {}
for key in itertools.product(string.digits, repeat=KEY_DIGIT):
    key = pad(''.join(key))
    dec1_list[single_decrypt(key, ENC_INPUT)] = key
    enc1_list[single_encrypt(key, PLAIN_INPUT)] = key

print('------------[Finish creating Map]-------------')

for dk, dv in dec1_list.items():
    if dk in enc1_list.keys():
        ev = enc1_list[dk]
        print(b'KEY1: ' + ev)
        print(b'KEY2: ' + dv)
        print(b'Flag: ' + double_decrypt(ev, dv, ENC_FLAG))
        exit(0)

実行結果

$ python solve.py 
b'9661    ' b'5430    '
Here is the flag:
9f87e29670632fb03cc44031bc1c20dad08b2534f95e4a949a69c089ac0aab4b7224aff24a6ae97c
enc input: 6c580f92822fdf01
------------[Finish creating Map]-------------
b'KEY1: 9771    '
b'KEY2: 5531    '
b'Flag: picoCTF{this_is_test_local_flag}

おおー！flagが復号できています！
上記のスクリプトを MODE = 1 に切り替えて、一度 nc mercury.picoctf.net 3620 で下記のように各値を取得・スクリプトに設定して、再度流してみます。

$ nc mercury.picoctf.net 3620
Here is the flag:
949b664d8336dc2ca74e3c9f3aa60659f8c2b48b06c20278a2842cb3e45e1bfcbd5f4ad74f5fbb1a
What data would you like to encrypt? 00
a1060458408d2378

実行結果

$ python solve.py 
------------[Finish creating Map]-------------
b'KEY1: 177517  '
b'KEY2: 739797  '
b'Flag: 3b19585774c51cea36113c7b2c741a62

やったー！！！なんか取れた！！！٩(๑❛ᴗ❛๑)尸…ﾌﾗｸﾞ?
これは、問題文をよく読み返すと

The flag is not in standard format.

ということで、このまま(strになおして)投げると通りました！

(自分でinputする値の get_input 処理を忘れており、数日間 localのflagは取れるのにremoteのが取れない状態になっており、めっちゃDebugしてました。コードがわりかし綺麗なのは沢山Debugしたから！)