picoCTF 2024 Writeup : Cryptography

# 最初に

picoCTF 2024のCryptographyを解いていきます！


# Writeup

問題は全部で5問ですね

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2152468/eec26188-b32b-74d8-b404-370a0b949a19.png)

## interencdec


`enc_flag`が与えられたので、中身を少しみてみます

```
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/interencdec]
└─$ file enc_flag    
enc_flag: ASCII text
                                                                                                  
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/interencdec]
└─$ strings enc_flag 
YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclgya3lNRFJvYTJvMmZRPT0nCg==
```

記載されている文字列をBASE64でデコードすると
`b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrX2kyMDRoa2o2fQ=='`になります。
この出力もBASE64っぽいのですが、BASE64には`'`が含まれないです。。。

試しに`'`で囲まれたところだけでBASE64してみると、
`wpjvJAY{jhlzhy_k3jy9wa3k_i204hkj6}`になり、
フラグっぽい形式になりました！


前半の7文字は`picoCTF`になる（はず）ので、アルファベット表と見比べると、7文字シフトになっています。
ただし数字は考慮してないようなので、以下のプログラムを作ってをデコードしたら、フラグがとれました！

```
def decrypt_caesar_cipher(cipher_text, shift): 
	decrypted_text = "" 
	for char in cipher_text: 
		if char.isalpha(): # 文字がアルファベットの場合のみシフトを行う 
			shift_base = 65 if char.isupper() else 97 # 大文字と小文字の基準値を設定 
			decrypted_text += chr((ord(char) - shift_base - shift) % 26 + shift_base) 
		else: 
			decrypted_text += char # 非アルファベット文字はそのまま追加 
	return decrypted_text 
# 使用例 
cipher_text = "wpjvJAM{jhlzhy_k3jy9wa3k_i204hkj6}" 
shift = 7 
decrypted_text = decrypt_caesar_cipher(cipher_text, shift) 
print("Decrypted text:",decrypted_text)
```



## rsa_oracle

問題文
> Can you abuse the oracle?
An attacker was able to intercept communications between a bank and a fintech company. They managed to get the message (ciphertext) and the password that was used to encrypt the message.
After some intensive reconassainance they found out that the bank has an oracle that was used to encrypt the password and can be found here nc titan.picoctf.net 52650. Decrypt the password and use it to decrypt the message. The oracle can decrypt anything except the password.

和訳は以下です
> ある攻撃者が銀行とフィンテック企業間の通信を傍受することに成功した。 彼らはメッセージ（暗号文）とメッセージを暗号化するために使用されたパスワードを取得することに成功した。いくつかの集中的な再調査の後、彼らは銀行がパスワードを暗号化するために使用されたオラクルを持っていることを発見し、nc titan.picoctf.net 52650で見つけることができます 。 パスワードを解読し、それを使ってメッセージを解読する。 オラクルはパスワード以外なら何でも解読できる。

なんだか最後の文章が意味深ですね、、


password.encとsecret.encが与えられていて、暗号化されたpassword.encを復号化できれば、それを使ってsecret.encも復号化できる、という流れでしょうか



password.encをいろいろ見てみましたが、エンコードされた文字列があるだけでした
```
                                                                                                
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ file password.enc         
password.enc: ASCII text, with no line terminators
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ strings password.enc         
2575135950983117315234568522857995277662113128076071837763492069763989760018604733813265929772245292223046288098298720343542517375538185662305577375746934
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ exiftool password.enc 
ExifTool Version Number         : 12.76
File Name                       : password.enc
Directory                       : .
File Size                       : 154 bytes
File Modification Date/Time     : 2024:12:30 17:49:00+09:00
File Access Date/Time           : 2024:12:30 17:50:04+09:00
File Inode Change Date/Time     : 2024:12:30 17:49:37+09:00
File Permissions                : -rwxrwx---
File Type                       : TXT
File Type Extension             : txt
MIME Type                       : text/plain
MIME Encoding                   : us-ascii
Newlines                        : (none)
Line Count                      : 1
Word Count                      : 1
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ binwalk password.enc 

DECIMAL       HEXADECIMAL     DESCRIPTION
-------------------------
```



secret.encも同様に初期調査。secret.encはopensslで暗号化されていて、暗号化にはSaltが使われているみたいですが、binwalkの出力からSaltは`0x67D6DDC53027205E`のようですね
```
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ file secret.enc 
secret.enc: openssl enc'd data with salted password
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ strings secret.enc  
Salted__g
0' ^
Lc}5
|UV;
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ exiftool secret.enc  
ExifTool Version Number         : 12.76
File Name                       : secret.enc
Directory                       : .
File Size                       : 64 bytes
File Modification Date/Time     : 2024:12:30 17:48:57+09:00
File Access Date/Time           : 2024:12:30 17:51:51+09:00
File Inode Change Date/Time     : 2024:12:30 17:49:37+09:00
File Permissions                : -rwxrwx---
Error                           : Unknown file type
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/rsa_oracle]
└─$ binwalk secret.enc  

DECIMAL       HEXADECIMAL     DESCRIPTION
--------------------------------------------------------------------------------
0             0x0             OpenSSL encryption, salted, salt: 0x67D6DDC53027205E
```



secret.encを16進数で表示させましたが、特に何もなさそう。。。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2152468/96cd9a86-d8cf-f731-bfd2-2e3e7cca382b.png)





問題文にあった`nc titan.picoctf.net 64872`をしてみて、少し触ってみました。
暗号化と復号化ができるみたい
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2152468/cc77930d-324e-7248-0525-3d638c3f0df5.png)

（Oracleって、賢者とかの方のOracleだったんだ、、、https://eow.alc.co.jp/search?q=oracle）


試しに`password`を暗号化してみる
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2152468/c70605c7-a943-e762-e669-fe27533ce446.png)

暗号化された`password`を入れるとちゃんと復号化してくれるみたい
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2152468/9d1af4f9-806e-e79f-41cc-094975aa84f7.png)



ここまでの内容を整理すると、
- RSA暗号化で、共通鍵を暗号化　→　password.enc
- メッセージは共通鍵で暗号化　→　secret.enc
- RSA暗号化と復号化はOracleがしている。ただし、password.encは受け付けない


ここからわからなくなったので、少し調べてみた。

いくつかの平文と暗号文のセットが与えられたときに、平文が与えらていない暗号文を解読する問題を「選択平文攻撃」というらしい。


参考


https://piedpin.com/top/2019/12/31/chosen-plaintext-attack/


今回の問題だと以下のWebページが参考になるみたいだが、ちょっと難しい。。。
今度の勉強会のネタにしよう。。。。

https://crypto.stackexchange.com/questions/2323/how-does-a-chosen-plaintext-attack-on-rsa-work/2331#2331


https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Retrieve-Modulus/README.md





## Custom encryption

問題文は以下です
> Can you get sense of this code file and write the function that will decode the given encrypted file content.
Find the encrypted file here flag_info and code file might be good to analyze and get the flag.


`enc_flag`と`custom_encryption.py`が与えられています

まずは、`enc_flag`を見てみます
```
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/CustomEncryption]
└─$ file enc_flag                             
enc_flag: ASCII text
                                                                                                   
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/CustomEncryption]
└─$ strings enc_flag 
a = 94
b = 21
cipher is: [131553, 993956, 964722, 1359381, 43851, 1169360, 950105, 321574, 1081658, 613914, 0, 1213211, 306957, 73085, 993956, 0, 321574, 1257062, 14617, 906254, 350808, 394659, 87702, 87702, 248489, 87702, 380042, 745467, 467744, 716233, 380042, 102319, 175404, 248489]
```

`custom_encryption.py`に暗号化の手順が記載されており、enc_flagには出力結果があるので、そこから復号化する以下の関数を使えばフラグが手に入ります！
```
def decrypt(cipher, key):
    plaintext = ""
    for num in cipher:
        decrypted_char = chr(num // (key * 311))
        plaintext += decrypted_char
    return plaintext

def dynamic_xor_decrypt(cipher_text, text_key):
    decrypted_text = ""
    key_length = len(text_key)
    for i, char in enumerate(cipher_text):
        key_char = text_key[i % key_length]
        decrypted_char = chr(ord(char) ^ ord(key_char))
        decrypted_text += decrypted_char
    return decrypted_text[::-1]
```






## C3

`convert.py`と`ciphertext`が与えられていて、`convert.py`の出力が`ciphertext`みたい。


`convert.py`にコメントを追加したのが以下になります！
```

import sys
chars = ""
from fileinput import input

# 入力から各行を読み込み、chars文字列に追加
for line in input():
  chars += line

# lookup1は入力文字のセット、lookup2は出力文字のセット
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"

out = ""

prev = 0
# 各文字をループで処理
for char in chars:

  # lookup1内での文字のインデックスを取得
  cur = lookup1.index(char)
  
  # 出力文字列に対応する文字をlookup2から追加
  # (cur - prev) % 40により前の文字との差分を計算し、ルックアップ
  out += lookup2[(cur - prev) % 40]
  
  # 現在のインデックスを保存
  prev = cur

# 結果を標準出力に書き込み
sys.stdout.write(out)

```



`convert.py`の内容から復号化するプログラムとして、以下を作成
```
import sys
chars = "DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl"
from fileinput import input


lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"

out = ""

prev = 0
for char in chars:
  cur = lookup2.index(char)
  out += lookup1[(cur + prev) % 40]
  prev = (cur + prev) % 40

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
```


最初は上記の処理の入力を`ciphertext`にしていて、答えが合わなかったですが、`#selfinput`から、このソースコード自体を入力してみると正解のフラグが手に入りました！

```
┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2024/Cryptography/C3]
└─$ python2 answer_from_writeup.py answer_from_writeup.py
```





## flag_printer

encoded.txtは1769612行ありました
このテキストファイルをflag_printer.pyで画像に変換しているみたい


以下のWriteupをみてみると、ニュートン補完を使ってすばやく多項式を解いているみたい

https://qiita.com/kusano_k/items/9d53b792c013e963c680#flag_printer-500-points


以下のGitHubにGaloisを使って、多項式を解く方法が記載されているから、これを試してみたのですが、やはり計算に時間がかかってしまいました。。。。

https://github.com/Glank/Galois



うまくやる方法は見つけられなかったです。。。。




# 最後に

今回学んだことは以下です
- 選択的平文攻撃 というものがあるらしい（これから勉強します。。。！）