picoCTF 2023 Writeup : Cryptography

最初に

PicoCTF2023のCryptographyを解いていきます

Writeup

HardはSRAとPower Analysis : Warmupにのみ挑戦しています（どちらも1日で理解できなかった。。。。）

rotation

Rot18ですね

ReadMyCert

ダブルクリックしたらフラグが表示されました💦

HideToSee

stegseekしたら、テキストファイルがみつかりました

┌──(kali㉿kali)-[~/…/PicoCTF/picoCTF_2023/Cryptography/HideToSee]
└─$ stegseek atbash.jpg    
StegSeek 0.6 - https://github.com/RickdeJager/StegSeek

[i] Found passphrase: ""
[i] Original filename: "encrypted.txt".
[i] Extracting to "atbash.jpg.out".

中身はkrxlXGU{zgyzhs_xizxp_xz00558y}で、rot系の暗号化かな、とおもったが、違うみたい。。。

画像を開いてみると、内側のkのところと外側のpが対応しているから、画像が変換表になっているのか、、、

picoCTF{atbash_crack_ca00558b}

SRA

RSA暗号化の問題のようですが、envyとなっている秘密鍵dと、公開鍵で暗号化された暗号文pride（cでよく表現される）の値が出力されているので、あとは分からないのはモジュラスだけ。。

うーん、、、わからない、、、

以下のWriteupをみてみました

流れは以下になるみたいです

1. $ed ≡ 1 (mod\ φ(n))$から、$ed -1 = kφ(n)=k(p-1)*(q-1)$である
2. $e=65537,\ d=envy$で既知なので、$ed-1$も既知
3. $ed-1$を素因数分解する
4. kの候補を求める（https://eshard.com/posts/picoctf-sra-challenge#:~:text=)%0A%20%20%20%20return%20candidates-,Find%20k%20candidates,-We%20can%20first）
5. 各$k$の候補について、その素因数を$ed-1$の素因数から除いた残りを掛け合わせて、$p-1,q-1$の候補を求める
6. $p-1,q-1$の候補からモジュラスnを求める

4のところで、少し悩んだので、自分なりの理解をメモとして記載しておきます

$c = m^e (mod n)$より、暗号文のビット列は、絶対にモジュラスnのビット列よりも小さい。
n=pqで、ほぼ$ed-1$と等しいので、$ed-1=k(p-1)(q-1)$のうち、少なくとも暗号文があまりとして出力されるだけの$n=pq$が必要なので、$ed-1$のビット長から暗号文のビット長を引いた値は少なくともモジュラスnのために確保しておかないといけない。
引いて残った値がkの値のビット長の候補になる

Writeupのコードを実行してみたが、picoのインスタンスが起動している15分の間に解き切れなかった、、、、
マシンパワー不足。。。

PowerAnalysis: Warmup

The flag will be of the format picoCTF{} where is 32 lowercase hex characters comprising the 16-byte encryption key being used by the program.

このフラグはpicoCTF{<暗号化キー>}というフォーマットで、<暗号化キー>はプログラムが使用する16バイトの暗号化キーを構成する小文字の16進文字32個である。

コードを見てみたが、よくわからなかったので以下のWriteupを見てみた

サイドチャネル攻撃という攻撃ができるみたい。

もともとは、漏れ出している物理的な信号から情報を盗み取るものだが、今回は恣意的にビットの情報が漏れだしているという想定になっている。

上記のWriteupでは、以下のステップで問題を解いていました

1. サーバーからの応答がすべて0になる入力を求める
2. １の入力を１バイトずつ分割する
3. １バイトの値を１から２０までを足した数を用意する（全部で２０個）
4. １バイトで表現できるすべてのキーを使って自前で応答を計算して、それがサーバーからの応答と完全に一致すれば、それがキーになる

サイドチャネル攻撃とは...

サイドチャネル攻撃（side-channel attack）とは、ICカードや半導体機器といった攻撃対象のハードウェアを物理的に観測することで、内部の秘匿された情報を得る攻撃手法

以下サイトには6種類の攻撃手法がまとめられていた

1. タイミング攻撃：命令を処理する時間差を分析して情報を盗む
2. 電力解析攻撃：命令を処理するときの電力消費量の差を分析して情報を盗む
3. 電磁波解析攻撃：電子機器から微量にでている電磁波から情報を盗みとる
4. 故障利用攻撃：ICチップなどに衝撃を与えて仕様・設定を変更する、あるいは故障時の動作から情報を盗む
5. キャッシュ攻撃：データ取得までの時間からキャッシュに含まれている情報を推測する
6. 音響解析攻撃：コンピュータが動くときに発するノイズを解析して、情報を推測し盗む

（音響解析とか、本当にできるのか、、、、、）

最後に

今回学んだことは以下です

• RSA暗号化の仕組み（今まであまりちゃんと勉強していなかった。。）
• サイドチャネル攻撃という攻撃手法の存在（CTFではなかなか出てこないかも、、、）

参考

RSA暗号化

以下のWebページの内容を参考に簡単に整理してみる

Pythonのコードもあわせて記載しますが、
from Crypto.Util.number import getPrime, inverse
をインポートしています！

1. 大きな素数を2つ選択

選択した素数をpとqとおく

Pythonのコードは以下

p = getPrime()
q = getPrime()

2. モジュラスnの計算

n=p*qで暗号化・復号化の時に利用するモジュラスnを計算する

3. オイラーのトーシェント関数φ(n)の計算

名前はややこしいが、単純にφ(n)=(p-1)*(q-1)となる

φ(n)はnと互いに素な正の整数の個数だそうです

4. 公開鍵eの選択

以下の2条件を満たす整数eを選んで公開鍵の要素にする

• 1 < e < φ(n)
• e と φ(n) が互いに素

要素というのは、モジュラスnとeのセットで、公開鍵になるから。
ただ、よく65537が使われるみたい。

5. 秘密鍵dの計算

ed ≡ 1 (mod φ(n)) を満たす整数dが、秘密鍵の要素になる（nとセットで秘密鍵になる）

Pythonのコードは以下

d = inverse(e, (p-1)*(q-1))

6. 暗号化

平文をmとして、暗号化文をcとすると、mは以下の式で求める

c = m^e (mod n)

Pythonのコードは以下

c = pow(m, e, n)

7. 復号化

復号化は以下の方法で行う

m = c^d (mod n)

Pythonのコードは以下

m = pow(c, d, n)

SRA

Writeupのコードをほぼ利用していますが、エクスプロイトできるはずのコードです

import math


def get_subsets_sum(data, target, epsilon):
    """Find sums of values in `data` which gives `target` ± `epsilon`."""
    subsets, subsets_primes = [], []

    differences = {}
    for value in data:
        prospects = []
        for diff in differences:
            if (diff >= value) and abs(value - diff) < epsilon:
                new_subset = [value] + differences[diff]
                new_subset.sort()
                if new_subset not in subsets:
                    subsets.append(new_subset)
            if value - diff < 0.:
                prospects.append((value, diff))
 
        # update the differences record
        for prospect in prospects:
            new_diff = target - sum(differences[prospect[1]]) - prospect[0]
            differences[new_diff] = differences[prospect[1]] + [prospect[0]]
        differences[target - value] = [value]
    return subsets
    
    

def get_subsets_product(data, target, epsilon):
    """Find products of values in `data` which gives `target` ± `epsilon` (`epsilon` is given as bit size)."""  
    data = sorted(data, reverse=True)
    candidates = []
    bit_sizes = [math.log2(value) for value in data]
    target_bit_size = math.log2(target)
    bit_sizes_substets = get_subsets_sum(bit_sizes, target_bit_size, epsilon)
    for subset in bit_sizes_substets:
        values_subset = [data[bit_sizes.index(bit_size)] for bit_size in subset]
        candidates.append(math.prod(values_subset))
    return candidates
    
    
    

def remove_factors(factors, k_value, k_factors):
    factors = sorted(factors, reverse=True)
    k_factors = sorted(k_factors, reverse=True)
    result = factors.copy()
    for k_factor in k_factors:
        if k_value % k_factor == 0:
            k_value = k_value // k_factor
            result.remove(k_factor)
    return result
    

def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True


#### change your own value ####
e = 65537
d =  37642899272608646746358415604282012831815978783491698369307847278228363464193 # envy
cipher = 23480057296803584143829366880771059073699272934577455886827187897004262004743 # anger

factors_string = " 2^9 × 3^3 × 5 × 23 × 31 × 2689 × 15201 896867 604869 × 1 363079 285498 373479 × 898393 625209 751288 360473 149174 581171"

###############################


dem1 = d * e - 1 # 2086950824495258768356121134224211302266588178265585741409740007232297412609299720

factors = []

for factor in factors_string.split(' × '):
    factor = factor.replace(' ', '').strip()
    if '^' in factor:
        factor = factor.split('^')
        factors += [int(factor[0])] * int(factor[1])
    else:
        factors.append(int(factor))

factors = sorted(factors, reverse=True)
print(factors)




k_size_max = int(math.log2(dem1) - math.log2(cipher))
print(f"k_size_max={k_size_max}")

k_factors = list(filter(lambda factor: math.log2(factor) < k_size_max, factors))
print(f"k_factors={k_factors}")


k_candidates = get_subsets_product(k_factors, 2**17, 1)
print(f"k_candidates={k_candidates}")


porqm1_candidates = set()

for k_candidate in k_candidates:
    remaining_factors = remove_factors(factors, k_candidate, k_factors)
    porqm1_candidate_set = get_subsets_product(remaining_factors, 2**128, 5)
    for porqm1_candidate in porqm1_candidate_set:
        if is_prime(porqm1_candidate + 1):
            porqm1_candidates.add(porqm1_candidate)
            
porqm1_candidates = list(porqm1_candidates)
print(f"porqm1_candidates={porqm1_candidates}")

for idx, pm1 in enumerate(porqm1_candidates):
    for qm1 in porqm1_candidates[idx + 1:]:
        n_candidate = (pm1 + 1) * (qm1 + 1)
        possible_plain = pow(cipher, d, n_candidate)
        possible_plain = possible_plain.to_bytes(length=256, byteorder='big')
        try:
            possible_plain = possible_plain.decode('ascii')
        except UnicodeDecodeError:
            continue
        print(possible_plain)

素数判定には以下のQiitaを参考にしています

PowerAnalysis: Warmup

以下に記載されているエクスプロイトを記載します

from pwn import * # pip install pwntools

Sbox = (99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22)
Sbox_bits = [x & 0x1 for x in Sbox] #computes the LSBs for Sbox to make life easier

def sendinput(plaintext): #input: plaintext, output: leaked bits count
    r = remote('saturn.picoctf.net', 56726) #change port number
    #r = process('./encrypt.py')
    line = r.recvuntil(b': ')
    r.sendline(plaintext.encode())
    final = r.recvline_regex('\d+').decode()
    r.close()
    if final[-2].isdigit():
        return final[-2:]
    return final[-1]

def testbyte(bits, zero_payload): #decreases bit leakage of given position
    for i in range(0xff): #will return before it tests every byte
        prepend = ''.join([x for x in zero_payload]) #increases each byte
        payload = "{:02x}".format(i) + "00"*(16 - len(zero_payload) - 1)
        print(prepend + payload)
        result = int(sendinput(prepend + payload)) #receives the bit leakage
        print("Bits: {}".format(result))
        if result < bits:
            return payload[0:2] #return incremented byte
        elif result > bits: #LSB was already 0
            return "00"

def findSbox(position, zero_payload, size):
    payload = zero_payload.copy()
    data_byte = []
    Sboxorigin = []
    for i in range(size):
        payload[position] = "{:02x}".format(int(zero_payload[position], 16) + i)
        data_byte.append(int(payload[position], 16))
        print(''.join(payload))
        result = int(sendinput(''.join(payload)))
        Sboxorigin.append(result)
    #print("Leaked bytes: {}".format(''.join(Sboxorigin)))
    for key in range(0xff):
        testleak = [0] * size
        for pos in range(size):
            testleak[pos] = Sbox_bits[data_byte[pos] ^ key]
        if Sboxorigin == testleak:
            print("MATCH: 0x{:02x}".format(key))
            return key

bits = int(sendinput("00"*16)) #gets bit leak standard
zero_payload = [] #list of payload bytes that produce 0 bit leakage

for i in range(0x10): #for each byte
    result = testbyte(bits, zero_payload)
    zero_payload.append(result)
    if result != "00":
        bits -= 1

assert bits == 0
#zero_payload = ['00', '01', '00', '01', '00', '00', '00', '01', '00', '02', '04', '01', '03', '03', '00', '00']
print("Zero payload: {}".format(''.join(zero_payload)))
result = sendinput(''.join(zero_payload))
assert int(result) == 0


encryption_key = []
for i in range(0x10):
    size = 20 #large number prevents false positives
    print("Testing byte: {}".format(i + 1))
    result = findSbox(i, zero_payload, size)
    encryption_key.append(result)

print("Encryption key: {}".format(''.join(['{:02x}'.format(x) for x in encryption_key]))) #formats nicely
#key = 81808c36fca7288b8a57f90907ccbae6