III.3.1.5 ElGamalへの適用

故障利用解析を利用してElGamal署名に使用された秘密鍵を導出する方法を述べ る． 以下のElGamal署名において，乱数$x$を直接操作することにより，RSA同様に秘密 鍵$x_a$を導出することができる[And96,BD+96]．

まず，DSAやSchnorr署名などでも用いられているElGamal署名方式を説明する． メッセージ$m$に対するElGamal署名は，署名用の秘密鍵$x_a$と乱数$x$を用い， 次の$r$と$s$が署名となる．

$$\begin{eqnarray*} r &=& g^x \bmod p\\ s &=& \frac{hash(m)-x_a\cdot r}{x} \bmod (p-1) \end{eqnarray*}$$

ここで，乱数$x$は，$(p-1)$を$x$で割り切れない必要がある．また，乱数$x$は メッセージごとに毎回異なる独立な値を用いなければならない．

図 III.13: ElGamal署名

ElGamal署名で用いる乱数生成に着目すると， 擬似乱数生成がソフトウェア(カード上のコード)で行われる場合の 乱数直接操作攻撃や，ハードウェアによる擬似乱数生成の場合の乱数固定攻撃 などが考えられる[ZM97]．

これらICカード中の擬似乱数生成器を操作する攻撃方法に 対しては，フォールトトレラント技術を用いたり，擬似乱数生成器の生成結果の検証を行うことにより擬似乱数生成器の改竄を困難にすることができ， 耐タンパーなLSIを設計するのと同じぐらい重要であると指摘している．

乱数直接操作攻撃(ソフトウェア)

擬似乱数生成器の内部ステータスを操作することにより，

1. 擬似乱数生成の内部ステータスを保持しているメモリの位置を探 す(鍵など重要な情報はRAMの若いアドレスに配置されること が多いと言われている[And96])．
2. 物理的ストレスなどにより，擬似乱数生成器の元の内部ス テータス$S_{info}$を全ビット1など自明な値に置き換える．
3. 署名用鍵$x_a$を次の手順で求める．
   1. 既知の内部状態(全ビット1など)の擬似乱数生成器 から生成される乱数$x_0$を計算する．
   2. 既知の乱数$x_0$より署名鍵$x_a$を計算する．
      
      $$x_a = \frac{hash(m)-s\cdot x_0}{r}\bmod (p-1)$$
      
      

乱数直接操作攻撃(ハードウェア)

定格よりも低い駆動電圧を与えたり，定格外の温度環境 など，ハードウェアの擬似乱数生成器は異常な環境では予測可能な乱数を生成することがある [AK]．この場合，乱数を直接操作できるため，以下のように署名用の 鍵が求まる．

$$x_a = \frac{hash(m)-s\cdot x_0}{r}\bmod (p-1)$$

乱数固定攻撃

これまでに紹介した方法では，既知の乱数値を用いていたが， 固定乱数値(値は既知でない)を用いても攻撃ができる． 攻撃者は固定の乱数$x_0$を用いて二つのメッセー ジ$m_1$と$m_2$に署名を行わせる．すなわち，

$$r_0=g^{x_0}\bmod p, s_1 = \frac{hash(m_1)-x_a\cdot r_0}{x_0}\bmod (p-1)$$

$$r_0=g^{x_0}\bmod p, s_2 = \frac{hash(m_2)-x_a\cdot r_0}{x_0}\bmod (p-1)$$

$m_1$と$m_2$に対する署名の結果から$x_0$が求まる．

$$x_0 = \frac{hash(m_1)-hash(m_2)}{s_1-s_2}\bmod (p-1)$$

したがって，署名に用いた秘密鍵は

$$x_a = \frac{hash(m_1)-s_1\cdot x_0}{r_0}\bmod (p-1)$$

この乱数を固定させた攻撃方法は，擬似乱数生成器を操作し既知の 乱数を出力させる攻撃方法よりも適用が容易であると思われる．