[要約] 要約：RFC 3607は、中国の宝くじの暗号解読に関する研究を再評価し、インターネットをコードブレーキングツールとして利用する方法を提案しています。目的：このRFCの目的は、インターネットを利用して中国の宝くじの暗号を解読するための手法を提案し、その有効性を検証することです。
Network Working Group M. Leech
Request for Comments: 3607 Nortel Networks
Category: Informational September 2003
Chinese Lottery Cryptanalysis Revisited: The Internet as a Codebreaking Tool
中国の宝くじ暗号化再検討：コードブレイクツールとしてのインターネット
Status of this Memo
本文書の位置付け
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
このメモは、インターネットコミュニティに情報を提供します。いかなる種類のインターネット標準を指定しません。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (2003). All Rights Reserved.
Copyright（c）The Internet Society（2003）。無断転載を禁じます。
Abstract
概要
This document revisits the so-called Chinese Lottery massively-parallel cryptanalytic attack. It explores Internet-based analogues to the Chinese Lottery, and their potentially-serious consequences.
この文書は、いわゆる中国の宝くじを大規模に平行に並行した暗号化攻撃を再訪します。それは、中国の宝くじに対するインターネットベースの類似物と、それらの潜在的に重大な結果を探求します。
In 1991, Quisquater and Desmedt [DESMEDT91] proposed an esoteric, but technically sound, attack against DES or similar ciphers. They termed this attack the Chinese Lottery. It was based on a massively-parallel hardware approach, using consumer electronics as the "hosts" of the cipher-breaking hardware.
1991年、Quisquaterとdesmedt [desmedt91]は、難解な、しかし技術的には健全なDESまたは同様の暗号に対する攻撃を提案しました。彼らはこの攻撃を中国の宝くじと呼んだ。これは、コンシファーエレクトロニクスを暗号破壊ハードウェアの「ホスト」として使用して、非常に平行したハードウェアアプローチに基づいていました。
In the decade since Quisquater and Desmedt proposed their Chinese Lottery thought experiment, there has been considerable growth in a number of areas that make their thought experiment worth revisiting.
QuisquaterとDesmedtが中国の宝くじの思考実験を提案してからの10年間で、彼らの思考実験を再訪する価値のある多くの分野でかなりの成長がありました。
In 1991, the Internet had approximately 8 million reachable hosts attached to it and in 2002, the number is a staggering 100 million reachable hosts. In the time since the Chinese Lottery paper, computer power available to the average desktop user has grown by a factor of approximately 150.
1991年には、インターネットには約800万人の到達可能なホストが添付されており、2002年には1億人の到達可能なホストです。中国の宝くじ紙以来、平均的なデスクトップユーザーが利用できるコンピューター電力は約150倍になりました。
The combined growth of the Internet, and the unstoppable march of Moore's Law have combined to create a dangerous potential for brute-force cryptanalysis of existing crypto systems.
インターネットの成長と止められないムーアの法律の止められない行進が組み合わさって、既存の暗号システムのブルートフォース暗号化の危険な可能性を作り出しました。
In the last few years, several widescsale attacks by so-called Internet Worms [SPAFF91] have successfully compromised and infected surprisingly-large numbers of Internet-attached hosts. In 2001, The Cooperative Association for Internet Data Analysis [CAIDA2001] reported that the Code Red v2 worm was able to infect over 350,000 hosts in its first 14 hours of operation. The payload of the Code Red worm was mischief: the defacement of the host website with a political message. It was bold, brash, and drew attention to itself nearly immediately.
過去数年間で、いわゆるインターネットワーム[SPAFF91]によるいくつかのワイドセール攻撃は、驚くほど多くのインターネットに取り付けられたホストに成功し、感染しました。2001年、インターネットデータ分析協同組合[CAIDA2001]は、コードレッドV2ワームが最初の14時間の操作で350,000人以上のホストに感染することができると報告しました。コードレッドワームのペイロードはいたずらでした。ホストWebサイトの政治的メッセージの汚れでした。それは大胆で、無作法で、すぐにそれ自体に注意を向けました。
Consider for a moment, an Internet worm with a darker and ultimately more dangerous purpose: to brute-force cryptanalyse a message, in order to determine the key used with that message. In order for the worm to be successful, it must avoid detection for long enough to build up a significant level of infected systems, in order to have enough aggregate CPU cycles to complete the cryptanalysis. Furthermore, our worm would need to avoid detection for long enough for the cracked key to be useful to the owners of the worm. Recent research [USEN2002] on stealthy worms paints a very dark picture indeed.
少しの間、暗くて最終的にはより危険な目的を持つインターネットワームを考えてみましょう。そのメッセージで使用されるキーを決定するために、メッセージをcryptanalyseすることです。ワームが成功するためには、暗号化を完了するのに十分な凝集CPUサイクルを持つために、かなりのレベルの感染システムを構築するのに十分な長さの検出を避ける必要があります。さらに、私たちのワームは、ひび割れたキーがワームの所有者に役立つように十分に長い間検出を避ける必要があります。ステルスワームに関する最近の研究[Usen2002]は、非常に暗い絵を描いています。
Even after such a worm is detected it would be nearly impossible to tell whose key the worm was attacking. Any realistic attack payload will have one or two pieces of ciphertext, and some known plaintext, or probable-plaintext characteristics associated with it; hardly enough data to determine the likely victim.
そのようなワームが検出された後でも、ワームが誰のキーを攻撃しているかを伝えることはほとんど不可能です。現実的な攻撃ペイロードには、1つまたは2つの暗号文があり、いくつかの既知のプレーンテキスト、またはそれに関連する可能性のあるプレーンテキスト特性があります。犠牲者の可能性を決定するのに十分なデータはほとんどありません。
When a given instance of the worm determines the key, it needs to contact the originator in order to give them the key. It has to do this in such a way as to minimize the probability that the originator will get caught.
ワームの特定のインスタンスがキーを決定する場合、キーを与えるためにオリジネーターに連絡する必要があります。オリジネーターが捕まる確率を最小限に抑えるために、これを行う必要があります。
One such technique would be for the worm to public-key encrypt the key, under the public key(s) of the originator(s), and place this in some innocuous spot on the website of the compromised host. The worm could also back-propagate so that a number of compromised websites in the topological neighborhood of the worm will also contain the data. The file containing the key would be identified with some unique keyword which the originators occasionally look for using Internet search engines. The worm could make the process more efficient by using the "keyword registry" services of various Internet search engines.
そのような手法の1つは、ワームがパブリックキーを作成者の公開鍵の下でキーを暗号化することです。また、ワームはプロパゲートする可能性があるため、ワームのトポロジー近隣にある多くの侵害されたWebサイトにもデータが含まれています。キーを含むファイルは、インターネット検索エンジンの使用を時々探している一意のキーワードで識別されます。このワームは、さまざまなインターネット検索エンジンの「キーワードレジストリ」サービスを使用することにより、プロセスをより効率的にすることができます。
Another approach would be to post a (possibly PGP-encrypted) message to several newsgroups, through an anonymous posting service. Similarly, Internet "chat" services like IRC could be used; indeed there's an emerging tradition of using IRC and similar services for real-time, anonymous, control of worms and viruses.
別のアプローチは、匿名の投稿サービスを通じて、いくつかのニュースグループに（おそらくPGP暗号化された）メッセージを投稿することです。同様に、IRCのようなインターネット「チャット」サービスを使用できます。実際、IRCと同様のサービスをリアルタイム、匿名、ワームやウイルスの制御に使用するという新たな伝統があります。
Any of these methods can be used both to allow the "winning" worm instance to send results and for the originator to send new work for the amassed army of compromised systems.
これらの方法は、「勝利」ワームインスタンスが結果を送信できるようにし、発信者が妥協したシステムの蓄積された軍隊のために新しい仕事を送ることを可能にするために使用できます。
Both Internet growth and CPU performance follow a reasonably predictable doubling interval. Performance of computing hardware appears to still be following Moore's Law, in which performance doubles every 1.5 years. Internet growth appears to be following a doubling period of 3 years.
インターネットの成長とCPUのパフォーマンスの両方が、合理的に予測可能な2倍の間隔に従います。コンピューティングハードウェアのパフォーマンスは、ムーアの法律に従っているようであり、パフォーマンスは1。5年ごとに2倍になります。インターネットの成長は、3年の倍増期間に続いているようです。
By establishing a common epoch for both performance and Internet growth, we can easily determine the likely attack time for any given year, based on a purely arithmetic approach.
パフォーマンスとインターネットの成長の両方に共通のエポックを確立することにより、純粋に算術的アプローチに基づいて、任意の年の攻撃時間を簡単に決定できます。
A simplifying assumption is that it is indeed possible to construct a suitably-stealthy worm and that it can achieve a steady-state infection of about 0.5% of all attached hosts on the Internet.
単純化された仮定は、適切にステルスのようなワームを構築することが実際に可能であり、インターネット上のすべての付属ホストの約0.5％の定常状態感染を達成できることです。
In 1995, J. Touch, at ISI, published a detailed performance analysis of MD5 [RFC1810]. At that time MD5 software performance peaked at 87mbits/second, or an equivalent of 170,000 single-block MD5 operations per second. In the same year, peak DES performance was about 50,000 setkey/encrypt operations per second.
1995年、ISIのJ. Touchは、MD5 [RFC1810]の詳細なパフォーマンス分析を公開しました。当時、MD5ソフトウェアのパフォーマンスは87MBITS/秒、または1秒あたり170,000個のシングルブロックMD5操作に相当しました。同じ年に、Peak DESパフォーマンスは1秒あたり約50,000セットキー/暗号化操作でした。
In 1995, the Internet had about 20,000,000 attached hosts. In 2002, there are a staggering 100,000,000 attached hosts.
1995年、インターネットには約20,000,000人のホストが添付されていました。2002年には、驚異的な100,000,000人の添付ホストがあります。
A simple C program, given in Appendix A can be used to predict the performance of our hypothetical worm for any given year. Running this program for 2002 gives:
付録Aに示されている簡単なCプログラムを使用して、任意の年の仮想ワームのパフォーマンスを予測できます。2002年にこのプログラムを実行すると：
Year of estimate: 2002 For a total number of infected hosts of 503968 aggregate performance: MD5 9.79e+11/sec DES 2.88e+11/sec DES could be cracked in about 1.45 days DES with 8 character passwords could be cracked in 16.29 minutes MD5 with 64-bit keys could be cracked in about 218.04 days MD5 with 8 character passwords could be cracked in 4.79 minutes
見積もり年：2002年503968の総宿主の総数が集約されたパフォーマンス：MD5 9.79E 11/sec DES 2.88E 11/SEC DESは、8文字のパスワードで約1.45日で16.29分でCRACKEN MD5でクラックする可能性があります。64ビットキーは、約218.04日でMD5でクラックする可能性があり、8つの文字パスワードが4.79分で割れてしまう可能性があります
The numbers given above suggest that an undetected attack against MD5, for a reasonable key length, isn't likely in 2002. A successful attack against DES, however, appears to be a near-certainty.
上記の数字は、妥当なキーの長さのためにMD5に対する検出されない攻撃が2002年にはそうではない可能性が高いことを示唆しています。しかし、DESに対する成功した攻撃は、ほぼ確実であるように見えます。
DES has been shown to be weak in the recent past. The success of the EFF machine, described in [EFF98] shows how a massively-parallel hardware effort can succeed relatively economically. That this level of brute-force cryptanalytic strength could be made available without custom hardware is a sobering thought. It is clear that DES needs to be abandoned; in favor of either 3DES or the newer AES [FIPS197].
DESは最近の過去に弱いことが示されています。[Eff98]に記載されているEFFマシンの成功は、非常に平行したハードウェアの努力が比較的経済的にどのように成功するかを示しています。カスタムハードウェアなしでは、このレベルのブルートフォースの暗号化強度を利用できるようにすることは、冷静な考えです。DEが放棄される必要があることは明らかです。3DESまたは新しいAES [FIPS197]のいずれかを支持します。
The picture for MD5 (when used in simple MAC constructions) is much brighter. For short messages long keys with MD5 are effectively free, computationally, so it makes sense to use the longest architecturally-practical key lengths with MD5.
MD5の写真（単純なMac構造で使用される場合）ははるかに明るくなります。短いメッセージの場合、MD5の長いキーは効果的に自由で計算されるため、MD5で最も長く建築的に実用的なキーの長さを使用することは理にかなっています。
Operating system software is becoming more complex and the perpetrators of Internet Worms, Viruses, Trojan Horses, and other malware, are becoming more sophisticated. While their aim has largely been widescale vandalism, it seems reasonable to assume that their methods could be turned to a more focussed and perhaps more sinister activity.
オペレーティングシステムソフトウェアはより複雑になりつつあり、インターネットワーム、ウイルス、トロイの木馬、およびその他のマルウェアの加害者がより洗練されています。彼らの目的は主にワイドスケールの破壊行為でしたが、その方法がより焦点を絞まれた、おそらくより不吉な活動に変えることができると仮定するのは合理的と思われます。
As of February 2003, at least one worm, known as W32/Opaserv.A has a payload designed to implement a distributed DES cracker.
2003年2月現在、W32/OpaServ.Aとして知られる少なくとも1つのワームには、分散DESクラッカーを実装するために設計されたペイロードがあります。
John Morris, of Nortel IS, contributed the idea of anonymous newsgroup posting.
ノルテルのジョン・モリスは、匿名のニュースグループの投稿のアイデアに貢献しました。
Appendix A: Source Code
付録A：ソースコード
/*
* This program calculates the performance of a hypothetical
* "Chinese Lottery" brute-force cryptanalysis worm, based on
* the current date, estimates of Internet growth rate and
* Moores Law.
*
*/ #include <stdio.h> #include <math.h> /*
* EPOCH for the calculations
*/ #define EPOCH 1995.0 /*
* Size of the Internet (ca 1995)
*/ #define INTERNET_SIZE 20000000.0
/*
* Software MD5 performance (ca 1995)
*/ #define MD5PERF 170000.0
/*
* Software DES performance (ca 1995)
*/ #define DESPERF 50000.0
main (argc, argv) int argc; char **argv; {
double yeardiff;
double cryptoperf, multiplier;
double cracktime;
yeardiff = (double)atoi(argv[1]) - EPOCH;
/*
* Moores Law performance double interval is 1.5 years
*/
cryptoperf = yeardiff / 1.5;
cryptoperf = pow(2.0, cryptoperf);
/*
* Some fuzz here--not all hosts will be the fastest available
*/
cryptoperf *= 0.450;
/*
* Internet size doubling interval is every 3 years
*/
multiplier = yeardiff / 3.0;
multiplier = pow(2.0, multiplier);
multiplier *= (INTERNET_SIZE*0.0050);
fprintf (stderr, "Year of estimate: %d\n", atoi(argv[1]));
fprintf (stdout, "For a total number of infected hosts of %d\n", (int)multiplier); fprintf (stdout, "aggregate performance: MD5 %5.2e/sec DES %5.2e/sec\n", MD5PERF*cryptoperf*multiplier, DESPERF*cryptoperf*multiplier);
fprintf（stdout、 "％d \ nの感染した宿主の総数の場合"、（int）乗数）;fprintf（stdout、 "集約パフォーマンス：md5％5.2e/sec des％5.2e/sec \ n"、md5perf*cryptoperf*Multiplier、desperf*cryptoperf*Multiplier）;
cracktime = pow(2.0, 55.0);
cracktime /= (DESPERF*cryptoperf*multiplier);
fprintf (stdout,
"DES could be cracked in about %3.2lf days\n",
cracktime/86400.0);
cracktime = pow(2.0, 8.0*6.0);
cracktime /= (DESPERF*cryptoperf*multiplier);
fprintf (stdout,
"DES with 8 character passwords could be cracked in
%3.2lf minutes\n",cracktime/60);
cracktime = pow(2.0, 64.0);
cracktime /= (MD5PERF*cryptoperf*multiplier);
fprintf (stdout,
"MD5 with 64-bit keys could be cracked in about
%3.2lf days\n", cracktime/86400.0);
cracktime = pow(2.0, 8.0*6.0);
cracktime /= (MD5PERF*cryptoperf*multiplier);
fprintf (stdout,
"MD5 with 8 character passwords could be cracked in
%3.2lf minutes\n", cracktime/60); }
Normative References
引用文献
[DESMEDT91] "Chinese Lotto as an Exhaustive Code-Breaking Machine". J. Quisquater, Y. Desmedt, Computer, v. 24, n. 11, Nov 1991, pp. 14-22.
[desmedt91]「徹底的なコード破壊マシンとしての中国の宝くじ」。J. Quisquater、Y。Desmedt、Computer、v。24、n。11、1991年11月、14-22ページ。
[RFC1810] Touch, J., "Report on MD5 Performance", RFC 1810, June 1995.
[RFC1810] Touch、J。、「MD5パフォーマンスに関するレポート」、RFC 1810、1995年6月。
[EFF98] "Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design", Electronic Frontier Foundation, 1998.
[EFF98]「クラッキングDE：暗号化研究、盗聴政治＆チップデザインの秘密」、1998年電子フロンティア財団。
[CAIDA2001] "CAIDA Analysis of Code Red" http://www.caida.org/analysis/security/code-red/
[Caida2001] "Caida分析コードレッド" http://www.caida.org/analysis/security/code-red/
[SPAFF91] "The Internet Worm Program: An Analysis", Eugene Spafford, 1991.
[SPAFF91]「インターネットワームプログラム：分析」、Eugene Spafford、1991。
[FIPS197] "Advanced Encryption Standard", US FIPS197, November, 2001.
[FIPS197]「Advanced Encryption Standard」、US FIPS197、2001年11月。
[USEN2002] "How to 0wn the Internet in Your Spare Time", Proc. 11th Usenix Security Symposium, 2002.
[usen2002]「空き時間にインターネットを0wnする方法」、proc。第11回USENIXセキュリティシンポジウム、2002年。
Author's Address
著者の連絡先
Marcus D. Leech Nortel Networks P.O. Box 3511, Station C Ottawa, ON Canada, K1Y 4H7
Marcus D. Leech Nortel Networks P.O.ボックス3511、駅Cオタワ、カナダ、K1Y4H7
Phone: +1 613-763-9145
EMail: mleech@nortelnetworks.com
Full Copyright Statement
完全な著作権声明
Copyright (C) The Internet Society (2003). All Rights Reserved.
Copyright（c）The Internet Society（2003）。無断転載を禁じます。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
このドキュメントと翻訳は他の人にコピーされて提供される場合があります。また、それについてコメントまたは説明する派生作品、またはその実装を支援することは、いかなる種類の制限なしに、準備、コピー、公開、および部分的に配布される場合があります。、上記の著作権通知とこの段落がそのようなすべてのコピーとデリバティブ作品に含まれている場合。ただし、このドキュメント自体は、インターネット協会や他のインターネット組織への著作権通知や参照を削除するなど、いかなる方法でも変更できない場合があります。インターネット標準プロセスに従うか、英語以外の言語に翻訳するために必要な場合に従う必要があります。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assignees.
上記の限られた許可は永続的であり、インターネット社会やその後継者または譲受人によって取り消されることはありません。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
この文書と本書に含まれる情報は、「現状」に基づいて提供されており、インターネット社会とインターネットエンジニアリングタスクフォースは、ここにある情報の使用が行われないという保証を含むがこれらに限定されないすべての保証を否認します。特定の目的に対する商品性または適合性の権利または黙示的な保証を侵害します。
Acknowledgement
謝辞
Funding for the RFC Editor function is currently provided by the Internet Society.
RFCエディター機能の資金は現在、インターネット協会によって提供されています。