ångstromCTF 2020 writeup [Misc]

ångstromCTF 2020 writeup [Misc]

ångstromCTF 2020 のMiscのwriteupです。

Sanity Check (5pts)

discordに参加して、#rolesに書いてある通りに:triangular_flag_on_post:でリアクションすると、#generalのtopicに書かれたflagを見ることができるようになります。

actf{never_gonna_let_you_down}

ws1 (30pts)

pcapファイルが渡されます。grepします。

$ strings recording.pcapng | grep actf
flagz,actf{wireshark_isn't_so_bad_huh-a9d8g99ikdf})
flag=actf%7Bwireshark_isn%27t_so_bad_huh-a9d8g99ikdf%7D

ws2 (80pts)

pcapファイルが渡されます。wiresharkで覗いてみると

54	10.100649	127.0.0.1	127.0.0.1	HTTP	102	POST / HTTP/1.1  (JPEG JFIF image)

でjpegが送られているので、エクスポートします。

msd (140tps)

プログラムを見ると、flagの各文字のアスキーコード(10進)の各桁の数字a($0\leq a\leq 9$)と画像breathe.jpgの各ピクセルのRGBの値b($0\leq b\leq 255$)について、bの最高位の値をaに置き換えてから、$b=min(b,255)$をしています。
よって、output.png, breathe.jpgの各ピクセルのRGBの値の組(c,b)について、

  • $c=255$の時... aは不明
  • $c\neq 255$でbとcの桁数が同じ... aはcの最高位の値
  • $c\neq 255$でbとcの桁数が違う(cの桁の方が小さいはず)... $a=0$
    として各aを求めることができます。
from numpy import *
from PIL import Image

p1 = Image.open("breathe.jpg")
img1 = array(p1)
p2 = Image.open("output.png")
img2 = array(p2)

h, w, c = img1.shape

def decode(p1, p2):
    p1 = str(p1)
    if str(p2)[1:]==p1[1:]:
        return str(p2)[0]
    if str(p2)==p1[1:] or str(p2)==p1[-1:]:
        return "0"
    if p2==255:
        #print(p1,p2)
        return "#"
    if len(str(p1))!=len(str(p2)):
        return "0"
    return str(p2)[0]

flagord = ""
for y in range (0, h):
    for x in range (0, w):
        pixel1 = p1.getpixel((x,y))
        pixel2 = p2.getpixel((x,y))
        for i in range(0,3):
            flagord += decode(pixel1[i], pixel2[i])
print(flagord)

このflagordを見てみると、

7611111410110932105112115117109321001111081111143211510511632971091011164432991111101151019911610111611711432971001051121051159910511010332101108105116443211510110032100111321011051171151091111003211610110911211111##210#1109910510010510011#11011###11#11##210#97##11111#1013#10111##210011110#111114101#21099#10#110###2#210210#11#112##2##2##11#2210111010#10##2##100##10#10#11010#10##211#10111010###10####211#11#10#11##211011111#11#11#11#100#210112010111###10...

となっており、charに直すと、

Lorem ipsum dolor sit amet, ...

となります。wikipediaを調べると、lorem ipsumというものがあり、一般的なテキストとして載っている

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

はasciiにすると1207文字らしいです。

それはそうと、actf{ ... }をasciiに直した97 99 116 102 123 ... 125をflagordの中から探します。
flagordを見ているとflagはlorem ipsumの文章とactf{...}からなっていそうな気がしてくるのでこれを仮定し、さらにactf{...}の中に大文字のLはないものと仮定して、検索に引っかかる範囲でlorem ipsumとactf{...}の位置を調べます。
まず、actf{}固有の{ (123)を探します。ただし、123で検索すると112 34 (p )がlorem ipsumの"aliquip ex"に引っかかるので、2123で検索します。
すると、0-indexedで先頭の2の位置が$3732, 16312, 26376, 36440, ...$とわかります。よって、actf{...}の先頭の文字aを表す9の位置は$3723, 16303, 26367, 36431, ...$です。この数列の差は2516の倍数になっているので、flagをasciiにしたものの長さは2516な気がしてきます。

次に、lorem ipsum固有のL (67)で検索してみます。すると、0-indexedで先頭の6の位置は$0,6341, 16405, 22644, 28986,...$とわかります。この数列について差を取ったりしていると、どうもflagは

  • lorem_ipsum(1207文字) + actf{...}(104文字) + lorem_ipsum
    という形だと上記の情報と矛盾しないことがわかってきます。

よって、flagordの文字列をoutという名前のファイルに貼っておいて、

with open("out", "r") as intxt:
    string = intxt.read().strip("\n")

for i in range(0,len(string),2516):
    print(string[i+2414 : i+2516])

を実行すると、

97#911610212#10#11010##2102101##10112010###10#101##1011#21121#2#####0#1######10#10#10#12110#####12112#
9799116102123105110104971081019510112010497108101951011221121224549505148579810#10#103121104####1#112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10310312110#####121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1####2#10#10#10#12110#####1211##       
####11#10#1##10#110104##10#101##10112010###10#101##101122112122#2###0#1##2###10#10210212110#####1#11##
979911610212310511010497108101951011201049710810195101122112122454950514857981051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#00212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
##2#11#10212#10#11010###10#101##10112010###10#101##101122112122##2##0#12#####10#10#10#12110#####12112#       
979911610212310511010###10#101#510112010###10#101##101122112122454950514857#810#10#10#12110##2##1211##       
####11#10212#105110104#71081019#1011201049710810195101122112122454950514857981051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
#79911#10012310#11010###10#101##10112010###10#101951011221121224549505148579810#10#10#12110#####12112#       
9799116102123105110104971081019#101120104971081012#101122112122####20#1######10#10#10#12110#####12112#       
979911610212310511010497108101951011201049710810195101122112122454950514857981051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#1#110#####121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###102101##10112010##71081019#10112#11#12#4##950#1#85#9810#10#10#12110#####121125       
979#11#10212#10#11010###10#101##10112010#2210#101##101122112122454#50#14#57#81051031031#11049#98121125       
979911610212310511010497108101951011201049710810195101122112122#####0#1######10#10#10#1#110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
979911610212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110###2#12112#       
97991161021231051101049710810195101120104971081019510112211212###2##0#1######10#10#10#12110####2121122
####11#10#12#10#11010#97108101#51011#01049#10#10195101122112122#54#50214#57#81051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010##210#101##101120104971081019510112211212245495051######10#10#10#12110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
#2##11#10212#10#11010###10#101#2101120102##10#1012#1011##112122##4950514857981051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####051#85#98105103103121104#79#12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###10#101#2101120102##10#1012#101122112122#2##20#1##2###10#10#10#1210049798121125       
####11#10212#10#11010##2102101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
#79#11#10#12#10#11010#97108101#51011#01049#10#10195101122112122#54#50514857981051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#110102##10#101##10112010###10#101##101122112122#####021#2##2#10#10#10#12110##2##12112#       
979911610212310511010497108101951011201049710810195101122112122#2###0#1######10#102102121102##2#1#11##       
97#91161021231051101049#10#10195101120104#71081019#10112#11#12#45295051#85#98105103103121104#79#12112#
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###10#1019510112010497108101951011#21121#2#####0#1######10#10#10#12110#####1#11##       
####11#10212#10#11010##2102101##10112010###10#101##101122112122##2##0#12##2##10#10#10#12110#2##2121122       
#79911610212310511010497108101951011201049710810195101122112122454950514857981051031031211049798121125       
####11#10212#10#11010###10#101##10112010###10#101##1011221121224#49#05148#79#10#10#10#1201009798121125       
####11#1021##10#11010###10#101##10112010###10#101##10112#11#12######0#1######10#10#10#12110#####12112#       
####11#10#12#10#11010###10#101##1011#010###10#101##101122112122#####0#1######10#10#10#1211049798121125
979911610212310#11010###10#101##10112010###10#101##1011#21121#2#####0#1######10#10#10#12110#####1#11##       
97#91061021231051001049#10#10195101120104#71081019#10112#11#12245##50#1######10#10#10#12110#####12112#       
####11#10#12#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10#1##10#11010###10#101##10112010###10#101##10112#11#12######0#1######10#10#10#12110#####12112#       
2##211#10212#10#11010###10#101##10112010###10#101951011#21121224549505148579810510310312110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##1011##11#1#######0#1######10#10#10#12110#####1#112#       
####11#1021##10#11010###10#101##10112010###10#101##10112#11#12######0#1######10#10#10#12110#####12112#       
###910#10212#10511010###10#101##1011#010###10#101##101122112122#####0#1######10#10#10#1#110#####12112#
####11#1021##10#11010###10#101##1011#010###10#101##101122112122#####0#1#####210#10#10#12110#####12112#       
##2#11#10212#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#12110#####12112#       
####11#10#12#10#11010###10#101##10112010###10#101##101122112122#####0#1######10#10#10#1#110#####12112#       
####11#10212#10#11010###10#101##10112010###10#101##1011#21121#2#####0#1######10#10#10#12110#####1#11##

先頭が2になっている行がありますが無視して、7行目の

979911610212310511010497108101951011201049710810195101122112122454950514857981051031031211049798121125

をcharに直します。

string = "979911610212310511010497108101951011201049710810195101122112122454950514857981051031031211049798121125"

flag = ""
while(len(string)>0):
    num = string[:2]
    if(int(num)<30):
        num = string[:3]
        string = string[3:]
    else:
        string = string[2:]
    flag += chr(int(num))

print(flag)
$ python3 make.py
actf{inhale_exhale_ezpz-12309biggyhaby}

やったぜ。

Shifter (160pts)

$ nc misc.2020.chall.actf.co 20300
Solve 50 of these epic problems in a row to prove you are a master crypto man like Aplet123!
You'll be given a number n and also a plaintext p.
Caesar shift `p` with the nth Fibonacci number.
n < 50, p is completely uppercase and alphabetic, len(p) < 50
You have 60 seconds!
--------------------
Shift TMWTRILMRTRCYYPGHCVQUVFVWQIAYE by n=8
:

とのこと。先にFibonacciを求めておいて、各クエリについてstringをFib[n]だけシフトします。

import socket

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('misc.2020.chall.actf.co', 20300))

fib = [0]
fib.append(1)
fib.append(1)
for _ in range(55):
    fib.append((fib[-2]+fib[-1]) % 26)

print(fib)
q = s.recv(256)
while True:
    q = s.recv(256).decode("utf-8")
    print(q)
    ql = q.split("\n")[-2].split(" ")
    print(ql)
    if len(ql)==1:
        break
    shift = fib[int(ql[3][2:])]
    ans = ""
    for c in ql[1]:
        c = ord(c)
        c += shift
        if c>ord('Z'):
            c -= 26
        ans += chr(c)
    print(ans)
    s.sendall(str(ans + '\n').encode('utf-8'))
...
actf{h0p3_y0u_us3d_th3_f0rmu14-1985098}

Noisy (240pts)

flagをモールス信号に変換した後、モールス信号に応じて0または1を10回連続で送ることを繰り返しています。

. -> 10 -> 11111111110000000000
- -> 110 -> 111111111111111111110000000000
 (space) -> 000 -> 000000000000000000000000000000

という感じです。
ただし、(0-0.5), (1-0.5)に平均0分散2の正規分布に基づいた乱数aを足されているので、このノイズを取り除く必要があります。
問題文を見るとflagを繰り返し送っているそうなので、この繰り返しの周期を割り出してから、flagのある箇所のビットを表す複数個のビットについて多数決をすることを目指します。

まずは、与えられたデータを愚直に01に直します。10個の数の集合$S={S_0,S_1,\ldots,S_9}$について、
もとのビットが1だったとして数値$S_i$が現れる確率$N(S_i-0.5 | \mu=0, \sigma=2)$、
もとのビットが0だったとして数値$S_i$が現れる確率$N(S_i+0.5 | \mu=0, \sigma=2)$、
を使って0か1かを決めてしまいます。(下のコードでは和を使っていますが、積のほうがいい気がします...)

from statistics import mean
import math

bits = []

with open("4ea.txt") as intxt:
    inl = intxt.readlines()
    assert len(inl)==28800

    for i in range(2880):
        vals = []
        for j in range(10):
            vals.append(float(inl[i*10+j].strip("\n")))
        p1 = sum([math.exp(-(i-0.5)**2/8) for i in vals])
        p0 = sum([math.exp(-(i+0.5)**2/8) for i in vals])
        if p1>p0:
            bits.append(1)
        else:
            bits.append(0)

次に、周期を決めます。
bitsの長さが2880であることからflagを表すバイナリの長さは2880の約数だと思われるので、この中でそれっぽいものを目で見て探します。

for i in range(1,289): # 繰り返し回数
    if 2880%i==0:
        print(i)
        plen = 2880//i
        for j in range(i):
            for k in range(plen):
                print(bits[j*plen+k], end="")
            print()

すると、周期n=30のときに縦の列でかなり数字がそろっていて、それっぽくなります。

30
100100100101000011011011000010100001010000001101011011001001010011010110110000101000010101000010
111100001101000011011011000111100001010000101101010011000011010000110100110000100000010101010010
101100001101000011011011000010100001010100000111011011001010010001110110110000101100110101000010
101100001101000011011011000010100001010100001101011011000011010000110110110000100000010101000010
101100001011100011111011000010000001110100001101011011000011010000110110110000101000010101010010
111100001100000011011110000010100111010100001101011011001111110000010110110000101000010101000010
101100011101000011011011000010100001010110000100011011000011010100111010110001101000010101000010
101100001101000011011011000010100001010110001101011011000011010000110110111010101010010101000010
101110001101000011010011000010100001010100001101011011000011010000110100110000101000010101000010
101100001101000011011011000010100001010100001111011011100011010000101110110000101000010101000010
101100001101000011011001000010100011010100101101011011000011110000110100010000111000010101000010
101000001101010011011011000010100000010100000101011011000011010000110110110000101000010101000010
101000001101000011011011000010100001010100001101011011000011010000110110110000101000010101000110
101100001101010011011111000010100001010100001101011011000001110000110110110000101001010101001010
101100001001001011011010000010100001010100001100011011000111010100010110110000101000010101000010
101100001101000011011011001010000000010100001101011011000011010000110110110000101000010101000010
101100001101100011011011010000100001010000001101011011000011010000110010110000101000010101000011
101100001101000011011010000010100001010101101001011011000011011000110110010000101001010101000010
101100101111000011011011000010110001010100101101011011000011010000110110110000101000010100000010
101100001101010011011011000010100001010100001101011011000011011000110110110001101000011101001010
101100001001000011011011000010100010010100001101011011000011010000110100100000101000010101000010
111100001101000111011011000010100001010100001101011001000011010000110110110000101000110101000000
101100001101010011011011001010101001010100001101110011000011010000110110110001101000010111000010
101100001101000011011011000010100001010100011101011011001011010001110110100000101000010101000010
101100001101000011011011000011100101010100001101011011000011010000110110110000101000000101000010
101110001101000011011111000010100001010100001111011011000011010010110110110000001000011001000110
101100000101000011011011000010100001010100000101011011000011010100110110110000101001010100001010
101100001101000011011011000010101011010100001101011111000011010000110110110000101000010101000010
110100001101000011011011001010100001010100001101011111000011011000110110100000101010000101000010
101100001101000001111011000000110001011100001111011011100011010000011110110000101000010101000010

周期を決めたので、多数決によってflagを表すバイナリを作ってみます。

i=30
signal = []
plen = 2880//i
for k in range(plen):
    samesigs = []
    for j in range(i):
        samesigs.append(bits[j*plen+k])
    ones = samesigs.count(1)
    zeros = 30-ones
    print(ones)
    if ones>=15:
        signal.append("1")
    else:
        signal.append("0")

print("".join(signal))

morse = ""
i = 0
while i<2880//30:
    if signal[i]=="1":
        if signal[i+1]=="1":
            assert signal[i+2]=="0"
            morse += "-"
            i += 2
        else:
            morse += "."
            i += 1
    else:
        assert signal[i+1]=="0" and signal[i+2]=="0"
        morse += " "
        i += 2
    i+=1

print(morse)
$ python3 solve.py
[30, 4, 28, 28, 2, 0, 2, 1, 28, 27, 2, 29, 2, 4, 1, 1, 29, 30, 2, 30, 29, 3, 29, 27, 0, 1, 3, 1, 28, 2, 28, 2, 2, 2, 4, 27, 1, 30, 1, 27, 2, 1, 4, 1, 26, 29, 4, 28, 1, 30, 28, 2, 29, 30, 2, 0, 4, 2, 28, 29, 3, 30, 3, 3, 2, 3, 26, 29, 3, 28, 26, 0, 28, 27, 1, 0, 1, 3, 29, 1, 28, 1, 2, 3, 2, 28, 2, 29, 1, 28, 0, 2, 3, 2, 29, 1]101100001101000011011011000010100001010100001101011011000011010000110110110000101000010101000010
.- -. --- .. ... -.-- -. --- .. ... .

このモールス信号をオンラインデコーダーで復号すると、anoisynoiseとなります。