-
-
[讨论]RC4算法暴力破解的尝试(附源码)
-
2013-7-7 10:46
-
目录：
一．命题
二．C源码的故事
三．望尽天涯路
四．蓦然回首
五．单线程与多线程性能对比
六．附件说明
一．命题
问题来源于帖子“关于RC4算法的暴力破解问题”。新开一帖，将解决问题的过程写出来与大家探讨，同时给人一个膜拜的机会
。问题肯定多多，欢迎鄙视
！
前段时间在弄一个目标，几乎可以肯定是某种对称加密算法，但是不能确定是哪一个。于是将一些常见的对称算法依次过了一遍，包括3-WAY、AES(RIJNDAEL)、DES/TDEA、IDEA、RC4、RC6、TEA等等。
之前对这些东西并不熟悉，学习过程中走了弯路。一开始是看一些知道的库的源码，比如cryptlib、cryptopp、OpenSSL和LibTomCrypt等。后来才发现这些库为方便使用，大都经过封装，虽然标准规范摆在那里，要从中学习算法代码的具体实现反到不合适——细节被隐藏了——让人不能抓住重点。
而且这些库都是借用了别人的代码。以DES算法为例，在我关注帖子“DES算法求助”时，仔细研究了一下。
cryptlib和OpenSSL是基于"Eric Young"的代码，cryptopp源于"Phil Karn"的des.c。在输入相同的情况下，LibTomCrypt与KARN_portable产生的key schedule完全一致。这些公开的库必须是符合DES标准的，所以同样的输入得到相同的输出。
“DES算法求助”里的算法有点另类，逆向它的加密算法后，根据DES的原理，写出了它的解密算法。没花时间去进一步研究为什么它与标准库的输出不同。
本命题可简化为：已知RC4算法Keystream的前8个字节，求对应的Key(密钥)：
Keystream(Hex.): 50 35 38 62 2C 1E 0C 6F
二．C源码的故事
关于RC4攻击有很多文章可读，比如这里：http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html。
粗略看了几篇，不得要领。回过头来尝试“暴力”。
诚如原帖楼主所言，“暴力破解”(brute-force attack)，或称穷举法(exhaustive key search)，效率是关键，VB在这里稍微高级了点，低级的C比较合适，有利于优化。
正好手头有RC4算法的C源码：RC4.C。来自"Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition"一书的配套光盘。
从作者"Bruce Schneier"的说明来看，它正是某人匿名公开到sci.crypt的那个东西。他在该书的RC4章节讲述了它的来源。
RC4已经成为一些常用加密协议和标准的一部分，比如WEP、WPA和TLS。它在如此众多应用领域取得成功的主要因素在于其速度和简易，在软件和硬件上都易于得到高效的实现。
可以从RC4.C中发现确实如此，非常简单，但你不得不赞叹它的精妙。
三．望尽天涯路
在RC4.C的基础上，稍微修改一下，就可以从事“暴力”活动了。
发现RC4.C的Line#92一行可能是笔误：
xorIndex = state[x] + (state[y]) % 256;
对比http://en.wikipedia.org/wiki/RC4的算法部分，应为：
xorIndex = (state[x] + state[y]) % 256;
由于结果和运算数据的类型均为unsigned char，所以不会有任何影响，不易察觉。
因为RC4的Key是可变长度的，为了通用，设计了一个递归函数(Recursive Function)，将prepare_key函数和rc4函数(改为GetKeyStream函数)放进去。再定义三个全局变量：int KeyLength，unsigned char Key[8]和unsigned char KeyStream[8]。
程序的思路非常直接：KeyLength的取值为1~8，编译时给定一个KeyLength，程序将Key的KeyLength个字符从0x00~0xFF进行穷举，计算KeyStream的字符，如果匹配目标KeyStream，则表明找到一个Key。
所以程序只支持最长8字节Key的尝试，不要小看它，到后来才发现要枚举它的每一种组合完全是Mission Impossible。
只是一个命令行的小程序(Console Application)，一开始还打印出每一循环的Key，实在太慢就删掉了。
在KeyLength为1~3时，很快有结果，无解。在KeyLength=4时，在我的测试机器上等待的时间就稍长了，同样无解。
在KeyLength≧5时，事情变得糟糕了，运行时只有光标在闪烁，不知道进度，也不知道程序是否正常。于是增加两个热键：
CTRL+C 可打印当前Key的值以显示进度。
CTRL+BREAK 用于终止程序，并打印程序的开始、终止、运行时间及Key的进度。
同时，将目标Keystream减少为4字节(unsigned char KeyStream[4])，一方面GetKeyStream函数会快一倍，同时增加了获得匹配输出的机会。面对一个没有任何输出的屏幕是令人沮丧的。
在得到一个Key的输出后，通过另一个小程序来验证Keystream的第二个4字节。
在一些明显影响效率的地方也进行了优化。
对每一个给定的Key，prepare_key函数首先要对unsigned char state[256]进行初始化：各字节赋值依次为0x00~0xFF。每一循环都要在内存中逐字节写256次是很慢的，改为在main函数中写好，需要时通过memcpy 函数进行复制，编译器基本上会生成"REP MOVSD "指令，这样会快很多。
编程工作在虚拟机里进行，运行是在另一台物理机"Intel Core2 Quad CPU"里进行。几年前的机器，速度较慢。关闭杀软的实时检测，停用不需要的服务。
在这个四核机器上同时运行四个实例，KeyLength分别对应5~8。在运行约7小时后终止程序，得到以下结果：
Keystream Key
--------- ---
50 35 38 62 01 2F C7 32 01 4E 3B 4D 40
50 35 38 62 9C 7E 88 8A 01 C0 1C FD D2
50 35 38 62 EA 61 1B 17 02 86 2B 88 6E
50 35 38 62 23 E7 8D 96 02 F3 DF 6F 84
50 35 38 62 2B 97 FE 78 03 53 18 DF 55
50 35 38 62 EF C0 78 A3 03 9A C8 18 79
50 35 38 62 F1 06 6F 45 00 00 42 A2 B9 47
50 35 38 62 2F 6C A9 BA 00 01 71 68 2F 8F
50 35 38 62 A4 A8 9C 4E 00 01 96 46 CB B1
50 35 38 62 A8 78 6E A9 00 02 16 9E 9B 6F
50 35 38 62 6A 3A 80 EA 00 02 22 87 9B A9
50 35 38 62 64 94 FB FD 00 00 02 EF 99 40 65
50 35 38 62 4C EA 00 FB 00 00 03 CA 04 AA 30
50 35 38 62 38 1D 3C 97 00 00 04 55 64 20 9F
50 35 38 62 E9 F2 56 54 00 00 04 9B 8E 75 0E
50 35 38 62 EA B8 29 83 00 00 00 00 8E BE 23 FE
50 35 38 62 33 8E BD 4D 00 00 00 01 85 25 46 B6
50 35 38 62 0A 21 C8 50 00 00 00 01 FE F9 31 C2
50 35 38 62 50 7F DF 9D 00 00 00 02 5C 17 DC D6
50 35 38 62 4C B8 44 28 00 00 00 03 91 93 B2 F3
50 35 38 62 97 43 2D 5A 00 00 00 03 9D 93 BC 01
50 35 38 62 DF E3 49 0E 00 00 00 03 FC D1 E9 0D
50 35 38 62 EF 63 4E 82 00 00 00 03 FF 9C 77 6A
50 35 38 62 18 11 60 20 00 00 00 05 AF 67 30 F8
令人失望，没有一个符合目标Keystream。但证实了原来的猜想：对给定长度的Keystream，存在多解。
四．蓦然回首
显然继续下去是毫无意义的。既然这个Key是人为的，那么可以尝试字典攻击。但在这之前决定缩小Key中每个字符的范围再试一下。
本想限定为数字加字母，改写时为减少几个判断，索性将每个字符的取值定为0x30~0x7A(共0x4B，75.个字符)：
00000000: 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 0123456789:;<=>?
00000010: 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F @ABCDEFGHIJKLMNO
00000020: 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F PQRSTUVWXYZ[\]^_
00000030: 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F `abcdefghijklmno
00000040: 70 71 72 73 74 75 76 77 78 79 7A pqrstuvwxyz
这样计算量大幅降低。新程序的C文件命名为：rc4KStream75.c。
补充两个优化时应注意的问题。
其一，RC4.C中的prepare_key函数和rc4函数各有几处取模操作符(%)，通常会编译为IDIV指令，我们知道除法会严重影响性能。应该改写，将%消灭。这个容易，既然运算的数据全为unsigned char，%256完全是多此一举。
剩下一个"% key_data_len"改为"-= key_data_len"的循环。
其二，编译选项。我虚拟机里是VC6，不同版本的Visual Studio选项有些许差异。应根据运行时的目标机器建立测试基准，耐心地试验各种选项组合，以确定最快的一个。
举个例子，/Ot意为"Favors fast code"，不要轻信编译器的优化能力。应选择/Os("Favors small code")。较少的机器指令会明显提高执行效率，有数倍的差距！
后来为加快进度，又试着写了一个四线程的版本：rc4KStream75MT.c。
单线程用/ML和/MD没有太大差别，而多线程一定要用/MT。
另外最好用Hiew等工具检查一下prepare_key和GetKeyStream两个关键函数的指令是否符合C代码的预期。理论上这两个函数最好用汇编来写，看了一下，感觉自己写出来的东西比编译器强不到那里去，而且后来很快就有了答案，好奇心既已满足，便不再深究。
没想到，在KeyLength=5的那个实例中答案很快揭晓，并且是唯一的匹配项。以下是验证程序汇集其它匹配Key的输出结果。
Target Keystream:
50 35 38 62 2C 1E 0C 6F
Keystream Key String
--------- --- ------
50 35 38 62 2C 1E 0C 6F 31 32 33 34 35 12345
50 35 38 62 1E 23 14 43 30 77 47 71 78 72 0wGqxr
50 35 38 62 33 61 75 03 31 47 3B 36 3D 4E 1G;6=N
50 35 38 62 95 A7 ED 12 32 4F 70 49 6F 31 2OpIo1
50 35 38 62 55 D1 B7 E4 30 32 67 61 71 39 65 02gaq9e
50 35 38 62 0B D1 62 59 30 33 57 72 52 6B 3D 03WrRk=
50 35 38 62 57 94 D7 D6 30 35 4D 56 57 61 48 05MVWaH
50 35 38 62 48 51 FE B6 30 30 32 72 3B 45 41 59 002r;EAY
50 35 38 62 5B 45 F7 54 30 30 33 63 5D 43 36 35 003c]C65
50 35 38 62 BC 87 E4 B9 30 30 33 63 6A 4F 67 3F 003cjOg?
50 35 38 62 80 FD 34 7A 30 30 33 64 50 69 45 5A 003dPiEZ
50 35 38 62 9E 7F E6 FE 30 30 34 48 7A 4E 68 32 004HzNh2
50 35 38 62 8A 2F 47 DB 30 30 35 63 50 3B 3B 4B 005cP;;K
50 35 38 62 2A 91 D0 81 30 30 35 71 55 44 72 40 005qUDr@
00 F8 7E 67 24 33 15 9C 31 32 33 34 35 36 123456
7D 0F D8 8F D1 B4 16 6C 31 32 33 34 35 36 37 1234567
BB F3 39 D4 09 B1 DE A7 31 32 33 34 35 36 37 38 12345678
让人大跌眼镜，第一行的Keystream竟然与目标完全一致！我们可以大胆地猜测它就是正确的Key，又一次证明简单密钥的危险！最后三行是有意增加的，列在这里仅为了对比。
五．单线程与多线程性能对比
以下为附件中最终版本找到Key时的运行记录：
rc4KStream75_5.exe
Found: 31 32 33 34 35 52.265 sec.
Start: 2013-07-04 16:43:06.687
End: 2013-07-04 17:46:41.531
Execution time: 3814.844 seconds. 1h03m34s
rc4KStream75MT_5.exe
Found: 31 32 33 34 35 81.766 sec.
Start: 2013-07-04 15:40:03.000
End: 2013-07-04 16:08:41.812
Execution time: 1718.813 seconds. 28m38s
单线程找出它用了52秒，而多线程用了81秒，这有点奇怪。整个5字节的Key搜索完成，单线程用时约一小时，多线程仅耗时28分钟。
用于编程虚拟机的Host是更早的双Intel Xeon CPU，共四核。但VM只配置了一个处理器、单核。以下为两台机器跑完KeyLength=3后的耗时对比(秒为单位)：
Intel Core2 Quad Intel Xeon(VM)
---------------- --------------
rc4KStream75_3.exe 0.671~0.688 1.62 ~1.78
rc4KStream75MT_3.exe 0.312~0.344 1.296~1.313
就虚拟机自身比较，多线程要快于单线程。无单核物理机进行对比测试。
最后对完成KeyLength=6~8的用时作一个大致估算，以4字节Key的实际数据为依据：
rc4KStream75_4.exe
Start: 2013-07-04 16:38:59.593
End: 2013-07-04 16:39:50.515
Execution time: 50.922 seconds.
5 50.922 * 75**1 = 3819 1h03m39s(结果与实际接近)
6 50.922 * 75**2 = 286436 3D07h33m56s
7 50.922 * 75**3 = 21482718 248D15h25m18s
8 50.922 * 75**4 = 1611203906 18648D04h38m26s(51Y33D)
rc4KStream75MT_4.exe
Start: 2013-07-04 16:13:09.015
End: 2013-07-04 16:13:31.609
Execution time: 22.594 seconds.
5 22.594 * 75**1 = 1694 28m14s(结果与实际接近)
6 22.594 * 75**2 = 127091 1D11h18m11s
7 22.594 * 75**3 = 9531843 110D07h44m03s
8 22.594 * 75**4 = 714888281 8274D04h04m41s(22Y244D)
测试是一门单独的学科，这里并不严格，只想借此说明问题。这台机器上，在Key为8字节、各字节为75个可能和只计算Keystream首4字节的情况下，单线程需要51年，多线程也需要近23年。
可见密钥长度和复杂程度的重要性！
六．附件说明
Size Name Description
-------- ------------------ -----------
1222 RC4.ZIP Cypherpunks邮件列表的C源码
4403 rc4KStream75.c 单线程C源码
6979 rc4KStream75MT.c 四线程C源码
16384 rc4KStream75.exe MD5: 844a293a3fe268312e2babbbe8b095e4
45056 rc4KStream75MT.exe MD5: 1aa9459479658fb5230bd1e1721b8ae9
因为简单，就没有项目了。直接用命令行进行Build，最终的编译选项见各源码注释，KeyLength=3。
视你的机器和C编译器版本，调整选项重新编译。
如果用我的exe，对其它KeyLength，找个编辑器直接改exe的一个字节就好了：rc4KStream75.exe文件偏移0x3010处，rc4KStream75MT.exe文件偏移0x8030处，现在是0x03，可改为0x01~0x08。
还有些问题，比如提高进程自身的优先级会对速度有多大影响，中断后下次怎么继续等等，留给感兴趣的人接着玩吧！
字典攻击方面，要得到本例的答案，应该不会需要太多时间。几年前干过一件事，好象是用Rainbow字典，为Windows登录密码大概是长度为8、字母+数字的组合生成约1GB的Hash库，时间久已记不清了，残存的印象是从当时的测试结果来看，效果非常好。另外也有网站提供根据SAM里的Hash查明文的服务。
以前数学太烂，写代码又非职业程序员，基本上复制粘贴。这两天看温网，转播评论员说，“业余爱好者千万别学A.radwanska”。确实看她打球就觉得别扭，瞧瞧人家小德的动作多么规范！就是这个意思了。
Anyway，文章写出来总是希望有更多人读的。好评/差评？亲，你怎么看
。
一．命题
二．C源码的故事
三．望尽天涯路
四．蓦然回首
五．单线程与多线程性能对比
六．附件说明
一．命题
问题来源于帖子“关于RC4算法的暴力破解问题”。新开一帖，将解决问题的过程写出来与大家探讨，同时给人一个膜拜的机会
。问题肯定多多，欢迎鄙视！前段时间在弄一个目标，几乎可以肯定是某种对称加密算法，但是不能确定是哪一个。于是将一些常见的对称算法依次过了一遍，包括3-WAY、AES(RIJNDAEL)、DES/TDEA、IDEA、RC4、RC6、TEA等等。
之前对这些东西并不熟悉，学习过程中走了弯路。一开始是看一些知道的库的源码，比如cryptlib、cryptopp、OpenSSL和LibTomCrypt等。后来才发现这些库为方便使用，大都经过封装，虽然标准规范摆在那里，要从中学习算法代码的具体实现反到不合适——细节被隐藏了——让人不能抓住重点。
而且这些库都是借用了别人的代码。以DES算法为例，在我关注帖子“DES算法求助”时，仔细研究了一下。
cryptlib和OpenSSL是基于"Eric Young"的代码，cryptopp源于"Phil Karn"的des.c。在输入相同的情况下，LibTomCrypt与KARN_portable产生的key schedule完全一致。这些公开的库必须是符合DES标准的，所以同样的输入得到相同的输出。
“DES算法求助”里的算法有点另类，逆向它的加密算法后，根据DES的原理，写出了它的解密算法。没花时间去进一步研究为什么它与标准库的输出不同。
本命题可简化为：已知RC4算法Keystream的前8个字节，求对应的Key(密钥)：
二．C源码的故事
关于RC4攻击有很多文章可读，比如这里：http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html。
粗略看了几篇，不得要领。回过头来尝试“暴力”。
诚如原帖楼主所言，“暴力破解”(brute-force attack)，或称穷举法(exhaustive key search)，效率是关键，VB在这里稍微高级了点，低级的C比较合适，有利于优化。
正好手头有RC4算法的C源码：RC4.C。来自"Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition"一书的配套光盘。
从作者"Bruce Schneier"的说明来看，它正是某人匿名公开到sci.crypt的那个东西。他在该书的RC4章节讲述了它的来源。
RC4最早由"RSA Data Security, Inc."的"Ron Rivest"(RSA中的R)在1987年设计，随后的七年中一直是专有的，算法的细节只有在签署保密协议后才可使用。维基上讲：RC4名称本身是注册商标，所以人们往往将其称为ARCFOUR或ARC4(alleged RC4)以避开商标问题。虽然"RSA Security"从未正式发布其算法，但是Rivest自己却在某个课程笔记中将其指向英文维基百科的RC4条目。
1994年9月，有人匿名将源码发布到Cypherpunks的邮件列表中。然后迅速蔓延到Usenet的新闻组sci.crypt，并通过互联网出现在世界各地的FTP站点。拥有RC4合法副本的人确认了这个泄露源码的输出与经过授权的RC4完全一致。
"RSA Data Security, Inc."试图把这个精灵重新放回魔瓶里，声称即便它已经公开，但仍然属于商业秘密。
不过为时已晚。此后，在Usenet上它一再被讨论和详细分析，在各种会议上分发，并在密码学课程中讲解。
RC4已经成为一些常用加密协议和标准的一部分，比如WEP、WPA和TLS。它在如此众多应用领域取得成功的主要因素在于其速度和简易，在软件和硬件上都易于得到高效的实现。
可以从RC4.C中发现确实如此，非常简单，但你不得不赞叹它的精妙。
三．望尽天涯路
在RC4.C的基础上，稍微修改一下，就可以从事“暴力”活动了。
发现RC4.C的Line#92一行可能是笔误：
对比http://en.wikipedia.org/wiki/RC4的算法部分，应为：
由于结果和运算数据的类型均为unsigned char，所以不会有任何影响，不易察觉。
因为RC4的Key是可变长度的，为了通用，设计了一个递归函数(Recursive Function)，将prepare_key函数和rc4函数(改为GetKeyStream函数)放进去。再定义三个全局变量：int KeyLength，unsigned char Key[8]和unsigned char KeyStream[8]。
程序的思路非常直接：KeyLength的取值为1~8，编译时给定一个KeyLength，程序将Key的KeyLength个字符从0x00~0xFF进行穷举，计算KeyStream的字符，如果匹配目标KeyStream，则表明找到一个Key。
所以程序只支持最长8字节Key的尝试，不要小看它，到后来才发现要枚举它的每一种组合完全是Mission Impossible。
只是一个命令行的小程序(Console Application)，一开始还打印出每一循环的Key，实在太慢就删掉了。
在KeyLength为1~3时，很快有结果，无解。在KeyLength=4时，在我的测试机器上等待的时间就稍长了，同样无解。
在KeyLength≧5时，事情变得糟糕了，运行时只有光标在闪烁，不知道进度，也不知道程序是否正常。于是增加两个热键：
同时，将目标Keystream减少为4字节(unsigned char KeyStream[4])，一方面GetKeyStream函数会快一倍，同时增加了获得匹配输出的机会。面对一个没有任何输出的屏幕是令人沮丧的。
在得到一个Key的输出后，通过另一个小程序来验证Keystream的第二个4字节。
在一些明显影响效率的地方也进行了优化。
对每一个给定的Key，prepare_key函数首先要对unsigned char state[256]进行初始化：各字节赋值依次为0x00~0xFF。每一循环都要在内存中逐字节写256次是很慢的，改为在main函数中写好，需要时通过
编程工作在虚拟机里进行，运行是在另一台物理机"Intel Core2 Quad CPU"里进行。几年前的机器，速度较慢。关闭杀软的实时检测，停用不需要的服务。
在这个四核机器上同时运行四个实例，KeyLength分别对应5~8。在运行约7小时后终止程序，得到以下结果：
--------- ---
50 35 38 62 01 2F C7 32 01 4E 3B 4D 40
50 35 38 62 9C 7E 88 8A 01 C0 1C FD D2
50 35 38 62 EA 61 1B 17 02 86 2B 88 6E
50 35 38 62 EF C0 78 A3 03 9A C8 18 79
50 35 38 62 F1 06 6F 45 00 00 42 A2 B9 47
50 35 38 62 2F 6C A9 BA 00 01 71 68 2F 8F
50 35 38 62 A4 A8 9C 4E 00 01 96 46 CB B1
50 35 38 62 A8 78 6E A9 00 02 16 9E 9B 6F
50 35 38 62 6A 3A 80 EA 00 02 22 87 9B A9
50 35 38 62 64 94 FB FD 00 00 02 EF 99 40 65
50 35 38 62 4C EA 00 FB 00 00 03 CA 04 AA 30
50 35 38 62 38 1D 3C 97 00 00 04 55 64 20 9F
50 35 38 62 E9 F2 56 54 00 00 04 9B 8E 75 0E
50 35 38 62 EA B8 29 83 00 00 00 00 8E BE 23 FE
50 35 38 62 33 8E BD 4D 00 00 00 01 85 25 46 B6
50 35 38 62 0A 21 C8 50 00 00 00 01 FE F9 31 C2
50 35 38 62 50 7F DF 9D 00 00 00 02 5C 17 DC D6
50 35 38 62 4C B8 44 28 00 00 00 03 91 93 B2 F3
50 35 38 62 97 43 2D 5A 00 00 00 03 9D 93 BC 01
50 35 38 62 DF E3 49 0E 00 00 00 03 FC D1 E9 0D
50 35 38 62 EF 63 4E 82 00 00 00 03 FF 9C 77 6A
50 35 38 62 18 11 60 20 00 00 00 05 AF 67 30 F8
令人失望，没有一个符合目标Keystream。但证实了原来的猜想：对给定长度的Keystream，存在多解。
四．蓦然回首
显然继续下去是毫无意义的。既然这个Key是人为的，那么可以尝试字典攻击。但在这之前决定缩小Key中每个字符的范围再试一下。
本想限定为数字加字母，改写时为减少几个判断，索性将每个字符的取值定为0x30~0x7A(共0x4B，75.个字符)：
00000010: 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F @ABCDEFGHIJKLMNO
00000020: 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F PQRSTUVWXYZ[\]^_
00000030: 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F `abcdefghijklmno
00000040: 70 71 72 73 74 75 76 77 78 79 7A pqrstuvwxyz
这样计算量大幅降低。新程序的C文件命名为：rc4KStream75.c。
补充两个优化时应注意的问题。
其一，RC4.C中的prepare_key函数和rc4函数各有几处取模操作符(%)，通常会编译为IDIV指令，我们知道除法会严重影响性能。应该改写，将%消灭。这个容易，既然运算的数据全为unsigned char，%256完全是多此一举。
剩下一个"% key_data_len"改为"-= key_data_len"的循环。
其二，编译选项。我虚拟机里是VC6，不同版本的Visual Studio选项有些许差异。应根据运行时的目标机器建立测试基准，耐心地试验各种选项组合，以确定最快的一个。
举个例子，/Ot意为"Favors fast code"，不要轻信编译器的优化能力。应选择/Os("Favors small code")。较少的机器指令会明显提高执行效率，有数倍的差距！
后来为加快进度，又试着写了一个四线程的版本：rc4KStream75MT.c。
单线程用/ML和/MD没有太大差别，而多线程一定要用/MT。
另外最好用Hiew等工具检查一下prepare_key和GetKeyStream两个关键函数的指令是否符合C代码的预期。理论上这两个函数最好用汇编来写，看了一下，感觉自己写出来的东西比编译器强不到那里去，而且后来很快就有了答案，好奇心既已满足，便不再深究。
没想到，在KeyLength=5的那个实例中答案很快揭晓，并且是唯一的匹配项。以下是验证程序汇集其它匹配Key的输出结果。
50 35 38 62 2C 1E 0C 6F
Keystream Key String
--------- --- ------
50 35 38 62 2C 1E 0C 6F 31 32 33 34 35 12345
50 35 38 62 1E 23 14 43 30 77 47 71 78 72 0wGqxr
50 35 38 62 33 61 75 03 31 47 3B 36 3D 4E 1G;6=N
50 35 38 62 95 A7 ED 12 32 4F 70 49 6F 31 2OpIo1
50 35 38 62 55 D1 B7 E4 30 32 67 61 71 39 65 02gaq9e
50 35 38 62 0B D1 62 59 30 33 57 72 52 6B 3D 03WrRk=
50 35 38 62 57 94 D7 D6 30 35 4D 56 57 61 48 05MVWaH
50 35 38 62 48 51 FE B6 30 30 32 72 3B 45 41 59 002r;EAY
50 35 38 62 5B 45 F7 54 30 30 33 63 5D 43 36 35 003c]C65
50 35 38 62 BC 87 E4 B9 30 30 33 63 6A 4F 67 3F 003cjOg?
50 35 38 62 80 FD 34 7A 30 30 33 64 50 69 45 5A 003dPiEZ
50 35 38 62 9E 7F E6 FE 30 30 34 48 7A 4E 68 32 004HzNh2
50 35 38 62 8A 2F 47 DB 30 30 35 63 50 3B 3B 4B 005cP;;K
50 35 38 62 2A 91 D0 81 30 30 35 71 55 44 72 40 005qUDr@
00 F8 7E 67 24 33 15 9C 31 32 33 34 35 36 123456
7D 0F D8 8F D1 B4 16 6C 31 32 33 34 35 36 37 1234567
BB F3 39 D4 09 B1 DE A7 31 32 33 34 35 36 37 38 12345678
让人大跌眼镜，第一行的Keystream竟然与目标完全一致！我们可以大胆地猜测它就是正确的Key，又一次证明简单密钥的危险！最后三行是有意增加的，列在这里仅为了对比。
五．单线程与多线程性能对比
以下为附件中最终版本找到Key时的运行记录：
Found: 31 32 33 34 35 52.265 sec.
Start: 2013-07-04 16:43:06.687
End: 2013-07-04 17:46:41.531
Execution time: 3814.844 seconds. 1h03m34s
rc4KStream75MT_5.exe
Found: 31 32 33 34 35 81.766 sec.
Start: 2013-07-04 15:40:03.000
End: 2013-07-04 16:08:41.812
Execution time: 1718.813 seconds. 28m38s
单线程找出它用了52秒，而多线程用了81秒，这有点奇怪。整个5字节的Key搜索完成，单线程用时约一小时，多线程仅耗时28分钟。
用于编程虚拟机的Host是更早的双Intel Xeon CPU，共四核。但VM只配置了一个处理器、单核。以下为两台机器跑完KeyLength=3后的耗时对比(秒为单位)：
---------------- --------------
rc4KStream75_3.exe 0.671~0.688 1.62 ~1.78
rc4KStream75MT_3.exe 0.312~0.344 1.296~1.313
就虚拟机自身比较，多线程要快于单线程。无单核物理机进行对比测试。
最后对完成KeyLength=6~8的用时作一个大致估算，以4字节Key的实际数据为依据：
Start: 2013-07-04 16:38:59.593
End: 2013-07-04 16:39:50.515
Execution time: 50.922 seconds.
5 50.922 * 75**1 = 3819 1h03m39s(结果与实际接近)
6 50.922 * 75**2 = 286436 3D07h33m56s
7 50.922 * 75**3 = 21482718 248D15h25m18s
8 50.922 * 75**4 = 1611203906 18648D04h38m26s(51Y33D)
rc4KStream75MT_4.exe
Start: 2013-07-04 16:13:09.015
End: 2013-07-04 16:13:31.609
Execution time: 22.594 seconds.
5 22.594 * 75**1 = 1694 28m14s(结果与实际接近)
6 22.594 * 75**2 = 127091 1D11h18m11s
7 22.594 * 75**3 = 9531843 110D07h44m03s
8 22.594 * 75**4 = 714888281 8274D04h04m41s(22Y244D)
测试是一门单独的学科，这里并不严格，只想借此说明问题。这台机器上，在Key为8字节、各字节为75个可能和只计算Keystream首4字节的情况下，单线程需要51年，多线程也需要近23年。
可见密钥长度和复杂程度的重要性！
六．附件说明
-------- ------------------ -----------
1222 RC4.ZIP Cypherpunks邮件列表的C源码
4403 rc4KStream75.c 单线程C源码
6979 rc4KStream75MT.c 四线程C源码
16384 rc4KStream75.exe MD5: 844a293a3fe268312e2babbbe8b095e4
45056 rc4KStream75MT.exe MD5: 1aa9459479658fb5230bd1e1721b8ae9
因为简单，就没有项目了。直接用命令行进行Build，最终的编译选项见各源码注释，KeyLength=3。
视你的机器和C编译器版本，调整选项重新编译。
如果用我的exe，对其它KeyLength，找个编辑器直接改exe的一个字节就好了：rc4KStream75.exe文件偏移0x3010处，rc4KStream75MT.exe文件偏移0x8030处，现在是0x03，可改为0x01~0x08。
还有些问题，比如提高进程自身的优先级会对速度有多大影响，中断后下次怎么继续等等，留给感兴趣的人接着玩吧！
字典攻击方面，要得到本例的答案，应该不会需要太多时间。几年前干过一件事，好象是用Rainbow字典，为Windows登录密码大概是长度为8、字母+数字的组合生成约1GB的Hash库，时间久已记不清了，残存的印象是从当时的测试结果来看，效果非常好。另外也有网站提供根据SAM里的Hash查明文的服务。
以前数学太烂，写代码又非职业程序员，基本上复制粘贴。这两天看温网，转播评论员说，“业余爱好者千万别学A.radwanska”。确实看她打球就觉得别扭，瞧瞧人家小德的动作多么规范！就是这个意思了。
Anyway，文章写出来总是希望有更多人读的。好评/差评？亲，你怎么看
。
阿里云助力开发者！2核2G 3M带宽不限流量！6.18限时价，开 发者可享99元/年，续费同价！
|
|
|---|---|
|
|
|
|
|
好评 这个可以有
51年 
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
我一年无法直视？
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
