picoCTF 2021 New Caesar Writeup

落ち着いて，粘り強く，１行１行解読すれば，そこまで難しい問題ではなかった。次のCTFでは，こういう取りこぼしをしないようにしたい。Cryptographyというよりpython力が全てなのでGeneral Skillsでいいと思う。

628 solvesと初心者には難問。これが出来れば中級者ってとこでしょうか。

Category:
Cryptography

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

Hints

1. How does the cipher work if the alphabet isn't 26 letters?
2. Even though the letters are split up, the same paradigms still apply

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)

Solution:

keyは？

ALPHABET = string.ascii_lowercase[:16]
assert all([k in ALPHABET for k in key])
assert len(key) == 1

上記から，key は ALPHABET = "abcdefghijklmnop" のいずれか1文字
作戦的には，後で16通り総当たりする

b16_encodeとは？

def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))    #２進数に
        enc += ALPHABET[int(binary[:4], 2)]  #上位4ビットをインデックスに
        enc += ALPHABET[int(binary[4:], 2)]  #下位4ビットをインデックスに
    return enc

b16 = b16_encode(flag)

この処理を通過すると文字長が２倍になり，使われる文字は全てALPHABETの範囲内になる

例えば "p" を b16_encode する
"p" は２進数で "01110000"
ALPHABET[7] -> "h"
ALPHABET[0] -> "a"

つまり
b16_encode("a") -> "ha"

次に shift

def shift(c, k):
	t1 = ord(c) - LOWERCASE_OFFSET              # c が "a" から何文字目か
	t2 = ord(k) - LOWERCASE_OFFSET              # key が "a" から何文字目か
	return ALPHABET[(t1 + t2) % len(ALPHABET)]  # ALPHABETの範囲内で入れ替え

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

この処理で初めてkeyが使われる

例えば shift("h", "b") でcallしたとする
t1 = 104 - 97 = 7
t2 = 98 - 97 = 1
(t1 + t2) % len(ALPHABET) -> 8
ALPHABET[8] -> "i"

new_caesar.py の解析がすんだので，ソルバーを作成する

solver.py

# coding: UTF-8
import string

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

enc ="kjlijdliljhdjdhfkfkhhjkkhhkihlhnhghekfhmhjhkhfhekfkkkjkghghjhlhghmhhhfkikfkfhm"

# 16通り総当たりするための配列を用意する
brute16 = []
for i in range(len(ALPHABET)):
    brute16.append("")

# print(brute16)

# shiftの逆
for k in range(len(ALPHABET)):
    for j in enc:
    
        # 取り出した enc 中の文字が ALPHABET の何番目か？
        index = ALPHABET.index(j)
        
        # indexは ( ord(c) - LOWERCASE_OFFSET + ord(k) - LOWERCASE_OFFSET ) % len(ALPHABET)
        # よって index - k + LOWERCASE_OFFSETが求める 値となる
        # ただkの方が大きいときもあるので，そのときは16加算する（剰余の逆）
        if(k > index):
            index += len(ALPHABET)
        brute16[k] += chr( index - k + LOWERCASE_OFFSET )

# print(brute16)

# b16_encodeの逆
for k in range(len(ALPHABET)):
    flag=""
    buf = brute16[k]
    for i in range(0, len(buf), 2):
        hi = ALPHABET.index(buf[i])
        lo = ALPHABET.index(buf[i+1])
        flag += chr( ( hi << 4 ) + lo )
    print("key= ", end="")
    print(ALPHABET[k], end="")
    print(" flag= ", end="")
    print(flag)

実行結果

>python new_caesar_sol2.py
key= a flag= ©¸“¸¹s“u¥§yªw¨{}vt¥|yzut¥ª©¦vy{v|wu¨¥¥|
key= b flag= ˜§‚§¨b‚d”–h™f—jlec”khidc”™˜•ehjekfd—””k
key= c flag= ‡–q–—QqSƒ…WˆU†Y[TRƒZWXSRƒˆ‡„TWYTZUS†ƒƒZ
key= d flag= v…`…†@`BrtFwDuHJCArIFGBArwvsCFHCIDBurrI
key= e flag= et_tu?_1ac5f3d7920a85610afeb2572831daa8
key= f flag= TcNcd.N PR$U"S&(!/P'$% /PUTQ!$&!'" SPP'
key= g flag= CR=RS=OADBOODC@BOO
>32? 1>>,AB,>03 1
key= i flag= !001ûý-/ñ"ÿ óõþü-ôñòýü-"!.þñóþôÿý --ô
key= j flag= /
/ ê
ìàîâäíëãàáìëíàâíãîìã
ß ÝÑÓÜÚÒßÐÛÚ ÜßÑÜÒÝÛÒ
ÈèÊúüÎÿÌýÀÂËÉúÁÎÏÊÉúÿþûËÎÀËÁÌÊýúúÁ
key= m flag= íü×üý·×¹éë½î»ì¿±º¸é°½¾¹¸éîí꺽¿º°»¹ìéé°
key= n flag= ÜëÆëì¦Æ¨Øڬݪۮ ©§Ø¯¬­¨§ØÝÜÙ©¬®©¯ª¨ÛØد
key= o flag= ËÚµÚەµ—Çɛ̙ʝŸ˜–Çž›œ—–ÇÌËȘ›˜ž™—ÊÇǞ
key= p flag= ºÉ¤Éʄ¤†¶¸Š»ˆ¹ŒŽ‡…¶Š‹†…¶»º·‡ŠŒ‡ˆ†¹¶¶

この中でフラグっぽいのは

key= e flag= et_tu?_1ac5f3d7920a85610afeb2572831daa8

new_caesar.pyに上記flagとkeyを設定して，検証

>python new_caesar.py
kjlijdliljhdjdhfkfkhhjkkhhkihlhnhghekfhmhjhkhfhekfkkkjkghghjhlhghmhhhfkikfkfhm

OK！
こういう問題を解くのは，チョー楽しい！