基于分布式计算的暴力破解分组密码算法

Vol .34 No.13 Computer Engineering · 安全技术 ·

文章编号：1000—3428(2008)13—0121—03

文献标识码：A

2008年7月

July2008

中图分类号：TP309

基于分布式计算的暴力破解分组密码算法

张丽丽1,2,3，张玉清2

(1. 西安电子科技大学通信工程学院，西安 710071；2. 中国科学院研究生院国家计算机网络入侵防范中心，北京 100043；

3. 河南科技大学电子信息工程学院，洛阳 471003)

摘 要：暴力破解分组密码算法是密码学的重要研究方向。该文基于分布式算法，设计具有高通用性的暴力破解分组密码软件。在局域网内对分组密码算法DES和SMS4的暴力破解进行模拟实现，测试其性能并分析DES和SMS4的暴力破解结果。实验结果表明，该软件通用性较强。

关键词：暴力破解；分布式计算；分组密码

Brute Force Attack on Block Cipher Algorithm

Based on Distributed Computation

ZHANG Li-li1,2,3, ZHANG Yu-qing2

(1. School of Telecommunication Engineering, Xidian University, Xi’an 710071;

2. National Computer Network Intrusion Protection Center, Graduate University of Chinese Academy of Sciences, Beijing 100043;

3. Electric and Information Engineering College, Henan University of Science and Technology, Luoyang 471003)

【Abstract】Brute force attack on block cipher algorithm is an important direction of cryptology. Software of brute force attack on block cipheralgorithms is designed based on distributed computing. Brute force attack on block cipher algorithms DES and SMS4 are simulized in the LAN andthe function test to the software is carried on. It analyzes the software and results of brute force attack on DES and SMS4. Experimental results showthat this software has strong commonability.

【Key words】brute force attack; distributed computation; block cipher

随着社会经济的发展，信息安全受到越来越多的重视。密码学是信息安全的基础与核心，暴力破解分组密码算法是密码学研究的一个重要方向。通过对暴力破解密码算法的研究与实现，可以很好地检验密码算法的基本安全性，从而设计更可靠的密码算法。20世纪90年代以前，主要采用硬件方法实现对分组密码算法的暴力破解[1-2]。随着计算机技术特别是互联网的飞速发展，人们开始采用分布式计算[2]实现对分组密码算法的暴力破解。国内对该领域的研究很少，而国外已实现对40 bit的RC4, 56 bit的DES和 bit的RC5的暴力破解，目前正在破解72 bit的RC5。本文采用分布式计算实现暴力破解分组密码算法。 它的计算机上。 2 暴力破解分组密码算法软件的设计 2.1 软件设计思想 暴力破解分组密码算法软件的设计思想如图1所示。 K加密K加密M1C1

(a)生成C1 (b)生成C2 C1解密是否满足条件是解密是否满足条件是提交密钥否密钥空间 M2C2

1 暴力破解和分布式计算介绍 1.1 暴力破解 暴力破解[3]也称为穷举攻击，它通过穷举所有可能的密钥进行破解。暴力破解是密码分析中最简单的方法，它以简单的轮环形式工作，具体步骤如下：(1)创建一个密钥猜想；(2)送入猜想的密钥；(3)判断猜想的密钥是否正确；(4)如果正确则获得密钥，否则返回第(1)步。 1.2 分布式计算 分布式计算是一门计算机科学，它研究如何把一个需要巨大计算能力才能解决的问题分成较小的部分并把这些部分分配给众多计算机进行处理，通过综合这些计算结果得到最终结果。分布式计算具有以下优点：(1)实现稀有资源共享；(2)在多台计算机上平衡计算负载；(3)把程序放在最适合运行

C2(c)暴力破解C1 图1 软件设计思想 暴力破解分组密码算法软件的设计步骤如下： 基金项目：国家自然科学基金资助项目(60573048, 60373040)；中国科学院研究生院科研启动基金资助项目

作者简介：张丽丽(1979－)，女，硕士研究生，主研方向：网络与信息安全；张玉清，教授、博士生导师

收稿日期：2007-12-12 E-mail：lillyzh@126.com

—121—

(1)得到需要破解的密文。用分组加密算法，对一个明文块(不同的算法分组长度可能不同)M1用密钥K加密得到密文C1，见图1(a)。对另一个明文块M2用K加密得到密文C2，见图1(b)。 (2)暴力破解密文C1。如果某个密钥解密C1得到的明文满足如下条件：每个字节都是69个字符(A-Z, a-z, 0-9, 空格和几个常见标点符号——“,”“.”“:”“!”“?”“;”)之一，则该密钥可能是正确的加密密钥，用该密钥解密密文C2(解密C2的目的是减小提交错误密钥的概率)，若得到的明文仍满足上述条件，则客户端认为该密钥是正确加密密钥，把该密钥上传给服务器，见图1(c)。 服务器必须进一步检测客户端上传的密钥，只有解密得到有意义明文的密钥才是正确的加密密钥。 2.2 软件架构 软件架构图包括服务器和客户端2个部分，如图2所示。客户端从服务器下载密钥块信息，进行破解运算，完成计算后把结果上传给服务器。两者之间采用UDP作为通信协议。 服务器服务端保存信息到数据库更新密钥块数据显示信息显示框数据库从数据库读密钥快信息(密钥块0～密临时储存钥块N-1）密钥块信息密钥块结果通信组件UDP数据包通信组件密钥块信息 运算结果解密算法显示信息显示框客户端 图2 软件架构 数据库里存储着密钥块数据。每条数据包含的密钥块信息如下：ID表示序列号；BeginPos表示开始位置；EndPos表示结束位置；BeginTime表示开始时间；Status表示状态；Result表示结果。由于数据库记录着当前的用户信息、任务分配状况、分配策略等重要信息，因此须对其进行重点保护。 2.3 软件的功能介绍 2.3.1 服务器 服务器的主要功能是对任务进行如下处理： (1)任务分块。将巨大的密钥空间分成若干较小的密钥块，每个密钥块里含有若干个密钥。密钥块的具体划分与分组密码算法有关。 (2)密钥块状态跟踪。在给客户端分发密钥块前，服务器需要跟踪密钥块的状态。软件设计中把密钥块状态分为未分配、已分配但未返回结果和计算完毕3种情况。软件设定的返回结果的最大时间是10 min，在10 min内仍未返回结果的密钥块将被重新分配。 (3)任务分发。服务器根据跟踪到的密钥块状态，把未分配或已分配但未返回结果的密钥块分发给客户端。 2.3.2 客户端 不同密钥块所对应客户端软件的主要功能是从服务器下载密钥块并进行破解运算，不同密钥块对应不同的密钥集合。当客户端完成从服务器下载密钥块数据后，先找到该密钥块对应的密钥集合，再调用内嵌的解密算法，用各个密钥逐个进行解密运算，计算完毕后把计算结果反馈给服务器。 —122

—3 暴力破解DES算法 3.1 DES算法[4]简介和计算量分析 DES是分组密码算法，它把 bit的明文用 bit的密钥加密为 bit的密文，由于密钥的第8n位(n=1,2,…,8)是校验位，用于保证含有奇数个1，因此密钥实际只有56 bit。解密算法与加密算法结构相同，但轮密钥的使用顺序相反。 DES实际密钥只有56 bit，破解一个由DES算法加密的密文，其密钥空间包含256即72 057 594 037 927 936个密钥，计算量巨大。 3.2 DES算法的暴力破解 笔者在局域网内模拟实现了DES算法的暴力破解，即在给定密钥前4 B的情况下进行暴力破解，这种情况下密钥空间包含228个密钥。模拟过程用到的数据如下： 对明文M1“zhanglil”用密钥K加密得到密文C1；对明文M2“testdata”用同样的K加密得到密文C2。以十六进制表示K, M1, C1, M2, C2： K为31 32 34 37 61 62 67； M1为7A 68 61 6E 67 6C 69 6C； C1为0C F2 E7 4E 0F 0A 05 99； M2为74 65 73 74 61 74 61； C2为6B C4 2C B1 E0 06 BF E2。 在软件实现时，C1, C2已知，破解任务是在含有228个密钥的密钥空间寻找加密密钥。 服务器把密钥空间划分为214个密钥块，每个密钥块包含214个密钥。 服务器程序启动后，从数据库读取数据。当客户端请求数据时，服务器会根据跟踪到的密钥块状态发送合适的密钥块。服务器程序运行时，各个密钥块的状态及该密钥块的分发时间和结果返回时间都会显示在界面上。 客户端程序内嵌DES解密算法进行解密运算，其设计面临的2个关键问题如下： (1)因为客户端从服务器下载的是密钥块，所以要建立密钥块与其密钥空间的对应关系。 (2)因为DES算法中密钥的第8n位(n=0,1,…,8)是校验位，所以要保证解密前解密密钥后4 B的每个字节的二进制都包含奇数个1。 在客户端程序设计中同时解决上述2个问题，具体如下：(1)设从服务器下载的密钥块的BeginPos(开始位置)是n，则n的取值为0～214-1。 (2)根据校验结果，确定密钥的第5个字节。计算a=[n/128]，a的取值范围是0～127。把2a转化为二进制，判断含有1的个数，若含有奇数个1，则把2a赋给密钥的第5个字节；若含有偶数个1，则把2a+1赋给密钥的第5个字节。 (3)根据校验结果，确定密钥的第6个字节。计算b=n mod 128，b的取值范围是0～127。检验2b的二进制中含有1的个数，若含有奇数个1，则把2b赋给密钥的第6个字节；若含有偶数个1，则把2b+1赋给密钥的第6个字节。 (4)通过一个确定的n唯一确定第5个和第6个字节后，用一个for循环遍历第7个字节的27个取值，在for循环内再嵌套一个for循环遍历第8个字节的27个取值。在确定 第7个和第8个字节前，也要进行奇偶校验。 (5)每下载一个密钥块，通过2个for循环逐个遍历该密钥块对应的214个密钥，每进行一个密钥就调用一次解密函数。 遍历完密钥块内所有密钥后，客户端把运算结果上传给服务器。 (6)客户端程序运行时，接收每个密钥块的时间、该密钥块任务完成时间及当前正在计算的密钥块都会显示在界 (4)通过一个确定的n唯一确定第13个和第14个字节后，用一个for循环遍历第15个字节的28个取值，在for循环内再嵌套一个for循环遍历第16个字节的28个取值。 (5)每下载一个密钥块，通过2个for循环就可以逐个遍历面上。 3.3 软件性能测试 为了检测本文软件的性能，笔者用8台电脑测试214个即16 384个密钥块(每个密钥块包含214个密钥)，结果见表1。 表1 局域网内暴力破解DES的测试结果 密钥块数 电脑数 时间/s 平均速度/(keys·s-1) 16 384 1 38 963 6 8 16 384 2 19 485 13 776 16 384 4 9 741 27 557 16 384 8 4 803 55 8 测试结果表明，1台CPU为Pentium4, 2.8 GHz，内存为256 MB的电脑，计算完密钥空间里的228个密钥需36 3 s，即10 h 49 min。测试所用8台电脑的硬件条件基本相同。 4 暴力破解SMS4算法 4.1 SMS4算法介绍和计算量分析 SMS4是我国在2006年1月6日公布的第一个商用分组密码算法。该算法的分组长度是128 bit，密钥长度为128 bit，即16 B。加密算法和密钥扩展算法都采用32轮非线性迭代结构。解密算法与加密算法的结构相同，但轮密钥的使用顺序相反。SMS4算法的密钥是128 bit，破解一个由SMS4算法加密的密文，其密钥空间含有2128个密钥。 4.2 SMS4算法的暴力破解 本文在局域网内模拟实现了SMS4算法的暴力破解。同模拟DES算法暴力破解一样，只对密钥后4 B形成的密钥空间进行暴力破解，此时密钥空间含有232个密钥。模拟过程所用数据如下：对明文M1“welcome to China”用密钥K加密得到密文C1；对明文M2“hello, everybody””用K加密得到密文C2。用十六进制表示K, M1, C1, M2, C2： K为01 23 45 67 AB CD EF FE DC BA 98 76 32 10； M1为77 65 6C 63 6F 6D 65 20 74 6F 20 63 68 69 6E 61； C1为8F 39 52 4E 7E 7A D5 7F 94 01 00 D4 47 D7 34 A9； M2为6E 65 6C 6C 6F 2C 65 76 65 72 79 62 6F 6E 79 21； C2为02 67 61 6C 3B 4D 1B 62 28 BA 2D 4B 18 88 1D。 在软件实现时，C1, C2已知，破解任务是在含有232个密钥的密钥空间中寻找加密密钥。暴力破解SMS4与暴力破解DES类似，只是服务器端任务的划分和客户端的破解运算模块不同。 服务器把密钥空间划分为216个密钥块，每个密钥块包含216个密钥。 因为在SMS4算法中密钥不含校验位，所以客户端程序设计相对简单，关键是建立密钥块与其密钥空间的对应关系，具体如下： (1)设从服务器下载的密钥块的BeginPos(开始位置)是n，则n的取值为0～216-1。 (2)确定密钥的第13个字节。计算a=[n/256]，a的取值范围是0～255。把a赋给第13个字节。 (3)确定密钥的第14个字节。计算b=n mod 256，b的取值范围是0～255。把b赋给第14个字节。 该密钥块包含的216个密钥，每进行一个密钥就调用一次解密函数。遍历完密钥块内所有密钥后，客户端把运算结果上传给服务器。 4.3 软件性能测试 为了检测软件性能，笔者用8台电脑(即破解DES所用的8台电脑)对3 000个密钥块(每个密钥块包含216个密钥)进行测试。由于SMS4的破解速度较慢，而密钥空间较大，因此本文测试了部分密钥块，测试结果见表2。 表2 局域网内暴力破解SMS4的测试结果 密钥块数 电脑数 时间/s 平均速度/(keys·s -1) 3 000 1 45 011 4 367 3 000 2 22 580 8 703 3 000 4 11 265 17 452 3 000 8 5 631 34 915 分析对数据库中232个密钥块破解时间，统计得1台电脑运算完密钥空间的232个密钥大约需要273 h 16 min。 5 测试结果分析 本文软件的客户端按从小到大的顺序下载密钥块，在穷举密钥块所对应密钥空间内的密钥时，按密钥对应的值从小到大逐个进行搜索，因此，搜索到加密密钥的时间与密钥对应的值有关，对应的值越大，破解成功的时间越长。 笔者在局域网内模拟实现了分组算法DES和SMS4的暴力破解。从客户端返回的运算结果表明，在模拟实现DES算法的暴力破解时，只有密钥块6193的返回结果中包含密钥，且密钥块6193返回的密钥是笔者所用的加密密钥 (31 32 34 37 61 62 67)。在模拟实现SMS4算法的暴力破解时，只有密钥块30292的返回结果包含密钥，且密钥块30292返回的密钥是笔者所用加密密钥(01 23 45 67 AB CD EF FE DC BA 98 76 32 10)。由软件性能测试结果可知，暴力破解SMS4的速度比DES慢，这是因为SMS4加密算法的轮数比DES多。由于SMS4的密钥比特数比DES长很多，在同等条件下暴力破解SMS4算法比暴力破解DES算法所用时间长很多，因此在抗暴力破解方面SMS4比DES算法强。暴力破解的速度不仅跟分组算法有关，受参与计算的机器的性能的影响，机器上其他程序的运行也会影响该暴力破解速度。 6 结束语 本文在局域网内模拟实现了暴力破解分组密码算法DES和SMS4。下一步工作将考虑在互联网上实现对DES和SMS4的暴力破解。 参考文献 [1] Electronic Frontier Foundation. Cracking DES: Secrets of Encryp-

tion Research, Wiretap Politics, and Chip Design[Z]. 1998.

[2] Curtin M, Dolske J. A Brute Force Search of DES Keyspace.

(1998-05-11). http://www.interhack.net/pubs/des-key-crack/. [3] 付安民. 对称密码算法暴力破解的研究现状和进展[C]//北京地

区高校研究生学术交流会议论文集. 北京: [s. n.], 2006. [4] 杨 波. 现代密码学[M]. 北京: 清华大学出版社, 2003.

—123—