👏

picoCTF 2024 Writeup - Cryptography

2024/03/31に公開

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