在多FPGA上的高性能VPN口令恢复方法

韩 宇,周清雷,李 斌,朱维军

1(郑州大学 信息工程学院,郑州 450000)2(解放军信息工程大学 信息工程学院,郑州 450000)

1 引 言

虚拟专用网络(Virtual Private Network,VPN)属于远程访问技术,是在公共网络的基础上,通过隧道协议和密码技术建立的虚拟网络[1].对用户来说,使用 VPN 可以达到和使用专用网络同样的效果.用户能够通过VPN在外网访问企业或校园内网的服务器资源,并且为了保证数据安全,VPN利用加密技术对经过隧道传输的数据进行加密,以保证数据仅被指定的发送者和接收者了解,从而保证数据的私有性和安全性[2].

随着互联网的迅速发展,出现了大量利VPN技术进行“翻墙”的软件,例如:自由门、极速安全VPN、蝙蝠VPN等.但其中部分软件通过私自架设服务器,与国外非法服务器进行互连互通,在国内传播不良信息.由于VPN所传输的数据均经过加密,且CPU属于通用处理器,以及GPU的优势在于处理浮点运算,因此使用传统CPU、GPU进行VPN数据破解的能力有限[3].这无疑给执法部门的调查和取证带来巨大障碍.鉴于此,本文在分析使用PPTP隧道协议进行通信的VPN的基础上,提出了一种基于FPGA的VPN口令恢复方案.该方案针对PPTP隧道协议,实现了VPN-DES的破解模式,并采用了全流水线架构的FPGA设计.相比于GPU的破解效率,其性能提升了8.5倍左右,相比于CPU的破解效率,其性能则提升了27万倍左右.

2 MS-CHAPv2协议与MPPE协议

2.1 MS-CHAPv2协议

MS-CHAP是Microsoft开发的挑战握手协议(Challenge-Handshake Authentication Protocol).MS-CHAP用作Microsoft为VPN实施PPTP协议的一个身份验证选项.目前存在两个版本的CHAP协议,MS-CHAPv1(在RFC 2433中定义)和MS-CHAPv2(在RFC 2759中定义).MS-CHAPv2质询握手身份验证协议是一个通过单向加密密码进行的相互身份验证协议.与 MS-CHAPv1相比,MS-CHAPv2通过捎带响应数据包上的对等体挑战串和成功数据包上的验证器响应,提供了通信双方的相互验证,进一步增强了通信的安全性.目前,PPTP协议使用MS-CHAPv2协议[4]进行身份验证.MS-CHAPv2协议具体流程如图1所示.

图1 MS-CHAPv2协议流程图Fig.1 MS-CHAPv2 protocol flow

1)客户端向服务器发送请求报文.

2)服务器回复一个随机生成的16-bytes认证挑战串(authenticator challenge).

3)客户端生成回复报文:

(a)客户端随机生成一个16-bytes对等挑战串(peer challenge);

(b)客户端使用服务器发送的16-bytes认证挑战串(authenticator challenge)、(a)中生成的16-bytes对等挑战串(peer challenge)以及登录时的用户名,进行hash运算,最终生成一个8-bytes的挑战串(challenge);

(c)客户端对登录时输入的口令进行hash运算,生成一个16-byte的口令hash值(NT password hash);

(d)将在(c)中生成的口令hash值(NT password hash)末尾补5-bytes的0后,再平均分为三份7-bytes二进制串作为DES 的密钥;

(e)取在(b)中生成的挑战串(challenge)前8-bytes 二进制串(本文之后将新提取出来的8-bytes称为challenge),并使用分别使用(d)中的三组DES 的秘钥进行加密运算;

(f)最后将在(e)中输出的三组DES加密结果、(a)中生成的16-bytes对等挑战串(peer challenge)以及用户名作为响应串(response date)回复给服务器.

4)服务器使用相同方式计算出挑战串(challenge)值后对响应串(response date)进行解密运算,并与存储在数据库里的口令hash值进行对比.如果解密结果与服务器存储的口令hash值相同,则完成服务器对客户端的认证.

5)服务器向客户端发送认证信息(server authenticate):

(a)服务器对口令hash值进行MD4加密,生成password-hash-hash;

(b)服务器使用根据客户端的回复的SHA值、(a)中生成的password-hash-hash以及明文“Magic server to client signing constant”生成hash值;

(c)服务器使用(b)生成的20-bytes hash值、从客户端接受的8-bytes challenge以及明文“Pad to make it do more than one iteration”生成另一个hash值;

(d)服务端使用“S=hupper-case ASCII representation of the byte value”格式回复(c)中生成的20-bytes hash值.

6)客户端经过同样的流程生成20-byte的hash值,与从服务器端接受的数据进行对比,如果相同,则完成客户端对服务器的认证.

2.2 MPPE协议

相比MS-CHAPv2协议,MPPE协议流程较为简单.MPPE(Microsoft Point-to-Point Encryption-微软点对点加密术)协议是由Microsoft设计的数据链路层通信保护机制[5].MPPE协议在PPTP协议中使用RC4算法对通信数据进行加密.RC4算法是一种对称加密算法,即加密和解密使用相同的key值,具体详情可查阅RFC7465.在PPTP协议中,MPPE协议对MS-CHAPv2协议生成的部分认证信息以及口令哈希值进行SHA运算,将其结果截断一定长度后作为RC4算法的key值.RC4 Key值生成流程如下:

1)对MS-CHAPv2协议生成的认证信息、口令哈希值,以及一个27-byte的字符串常量进行SHA运算,将其结果截断成一个16-byte的master-master key.

2)再将master-master key与特定字符常量进行SHA运算,将其结果通过截断转换成session keys即RC4算法中使用的key值(生成40-bit和128-bit RC4 key值时使用的字符常量略有不同).

2.3 MS-CHAPv2与MPPE协议分析

根据MS-CHAPv2协议流程可知,客户端使用用户口令的MD4哈希值,生成三组DES密钥(key1,key2,key3)后,结合authenticator challenge、用户名以及随机生成的16-bytes peer challenge生成challenge挑战串.再使用三组DES密钥(key1,key2,key3)分别对challenge进行加密.最后将三组DES加密结果以及peer challenge拼接成响应包(response date)发送给服务器端.由于服务器端是通过对比存储在数据库中的口令MD4哈希值进行身份认证的.因此当服务器端用相同方式计算出挑战串并对比后,即可完成口令验证过程.

根据MPPE协议可知,结合口令MD4哈希值、部分身份认证信息(response date)以及特定字符常量,经过SHA运算后可以生成RC4 key.之后便使用RC4算法完成对数据的加密过程.

根据口令验证以及数据加密过程可知,全部流程中实际只有一个未知量即用户口令的MD4哈希值.协议中的其他元素都是以明文形式存在,或可以很容易地从明文中派生出,例如:challenge、用户名等.因此,获取用户口令的MD4哈希值即可完成对口令验证以及数据加密过程的破解.

3 VPN口令恢复与优化

3.1 VPN口令恢复流程

根据上节对MS-CHAPv2协议和MPPE协议的分析,VPN口令恢复流程主要分为6个步骤:数据包解析,哈希提串,MD4加密,分组DES加密,获取RC4 key,解密通信数据,如图2所示.

图2 VPN口令破解流程Fig.2 VPN password cracking process

各步骤具体流程如下:

数据包解析:获取到身份认证报文中的authenticator challenge、peer challenge以及用户名字段.

口令穷举:使用明文字典或口令掩码进行暴力穷举.

哈希提串:根据数据包解析出的内容,通过hash运算计算出challenge挑战串

MD4加密:将输入的口令进行MD4运算[6],输出128 bits密文.

分组DES加密:将128 bits 密文扩展为21-bytes(低位补5字节0)后,平均分为三组,每组7-bytes,分别进行DES加密.

获取RC4 key:根据MPPE协议加密原理,通过SHA运算获取RC4 key.

解密通信数据:使用RC4 key值对通信的数据进行解密,得到解密信息.

其中数据包解析、口令穷举步骤较为简单,基本不涉及计算.哈希提串、获取RC4 key和解密通信数据步骤也只需执行一次,运算量较小,且生成的challenge串在运算迭代中是不变的,因此可以使用CPU实现.但MD4加密与分组DES加密两步骤,运算量相对较大,且在算法运行时,要循环执行直至输出正确的破解结果为止.由于MD4加密与分组DES加密两步骤属于逻辑运算,且FPGA作为高速逻辑运算部件,在逻辑运算上比通用处理器具有更大的优势,因此,可以采用高速逻辑运算部件FPGA对上述两个步骤进行加速[7].

3.2 VPN-DES模式

目前使用字典进行口令恢复时,普遍存在破解率不稳定,字典过大时的存储问题以及字典传输存在瓶颈等问题.因此,通过对PPTP协议的进一步分析,本文采用一种基于DES算法的口令恢复流程—VPN DES模式,其依靠对DES密钥的穷举达到等同于获得明文口令的效果.

通过1.3节对两种协议的分析可知,用户口令的MD4哈希值与用户明文口令是等价的,即意味着用户口令的MD4哈希值足以作为接入VPN连接时的身份验证依据以及解密通信数据的密钥.又由于三组DES密钥是通过用户口令的MD4哈希值在末尾补零生成的,则三组DES密钥与MD4哈希值也是等价的,具体关系如图3所示.

图3 口令等价关系图Fig.3 Password equivalent relationship

另外,由于MD4是非对称加密算法且需要穷举的口令空间2128过大,不适合暴力破解.于是可以通过对DES密钥的破解从而间接获得MD4哈希值.从图3可知,第三个DES密钥实际只有两个字节长(其余5字节是通过补零得到的),通过CPU就可以快速破解.因此,主要计算量集中在剩余两个DES密钥的破解上,需要穷举的口令空间一共为257.又由于所有DES密钥长度均为56 bit,则可以通过将对两个DES密钥的破解压缩为一次全DES密钥空间的穷举,即可将口令空间进一步缩小到256,即破解单一DES密钥需要穷举的口令空间.具体破解流程如图4所示.

图4 VPN-DES破解流程Fig.4 VPN-DES crack process

VPN-DES破解流程与1.2节破解流程基本相似,不同点在于:

1)将输入的明文口令改为输入7字节的二进制key值.

2)省去了MD4加密步骤.输入数据经过DES加密后,只需和数据包中解析出的三组DES加密结果进行对比即可.

由此可知,VPN口令恢复的关键点在于获取DES密钥.因此,高效的DES算法是本文设计的关键所在[8].

4 基于FPGA的实现方案

4.1 DES算法设计

DES全称为Data Encryption Standard,即数据加密标准,是一种使用对称密钥的块加密算法[9].它使用64位密钥key(实际key只有56位有效值,第8,16,32,40,48,56,64位是校验位)对64位明文块进行加密.DES算法每轮迭代都需要一个64位的k值参与运算,经过16轮迭代后输出密文,详情可查阅RFC4772.DES算法概要如图5所示.

本文VPN口令恢复算法的计算量主要源于DES加密的多次迭代.因此,并行的DES加密可以有效提高口令恢复速度[10,11].DES算法的处理流程可以分为若干步且数据的处理是单向的,所以DES算法适合用流水线模式实现.伪Verilog代码如下所示:

图5 DES算法概要图Fig.5 Outline of the DES algorithm

Input:desIn,key;

Output:desOut;

IP[1:64]<= desIn; // Register the 64 bit input

key_sel uk(key); // key_sel uk()provides K1～K15

crp u0()～crp u15(); // 16 rounds of iteration

L1 <=IP[33:64]; R1 <=IP[01:32] ^ out0;

L2 <= R0;R2 <= L0 ^ out1;

…

L15 <= R14;R15 <= L14 ^ out15;

assign FP = {(out15 ^ L14),R14};

desOut <= FP;

使用FPGA全流水线实现DES算法时,F函数需要被实例化16次,并使用多个寄存器Reg存储每个F函数的输出结果,以便数据有序的参与流水线运算[12].其中参与F函数运算的k1～k16的生成方式可以简化成一个具有64位相同输入,48位不同输出的运算模块,因此可以预先生成,并通过使用多组寄存器Reg控制k1～k16传送给F函数的时序.具体设计如图6所示.

图6 FPGA实现DES全流水线设计图Fig.6 FPGA DES implementation of the entire pipeline design

当算法开始运行时,第一轮时钟周期接受输入的64-bytes key和64-bytes待加密明文块.64-bytes key经过密钥生成模块后,生成k1～k16.先将k1传送给F函数1,其余K值传送给寄存器Reg组,等待下一轮时钟周期.第二轮时钟周期时,接受新输入的64位key和64位代加密明文块重复第一轮的操作,与此同时F函数2从寄存器Reg中读取上一轮F函数1输出的结果以及上一轮存储在寄存器Reg组中的K2进行运算.以此类推直至16轮迭代完成后,输出与第一轮时钟周期时接受的key相对应的密文.虽然每组数据需要经过16个时钟周期才能计算出结果,但当算法满负荷运行时,每个时钟周期都会输出一块密文,相比串行DES加密而言无疑大大提高了处理速度[13].

4.2 VPN-DES模式实现

使用FPGA 实现的VPN-DES模式整体架构主要包含5个模块单元:任务管理单元,任务解析单元,密钥穷举单元,烧录程序单元,破解引擎单元,状态信息管理单元,结果管理单元.如图7所示.

任务管理单元:主要负责接收包含任务信息的数据包,并将提取的信息发送给任务解析单元.

任务解析单元:解析收到的任务信息,提取FPGA烧录程序类型以及密钥穷举范围.

图7 FPGA架构设计图Fig.7 FPGA architecture design

密钥穷举单元:根据任务信息中的穷举范围自动生成密钥,并将生成的密钥发送给破解引擎单元.

烧录程序单元:根据任务信息中的烧录程序类型选择相应程序对FPGA芯片进行烧录.

破解引擎单元:主要负责根据任务信息对算子进行配置,之后再结合穷举生成的密钥代入DES流水线中进行运算.

状态信息管理单元:主要负责收集FPGA运算时各个算子的运行状态.

结果管理单元:将DES流水线中计算出的加密结果与任务信息中解析的结果进行对比,并对所有算子的加密结果进行汇总.

4.3 系统整体结构

图8描述了系统整体设计框架,包含用户界面、管理节点和FPGA集群.

图8 系统整体架构图Fig.8 System overall structure

每当有新的FPGA节点加入集群时,新加入的FPGA节点会主动向管理节点发送自己的IP地址.管理节点根据用户界面输入的任务信息对管理的FPGA节点分发任务配置信息和口令切片,并实时收集运行状态以及查询结果.以本文提出的DES破解模式为例,管理节点将用户界面上传的任务信息(即穷举策略或范围以及从报文中提取的responsedate、peer challenge、用户名等信息)分发到各个FPGA节点后,各FPGA节点根据收到的任务信息开始进行暴力破解.在任务执行期间,管理节点实时收集各节点的运行状态以及破解结果,每当有FPGA节点破解成功时,管理节点会在用户界面显示相应任务的破解结果.当任务破解完成或用户主动终止时,系统停止运行.

5 实验结果与分析

实验对比了在系统集群分别包含多组FPGA节点(每个节点包含4块FPGA芯片,每个芯片又包含64条算子)的情况下,口令恢复的性能、功耗以及效能.其次对比了CPU、GPU以及单组FPGA在相同测试环境下破解口令集时的性能、功耗、性价比.之后又对比了使用FPGA实现的不同VPN破解模式下的性能、功耗以及效能.最后展示了本文以及其它文献对DES算法的实现情况.

测试环境采用CentOS 7.0系统,配置8G DDR3内存,具体测试环境如表1所示.

通过程序自动生成1000组经过加密的DES密钥,在不同规模的FPGA节点下进行仿真实验,分别对性能(百万口令每秒),功耗(瓦)进行测试,并通过式(1)计算能效(百万口令每焦),即每百万条口令消耗一焦电量.结果如表2所示.

(1)

从表2实验结果可知,随着FPGA规模的增加,其性能、功耗近似呈线性增长,能效基本保持不变.因此,合理扩大FPGA规模能有效提高破解性能且不会带来过多的能源消耗.

表1 测试环境
Table 1 Test environment

名称型号测试程序环境价格FPGAXCKU060FPGA系统集群CentOS6700GPUGTX 1080HashCat v3.6CentOS 4500CPUi5-7500VPN-DES模式CentOS 1399

表2 多组FPGA口令恢复测试
Table 2 Multiple FPGA password recovery test

规模性能功耗能效FPGA ∗297260 M/s102 W954 M/JFPGA ∗4194520 M/s201 W967 M/JFPGA ∗6291740 M/s310 W941 M/JFPGA ∗8389120 M/s410 W950 M/J

其次,实验使用单组FPGA、GPU、CPU对相同的口令集进行恢复,分别对其性能和功耗进行测试,并通过式(1)计算能效,式(2)计算性价比.结果如表3所示.

(2)

表3 FPGA、GPU、CPU口令恢复对比
Table 3 FPGA、GPU、CPU password recovery comparison

名称性能功耗能效性价比FPGA48640 M/s49 W993 M/J7.26GPU17769 M/s230 W77 M/J3.8CPU0.12 M/s65 W0.02 M/J8.58∗10-5

从表3测试结果可知,相对于GPU、CPU,FPGA口令破解的性能更高,且能效是GPU的12.8倍左右,是CPU的5万倍左右;性价比是GPU的1.9倍左右,是CPU的8.5万倍左右.

实验接着对比了使用FPGA实现的不同VPN破解模式下的性能、功耗、能效.结果如表4所示.

表4 VPN-DES、VPN-普通模式下口令恢复对比
Table 4 Password recovery comparison in VPN-DES and VPN-ordinary mode

名称性能功耗能效VPN-DES48640 M/s49 W993 M/JVPN-普通4470 M/s47W95 M/J

从表4实验结果可知,VPN-DES模式性能更高,是其VPN-普通模式的10.8倍左右;能效是VPN-普通模式的10.5倍左右.其原因是VPN-DES模式与VPN-普通模式相比其优越性在于将近乎无限的口令空间缩小到256大小,且少执行了一个md4运算,这在文中第3.2节已有过解释.因此,基于FPGA的VPN口令恢复在VPN-DES破解模式下具有明显优势.

最后,实验对比了不同文献对关键算法DES的实现情况,如表5所示.

表5 本文DES实现与其他文献实现
Table 5 DES implementation and other literature implementation

参考文献设备频率吞吐量Trimberger S[12]XCV300E-8102 MHz8.4Gbps汪翼[13]Xilinx 100 MHz6.4GbpsPatterson[14]XCV150168 MHz10.8GbpsKHAN F[15]Spartan3e310 MHz1.24 Gbps本文XCKU060190 MHz12.1Gbps

以本文所使用的XCKU060型号FPGA为例,同时使用16组FPAG在VPN-DES模式下进行破解,大约一天时间就能遍历全部口令空间.

6 结束语

本文实现了基于FPGA的VPN口令恢复,并提出使用VPN-DES模式以及全流水线设计加快了口令的破解速度.经过实验表明,FPGA集群系统在相同测试环境下较GPU和CPU而言其性能有了大幅提高,且系统可以在有限时间内遍历全口令空间.因此,拥有100%的破解率.下一步工作主要是扩展对使用其他协议进行VPN通信的口令恢复,例如IPSec协议.