分散システム 電子・情報工学系 新城 靖 <yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/dsys-2002/2003-03-04
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html
古くから暗号が使われてきた、4つのグループ
暗号とは、情報の意味が当事者以外にはわからないように情報を変
換することである。
図? 暗号の考え方
暗号化の方法が秘密になっていると、一見、より強そうにみえる。しかし、そ の暗号が、強いのか弱いのか調べる方法がない。攻撃すると、簡単に落ちるか もしれない。暗号化の方法を提供している者が信頼できない時には使えない。
鍵を長くするだけで、安全性が指数関数的に高くなる。
鍵を1ビット長くすると、解読時間が2倍になる。
(「鍵の長さを2倍にすると解読時間が2倍になる」は、誤り)。
図? 指数関数 図? 指数関数
パスワードは、コンピュータの中では、暗号化の鍵として使われる。 長いパスワードは、破られにくい。1文字(大文字小文字数字記号)増やすと、 総当たりで解読に要する時間が、50倍から100倍近くかかるようになる。
暗号の安全にとって、最近のコンピュータの高速化と低下価格下は、 1つの脅威となっている。
SETI (the Search for Extraterrestrial Intelligence)。
暗号の方法は、大きく2つに分類される
Caesar暗号は、知れている最後の暗号である。 平文アルファベットをN文字ずらした暗号文アルファベットに変える。
N=2 の時の対応表
abcdefghijklmnopqrstuvwxyz CDEFGHIJKLMNOPQRSTUVWXYZAB暗号の説明では、平文を小文字で、暗号文を大文字で書く習慣がある。 カルタゴ人以来騙された人はいない。
N=13 で、大文字小文字を保存する方法を、rot13 暗号という。rot13 は、電 子メールやネットワーク・ニュースで「ネタばらし」の部分を書く時に使われ る。
漢字の場合、rot47 という方法がある。nkf -r で、rot13/47 が使える。
数の集合から、無作為抽出で抜き出された数。
真性乱数。ビット列にすると、0と1の発生確率がそれぞれ1/2で、各ビッ トは他の部分と独立(iid(independent and identically distributed)) である。
物理乱数。量子力学の効果を増幅してディジタル化したもの。 平滑化して0,1のバランスをとれば、真性乱数になる。
疑似乱数(pseudo random number)。種(seed)と呼ばれる入力ビットパタンを基 に計算された、種よりも長いランダムに見えるビット・パタン。種が決まれば 出力乱数は一意に決まる。
例:
乱数表: 0 18 19 22 22 7 9 4 14 3
平文: h e l l o w o r l d 8 5 12 12 15 23 15 18 12 4 暗号文: H W E H K D X V Z G : 8 23 5 8 11 4 24 22 26 7乱数表そのものや、大きな乱数表の中でどこから使い始めるかを鍵にすること ができる。
真性乱数を使うと、解読する方法は数学的に存在しないことが証明されている。
しかし、真性乱数を使うことはコストが大きい。 送信側と受信側で同じ真性乱数を作るのが大変である。
乱数表を記憶する変わりに、疑似乱数を使う方法がある。使う疑似乱数の性質 が悪いと簡単に解読される。
実際には、文字をずらすのではなく、足し算、引き算や、排他的論理和と呼ば れる計算が使われることが多い。
Caesar暗号やバーナム暗号では、平文の文字の順序を変えずに、文字を置き換 える。これを置換暗号という。これにたいして、転置暗号(transposition cipher)では、平文の文字の順序を入れ替えるが、文字の置き換えは行わない。 (下の例では、大文字小文字が変わっているが、これは暗号化の説明のために 変えて書いているだけである。)
次は、転置暗号の1つ、コラム転置の例である。キーは、同じ文字を含まない 1個の単語や熟語である。このキーでコラムに番号付けをする。たとえばコラ ム1は、アルファベットで先頭に近い文字の下のコラムとなる。
MEGABUCK -------- 74512836 -------- pleasetr ansferon emillion dollarst omyswiss bankacco untsixtw otwoabcd
平文: pleasetransferonemilliondollarstomyswissbankaccountsixtwotwo 暗号文: AFLLSKSOSELAWAIATOOSSCTCLNMOMANTESILYNTWRNNTSOWDPAEDOBUOERIRICXB
DES(Data Encryption Standard)は、アメリカ商務省標準局 (NBS, National Bureau of Standard, 現在のNIST, National Institute of Standrds and Technology)が1977年に定めた暗 号標準である。IBM社による提案が元になっている。DESは、 アメリカ政府内で、コンピュータ・データのうち、非機密だが取扱 い注意(unclassified but sensitive)のデータを暗号化するため の標準である。DESを一般の商用にも使うことを推奨している。 たとえば、UNIXのパスワード・ファイルは、DESにより暗号 化されている。
DESは、対称暗号系(慣用暗号系)の1つであり、暗号化と復号 化に同一の鍵(56ビット)を用いる。DESは、転時暗号の一種 である。転時暗号では、平文の文字の順序(コンピュータでは、ビッ ト)を入れ替えるものである。DESでは、64ビットの平文につ いて、鍵をもとにビットの入れ替えを16段繰り返す。
アメリカでは、DESを取り扱うチップ(IC)が多く利用されて いる。アメリカは、暗号に関する製品がソフトウェアも含めて輸出 禁止になっており、DESチップもその制約を受けている。DES 暗号化を行うソフトウェアについては、アメリカ以外で開発された ものが広くインターネット上で配布されている。
DESが作られる時、コンピュータ科学者は、56ビットのキーの長さでは短 すぎると主張した。IBMの提案は、128ビットだった。安全保証局の要求 で、56ビットに減らされた。1988年にアメリカ連邦政府は、1988年 にDESの効果を保証しないと決定した。
DES は、Unix のパスワードのハッシュ関数として使われている。
DES に変わる新しい標準。全世界に対して公募され、ベルギーのJoan Daemen とVincent Rijmenにより開発されたRijndael方式が採用された。鍵の長さは、 128ビット、192ビット、256ビットから選べる。
暗号やディジタル署名で使われるのは、Collision Proof 性が求められる。
暗号を使えば、一方向関数が作れる(暗号を使わなくても一方向関数を作るこ とはできる)。
one_way_function( x ) { return x をキーとして 0 を暗号化したもの ; }Unix の /etc/passwd に保存されているものは、DES を25回繰り返して使って 作った一方向関数の結果。パスワードそのものは、保存されてない。
チェックサムや CRC (Cyclic Redundancy Check) にも似ているが、一方向関 数としての Collision Proof 性が求められる。
元データが壊れていないか(誰かに改ざんされていないか)を調べる時には、 メッセージ・ダイジェストを計算して比較する。
公開鍵暗号系(非対称暗号系)では2つの異なる鍵を用いる。 便宜上、この2つを公開鍵と秘密鍵と呼ぶ。
これらの鍵は、互いに相手の逆関数になっている。
図? 公開鍵暗号を使った暗号通信の手順
ここで、公開鍵から秘密鍵を計算することは難しい。ある平文を公開鍵で暗号 化してみたところで、秘密鍵を得ることは難しい。
公開鍵暗号の利点は、鍵を管理する手間が掛らないこと。
RSA暗号は、Rivest, Shamir, Adleman の3人によって開発され た公開鍵暗号系である。RSA暗号の安全性は、大きな数を素因数 分解することの難しさに基づく。北米では、RSAは、2000年 に特許が切れた。
公開鍵に基づく暗号化の1つの方法。買得の難しさは、楕円曲線上の離散対数 問題を解くのと同程度と言われている。RSA よりも鍵が短くて高速である。
最近(2002年9月)、Sun がソース・コードを OpenSSL プロジェクトに寄進した。
認証とは、情報の正当性や完全性を確保する技術である。
ディジタル署名では、通常の署名と同様に、次のような性質が必要である。
公開鍵暗号系を使ってディジタル署名を行うことができる。
図? 公開鍵暗号を使ったディジタル署名の手順
メッセージ全体を暗号化する代わりに、メッセージを平文で送り、それにメッ セージを一方向関数(ハッシュ関数)と呼ばれる方法で計算した結果だけを、 秘密鍵で暗号化したものを送る方法もある。一方向関数では、計算結果から元 の値(メッセージ)を計算することが難しい。
ディジタル署名や利用者認証は、公開鍵暗号系ではなく、共通鍵暗号系を用い ても可能である。ただし、この場合、鍵を管理する信用できる管理センターが 必要となる。
乱数を送って、秘密鍵で暗号化してもらう。
公開鍵で復号化して、元の乱数が得られたら Ok。
毎回違う数を使えば、傍受されていても平気。
利用者認証のために、公開鍵暗号系を用いることができる。銀行の口座を例に、 これを説明する。
単なる暗証番号の場合、通信を傍受されたら終り。
鍵がが本物であるかをどうやって確認するか。
Socket 版
/* Returns the number of characters successfully written */ size_t write(int file_descriptor, void *buf, size_t len)
OpenSSL 版
/* Returns the number of characters successfully written */ int SSL_write(SSL *socket_info, char *buf, int len)
http://www-6.ibm.com/jp/developerworks/security/011005/j_s-stun.html
認証には、証明書が使われる。 鍵の交換には、証明書に含まれている
X.509 形式(バイナリ)を、テキストに変換したものの例:
% openssl x509 -text < file -----BEGIN CERTIFICATE----- MIIFzDCCBTWgAwIBAgIQTQ6TH7jULsH9SKia3+rrKTANBgkqhkiG9w0BAQQFADCB ujEfMB0GA1UEChMWVmVyaVNpZ24gVHJ1c3QgTmV0d29yazEXMBUGA1UECxMOVmVy ... 8eojpxZlyWSw12X3ejKJDpfYhWlhV+K5IwVPM8YQdE+mq6nCqLB4DfvylyXSFSww tSjcG4xpQt54YAjVHnzFqmuK+/gIUuFRiGhEjrRx6x2hbdAoWs2usfHO9dbCUx1/ -----END CERTIFICATE----- Certificate: Data: Version: 3 (0x2) Serial Number: 4d:0e:93:1f:b8:d4:2e:c1:fd:48:a8:9a:df:ea:eb:29 Signature Algorithm: md5WithRSAEncryption Issuer: O=VeriSign Trust Network, OU=VeriSign, Inc., OU=VeriSign International Server CA - Class 3, OU=www.verisign.com/CPS Incorp.by Ref. LIABILITY LTD.(c)97 VeriSign Validity Not Before: Nov 21 00:00:00 2002 GMT Not After : Dec 5 23:59:59 2003 GMT Subject: C=JP, ST=Ibaraki, L=Tsukuba, OU=Terms of use at www.verisign.co.jp/RPA (c)00, OU=Authenticated by VeriSign Japan K.K., OU=Member, VeriSign Trust Network, O=University of Tsukuba, OU=College of Information Sciences, CN=www3.coins.tsukuba.ac.jp Subject Public Key Info: Public Key Algorithm: rsaEncryption RSA Public Key: (1024 bit) Modulus (1024 bit): 00:ae:5a:64:7f:0e:ba:28:b3:49:85:de:1c:0d:c7: f1:43:84:16:07:91:0c:11:80:06:f2:be:92:1c:48: a6:b2:68:2d:91:60:37:f1:ce:b8:77:c3:c7:33:9d: b2:76:88:23:72:65:25:9e:ff:23:e2:58:e0:4d:71: 34:11:42:9a:45:d9:fc:27:65:23:9a:b8:a4:e7:45: 0b:66:5a:c8:06:da:9d:ef:ce:08:8f:07:ba:d7:f0: cd:1c:54:7d:4f:32:f4:27:96:d4:8a:ae:9a:ec:54: 26:b8:49:9e:1d:49:25:6d:3c:51:85:ef:94:6c:20: cf:70:60:39:ae:f4:b7:c1:05 Exponent: 65537 (0x10001) X509v3 extensions: X509v3 Basic Constraints: CA:FALSE 2.5.29.3: 0...0...0.. ....This certificate incorporates by reference, and its use is strictly subject to, the VeriSign Certification Practice Statement (CPS), available at: https://www.verisign.com/CPS; by E-mail at CPS-requests@verisign.com; or by mail at VeriSign, Inc., 2593 Coast Ave., Mountain View, CA 94043 USA Tel. +1 (415) 961-8830 Copyright (c) 1996 VeriSign, Inc. All Rights Reserved. CERTAIN WARRANTIES DISCLAIMED and LIABILITY LIMITED......(https://www.verisign.com/repository/CPS Netscape Cert Type: SSL Server X509v3 Extended Key Usage: Netscape Server Gated Crypto Signature Algorithm: md5WithRSAEncryption 16:45:20:d5:40:2f:d1:59:0a:83:b5:92:4b:e9:1f:13:3e:5f: 39:e8:d6:87:36:65:af:87:95:46:31:a1:5c:b3:f1:ea:23:a7: 16:65:c9:64:b0:d7:65:f7:7a:32:89:0e:97:d8:85:69:61:57: e2:b9:23:05:4f:33:c6:10:74:4f:a6:ab:a9:c2:a8:b0:78:0d: fb:f2:97:25:d2:15:2c:30:b5:28:dc:1b:8c:69:42:de:78:60: 08:d5:1e:7c:c5:aa:6b:8a:fb:f8:08:52:e1:51:88:68:44:8e: b4:71:eb:1d:a1:6d:d0:28:5a:cd:ae:b1:f1:ce:f5:d6:c2:53: 1d:7f -----BEGIN CERTIFICATE----- MIIFzDCCBTWgAwIBAgIQTQ6TH7jULsH9SKia3+rrKTANBgkqhkiG9w0BAQQFADCB ujEfMB0GA1UEChMWVmVyaVNpZ24gVHJ1c3QgTmV0d29yazEXMBUGA1UECxMOVmVy ... 8eojpxZlyWSw12X3ejKJDpfYhWlhV+K5IwVPM8YQdE+mq6nCqLB4DfvylyXSFSww tSjcG4xpQt54YAjVHnzFqmuK+/gIUuFRiGhEjrRx6x2hbdAoWs2usfHO9dbCUx1/ -----END CERTIFICATE----- %
証明書がついていたとして、それが本物であるかをどうやって確認するか。
認証局(CA, Certificate Authority)に、証明書を発行してもらう。(認証局の 秘密鍵でディジタル署名をしてもらう)
その認証局は、信頼できるか?
WWWブラウザには、ルート認証局の証明書が予め含まれている。
末端のWWWサイトは、ルート認証局、または、中間認証局から発行された証 明書を提示する。
接続時に、乱数(共通鍵暗号に基づく暗号化の鍵を生成するため)を交換する。 その乱数は、普通、サーバ側が提示した証明書に含まれている公開鍵で暗号化 される。
ハンドシェークで使われる公開鍵暗号系
データを暗号化するために使われる共通鍵暗号系
---------------------------------------------------------------------- % openssl s_client -connect www3.coins.tsukuba.ac.jp:https -state CONNECTED(00000003) SSL_connect:before/connect initialization SSL_connect:SSLv2/v3 write client hello A SSL_connect:SSLv3 read server hello A depth=1 /O=VeriSign Trust Network/OU=VeriSign, Inc./OU=VeriSign International Server CA - Class 3/OU=www.verisign.com/CPS Incorp.by Ref. LIABILITY LTD.(c)97 VeriSign verify error:num=20:unable to get local issuer certificate verify return:0 SSL_connect:SSLv3 read server certificate A SSL_connect:SSLv3 read server key exchange A SSL_connect:SSLv3 read server done A SSL_connect:SSLv3 write client key exchange A SSL_connect:SSLv3 write change cipher spec A SSL_connect:SSLv3 write finished A SSL_connect:SSLv3 flush data SSL_connect:SSLv3 read finished A --- Certificate chain 0 s:/C=JP/ST=Ibaraki/L=Tsukuba/OU=Terms of use at www.verisign.co.jp/RPA (c)00/OU=Authenticated by VeriSign Japan K.K./OU=Member, VeriSign Trust Network/O=University of Tsukuba/OU=College of Information Sciences/CN=www3.coins.tsukuba.ac.jp i:/O=VeriSign Trust Network/OU=VeriSign, Inc./OU=VeriSign International Server CA - Class 3/OU=www.verisign.com/CPS Incorp.by Ref. LIABILITY LTD.(c)97 VeriSign 1 s:/O=VeriSign Trust Network/OU=VeriSign, Inc./OU=VeriSign International Server CA - Class 3/OU=www.verisign.com/CPS Incorp.by Ref. LIABILITY LTD.(c)97 VeriSign i:/C=US/O=VeriSign, Inc./OU=Class 3 Public Primary Certification Authority --- Server certificate -----BEGIN CERTIFICATE----- MIIFzDCCBTWgAwIBAgIQTQ6TH7jULsH9SKia3+rrKTANBgkqhkiG9w0BAQQFADCB ujEfMB0GA1UEChMWVmVyaVNpZ24gVHJ1c3QgTmV0d29yazEXMBUGA1UECxMOVmVy ... 8eojpxZlyWSw12X3ejKJDpfYhWlhV+K5IwVPM8YQdE+mq6nCqLB4DfvylyXSFSww tSjcG4xpQt54YAjVHnzFqmuK+/gIUuFRiGhEjrRx6x2hbdAoWs2usfHO9dbCUx1/ -----END CERTIFICATE----- subject=/C=JP/ST=Ibaraki/L=Tsukuba/OU=Terms of use at www.verisign.co.jp/RPA (c)00/OU=Authenticated by VeriSign Japan K.K./OU=Member, VeriSign Trust Network/O=University of Tsukuba/OU=College of Information Sciences/CN=www3.coins.tsukuba.ac.jp issuer=/O=VeriSign Trust Network/OU=VeriSign, Inc./OU=VeriSign International Server CA - Class 3/OU=www.verisign.com/CPS Incorp.by Ref. LIABILITY LTD.(c)97 VeriSign --- No client certificate CA names sent --- SSL handshake has read 3124 bytes and written 314 bytes --- New, TLSv1/SSLv3, Cipher is EDH-RSA-DES-CBC3-SHA Server public key is 1024 bit SSL-Session: Protocol : TLSv1 Cipher : EDH-RSA-DES-CBC3-SHA Session-ID: F6C55343A60037D253380BE859EB1F05AB0B215F923A1EC32B024FFA13BE205E Session-ID-ctx: Master-Key: CCEB0A1C4A35D2C0092D906DE1A606C04D940A580FC23C1DD8F97FC985D942C9A8A3DB0387C0CBE3FEA122728EC14F4A Key-Arg : None Start Time: 1046616303 Timeout : 300 (sec) Verify return code: 0 (ok) --- GET / HTTP/1.0 HTTP/1.1 200 OK Date: Sun, 02 Mar 2003 14:45:14 GMT Server: Apache/1.3.27 (Unix) mod_ssl/2.8.11 OpenSSL/0.9.7a Last-Modified: Fri, 15 Nov 2002 00:24:29 GMT ETag: "c15e-114-3dd43ebd" Accept-Ranges: bytes Content-Length: 276 Connection: close Content-Type: text/html <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML> <HEAD> <TITLE>筑波大学第三学群情報学類ホームぺージ(認証用)</TITLE> </HEAD> <BODY> <H3>このページは、認証用テストページです。<BR><BR> 現在、作業中です。 </H3> (H14.11.15: 筑波大学情報学類) </BODY> </HTML> SSL3 alert read:warning:close notify closed SSL3 alert write:warning:close notify % ----------------------------------------------------------------------
IP spoofing (なりすまし).
rsh のセッションで行われるであろうパケットを偽造する。
IP アドレスでホストを認証すると危ない。
DNS spoofing.
偽のDNSのサーバを立てる。
サーバは、2つの鍵と64ビットの乱数を送る。 クライアントは、乱数を送り返す。 乱数が一致したら、IP spoofing されていない。
クライアントは、セッション鍵(対称暗号系の鍵)をサーバの2つの公開鍵で 暗号化して送る。
対象暗号の鍵(セッション鍵)を生成し、公開鍵で送る。
これ以降の通信は、セッション鍵で暗号化される。
個人ごとに RSA 公開鍵での認証機能を利用したほうがよい。
よくつかわれるもの。
% cat bin/ssh-coins-mail #!/bin/sh host=mail.coins.tsukuba.ac.jp ssh -L 10143:$host':'143 -L 10110:$host':'110 -L 10025:$host':'25 $host $* %
自分自身(localhostが便利)のポート番号10143, 10110, 10025 に来た接続要
求を、リモートの host の143, 110, 25 に転送する。ssh の接続先(最後の
$host)と、-L で指定するホストは必ずしも一致していなくてもよい。
ssh コマンドは、Unix、MacOSX、Cygwin で使える。Windows の TeraTerm や
PuTTY でも使える。
図 ssh によるトンネリング(SMTP、POP、IMAP)
---------------------------------------------------------------------- % telnet localhost 10143 Trying 127.0.0.1... Connected to localhost. Escape character is '^]'. OK [CAPABILITY IMAP4REV1 LOGIN-REFERRALS STARTTLS AUTH=LOGIN] orchid-a.coins.tsukuba.ac.jp IMAP4rev1 2001.315rh at Mon, 3 Mar 2003 00:23:09 +0900 (JST) login yas XXXXXXXX OK [CAPABILITY IMAP4REV1 IDLE NAMESPACE MAILBOX-REFERRALS SCAN SORT THREAD=REFERENCES THREAD=ORDEREDSUBJECT MULTIAPPEND] User yas authenticated select #mh/inbox 144 EXISTS 0 RECENT OK [UIDVALIDITY 1046618627] UID validity status OK [UIDNEXT 145] Predicted next UID NO [UIDNOTSTICKY] Non-permanent unique identifiers: #mh/inbox FLAGS (\Answered \Flagged \Deleted \Draft \Seen) OK [PERMANENTFLAGS ()] Permanent flags OK [UNSEEN 144] first unseen message in #mh/inbox OK [READ-WRITE] SELECT completed logout BYE orchid-a.coins.tsukuba.ac.jp IMAP4rev1 server terminating connection OK LOGOUT completed Connection closed by foreign host. % ----------------------------------------------------------------------
SSH2 を使った方がよい。
RSA社が提唱している公開鍵を使ってセッション鍵(秘密鍵)を交換する 方式(PKCS1 1.5 )そのものに、脆弱性がある [1]。
PKCS -- Public-Key Cryptography Standards
[1] Daniel Bleichenbacher, "Chosen ciphertext attacks on RSA encryption standard PKCS #1", Advances in Cryptology, CRYPTO 98. Springer.
サーバ鍵を1時間に1回しか変えない。
SSH 1.5 は、1024 ビットの鍵を使っている。 これを破るには、2 20 + 2 19 回接続でよい。毎 秒、約 400 回。
1個所からの接続に上限を付ける。OpenSSH はそうなっている。 Distributed 攻撃には、弱そう。
OpenSSH
http://www.openssh.com/