(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210718908.0 (22)申请日 2022.06.23 (71)申请人 复旦大学 地址 200433 上海市杨 浦区邯郸路2 20号 (72)发明人 韩伟力　张浩东　张俊杰　 (74)专利代理 机构 上海正旦专利代理有限公司 31200 专利代理师 陆飞　陆尤 (51)Int.Cl. G06F 9/50(2006.01) G06F 16/901(2019.01) G06F 16/903(2019.01) G06T 1/20(2006.01) (54)发明名称 基于hashcat与GPU并行计算的PCFG口令猜 测方法 (57)摘要 本发明属于口令安全技术领域， 具体为一种 基于hashcat与GPU并行计算的PCFG口令猜测方 法。 本发明首先对PC FG口令猜测模型生成的训练 数据进行预处理， 构建相应数据结构后传输至 GPU端， 在GP U端利用处理的数据和设计的索引算 法并行生 成口令猜测并在口令密文中进行匹配， 最后将命中信息传回CPU端并重构命中口令以实 现口令恢复。 本发明猜测方法兼容hashcat的运 行流程， 可作为一种攻击模式直接实现在 hashcat中。 本发明在利用PCFG高效的猜测效率 的同时， 利用GPU并行计算减少了口令生成的时 间成本； 将PCFG口令生成过程与hashcat运行过 程相结合， 减少了概率猜测模型与实用破解工具 结合使用的传输时延。 权利要求书3页 说明书4页 附图1页 CN 115220913 A 2022.10.21 CN 115220913 A 1. 一种基于hashcat与GPU并行计算的PCFG口令猜测方法， 其特征在于， 通过在CPU端 预处理PCFG模型训练得到的模 型数据和在GPU端 各线程中使用设计的索引算法定位该线程 需要生成的口令， 使 得PCFG能利用GPU在口令级别上实现并行口令生 成； 并通过与实用口令 破解工具hash cat结合， 提升在现实场景 下破解密文口令的速度； 具体步骤如下： 步骤一、 CPU 端处理PCFG模型 数据 模型数据的处理分为两个部分： 构 建片段字典和重构预终端； 通过在CPU端对PCFG口令 猜测模型 的模型数据进行预处理， 得到片段字典和重构后的预终端结构； 片段字典在破解 开始之前传入GPU端待用； 进行口令破解时， 每次基于GPU内存限制生成并传输一定数量预 终端结构进入GPU 端， 进行后续口令猜测过程； 步骤二、 GPU 端并行生成并匹配猜测口令 根据每次传入GPU的预终端结构中的信息， 利用索引算法在每个GPU线程中确定待生成 的口令及其相应片段元素在片段字典中的位置， 从而生成猜测口令； 对生成的猜测口令按 相应哈希算法处理后在密文口令文件中进行匹配， 对于匹配成功的猜测口令， 记录其索引 信息并传回CPU 端； 步骤三、 CPU 端重构并输出命中口令 对于匹配成功的口令， 其相应索引信息被传回CPU端， 在CPU端利用索引算法重构命中 口令的明文， 以此完成口令恢复， 最后将破解信息 输出到指定位置 。 2.根据权利要求1所述的PCFG口令猜测方法， 其特征在于， 在步骤一中， 所述构建片段 字典， 是指将PCFG训练得到的所有片段字符串 按顺序存 储成一个字典； 具体过程 为： （1） 对于所有片段元素即字符串， 依次按类型、 长度和概率的顺序进行排序， 即先按类 型进行排序， 对于同种类型的片段元素， 按长度进 行排序， 对 所有同类型且长度相同的片段 元素， 按概率进行排序； （2） 将每种类型片段不同长度的元素看成一组， 为了获取每组元素的位置， 另设一个长 度为K*N的一 维数组存储 所有元素组在片段字典 中的起始 位置， 其中K为片段类型数， N为片 段元素的最大长度； 通过该一 维数组， 根据 某元素在该组中的编号， 即可获取到该元素在整 个片段字典的相对偏移， 从而计算出 该元素的地址 。 3.根据权利要求1所述PCFG口令猜测方法， 其特征在于， 在步骤一中， 所述重构预终端 的具体过程分为三个部分： 片段元素概率重分配、 修改预终端的基本结构和预终端结构长 度微调； （1） 片段元素概率重分配， 是在生成预终端之前， 重新分配同类型、 同长度片段元素的 概率， 以此调整预终端中每个片段的元素数量， 进而调整一个预终端将生成的口令数目， 使 后续在GPU进行并行口令生成时同一个warp中的线程处理同一个预终端， 从而减少线程间 的等待时延； 具体来说， 对于片段字典中同类型、 同长度的元素， 按8个一组重新分配概率， 以此生成的预终端每个片段中包含8个元素； 对于包含2个及以上片段的预终端， 生成的口 令数是32的整数倍， 无需其他操作； 对于仅包含一个片段的预终端， 重复4次该预终端使得 生成的口令数达 到32； （2） 修改预终端的基本结构； 在原始的预终端结构中， 每个预终端存储每个片段对应的 类型、 长度、 概率和其中包含的具体元素即字 符串数组； 所述修改预终端的基本结构， 首先， 在每一个预终端结构中增加四个值， 分别是偏移量、 片段数量、 前猜测数和当前猜测数； 其权　利　要　求　书 1/3 页 2 CN 115220913 A 2次， 对于构成预终端的每个片段， 保留类型和片段长度两项基础信息， 去除原结构 体中存储 的概率信息和具体元素字 符串， 新增两个值， 即元素起始编号和元素数量； 以此减少原有 结 构的冗余存 储， 并为之后的索引计算做好 准备； （3） 对预终端结构长度微调， 是对单个预终端结构大小进行微调； 考虑到GPU 的内存访 问始终以缓存 行为单位执行， 且缓存 行大小为 128字节， 在减少预终端 结构长度的基础上使 一个预终端的总长度为GPU缓存行大小的整 数倍， 以此减少获取预终端时的存储访问次数； 具体地， 在一个预终端结构中， 分别使用8字节、 1字节、 8字节、 7字节来存储偏移量、 片段数 量、 前猜测数和当前猜测数； 对 预终端中包含的每个段， 分别使用1字节、 1字节、 1字节和5字 节来存储类型、 长度、 元 素起始编号和元 素数量， 并限制一个预终端最多含有2 9个片段。 4.根据权利要求1所述的PCFG口令猜测方法， 其特征在于， 在步骤二中， 所述利用索引 算法生成猜测口令的具体流 程为： （1） 使用pt_id ‑guess_id来表示第pt_id个预终端所生成的第guess_id个猜测口令； 于 是， 在GPU中， 对于每一个编号为thread_id的线程， 使用下式， 通过遍历pt _id的方式计算该 线程在处 理编号为pt_id的预终端需要生成的 口令的gues s_id： 其中， thread_size表示使用的线程总 数， offset与current_guess分别为每个预终端 结构中存储的偏移量和当前猜测数； 具体过程为， 从1开始遍历每一个pt_id， 对于每一个 pt_id， 获取到其中存储的o ffset和current_guess， 进而从0开始遍历 𝛼来计算当前pt_id 中需要生成的口令的guess_id， 直到得到的guess_id>current_guess， 则开始 处理下一个 pt_id； （2） 一个预终端通过顺序选择各个片段中的元素来生成口令； 从左向右， 先遍历所有第 i个片段的元素， 对每个片段i的元素， 遍历所有第i +1个片段的元素； 因此， 在已知口令对应 的pt_id和guess_id之后， 利用一维数 组转为多维数组的方式， 基于guess_id来逆推出组成 该猜测口令的各个片段的元素编号seg_id； 由于在预终端结构中， 每个片段都存储了起始 元素在片段字典中所在组的偏移， 由该值加上seg_id则可以计算出该元素在片段字典中所 在组的偏移； 接着利用存储在K*N的一 维数组中的片段字典每组元素的起始 地址， 加上偏移 值计算出该元素的地址， 从而在片段字典 中得到具体的字符串； 拼接每段的元素字符串， 最 终得到猜测口令 。 5.根据权利要求3所述的PCFG口令猜测方法， 其特 征在于， 步骤一中： 所述偏移量， 记录上一个预终端要生成的最后一条猜测口令所对应的线程编号， 可以 用来计算当前 预终端要生成的第一条猜测口令所对应的线程编号； 所述片段数量， 记录组成当前预终端的口令片段的数量， 可以用来判断组成该预终端 的具体片段 数据的存 储边界； 所述前猜测数， 记录在当前预终端之前的所有预终端所生成的猜测口令总数， 可用来 计算当前 预终端生成的某条猜测口令在猜测方法生成的所有猜测口令中的位置； 所述当前猜测数， 记录当前预终端所能生成的猜测口令总数， 可以用来判断当前预终 端是否已分配完所有猜测口令的生成任务； 所述元素起始编 号， 记录当前片段中的第 一个元素在片段字典的同类型同长度 元素中权　利　要　求　书 2/3 页 3 CN 115220913 A 3