「デジタル証明書」とは一体どんなもの？ （４択）

• 「デジタル証明書」とは一体どんなもの？：ITpro

という記事がありました。
「説明として誤っているものを1つ選んでください」
なので気をつけて解きましょう。

「細かい技術のことはいいから証明書って何だか理解するのも大切」
かと思うんですが
「細かい技術のこと無しに証明書って何だか理解するって丸暗記?」
とも思い
この間を上手に埋めるって方法は何かないものですかねぇ．．．

ハッシュ函数の困難性・耐性って?

去年末の MD5 の隙をついた偽 CA 証明書の生成以降
ハッシュ函数に対する攻撃の記事に関してちょっと敏感になってるんですが
ちょっと混乱してるので攻撃方法に関して再確認しました
Wikipedia の「ハッシュ関数」を読んだりしただけなんですが

ハッシュ函数が満たすべき・持つべき性質として

• 原像計算困難性
• 第 2 原像計算困難性
• 衝突困難性

ってのが挙げられています
去年末のやつは

• 選択プレフィックス衝突? (chosen prefix collision)

ってのを起こすのが簡単だってことで可能となった攻撃なんですが
これは衝突困難性と第 2 原像計算困難性の間にいる感じかな?

攻撃方法は色々考えられるわけですが最終的には総当たりすることになります
総当たりするまでに下拵えして総当たりの計算量減らそうってのが研究されてます
なので、減った結果の総当たりの量のことを困難性の数字での表現として取ります

衝突困難性

これは
「ハッシュ函数に対してハッシュ値が等しくなる 2 つのデータをみつけなさい」
という問題を解くのが難しいということ

攻撃方法というか、「誕生日のパラドックス」って言われてるのがありまして
「1 つのクラスに同じ誕生日の人がいる確率が 1/2 以上になるのはクラスが何人から?」
っていう問題の答が 23 人ってのは意外と少なくない?
というものです

この問題の意味が取りづらいんですが
「誰か一人選んだときにその人と同じ誕生日の人がクラスにいる確率」ではなくて
「クラス全員の誕生日を並べたときに同じものが2つ以上ある確率」を考えています

ハッシュ函数の衝突を起こすっていうのも状況は全く同じでして
誕生日の場合は
「365 日のうちから何回日付を選んでくれば衝突するか?」
でしたが、ハッシュ函数の場合は
「函数の吐くハッシュ値をいくつ取ってくれば衝突するものが現れるでしょうか?」
とになります
で、計算すると、これがハッシュ値の取りうる個数の平方根に近くなることが知られてます

例えば MD5 だと 128bit のハッシュ値なので 2⁶⁴ コのハッシュ値を計算すれば
SHA-1 だと 160bit のハッシュ値なので 2⁸⁰ コのハッシュ値を計算すれば
計算したものの中で衝突してるものがある確率が 1/2 を越える、ということです
なので、それぞれ基本の衝突困難性は 64bit, 80bit と言われていまして
それが研究者の方々によってより良い攻撃方法が発見される度に
困難性がの数字が落ちていって「破られた」とか言われたりしています
まぁ「破られた」っていうのは基本の衝突困難性よりも数字が落ちたときでしょうか

これが、MD5 だと今や、パソコンでもものの数分で計算できるところまで
衝突困難性が落っこちてしまっています

第 2 原像困難性

これは
「ハッシュ函数とデータ x に対して x とハッシュ値が等しくなるデータ y をみつけなさい」
です

RSA による署名では、元データのハッシュ値が秘密鍵で暗号化されています
元データが公開された状態なので第 2 原像困難性が破られてしまうと
どんな偽物の署名が作られる可能性が高くなってしまいます

原像困難性

これは
「ハッシュ函数とハッシュ値 h が与えられたとき、ハッシュ値が h と等しくなるデータ y をみつけなさい」
です
 
第 2 原像困難性のときはハッシュ値 h の元となるデータ x が与えられていたので
それを元に他のデータを生成することができたかもしれませんでしたが
原像困難性の場合はより少ない情報で計算する必要が出てきます

HTTP の基本認証などログイン時の認証用パスワードは
ハッシュ値が保存されていてログイン時に入力されたパスワードのハッシュ値と照合されます
万が一パスワードのハッシュ値が漏れてしまうと
この原像困難性が無くてはパスワードと同じハッシュ値を返すデータが生成されてしまい
なりすましが発生してしまいます


原像困難性は総当たりが妥当な攻撃方法だろうということで
出力される bit 長が困難性として挙げられています
MD5 なら 128bit, SHA-1 なら 160 bit になります

先日の MD5 に対する攻撃というのは
この 128bit が 123.4bit まで落ちたということのようです
こういうのはブレークスルーがおきるとあっという間だったりするので
近々劇的に困難性が落ちるかもしれません

「IT ホワイトボックス」でインターネットの暗号化に関して学んだ

この 4 月から IT ホワイトボックスって番組が NHK 教育でやってまして
初回は村井純さんが RFC って何かとか説明するっていうマニアな番組なんですが
3 回目のタイトルが「メールは盗み見られないのか?」でした
『杜撰な研究者の日記: ITホワイトボックス第３回「メールは盗み見られないのか？」を見ました』
で内容は見てたんですけど昼間に再放送がチェックできたんで見ました
夜には初回の再放送もやってたんで 3 回目もまた再放送あるのかも

例えば暗号の説明としてシーザー暗号から入るんですけど
『つながり‐コンピュータとネットワークのしくみ‐ | 日本科学未来館』の映像とか出て
0 と 1 を白黒の玉で表現して実際に手を動かしてもらっていました
こういう説明がどのくらい効果的なんのかは良く分からないんですが
身体感覚から入るってのは良いんだろうなぁ、きっと
日本科学未来館は楽しそうだなと思いました
台場の RiSuPia には行ったことがあったんですが、こっちも見てみたいな、楽しそう
XOR とか出てきたらどうしようかとドキドキしてたんですが出てきませんでした

公開鍵暗号の話は「錠と鍵」で説明で
デジタルだから錠がいくらでもコピーできるんだ、ってことは言ってなかった
「公開鍵はいま世界で最も良く使われてる暗号」みたいなこと言ってた気がしたんだけど
「RSA は公開鍵で最も良く使われているアルゴリズム」ってこと言いたかったのかなぁ
公開鍵暗号っていうと RSA なんですかね、まぁ、言葉としては流通してると思うんですが
Diffie-Hellman ってそんな大切じゃないのかな? こっちの名前をどっちかっていうと出して欲しい

で、「暗号化なんて普段してないし、メールの内容も見られても困らないし」って発言に対し
「クレジットカードの番号とかネットバンキングとかしてませんか?」って返すわけですが
それもぉメールじゃなくって HTTP の話じゃん!! って思うんですが
まぁ、メールを軸に色々紹介するっていう番組みたいなんで仕方ないのかな．．．
何でウェブじゃなくてメール中心で話組んだんだろうなぁ

面白いなと思ってるんで機会があれば続きも見たいです

「不況に勝つための SSL 投資」

SoftwareDesign 2009 年 3 月号の "Hosting Department" っていう特別連載で
EV SSL サーバ証明書の解説が載ってたんですが
? って思ったところがあったので重箱の隅を備忘録

H-2 ページの上の段落で

EV SSL 証明書も従来の SSL 証明書と同様にセキュアなハッシュ関数を含んでおり

多分これは「ハッシュ関数」ではなくて「電子署名」のことを言っているんだと
この後から特に断りが入らず Windows 環境に特化したような話になってしまって

OCSP 機能では後述のようにブラウザのアドレスバーの表示を緑色に変えることで EV SSL 証明書の有効性を示しますが

IE7 などでは緑で表示するのに OCSP でのチェックを通る必要があるのかもしれませんが
OCSP は通常の証明書でも利用されている機能で EV とは特別な関係にはない、はず
と思ったら Firefox も OCSP 切ると緑じゃなくなったな
OCSP は必須になったんですか? 教えて偉いひと

まぁ、Firefox はオープンソースなのでちゃんと読めばアルゴリズム分かるんでしょうが
他のブラウザに関してはリーバースエンジニアリング的にしか
EV で表示が緑っぽくなるアルゴリズムが分からない状況なので
色々混乱しちゃったりする部分もあるのかなぁ、と思いました
アルゴリズム公開してほしいですネ!!

IIS で SSL するなら certreq.exe が素敵

Windows Server には certreq なんてコマンドがあったんですね
IIS 使っていいて SSL サーバ証明書を導入しようとしたときに
CSR を作るウィザードとか出てくると思うんですが
その API をコマンドラインから叩けるものみたいです
別件で検索してたら

• 任意のサブジェクトを持つクライアント証明書発行 certreq.exe

というページを拝見しまして

• Appendix 3: Certreq.exe Syntax

を見ながらいじってみました。

作ってみた inf ファイルはこんな感じ

[NewRequest]
Subject = "C=JP,ST=Tokyo,L=Chiyoda-ku,O=SSL-PKI,CN=ssl-pki.seesaa.net"
Exportable = TRUE
KeyLength = 2048
MachineKeySet = TRUE
SMIME = FALSE

比較的ミニマルな感じで作ってみました。
Subject の RDN の区切り文字が "," なんですよね。
これは IIS のウィザードでも "," が入力できないのと対応しています。

これを test.inf という名前で保存して

> certreq -new test.inf test.csr

とコマンドを打つと test.csr に CSR が書き出されます。
秘密鍵は Windows の奥底に保存されて眠っているはず。
RFC 5280 のことは考えず、とりあえず署名して証明書作ります。
ここは慣れてるので OpenSSL で

$ openssl req -x509 -new -out CA.crt -keyout CA.key
$ openssl x509 -req -in test.csr -CA CA.crt -CAkey CA.key -set_serial 37 -out test.crt

これで test.crt という証明書ができました。

最後にこれを Windows にインストールします

> certreq -accept test.crt

これで「保留中の要求を処理し、証明書をインストールする」と同じ状態になります。
「IIS マネージャ」の「サイトのプロパティ」の「ディレクトリセキュリティ」の「サーバ証明書」から
「既存の証明書を利用」とか「現在の証明書を置き換える」を選ぶと
test.crt も一覧の中に出てきます。
今回はここで止めてしまったんですがこれだとルート証明書が無くてちょっと良くないかも。
まぁ、実際はルート証明書とか中間認証局の証明書もインストールしましょう。

IIS で SSL するだけなら簡単なんですが
CSR とサイトが紐付いてしまっているうえに
「更新」で Subject の Distinguished Name や鍵長が変更できなかったり
不自由な部分があるんですけど certreq.exe を使えば分離できて happy な感じ。
もしかしたらウィザード自体が個別に呼べたりするなら何の問題も無いんですけど。
変に CSR 作って証明書入れるだけの為にサイト作るよりはこっちがスマートだなぁ。

OpenSSL は桁が溢れる

openssl コマンドを使うと簡単に自己署名証明書が作れます
Extension をどうにかしようとすると設定ファイルを書かないといけませんが

$ openssl req -new -x509 -nodes

とすれば秘密鍵がファイルに保存されて証明書が PEM で標準出力に流れます
これだと 30 日有効な証明書が出るのですが
-days というオプションで有効日数を指定してやることもできます

試しに手元のパソコンで

$ openssl req -x509 -days 10553 -new -nodes | openssl x509 -noout -text

としてみたところ

Validity
    Not Before: Feb 27 17:44:15 2009 GMT
    Not After : Dec 14 11:15:59 1901 GMT

見事に 2038 年問題が発生しました
ASN.1 を parse してみたところ (作りなおしたので日付ずれますが)

112:d=3  hl=2 l=  13 prim: UTCTIME           :090227174633Z
127:d=3  hl=2 l=  15 prim: GENERALIZEDTIME   :19011214111817Z

notBefore と notAfter で型が違っていました
RFC 5280 には

CAs conforming to this profile MUST always encode certificate validity dates through the year 2049 as UTCTime

と書いてあるのに何故 GeneralizedTime が出てくるのでしょう?
2038 年でも UTCTime なはずなんだけど
試しに 64bit な CPU で同じことをしてみたところ

111:d=3  hl=2 l=  13 prim: UTCTIME           :090227182337Z
126:d=3  hl=2 l=  13 prim: UTCTIME           :380119182337Z

溢れずに UTCTime で出てきました
ん〜続きを読む

ユークリッドの互除法

ユークリッドの互除法が頭から抜けていたので復習しました

a > b > 0 を正の整数とする
a を b で割った商を q 余りを r とする

a = b × q + r

このとき 0 ≦ r ＜ b の条件の下 q と r は一意

a = r0、b = r1 と思いこれを繰り返す

r0 = r₁ × q₂ + r₂ (0 ≦ r₂ ＜ r₁)
r₁ = r₂ × q₃ + r₃ (0 ≦ r₃ ＜ r₂)
r₂ = r₃ × q₄ + r₄ (0 ≦ r₄ ＜ r₃)
・・・
r_n-2 = r_n-1 × q_n + r_n (0 ≦ r_n ＜r_n-1)
r_n-1 = r_n × q_n+1 + 0

ri は 0 以上でどんどん小さくなるのでいつかは 0 となる
上は n+1 番目で 0 となるとした場合の表示

このとき、a = r₀ と b = r₁ の公約数 d は全ての r_i を割る
d は各左辺を割り切るので右辺も割り切らないといけないから
特に d は a と b の最大公約数であったとしても r_n を割り切る
逆に一番下から見ていくと r_n は r_n-1 を割り切るので
1 つ前に戻って r_n-2 も割り切り、繰り返すと a = r₀ と b = r₁ も割り切る
つまり r_n は a と b の公約数

• a と b の最大公約数は r_n を割り切る
• r_n は a と b の公約数

r_n は a と b の最大公約数ということ

上の式達を下から解いていくと r_n を a と b を用いて表わすことができる

r₀ = 1・a + 0・b
r₁ = 0・a + 1・b
r_i = x_i a + y_i b

と表現できたとする

r_i = r_i-2 - r_i-1 q_i
= (x_i-2 a + y_i-2 b) - (x_i-1 a + y_i-1 b) q_i
= (x_i-2 - x_i-1 q_i) x - (y_i-2 - y_i-1 q_i) b

つまり

x_i = x_i-2 - x_i-1 q_i
y_i = y_i-2 - y_i-1 q_i

という漸化式が成立する

r₀ = a, r₁ = b だったので
x₀ = 1, y₀ = 0, x₁ = 0, y₁ = 1
という初期値から漸化式を解いていけば良い
例えば Python を使って例外処理を考えないと

def euclid(a, b):
    if b == 0: return None

    x0, y0, z0 = 1, 0, a
    x1, y1, z1 = 0, 1, b

    while z1 != 0:
        r = z0 % z1
        q = z0 / z1
        x0, y0, z0, x1, y1, z1 = x1, y1, z1, x0 - x1 * q, y0 - y1 * q, r

    return x0, y0, z0

とすると

(x, y, z) = euclid(a, b)
if x * a + y * b == z:
    print "z is GCD"

というわけで最大公約数 z = x a + y b という x, y, z が求まる

Digital Signature Algorithm (DSA)

電子署名の方法は RSA + ハッシュしか良く知らなかったので
他のもということで DSA について調べてみました

電子署名アルゴリズムの 1 つ DSA は Digital Signature Algorithm の略
例えば NIST の FIPS 186 で文章化されています

FIPS 186-2 では鍵長は 1024bit で使うハッシュ関数は SHA-1 としていますが
暗号の 2010 年問題というやつで SHA-1 や鍵長に限界が感ぜられているので
FIPS 186-3 がまだ草案ですが鍵長は 3072bit までで SHA-2 が使えるようになる予定です

DSA のパラメータ

DSA ではアルゴリズムにパラメータが指定されます
鍵長を L bit、ハッシュ値の長さを N bit とします
ハッシュ関数はハッシュ値として N bit なものを出力するとします

• 大きな素数 p を 2^L-1 < p < 2^L となるように選びます

• p-1 の素因数 q を 2^N-1 < q < 2^N の範囲で選びます

p は奇数なので p-1 は偶数となり自明でない素因数分解ができます
(実際には q を選んで n もランダムで選んで p = q n + 1 が素数かチェックする?)

• mod p の世界で q 乗して初めて 1 になる数 g を探します (1 < g < p)

(mod p = p で割った余りを考えろ、と読みましょう)
p は素数なので mod p の世界は有限体となり乗法群の位数は p-1
p-1 の素因数である q を位数とする元 g が存在するはずなので選びます

以上の (p, q, g) の triple が DSA のパラメータとなります

DSA の秘密鍵・公開鍵

次に秘密鍵・公開鍵を作ります、といっても簡単で

• x を 0 < x < q で選んで秘密鍵とする

• y = g^x mod p を公開鍵とする

送信者は受信者に {(p, q, g), y} というデータを渡すことになります

DSA の署名と検証

署名しましょう
平文 M のハッシュ値を z とします

• 整数 k を 0 < k < q となるように選びます (x 同様内緒にします)

• r = (g^k mod p) mod q とします
• s = k^-1 (z + x r) mod q とします

この (r, s) が署名となります
k は M 毎に選びます、同じものを再び使うことのないようにします
r と s のどちらかが 0 になってしまった場合、k を選ぶところからやり直します

というわけで、メーッセージの受信者は

• (p, q, g) と y と z = Hash(M) と (r, s) を知っていて
• x と k は知らない

という状況になります
x と k を使わずに r を表現する方法を作れれば検証方法確立です

(g^z y^r)^(s-1) mod p

を考えます. y=g^x を使えばこれは

g^{(z + x r) (s-1)} mod p

です
g^q = 1 mod p だったので g の肩は mod q の世界でした
s の定義を見てみればこの値は

g^k mod p

なので更に mod q とってやれば

((g^z y^r)^(s-1) mod p) mod q = r

となります
左辺は x も k も使わない表現で r を表わすことができました

なので、受信者は

• アルゴリズムパラメータ (p, q, g)
• 公開鍵 y
• 平文 M
• ハッシュ関数
• 署名 (r, s)

が与えられたとき、(r, s) の検証がしたければ

((g^z y^r)^(s-1) mod p) mod q = r

が成立するかどうか確認すれば良いことになります

DSA の雑感

署名を偽造する一番素直な方法は

• y = g^x となる x を求める
• ((g^z y^r)^(s-1) mod p) mod q = r となる s を求める

のどちらかでしょうか
ここで後者の場合 k は攻撃者が選んで良いので r は知ってます
どっちも計算大変だよね? というのが署名を信頼する元になっています
なので p, q が大きいことが大切になってきます

q を使う理由は、単純に mod p の世界で考えてしまうと
平方剰余の乗法性を用いて既知のデータから未知のデータが類推し易くなるから
k をランダムで選ぶと既存の平文と署名から検証可能な平文と署名が作れちゃうとか
色々と知るべきことが残っていそうなんですがとりあえず DSA の流れということで

ちなみに、未だに s の形があの形なことが納得し切れていません
積だけだと攻撃に弱そうなことは分かるんですが.....

サイドチャネル攻撃ってのが凄いなと思った

先日、IPA の暗号フォーラム 2008 を見てきました
不勉強で今回始めて知ったのですが
サイドチャネル攻撃という方法があるのだというのを知りました

• Wikipedia: サイドチャネル攻撃

暗号への攻撃というとアルゴリズムの隙をついたものが多く
総当たりするか、その数を減らす為にアルゴリズムの隙を狙うくらい?
と思っていたのですが「実装の隙を狙う」という方法が現実的になってるそうです

どんなデータを用いるかというと、

• 処理時間

や、組み込み系だと

• 消費電力
• 電磁波

などを計測してパターンを見付けると総当たりすべき範囲が絞れてしまう!!
OpenSSL の場合処理時間が知られないよう返事をするタイミングを操作してるそうです
RSA/DES/AES などでそれぞれ方法があるらしいのですが
デモで実際に取得した電磁波のデータから秘密鍵を復元するデモを見せてくれました
http://www.rcis.aist.go.jp/special/SASEBO/index-ja.html

コンセントを通じて CPU のアナログノイズなんかも観測できるという話で
そこまで考えるとちょっと大変だなぁと思うのですが
近い将来その辺りのことまで考えないといけなくなるのでしょうか
SUICA や PASMO の改札の近くでアンテナを立てておけば
ズラズラと偽造用のデータが流れるとかいうんだと怖いですねぇ

そういえば

• キーボード打鍵時の電磁波で情報漏えい、スイスの研究者が実証

とかもっと昔には

• キーボードのタイプ音から情報漏洩のおそれ--米研究者らが報告

なんて記事もありましたけど、やぁ、どうしよう

• セロハンテープでX線写真を撮影（動画）

あ、これはちょっと違うな