シミュレーションによる FIA 5

前回は，RSA への FIA で秘密鍵が見えることを確認しました． 今回は，共通鍵暗号である AES を狙います． 暗号化の終盤で，値の分からない 1 byte に fault が入ることで，数組の暗号文から秘密鍵が復元できます． この種の攻撃は Differential Fault Analysis と呼ばれます．

AES

AES は，128 bit ブロックを 4*4 bytes の行列として扱います．

また，AES にはいくつか演算があります．

• SubBytes：全 16 bytes に S-Box の変換を適用します．
• ShiftRows：r 行目を左に r bytes シフトします
• MixColumns：各行に GF(s^8) 上の行列を左から乗算します．入力 1 byte が変化すると，出力は必ず 4 bytes 変化します．
• AddRoundKey：RoundKey と XOR します

以上の計算を複数回適用することで AES-128 は達成されます．

AddRoundKey(K0) → (SubBytes → ShiftRows → MixColumns → AddRoundKey) * 9 → SubBytes → ShiftRows → AddRoundKey(K10)

また，RoundKey をどのように生成するかについて，その処理を鍵スケジュールと呼びます． 上記の記事で使用している変数をそのまま使いますが，w[i] = w[i-4] ⊕ f(W[i−1]) という漸化式なので，W[i−4] = W[i] ⊕ f(W[i−1]) とたどることができます． なので，最後のラウンド鍵 (K10) が分かれば，K9, K8,...，マスター鍵が復元できるということになります． したがって，DFA では K10 の 16 bytes を求めることが必要です．

Fault の注入

DFA では，常に同じ平文を 2 回暗号化し，片方だけに fault を入れて，2 つの暗号文の XOR を見ます． つまり，Δ = A ⊕ A' ですが，このΔ が，AES の各演算でどのように処理されるかがを気にする必要があります． 具体的に考えると，1 byte の fault が MixColumn を通過すると，4 bytes の fault へと伝搬します． さらに，SiftRows と 2 回目のMixColumns を通過することで，16 bytes の fault へと伝搬します． つまり，2 回の MixColumns を通ると完全に拡散してしまうということになります． ゆえに，ラウンド 1~7 に fault を入れると，暗号文は完全にランダム化され，差分が分かりません．

最終ラウンドでの fault

ラウンド 10 の SubBytes 入力の 1 byte (x) に差分 ε を入れるとします． その byte の暗号文出力は，ShiftRows で位置 j に移るとして，以下のようになります

C [j] = S(x) ⊕ K10[j]
C'[j] = S(x ⊕ ε) ⊕ K10[j]

そして，これに対して差分をとると K10 が消えます．

ΔC = S(x) ⊕ S(x ⊕ ε)

暗号文は変化が 1 byte だけなので，ΔC は計算が可能です． あとは，全ての (x, ε) の組（2^16通り）を試し、S(x) ⊕ S(x⊕ε) = ΔC を満たすものを列挙したうえで，見つかった x から K10[j] = C[j] ⊕ S(x) とすればよいことが分かります．

CTF

今回も CTF を用意しました． ある AES-128 暗号装置にグリッチを撃ち，9 ラウンド目の入力の row = 0, col = c（c = 0..3 は分かっている）のバイトを化けさせた暗号文を，列ごとに 3 組ずつ取得しました． フォルト値は不明です． 同じ鍵で暗号化されたフラグ（C_FLAG, AES-128-ECB）を復号してください．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import hashlib, sys

PAIRS = {0: [('bc43f11c0d8bc70ca693c49ee8bac968', '6743f11c0d8bc7dda693d69ee814c968'), ('85f24304c7757082013fbae469eff4c7', '63f24304c7757066013fc7e46968f4c7'), ('46477dc12a14da45339c63718486d5d3', '19477dc12a14da9d339cee71841bd5d3')], 1: [('75747c2945d8ec962ffb458c7300a7f8', '75a57c29d5d8ec962ffb455d73008af8'), ('590968351dba340dc444dbc4f654b398', '59f568355aba340dc444dbacf6546098'), ('e4c3edfe425438a58cd86833f96b16b7', 'e404edfeb85438a58cd86840f96b54b7')], 2: [('cd300794fb12a32aac23f4f0e7f558ca', 'cd309f94fbaca32aa223f4f0e7f558b4'), ('51d632aba4bbda208511e1af7406207c', '51d6bcaba4c4da200211e1af74062071'), ('a181e70229aa950e4606f7e7d555042d', 'a1813802293a950e4906f7e7d55504a3')], 3: [('35a6776bc30f76a36c0f2d0352d5d4fd', '35a6776ac30f96a36cfb2d0307d5d4fd'), ('0c71b6ec32d53b7dce18b298963f5e84', '0c71b60d32d5367dce7ab298873f5e84'), ('26d2554ad6cd02c8a44c0ccca7ea9a4b', '26d255bfd6cd1ac8a49f0ccc00ea9a4b')]}

C_FLAG = "94015c50392335fd2f7b8bbfe75bfb450c2cbd281f6ff06547678eea723db6da"

FLAG_SHA256 = "1dbf8476c7669a1460142924a8b69d48f063ca2892c9e53d582890f75c3cc6f5"

if __name__ == "__main__":
    for col, lst in PAIRS.items():
        print(f"col={col}:")
        for g, b in lst:
            print(f"  good={g}\n  bad ={b}")
    print("C_FLAG =", C_FLAG)
    if len(sys.argv) > 1:
        ok = hashlib.sha256(sys.argv[1].encode()).hexdigest() == FLAG_SHA256
        print("Correct!" if ok else "Wrong...")