暗号攻撃法
一般に,共通鍵暗号や公開鍵暗号では「秘密鍵を求める」ことが暗号解読の攻撃目標であり,またハッシュ関数では「衝突するような異なるメッセージの組を求める」ことが攻撃目標となる,
暗号攻撃法の種類や現在知られている暗号攻撃法について解説する.
- 解読のレベル
暗号の解読レベルには,完全解読と部分解読がある.
- 完全解読
- 暗号文から平文全体を求める
- 公開鍵から秘密鍵を求める
- 部分解読
- 解読のモデル(安全性のレベル)
- 一方向性 (Onewayness: OW)
暗号文から平文を求めるのは困難
- 強秘匿性 (Semantic Security: SS)
暗号文から平文のどのような部分情報も得ることは困難
- 識別不可能性 (Indistinguishability: IND)
暗号文 m0, m1 が平文 c0, c1 のどちらを暗号化したものか識別できない.
- 頑強性 (Non-Malleability: NM)
暗号文が与えられたとき,ある関係性を持った別の暗号文の生成ができない.
- 暗号の攻撃タイプ
暗号の攻撃タイプには以下の種類がある.
- 受動的攻撃
暗号通信を受信し,その情報のみから解読を試みる.
- 能動的攻撃
送信者に様々な質問をし(暗号文を送り),その回答(復号結果)の情報 を利用して解読を試みる.
- 暗号の攻撃モデル
暗号攻撃は解読のために攻撃者が利用できる条件により,以下のように分類できる.
- 暗号文攻撃(Ciphertext-only attack: COA)
暗号文だけを利用する攻撃
- 既知平文攻撃(Known-plaintext attack: KPA)
平文とそれに対応する暗号文を利用する攻撃
- 選択平文攻撃(Chosen-plaintext attack: CPA)
平文を任意に選択しそれに対応する暗号文を利用する攻撃(公開鍵暗号 では常に可能)
- 選択暗号文攻撃(Chosen-ciphertext attack: CCA, CCA1)
暗号文を任意に選択しそれに対応する平文が得られる条件で行う攻撃
- 適応的選択暗号文攻撃(Adaptive chosen-plaintext attack: CPA2)
選択暗号文攻撃における暗号文の選択を攻撃中に入手した平文の情報を参考に決定する攻撃
- ディジタル署名の攻撃タイプ
ディジタル署名の攻撃タイプには以下の種類がある.
- 受動攻撃(passive attack; key-only-attack)
公開鍵だけを使って偽造を行う.
- 一般選択文書攻撃(generic chosen-message attack)
署名偽造者があらかじめ選んだ文書に対して真の署名者に署名させた後に,そこで得た情報を用いて第3の文書の署名を偽造する.
- 適応的選択文書攻撃(adaptively chosen-message attack)
署名偽造者が任意に選んだ文書に対して真の署名者に署名させた後に,そこで得た情報を用いて第3の文書の署名を偽造する.
暗号やディジタル署名が破られたと言われる場合でも,上記のどの条件で解読されたかを見極める必要がある.現実に暗号が使われる環境で解読されたのならば,危険が現実的になり直ちに対応が必要である.しかし,現実には起こり難い条件ならば,直ちに心配する必要はない.
なお,アルゴリズム固有の脆弱性を利用せずに (効率は非常に悪くとも)
確実に攻撃を成功させることができる方法のことを「最良の攻撃方法」という.ここで,最良というのは,全てのアルゴリズムに対して攻撃方法として有効であるという意味であり,安全性の高いアルゴリズムであってもこの攻撃方法で必ず攻撃が成功するということである.このことから,安全性の上限は最良の攻撃方法を利用したときの強度で評価される.
共通鍵ブロック暗号の攻撃法は全ての鍵をしらみつぶしに探索する Brute-force Attack と暗号アルゴリズムを解析し,統計的特性を利用して鍵の探索範囲を限定する Short-cut Attack に分類できる.
現在,多くの共通鍵ブロック暗号に適用できる強力な解読法として以下の 3つが知られている.
- Brute-force Attack
- 鍵の全数探索法(暗号文単独攻撃)
全ての共通鍵暗号方式に対して適用可能という意味で,最良の攻撃法である.
- Short-cut Attack
公開鍵暗号では,攻撃は暗号の安全性のベースとなっている素因数分解問題や離散対数問題といった数学上の問題を解くことに対応している.
- 素因数分解問題(Integer Factorization Problem)
合成数 $N$ が与えられたときに、$N$ を素因数の積に分解する問題.
- 離散対数問題 (Discrete Logarithm Problem : DLP)
有限群 $G$ の生成元 $g$ と $y = g^x\ (x \in G)$ が与えられたときに $x$ を求める問題.
有限群 $G$ は有限体上の乗法群もしくは有限体上定義された楕円曲線の加法群がとられることが多く,後者の場合は楕円曲線離散対数問題と呼ばれる.
これらの問題の代表的な解法を示す.
- 素因数分解問題の解法
- p-1法、p+1法
合成数 $n$ の素因数 $p$ に対して、それぞれ $p-1$,$p+1$ が小さい素因数の積に分解されるとき有効な方法
- Fermat法
合成数 $n$ の素因数 $p$,$q$ に対して,$|p-q|$ が小さい場合に有効な方法
- 楕円曲線法
$Z_p$ 上の楕円曲線の位数が小さな素数の積に分解できるとき有効な方法
- 2次ふるい法
2次合同式 $k^2 = l^2 \bmod n$ を満たす $k$ と $l$ を求め,$\gcd(k \pm l, n)$ より $n$ の素因数を求める方法
- 数体ふるい法
2次ふるい法を一般化したもの
- 離散対数問題の解法
- Pohlig-Hellman法
$y = g^x \bmod p$ において,$g$ の位数 (原始根の場合 $p- 1$)
が小さな素数の積に分解されるとき有効な方法
- 指数計算法
ある素数の集合に対する対数を求め,それを利用して離散対数を求める方法
- 数体ふるい法
指数計算法の一種で、素因数分解問題に対する数対ふるい法を離散対数問題に応用した方法
- 誕生日攻撃
ハッシュ関数の出力長が $N$ のとき,おおよそ $2^{N/2}$ 個程度のメッセージ
$M'$ に対してハッシュ関数 $h$ を計算することで、$h(M) = h(M')$ なる $M'$ を見出すことができる (Birthday attack).この Birthday attack に対処するために,ハッシュ関数の出力長はある程度長くなければならない (128bit以上).
誕生日のパラドックス (Birthday paradox)
$n$ 個のパターンから重複を許して順次選択する場合,約 $\sqrt{n}$ 個選択すると同じパターンが $1/2$ の確率で存在する.
$n$ 個から $k$ 個選ぶとき重複しない確率 $P$ は次のようになる.
$P = n(n-1)(n-2)\cdots(n-k+1) / n^k = n! / \{n^k(n-k)!\}$
したがって,重複が発生する確率は,
$1 - P = 1 - n! / \{n^k(n-k)!\} \gt 1 - e^{-k(k-1)/2n} \fallingdotseq 1 - e^{k^2/2n} $
ここで, $1 - x \le e^{-x}$ としている ($x$ が小さいとして) .
この確率が $0.5$ 以上になる $k$ は,上式より次のようになる.
$k = \sqrt{2(\ln 2)n} ≒ 1.18 \sqrt{n} \fallingdotseq \sqrt{n}$
これより,$23$ 人集まるとその中に誕生日が同じ人が $1/2$ の確率で存在することが分かる. これは,誕生日のパラドックスと言われる.直感的な感覚が事実とは大きく異なる例である.
- 再生攻撃
- 攻撃者が通信を傍受し,送信メッセージのコピーを再度送信先に送り付ける.
- 再生攻撃に対する対処
タイムスタンプやシーケンス番号をメッセージに付加した後にMACを計算する(正常な処理では,同じ送信メッセージは発生しない).
- 統計的解析
ブロック暗号に対して使われてきた攻撃手法をハッシュ関数に適用したものである.
- Multi-Block Technique
ハッシュ値として数ビット程度しか違わないような値(Near
Collision)を出力する元データの組み合わせの中から,複数回ハッシュ値を計算させることでその違いがキャンセルされ,最終的に同じハッシュ値が出力される組み合わせを探す方法.
- Differencial Attack(差分解析)
元データをわずかに変更した場合にハッシュ値がどう変化するか差分を取ってチェックし,そこからコリジョンが起こる組み合わせを探る.データ列の中のあるビットの値を変更してもそれが最終的なハッシュ値に影響を与えない
Neutral Bit と呼ばれるビットが MD4/SHA 系のハッシュ関数に存在する可能性があると言われる.
サイドチャネル攻撃
C.Kocher らにより提案された実際に暗号が実装された装置に対する攻撃法である.
実行時の漏洩情報,すなわち,暗号処理装置外部から計測可能な情報(例えば、計算時間や電力消費量など)と,秘密鍵等の秘密情報との間の相関関係を利用して秘密情報を推定しようとする攻撃手法であり,特にスマートカード(ICカード)に対しては大きな脅威となりうることが報告されている.
サイドチャネル攻撃の例として、タイミング攻撃、DPA攻撃などが知られている.
- タイミング攻撃
漏洩情報として計算時間を用いて秘密情報を推定する.秘密情報推定の際に,統計的処理を行って推定する方法や一度の計算時間から秘密情報を割り出す方法がある.
- DPA(Differential Power Analysis)攻撃
漏洩情報として電力消費量を用い,統計的処理を行うことにより.秘密情報を推定する. この攻撃は,サイドチャネル攻撃の中でも最も強力な攻撃方法の一つである. DPA攻撃を防ぐための要件は以下の二つである.
- 秘密情報と計算実行手順とが独立である.
- 計算対象の値がランダム化されている.
- Fault-Based Attack
ICカード等のタンパーフリーデバイスの計算結果の誤りを利用した暗号解読法(1996.9.25:アメリカの情報テクノロジー研究所Bellcore).
公開鍵暗号系で用いられているべき乗剰余演算等の代数演算を実装したタンパーフリーデバイスに,放射線や高電圧をかけたり,瞬間的にクロックの周波数を上げたりすることで故意にエラーを起こさせ,その結果誤った計算結果と元の正しい計算結果からそこに格納されている秘密(鍵)情報を得る.