采用GPU的ZIP密码恢复算法

admin管理员组

文章数量:1533843

2024年4月23日发(作者：)

采用GPU的ZIP密码恢复算法

李永达;王党辉;黄小平

【摘 要】Generally, zip password recovery software uses CPUs to crack

password, which can only try a few passwords per seconds, and it takes a

long time to find out the correct password. This paper proposes a fast zip

password recovery algo-rithm on GPU, the AES decryption and HMAC

algorithm are optimized for GPU specially. This algorithm takes advan-tage

of password verification value to reject many incorrect passwords. The

algorithm uses macro to optimize the usage of GPU registers, the

computing resources have been fully used. The experimental result shows

that GPU can achieve 11.09 times speedup compared with the CPU.%常用

的zip密码恢复软件使用通用处理器进行密码恢复，每秒尝试密码次数少，往往需

要很长时间才能找到正确密码。为了提高密码破解效率，提出了GPU平台上的快

速ZIP密码恢复算法，针对GPU的特点，重点优化了寄存器使用以及存储器访问，

对AES和HMAC算法进行了并行优化，充分发挥了GPU大规模并行运算的优势，

并利用ZIP文档格式中的密码校验位提前筛选密码，大部分错误密码都不需要进

行后续运算。实验结果表明，恢复AES-128加密的ZIP文档，基于GPU的算法

实现了11.09倍的加速比。

【期刊名称】《计算机工程与应用》

【年(卷),期】2015(000)002

【总页数】4页(P190-193)

【关键词】ZIP密码恢复;图像处理单元(GPU);高级加密标准(AES);哈希运算消息认

证码(HMAC)

【作 者】李永达;王党辉;黄小平

【作者单位】西北工业大学 计算机学院，西安 710129;西北工业大学 计算机学院，

西安 710129;西北工业大学 计算机学院，西安 710129

【正文语种】中 文

【中图分类】TP311.56

Zip压缩格式具有压缩速度快、压缩比高等优点，网络上大部分压缩文档都采用

zip格式，Zip文档采用AES（Advanced Encryption Standard）加密算法进行

数据加密并具有很高的安全性，随着网络应用的普及，加密的zip文档越来越多，

密码遗忘成为常见的问题，zip密码恢复已经成为密码学研究的一个重点[1]。由于

目前没有有效的密码攻击方法破解AES密钥[2]，所以zip文档密码恢复只能采用

暴力破击和字典攻击的办法，很多zip文档的密码都含有数字和特殊字符，并且密

码长度超过6位，常用的zip密码恢复软件采用CPU尝试密钥，需要很长时间才

能得到正确的密码。

为了提高密码恢复的效率，本文实现的算法利用GPU大规模并行计算的优势进行

zip密码恢复[3]。该算法采用Nvidia的CUDA（Compute Unified Device

Architecture）计算平台，CUDA是将GPU作为数据并行计算的软硬件体系[4]，

算法需要在该体系下针对GPU进行优化，充分利用GPU上的运算资源，达到快

速恢复密码的目的。该算法主要优化了访存结构，使得每个SM（Stream M

ultiprocessor）能容纳更多的线程[5]，同时优化了密码结构，尽量保持同一个

warp的线程执行相同的代码，减少了控制开销。利用加密文件的PV（Password

Verification value）筛选出候选密码[6]，只有候选密码才需要进行解密和生成数

据摘要。本文实现的密码恢复算法采用蛮力攻击的办法，对于5位密码加密的Zip

文件[7]，只需要3 m in即可找出正确密码。

Zip文档格式包括文件区和目录区，图1为Zip文档格式[3]。从zip文档格式中

可以看出，用户可以保存多个文件到一个zip文档中，而保存的每个文件中，都包

含文件头部和文件数据，最后是中央目录，中央目录保存每个文件头部信息的备份，

所以通过中央目录可以很快地查找到需要的文件。

在根据明文和密钥产生密文的时候，Zip加密程序采用基于计数器模式的AES算

法[8]，明文不是直接参与AES加密，而是先加密计数器，再将加密后的计数器与

明文进行异或操作。计数器初始值设置为0x00…0（16 B）[9]。图2为zip加密

过程示意图。

由于异或操作的反操作符是它自身，所以解密的过程和加密的过程完全相同，解密

过程的思路是：使用AES密钥加密计数器值，得到加密的计数器值，其再与密文

异或就能得到明文。所以在本文的代码中，只需要实现AES加密算法，就可完成

AES的加解密。

每一个加密后的文件都有36字节的加密开销[3]，如图3所示，包括SALT、PV

和MAC字段。

Zip文档解密的主要步骤为：

（1）PBKDF2（Passw ord B lock Key Derivation Function 2）根据用户输入的

密码和随机数SALT产生AES密钥，两个字节的PV。

（2）产生的PV与加密文件中的PV比较，如果相同，则确定输入的密码是候选

密码。

（3）根据候选密码产生AES密钥，以计数器模式进行加密[10]，加密后的计数器

与文件异或，得到解密的数据。

（4）HMAC算法根据解密的数据生成10 Byte的MAC，将MAC与加密文件中

的MAC比较，如果相同，则可以确定这个密码是正确的密码。

（5）使用正确的密码，重复步骤（3），得到解密的zip文档。

密码恢复算法需要用到密码搜索空间[11]，密码搜索空间是通过设置密码长度和字

符集建立的穷举空间。该算法采用一个线程尝试一个密码的方法，通过大量的并发

线程提高效率。密码恢复算法采用命令行的方式运行，所以需要有命令行语法分析

单元，还有一些配置参数用来配置密码搜索空间、GPU优化参数以及输出模式

（少量输出、多行输出以及不输出）。性能评估使用CUDA时间测量函数

cudaEventElapsedTime[11]，该函数能精确到毫秒，而且能准确地统计程序在

GPU上花费的时间。为了更好地利用显卡的计算资源，密码恢复算法检测显卡信

息[11]，根据显卡上资源配置情况，动态生成Block和Gird大小。

3.1 算法结构

Zip密码恢复算法每一个CUDA线程对应一个密码，每个线程都执行相同的操作，

线程间不进行任何通信，从而避免了线程同步。线程第一步是计算出PV，根据

PV提前否决密码，大部分线程会在PV校验处结束，而不执行解密和MAC校验

[12]。通过PV校验的密码成为候选密码，候选密码保存在显存中，接下来GPU

会启动第二批线程对加密的文件执行解密操作，并进行MAC校验[12]，通过

MAC校验的密码即为正确密码。图4为密码恢复算法结构图。

根据GPU的特点，密码恢复算法主要优化了访存部分。算法中尽量通过增加计算

来减少访存，同时采用宏定义的方法，CUDA线程中不调用任何函数，也不使用

内联函数，只使用宏定义。这种方法可以避免函数调用过程中不断地申请新的寄存

器文件，使得一个SM（Stream M ultiprocessor）能容纳更多的Warp。

由于GPU上每个线程都要对Zip文件进行AES解密，而AES解密是一个复杂的

过程，所以密码恢复算法首先找出Zip文档中最小的Zip文件，采用最小的Zip

文件可以节约GPU上的存储资源，而且每个线程只需解密最短的文件，可以节约

计算时间。密码恢复算法将Zip文件拷贝至常数存储器（Constant memory）中，

该存储器中的数据是可以被缓存的，第一个线程读取Zip文件后，该文件就被保

存到了快速缓存中，之后所有的线程都能从缓存中读取Zip文件，如果不考虑缓

存的块冲突，缓存读取只需要一个周期就能完成[13]，从而极大地提高了访存效率。

密码恢复算法用到的密码搜索空间保存在主存中，GPU中每个线程对应一个密码，

所以密码不适合保存在共享存储器中，本文的密码恢复算法采用zero copy功能

直接将密码拷贝到线程的寄存器中，避免了主存和显存之间数据拷贝的操作。

3.2 AES解密

AES轮数依赖于密钥长度：16 Byte密钥（AES-128）是10轮，24 Byte密钥

（AES-192）是12轮，32 Byte密钥（AES-256）是14轮。使用密钥扩展算法，

16 Byte密钥扩展为44字，24字节密钥扩展为52字，32 Byte密钥扩展为60

字，每一轮使用4个字作为轮密钥[14]。本文采用T表方式来构造AES算法，如

图5所示。

该算法需要四个T表，还需要一个S盒，每一个都是256项，总共需要

5×256×4 B，这会占用5 kB空间。这样的访存对于GPU来说是非常不合理的，

通过观察发现，根据一个T表可以构造出另外三个T表，而T表其实都是由S盒

产生的。本文采用一个T表和一个S盒的方式，另外三个T表根据当前T表计算

得出，进一步优化，可以只使用一个S盒，这种办法能更有效地降低GPU的访存

延迟。如果使用PV提前否决密码的方式，需要执行AES算法的进程会非常少，

所以本文采用常数存储器来保存T表和S盒。如果不使用PV提前否决密码，采用

共享存储器来保存T表和S盒，首先将这两部分数据保存在常数存储器中，然后

再通过线程读入共享存储器，将T表和S盒相邻的数据保存在不同的共享存储器

块中，这样可以减少Bank Conflict，优化对共享存储器的访问。

3.3 HM AC算法

HMAC是密钥相关的哈希运算消息认证算法[6]。根据输入的密钥和消息，HMAC

使用Hash函数生成一个消息摘要作为输出。HMAC将Hash函数视为“黑盒”，

将其封装成一个模块，根据需要可以方便替换成更快和更安全的Hash函数。

本文的算法针对GPU进行了优化，尽量采用宏定义的方式来实现。由于每个密码

只需要使用一次，因此，使用ZeroCopy技术[15]在主机端和设备端传递密码。

同时减少寄存器的使用，但是由于整个程序用到了HMAC，AES算法，整个

cuda程序的瓶颈依然在于寄存器的合理利用，而且对于不同的显卡，资源利用率

也不同，为了解决这个问题，本文采用了自动检测的方法，程序运行前，先检测显

卡的信息，采用正则表达式提取出版本、流处理器个数、寄存器个数等信息，根据

这些信息决定Grid和Block配置。

Zip密码恢复程序采用CUDA编程，在GPU上实现了高效率的密码恢复。该程序

运行环境如表1所示。

Zip密码恢复程序采用的算法会反复地执行相同操作，如果不限制线程使用寄存器

的数量，程序总共需要152个寄存器。图6表示了当Block size设置为256时，

一个SM（Stream M ultiprocessor）中warp数量与每个线程使用寄存器数量之

间的关系。由图6可知，寄存器使用得越多，流处理器能并行执行的线程数越少。

Zip密码恢复程序最少需要用到50个寄存器。

Block和Grid的大小通常设置为2的指数，密码恢复程序的效率会随着这两个参

数的增长而增长，但是Block大小影响更为明显。当Block大小超过128时，这

种增长趋于平滑，这是由于当Block大小超过128时，每个SM上的Warp数都

超过4，这能保证每个SM都处于饱和状态。图7为统计结果。

在实验过程中，采用穷举的办法比较了zip密码恢复程序在CPU和GPU上每秒

尝试的密码数，并分别对AES-128和AES-256加密的zip文档进行比较[15]，不

同的zip文档大小也会有不同的比较结果，但是该程序可以找出zip文档中最小的

文件进行密码恢复，在常见的zip文档中，最小文件往往都不会超过1 MB，所以

文件长度的影响不明显。表2为该程序在CPU与GPU上的比较结果。

本文实现了基于GPU的zip密码恢复，充分发挥了GPU大规模并行运算方面的

优势，采用一个线程尝试一个密码的方式，线程之间相互独立。该设计重点优化了

访存结构，GPU上的运算资源得到充分利用，与CPU上的zip密码恢复程序相比，

实现了10～20倍的加速比。

【相关文献】

[1]Biham E，Kocher P C.A known plaintext attack on the PKZIP stream cipher[C]//FSE，

1994：144-153.

[2]Morris R，Thomson rd security：a case history[J]. Communications of the

ACM，1979，22（11）：594-597.

[3]Sanders J，Kandrot 高性能编程CUDA实战[M].聂雪军，译.北京：机械工业出版社，

2011：27-41.

[4]张舒，褚艳利，赵开勇，等.GPU高性能运算之CUDA[M].北京：中国水利水电出版社，2009：

152-163.

[5]Farber R.高性能CUDA应用设计与开发[M].于玉龙，唐堃，译.北京：机械工业出版社，2012：

2-16.

[6]Burr W，Dodson D，Polk onic authentication guideline[R].[S.l.]：NIST Special

Publication，2004.

[7]W inZip[EB/OL].[2013-04-10].http：//www.w .

[8]Phong P H，Dung P rd recovery for encrypted ZIP archives using GPUs[C]//So

ICT’10，Hanoi，Vietnam，2010.

[9]Daemen J，Rijmen proposal：rijndael[Z].1999.

[10]Thorpe J，van Oorschot cal dictionary and the memorable space of graphical

passwords[C]//Proc 13th USENIX Security Symposium，2004：135-150.

[11]_C programm ing guide[R].Sisha Clara：NVIDIA，2012.

[12]FIPS198：the keyed-Hash Message Authentication Code（HMAC）[EB/OL].（2002-

03-11）.http：///publications/.

[13]Standaert F，Rouvroy G，Quisquater J J，et al.A time/ memory tradeo ff using

distinguished points：new analysis and FPGA results[C]//LNCS 2523：Proc CHES 2002，

2002：593-609.

[14]Gentry C，Mackenzie P，Ramzan rd authenticated key exchange using

hidden smooth subgroups[C]//CCS’05，2005：299-309.

[15]Kasper E，Schwabe and tim ing-attack resistant AES-GCM[C]//CHES’09，

2009.

本文标签： 密码算法采用文件使用