ペンギン技術 blog

CTFのWriteupなどを記載していこうと思います

setodaNoteCTF Writeup [Crypto]

Crypto

base64

base64 decodeするだけ

ZmxhZ3tJdCdzX2NhbGxlZF9iYXNlNjQhfQ==

https://gchq.github.io/CyberChef/#recipe=From_Base64('A-Za-z0-9%2B/%3D',true)&input=Wm14aFozdEpkQ2R6WDJOaGJHeGxaRjlpWVhObE5qUWhmUT09

ROT13

ROT13するだけ
synt{Rira_lbh_Oehghf?}

https://gchq.github.io/CyberChef/#recipe=ROT13(true,true,false,13)&input=c3ludHtSaXJhX2xiaF9PZWhnaGY/fQ

pui_pui

以下の文字列が与えられる

\x41\x3a\x44\x6f\x20\x79\x6f\x75\x20\x6b\x6e\x6f\x77\x20\x4d\x6f\x6c\x63\x61\x72\x3f\x0a\x0a\x42\x3a\x4f\x66\x20\x63\x6f\x75\x72\x73\x65\x21\x20\x49\x20\x6c\x6f\x76\x65\x20\x74\x68\x65\x20\x73\x63\x65\x6e\x65\x20\x77\x68\x65\x72\x65\x20\x68\x65\x20\x73\x69\x6e\x6b\x73\x20\x69\x6e\x74\x6f\x20\x74\x68\x65\x20\x62\x6c\x61\x73\x74\x20\x66\x75\x72\x6e\x61\x63\x65\x20\x77\x68\x69\x6c\x65\x20\x67\x69\x76\x69\x6e\x67\x20\x74\x68\x65\x20\x74\x68\x75\x6d\x62\x73\x20\x75\x70\x2e\x0a\x0a\x41\x3a\x2e\x2e\x2e\x20\x57\x68\x61\x74\x3f\x0a\x0a\x42\x3a\x62\x74\x77\x2c\x20\x74\x68\x65\x20\x66\x6c\x61\x67\x20\x69\x73\x20\x66\x6c\x61\x67\x7b\x48\x61\x76\x65\x5f\x79\x6f\x75\x5f\x65\x76\x65\x72\x5f\x68\x65\x61\x72\x64\x5f\x6f\x66\x5f\x48\x65\x78\x64\x75\x6d\x70\x3f\x7d\x2e\x0a

\xを置換し、消す
「From Hex」でデコード
https://gchq.github.io/CyberChef/#recipe=From_Hex('Auto')&input=NDEzYTQ0NmYyMDc5NmY3NTIwNmI2ZTZmNzcyMDRkNmY2YzYzNjE3MjNmMGEwYTQyM2E0ZjY2MjA2MzZmNzU3MjczNjUyMTIwNDkyMDZjNmY3NjY1MjA3NDY4NjUyMDczNjM2NTZlNjUyMDc3Njg2NTcyNjUyMDY4NjUyMDczNjk2ZTZiNzMyMDY5NmU3NDZmMjA3NDY4NjUyMDYyNmM2MTczNzQyMDY2NzU3MjZlNjE2MzY1MjA3NzY4Njk2YzY1MjA2NzY5NzY2OTZlNjcyMDc0Njg2NTIwNzQ2ODc1NmQ2MjczMjA3NTcwMmUwYTBhNDEzYTJlMmUyZTIwNTc2ODYxNzQzZjBhMGE0MjNhNjI3NDc3MmMyMDc0Njg2NTIwNjY2YzYxNjcyMDY5NzMyMDY2NmM2MTY3N2I0ODYxNzY2NTVmNzk2Zjc1NWY2NTc2NjU3MjVmNjg2NTYxNzI2NDVmNmY2NjVmNDg2NTc4NjQ3NTZkNzAzZjdkMmUwYQ

謎の会話とflagがでてくる

A:Do you know Molcar?

B:Of course! I love the scene where he sinks into the blast furnace while giving the thumbs up.

A:... What?

B:btw, the flag is flag{Have_you_ever_heard_of_Hexdump?}.

tkys_secret_service

問題文をROT13してみるとThe~となる

The priteftoiu ic Ciutrilled Uuflazzocoed Iucirmatoiu (CUI) rezodeut ou uiucederal zyztemz aud irgauosatoiuz oz ic paraminut ompirtaufe ti cederal ageufoez aud fau doreftly ompaft the aboloty ic the cederal giverumeut ti znffezzcnlly fiudnft otz ezzeutoal mozzoiuz aud cnuftoiuz. Thoz pnblofatoiu privodez ageufoez woth refimmeuded zefnroty reqnoremeutz cir priteftoug the fiucodeutoaloty ic CUI wheu the oucirmatoiu oz rezodeut ou uiucederal zyztemz aud irgauosatoiuz; wheu the uiucederal irgauosatoiu oz uit filleftoug ir maoutaououg oucirmatoiu iu behalc ic a cederal ageufy ir nzoug ir iperatoug a zyztem iu behalc ic au ageufy; aud where there are ui zpefocof zacegnardoug reqnoremeutz cir priteftoug the fiucodeutoaloty ic Flag oz clag{pnopno_far_ic_mil} CUI prezfrobed by the anthirosoug law, regnlatoiu, ir giverumeutwode pilofy cir the CUI fategiry lozted ou the CUI Regoztry. The reqnoremeutz apply ti all fimpiueutz ic uiucederal zyztemz aud irgauosatoiuz that prifezz, ztire, aud/ir trauzmot CUI, ir that privode priteftoiu cir znfh fimpiueutz. The zefnroty reqnoremeutz are outeuded cir nze by cederal ageufoez ou fiutraftnal vehoflez ir ither agreemeutz eztablozhed betweeu thize ageufoez aud uiucederal irgauosatoiuz.

Flagの文字列がある
Flag oz clag{pnopno_far_ic_mil}

Flag is flag{~}にみえる
一部の文字を入れ替えるのか
o -> i
z -> s
c -> f

flag{pnipni_far_if_mil}
だめ

英単語と仮定して法則を見つける
aud -> and
u -> n

aud/ir -> and/or
privode -> provide
i -> o
flag{pnipni_far_of_mol}
まだだめ

agreemeutz -> agreements
z -> s

Uuflazzocoed -> Unclassified
f -> c?
大文字はそのまま?

モルカーっぽい
n -> u

lets_bake

150

あなたはシェフ帽の人物からレシピを受け取りました。どうやら組織からの秘密のメッセージのようです。
レシピを解読し、秘密のメッセージを入手してください。

Input:
NzRmNDRiMWE0Y2M2ZGNiNzc3NTMyNTcwZjk0MTE4NTMyNTcxZjE1YTE1NTJkY2M0

Recipe:
RnJvbV9CYXNlNjQoJ0EtWmEtejAtOSsvPScsdHJ1ZSkN]b2[sRnJvbV9IZXgoJ05vbmUnKQ0=]b2[sRm9yaygnJScsJ18nLGZhbHNlKQ0=]b2[sUkM0KHsnb3B0aW9uJzonVVRGOCcsJ3N0cmluZyc6J2NoZWYnfSwnTGF0aW4xJywnTGF0aW4xJyk=

問題文からサイバーシェフを使うとわかる

Recipeをどう解読するのか非常に苦戦したが、以下のように区切り、
それぞれBASE64デコードしたらうまくいった

RnJvbV9CYXNlNjQoJ0EtWmEtejAtOSsvPScsdHJ1ZSkN]b2[s
RnJvbV9IZXgoJ05vbmUnKQ0=]b2[s
Rm9yaygnJScsJ18nLGZhbHNlKQ0=]b2[s
UkM0KHsnb3B0aW9uJzonVVRGOCcsJ3N0cmluZyc6J2NoZWYnfSwnTGF0aW4xJywnTGF0aW4xJyk=

BASE64デコード

From_Base64('A-Za-z0-9+/=',true)
ok

From_Hex('None')
ok

Fork('%','_',false)
ok

RC4({'option':'UTF8','string':'chef'},'Latin1','Latin1')
ok

Inputをこのレシピ通りに変換するとフラグが得られる https://gchq.github.io/CyberChef/#recipe=From_Base64('A-Za-z0-9%2B/%3D',true)From_Hex('Auto')Fork('%25','_',false)RC4(%7B'option':'UTF8','string':'chef'%7D,'Latin1','Latin1')&input=TnpSbU5EUmlNV0UwWTJNMlpHTmlOemMzTlRNeU5UY3daamswTVRFNE5UTXlOVGN4WmpFMVlURTFOVEprWTJNMA

vul_rsa_01

200

あなたは組織の定期研修に参加しています。
教官から RSA 暗号の禁止事項くらいは覚えておくようにと課題が出題されました。
どうやら暗号文 c を解くことができればそれだけ早く帰れるようです。

以下の RSA 暗号を解読してフラグを入手してください。

c: 39119617768257067256541748412833564043113729163757164299687579984124653789492591457335

n: 13373801376856352919495636794117610920860037770702465464324474778341963699665011787021257

e: 65537

以下を参考に解いていく

RSA暗号解読問題を解く
https://k-mawa.hateblo.jp/entry/2018/06/07/192242
https://k-mawa.hateblo.jp/entry/2018/06/19/141347

Msieve(高速に素因数分解を行ってくれるプログラム)のインストール
https://inaz2.hatenablog.com/entry/2016/01/09/032521

Ubuntuにて必要となるパッケージをインストール

$ sudo apt-get install build-essential libgmp3-dev zlib1g-dev libecm-dev

ダウンロードとコンパイル

$ wget "http://downloads.sourceforge.net/project/msieve/msieve/Msieve%20v1.52/msieve152.tar.gz?r=&ts=1452107977&use_mirror=jaist" -O msieve152.tar.gz
$ tar xvf msieve152.tar.gz
$ cd msieve-1.52/
$ make all ECM=1

nの値を使い、解析を行う

$ ./msieve -e -p -q -v "13373801376856352919495636794117610920860037770702465464324474778341963699665011787021257"


Msieve v. 1.52 (SVN unknown)
:(略)
prp43 factor: 3058517013146002381763962882964790715736519
prp46 factor: 4372642466716249946441875327733923056149624303
elapsed time 00:29:31

ログより、30分ほどかかっている
nを素因数分解した場合の、2つの素数pとqが判明

pycryptoをインストール

$ pip install pycrypto

参考サイトの通り、スクリプトを書く

from Crypto.PublicKey import RSA
from Crypto import Random
from Crypto.Util.number import * #inverse()を使う
import Crypto.PublicKey.RSA as RSA

C = 39119617768257067256541748412833564043113729163757164299687579984124653789492591457335
N = 13373801376856352919495636794117610920860037770702465464324474778341963699665011787021257
E = 65537

p = 3058517013146002381763962882964790715736519
q = 4372642466716249946441875327733923056149624303

d = inverse(E,(p-1)*(q-1))
print (d)

#秘密鍵
rsa_key = RSA.construct((p*q, E, d))
print (rsa_key)

print (rsa_key.decrypt(C))

int = rsa_key.decrypt(C)
print (long_to_bytes(int))

スクリプトを実行

$ python3 rsa_test.py
4897557609358873156657999039608506066811736904039482454770352974851826510011931551945473
<_RSAobj @0x7f98fd45cda0 n(293),e,d,p,q,u,private>
46327402297761911070944293204953074319567693047395802794186233938451290661245
b'flag{weak_rsa_can_be_decrypted!}'

vul_rsa_02

250

あなたは引き続き組織の定期研修に参加しています。教官は昨日と同じ人物です。
「早く帰れると言ったな。あれは嘘だ」昨日の信じられない光景が脳裏に蘇ります。
RSA 暗号の禁止事項くらいは覚えておくようにと再び RSA 暗号の課題が出題されました。
もはや誰も信じていませんがどうやら暗号文 c を解くことができればそれだけ早く帰れるようです。

以下の RSA 暗号を解読してフラグを入手してください。

c: 227982950403746746755552239763357058548502617805036635512868420433061892121830106966643649614593055827188324989309580260616202575703840597661315505385258421941843741681

n: 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423

e: 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137

ROCAの脆弱性を試してみる

ROCAに必要なパッケージのインストール

$ sudo apt install git
$ sudo apt install libgmp-dev
$ sudo apt install cmake

necaのダウンロードとインストール

$ git clone https://gitlab.com/jix/neca
$cd neca
$cmake .
$make

./neca (nの値)のように実行

$ ./neca 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423
NECA - Not Even Coppersmith's Attack
ROCA weak RSA key attack by Jannis Harder (me@jix.one)

 *** Currently only 512-bit keys are supported ***

 *** OpenMP support enabled ***

N = 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423
Given key does not seem to be weak.

失敗

(参考)以下サイトでROCAの脆弱性があるかチェックできる
https://keychest.net/roca
(ここまで)

RSA暗号運用でやってはいけないnのこと
https://www.slideshare.net/sonickun/rsa-n-ssmjp

eの値が大きすぎてはいけない
Wiener's Attack が適用可能
eが大きいと相対的にdが小さくなることを利用
上記が使えそう

Pragyan CTF 2019 "Easy RSA" writeup
https://ctftime.org/writeup/13831

rsa-wiener-attack
https://github.com/pablocelayes/rsa-wiener-attack

上記を少し変更して問題に合わせる

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)

    for (k,d) in convergents:

        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d

# TEST functions

def test_hack_RSA():
    print("Testing Wiener Attack")
    times = 1

    while(times>0):
        e = 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137
        n = 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423
        d = 0
        print("(e,n) is (", e, ", ", n, ")")
        print("d = ", d)

        hacked_d = hack_RSA(e, n)

        print("d = ", d, ", hacked_d = ", hacked_d)
        print("-------------------------")
        times -= 1

if __name__ == "__main__":
    #test_is_perfect_square()
    #print("-------------------------")
    test_hack_RSA()

実行してみる

$ python3 RSAwienerHacker_m.py
Testing Wiener Attack
(e,n) is ( 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137 ,  314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423 )
d =  0
Hacked!
d =  0 , hacked_d =  19780253153570454414022314122363673676673
-------------------------

以下スクリプトにて復号する
(参考にしたサイト)https://tech.kusuwada.com/entry/2018/06/02/013904

from Crypto.PublicKey import RSA
from Crypto import Random
from Crypto.Util.number import * #inverse()を使う
import Crypto.PublicKey.RSA as RSA

E = 66936921908603214280018123951718024245768729741801173248810116559480507532472797061229726239246069153844944427944092809221289396952390359710880636835981794334459051137
N = 314346410651148884346780415550080886403387714336281086088147022485674797846237037974025946383115524274834695323732173639559408484919557273975110018517586435379414584423
C = 227982950403746746755552239763357058548502617805036635512868420433061892121830106966643649614593055827188324989309580260616202575703840597661315505385258421941843741681
d = 19780253153570454414022314122363673676673

key = RSA.construct(map(int, (N, E, d)))
print(long_to_bytes(key.decrypt(C)))

実行

$ python3 rsa_test.py
b'\x02my\xa6\xfb\xa2t\x19X\xce\x82F(U\xa9n\xc4\xdc\x16#\x13<\xfc4\x15y\x92\x0b\xef\xc0.\xb7\xb9\xe0\xa3\xbb\xb8r\x00flag{197_Michael_J_Wiener_673}'

なんか、フラグ以外に余計な出力がでているが・・・不明

WEARECIA

300

家に帰ると黒い封筒が郵便受けに入っていました。
封筒の中身は英字が羅列されたメモが一枚。
青銅色の紙に白いインクで書かれており右下には同じインクで WEARECIA と記載されています。
どうやら暗号文のようです。暗号文を解析してメッセージを受け取る必要がありそうです。

以下の暗号文を解読し、隠されたメッセージを見つけてください。
フラグは得られたメッセージを flag{} で囲んで回答してください。

EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJYQTQUXQBQVYUVLLTREVJYQTMKYRDMFDRCDNKFRHHMKVLLTGBMFDUTMALDUMKYQTGLWLWCM

(解けていない)

(追記)
https://github.com/satoki/ctf_writeups/tree/master/setodaNote_CTF/WEARECIA
以下を使うらしい
https://www.dcode.fr/vigenere-cipher
ALPHABETKRYPTOSABCDEFGHIJLMNQUVWXZ
KNOWING THE KEY/PASSWORD:PALIMPSEST

FLAGISを含む文字となる
BETWEENSUBTLESHADINGANDTHEABSENCEOFLIGHTLIESTHENUANCEOFIQLUSIONFLAGISWEARETHENATIONSFIRSTLINEOFDEFENSE