ECDSA 評 価 報 告 書2002 年 11 月 5 日

日本電信電話株式会社
岡本 龍明

 評価報告書
 年  月  日 はじめに
本評価報告書では、 の最近報告された攻撃法を中心にして、 の安全性評価を示す。また、  に対する攻撃法との比較／関連についても述べる。
なお、 仕様記述や既存の攻撃法に対する安全性評価については既に    などで報告されているため、本報告書では記述しない。本報告書で用いる記号等は      に準拠することとする。

     による の攻撃法
文献  には、 の  種類の攻撃法が報告されている。以下、それらの概要について解説する。

攻撃法 （重複署名）

この攻撃法は、重複署名   と呼ばれており、署名者が  つの異なる文書 ½ ¾ に対して共通の署名 を作ることができるという攻撃である。このことは、署名者が署名の否認をすることに悪用され得る。つまり、署名者はある相手に 文書 ½ （例えば、借用書）への署名として を渡しておき、後にその文書 ½ に対する責務を果たす必要が生じた段階で、文書 ¾ を提示して、署名 は文書¾ に対する署名であり文書½ に対して署名を付けた事実は無いと主張することで、文書 ½ に対する責務を回避しようする攻撃である（つまり、否認不可性 ! に対する攻撃である。）
以下  に対して重複署名攻撃が可能なことを示すが、幸いなことに、署名者が ½ ¾ の全てを開示した段階でその署名者の秘密鍵が露見する。従って、この  に対する重複署名攻撃は、実際的な意味で有効な攻撃とはなり得ない。

    この攻撃法の発見の意義は、もしこのような重複署名攻撃法が有効であったとしても従来の安全性の観点（適応的選択文書攻撃に対して存在的偽造不可など「不正者による署名偽造」の観点）では、安全であるとされることである。つまり、重複署名攻撃法は従来考慮されていなかった新しい観点（「署名者による署名否認」の観点）での攻撃法であり、に対する重複署名攻撃はその最初に発見された具体的攻撃法である。
それでは、 に対する重複署名攻撃法を示そう。まず、 つの文書 ½ " ¾ に対して重複署名攻撃を行おうとする署名者は、鍵生成手順
において以下のように秘密鍵 " 公開鍵 を生成し、さらに  つの文書に対する重複署名を作成する。

      をランダムに選ぶ。
 $   を計算し、 $  とする。
 $   &    ' "  $  とし、公開鍵  を公開する。
(#  $     &  '  を計算し、文書  と  に対する重複署名を  とする。
 の署名作成手順から、明らかに  は、文書  の正しい署名となっている。そこで、 が同時に  の署名にもなっていることを示そう。まず、 $   &    ' "  $       '  である。文書  、署名  の署名検証手順において、
 $    &   $   &  $    &       $  $   $   
従って、 の !座標は  に一致することより、署名  は文書  に対する署名検証にも合格する。つまり、 は文書  および  の重#
#%#½½½½½¾½½¾½¾½½¾½¾¾¾¾½¾½½½¾½¾½¾

複署名となっている。

攻撃法 （脆弱性）



この攻撃法は、脆弱性 ')* と呼ばれており、文書に対する正しい署名 を得ると、署名偽造者が同じ文書に対する別の署名を偽造できるという攻撃である。
この攻撃法は、以下のように行われる。

                       では、 をの !座標の表現とするため、署名検証では、
が$ &の !座標の表現と一致するかどうかをチェックする。このとき、 の代わりに  $  を用いると、  $
 &   $   $   となり、  と の !座標は同一であるため、結局 は  の !座標の表現と一致する。従って、文書に対する正しい署名 があると、  $  としたとき、  も同じ文書に対する正しい署名となる。この攻撃法の本質は、署名検証において、楕円曲線上の点の !座標の情報のみを用いるため、 !座標が同じ別の点（ !軸に対称な点）に関する署名も署名検証に合格することによる。なお、このことは、上で述べた攻撃法 （重複署名）や以下で述べる   の攻撃法でも利用される。
さて、以下ではこの攻撃法（脆弱性）の位置づけについて考察する。
通常の偽造においては、署名偽造とは、それまでに得た正しい署名 付き文書と異なる文書  に対する署名を偽造することであると考えられてきた。このことは、同じ文書に対して複数の署名が存在しても実効上の攻撃にはならないという考えに基づいている。しかし、文書を額面の金額（例えば、 万円）としてその署名 を電子マネーと考えると、同じに対して別の署名 を偽造することは、電子マネーの偽造と考えることも可能である。従って、同じ文書に対しての署名偽造が望ましくない応用分野もあり得ることに注意されたい。
一方、署名方式の望ましい安全性は、「適応的選択文書攻撃に対して存在的偽造不可」と考えられているが、これについては、 つのモデルが考えられる。 つは、同じ文書に対して複数の署名が存在しても実効上の攻撃にはならないという考えに基づくモデル（異文書攻撃モデル）
で、選択文書攻撃により 対の署名文書  ½  ½ ½     $ を得て、最終的に偽造者は偽造署名文書対 を $ という条件で出力するモデルである。もう  つのモデル（同一文書攻撃モデル）は、以下の点を除いて上で述べたモデルと同じであるが、異なる点は、偽造署名文書対の条件が      $     となる点である。つまり、異文書攻撃モデルでは、署名を $
偽造する対象となる文書  は選択文書攻撃で利用した文書 ½
と異なっている必要があるが、同一文書攻撃モデルでは、仮に$ であっても、$    であればよい。
この  つのモデルの観点で、 が署名に通常要求される安全性のレベルである「適応的選択文書攻撃に対して存在的偽造不可」を満足するかどうかを考えると、異文書攻撃モデルでは特にこの観点で具体的な                  

 
 %

     

攻撃方法が知られているわけではないが、同一文書攻撃モデルでは、ここで述べる「脆弱性」が「適応的選択文書攻撃に対して存在的偽造」となる。つまり、同一文書攻撃モデルでは  は「適応的選択文書攻撃に対して存在的偽造不可」を満足しないことになる。
なお、 は + , により「適応的選択文書攻撃に対して存在的偽造不可」であるという証明が報告されているが、今回の攻撃法の発見により、このような + , では、上で述べた同一文書攻撃モデルにおける安全性が考慮されていないことが明らかとなり、+, による安全性証明の限界が示されたことになる。

 

 による  の攻撃法

- により  種類の攻撃法が報告されている %。 つ目の攻撃法は、  の構成要素として共通鍵暗号に ./ 暗号（!' ）を用いた場合の攻撃法である（  は、ハイブリッド暗号であり、共通鍵暗号およびメッセージ認証と組み合わせて利用される。このとき用いる共通鍵暗号の一典型例が ./ 暗号である）。もう  つは、上で述べた  の攻撃法 （脆弱性）と同様の攻撃法であり、やはり脆弱性
')* と呼ばれる。

攻撃法 （ 暗号利用方式への攻撃法）  の構成要素として、共通鍵暗号として ./ 暗号を用いるものとする。このとき、選択暗号文攻撃に対して攻撃可能である（強秘匿でない）。つまり、公開鍵暗号として求められる安全性である「適応的選択暗号文攻撃に対して強秘匿  0!  」を満足しないことになる。
共通鍵暗号として ./ 暗号を用いたときは、 $をから鍵生成関数 12 で生成された値とし、平文の長さに応じての長さが可変となり、さらにそのプレフィックスは同じである（つまり、
 ならば の のサイズが ビットのときと  ビットのとき、ビットのプレフィックスはいずれの場合も同一となる）。このとき、平文に対する暗号文 は、   


 


 $      $   となる。

(そこで、次のような「強秘匿性に対する適応的選択暗号文攻撃」を考える。まず、敵は  つの平文 ¼ ½  ¼ $ ¼   ½ $ ½   "  ¼  $ ½  $ "    $   を暗号オラクルに送る。暗号オラクルは、そのいずれかの平文  （    をランダムに選びその暗号文 を敵に送る。このとき、

  

 $      $   
ここで   を の  ビットのサフィックスとすると、敵は、  $   $      を得る。そこで敵は、  を  の  ビットのプレフィックスとしたとき、  $         を作成し、選択暗号文攻撃として   を復号オラクルに送る。暗号文のサイズが  ビットであるため、,  の鍵は   $    となり、  の,  による検証は合格となるため、復号オラクルは   の復号結果である  $      を敵に送る。これにより、敵は正しい の値を得ることができる。つまり、適応的選択暗号文攻撃により強秘匿性を破ることになる。

攻撃法 （脆弱性）

 の場合と同様に、  においてデータ暗号やメッセージ認証に用いられる鍵は、楕円曲線上の点の !座標のみが用いられる。従って、
がと同じ !座標の値を持つことより、正しい暗号文$ $          を得た敵は、別の正しい暗号文

  $      $   を作ることが可能となる。つまり、  は脆弱 ') であり、頑強性 !')* を満足しない。従って、公開鍵暗号に求められる安全性「適応的選択暗号文攻撃に対して強秘匿  0!  」を満足しないことになる。

 その他
上で述べた特定の攻撃に関する  の安全性の観点以外で、の安全性に関する問題として、 の仕様のバリエーションと楕円曲線パラメータの安全性評価について述べる。

 仕様と  仕様の差異について の仕様には、  に提案されている  仕様と、米国で標準化されている 0 .#3#4 仕様が存在する。
    では、両者の違いは推奨する楕円曲線パラメータ擬似乱数生成器を指定しているかの  点ということになっているが、それ以外に、以下の点が異なっていると思われる。
ハッシュ関数  0 では 5 ! のみに限定されている。

 

楕円曲線の位数 のサイズがハッシュの出力サイズより小さい場合の規定が異なる。 0 では、 $ ' を行うのに対して、 では、 $  の先頭   ビット ' とする。

 

特に後者の相違点により、 で推奨している楕円曲線パラメータリス
トのうち 4 ビット未満のもの 例えば、6) のものなど）では、 0と  で互換性がないと思われる。一方、楕円曲線のパラメータサイズが 4 ビット以上で、ハッシュ関数として 5 ! を使う場合は、実効上は互換性があると考えられる。



安全性評価の階層について

暗号の評価では、様々な階層／レベルにおいてそれぞれの階層固有の安全性評価を行なう必要がある。例えば、 の場合では、基本的なレベル（下層）の安全性として基本問題（つまり楕円曲線上の離散対数問題）の安全性があり、その上位層の安全性としてスキーム（ ）の安全性がある。
ここで、基本問題の安全性評価とスキームの安全性評価は独立の問題であり、また基本問題の安全性は上位のすべてのスキームに共通である
ことは明確に意識されるべきであろう。
たとえば、"  においては、どのような楕円曲線の（安全な）パラメータを選ぶべきかどうかは、全てのスキーム（ " 5"

4 ）の共通の事項として記述されており、このことは明らかに  "5"   に限らずその他のすべての楕円曲線上のスキームにおいても共通である。
従って、  としては、いくつかの基本的な問題（素因数分解問題、離散対数問題、楕円曲線離散対数問題）については、各スキーム固有のパラメータとは独立に、スキーム間共通のパラメータ選定基準、推奨パラメータ等を規定すべきであると考える。たとえば、楕円曲線のパラメータについては、"  のパラメータは、各スキームに付属する推奨パラメータとして扱われているが、楕円曲線暗号系スキームに共通の規定として、安全な楕円曲線離散対数問題を構成するための推奨パラメータという扱いにすべきである。
一方、 で記述されているような広く認知されている選定基準を条件とすることは望ましいが、特定のパラメータ設計方針に偏るべきでないと考える。また、利用可能な有限体の規定も素体や  の拡大体といった特定の体に限定する必然性は無いと考える。例えば、  %4% では、本文でスキームの規定を行い、楕円曲線パラメータは、スキーム共通のパラメータとしてそのデータ表現も含めて 7 で扱われており、また、一般の有限体の利用が可能となる表現方式、パラメータ設計基準が示されている。
さらに、鍵長についても、  としての見解を明確に提示すべきと思われる。 では、鍵長が 4 ビット未満のパラメータも推奨パラメータに含まれているが、  としては、このようなパラメータを推奨しないことを明示するべきと考える。実際、   では、###% ならびに #%#% では、4 ビット以上が安全であるという記述があるにもかかわらず、#( では  の推奨パラメータを容認しているように思われることより、 ビットや 6 ビット鍵が利用される余地を残している。（さらに、上で述べたように、4 ビット未満のパラメータを用いた場合は、 0 仕様と  仕様で互換性が保証されない。）

 まとめ
最近発見された  の  つの攻撃法を中心に安全性の評価を行った。また、  に対する同様の攻撃法についても、 との比較検討を行う観点より、評価を行った。
結論から述べると、 の  つ目の攻撃法（重複署名）は、従来の8安全性の概念に無い新しいタイプの攻撃法であるが、今回示された攻撃法は実効的な意味が無く、特に考慮する必要は無いと考える。また、もう つの攻撃法（脆弱性：')*）は、従来知られている安全性（適応的選択文書攻撃に対して存在的偽造不可）の観点で、強いモデル（同一文書攻撃モデル）において、この安全性を破るものである（つまり、偽造が可能となる）。しかし、同じ !座標の点を用いた署名が複数ある場合はそれらを同一視するなどの運用上のルールを追加することで、この攻撃を回避することは比較的容易である。従って、実用上の問題としてはこの攻撃は深刻ではないが、運用上はこれらの攻撃が存在することを留意して対処すべきであろう。
但し、 の他の外部評価者も述べているように、もし可能であるならば安全性の証明が可能となる方式に仕様変更をすることが望ましいと考える。
一方、  への攻撃は、 への攻撃法と比べると、実効上意味のある攻撃になっており、より深刻である。特に、./ 暗号を用いた場合は、固定文書長に限定するなどの仕様変更を行う必要があり、現仕様のままでは利用を推奨できない。一方、脆弱性の問題は、  が0!  レベルの安全性を満足しないことを意味しているが、の脆弱性の問題と同様に運用レベルで対処可能である。
なお、本文では記述しなかったが、 !座標のみを利用することによる脆弱性の問題は、  最終リスト候補になっている 5  にも存在することを指摘しておく。
（つまり、5 は、5 方式が一般的に持つ「'!!-!' 攻撃」に対する脆弱性のみならず、5固有の脆弱性 ')* を持つことになる。）
さらに、  の推奨暗号リスト（およびそのサポートドキュメント）においては、鍵サイズを含めた楕円曲線暗号パラメータを全ての楕円曲線暗号系スキームに共通の推奨規定として明確に規定するべきであると考える（現状では、個々のスキーム固有のパラメータと共通的パラメータの規定が混同されている）。その際、  %4% の 7で規定されているような広く認知されている選定基準とし、特定のパラメータ設計方針や特定の有限体に限定すべきでないと考える。

参考文献
 暗号技術評価報告書（ 年度版）   /  年 % 月6  " " 9#" -:" #" ,!;" 9#  '" 0# #< 2= * > ,-   -'" # >
*?" ;0 ((" !@" #3%A  #% -" @#< >  /  > ) 1* *!
" :)  -<BB-#BB  ') #3