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.
著作権（C）インターネット協会（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は、その中国の宝くじの思考実験を提案しているので、再訪彼らの思考実験の価値が作る多くの分野でかなりの成長がありました。
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年に、数は驚異億台の到達可能なホストです。中国の宝くじ紙からの時間では、平均的なデスクトップのユーザーに利用可能なコンピュータパワーは約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.
ここ数年では、いわゆるインターネットワームによっていくつかのwidescsale攻撃[SPAFF91]が正常にインターネット接続ホストの驚く-大量に妥協し、感染しています。 2001年には、インターネットデータ分析のための協同組合[CAIDA2001]はコードレッドv2のワームは、操作の最初の14時間で35万オーバー宿主に感染することができたことを報告しました。政治的なメッセージを持つホストのウェブサイトの改ざん：Code Redワームのペイロードはいたずらでした。それは生意気な、大胆で、ほぼ即座にそれ自体に注目を集めました。
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.
このような技術の一つは、発信元（S）の公開鍵（複数可）の下で、公開鍵暗号鍵へのワームのためのもの、と妥協したホストのウェブサイト上でいくつかの無害な場所でこれを置くだろう。また、ワームはワームのトポロジカル近所で妥協ウェブサイトの数は、データが含まれていますようにバック伝播することができます。キーを含むファイルは、オリジネーターが時折インターネット検索エンジンを使って探していくつかのユニークなキーワードで識別されます。ワームは、さまざまなインターネット検索エンジンの「キーワード登録」サービスを使用して、プロセスをより効率的に作ることができます。
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性能の両方が合理的に予測倍増間隔に従ってください。コンピューティングハードウェアのパフォーマンスは、まだパフォーマンスは、すべての1.5年倍増したムーアの法則は、以下のように見えます。インターネットの成長は、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年、J.タッチは、ISIに、MD5 [RFC1810]の詳細なパフォーマンス分析を発表しました。その時点でMD5ソフトウェア性能は87mbits /秒でピークに達し、又は毎秒17万シングルブロックMD5操作の等価。同じ年では、ピークDES性能は毎秒約50,000にsetkey /暗号化操作をしました。
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年には、驚異億台の接続されたホストがあります。
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
8つの文字のパスワードとDESは4.79分で割れる可能8つの文字のパスワードをMD5についての218.04日でひび割れすることができ、64ビット鍵とMD5 16.29分でひび割れすることができ
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機械の成功は、超並列ハードウェアの努力は、比較的経済的に成功する方法を示しています。ブルートフォース暗号解読強度のこのレベルは、カスタムハードウェアなしで利用可能にすることができることを冷静に考えています。 DESが放棄する必要があることは明らかです。 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.
（簡単なMAC構造で使用される）MD5のための絵は、はるかに明るいです。短いメッセージのために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.
オペレーティングシステムソフトウェアは、より複雑になってきて、インターネットワーム、ウイルス、トロイの木馬、その他のマルウェアの加害者は、より高度化しています。彼らの目的は、主にwidescale荒らしてきましたが、彼らの方法は、より焦点を合わせ、おそらくより不吉な活動に回すことができることを考えるのが妥当と思われます。
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.
ノーテルISのジョン・モリスは、匿名のニュースグループへの投稿のアイデアを貢献しました。
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;
yeardiff =（ダブル）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);
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、コンピュータ、V。24、N。 11、1991年11月、頁14-22。
[RFC1810] Touch, J., "Report on MD5 Performance", RFC 1810, June 1995.
[RFC1810]タッチ、J.、 "MD5のパフォーマンスに関する報告書"、RFC 1810、1995年6月。
[EFF98] "Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design", Electronic Frontier Foundation, 1998.
[EFF98]「割れDES：暗号研究と盗聴政策＆チップ設計の秘密」、電子フロンティア財団、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] "インターネットワームプログラム：分析"、ユージンSPAFFORD、1991。
[FIPS197] "Advanced Encryption Standard", US FIPS197, November, 2001.
[FIPS197] "のAdvanced Encryption Standard"、米国FIPS197、2001年11月。
[USEN2002] "How to 0wn the Internet in Your Spare Time", Proc. 11th Usenix Security Symposium, 2002.
[USEN2002]、PROC「をどのようにあなたの空き時間にインターネットを0wnします」。第11回Usenixのセキュリティシンポジウム、2002。
Author's Address
著者のアドレス
Marcus D. Leech Nortel Networks P.O. Box 3511, Station C Ottawa, ON Canada, K1Y 4H7
マーカスD.ヒルNortel Networksの私書箱ボックス3511、駅のCオタワ、カナダON、K1Y 4H7
Phone: +1 613-763-9145 EMail: mleech@nortelnetworks.com
電話：+1 613-763-9145電子メール：mleech@nortelnetworks.com
Full Copyright Statement
完全な著作権声明
Copyright (C) The Internet Society (2003). All Rights Reserved.
著作権（C）インターネット協会（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 Editor機能のための基金は現在、インターネット協会によって提供されます。