📌

Google CTF writeup

2022/07/04に公開

CTF

tech

ELECTRIC MAYHEM CLS

問題概要

AESで16bytesした平文と暗号文、下図のような電力の組が50個与えられる
鍵を求めてください

考察/方針

図を見てみると、時間軸方向は一致していて、かなりきれいなデータをしている
AESの10ラウンドっぽい
まあ電力解析やろな…

調べてみると、電力解析に関するブログが出てきた。どうやら、平文をSubBytesしたもののハミング距離と、電力が相関するらしく、1bytesずつ鍵をブルートフォースすることができるらしい。「最初の一回目」というのがおそらく肝心で、二回目以降は正しい鍵がないとMixColumnsやらShiftRowsやらでグチャグチャになってしまうので、平文をSubBytesした値を見に行く。

色々書いたけど、上記のブログのほぼコピペでそのまま動く。電力の波形はtraces.jsonで与えられるので、それをうまくこのブログのコードに適用する。

問題を解いてるときに「最初の一回のSubBytesの部分の電力波形」と「一回目のSubBytesの結果」が相関すると思っていたので、きれいにそこを取り出す方法を考えていたが、多く取る分には問題ないらしい。ここは調査が必要。範囲を広く取れば広く取るほど徐々に収束して、安定していい結果が出るようになった気がする。

実装、結果

#ref: https://trmr.hatenablog.com/entry/2018/03/18/220441

import json
import numpy as np
import matplotlib.pyplot as plt
import scipy.io as sio
from Crypto.Cipher import AES
import binascii
import sys

humming = [bin(n).count("1") for n in range(256)]

json_open = open('traces.json', 'r')
json_load = json.load(json_open)

sbox = (
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16)

def addkey_subbytes(pt, guesskey):
    return sbox[pt ^ guesskey]

N = len(json_load)

print(N)
# print(json_load[0]['pt'])
# print(json_load[0]['ct'])
# print(json_load[0]['pm'])

bestguess = [0] * 16
data_start = 7
data_end = 200
NUM_POINTS = data_end - data_start
NUM_TRACES = len(json_load)
traces = []

for pt_ct_pm in json_load:
    traces.append(pt_ct_pm['pm'][data_start:data_end])

for k_idx in range(16): # determine key index
    cpaoutput = [0] * 256

    # follow valiables may not be need
    maxcpa = [0] * 256
    bestcor = 0
    bestkey = 0
    

    for kguess in range(256): # determine word key candidate
        sumnum = np.zeros(NUM_POINTS)
        sumden1 = np.zeros(NUM_POINTS)
        sumden2 = np.zeros(NUM_POINTS)

        hyp = np.zeros(NUM_TRACES)

        for t_idx in range(NUM_TRACES): # hypothesis hamming weight
            hyp[t_idx] = humming[addkey_subbytes(json_load[t_idx]['pt'][k_idx], kguess)]

        h_mean = np.mean(hyp, dtype=np.float64)
        t_mean = np.mean(traces, axis=0, dtype=np.float64)

        assert 0 < h_mean and h_mean < 8, "meanh is not between 0 and 8"
        assert len(t_mean) == NUM_POINTS, "meant is less than trace points"

        cors = []

        for t_idx in range(NUM_TRACES):
            hdiff = (hyp[t_idx] - h_mean)
            tdiff = traces[t_idx] - t_mean

            sumnum = sumnum + (hdiff * tdiff)
            sumden1 = sumden1 + hdiff * hdiff
            sumden2 = sumden2 + tdiff * tdiff

        cpaoutput[kguess] = sumnum / np.sqrt(sumden1 * sumden2)

        maxcpa[kguess] = max(abs(cpaoutput[kguess]))

    bestguess[k_idx] = np.argmax(maxcpa)
    print("[+] best guess key [{0}] is {1:02x} (score: {2})".format(k_idx, bestguess[k_idx], maxcpa[bestguess[k_idx]]))

strkey = ''.join(map(chr, bestguess))
print(strkey)

実行結果↓

[+] best guess key [0] is 57 (score: 0.7664977105152343)
[+] best guess key [1] is 30 (score: 0.8037369571679035)
[+] best guess key [2] is 63 (score: 0.8157907186646868)
[+] best guess key [3] is 6b (score: 0.8521975480655525)
[+] best guess key [4] is 41 (score: 0.8582517655176524)
[+] best guess key [5] is 77 (score: 0.8911782264396743)
[+] best guess key [6] is 6f (score: 0.8435973736511324)
[+] best guess key [7] is 63 (score: 0.9323855381027755)
[+] best guess key [8] is 4b (score: 0.7750422415424753)
[+] best guess key [9] is 61 (score: 0.7558696238936866)
[+] best guess key [10] is 57 (score: 0.6984881287051522)
[+] best guess key [11] is 6f (score: 0.7681638092660229)
[+] best guess key [12] is 43 (score: 0.8914487915813523)
[+] best guess key [13] is 6b (score: 0.8666624881937892)
[+] best guess key [14] is 61 (score: 0.8998081004528541)
[+] best guess key [15] is 31 (score: 0.8984227108207175)
W0ckAwocKaWoCka1

Cycling

問題概要

下記ソースコードを実行して結果を得ることができれば答えです。

#!/usr/bin/python3

# Copyright 2022 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
It is well known that any RSA encryption can be undone by just encrypting the
ciphertext over and over again. If the RSA modulus has been chosen badly then
the number of encryptions necessary to undo an encryption is small.
If n = 0x112b00148621 then only 209 encryptions are necessary as the following
example demonstrates:

>>> e = 65537
>>> n = 0x112b00148621
>>> pt = 0xdeadbeef
>>> # Encryption
>>> ct = pow(pt, e, n)
>>> # Decryption via cycling:
>>> pt = ct
>>> for _ in range(209):
>>>   pt = pow(pt, e, n)
>>> # Assert decryption worked:
>>> assert ct == pow(pt, e, n)

However, if the modulus is well chosen then a cycle attack can take much longer.
This property can be used for a timed release of a message. We have confirmed
that it takes a whopping 2^1025-3 encryptions to decrypt the flag. Pack out
your quantum computer and perform 2^1025-3 encryptions to solve this
challenge. Good luck doing this in 48h.
"""

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680

# Decryption via cycling:
pt = ct
for _ in range(2**1025 - 3):
  pt = pow(pt, e, n)
# Assert decryption worked:
assert ct == pow(pt, e, n)

# Print flag:
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())

方針

この問題は数式で書くと、次の式を解く問題といえます。

m = c^{\left(e^{\left(2^{1025}-3\right)}\right)} \mod n

バイナリ法は、 $m$ 乗するときに、 $\mathrm{O}(\log m)$ の計算量になるので、ざっくり $2^{1025}-3$ 回くらいは計算しないです。これでは大変つらいので、計算量を減らしていきましょう。

この問題のポイントは、 $e^{2^{1025}-3}$ 乗すると、もとに戻るということを利用するということです。これは何を表しているのでしょうか？

カーマイケル関数を $\lambda(n)$ と書くことにします。 $\lambda(n)$ は以下の式を満たす最小の値になります。

x^{\lambda(n)} \equiv 1 \mod n

$n = pq$ のとき、以下の式が成立します。

\lambda(n) = \mathrm{lcm}(p-1, q-1)

この問題は、問題文より、以下の式が成立します。( $2^{1025}-3$ ではなく、 $2^{1025}-2$ になっているのは、最初の暗号化の分の一回です)

m = m^{\left(e^{\left(2^{1025}-2\right)}\right)} \mod n

先程のカーマイケル関数の結果と組み合わせることで、以下の式を導けます。

e^{\left(2^{1025}-2\right)} = 1 \mod \lambda(n)

そしてさらにこの式を、カーマイケル関数の定義に照らし合わせると、以下のようになります（「最小」の部分は未証明です。）

\lambda(\lambda(n)) = 2^{1025}-2

ずいぶんとシンプルな式になりました。さて、ここから $A$ を適当な整数として、 $A \lambda(n)$ を求めていきます。求めたあとに、以下の式を求めることで、乗数をとても小さくすることができます。適当な整数がかかっていても、 $m^{A\lambda(n)}=1$ なことにはかわりないので、問題ありません。

e^{\left(2^{1025}-2\right)} \mod A \lambda(n) \rightarrow \mathrm{small\ value}

では、どのようにして、 $A\lambda(n)$ を求めればよいでしょうか？カーマイケル関数は、 $m = pqr$ (p,q,rは全部素数)だったとすると、

\lambda(m) = \mathrm{lcm}(p-1,q-1,r-1)

のようになります。ここで、計算結果が $2,3,5,11$ だったとすると、もともとの値の候補は、これらをかけ合わせた何かになるはずです。例えば

2 \times 3 = 6 \rightarrow 6 + 1 = 7 2 \times 5 = 10 \rightarrow 10 + 1 = 11 2 \times 11 = 22 \rightarrow 22 + 1 = 23 2 \times 3 \times 5 = 30 \rightarrow 30 + 1 = 31

のようになります。このように組み合わせをすべて列挙し、全部掛け算を求めることで、 $A\lambda(n)$ が求まるはずです。（多分指数を考慮に入れる必要はありますが、今回はなんかこれでうまくいきました。指数を考慮に入れる場合はおそらく重なるのは低い次数のものなので、低いものを何度かかければいいのかなと思っております。）

あとは、カーマイケル関数の定義よりこの結果が素数になっていてほしいので、素数であるもののみをフィルタリングして、すべての積を求めました。

全体の流れとしては、

$2^{1025}-2$ を素因数分解する(factorDBを用いれば可能)
素因数分解した値の組み合わせを列挙し、全ての積を求め、 $A\lambda(n)$ を求める
$X = e^{\left(2^{1025}-3\right)} \mod A\lambda(n)$ を求める
$c^X \mod n$ を求める

とすると、求まります。以下がソースコードです。

from Crypto.Util.number import *
import itertools
import math

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680

lambda_lambda_divs = [
 2,
 3,
 5,
 17,
 257,
 641,
 65537,
 274177,
 2424833,
 6700417,
 67280421310721,
 1238926361552897,
 59649589127497217,
 5704689200685129054721,
 7455602825647884208337395736200454918783366342657,
 93461639715357977769163558199606896584051237541638188580280321,
 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737
 ]

lambda_lambda = 1
for d in lambda_lambda_divs:
    lambda_lambda *= d

assert lambda_lambda == 2**1025-2

lambda_candidate = 1

for d in lambda_lambda_divs:
    lambda_candidate *= (d+1)**10

cand = lambda_lambda_divs[:5]

res = 1
cnt = 0
for L in range(0, len(lambda_lambda_divs) + 1):
    for subset in itertools.combinations(lambda_lambda_divs, L):
        print(f"{cnt}/{131072}")
        cnt += 1
        a = 2*math.prod(subset)+1
        if isPrime(a):
            res *= a

print(res.bit_length())
p = pow(e,2**1025-3,res)
pt = pow(ct, p, n)
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())

実行結果

...
131068/131072
131069/131072
131070/131072
131071/131072
464441
CTF{Recycling_Is_Great}

追記

ところで、このソースコード、 p = pow(e,2**1025-3,res) この部分に時間がかかります。実は、この部分、計算している内容は p = pow(e,-1,res) と同じなので、これに書き換えることでめちゃ早く計算が終わります。終わってから教えられました。どうして気づかなかったのか、悲しみです…

ELECTRIC MAYHEM CLS

問題概要

考察/方針

実装、結果

Cycling

問題概要

方針

追記

Discussion