picoCTF 2024 Writeup - Cryptography
interencdec - 50 points
このファイルを解読する
YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclh6ZzJhMnd6TW1zeWZRPT0nCg==
base64っぽいのでデコードする
b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg2a2wzMmsyfQ=='
Pythonのbyte文字列っぽい。b''の中をさらにbase64でデコード
wpjvJAM{jhlzhy_k3jy9wa3k_86kl32k2}
シフト暗号っぽいのでシフト数を変えながらシフト暗号を試していく。シフト数19でフラグは以下
picoCTF{caesar_d3cr9pt3d_86de32d2}
Custom encryption - 100 points
フラグの情報が提供されるが、フラグは暗号化されている。
a = 95
b = 21
cipher is: [237915, 1850450, 1850450, 158610, 2458455, 2273410, 1744710, 1744710, 1797580, 1110270, 0, 2194105, 555135, 132175, 1797580, 0, 581570, 2273410, 26435, 1638970, 634440, 713745, 158610, 158610, 449395, 158610, 687310, 1348185, 845920, 1295315, 687310, 185045, 317220, 449395]
暗号化のコードももらえる。
暗号化コードを元に逆演算をコードを以下のように書いた。
import sys
import string
import itertools
def generator(g, x, p):
return pow(g, x) % p
def decrypt(cipher, key):
plain = ""
for num in cipher:
plain += (chr((num // 311) // key))
return plain
def dynamic_xor_encrypt(plaintext, text_key):
cipher_text = ""
key_length = len(text_key)
for i, char in enumerate(plaintext[::-1]):
key_char = text_key[i % key_length]
encrypted_char = chr(ord(char) ^ ord(key_char))
cipher_text += encrypted_char
return cipher_text
def test(cipher, text_key):
p = 97
g = 31
a = 95
b = 21
u = generator(g, a, p)
v = generator(g, b, p)
key = generator(v, a, p)
b_key = generator(u, b, p)
shared_key = None
if key == b_key:
shared_key = key
else:
print("Invalid key")
return
semi_cipher = decrypt(cipher, shared_key)
plain = dynamic_xor_encrypt(semi_cipher, text_key)
print(f'testkey is {text_key} and plain is {plain}')
if __name__ == "__main__":
message = [237915, 1850450, 1850450, 158610, 2458455, 2273410, 1744710, 1744710, 1797580, 1110270, 0, 2194105, 555135, 132175, 1797580, 0, 581570, 2273410, 26435, 1638970, 634440, 713745, 158610, 158610, 449395, 158610, 687310, 1348185, 845920, 1295315, 687310, 185045, 317220, 449395]
for chars in itertools.product(string.ascii_lowercase, repeat=7):
test_key = ''.join(chars)
test(message, test_key)
暗号化にはパスワードが必要で、暗号化のコードにハードコードされているものとは異なるので、文字種は英小文字、文字数7で暗号化のコード合わせて総当たりで実行してみたら、フラグを取得することができた。パスワードが最初の方にあったのでうまくいったが、そうでなかったらかなり時間がかかりそうなので、もうちょっと良い方法がありそう。
出力をpicoCTFでgrepすると以下のようになる。
testkey is aedurtu and plain is picoCTF{custom_d2cr0pt6d_66778b34}
C3 - 200 points
暗号化スクリプトは以下
import sys
chars = ""
from fileinput import input
for line in input():
chars += line
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"
out = ""
prev = 0
for char in chars:
cur = lookup1.index(char)
out += lookup2[(cur - prev) % 40]
prev = cur
sys.stdout.write(out)k
この逆演算を実装する
import sys
chars = ""
from fileinput import input
for line in input():
chars += line
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"
prev = 0
out = ""
for char in chars:
cur2 = lookup2.index(char)
cur1 = (cur2 + prev) % 40
out += lookup1[cur1]
prev = cur1
sys.stdout.write(out)
これで暗号文を復号すると、以下のスクリプトが出力される
#asciiorder
#fortychars
#selfinput
#pythontwo
chars = ""
from fileinput import input
for line in input():
chars += line
b = 1 / 1
for i in range(len(chars)):
if i == b * b * b:
print chars[i] #prints
b += 1 / 1
これをplain.pyとして自分に対して実行する
cat plain.py | python plain.py
a
d
l
i
b
s
改行を無視してフラグとする。
picoCTF{adlibs}
rsa oracle - 300 points
暗号文と暗号化されたパスワードが提供される。
パスワードはRSAで暗号化されており、oracleが提供されている。
以下のコマンドでアクセスできる.
$ nc titan.picoctf.net 56147
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E --> encrypt D --> decrypt.
Eを入力すると暗号化、Dを入力すると復号できる。
E
enter text to encrypt (encoded length must be less than keysize): abcde
abcde
encoded cleartext as Hex m: 6162636465
ciphertext (m ^ e mod n) 4120004116206206702513484249045538085835043890717891139146808314354200269093606704545541757695062680749561879348979861497636645000615797970656841337573200
what should we do for you?
E --> encrypt D --> decrypt.
D
Enter text to decrypt: 4120004116206206702513484249045538085835043890717891139146808314354200269093606704545541757695062680749561879348979861497636645000615797970656841337573200
decrypted ciphertext as hex (c ^ d mod n): 6162636465
decrypted ciphertext: abcde
暗号化する場合はテキストを入力し、復号する場合はテキストから数値に変換して入力する仕組みのようだ。
まずnがわからないので、これを参考にしてnを推測する。
from Crypto.Util.number import *
from pwn import *
def extractmod_eunknown(_encrypt, limit=4):
"""
Reference: https://crypto.stackexchange.com/questions/43583/deduce-modulus-n-from-public-exponent-and-encrypted-data
Function to extract the value of modulus without the value of public key exponent
:input parameters:
_encrypt : <type 'function'> : Function interacting with the server for encryption
limit : <type 'int'> : number of values to be sent for encryption
"""
try:
m_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
ct_list = [_encrypt(long_to_bytes(m_list[i]**2)) for i in range(limit)]
ct_list2 = [_encrypt(long_to_bytes(m_list[i])) for i in range(limit)]
assert len(ct_list) == len(ct_list2)
mod_list = [(ct_list2[i]**2 - ct_list[i]) for i in range(limit)]
_gcd = mod_list[0]
for i in mod_list:
_gcd = GCD(_gcd, i)
return _gcd
except Exception as ex:
print("[+] Exception: " + ex)
return -1
def encrypt(bytes):
io = remote("titan.picoctf.net", 56147)
io.sendline('E')
io.recvuntil('keysize): ')
io.sendline(bytes)
io.recvuntil('ciphertext (m ^ e mod n) ')
res = io.recvline()
io.close()
print(f'res = {res}')
return int(res)
n = extractmod_eunknown(encrypt, 4)
print(f'n = {n}')
n = 22030393809425688903020776083523505810353854173783980905150189916038264607147057047205472760876171915535339237740583816113486066627010574973734069301111884
となるが、念の為factordbで検索すると
22030393809425688903020776083523505810353854173783980905150189916038264607147057047205472760876171915535339237740583816113486066627010574973734069301111884
=
2^2*5507598452356422225755194020880876452588463543445995226287547479009566151786764261801368190219042978883834809435145954028371516656752643743433517325277971
となるので5507598452356422225755194020880876452588463543445995226287547479009566151786764261801368190219042978883834809435145954028371516656752643743433517325277971の方を使う
eはよく利用される65537と推測する。この値とoracleを使って検算するとこの(n,e)で問題なさそう
この値を使ってこれを参考にchosen ciphertext attackをする
$ python
Python 3.11.7 (main, Mar 11 2024, 20:10:32) [Clang 15.0.0 (clang-1500.1.0.2.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> e = 65537
>>> n = 5507598452356422225755194020880876452588463543445995226287547479009566151786764261801368190219042978883834809435145954028371516656752643743433517325277971
>>> c = 2336150584734702647514724021470643922433811330098144930425575029773908475892259185520495303353109615046654428965662643241365308392679139063000973730368839
>>> cb = pow(2, e, n) * c % n
>>> cb
1446054595600954198957280399193510633956191834375426323379784853800742225364673510013742317914722904743422132526526045745421340145275405687385889870266050
cは暗号化されたパスワードを整数値に変換したものである。cb(リンク先のC_b)を求めたのでoracleでdecryptする
$ echo -n -e 'D\n1446054595600954198957280399193510633956191834375426323379784853800742225364673510013742317914722904743422132526526045745421340145275405687385889870266050\n' | nc titan.picoctf.net 56147
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E --> encrypt D --> decrypt.
Enter text to decrypt: decrypted ciphertext as hex (c ^ d mod n): 6c60cc6a60
decrypted ciphertext: l`Ìj`
what should we do for you?
E --> encrypt D --> decrypt.
m*2が0x6c60cc6a60なので2で割って平文のパスワードを取得する
>>> from Crypto.Util.number import *
>>> m = 0x6c60cc6a60 // 2
>>> mes = long_to_bytes(m)
>>> mes
b'60f50'
このパスワードを使って暗号文を復号するとフラグが出力される。復号方法はヒントに書かれていて、opensslを用いる
$ openssl enc -aes-256-cbc -d -pass pass:60f50 -in secret.enc
*** WARNING : deprecated key derivation used.
Using -iter or -pbkdf2 would be better.
picoCTF{su((3ss_(r@ck1ng_r3@_60f50766}
Discussion