[-]=======================================================================[-] Wizard Bible vol.56 (2013,5,6) [-]=======================================================================[-] x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第0章：目次 --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○第1章: 某キャンプ参加にあたってHow to !! 黒林檎 著 ○第2章: 基礎暗号学講座・第26回 〜Schnorr認証法〜 IPUSIRON 著 ○第3章: お知らせ ○第4章: 著者プロフィール x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第1章: 某キャンプ参加にあたってHow to !! --- 著者：黒林檎 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) はじめに 　どうも黒林檎です、今回は少し某キャンプでの狙い所と言いますか、そこらへ んを勝手にベラベラ語って行こうと思います。 　ついでに勝手に思ってる事を書いていくだけなのでIPAともキャンプとも関係が ないのであしからず。 　要するに100%当てにはするなと言う事です。 　今回は基本的に… 1)募集前にするべき事 2)参加確定した際にする事,不参加でもするべき事(次回に向けて) 3)参加時にする事 4)抑えておきたい分野.技術 　まぁまず最初に旧セキュリティ&プログラミングキャンプは参加費費用はもちろ ん宿泊費と食費も無料で、４泊５日で行う学生を対象にした強化合宿でありIPA様 が行っている人材育成国家プロジェクトです。 　このような素晴らしい方々により運営されております。 http://www.ipa.go.jp/jinzai/renkei/spcamp2011/instructor/index.html http://www.ipa.go.jp/jinzai/renkei/camp2012/instructor/index.html ■0x02.) セキュアなOSの講義について 　リンクを見れば解るように現在は”セキュリティキャンプ”と改名されて行わ れております。 　セプキャン2011の予算は3500万で実行されていると聞きましたが、現在では…。 　このキャンプの趣旨は優秀なセキュリティ人材を早期発掘と育成を目的として おり、2004年度ではセキュリティコースだけでなくプログラミングコースも取り 入れられました。 　しかし2011をもってセキュリティ＆プログラミングキャンプで、プログラミン グコースはなくなっています。 　その後、セキュリティキャンプに改名されました。 　私的には、セキュアなOSを作ろうに組み込まれたと思っています(プログラミン グコース詳細を知らないのではっきり言えませんが）。 ●IPAセキュキャン公式サイトから引用 「セグメントを利用したメモリ保護機構を作ろう（x86限定）」（川合講師） 「OSの提供するセキュアなAPIを作ろう（x86限定）」（川合講師） 「不正コード実行防止機能を自作しよう」（竹迫講師） 「組込みＯＳでの不正実行の検出機能を自作しよう」（坂井講師） 「シミュレータでの不正実行の検出機能を自作しよう」（坂井講師） 「組込みＯＳでのバッファオーバーラン防止機能を自作しよう」（坂井講師） 「組込みＯＳでのデータ実行防止機能を自作しよう」（坂井講師） 「プロセッサのセキュリティアシスト機能の設計」（坂井講師） 「セキュアOSのポリシー記述言語を使いやすく」（忠鉢講師） 「オリジナルセキュアOSを作ろう」（忠鉢講師） 「仮想化を用いてOSのセキュリティを向上しよう」（忠鉢講師） 「隠しファイルシステムを作成しよう」（忠鉢講師） 「ルートキットを作成しよう」（根津講師） 「ルートキットの感染の防止／検出／駆除ツールを作ろう」（根津講師） … というようにセキュアなOSがかなり充実しています。 　rootkit作成なんて凄く面白そうですね、Ring0動作のマルウェアなどは、攻撃 の見えない化でよく用いられています。 　かなり高いレベルを要求されそうですね(全部高いレベルを要求されるようです が)。 　軽く見てたんですがセキュアなOSはかなり気になる講義が多いので、是非参加 した方は良ければお話を聞かせて頂ければ光栄です。 　ソフトウェアセキュリティクラスの素晴らしさを個人的(第一優先)に伝えなけ ればならないのですが、セキュア少し気になったので先に書かさせて頂きました。 ■0x03.) ソフトウェアセキュリティクラスについて 　さて本命のソフトウェアセキュリティクラスについて、ここは少々古い情報で すが色々書かさせて頂きます。 ●IPAセキュキャン公式サイトから引用 「マルウェア概要」 「OllyDbg,IDAPro,などを中心とした解析方法概説」 「アセンブラ読経」 「マルウェア解析演習＆演習成果発表（クラス内）」 「ヒューリスティック検知演習＆演習成果発表（クラス内）」 … 　マルウェアの概要は種類から始まり、解析はなんたるか!とかマルウェアの分類 ..。まぁ、ここらへんは講義聞くほうが早いです。 ＃ソフトウェアセキュリティクラスを受講される方に一言言うなら、テキストが たくらすの1/4(言い過ぎか？)ぐらいの暑さです(2011は)。 　アセンブラ読解はその名前の通りアセンブラをひたすら紙とペンで読む作業。 　これのためにアセンブラ知識がいります。Pythonとかインタプリタで楽ゲーし てる人は少し予習しておくべきですね。 　マルウェア解析演習というのは名前が解らないexeプログラムが配布されます。 　それを仮想環境上の解析環境で指定配布されているツールで解析するという作 業。 　動的解析と静的解析両方のアプローチを行って解析してかまいません。 　流れは… 1)解析環境の用意 　既にされているなら… 2)動的解析 　このときに通信先やファイルシステムなど出せばよいです。 　使用APIなんかも割れるはずでしょう。 3)アンパック..(ツールが解析時なくてマニュアルアンパックしてる方がいました…) しないとコード（静的解析）できません。 アンパックされてるかはAPI見れば一発。 4)静的解析 　頑張ってください。 　IDA(静的)とOllydbg(静的)とSysAnalyzer(動的)とProcessMonitor(動的)とUPX なり配布されるアンパックツールを使用します(現在はマニュアルアンパックかも しれない…だったら頑張ってください)。 　１つ言うならば大多数が知ってるツールは用意されていますが、超マイナーツ ールはあるかわかりません。 　生徒用PCはインターネットにつながっていません(要するにPCは用意されており、 それで解析します。PCのスペックは高いです)。 　つまり、自分の環境が完全に構築できるわけではないということです。 　『アナライジングマルウェア』(オライリー出版)に載ってるツールはあったと 思います。 　後、知っておくべきはWindowsAPIについてです。 　これも素晴らしいことに、『アナライジングマルウェア』にマルウェア解析wi n32APIチート表がありますので、是非参考にしてください(CreatFile,RegOpenKe y,RegCreatkey,…要するにレジストリ関係のAPIは知ってて得すると思います)。 　解析するマルウェアがキチガイです。 　一応４人程度の班で解析するので技術不足が心配される方も心配ありません。 わたしがそうでした!! 　後は防御技術を勉強しますが、/GSとSafeSEHとかSoftware-DEPとかSEHOPという 耐コントロール奪取技術なども扱います。 　Hardware-DEPやASLRなどの耐コード実行技術など。 　デバッガなんかも講義内容に含まれます。 　ステップイントゥ、関数の中に入る機能。 　ステップオーバー、関数呼び出しを飛び越える機能。 　ブレークポイント、知ってますよね。 　まぁこういうのは講義受けてみたら良いと思います!! 　後は..ヒューリスティック検知演習＆演習成果発表（クラス内）ですね。ヒュ ーリスティックは「ウィルスらしさで検知する最近?(でもないが)ブームなマルウ ェア検知方法」です。おそらく検知エンジンを作成させられると思います。 http://www.atmarkit.co.jp/fsecurity/rensai/yarai06/yarai01.html 　こういう感じです。 　検知エンジン作成は..扱う特徴ーデータセット作成ー検知に私用出来るか判断 ーアルゴリズムを決める…です（え 　話はさておき.. 　ソフトウェアセキュリティクラスは愛甲さんがクラス長です。 　それだけでも参加する意味があるので是非参加してください。 #事前に読んでおいたら楽だと思う本.. ・『アナライジングマルウェア』(内容に何が書かれているかを理解しとけばよい と思います) ・『Gugハンター日記』(これは推奨ではないけど) ・『Hacking美しき策謀』(大体の人が読んでますね) ・API関連の書籍(APIについてはすごくでてきます) ・『クラッカープログラミング大全』(解析系の書籍なら何でもいいけど) 　こんな感じですかね。 　多分参加者の多数がレベル高い方なので、Kernel勉強しといた方が話には困ら ないと思うけど、講義受ける分にはそんな理解せんでよいと思います。 ■0x04.) ウェブセキュリティクラスについて ●IPAセキュキャン公式サイトから引用 ・「WebブラウザとSame Origin Policy」 ・「クロスサイトスクリプティング攻撃の原理と脅威」 ・「クロスサイトスクリプティングのバリエーション」 ・「HTML5とJavaScript」 ・「Content-Security-Policy」 ・「脆弱性を低減・撲滅するための設計実習および発表」 … 　WEBは個人情報の扱いとかが特に多い分野だし、素晴らしいと思います!! 　特にGoogleなんかでXSSみつけると金になります(これは黒い話) 　XSSはWEBアプリケーションに存在するセキュリティホールの一種で攻撃者が用 意したリンクや不正文字入力により、HTMLのDOM構造が壊れ、悪意あるスクリプト を実行出来てしまうことです。 　XSSに関してはha.chers.orgとhtml5sec.orgを参照してみてください。 　HTML5のXSSの基本構造は変化していませんが、ブラウザの新機能追加によるJa vaScriptコード実行機能により要素・属性が増えたせいで被害が大きくなるよう です。 　詳細は講義で聞いてください。 ■0x05.) ネットワークセキュリティクラスについて ●IPAセキュキャン公式サイトから引用 ・「パケット工作と攻撃への応用」 ・「偽装通信とその検出」 ・「侵入検知とその回避」 ・「各種通信解析演習と発表」 … 　使用メインツールはsnortとGPLとWireSharkでしょうか？ 　WireSharkは間違いなくフルで使います。 　シグネチャを作成する方法はしっかり予習するべし!! 　解析演習では10GB以上(だったと思う)のパケットを解析する課題だったはずで す。 　パケットを分ける?って技術が要ります。予習しときましょう。 　後問題なのはおそらく最後の夜に行われるCTFでしょう。 　私は攻防戦をイメージしていて、まったく問題とか「は？なにそれ」みたいな 状況で受けて、まったく解けず肩身狭い卒業をしました。 　CTFで得くこつはおそらく基本解析環境は、BackTrack(仮想環境上)かWindowsに なると思われます。 　Windowsでの解析ならBInTextのような文字列抽出ツールを使用し、問題が指し 示す解答らしき物をまとめて.txtにし、それを解答していきます。 　多分パズル問題(パズル解けたらjsが起動してアラートでパスでてくる奴)や.p capからパスを探せとか出ると思うけどまぁその問題のファイルを詳細に調べるの は重要だと思います。 　JSの解析などは、ぱっとみそんなにイメージが付きにくいと思います。解析＝ .exe（実行ファイル）ってイメージですし。 　JSの解析なんかは『コンピューターウィルス製造入門』嶋崎氏著（データハウ ス刊）などの本がよいと思われます。 　これ言っていいのかわからないんですけど、正直CTFの問題全部がオリジナルで はないと思います(問題のアイディアが)。それっぽい問題は過去のCTF大会(主に 海外)で出てるのが多いと思うで、検索PCで(URL: smokedshicken.org)なんか参照 にしたりしてCTF問題をあさればそれっぽいの出てくると思います(これはハッカ ー魂に反するので最後の必殺技としておいておいてください)。 　その際の検索するコツですが、英語で検索してください。 　日本の解説記事はすごく少なく見つけるまで時間がかかるので、海外サイトを あさる方が効率がよいです。 　XSSなんか見つける場合でも『”XSSがある”』っていうのは解ってるので、そ れっぽい(WEB関係の)スキャナを対象にぶち込んでたらポイポイ出る可能性ありま す(これはBackTrackのがよい)。 　まとめるとツールを使えば、効率よく解ける可能性があります。事前にツール を把握しておきたいところです。 　しかし、どう考えてもLinuxコマンドでやった方が素早く見つかる可能性がある ケースもあります。 　事前にCTFやHACKINGで良よく使われるコマンドを予習しておきましょう。 　すばらしいことに、最近hackerブーム到来で、CTFがすごくメジャーになってい ます。色々な(日本や海外サイトで)学習する事が効率がよい勉強法だと思います。 ■0x06.) 「参加前にすること」と「落ちてからすること」 　後は「参加前にすること」と「落ちてからすること(応募前にする事でもある)」 を説明していこうと思います。 　まぁこれやったからって別に合格するわけでもないけど気休めに実践してほし いです。 　セキュリティ&プログラミングキャンプは高度人材育成&発掘プロジェクトであ りますが、これは決してスキルが高い人が行くプロジェクトではないと言うこと です（９割高スキルの人らばっかですけど…）。 　まぁそれの証拠に私が参加した事を例題に挙げます。 　やることは１つです。 　まず応募容姿をじっくり見てください。2010年、2011年、2012年、そして2013 年(今期)を見て気づくことがあると思います。 …そう若干2011から応募用紙にスキルを求めてくる問題があるのです。 　まぁここらへんは解いてもらわないといけないのですが..。 　去年はYahoo知恵袋に問題を載せて「問いてください」という事件がありました。 　講師陣は常に監視している事を忘れてはいけません。これは自分にも言い聞か せています。 　参加に伴ってサイバー犯罪を犯す輩が現れれば、キャンプの存続が危ぶまれる ので、絶対にしないでください。とか、これをここで言うことではないかもしれ ませんが、一応…。 　要するに国家予算内でやってるので打ち切ら…おっとこれ以上は言えないって 奴ですよ。 　まぁ注意は一応ここらへんで。 　要するにセキュキャン(旧：セプキャン)は高度人材だけが行く場所ではないと いうことです。。 　重要なのは正義感と思うわけ、要するに犯罪者は許さないとかそういう。 　小言が続く… 　本題を一気で言うならば、応募設問でセキュリティコースではIT分野でのアピ ール(成果や得意分野)をしっかりする事だと思います。 　私が一番おすすめするのは「情報の開示」です。プログラミングで例えると、 オープンソースにできるって事だと思います。 　自分の勉強した分野や勉強して知ったこと、勉強内容、こんなことできたぜ、 こんなことしたぜ。そんなくだらない事でもこまめにブログなどに載せることだ と思います。 　これは結構広く知られているイメージではあります。 　「個人スキルを知るためにいるんだろ(笑)」って思うかもしれないが私は少し 違う気がします。このプロジェクトはただ人材を育成するってだけではなく、こ の国の技術者レベルをあげるという狙いがあると伺えます。 　要するに育てたけど、他国技術者になられてはプロジェクトが少しズレてしま うわけです。 　おそらくここを見ている読者層なら、日本のエンジニア人材が不足していると は聞いたことがあると思います。この国のどういうところでどう活躍したいかと か明確に示せれば、低レベルな技術者でも参加できる可能性があるということで す。 　…まあ予測ですが。 　まぁ例ですが…「貴方は他人の子供育てますか？」ってことです。 　まとめると「日本人材」と「本気度と熱意」と「情報開示」。 　情報開示の方法としてはブログなんかでハッキング関係を書くのもありですが、 少し私生活なんか噛ませて自分を知らせるというのもアリだと思います。 　まぁ馬鹿らしいと言えばそれで終わりなんですがね。 　おそらくただ実力に自身があって応募用紙を書いただけで、何もして情報開示 をしていない状態だと落ちると思います。 　是非落ちてしまった人は来年是非やって見てほしいです。 　ブログ内容についてですが、 ・プログラミング最低限出来るって証明するため少し書く ・ハッキング(ソフトウェアならそれ関係、WEBならXSS、ネットワークならパケッ ト読めるなどのアピール) ・Linuxコマンドを仕えるぜといったアピール … 　セプキャン(またはセキュキャン)の講師陣の多くは、『ハッカージャパン』(白 夜書房刊）を書いていますので、是非読んでほしい。 　セプキャン(セキュキャン)の参加についてのヒントがあるかも? x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第2章: 基礎暗号学講座・第26回 〜Schnorr認証法〜 --- 著者：IPUSIRON x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■0x01.) ゼロ知識認証とは 　認証に対する攻撃は受動的攻撃と能動的攻撃に大別できる。 　ここで、認証を受ける側をP(Prover)、認証を行う側をV(Verifier)とする。 　受動的攻撃はPとVでの認証のやり取りを敵が盗聴する（学習段階）。その後、 敵はPになりすまして、認証をパスしようとする攻撃である（なりすまし段階）。 　能動的攻撃はシーケンシャル攻撃とパラレル攻撃がある。 　シーケンシャル攻撃では、敵がVになりすまして、Pと何回かやり取りを行う（ 学習段階）。その後、敵はPになりすまして、認証をパスしようとする（なりすま し段階）。 　シーケンシャル攻撃では、学習段階で集めた情報を使って、なりすましを試み る。一方、パラレル攻撃では、学習段階となりすまし段階を随時実行できる。つ まり、任意のタイミングで学習段階となりすまし段階を切り替えることができる のである。 　そのため、パラレル攻撃の方がシーケンシャル攻撃よりも強い攻撃となる。 　パスワード認証は、上記で定義した能動的攻撃だけでなく受動的攻撃に対して も脆弱である。 　受動的攻撃に対する対策としては、ワンタイムパスワード認証やチャレンジレ スポンス認証がある。 　一方、能動的攻撃に対する対策としては、ワンタイムパスワード認証やチャレ ンジレスポンス認証では十分ではない。 　能動的攻撃に対しても安全であるためには、認証のやり取りからPだけが知って いる秘密sが漏れてはいけない。 　つまり、認証のやり取りにおいて、Pだけが知っている秘密sをVに提示するので はなく、「sを秘密にしたまま、sを知っていることだけ」をVに証明できればよい。 このような認証法をゼロ知識認証と呼ぶ。 　ゼロ知識認証であれば、受動的攻撃に対してだけでなく、能動的攻撃に対して も安全であるため、理想的な認証法であると期待できる（安全性の観点からは理 想的かもしれないが、効率性や運用の観点からは理想的とは言い切れない）。 ■0x02.) Schnorr認証法 　ゼロ知識認証にも多数の認証法が存在するが、今回はSchnorr認証法について解 説する。 　なお、"Schnorr"は「シュノア」と読む。 　Schnorr認証法は次のように動作する。 ●初期化段階 　信頼できるセンターが大きな素数p、位数が大きな素数q、Z_p^*の要素gを公開 する。 　証明者PはZ_qからsをランダムに選び、秘密鍵とする。 　次に、v=g^(-s) mod pを計算して、vを公開鍵としてセンターに登録する。 　以上より、センターの公開鍵は(p,q,g)、秘密鍵はsk=s、公開鍵はpk=vとなる。 ●認証プロトコル 1：証明者PはZ_qからランダムにrを選び、x=g^r mod pを計算して、xを検証者Vに 送信する（コミット）。 2：検証者VはZ_qからランダムにcを選び、証明者Pに送信する（チャレンジ）。 3：証明者Pはy=r+sc mod qを計算して、yを検証者Vに送信する（レスポンス）。 　なお、初期化段階の「g^q≡1 mod q」を満たすqの生成方法はWB41を参照せよ。 ■0x03.) Schnorr認証法の性質 　まず上記に記載したSchnorr認証法が以下の3つの性質を持つことを直観的に示 す。 ・完全性 ・健全性 ・ゼロ知識性 ●完全性 　完全性を示すためには、「秘密sを知っているアルゴリズムAは検証に受理でき ること」を示せばよい。 g^y・v^c mod p =g^(r+sc)・g^(-sc) mod p =g^r mod p =x 　つまり、AはSchnorr認証法の証明者と同じ手順通りに（honestに）動作を行え ば、100%検証が受理(accept)される。 ●健全性 　健全性を示すためには、「検証を合格するアルゴリズムA~は秘密sを知っている こと」を示せばよい。 　sを知らなければ、yがわからない。yがわからなければ、検証が受理(accept)さ れるのは、偶然以外ではありえない。 ●ゼロ知識性 　ゼロ知識性を示すためには、「手順通りに実行しても、秘密sに関する知識は検 証者Vに漏れないこと」を示せばよい。 　rはPだけが知っているので、Vはy=r+scからsを特定することはできない。 　また、「x=g^y・v^c mod p=g^y・g^(sc)・v^c mod p」のうち、Vにとって既知 な情報はx,g^y,v^c,pであり、g^(sc)は未知である。そのため、ここからもsは漏 れない。 　よって、敵が検証者になりすましても、敵はsを知ることができない。つまり、 受動的攻撃には耐えられそうである。これを0x05で定理化して、証明する。 　なお、実はチャレンジの範囲が広いために、能動的攻撃に耐えるためには、離 散対数問題よりも強い仮定が必要である。 ■0x04.) Schnorr認証法の安全性 　Schnorr認証法は、離散対数問題が困難という仮定のもとで、受動的攻撃に対し て安全であることを示す。そのためには、以下の定理を示せば、十分である。 [定理]確率τで受動的攻撃に成功する確率的多項式時間アルゴリズムA~が存在す ると仮定すると、確率τ^s(1-1/q)以上で離散対数問題を解く確率的多項式時間ア ルゴリズムMが存在する。 [方針]A~の存在を利用して、Mを構成する。 [直観的な証明]Mの入力はv=g^(-s)を満たす(p,g,v)である。 -sが離散対数であるため、Mは最終的に-sと一致する値を出力できれば、証明が完 成したことになる。 MはZ_qからランダムにy',c'を選択し、g^y'・v^c' mod pを計算し、その計算結果 をx'とする。 これはMはP'とV'の間で学習段階をシミュレートしていることに対応する。ただし、 手順通りの作り方と順番が異なる（ここでズルしている）。 (x',c',y')をトランスクリプトとして、学習段階のA~に与える。 すると、A~は攻撃段階を実行し始める。 攻撃段階のA~の相手である検証者をMはシミュレートしてあげる。この検証者をV' とする。 A~はV'に対してxを送信するので（コミット）、V'はZ_qからランダムにc1を選択 して、A~に返す（チャレンジ）。 すると、A~はV'にy1を送信する（レスポンス）。 このy1は確率τで検証に合格する値になっている。 MはA'を巻き戻し、再びチャレンジをA~に送信する。 このときのチャレンジはZ_qからランダムにc2を選択したものとする。 すると、A~はV'にy2を送信する（レスポンス）。 このy2も確率τで検証に合格する値になっている。 MはA~の力を利用して、同じxに対して、2通りの答えを得た。 c1,c2間には以下が成り立っている。 x≡g^y・v^c1 mod p≡g^y・v^c2 mod p　←(*) Mは(y1-y2)/(c2-c1) mod pを計算して、出力する。 これでMの構成は終わりである。 Mが出力した値が、離散対数-sと一致していることは、(*)を展開するとわかる。 次に、Mが離散対数を解く確率がτ^s(1-1/q)以上であることを示す。 c1=c2であると、y1=y2になってしまう。この確率は1/qである。つまり、1-1/qの 確率でc1≠c2となる。 後は、A~が2回連続で受動的攻撃に成功するにはτ^2である。 よって、Mが離散対数を解く確率がτ^s(1-1/q)以上である。　□ ■0x05.) ゼロ知識証明からデジタル署名へ 　受動的攻撃に対して安全なゼロ知識証明プロトコルに、ハッシュ関数を組み合 わせると、（ランダムオラクルモデルにおいて）選択メッセージ攻撃に対して安 全なデジタル署名を構成できることが知られている。 　これをFS（Fiat-Shamir）変換と呼ぶ。 　FS変換は次の通りである。 　まず、ゼロ知識証明プロトコルにおけるコミットメントをx、チャレンジをc、 レスポンスをyとする。 　このとき、FS変換では、メッセージをmとするとc=H(m,x)を計算し、mに対する 署名をσ=(c,y')とする（ただし、y'はcを用いてレスポンスを生成）。つまり、 署名者は検証者にm,σ=(c,y')を送信する。 　ゼロ知識証明では検証者のチャレンジcは乱数であるが、FS変換ではメッセージ とコミットメントを入力したときのハッシュ値を用いる。 　自分が知っているメッセージmでハッシュ値を作っても、自分でそのハッシュ値 はコントロールできない。つまり、入出力の相互変換がなくなるため、デジタル 署名に使えるのである。 　それでは、具体的にSchnorr認証法に対してFS変換を行ってみる。便宜上、FS変 換後のデジタル署名はSchnorrデジタル署名と呼ぶことにする。 　パブリックな情報を(p,q,g)とする。Schnorr認証法の公開鍵はv=g^(-s) mod p、 秘密鍵はsとする。 　また、ハッシュ関数をHとする。 　このときSchnorrデジタル署名の3つのアルゴリズムは次のようになる。 ●鍵生成アルゴリズム：KeyGen 　1^kを入力とする。 　vk=v、sk=sとし、検証鍵としてvk、署名鍵としてskを出力する。 ●署名アルゴリズム：Sign 　sk、メッセージmを入力とする。 1：Z_qからrをランダムに選択し、x=g^r mod pを計算する。 2：c=H(m,x)を計算する。 3：y=r+sc mod qを計算する。 4：メッセージm、署名σ=(c,y)を出力する。 ●検証アルゴリズム：Vrfy 　(m,σ)、vkを入力とする。 1：x=g^y・v^c mod pを計算する。 2：c=H(m,x)が成り立てばacceptし、成り立たなければrejectする。 　離散対数問題が困難であるという仮定のもとで、このSchnorr署名は選択メッセ ージ攻撃に対して安全である。 ■0x06.) 対話的ゼロ知識証明から非対話的ゼロ知識証明へ 　Schnorr認証法では証明者と検証者の間で、コミット・チャレンジ・レスポンス の通信、即ち3回の通信を行う。このように証明者と検証者で複数回やり取りを行 うことを「対話的」と呼ぶ。 　実際のネットワークの通信の場合、通信の度にヘッダが付与されるため、対話 の回数は少ない方が効率がよい。（効率だけの観点から見ると）、通信のやり取 りは3回よりも2回、2回よりも1回の方がよい。そこで、証明者と検証者の間の通 信が1回だけのゼロ知識証明は構成できるのかが問題になる。 　実はすでに紹介済みのFS変換と同様の考え方を用いると、任意の対話的ゼロ知 識証明を非対話ゼロ知識証明を構成することができるのである。 　（ゼロ知識証明からデジタル署名に変換する）FS変換では署名者が検証者にm, (c,y')を送信するが、非対話を構成するための変換では証明者が検証者に(x,y') を送信すればよい。 ■0x07.) 終わりに 　今回はゼロ知識認証の例としてSchnorr認証法を解説した。他にもよく知られた ゼロ知識認証法として、GQ認証法やFFS認証法などがある。 　興味のある方はこれらのキーワードで検索してもらいたい。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x --- 第3章: お知らせ --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ○Wizard Bible（http://wizardbible.org/）では随時、執筆ライターを募集して います。 　扱う内容のテーマは広義での「under ground」です。例えばハッキングやセキ ュリティからピッキングなどと幅広い内容を考えています。また特殊な職業や趣 味の解説などでも構いません。 　一回きりでも構いません。また必ず毎回連載する義務もありませんので、でき る範囲で構いません。気軽に声をかけてください。 ○Kenji AikoさんがQ&Aを作ってくれました。初めて参加する人でもわかりやすく 書かれていますので、参考にしてください。 http://wizardbible.org/wbQandA.html ○Wizard Bibleに参加希望の方は気軽にメール（ipusiron@gmail.com）ください。 x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ---- 第4章: 著者プロフィール --- x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x x0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0xx0xXx0x ■黒林檎 ●Job:自宅警備員 ●Web: http://profile.ameba.jp/r00tapple/ ●Web2:http://packr.tk/ ●Twitter: r00tapple ●Mail: packr@packr.tk ●Comment:こん○○は,黒林檎です!!。 　今回はIPA様のセキュリティキャンプをネタにしましたが、倍率も跳ね上がり始 め色々変わっていて情報が新しい!正しい!とは一概に言えない状況です!!(キッパリ 　参加者の参加前のお守り程度になればいいかなと思います。 　CTF初めました。ブログにそれっぽい記事とチームサイト(http://packr.tk)に 募集要項を載せてます!! 　活動不定期です。はい!! 　気になった方は私に声を掛けて頂ければお返事お出しします!! ■IPUSIRON ●Job: 自宅警備員予備軍 ●Web: http://akademeia.info ●Mail: ipusiron@gmail.com ●Comment: 　最近は錠前についてばかり追いかけており、暗号や数学についてはさぼり気味 でした。復習がてらに、今回は暗号ネタを取り上げました。久しぶりにやってみ て、暗号もやっぱり面白いということが再認識できました。 　今後は暗号・数学・錠前をバランスよく追いかけたいと思います。