在多核FPGA上实现Office文档口令破解的方法

李丽平,周清雷,李 斌

1(郑州大学 信息工程学院,郑州 450001)2(中国人民解放军信息工程大学 信息工程学院,郑州 450000)

1 引 言

当今社会是一个信息社会,随着计算机技术的发展,人们每天都要接触大量的电子文件,Office 是日常接触较频繁的电子文件,其中一些重要的资料以加密的形式保存.但间隔比较久就很容易忘记文件的加密口令,有可能会导致重要数据的丢失,这样会带来很多不便.基于此问题,设计专用的口令综合破解平台显得尤为重要.

目前市场上主要的Office办公软件Microsoft Office是一套由微软公司开发的办公软件,包含若干组件,最常用的组件包括:Word、 Excel、Powerpoint等.由于微软操作系统在计算机市场上占有的份额,使用Office文档的人数越来越多,一些重要信息需要进行加密保存和传输.因此信息的安全性和Office文档的保密性得到了广泛的关注.同时Office加密文档的口令恢复问题也越来越突出.本文着重研究Microsoft Office的加密文档破解技术,以下所称Office亦指Microsoft Office.

对于文档类口令破解的方法多种多样,常规的的破解方式为暴力破解,暴力破解的核心是枚举,即将口令字符集中所有的可能进行穷举验证[16],这种方式的理论成功率可以达到 100%,但是,口令空间巨大,穷举完所以口令所耗费的时间是无法想象的.一般的说,每个人常用的口令是有一定规则的.要破解文件口令只要对部分特定字符或者字符串进行组合生成口令字典即可,而不需要穷举整个口令字符空间,字典破解被认为是非常有效的破解方法[6].但是随着用户口令长度增加,口令空间组合方式爆炸式增长,字典文件中的候选口令数量急剧增加,验证时间越来越长.建立高效地用户口令字典,提高口令验证速度显然成为主要制约.

由于口令数量的陡增,口令的验证时间越来越长,单纯依靠 CPU 已经无法满足加密文档破解的需求.随着并行计算的发展,FPGA 已经广泛的应用于并行计算的各个领域.对比 CPU和GPU,FPGA打破了顺序执行的模式,利用硬件并行的优势,采用流水线模式,在每个时钟周期内完成更多的处理任务[1,4],而多核FPGA是将多个FPGA芯片集成到一块板卡上,实现多个流水线的并行计算.所以多核FPGA 更适合并行处理大量数据的计算,可以同时并行验证多组口令,极大的提高了口令验证的速度.本文基于多核FPGA设计口令破解程序,并以Office加密文档为实验对象,实现了Office加密口令的高效快速破解.

2 相关背景介绍

2.1 Office加密

Office作为使用最为广泛的办公软件,安全性主要利用其自身提供的加密功能实现,对文件进行加密,保护文档的内容不被泄露.对 Office 文档结构以及口令验证机制的研究可以参考Microsoft Office 的MS-CFB和 MS-OFFCRYPTO两个公开材料[2,3],其中MS-CFB主要涉及 Office 文档结构,包括存储格式、组织方式等;MS-OFFCRYPTO 主要涉及 Office 文件加密机制以及口令验证过程的加密参数等,本文通过对 Office 文件格式的分析,对Office 的加密机制进行了分析研究,澄清了加密参数的保存以及加解密过程.

根据微软官方的定义,加密Office文档需要包含Salt、KeyGeneration、Encryption、Decryption、Hash、 EncryptedVerifier和EncryptedVerifierHash 7种信息.这7种信息以流的形式保存在一个数据流中,这些信息的含义如表1所示.

Office各个版本的文档的加密的基本流程没有发生很大的变化,有上述参数参与的加密流程为:

·生成随机数Salt,并保存在文件的加密信息流中.

·读取用户输入的口令Password,和Salt生成加密密钥Key=KeyGeneration(Salt,Password).

·生成验证随机数Verifier,并进行加密运算EncryptedVerifier=Encryption(Key,Verifier),结果保存在文档的加密信息流中.

·对Verifier进行Hash运算VerifierHash=Hash(Verifier),EncryptedVerifierHash=Encryption(Key,VerifierHash).

·使用Key加密文件,得到加密文档.

2.2 多核FPGA

FPGA芯片是一种高性能计算平台[5].通过利用 FPGA 提供的并行性加速各种算法的执行,为构建高性能计算系统提供了条件[9,15].本文使用的FPGA芯片为Kintex®UltraScaleTMFPGA 加速开发套件.该套件基于可云端访问的生产就绪型 PCI 卡,支持各种框架、库、驱动器及开发工具,可通过 SDAccel 采用 OpenCL、C 或 C++轻松进行应用编程.其性能和优势为可重新编程的专用硬件适应于计算密集型应用,专门针对实况视频转码、数据分析以及人工智能 (AI) 应用(使用机器学习)的快速增长市场;单插槽 PCIe®半长全高封装兼容;可使用一款支持 75W 的卡通过传统 CPU 实现 10 至 30 倍的性能加速;采用 SDAccelTM开发环境,支持 OpenCL、C 和 C++.

表1 加密Office文档包含的信息
Table 1 Encrypts the information contained in an Office document

标识内容说明Salt16字节随机数,和用户口令一起生成加解密密钥HashHash函数,随着Office版本使用不同的函数.KeyGeneration密钥生成函数Encryption加密函数,使用KeyGeneration产生的密钥进行加密Decryption解密函数,使用上述密钥进行解密EncryptedVerifier加密的验证随机数,验证口令时读此数据EncryptedVerifierHashEncryptedVerifie的Hash希值,验证口令时读该数据

本文采用自主研发板卡,一块板卡集成4个上述的FPGA芯片,其芯片内部结构如图1所示.运用板卡在Vivado开发平台上用Verilog语言编写程序进行口令破解研究.

图1 FPGA器件的内部结构示意图Fig.1 Schematic diagram of the internal structure of the FPGA device

3 Office口令高速破解实现

3.1 破解流程简介

本文以Office2010加密文档为例,口令破解流程由文档解析、口令扩展、Hash迭代、AES、对比验证5个模块组成.其破解流程如图2所示.其中主要的计算部分是高次Hash迭代,其计算量在通用服务器平台上占99%以上.

Office加密文档口令验证过程中主要包括Hash迭代和AES算法.Hash迭代,主要进行十万次的SHA1迭代运算,Hash信息输出量500Mbps,在通用服务器平台上,该步骤的运算量占整个破解流程运算量的99%;AES128,以Hash迭代结果和部分验证串为输入,进行加密或解密操作(加密算法AES),主要进行字符串拼接、字符串比较、AES加解密等运算.以一条Hash流水线每秒可处理7.8M次SHA1运算,每个Hash迭代模块160条流水线计算,平均口令长度为20Byte,Office带宽需求为500Mbps.

图2 Office2010加密文档破解流程图Fig.2 Office2010 encrypted document cracking flowchart

3.2 SHA-1 算法

哈希函数是许多密码学算法的重要组成部分,使用SHA1,消息不超过512bits时可以生成一个160bit消息摘要[7,8].消息摘要比消息本身要短得多,所以它将花费更少的时间生成数字签名.更重要的是这个数字签名生成的消息摘要与通过消息生成的具有相同的安全性.消息不超过512bits时可以生成一个160bit消息摘要[13].程序流程为将整个消息分为多个512bit的数据块,分块处理,每块生成5个32bit的数据,组合为160bit的消息摘要.

在SHA1中需要一系列的函数和常数.每个函数ft (0≤t≤79)都操作32位字B,C,D并且产生32位字作为输出,以及常数K(t),如下公式(1)和(2)所示.

(1)

(2)

同时,需要5个32bit的缓冲区(H0,H1,H2,H3,H4)保存每一次的处理结果和作为下一次的输入.首次H0,H1,H2,H3,H4的值为:H0=67452301;H1=EFCDAB89;H2=98BADCFE;H3=10325476;H4=C3D2E1F0.

基于FPGA的SHA1算法算法流程如下:

1)将待处理的数据块分成相应的16个字W0,W1,…,W15,每个字32bit.

2)令A0=H0,B0=H1,C0=H2,D0=H3,E0=H4(H0,H1,H2,H3,H4为上述常数).

3)对与t从0到79进行如下循环:

Wt=S1(Wt-3⊕Wt-8⊕Wt-14⊕Wt-16),t≥16;

TEMP=S5(A)+f(t,B,C,D)+E+Kt+Wt);

E=D;D=C;C=S30(B);B=A;A=TEMP.

4)令H0=A+H0,H1=B+H1,H2=C+H2,H3=D+H3,H4=E+H4(更新H0,H1,H2,H3,H4).

最后的H0到H4就是当前的散列值输出.

3.3 AES算法

AES具有128比特的分组长度,3种可选的密钥长度,即128字节、192字节和256字节[10].AES的轮数Nr依赖于密钥长度.如果密钥长度为128字节,则Nr=10;如果密钥长度为192字节,则Nr=12;如果密钥长度为256字节,则Nr=14[18].

图3 字节序列被映射成一个4行多列的二维矩阵Fig.3 Byte sequence is mapped into a two-dimensional matrix of four rows and multiple columns

AES 算法有两个重要参数,状态矩阵和初始密钥,其中状态矩阵由字节序列映射得到,如图3所示.而初始密钥则用字(word)序列来表示.确定初始参数后,AES 算法的加密过程可以分为密钥扩展 (KeyExpansion)和轮变换两部分.其中,密钥扩展共进行16次逻辑操作.而轮变换又由字节替代(ByteSub)、行位移(ShiftRow)、列混合(MixColumn)和轮密钥加法(AddRoundKey)4 个模块组成[11,12].

流水线结构的AES算法密钥扩展流程:

1)将初始密钥以列为主,转化为4个32 bits的字,分别记为w[0…(Nk-1)];

2)按照如下方式,依次求解w[j],其中j是整数并且属于[4,K];(K=Nb*(Nr+1),Nb=4,Nr为轮数,128位密钥对应的Nr=10)

3)若j%4=0,则w[j]=w[j-4]⊕g(w[j-1]),否则w[j]=w[j-4]⊕w[j-1];

流水线结构的AES算法轮变换流程:

1)将待处理的128bit数据与密钥扩展函数模块输出的初始轮密钥进行AddRoundKey置换.

2)将置换的结果进行9轮字节代换、行位移、列混合和轮密钥加流水线操作.每级流水线之间用四个32bit的寄存器来保存中间结果.

3)将第9轮的结果进行字节代换、行位移、列混合和轮密钥加流水线操作,第十轮比前九轮少了中间的Mixcolumn置换.

最后输出128bit的解密结果.

在整个处理流程中,最主要的计算部分是高次SHA1迭代.在Office加密文档口令还原算法中,需进行10万次SHA1迭代.SHA1计算量在通用处理平台上,在Office中占99%以上.

3.4 基于多核FPGA的口令破解实现

目前常见的破解加密算法有三种:第一种方法就是暴力口令破解,穷举口令空间中所有的口令.第二种主要方式是字典破解,也是最常用的方式.其最大的优点是若加密文档口令采用的是有规律的字词时,将能够非常有效地缩短攻击者的破解时间.第三种方式主要是依靠生成 Rainbow Tables 即彩虹链表来进行破解,这种方法要求较高,目前只是在 Word2003、 Excel2003 可以使用[19].

随着用户的安全意识增强,口令长度日益增大,简单暴力破解,穷举口令空间也很难奏效.且密码算法强度大大加强,新的安全散列算法标准也已经确立,口令破解难度越来越大,这是一个无法回避的问题.本文方法一和二结合使用,即采用基于口令结构字典穷举口令的破解规则.设定好口令的排列规则或者生成规则,即时的生成密码,然后采用对应的目标算法进行验证.既提高破解效率又降低穷举量.

字典模式结构稍微复杂,首先是字典库的存储,字典库的大小以T为单位,容量要求只是一方面,另外一个重要的需求是读取速度,基于这两个方面需求选取容量大,速度快的盘阵作为传输口令的源头.但盘阵仍难以同时满足几十块FPGA板卡的处理需求.因此,将口令的传输设计成为流转链形式,其示意图如4所示,由此盘阵“多对一”的问题得到解决.同时,为了解决重新配置流转链的问题,采取了主动退出机制,即当中间某块FPGA所有任务都破解完毕,其主动退出任务破解流程,进而继续转发字典,使得字典文件顺利流转到下一块FPGA.字典文件的传输使用万兆网络,同时文档头信息、验证结果以及一些少量控制信息用千兆网络进行传输.

图4 字典模式FPGA互联结构Fig.4 Dictionary mode FPGA interconnect structure

基于多核FPGA的Office2010口令字典破解算法主要有5个模块组成,如图5所示,是基于FPGA的Office口令字典破解算法流程图.其中,口令生成模块被包括在核心算子模块内.

1)顶层接口模块(外部接口模块).数据流程:上位机输入数据(主要数据有Clk,Salt,PCI_HashInput,PCI_HashValue)到顶层接口,外部接口把数据传给寄存器,寄存器把数据分发给需要的模块.

图5 基于FPGA的Office口令破解流程图Fig.5 FPGA-based Office password cracking flowchart

2)寄存器控制模块.接收各个模块传输的数据,控制和转发各个模块的数据存储.

3)字典解析模块.将读取到的口令结构字典解析为核心算子能识别的符号.“#”后为明文、“?”后为掩码、“0a”是结束符、“?d”为数字、“?l”小写字母、“?u”大写字母、“?s”是特殊字符.然后将数字、小写字母、大写字母和特殊字符分别标记掩码mask为1、2、3和4传给核心算子,明文为不需要穷举的字符直接传输.

4)口令生成模块.生成口令给核心算子进行运算.生成流程:根据输入的掩码mask来决定每一位的穷举,mask取值1、2、3、4分别代表数字(？d)、小写字母(？l)、大写字母(？u)、特殊字符(？s).如果对应位的掩码为1就只穷举数字0-9(十六进制ASCII码为31-39),9的下一位为0.同理对应掩码为2就穷举a-z(十六进制ASCII码为61-7A),z的下一位为a;对应掩码为3就穷举A-Z(十六进制ASCII码为41-5A),Z的下一位为A;而对应掩码为4则穷举特殊字符(十六进制ASCII码为20-2f,3a-40,5b-60,7b-7f).其FPGA代码如下:

4′h4:begin if(next_ascii ==8′h2f) next_ascii <=8′h3a;else if(next_ascii ==8′h40) next_ascii <=8′h5b;else if(next_ascii ==8′h60) next_ascii <=8′h7b;else if(next_ascii ==8′h7f) next_ascii <=8′h20;end

5)核心算子模块.核心算子模块可以分为口令扩展、SHA1、AES三部分.口令扩展是对口令生成模块生成的口令进行处理,先转换为Unicode码,再扩展成512位字符串方便下一步的SHA1操作.SHA1模块是对数据进行100000次SHA1迭代,输出的数据给AES算法.AES模块是对SHA1后的数据进一步进行AES处理,生成一个验证串与外部接口输入的PCI_HashValue值进行比较,如果相同证明口令正确,输出口令.

4 实验分析

4.1 实验平台

本文提供的硬件平台如下:

CPU是4.0GB内存,AMD X4 750 3.4GHz处理器;GPU的型号为GTX1080;FPGA型号为XCKU115-2FLVB2104E XCKU060,每块 FPGA 的外围配有 DDR3 内存、千兆网卡、万兆网卡.软件平台如下:操作系统为Window7;开发平台为Vivado2017、Microsoft Visual Studio2015等.用Verilog语言在Vivado开发平台上设计运行口令恢复程序,仿真结果如图6所示.

图6 Office口令破解程序在Vivado平台上的仿真时序图Fig.6 Simulation timing diagram of the Office password cracking program on Vivado platform

4.2 实验结果对比

当前,国内外有很多针对口令破解的研究,并且开发了实用工具.主要有AOPR,Passware,AccentSoft,oclHashcat等.AOPR(Advanced Office Password Recovery)是俄罗斯 ElcomSoft 公司推出的一款口令破解软件,它只能运行在 Windows 操作系统.Passware Kit可高效的利用PC机上的多核CPU来加速密码恢复.oclHashcat 是一款支持 GPU 加速的的口令破解软件.

各常用口令破解软件的性能和功耗等如表2所示,其中加密文档类型为MS Office 2010,软硬件平台与4.1节一致.并通过公式(3)和公式(4)计算各软件的能效比和性价比.

能效比=性能/功耗

(3)

性价比=性能/价格

(4)

由表2可知,Hashcat和本文的基于FPGA的口令破解程序性能较高,性价比较好.其中,基于GPU的Hashcat口令破解软件和本文基于多核FPGA的口令破解程序的能耗分别是常规口令破解软件的23倍和62倍,性价比分别是15倍和18倍.

表2 各软件的性能对比分析
Table 2 Performance comparison analysis of each software

软 件性能(个/秒)功耗价格(RMB)能效比(个/秒/瓦)性价比AOPR505130W21003.880.24Passware69995W11907.360.59GPU Password Recovery75095W18507.890.41AccentSoft72595W18507.630.39Hashcat26841160W3699167.767.25FPGA138600278W4000498.228.66

基于多块GPU和FPGA用Hashcat和本文的口令破解程序进一步对Office文档进行口令恢复测试,实验对象为100个MS Office 2010加密文档,使用相同的字典对其进行口令恢复,其对比分析结果如表3和表4所示.

表3 基于多核FPGA的Office文档口令恢复测试结果
Table 3 Office document password recovery test results based on multi-core FPGA

规模时间s速度(个/s)功耗W能效FPGA∗112976138600278.19498.22FPGA∗43962453954885.32512.76FPGA∗821558346001562.7534.07FPGA∗16123714543413027.64480.35

由表可知,本文的基于多核FPGA的Office口令破解系统与Hashcat口令破解系统相比,其速度是Hashcat的5倍多,能效比是Hashcat的3倍多.本文基于多核FPGA的口令破解系统在速度和能效上有很大的提高.且由表3可知,FPGA板卡越多,其口令破解速率越高,能效比越高.

表4 基于GPU的Hashcat Office文档口令恢复结果
Table 4 GPU-based Hashcat Office document password recovery results

规模时间s速度(个/s)功耗W能效GPU∗16700826841160.85166.87GPU∗41816199037556.88177.84GPU∗8100691786221032.6172.98GPU∗1655083365042052.97163.91

5 结束语

本文实现了基于多核FPGA的Office口令破解程序.并以Office2010加密文档为例,与其他常用的口令破解工具做了详细的对比分析.相比于基于GPU的Hashcat口令破解工具,本文基于多核FPGA的口令破解程序速度提高了5倍多,能效比更是Hashcat的3倍多,其他常用口令破解软件的70倍.FPGA板卡越多,其口令破解速率越高,能效比越高.但是当板卡达到一定数量时,因受信息传输速率等因素的影响,其能效比会有下降.因此,下一步的工作主要是针对信息传输的瓶颈问题,做出一些改进,提高信息传输效率.以及口令破解字典的应用,研究更高效的口令破解字典.