2023年7月31日发(作者：)
第３３卷第８期 ２０１２年８月 通信学报 Ｖｂｌ＿３３ ＮＯ．８ Ｊｏｕｍａｌ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ａｕｇｕｓｔ ２０１２ ＰＲＥＳＥＮＴ密码代数故障攻击 吴克辉 ，赵新杰 ，王韬 ，郭世泽 ，刘会英 （１．军械工程学院计算机工程系，河北石家庄０５０００３；２．北方电子设备研究所，北京１０００８３） 摘要：提出了一种新的ＰＲＥＳＥＮＴ密码故障分析方法——代数故障攻击。将代数攻击和故障攻击相结合，首先 利用代数攻击方法建立密码算法等效布尔代数方程组；然后通过故障攻击手段获取错误密文信息，并将故障差分 和密文差分转化为额外的布尔代数方程组；最后使用ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器求解方程组恢复密钥。结果表明：在 ＰＲＥＳＥＮＴ－８０的第２９轮注入宽度为４的故障，故障位置和值未知时，２次故障注入可在５０ｓ内恢复６４ｂｉｔ后期白 化密钥，将ＰＲＥＳＥＮＴ－８０密钥搜索空间降低为２ ，经ｌｍｉｎ暴力破解恢复完整主密钥；和现有ＰＲＥＳＥＮＴ故障攻 击相比，该攻击所需样本量是最小的；此外该代数故障分析方法也可为其他分组密码故障分析提供一定思路。 关键词：故障攻击；代数攻击；代数故障攻击；ＰＲＥＳＥＮＴ密码 中图分类号：ＴＰ３９３．０８ 文献标识码：Ａ 文章编号：１０００—４３６Ｘ（２０１２）０８—００８５—０８ Ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ ｏｎ ＰＲＥＳＥＮＴ ｗｕ Ｋｅ—ｈｕｉ ，ＺＨＡＯ Ｘｉｎ－ｊｉｅ ，ｗＡＮＧ Ｔａ０ ，ＧＵＯ Ｓｈｉ—ｚｅ ，ＬＩＵ Ｈｕｉ．ｙｉｎｇ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆＣｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｏｒｄｎａｎｃｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｌｌｅｇｅ，Ｓｈｉｊｉａｚｈｕａｎｇ ０５０００３，Ｃｈｉｎａ； ２．Ｔｈｅ Ｉｎｓｔｉｔｕｔｅ ｏｆＮｏｒｔｈ Ｅｌｅｃｔｒｏｎｉｃ Ｅｑｕｉｐｍｅｎｔ，Ｂｅｉｊｉｎｇ １０００８３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｎｅｗ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｍｅｔｈｏｄ ｏｎ ＰＲＥＳＥＮＴ－－ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ ｗａｓ ｐｒｏｐｏｓｅｄ．Ｔｈｉｓ ａｕａｃｋ ｃｏｍｂｉｎｅｄ ｃｏｎ— ｖｅｎｆｉｏｎａｌ ａｌｇｅｂｒａｉｃ ｃｒｙｐｔａｎａｌｙｓｉｓ ｗｉｔｈ ｆａｕｌｔ ａｔｔａｃｋ，ｆｉｒｓｔｌｙ ｂｕｉｌｔ ｅｑｕｉｖａｌｅｎｔ Ｂｏｏｌｅａｎ ａｌｇｅｂｒａｉｃ ｅｑｕａｔｉｏｎｓ ｏｆ ｃｉｐｈｅｒ ｅｎｃｒｙｐ— ｔｉｏｎ ｂｙ ａｌｇｅｂｒａｉｃ ｃｒｙｐｔａｎａｌｙｓｉｓ ｍｅｔｈｏｄ；ｓｅｃｏｎｄｌｙ ｇｏｔ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｆａｕｌｔ ｃｒｙｐｔｏｇｒａｐｈ ｂｙ ｆａｕｌｔ ａｔｔａｃｋ ｔｅｃｈｎｉｑｕｅ，ａｎｄ ｔｒａｎｓｆｏｒｍｅｄ ｄｉｆｆｅｒｅｎｔｉａｌ ｏｆ ｆａｕｌｔ ａｎｄ ｃｒｙｐｔｏｇｒａｐｈ ｉｎｔｏ ａｄｄｉｉｏｎａｌｔ ａｌｇｅｂｒａｉｃ ｅｑｕａｔｉｏｎｓ；ｆｉｎａｌｌｙ ｕｔｉｌｉｚｅｄ Ｃｒｙｐｔｏ Ｍｉｎｉ ＳＡＴ ｓｏｌｖｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｅｑｕａｔｉｏｎｓ ａｎｄ ｒｅｃｏｖｅｒ ｋｅｙ．Ｅｘｐｅｒｉｍｅｎｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ａｆｔｅｒ ｉｎｊｅｃｔｉｎｇ ４－ｂｉｔ ｆａｕｌｔ ｔｏ ｔｈｅ ２９ ｒｏｕｎｄ ｏｆ ＰＲＥＳＥＮＴ－８０，ｔｈｅ ｆａｕｌｔ ｌｏｃａｔｉｏｎ ａｎｄ ｆａｕｌｔ ｖａｌｕｅ ａｒｅ ｕｎｋｎｏｗｎ，ｏｎｌｙ ２ ｉｎｊｅｃｔｉｎｇｓ ｃａｎ ｒｅｃｏｖｅｒ ６４一ｂｉｔ ｌａｓｔ ｗｈｉｔｅｎｉｎｇ ｋｅｙ ｉｎ ５０ ｓｅｃｏｎｄｓ ｔｈａｔ ｒｅｄｕｃｅ ｍａｓｔｅｒ ｋｅｙ ｏｆ ＰＲＥＳＥＮＴ－８０ ｓｅａｒｃｈｉｎｇ ｓｐａｃｅ ｔｏ ２ ．ｔｈｅｎ ｒｅｃｏｖｅｒ ｔｈｅ ｍａｓｔｅｒ ｋｅｙ ａｆｔｅｒ ｌ ｍｉｎ— ｕｔｅ ｂｒｕｔｅ－－ｆｏｒｃｅ・－ｓｅａｒｃｈ ｏｎ ａｖｅｒａｇｅ；ｃｏｍｐａｒｅｄ ｗｉｔｈ ｐｒｅｖｉｏｕｓ ｆａｕｌｔ ａｔｔａｃｋ ｏｎ ＰＲＥＳＥＮＴ，ｔｈｅ ａｍｏｕｎｔ ｏｆ ｔｈｉｓ ａｔｔａｃｋ ｓａｍｐｌｅ ｉｓ ｔｈｅ ｓｍａｌｌｅｓｔ；ｍｅａｎｗｈｉｌｅ，ｔｈｅ ａｎａｌｙｓｉｓ ｍｅｔｈｏｄ ｐｒｏｐｏｓｅｄ ｃａｎ ｂｅ ａｐｐｌｉｅｄ ｉｎｔｏ ｔｈｅ ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ ｏｆ ｏｔｈｅｒ ｂｌｏｃｋ ｃｉｐｈｅｒｓ． Ｋｅｙ ｗｏｒｄｓ：ｆａｕｌｔ ａｔｔａｃｋ；ａｌｇｅｂｒａｉｃ ａｔｔａｃｋ；ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ；ＰＲＥＳＥＮＴ １ 引言 密码算法安全性分析可分为面向设计的数学 分析和面向实现的旁路分析２种。前者将密码实现 收稿日期：２０１１—０７—３０；修回日期：２０１１—１０—２４ 视为黑盒，通过观测密码输入和输出，利用差分分 析、线性分析、代数分析等数学方法分析其安全性， 但受复杂度限制，现有方法仅能对算法安全性进行 理论分析，很少能对其构成实际威胁；后者将密码 基金项目：国家自然科学基金资助项目（６０７７２０８２，６１１７３１９１）；河北省自然科学基金资助项目（０８Ｍ０１０） Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍｓ：Ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ（６０７７２０８２，６１１７３１９１）；Ｔｈｅ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｈｅｂｅｉ Ｐｒｏｖｉｎｃｅ（０８Ｍ０１０） 通信学报 第３３卷 实现视为灰盒，通过观测密码实现过程中泄露的时 间、功耗、电磁、声音、故障等信息，结合密码输 入和输出，利用简单分析、差分分析、相关分析、 碰撞分析、互信息分析等方法，基于密钥分而治之 的思想，在极小的代价下快速恢复密钥，目前已对 多种密码算法的各种实现构成严峻威胁。在旁路分 析中，根据密码运行泄露信息不同，可将其分为计 时分析、功耗分析、电磁分析、故障分析等。 密码故障分析作为一种有效的旁路攻击方法， 最早由Ｂｏｎｅｈ等人【ｌ１２．＿在１９９６年提出，并成功攻破 ＲＳＡ签名算法。随后Ｂｉｈａｍ和Ｓｈａｍｉｒ于１９９７年 提出了差分故障分析（ＤＦＡ，ｄｉｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙ． ｓｉｓ）方法，对ＤＥＳ密码进行了攻击。此后密码学 家在此基础上实现了针对分组密码的差分故障攻 击 Ｊ。然而差分故障分析也具有一定的缺点：需 要结合具体算法结构和操作进行密钥推导，分析方 法繁琐；另外，即使在相同故障模型下，针对同一 密码算法分析中，研究者常会得到不同的实验结 果，这些都大大限制了差分故障攻击的通用性和实 用性。因此，研究通用、自动化的分析方法一直是 密码故障分析尚待解决的一个公开问题。 ２００２年，Ｃｏｕｒｔｏｉｓ等 在亚密会上首次提出代 数攻击的思想，将密码算法用代数方程组来等价表 示，通过求解方程组方法进行密钥恢复。由于该方 法可利用解析器进行密钥的自动化求解，可充分利 用计算机资源，因此，代数攻击为密码分析提供了 一种新的通用分析手段。然而，随着分组密码轮数 的增加，未知变量和代数方程组规模也会递增，在 有限复杂度内进行密钥求解是一个Ｎ—Ｐ完全问题， 这些都极大限制了代数分析的实用性。２００９年， Ｒｅｎａｕｌｄ［７，８１等将代数攻击和旁路分析相结合，提出 代数旁路攻击（ＡＳＣＡ，ａｌｇｅｂｒａｉｃ ｓｉｄｅ．ｃｈａｎｎｅｌ ａｔｔａｃｋ） 思想，在代数攻击基础上，通过旁路攻击手段采集 密码执行泄露的中间状态信息，并将其转化为额外 的代数方程组，结合密码算法方程组，加快代数方 程组求解速度。结果表明：针对ＰＲＥＳＥＮＴ和ＡＥＳ 密码算法，基于汉明重泄露模型，使用ｚＣｈａｆｆ解析 器，一条功耗曲线分析即可恢复完整密钥。代数旁 路分析为密码旁路分析提供了一种新的通用手段， 现有攻击大都基于功耗泄露模型，如何引入新的泄 露模型是代数旁路分析的一个热点问题。 本文尝试将代数攻击和故障攻击相结合，衍化 出一种新的代数旁路攻击手段——代数故障攻击， 并应用其对ＰＲＥＳＥＮＴ轻型分组密码进行故障分析。 现有ＰＲＥＳＥＮＴ故障攻击大都基于差分故障分析思 想开展，文献［９］首次对ＰＲＥＳＥＮＴ－８０加密过程进行 了差分故障分析，４０—５０对正确．故障样本可恢复后 期白化密钥，将主密钥搜索空间降低到２ ，文献［１０１ 提出了一种基于故障传播路径的差分故障分析方 法，８次故障注入即可将ＰＲＥＳＥＮＴ－８０密钥空间降低 到２Ｈ ；文献［１１】对ＰＲＥＳＥＮＴ密钥扩展进行了故障 分析，６４次故障注入可恢复第５１ｂｉｔ后期白化密钥， 将主密钥空间降低到２２９。在轻型分组密码代数故障 攻击方面，笔者尚未发现国内外有公开发表的文献。 本文首次提出针对ＰＲＥＳＥＮＴ的代数故障分析方 法，在ＰＲＥＳＥＮＴ加密第２９轮注入宽度为４的故障 模型下，２次故障注入可在５０ｓ内恢复６４ｂｉｔ后期白化 密钥，将ＰＲＥＳＥＮＴ－８０密钥搜索空问降低为２ ，并 给出了有效故障样本的判断方法；和现有ＰＲＥＳＥＮＴ 故障攻击相比，文中攻击所需样本量是最小的。 本文结构如下：第２节阐述ＰＲＥＳＥＮＴ分组密码 算法，第３节给出了代数故障攻击原理，第４节介绍 ＰＲＥＳＥＮＴ故障攻击模型，第５节给出了ＰＲＥＳＥＮＴ 代数故障攻击具体过程，第６节为结束语。 ２ ＰＲＥＳＥＮＴ密码算法 ＰＲＥＳＥＮＴ是由Ｂｏｇｄａｎｏｖ［１２［等人于２００７年提 出的轻量级分组密码，具有良好的硬件实现效率， 在０．１８ｇｍ工艺下仅需１５７０ＧＥ逻辑单元，可在ＲＦＩＤ 卡以及传感器网络等资源受限环境中广泛使用。算 法采用ＳＰＮ结构，分组长度为６４ｂｉｔ，支持８０ｂｉｔ、 １２８ｂｉｔ ２种密钥长度，共迭代３１轮。 加密过程如下。 轮函数Ｆ由轮密钥加、Ｓ盒代换、Ｐ置换３部 分组成。 １）轮密钥加Ａ ：６４ｂｉｔ轮输入同轮密钥进行异或。 ２）Ｓ盒代换层乩：将轮密钥加６４ｂｉｔ输出查找 １６个４进４出的Ｓ盒。 ３）Ｐ置换层ＤＬ：通过置换表Ｐ（ ）对Ｓ盒代换 ６４ｂｉｔ输出按比特进行重新排列。 为提高算法安全性，ＰＲＥＳＥＮＴ在第３１轮后使 用６４ｂｉｔ密钥 进行后期白化操作，具体加密流程 如图１所示。 密钥扩展算法如下。 首先将初始主密钥存储在寄存器 中，表示为 岛９岛８…ｋ０。第ｉ轮密钥 由寄存器 的前６４ｂｉｔ组 第８期 吴克辉等：ＰＲＥＳＥＮＴ密码代数故障攻击 ・８７・ 成。当生成第ｉ轮密钥 后，密钥寄存器 通过以 下方法进行更新： ［ｋ７９／ｃ７８…ｋｌｋｏ］＝［ｋｌｓｋｌ７…ｋ２ｏｋ１９］ ［ｋ７９ｋ７８ｋ７７ｋ７６］＝Ｓ［ｋ７９ｋ７８ｋ７７幻６】 ［忌１９足ｌ８足１７足１６足１５】＝［足ｌ９忌ｌ８足１７足１６ １５］０ ｒｏｕｎｄ＿ｃｏｕｎｔｅｒ 段：密码算法方程组构建、故障注入及利用和代数 方程组求解。其中，Ｐ、 、Ｃ分别表示明文、中问 状态以及密文， 、砍分别表示主密钥和轮密钥。．厂 和ｇ分别表示加密操作和密钥扩展。 和ｃ 分别 表示注入故障中间状态及错误密文输出，而△墨和 ＡＣ则分别表示注入故障差分和密文差分值。 １）密码算法方程组构建 其中，ｒｏｕｎｄ＿ｃｏｕｎｔｅｒ为当前的加密轮数。易见，只 需分析出６４ｂｉｔ后期白化密钥，即可将８０ｂｉｔ ＰＲＥ． ＳＥＮＴ的主密钥搜索空问降低到２ 。 将密码算法加密和密钥扩展分别表示为关于 Ｐ、 、Ｃ、Ｋ、ｒｋ的代数方程组 ）和ｇ（）。给定一 个密码算法的代数方程组，密钥恢复等价于代数方 程组求解。代数方程组构造过程中，最为关键的是 如何构造非线性部件Ｓ盒对应代数方程组。常用的 Ｓ盒代数方程组构造方法包括待定系数法、比较系 数法ｌｌ引。本文主要参考文献［１４１中基于高斯消元法 构造Ｓ盒代数方程组的方法，对ＰＲＥＳＥＮＴ密码的 ｓ盒构建等效方程组。 不同于其他类型的代数旁路攻击，代数故障攻 击只需构建密码算法注入故障所在轮直至加密结 束之间的代数方程组，因此攻击利用的代数方程组 数量较少，便于求解。 图１ ＰＲＥＳＥＮＴ加密流程 ２）故障注入及利用 在构建密码算法等效代数方程组之后，需要进 行故障注入和利用。故障注入的方法有很多，如光 学辐射诱导、电压故障诱导、临界温度诱导、电磁 ３代数故障攻击 如图２所示，代数故障攻击一般可分为３个阶 图２密码代数故障攻击模型 通信学报 第３３卷 辐射诱导等。由于故障诱导不是本文研究重点，更 多相关内容可参考文献［１５】。故障利用的主要思想 是将故障注入差分ＡＸ和密文输出差分ＡＣ使用代数 故障输出差分。 ４．２故障模型 假设在ＰＲＥＳＥＮＴ第３１轮ｓ盒输入注入４ｂｉｔ 故障，则： Ｓ［ａ】（壬》Ｓ［ａ①ｆ】＝ｆ （１） 其中，厂和厂’为Ｓ盒输入和输出差分，ａ为第３１轮 ．．方程组表示，同密码算法代数方程组联立，降低代 数方程组的求解复杂度，加快方程组求解速度。 ３）代数方程组求解 代数方程组的求解问题一直是代数攻击领域 研究的难点，在全轮分组密码中，密钥求解是一 个 查表索引，将ａ，ｆ ０），ｆ’所有候选值代入式 （１），可得满足式（１）的ａ值统计，如表１所示。 表１ ＰＲＥＳＥＮＴ Ｓ盒故障分析效率 Ｎ—Ｐ完全问题，求解复杂度非常高，因此现有代数 攻击仅能对约减轮的分组密码进行安全性分析。随 着旁路信息的引入，代数方程组的求解速度可大大 提高，从而对全轮密码算法实现构成严峻威胁。 目前，求解代数方程组主要包括基于可满足性 问题ｌ７，８１（使用ｚＣｈａｆｆ、Ｍｉｎｉｓａｔ、ＣｒｙｐｔｏＭｉｎｉｓａｔ等解 析器）、基于伪随机优化问题ｌＩ钊（使用ＣＰＬＥＸ、ＳＣＩＰ 解析器）、线性化（直接线性化ＸＬ 】、扩展线性化 ＸＳＬｆＪ州）、基于Ｇｒｏｂｎｅｒ基¨圳等方法。本文采用第１ 种，利用ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器进行密钥求解。 根据表１，对于给定的１对输入和输出差分， 可以获取２～４个ｓ盒索引，２对输入和输出差分即 可以较高概率恢复Ｓ盒索引，结合密文恢复４ｂｉｔ后 期白化密钥 。攻击中，如果每个故障样本经传 ４ ＰＲＥＳＥＮＴ代数故障攻击模型 ４．１符号定义 Ａ 、 、Ｃｆ：分别表示第ｉ轮轮密钥加、Ｓ盒代 播后都能传播到ＰＲＥＳＥＮＴ第３１轮的１６个Ｓ盒（如 图３所示），则就有可能使用２个样本恢复 。 此时，可能的故障传播过程为：在第２９轮Ａ 注入宽度为４的故障（或者在曰 注入故障），使得 Ｂ２９的４个比特全出错，即输出差分为１１１１２（ＯｘＯｆ）， 这４个比特经Ｐ置换可扩散至第３Ｏ轮的４个Ｓ盒 输入，经第３０轮Ｓ盒后，输出差分全为ｌ１１１２（ＯｘＯｆ）， 换、Ｐ置换输出；Ａ 、Ｂ 、Ｃｆ ：分别表示第ｉ轮 轮密钥加、Ｓ盒代换、Ｐ置换故障输出；△Ａ 、ＡＢ 、 △ ：分别表示第ｉ轮轮密钥加、Ｓ盒代换、Ｐ置换 ２９轮 ３Ｏ轮 ３ｌ轮 图３ ＰＲＥＳＥＮＴ故障攻击模型 第８期 吴克辉等：ＰＲＥＳＥＮＴ密码代数故障攻击 ．８９． 再经第３０轮Ｐ置换扩散至第３１轮的１６个ｓ盒， 使得这１６个Ｓ盒输入和输出差分均不为０。表２为 ＰＲＥＳＥＮＴ的部分Ｓ盒差分表，其中输出差分中均 出现Ｏｘｆ，其对应Ｓ盒输入差分一共有０ｘ０６，０ｘ０７， ０ｘ０８，０ｘ０ｆ４种。根据上文分析，如果在Ａ 注入４ｂｉｔ 故障，如果Ｓ盒输入差分为０ｘ０６，０ｘ０７，０ｘ０８，０ｘ０ｆ中任 １６个Ｓ盒输出均不为０，且根据ＰＲＥＳＥＮＴ单比特 Ｓ盒输入差分对应Ｓ输出差分表，输出值均属于集合 ｛０ｘ０３，０ｘ０５，０ｘ０６，０ｘ０７，０ｘ０９，０ｘ０ａ，０ｘ０ｂ，０ｘ０ｃ，０ｘ０ｄ，０ｘ０ｅ， ０ｘ０ｆ｝时，视为理想故障样本，否则剔除该故障样本。 需要说明的是，在故障宽度为４的情况下，如 果在第２９轮Ｐ置换输出到第３ｌ轮输出之间注入宽 意一种，就有可能使得Ｂ２９为０ｘ０ｆ（或者直接在Ｂ２９ 注入差分为０ｘ０ｆ故障），当扩散至第３Ｏ轮４个Ｓ盒时， Ｓ盒输入差分可能为０ｘ０１，０ｘ０２，０ｘ０４，０ｘ０８，而当３Ｏ轮 度为４的故障，由于ＰＲＥＳＥＮＴ的Ｐ置换特性，均 不能使得第３１轮的１６个输出差分全不为０。而如 果在第２９轮前注入宽度为４的故障，经过多轮故 ４个Ｓ盒输入差分均为０ｘ０８时，恰好使得３Ｏ轮的４ 个Ｓ盒输出差分均为０ｘ０ｆ，然后经Ｐ转换传播后，使 得 的１６个Ｓ盒输入出现单比特故障。 综上，文中理想的故障模型为在第２９轮Ａ 注入宽度为４的故障，其故障差分为０ｘ０６，０ｘ０７， ０ｘ０８，０ｘ０ｆ，使得Ｂ２９的４个比特全出错，或者直接 在 注入差分为 ０厂故障。 表２ ＰＲＥＳＥＮＴ差分Ｓ盒（输出差分有ＯｘＯｆ） ４．３故障样本筛选 根据４．２节，理想的故障样本对应的第３１轮 ｌ６个Ｓ盒输入差分应可能为０ｘ０１，０ｘ０２，０ｘ０４，０ｘ０８ 中１种，而第３１轮Ｓ盒输出差分应有ｌ６个非零 值。 在获取到故障密文样本后，首先将密文经逆Ｊｐ 置换得到第３１轮Ｓ盒输出差分△ ，如果△∥ 的 障传播，第３１轮的１６个Ｓ盒输入差分很难满足均 为单比特故障差分。 ５ ＰＲＥＳＥＮＴ代数故障攻击 ５．１ ＰＲＥＳＥＮＴ代数方程组构建 密码代数攻击都可归结于建立和求解有限域 ＧＦ（ ）上系数任意选取的非线性布尔方程组，而建 立分组密码Ｓ盒的超定、稀疏代数方程组一直是代 数攻击研究的难点。本文参考文献［１４１中基于高斯 消元法建立Ｓ盒代数方程组的方法，用９个极端稀 疏的八元二次布尔方程（ＭＱ方程）表示ＰＲＥＳＥＮＴ 的Ｓ盒，用大约８ ０００个未知变元、２０ ０００个ＭＱ 方程来表示ＰＲＥＳＥＮＴ ３ １轮加密。未知变元包括４ 种类型，如表３所示。 表３ 新增变元及说明 变元 说 明 Ｐ 第ｒ轮轮密钥加输入比特 第ｒ轮轮密钥比特 第ｒ轮查Ｓ盒前输入比特 第ｒ轮查Ｓ盒前输出比特 注：（Ｏ≤ｒ＜￣３１，Ｏ≤ｆ乓６３） ＰＲＥＳＥＮＴ加密转化为以下等效布尔方程组： Ｐ ０ ｋｉ ＝ｘｉ （０≤ｒ≤３１，０≤ｉ≤６３） （２） ｓ（ｘ４ ，ｘ４川， ｆ＋２，ｘ４，＋３）： ， ＋ｌ，）， ，ｙ４Ｈ。 （０≤ｒ≤３０，０≤ｔ≤１５） （３） Ｙ ＝Ｐｇ（ｆ） （０≤，．≤３０，０≤ｉ≤６３） （４） 式（２）表示３ｌ轮及白化轮加密过程中与轮密 钥加操作；式（３）表示３ｌ轮加密过程中Ｓ盒代换 操作；式（４）表示３ｌ轮加密过程中Ｐ置换操作， 置换函数ｇ详见文献［１２】。此外，如考虑到轮密钥 扩展，每轮还可增加大约２００个ＭＱ方程。 ・９０・ 通信学报 第３３卷 其中，代换函数Ｓ的输入变元 ｌ，Ｘ２，Ｘ３，Ｘ４和输 出变元Ｙ１，Ｙ２，Ｙ３，ｙ４满足以下Ｓ盒代数方程组：１０ ④Ｘ２ ０ Ｙ２ ０ｘｌＹ１ ０ｘｌＹ３ ０ｘｌＹ４④ｘ４ｙｌ ＝０ Ｘｌ ０Ｘ２ ０ｘ４①Ｙ４①ｘｌＹ２（壬》ＸｚＹｌ④ｘ２Ｙ２ ０ｘｚＹ３① Ｘ２Ｙ４ ０ｘ３Ｙｌ ０ｘ４Ｙ１ ０ ０ ），２①ｘｊｙ３（壬》 ），４ ０Ｘ２Ｙ２（壬》ｘ３Ｙ１ ０ｘ３Ｙ２＝０ ０ ｙ２①ｘｚＹ２（壬》 ３ ０ｘ３Ｙ４（壬》ｘ４Ｙｌ＝０ １④ｘ３④ｘ４ ０ Ｙ１ ０ ｙ２①ＸｌＹ３ ０ Ｘ３Ｙ１（王》Ｘ４Ｙｌ：０ ④ ０ Ｙ３ ０ｘｌＹ３ ０ ），４ ０ｘ２Ｙ１ ０ｘ２Ｙ２④ ２Ｙ４①Ｘ３Ｙ１①Ｘ４Ｙ１：０ ０ ０ ０ｘｌＹ３①ｘｌＹ４ ０ｘ２Ｙ２ ０ｘ２Ｙ３④ ｘ２Ｙ４ ０ ｘ３Ｙ４ ０ ｘ４ｙ２＝０ ④Ｘ１Ｙ３①ｘ２Ｙ１①Ｘ２Ｙ２ ０ｘ２Ｙ３①ｘ２Ｙ４（壬》ｘ４Ｙｌ ０ ｘ４Ｙ３：０ ２①Ｘ４ ０ｘｌＹ２ ０ ｙ３①ｘｌＹ４ ０ｘ２Ｙ３ ０ｘ２Ｙ４① ｘ３Ｙ４ ０ ｘ４ｙｌ①ｘ４ｙ４＝０ ５．２故障信息利用 １）故障位置已知 基于４．２节故障模型，第２９轮ＡＢ 。中只有１个 Ｓ盒输出差分为０ｘ０ｆ，其他为０。假如第 个Ｓ盒输 出差分为ＯｘＯｆ，则可表示为 （５） 其他ｌ５个Ｓ盒输出差分均为０，可表示为 ４ｍ＋３ Ｐｌ（Ｂ ０ Ｂｉ ０１）＝１ ｍＥ【０，１５１，ｍ≠＇『 （６） ｆ＝４ｍ 此外，由于正确和故障密文可直接代入正确和 故障样本的等效代数方程组，相当于密文差分的间 接代入，故无需再建立关于密文差分的代数方程。 ２）故障位置未知 基于４．２节故障模型，第２９轮ＡＢ２９中只有１个 ｓ盒输出差分为ＯｘＯｆ，非０差分对应的位置有１６种 可能。每种可能位置的故障差分表示为（Ｂ ｒ 表示 第，种可能的故障位置情况下第，．轮Ｓ盒代换的故 障输出）： ４ｍ＋３ ｎ（ ０ Ｂ ｒ，：０１） ｍ， ∈【０，１５］ （７） ｉ＝４ｍ 由于只有１种可能位置的故障差分对应的代数 方程组成立，即ｌ６个变量 ｆ中只有１个为１，其余 为０，因此集合 ， ２，ｆ１３，… ）的汉明重为１，即满 足函数： ＨＷ ｌ， ２， ３，…，ｆｌｓ）＝ｌ （８） 其中，汉明重函数ＨＷ如下： 对于１个１６ｂｉｔ的集合ｘ： ， ，…， ，ｘｍ）， 共有１７种可能的汉明重ＨＷ（Ｘ）（０≤ＨＷ（ ≤１６）， 可以分别用一个５ｂｉｔ的变量ｙ＿（ｙ１，Ｙ２，Ｙ３，Ｙ４，Ｙ５）表示。 ｘ、ｙ满足以下方程（其中，１≤ｉ≤』≤ｍ≤ｎ≤Ｐ≤ ｎ 目≤ ≤ｔ≤１６）： １６ ０ Ｙ ＝ｎ ＝ ｌ２ ８７０ Ｙ２＝∑ａｔｘｉｘＪＸｎ￣ＸｎＸｐＸｑＸｓＸｔ １＝１ １ ８２０ Ｙ ＝∑ａｔｘｉｘ，ＸｍＸｎ （９） ｔ＝ｌ １２０ Ｙ ＝∑ ｔ＝ｌ １６ Ｙ ＝∑ ５．３实验结果及比较 在普通ＰＣ机（ＣＰＵ为Ａｔｈｌｏｎ６４ ３０００＋１．８１ＧＨｚ， 内存为１ＧＢ）上，利用Ｃ＋＋语言、ＣｒｙｐｔｏＭｉｎｉＳＡＴ 软件实现了ＰＲＥＳＥＮＴ代数故障攻击仿真实验，攻 击流程如图４所示。 图４ ＰＲＥＳＥＮＴ代数故障攻击流程 下面给出某次ＰＲＥＳＥＮＴ代数故障攻击的过程。 １）产生１个随机明文Ｐ＝２３２Ｆ２Ｂ９８Ｃ１５１Ｅ ＡＢ５ｌ６，密钥Ｋ＝７ＦＢ５３１４２１Ｃ９Ｅ０２３１６０Ｂ２ 后期白 化密钥为６２ＤＥｌ９Ａ３Ｂ６４ＡＤ６Ｅ８ 此时正确密文 为：Ｅ５Ｂ３１３６ＦＤ４３２ＥＤ２Ｅ１６；然后设定攻击样本量， 在ＰＲＥＳＥＮＴ加密第２９轮注入４ ｂｉｔ随机故障。 第８期 吴克辉等：ＰＲＥＳＥＮＴ密码代数故障攻击 ・９ｌ・ ２）按照４．３节方法筛选有效故障样本，如第１ 个有效故障密文ｃ ＝４３３７１Ｄ６２８Ｂ８７２９２７ 第２ 个有效故障密文Ｃ；ｌ； ＝Ｅ８２４３５Ｂ１３９Ｆ６Ｃ６９７１６ｏ ３）参考５．１节方法构建３个样本（１个正确样 本，２个故障样本）的ＰＲＥＳＥＮＴ最后３轮代数方 程组；参考５．２节方法将故障注入差分、密文差分 转化为额外代数方程组。 ４）将密码算法和故障信息代数方程组转化为 ＳＡＴ子句，利用ＣｒｙｐｔｏＭｉｎｉＳＡ解析器求解密钥。 实验中２对ＰＲＥＳＥＮＴ正确一故障样本３轮的代数方 程组大约转化为７８ ０００个ＳＡＴ子句。解析器密钥 求解结果如表４所示。 表４ ＰＲＥＳＥＮＴ代数故障攻击结果 编号 编号 编号 。 编号 －８３４ ０ －８５０ ０ ８６６ １ ８８２ １ ８３５ ｌ －８５１ Ｏ －８６７ ０ ８８３ ｌ ８３６ １ －８５２ ０ ８６８ １ －８８４ ０ ８３７ ０ ８５３ １ ｓ／垦茁琏＊ ８６９ １ ８８５ １ －８３８ ０ ８５４ 如 ∞ １ ∞ －８７０ 加 ０ －８８６ ０ －８３９ ０ －８５５ ０ ８７１ １ ８８７ １ ８４０ ｌ －８５６ ０ ８７２ ｌ ８８８ １ －８４１ ０ ８５７ １ －８７３ ０ —８８９ ０ ８４２ １ ８５８ ｌ －８７４ ０ ８９０ １ ８４３ １ －８５９ ０ ８７５ １ ８９１ １ —８４４ ０ ８６０ １ －８７６ ０ ８９２ １ ８４５ １ －８６１ ０ －８７７ ０ －８９３ ０ ８４６ １ －８６２ ０ ８７８ １ ８９４ １ ８４７ １ －８６３ ０ －８７９ ０ －８９５ ０ ８４８ １ ８６４ １ ８８０ １ －８９６ ０ －８４９ ０ ８６５ １ －８８１ ０ －８９７ ０ 如表４所示，编号８３４至８９７依次表示６４ｂｉｔ 的后期白化密钥比特值，如果编号为正，表示对应 密钥位为１，否则为０。根据表４，求解的后期白化 密钥为０１１０００１０１１０１１１１００００１１００１１０１０００１１１０１１０ １ １００１００１０１０１ １０１０１ １０１ １ １０１０００２，即６２ＤＥ１９Ａ３Ｂ６４ ＡＤ６Ｅ８ 同真实密钥一致，攻击成功；且故障 已知时，耗时１６．３５ｓ，故障位置未知时，耗时 ３１．５８ｓ。 图５表示在ＰＲＥＳＥＮＴ密码第２９轮注入４ｂｉｔ 故障，成功恢复 条件下，不同样本量对应的 ＣｒｙｐｔｏＭｉｎｉＳＡＴ求解平均时间。可见最少仅需２ 对正确一故障样本即可将ＰＲＥＳＥＮＴ－８０密钥搜索 空间降低为２ ，且样本量同求解时间成正比；另 外较之故障位置已知，故障位置未知条件下代数 方程组复杂度稍高，导致ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器 求解时间稍长。 图５不同样本量下ＣｒｙｐｔｏＭｉｎｉＳＡＴ求解平均时间 实验结果同国内外ＰＲＥＳＥＮＴ故障攻击比较 如表５所示。可见，本文的攻击方案在故障样本 量方面优势明显，攻击可行性较强，而且可利用 解析器自动恢复密钥，具有一定的优越性。由于 代数分析在分组密码领域的通用性，本文的分析 方法可以扩展至其他分组密码的故障攻击，从而 成为从故障攻击角度，评估分组密码实现安全性 的通用手段之一。 表５实验结果同国内外ＰＲＥＳＥＮＴ故障攻击比较 ６结束语 本文将代数攻击和故障攻击相结合，对代数故 障攻击进行了研究。给出了代数故障攻击模型，以 ＰＲＥＳＥＮＴ轻型分组密码为例进行了攻击应用；首 先建立了ＰＲＥＳＥＮＴ故障攻击模型，然后给出了故 障样本筛选、ＰＲＥＳＥＮＴ密码代数方程组构建、故 障信息利用方法，最后通过仿真实验验证了攻击方 法的可行性。 结果表明：应用文中故障模型，理想情况下， ２次故障注入，使用ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器进行 方程组求解，即可恢复ＰＲＥＳＥＮＴ．８０的６４ｂｉｔ后期 白化密钥，耗时不超过５０ｓ；同现有攻击相比， ・９２・ 通信学报 第３３卷 文中提出故障模型所需的故障注入次数较小，给 出的密文筛选方案明确，而且可使用解析器自动 进行密钥求解，具有一定的优越性；此外，文中 方法可为其他分组密码故障攻击提供一定的借鉴 和参考。 参考文献： Ｉ１】 ＤＯＮＥＨ Ｄ，ＤＥＭＩＬＬＯ Ｒ．ＬＩＰＴＯＮ Ｒ．Ｏｎ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｃｈｅｃｋｉｎｇ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｆａｕｌｔｓ［Ａ］Ｅｕｒｏｃｒｙｐｔ’９７［Ｃ］．Ｋｏｎｓｔｎａｚ， Ｇｅｒｍａｎｙ．１９９７．３７—５ １ ［２］ ＢＩＨＡＭ Ｅ，ＳＨＡＭＩＲ Ａ Ｄｉｆｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｆ ｓｅｃｒｅｔ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍｓ［Ａ］．Ｃｒｙｐｔｏ’９７［Ｃ］．Ｓａｎｔａ Ｂａｒｂａｒａ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ， １９９７．５１３—５２５ ［３］ ＤＥＢＤＥＥＰ Ｍ．Ａｎ ｉｍｐｒｏｖｅｄ ｆａｕｌｔ ｂａｓｅｄ ａｔｔａｃｋ ｏｆ ｔｈｅ ａｄｖａｎｃｅｄ ｅｎ— ｃｒｙｐｔｉｏｎ ｓｔｎａｄａｒｄ［Ａ］．ＡＦＲＩＣＡＣＲＹＰＴ ２００９［Ｃ］．Ｇａｍｍａｒｈ，Ｔｕｎｉｓｉａ， ２Ｏ０９．４２１—４３４． 【４］ ＺＨＡＯ Ｘ Ｊ，ＷＡＮＧ Ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅｄ ｄｉｆｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｎ ｃａｍｅｌｌｉａ ｂｙ ｅｘｐｌｏｒｉｎｇ ｆａｕｌｔ ｗｉｄｔｈ ａｎｄ ｄｅｐｔｈ［ＥＢ／ＯＬ］ｈｔ【ｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ ｏｒｇ／２０１０／０２６．ｐｄｆ，２０１０ ［５Ｊ Ｌ１ ＧＵＤ ＬＩ ＪＲ．Ｄｉｆｆｅｒｅｎｔｉａｌｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｎｔｈｅＡＲＩＡａｌｇｏ— ｒｉｔｈｍ［Ｊ］Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ，２００８，１７８（１９）：３７２７—３７３７． ［６］ ＮＩＣＯＬＡＳ Ｔ Ｃ．ＪＯＳＥＦ Ｐ．Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ｂｌｏｃｋ ｃｉｐｈｅｒｓ ｗｉｔｈ ｏｖｅｒ－ ｄｅｆｉｎｅｄ ｓｙｓｔｅｍｓ ｏｆ ｅｑｕａｔｉｏｎｓ［Ａ］ＡＳＩＡＣＲＹＰＴ ２００２［Ｃ］Ｂｅｒｌｉｎ Ｈｅｉ— ｄｅｌｂｅｒｇ，２００２ ２６７—２８７ ［７】 ＭＡＴＨＩＥＵ Ｒ，ＦＲＡＮＣＯＩＳ—Ｘ Ｓ Ａｌｇｅｂｒａｉｃ ｓｉｄｅ—ｃｈａｎｎｅｌ ａｔｔａｃｋｓ［Ａ］ ＩＮＳＣＲＹＰＴ ２００９［Ｃ］．Ｃａｌｉｆｏｒｎｉａ．ＵＳＡ．２００９ ３９３—４１０ ［８］ ＭＡＴＨＩＥＵ Ｒ，ＦＲＡＮＣＯＩＳ—Ｘ，ＮＩＣＯＬＡＳ Ｖ－Ｃ Ａｌｇｅｂｒｉａｃ ｓｉｄｅ—ｃｈａｎｎｅｌ ａｔｔａｃｋｓ ｏｎ ｔｈｅ ＡＥＳ：Ｗｈｙ ｔｉｍｅ ａｌｓｏ ｍａｔｔｅｒｓ ｉｎ ＤＰＡ［Ａ］．ＣＨＥＳ ２００９［Ｃ】 Ｃａｌｉｆｏｒｎｉａ ＵＳＡ．２００９．９７—１１１． ［９］ 李卷孺，谷大武．ＰＲＥＳＥＮＴ算法的差分故障攻击［Ａ］．中国密码学 会２００９年会［ｃ］．中国，北京，２００９．３－１３ ＬＩ Ｊ Ｒ，ＧＵ Ｄ、 Ｄｉｆｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｎ ＰＲＥＳＥＮＴ［Ａ】．ＣＨＩ・ ＮＡＣＲＹＰＴ ２００９［Ｃ１ Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，２００９．３－１３． 【１０１ ＺＨＡＯ Ｘ Ｊ．ＷＡＮＧ Ｔ Ｆａｕｌｔ ｐｒｏｐａｇａｔｅ ｐａｔｔｅｒｎ ｂａｓｅｄ ＤＦＡ ｏｎ ＳＰＮ ｓｔｒｕｃｔｕｒｅ ｂｌｏｃｋ ｃｉｐｈｅｒｓ ｕｓｉｎｇ ｂｉｔｗｉｓｅ ｐｅｒｍｕｔａｔｉｏｎ．ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ＰＲＥＳＥＮＴ ａｎｄ ＰＲＩＮＴｃｉｐｈｅｒ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１１／０８９． ｐｄｆ，２０１１． ＷＡＮＧＧＬ，ＷＡＮＧ Ｓ Ｓ Ｄｉｆｆｅｒｅｎｔｉｌａｆａｕｌｔａｎａｌｙｓｉｓ ｏｎ ＰＲＥＳＥＮＴｋｅｙ ｓｃｈｅｄｕｌｅ［Ａ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ｓｅｃｕｒｉｔｙ（ＣＩＳ ２０１０）［Ｃ１．２０１０．３６２—３６６． ［１２］ ＢＯＧＤＡＮＯＶ Ａ．ＫＮＵＤＳＥＮ Ｌ Ｒ，ＬＥＡＮＤＥＲ， 日ｆ．ＰＲＥＳＥＮＴ：ａｎ ｕｌｔｒａ—ｌｉｇｈｔｗｅｉｇｈｔ ｂｌｏｃｋ ｃｉｐｈｅｒｉＡ］．ＣＨＥＳ ２００７［Ｃ］．Ｖｉｅｎｎａ，Ａｕｓｔｒｉａ， ２００７ ４５０．４６６ ［１３ Ｊ 李伟博，解永宏，胡磊分组密码ｓ盒的代数方程［Ｊ１．中国科学院研究 生学报，２００８，２５（４）：５２４ ５２９． ＬＩ Ｗ Ｂ．ＸＩＥ Ｙ Ｈ．ＨＵ Ｌ．Ａｌｇｅｂｒａｉｃ ｅｑｕａｔｉｏｎｓ ｏｆ ｓｂｏｘ ｂｌｏｃｋ ｃｉｐｈｅｒ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ｇｒａｄｕａｔｅ Ｓｃｈｏｏｌ ｏｆ ｔｈｅ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ， ２００８，２５（４）：５２４—５２９． ［１４］ ＡＬＥＸ Ｂ．ＣＨＲＩＳＴＯＰＨＥ Ｄ Ｃ．Ｂｌｏｃｋ ｃｉｐｈｅｒｓ ａｎｄ ｓｙｓｔｅｍｓ ｏｆ ｑｕａｄｒａｔｉｃ ｅｑｕａｔｉｏｎｓ［Ａ］ＦＳＥ ２００３［Ｃ］２００３．２７４—２８９． ［１５］ ＧＩＲＡＵＤ Ｃ，ＴＨＩＥＢＥＡＵＬＤ Ｈ．Ａ ｓｕｒｖｅｙ ｏｎ ｆａｕｌｔ ａｔｔａｃｋｓ［Ａ］Ｉｎｔｅｒｎａ— ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｍａｒｔ Ｃａｒｄ Ｒｅｓｅａｒｃｈ ｎａｄ Ａｄｖａｎｃｅｄ Ａｐｐｌｉｃａｔｉｏｎｓ （ＣＡＲＤＩＳ’ｏ４）［Ｃ】Ｔｏｕｌｏｕｓｅ，Ｆｒａｎｃｅ，２００４．２２—２７ 【１６］ ＹＯＳＳＥＤ Ｏ，ＭＡＲＩＯ Ｋ，ＴＨＯＭＡＳ ｅｔ ａ１．Ｓｉｄｅ—ｃｈａｎｎｅｌ ａｎａｌｙｓｉｓ ｉｎ ｔｈｅ ｐｒｅｓｅｎｃｅ ｏｆ ｅｒｒｏｒｓ［Ａ］ＣＨＥＳ ２０１０［Ｃ］．Ｓａｎｔａ Ｂａｒｖａｒａ，Ｃａｌｉｆｏｒｎｉａ， ２０１０．４２８—４４２． 【１７】 ＣＯＵＲＴＯＩＳ Ｎ Ｔ，ＫＬＩＭＯＶ Ａ，ＰＡＲＡＲＩＮ Ｊ．Ｅｆｉｆｃｉｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｏｌｖｉｎｇ ｏｖｅｒｄｅｆｍｄ ｓｙｓｔｅｍｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｐｏｌｙｎｏｍｉｌａ ｅｑｕａｔｉｔｏｎ［ＥＢ／ＯＬ］． ｈｔｔｐ：／］ｗｗｗ．ｉａｃｒ．ｏｒｇ／ｒａｃｈｉｖｅ／ｅｎｒｏｃｒｙｐｔ２０００／１８０７／１８０７０３９８一ｎｅｗ／ｐｄｆ，２０００ ［１８１ ＫＩＰＮＩＳ Ａ，ＳＨＡＭＩＲ Ａ．Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ＨＦＥ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏ— ｓｙｓｔｅｍ ｂｙ ｒｅｌｉｎｅａｒｉｚａｔｉｏｎ［Ａ］．Ｃｒｙｔｏ９９［Ｃ］，Ｓａｎｔａ Ｂ￣ｂａｒａ，Ｃａｌｉｆｏｒｎｉａ， ＵＳＡ．１９９９ １９—３０ ［１９］ＳＥＧＥＲ Ａ Ｊ Ｍ．Ａｌｇｅｒｉａｃ ａｔｔａｃｋｓ ｆｒｏｍ ａ Ｇｒｏｂｎｅｒ ｂａｓｉｓ ｐｅｒｓｐｅｃ ｔｉｖｅｓ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ ｗｉｎ．ｔｒｕｅ．ｎｌ／ ２（ｘ）４ 作者简介 吴克辉（１９８６一），男，甘肃景泰人， 军械工程学院硕士生，主要研究方向为分 组密码旁路分析。 赵新杰（１９８６一），男，河南开封人， 军械工程学院博士生，主要研究方向为分 组密码旁路分析和故障分析。 王韬（１９６４一），男，河北石家庄人， 博士，军械工程学院教授、博士生导师， 主要研究方向为信息安全和密码学。 郭世泽（１９６９一），男，河北石家庄人，博士，北方电 子设备研究所研究员、博士生导师，主要研究方向为信息安 全和密码学。 刘会英（１９８４一），男，湖北黄石人，军械工程学院博 士生，主要研究方向为图像加密和密码旁路分析。
2023年7月31日发(作者：)
第３３卷第８期 ２０１２年８月 通信学报 Ｖｂｌ＿３３ ＮＯ．８ Ｊｏｕｍａｌ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ａｕｇｕｓｔ ２０１２ ＰＲＥＳＥＮＴ密码代数故障攻击 吴克辉 ，赵新杰 ，王韬 ，郭世泽 ，刘会英 （１．军械工程学院计算机工程系，河北石家庄０５０００３；２．北方电子设备研究所，北京１０００８３） 摘要：提出了一种新的ＰＲＥＳＥＮＴ密码故障分析方法——代数故障攻击。将代数攻击和故障攻击相结合，首先 利用代数攻击方法建立密码算法等效布尔代数方程组；然后通过故障攻击手段获取错误密文信息，并将故障差分 和密文差分转化为额外的布尔代数方程组；最后使用ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器求解方程组恢复密钥。结果表明：在 ＰＲＥＳＥＮＴ－８０的第２９轮注入宽度为４的故障，故障位置和值未知时，２次故障注入可在５０ｓ内恢复６４ｂｉｔ后期白 化密钥，将ＰＲＥＳＥＮＴ－８０密钥搜索空间降低为２ ，经ｌｍｉｎ暴力破解恢复完整主密钥；和现有ＰＲＥＳＥＮＴ故障攻 击相比，该攻击所需样本量是最小的；此外该代数故障分析方法也可为其他分组密码故障分析提供一定思路。 关键词：故障攻击；代数攻击；代数故障攻击；ＰＲＥＳＥＮＴ密码 中图分类号：ＴＰ３９３．０８ 文献标识码：Ａ 文章编号：１０００—４３６Ｘ（２０１２）０８—００８５—０８ Ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ ｏｎ ＰＲＥＳＥＮＴ ｗｕ Ｋｅ—ｈｕｉ ，ＺＨＡＯ Ｘｉｎ－ｊｉｅ ，ｗＡＮＧ Ｔａ０ ，ＧＵＯ Ｓｈｉ—ｚｅ ，ＬＩＵ Ｈｕｉ．ｙｉｎｇ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆＣｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｏｒｄｎａｎｃｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｌｌｅｇｅ，Ｓｈｉｊｉａｚｈｕａｎｇ ０５０００３，Ｃｈｉｎａ； ２．Ｔｈｅ Ｉｎｓｔｉｔｕｔｅ ｏｆＮｏｒｔｈ Ｅｌｅｃｔｒｏｎｉｃ Ｅｑｕｉｐｍｅｎｔ，Ｂｅｉｊｉｎｇ １０００８３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｎｅｗ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｍｅｔｈｏｄ ｏｎ ＰＲＥＳＥＮＴ－－ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ ｗａｓ ｐｒｏｐｏｓｅｄ．Ｔｈｉｓ ａｕａｃｋ ｃｏｍｂｉｎｅｄ ｃｏｎ— ｖｅｎｆｉｏｎａｌ ａｌｇｅｂｒａｉｃ ｃｒｙｐｔａｎａｌｙｓｉｓ ｗｉｔｈ ｆａｕｌｔ ａｔｔａｃｋ，ｆｉｒｓｔｌｙ ｂｕｉｌｔ ｅｑｕｉｖａｌｅｎｔ Ｂｏｏｌｅａｎ ａｌｇｅｂｒａｉｃ ｅｑｕａｔｉｏｎｓ ｏｆ ｃｉｐｈｅｒ ｅｎｃｒｙｐ— ｔｉｏｎ ｂｙ ａｌｇｅｂｒａｉｃ ｃｒｙｐｔａｎａｌｙｓｉｓ ｍｅｔｈｏｄ；ｓｅｃｏｎｄｌｙ ｇｏｔ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｆａｕｌｔ ｃｒｙｐｔｏｇｒａｐｈ ｂｙ ｆａｕｌｔ ａｔｔａｃｋ ｔｅｃｈｎｉｑｕｅ，ａｎｄ ｔｒａｎｓｆｏｒｍｅｄ ｄｉｆｆｅｒｅｎｔｉａｌ ｏｆ ｆａｕｌｔ ａｎｄ ｃｒｙｐｔｏｇｒａｐｈ ｉｎｔｏ ａｄｄｉｉｏｎａｌｔ ａｌｇｅｂｒａｉｃ ｅｑｕａｔｉｏｎｓ；ｆｉｎａｌｌｙ ｕｔｉｌｉｚｅｄ Ｃｒｙｐｔｏ Ｍｉｎｉ ＳＡＴ ｓｏｌｖｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｅｑｕａｔｉｏｎｓ ａｎｄ ｒｅｃｏｖｅｒ ｋｅｙ．Ｅｘｐｅｒｉｍｅｎｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ａｆｔｅｒ ｉｎｊｅｃｔｉｎｇ ４－ｂｉｔ ｆａｕｌｔ ｔｏ ｔｈｅ ２９ ｒｏｕｎｄ ｏｆ ＰＲＥＳＥＮＴ－８０，ｔｈｅ ｆａｕｌｔ ｌｏｃａｔｉｏｎ ａｎｄ ｆａｕｌｔ ｖａｌｕｅ ａｒｅ ｕｎｋｎｏｗｎ，ｏｎｌｙ ２ ｉｎｊｅｃｔｉｎｇｓ ｃａｎ ｒｅｃｏｖｅｒ ６４一ｂｉｔ ｌａｓｔ ｗｈｉｔｅｎｉｎｇ ｋｅｙ ｉｎ ５０ ｓｅｃｏｎｄｓ ｔｈａｔ ｒｅｄｕｃｅ ｍａｓｔｅｒ ｋｅｙ ｏｆ ＰＲＥＳＥＮＴ－８０ ｓｅａｒｃｈｉｎｇ ｓｐａｃｅ ｔｏ ２ ．ｔｈｅｎ ｒｅｃｏｖｅｒ ｔｈｅ ｍａｓｔｅｒ ｋｅｙ ａｆｔｅｒ ｌ ｍｉｎ— ｕｔｅ ｂｒｕｔｅ－－ｆｏｒｃｅ・－ｓｅａｒｃｈ ｏｎ ａｖｅｒａｇｅ；ｃｏｍｐａｒｅｄ ｗｉｔｈ ｐｒｅｖｉｏｕｓ ｆａｕｌｔ ａｔｔａｃｋ ｏｎ ＰＲＥＳＥＮＴ，ｔｈｅ ａｍｏｕｎｔ ｏｆ ｔｈｉｓ ａｔｔａｃｋ ｓａｍｐｌｅ ｉｓ ｔｈｅ ｓｍａｌｌｅｓｔ；ｍｅａｎｗｈｉｌｅ，ｔｈｅ ａｎａｌｙｓｉｓ ｍｅｔｈｏｄ ｐｒｏｐｏｓｅｄ ｃａｎ ｂｅ ａｐｐｌｉｅｄ ｉｎｔｏ ｔｈｅ ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ ｏｆ ｏｔｈｅｒ ｂｌｏｃｋ ｃｉｐｈｅｒｓ． Ｋｅｙ ｗｏｒｄｓ：ｆａｕｌｔ ａｔｔａｃｋ；ａｌｇｅｂｒａｉｃ ａｔｔａｃｋ；ａｌｇｅｂｒａｉｃ ｆａｕｌｔ ａｔｔａｃｋ；ＰＲＥＳＥＮＴ １ 引言 密码算法安全性分析可分为面向设计的数学 分析和面向实现的旁路分析２种。前者将密码实现 收稿日期：２０１１—０７—３０；修回日期：２０１１—１０—２４ 视为黑盒，通过观测密码输入和输出，利用差分分 析、线性分析、代数分析等数学方法分析其安全性， 但受复杂度限制，现有方法仅能对算法安全性进行 理论分析，很少能对其构成实际威胁；后者将密码 基金项目：国家自然科学基金资助项目（６０７７２０８２，６１１７３１９１）；河北省自然科学基金资助项目（０８Ｍ０１０） Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍｓ：Ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ（６０７７２０８２，６１１７３１９１）；Ｔｈｅ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｈｅｂｅｉ Ｐｒｏｖｉｎｃｅ（０８Ｍ０１０） 通信学报 第３３卷 实现视为灰盒，通过观测密码实现过程中泄露的时 间、功耗、电磁、声音、故障等信息，结合密码输 入和输出，利用简单分析、差分分析、相关分析、 碰撞分析、互信息分析等方法，基于密钥分而治之 的思想，在极小的代价下快速恢复密钥，目前已对 多种密码算法的各种实现构成严峻威胁。在旁路分 析中，根据密码运行泄露信息不同，可将其分为计 时分析、功耗分析、电磁分析、故障分析等。 密码故障分析作为一种有效的旁路攻击方法， 最早由Ｂｏｎｅｈ等人【ｌ１２．＿在１９９６年提出，并成功攻破 ＲＳＡ签名算法。随后Ｂｉｈａｍ和Ｓｈａｍｉｒ于１９９７年 提出了差分故障分析（ＤＦＡ，ｄｉｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙ． ｓｉｓ）方法，对ＤＥＳ密码进行了攻击。此后密码学 家在此基础上实现了针对分组密码的差分故障攻 击 Ｊ。然而差分故障分析也具有一定的缺点：需 要结合具体算法结构和操作进行密钥推导，分析方 法繁琐；另外，即使在相同故障模型下，针对同一 密码算法分析中，研究者常会得到不同的实验结 果，这些都大大限制了差分故障攻击的通用性和实 用性。因此，研究通用、自动化的分析方法一直是 密码故障分析尚待解决的一个公开问题。 ２００２年，Ｃｏｕｒｔｏｉｓ等 在亚密会上首次提出代 数攻击的思想，将密码算法用代数方程组来等价表 示，通过求解方程组方法进行密钥恢复。由于该方 法可利用解析器进行密钥的自动化求解，可充分利 用计算机资源，因此，代数攻击为密码分析提供了 一种新的通用分析手段。然而，随着分组密码轮数 的增加，未知变量和代数方程组规模也会递增，在 有限复杂度内进行密钥求解是一个Ｎ—Ｐ完全问题， 这些都极大限制了代数分析的实用性。２００９年， Ｒｅｎａｕｌｄ［７，８１等将代数攻击和旁路分析相结合，提出 代数旁路攻击（ＡＳＣＡ，ａｌｇｅｂｒａｉｃ ｓｉｄｅ．ｃｈａｎｎｅｌ ａｔｔａｃｋ） 思想，在代数攻击基础上，通过旁路攻击手段采集 密码执行泄露的中间状态信息，并将其转化为额外 的代数方程组，结合密码算法方程组，加快代数方 程组求解速度。结果表明：针对ＰＲＥＳＥＮＴ和ＡＥＳ 密码算法，基于汉明重泄露模型，使用ｚＣｈａｆｆ解析 器，一条功耗曲线分析即可恢复完整密钥。代数旁 路分析为密码旁路分析提供了一种新的通用手段， 现有攻击大都基于功耗泄露模型，如何引入新的泄 露模型是代数旁路分析的一个热点问题。 本文尝试将代数攻击和故障攻击相结合，衍化 出一种新的代数旁路攻击手段——代数故障攻击， 并应用其对ＰＲＥＳＥＮＴ轻型分组密码进行故障分析。 现有ＰＲＥＳＥＮＴ故障攻击大都基于差分故障分析思 想开展，文献［９］首次对ＰＲＥＳＥＮＴ－８０加密过程进行 了差分故障分析，４０—５０对正确．故障样本可恢复后 期白化密钥，将主密钥搜索空间降低到２ ，文献［１０１ 提出了一种基于故障传播路径的差分故障分析方 法，８次故障注入即可将ＰＲＥＳＥＮＴ－８０密钥空间降低 到２Ｈ ；文献［１１】对ＰＲＥＳＥＮＴ密钥扩展进行了故障 分析，６４次故障注入可恢复第５１ｂｉｔ后期白化密钥， 将主密钥空间降低到２２９。在轻型分组密码代数故障 攻击方面，笔者尚未发现国内外有公开发表的文献。 本文首次提出针对ＰＲＥＳＥＮＴ的代数故障分析方 法，在ＰＲＥＳＥＮＴ加密第２９轮注入宽度为４的故障 模型下，２次故障注入可在５０ｓ内恢复６４ｂｉｔ后期白化 密钥，将ＰＲＥＳＥＮＴ－８０密钥搜索空问降低为２ ，并 给出了有效故障样本的判断方法；和现有ＰＲＥＳＥＮＴ 故障攻击相比，文中攻击所需样本量是最小的。 本文结构如下：第２节阐述ＰＲＥＳＥＮＴ分组密码 算法，第３节给出了代数故障攻击原理，第４节介绍 ＰＲＥＳＥＮＴ故障攻击模型，第５节给出了ＰＲＥＳＥＮＴ 代数故障攻击具体过程，第６节为结束语。 ２ ＰＲＥＳＥＮＴ密码算法 ＰＲＥＳＥＮＴ是由Ｂｏｇｄａｎｏｖ［１２［等人于２００７年提 出的轻量级分组密码，具有良好的硬件实现效率， 在０．１８ｇｍ工艺下仅需１５７０ＧＥ逻辑单元，可在ＲＦＩＤ 卡以及传感器网络等资源受限环境中广泛使用。算 法采用ＳＰＮ结构，分组长度为６４ｂｉｔ，支持８０ｂｉｔ、 １２８ｂｉｔ ２种密钥长度，共迭代３１轮。 加密过程如下。 轮函数Ｆ由轮密钥加、Ｓ盒代换、Ｐ置换３部 分组成。 １）轮密钥加Ａ ：６４ｂｉｔ轮输入同轮密钥进行异或。 ２）Ｓ盒代换层乩：将轮密钥加６４ｂｉｔ输出查找 １６个４进４出的Ｓ盒。 ３）Ｐ置换层ＤＬ：通过置换表Ｐ（ ）对Ｓ盒代换 ６４ｂｉｔ输出按比特进行重新排列。 为提高算法安全性，ＰＲＥＳＥＮＴ在第３１轮后使 用６４ｂｉｔ密钥 进行后期白化操作，具体加密流程 如图１所示。 密钥扩展算法如下。 首先将初始主密钥存储在寄存器 中，表示为 岛９岛８…ｋ０。第ｉ轮密钥 由寄存器 的前６４ｂｉｔ组 第８期 吴克辉等：ＰＲＥＳＥＮＴ密码代数故障攻击 ・８７・ 成。当生成第ｉ轮密钥 后，密钥寄存器 通过以 下方法进行更新： ［ｋ７９／ｃ７８…ｋｌｋｏ］＝［ｋｌｓｋｌ７…ｋ２ｏｋ１９］ ［ｋ７９ｋ７８ｋ７７ｋ７６］＝Ｓ［ｋ７９ｋ７８ｋ７７幻６】 ［忌１９足ｌ８足１７足１６足１５】＝［足ｌ９忌ｌ８足１７足１６ １５］０ ｒｏｕｎｄ＿ｃｏｕｎｔｅｒ 段：密码算法方程组构建、故障注入及利用和代数 方程组求解。其中，Ｐ、 、Ｃ分别表示明文、中问 状态以及密文， 、砍分别表示主密钥和轮密钥。．厂 和ｇ分别表示加密操作和密钥扩展。 和ｃ 分别 表示注入故障中间状态及错误密文输出，而△墨和 ＡＣ则分别表示注入故障差分和密文差分值。 １）密码算法方程组构建 其中，ｒｏｕｎｄ＿ｃｏｕｎｔｅｒ为当前的加密轮数。易见，只 需分析出６４ｂｉｔ后期白化密钥，即可将８０ｂｉｔ ＰＲＥ． ＳＥＮＴ的主密钥搜索空问降低到２ 。 将密码算法加密和密钥扩展分别表示为关于 Ｐ、 、Ｃ、Ｋ、ｒｋ的代数方程组 ）和ｇ（）。给定一 个密码算法的代数方程组，密钥恢复等价于代数方 程组求解。代数方程组构造过程中，最为关键的是 如何构造非线性部件Ｓ盒对应代数方程组。常用的 Ｓ盒代数方程组构造方法包括待定系数法、比较系 数法ｌｌ引。本文主要参考文献［１４１中基于高斯消元法 构造Ｓ盒代数方程组的方法，对ＰＲＥＳＥＮＴ密码的 ｓ盒构建等效方程组。 不同于其他类型的代数旁路攻击，代数故障攻 击只需构建密码算法注入故障所在轮直至加密结 束之间的代数方程组，因此攻击利用的代数方程组 数量较少，便于求解。 图１ ＰＲＥＳＥＮＴ加密流程 ２）故障注入及利用 在构建密码算法等效代数方程组之后，需要进 行故障注入和利用。故障注入的方法有很多，如光 学辐射诱导、电压故障诱导、临界温度诱导、电磁 ３代数故障攻击 如图２所示，代数故障攻击一般可分为３个阶 图２密码代数故障攻击模型 通信学报 第３３卷 辐射诱导等。由于故障诱导不是本文研究重点，更 多相关内容可参考文献［１５】。故障利用的主要思想 是将故障注入差分ＡＸ和密文输出差分ＡＣ使用代数 故障输出差分。 ４．２故障模型 假设在ＰＲＥＳＥＮＴ第３１轮ｓ盒输入注入４ｂｉｔ 故障，则： Ｓ［ａ】（壬》Ｓ［ａ①ｆ】＝ｆ （１） 其中，厂和厂’为Ｓ盒输入和输出差分，ａ为第３１轮 ．．方程组表示，同密码算法代数方程组联立，降低代 数方程组的求解复杂度，加快方程组求解速度。 ３）代数方程组求解 代数方程组的求解问题一直是代数攻击领域 研究的难点，在全轮分组密码中，密钥求解是一 个 查表索引，将ａ，ｆ ０），ｆ’所有候选值代入式 （１），可得满足式（１）的ａ值统计，如表１所示。 表１ ＰＲＥＳＥＮＴ Ｓ盒故障分析效率 Ｎ—Ｐ完全问题，求解复杂度非常高，因此现有代数 攻击仅能对约减轮的分组密码进行安全性分析。随 着旁路信息的引入，代数方程组的求解速度可大大 提高，从而对全轮密码算法实现构成严峻威胁。 目前，求解代数方程组主要包括基于可满足性 问题ｌ７，８１（使用ｚＣｈａｆｆ、Ｍｉｎｉｓａｔ、ＣｒｙｐｔｏＭｉｎｉｓａｔ等解 析器）、基于伪随机优化问题ｌＩ钊（使用ＣＰＬＥＸ、ＳＣＩＰ 解析器）、线性化（直接线性化ＸＬ 】、扩展线性化 ＸＳＬｆＪ州）、基于Ｇｒｏｂｎｅｒ基¨圳等方法。本文采用第１ 种，利用ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器进行密钥求解。 根据表１，对于给定的１对输入和输出差分， 可以获取２～４个ｓ盒索引，２对输入和输出差分即 可以较高概率恢复Ｓ盒索引，结合密文恢复４ｂｉｔ后 期白化密钥 。攻击中，如果每个故障样本经传 ４ ＰＲＥＳＥＮＴ代数故障攻击模型 ４．１符号定义 Ａ 、 、Ｃｆ：分别表示第ｉ轮轮密钥加、Ｓ盒代 播后都能传播到ＰＲＥＳＥＮＴ第３１轮的１６个Ｓ盒（如 图３所示），则就有可能使用２个样本恢复 。 此时，可能的故障传播过程为：在第２９轮Ａ 注入宽度为４的故障（或者在曰 注入故障），使得 Ｂ２９的４个比特全出错，即输出差分为１１１１２（ＯｘＯｆ）， 这４个比特经Ｐ置换可扩散至第３Ｏ轮的４个Ｓ盒 输入，经第３０轮Ｓ盒后，输出差分全为ｌ１１１２（ＯｘＯｆ）， 换、Ｐ置换输出；Ａ 、Ｂ 、Ｃｆ ：分别表示第ｉ轮 轮密钥加、Ｓ盒代换、Ｐ置换故障输出；△Ａ 、ＡＢ 、 △ ：分别表示第ｉ轮轮密钥加、Ｓ盒代换、Ｐ置换 ２９轮 ３Ｏ轮 ３ｌ轮 图３ ＰＲＥＳＥＮＴ故障攻击模型 第８期 吴克辉等：ＰＲＥＳＥＮＴ密码代数故障攻击 ．８９． 再经第３０轮Ｐ置换扩散至第３１轮的１６个ｓ盒， 使得这１６个Ｓ盒输入和输出差分均不为０。表２为 ＰＲＥＳＥＮＴ的部分Ｓ盒差分表，其中输出差分中均 出现Ｏｘｆ，其对应Ｓ盒输入差分一共有０ｘ０６，０ｘ０７， ０ｘ０８，０ｘ０ｆ４种。根据上文分析，如果在Ａ 注入４ｂｉｔ 故障，如果Ｓ盒输入差分为０ｘ０６，０ｘ０７，０ｘ０８，０ｘ０ｆ中任 １６个Ｓ盒输出均不为０，且根据ＰＲＥＳＥＮＴ单比特 Ｓ盒输入差分对应Ｓ输出差分表，输出值均属于集合 ｛０ｘ０３，０ｘ０５，０ｘ０６，０ｘ０７，０ｘ０９，０ｘ０ａ，０ｘ０ｂ，０ｘ０ｃ，０ｘ０ｄ，０ｘ０ｅ， ０ｘ０ｆ｝时，视为理想故障样本，否则剔除该故障样本。 需要说明的是，在故障宽度为４的情况下，如 果在第２９轮Ｐ置换输出到第３ｌ轮输出之间注入宽 意一种，就有可能使得Ｂ２９为０ｘ０ｆ（或者直接在Ｂ２９ 注入差分为０ｘ０ｆ故障），当扩散至第３Ｏ轮４个Ｓ盒时， Ｓ盒输入差分可能为０ｘ０１，０ｘ０２，０ｘ０４，０ｘ０８，而当３Ｏ轮 度为４的故障，由于ＰＲＥＳＥＮＴ的Ｐ置换特性，均 不能使得第３１轮的１６个输出差分全不为０。而如 果在第２９轮前注入宽度为４的故障，经过多轮故 ４个Ｓ盒输入差分均为０ｘ０８时，恰好使得３Ｏ轮的４ 个Ｓ盒输出差分均为０ｘ０ｆ，然后经Ｐ转换传播后，使 得 的１６个Ｓ盒输入出现单比特故障。 综上，文中理想的故障模型为在第２９轮Ａ 注入宽度为４的故障，其故障差分为０ｘ０６，０ｘ０７， ０ｘ０８，０ｘ０ｆ，使得Ｂ２９的４个比特全出错，或者直接 在 注入差分为 ０厂故障。 表２ ＰＲＥＳＥＮＴ差分Ｓ盒（输出差分有ＯｘＯｆ） ４．３故障样本筛选 根据４．２节，理想的故障样本对应的第３１轮 ｌ６个Ｓ盒输入差分应可能为０ｘ０１，０ｘ０２，０ｘ０４，０ｘ０８ 中１种，而第３１轮Ｓ盒输出差分应有ｌ６个非零 值。 在获取到故障密文样本后，首先将密文经逆Ｊｐ 置换得到第３１轮Ｓ盒输出差分△ ，如果△∥ 的 障传播，第３１轮的１６个Ｓ盒输入差分很难满足均 为单比特故障差分。 ５ ＰＲＥＳＥＮＴ代数故障攻击 ５．１ ＰＲＥＳＥＮＴ代数方程组构建 密码代数攻击都可归结于建立和求解有限域 ＧＦ（ ）上系数任意选取的非线性布尔方程组，而建 立分组密码Ｓ盒的超定、稀疏代数方程组一直是代 数攻击研究的难点。本文参考文献［１４１中基于高斯 消元法建立Ｓ盒代数方程组的方法，用９个极端稀 疏的八元二次布尔方程（ＭＱ方程）表示ＰＲＥＳＥＮＴ 的Ｓ盒，用大约８ ０００个未知变元、２０ ０００个ＭＱ 方程来表示ＰＲＥＳＥＮＴ ３ １轮加密。未知变元包括４ 种类型，如表３所示。 表３ 新增变元及说明 变元 说 明 Ｐ 第ｒ轮轮密钥加输入比特 第ｒ轮轮密钥比特 第ｒ轮查Ｓ盒前输入比特 第ｒ轮查Ｓ盒前输出比特 注：（Ｏ≤ｒ＜￣３１，Ｏ≤ｆ乓６３） ＰＲＥＳＥＮＴ加密转化为以下等效布尔方程组： Ｐ ０ ｋｉ ＝ｘｉ （０≤ｒ≤３１，０≤ｉ≤６３） （２） ｓ（ｘ４ ，ｘ４川， ｆ＋２，ｘ４，＋３）： ， ＋ｌ，）， ，ｙ４Ｈ。 （０≤ｒ≤３０，０≤ｔ≤１５） （３） Ｙ ＝Ｐｇ（ｆ） （０≤，．≤３０，０≤ｉ≤６３） （４） 式（２）表示３ｌ轮及白化轮加密过程中与轮密 钥加操作；式（３）表示３ｌ轮加密过程中Ｓ盒代换 操作；式（４）表示３ｌ轮加密过程中Ｐ置换操作， 置换函数ｇ详见文献［１２】。此外，如考虑到轮密钥 扩展，每轮还可增加大约２００个ＭＱ方程。 ・９０・ 通信学报 第３３卷 其中，代换函数Ｓ的输入变元 ｌ，Ｘ２，Ｘ３，Ｘ４和输 出变元Ｙ１，Ｙ２，Ｙ３，ｙ４满足以下Ｓ盒代数方程组：１０ ④Ｘ２ ０ Ｙ２ ０ｘｌＹ１ ０ｘｌＹ３ ０ｘｌＹ４④ｘ４ｙｌ ＝０ Ｘｌ ０Ｘ２ ０ｘ４①Ｙ４①ｘｌＹ２（壬》ＸｚＹｌ④ｘ２Ｙ２ ０ｘｚＹ３① Ｘ２Ｙ４ ０ｘ３Ｙｌ ０ｘ４Ｙ１ ０ ０ ），２①ｘｊｙ３（壬》 ），４ ０Ｘ２Ｙ２（壬》ｘ３Ｙ１ ０ｘ３Ｙ２＝０ ０ ｙ２①ｘｚＹ２（壬》 ３ ０ｘ３Ｙ４（壬》ｘ４Ｙｌ＝０ １④ｘ３④ｘ４ ０ Ｙ１ ０ ｙ２①ＸｌＹ３ ０ Ｘ３Ｙ１（王》Ｘ４Ｙｌ：０ ④ ０ Ｙ３ ０ｘｌＹ３ ０ ），４ ０ｘ２Ｙ１ ０ｘ２Ｙ２④ ２Ｙ４①Ｘ３Ｙ１①Ｘ４Ｙ１：０ ０ ０ ０ｘｌＹ３①ｘｌＹ４ ０ｘ２Ｙ２ ０ｘ２Ｙ３④ ｘ２Ｙ４ ０ ｘ３Ｙ４ ０ ｘ４ｙ２＝０ ④Ｘ１Ｙ３①ｘ２Ｙ１①Ｘ２Ｙ２ ０ｘ２Ｙ３①ｘ２Ｙ４（壬》ｘ４Ｙｌ ０ ｘ４Ｙ３：０ ２①Ｘ４ ０ｘｌＹ２ ０ ｙ３①ｘｌＹ４ ０ｘ２Ｙ３ ０ｘ２Ｙ４① ｘ３Ｙ４ ０ ｘ４ｙｌ①ｘ４ｙ４＝０ ５．２故障信息利用 １）故障位置已知 基于４．２节故障模型，第２９轮ＡＢ 。中只有１个 Ｓ盒输出差分为０ｘ０ｆ，其他为０。假如第 个Ｓ盒输 出差分为ＯｘＯｆ，则可表示为 （５） 其他ｌ５个Ｓ盒输出差分均为０，可表示为 ４ｍ＋３ Ｐｌ（Ｂ ０ Ｂｉ ０１）＝１ ｍＥ【０，１５１，ｍ≠＇『 （６） ｆ＝４ｍ 此外，由于正确和故障密文可直接代入正确和 故障样本的等效代数方程组，相当于密文差分的间 接代入，故无需再建立关于密文差分的代数方程。 ２）故障位置未知 基于４．２节故障模型，第２９轮ＡＢ２９中只有１个 ｓ盒输出差分为ＯｘＯｆ，非０差分对应的位置有１６种 可能。每种可能位置的故障差分表示为（Ｂ ｒ 表示 第，种可能的故障位置情况下第，．轮Ｓ盒代换的故 障输出）： ４ｍ＋３ ｎ（ ０ Ｂ ｒ，：０１） ｍ， ∈【０，１５］ （７） ｉ＝４ｍ 由于只有１种可能位置的故障差分对应的代数 方程组成立，即ｌ６个变量 ｆ中只有１个为１，其余 为０，因此集合 ， ２，ｆ１３，… ）的汉明重为１，即满 足函数： ＨＷ ｌ， ２， ３，…，ｆｌｓ）＝ｌ （８） 其中，汉明重函数ＨＷ如下： 对于１个１６ｂｉｔ的集合ｘ： ， ，…， ，ｘｍ）， 共有１７种可能的汉明重ＨＷ（Ｘ）（０≤ＨＷ（ ≤１６）， 可以分别用一个５ｂｉｔ的变量ｙ＿（ｙ１，Ｙ２，Ｙ３，Ｙ４，Ｙ５）表示。 ｘ、ｙ满足以下方程（其中，１≤ｉ≤』≤ｍ≤ｎ≤Ｐ≤ ｎ 目≤ ≤ｔ≤１６）： １６ ０ Ｙ ＝ｎ ＝ ｌ２ ８７０ Ｙ２＝∑ａｔｘｉｘＪＸｎ￣ＸｎＸｐＸｑＸｓＸｔ １＝１ １ ８２０ Ｙ ＝∑ａｔｘｉｘ，ＸｍＸｎ （９） ｔ＝ｌ １２０ Ｙ ＝∑ ｔ＝ｌ １６ Ｙ ＝∑ ５．３实验结果及比较 在普通ＰＣ机（ＣＰＵ为Ａｔｈｌｏｎ６４ ３０００＋１．８１ＧＨｚ， 内存为１ＧＢ）上，利用Ｃ＋＋语言、ＣｒｙｐｔｏＭｉｎｉＳＡＴ 软件实现了ＰＲＥＳＥＮＴ代数故障攻击仿真实验，攻 击流程如图４所示。 图４ ＰＲＥＳＥＮＴ代数故障攻击流程 下面给出某次ＰＲＥＳＥＮＴ代数故障攻击的过程。 １）产生１个随机明文Ｐ＝２３２Ｆ２Ｂ９８Ｃ１５１Ｅ ＡＢ５ｌ６，密钥Ｋ＝７ＦＢ５３１４２１Ｃ９Ｅ０２３１６０Ｂ２ 后期白 化密钥为６２ＤＥｌ９Ａ３Ｂ６４ＡＤ６Ｅ８ 此时正确密文 为：Ｅ５Ｂ３１３６ＦＤ４３２ＥＤ２Ｅ１６；然后设定攻击样本量， 在ＰＲＥＳＥＮＴ加密第２９轮注入４ ｂｉｔ随机故障。 第８期 吴克辉等：ＰＲＥＳＥＮＴ密码代数故障攻击 ・９ｌ・ ２）按照４．３节方法筛选有效故障样本，如第１ 个有效故障密文ｃ ＝４３３７１Ｄ６２８Ｂ８７２９２７ 第２ 个有效故障密文Ｃ；ｌ； ＝Ｅ８２４３５Ｂ１３９Ｆ６Ｃ６９７１６ｏ ３）参考５．１节方法构建３个样本（１个正确样 本，２个故障样本）的ＰＲＥＳＥＮＴ最后３轮代数方 程组；参考５．２节方法将故障注入差分、密文差分 转化为额外代数方程组。 ４）将密码算法和故障信息代数方程组转化为 ＳＡＴ子句，利用ＣｒｙｐｔｏＭｉｎｉＳＡ解析器求解密钥。 实验中２对ＰＲＥＳＥＮＴ正确一故障样本３轮的代数方 程组大约转化为７８ ０００个ＳＡＴ子句。解析器密钥 求解结果如表４所示。 表４ ＰＲＥＳＥＮＴ代数故障攻击结果 编号 编号 编号 。 编号 －８３４ ０ －８５０ ０ ８６６ １ ８８２ １ ８３５ ｌ －８５１ Ｏ －８６７ ０ ８８３ ｌ ８３６ １ －８５２ ０ ８６８ １ －８８４ ０ ８３７ ０ ８５３ １ ｓ／垦茁琏＊ ８６９ １ ８８５ １ －８３８ ０ ８５４ 如 ∞ １ ∞ －８７０ 加 ０ －８８６ ０ －８３９ ０ －８５５ ０ ８７１ １ ８８７ １ ８４０ ｌ －８５６ ０ ８７２ ｌ ８８８ １ －８４１ ０ ８５７ １ －８７３ ０ —８８９ ０ ８４２ １ ８５８ ｌ －８７４ ０ ８９０ １ ８４３ １ －８５９ ０ ８７５ １ ８９１ １ —８４４ ０ ８６０ １ －８７６ ０ ８９２ １ ８４５ １ －８６１ ０ －８７７ ０ －８９３ ０ ８４６ １ －８６２ ０ ８７８ １ ８９４ １ ８４７ １ －８６３ ０ －８７９ ０ －８９５ ０ ８４８ １ ８６４ １ ８８０ １ －８９６ ０ －８４９ ０ ８６５ １ －８８１ ０ －８９７ ０ 如表４所示，编号８３４至８９７依次表示６４ｂｉｔ 的后期白化密钥比特值，如果编号为正，表示对应 密钥位为１，否则为０。根据表４，求解的后期白化 密钥为０１１０００１０１１０１１１１００００１１００１１０１０００１１１０１１０ １ １００１００１０１０１ １０１０１ １０１ １ １０１０００２，即６２ＤＥ１９Ａ３Ｂ６４ ＡＤ６Ｅ８ 同真实密钥一致，攻击成功；且故障 已知时，耗时１６．３５ｓ，故障位置未知时，耗时 ３１．５８ｓ。 图５表示在ＰＲＥＳＥＮＴ密码第２９轮注入４ｂｉｔ 故障，成功恢复 条件下，不同样本量对应的 ＣｒｙｐｔｏＭｉｎｉＳＡＴ求解平均时间。可见最少仅需２ 对正确一故障样本即可将ＰＲＥＳＥＮＴ－８０密钥搜索 空间降低为２ ，且样本量同求解时间成正比；另 外较之故障位置已知，故障位置未知条件下代数 方程组复杂度稍高，导致ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器 求解时间稍长。 图５不同样本量下ＣｒｙｐｔｏＭｉｎｉＳＡＴ求解平均时间 实验结果同国内外ＰＲＥＳＥＮＴ故障攻击比较 如表５所示。可见，本文的攻击方案在故障样本 量方面优势明显，攻击可行性较强，而且可利用 解析器自动恢复密钥，具有一定的优越性。由于 代数分析在分组密码领域的通用性，本文的分析 方法可以扩展至其他分组密码的故障攻击，从而 成为从故障攻击角度，评估分组密码实现安全性 的通用手段之一。 表５实验结果同国内外ＰＲＥＳＥＮＴ故障攻击比较 ６结束语 本文将代数攻击和故障攻击相结合，对代数故 障攻击进行了研究。给出了代数故障攻击模型，以 ＰＲＥＳＥＮＴ轻型分组密码为例进行了攻击应用；首 先建立了ＰＲＥＳＥＮＴ故障攻击模型，然后给出了故 障样本筛选、ＰＲＥＳＥＮＴ密码代数方程组构建、故 障信息利用方法，最后通过仿真实验验证了攻击方 法的可行性。 结果表明：应用文中故障模型，理想情况下， ２次故障注入，使用ＣｒｙｐｔｏＭｉｎｉＳＡＴ解析器进行 方程组求解，即可恢复ＰＲＥＳＥＮＴ．８０的６４ｂｉｔ后期 白化密钥，耗时不超过５０ｓ；同现有攻击相比， ・９２・ 通信学报 第３３卷 文中提出故障模型所需的故障注入次数较小，给 出的密文筛选方案明确，而且可使用解析器自动 进行密钥求解，具有一定的优越性；此外，文中 方法可为其他分组密码故障攻击提供一定的借鉴 和参考。 参考文献： Ｉ１】 ＤＯＮＥＨ Ｄ，ＤＥＭＩＬＬＯ Ｒ．ＬＩＰＴＯＮ Ｒ．Ｏｎ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｃｈｅｃｋｉｎｇ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｆａｕｌｔｓ［Ａ］Ｅｕｒｏｃｒｙｐｔ’９７［Ｃ］．Ｋｏｎｓｔｎａｚ， Ｇｅｒｍａｎｙ．１９９７．３７—５ １ ［２］ ＢＩＨＡＭ Ｅ，ＳＨＡＭＩＲ Ａ Ｄｉｆｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｆ ｓｅｃｒｅｔ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍｓ［Ａ］．Ｃｒｙｐｔｏ’９７［Ｃ］．Ｓａｎｔａ Ｂａｒｂａｒａ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ， １９９７．５１３—５２５ ［３］ ＤＥＢＤＥＥＰ Ｍ．Ａｎ ｉｍｐｒｏｖｅｄ ｆａｕｌｔ ｂａｓｅｄ ａｔｔａｃｋ ｏｆ ｔｈｅ ａｄｖａｎｃｅｄ ｅｎ— ｃｒｙｐｔｉｏｎ ｓｔｎａｄａｒｄ［Ａ］．ＡＦＲＩＣＡＣＲＹＰＴ ２００９［Ｃ］．Ｇａｍｍａｒｈ，Ｔｕｎｉｓｉａ， ２Ｏ０９．４２１—４３４． 【４］ ＺＨＡＯ Ｘ Ｊ，ＷＡＮＧ Ｆｕｒｔｈｅｒ ｉｍｐｒｏｖｅｄ ｄｉｆｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｎ ｃａｍｅｌｌｉａ ｂｙ ｅｘｐｌｏｒｉｎｇ ｆａｕｌｔ ｗｉｄｔｈ ａｎｄ ｄｅｐｔｈ［ＥＢ／ＯＬ］ｈｔ【ｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ ｏｒｇ／２０１０／０２６．ｐｄｆ，２０１０ ［５Ｊ Ｌ１ ＧＵＤ ＬＩ ＪＲ．Ｄｉｆｆｅｒｅｎｔｉａｌｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｎｔｈｅＡＲＩＡａｌｇｏ— ｒｉｔｈｍ［Ｊ］Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ，２００８，１７８（１９）：３７２７—３７３７． ［６］ ＮＩＣＯＬＡＳ Ｔ Ｃ．ＪＯＳＥＦ Ｐ．Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ｂｌｏｃｋ ｃｉｐｈｅｒｓ ｗｉｔｈ ｏｖｅｒ－ ｄｅｆｉｎｅｄ ｓｙｓｔｅｍｓ ｏｆ ｅｑｕａｔｉｏｎｓ［Ａ］ＡＳＩＡＣＲＹＰＴ ２００２［Ｃ］Ｂｅｒｌｉｎ Ｈｅｉ— ｄｅｌｂｅｒｇ，２００２ ２６７—２８７ ［７】 ＭＡＴＨＩＥＵ Ｒ，ＦＲＡＮＣＯＩＳ—Ｘ Ｓ Ａｌｇｅｂｒａｉｃ ｓｉｄｅ—ｃｈａｎｎｅｌ ａｔｔａｃｋｓ［Ａ］ ＩＮＳＣＲＹＰＴ ２００９［Ｃ］．Ｃａｌｉｆｏｒｎｉａ．ＵＳＡ．２００９ ３９３—４１０ ［８］ ＭＡＴＨＩＥＵ Ｒ，ＦＲＡＮＣＯＩＳ—Ｘ，ＮＩＣＯＬＡＳ Ｖ－Ｃ Ａｌｇｅｂｒｉａｃ ｓｉｄｅ—ｃｈａｎｎｅｌ ａｔｔａｃｋｓ ｏｎ ｔｈｅ ＡＥＳ：Ｗｈｙ ｔｉｍｅ ａｌｓｏ ｍａｔｔｅｒｓ ｉｎ ＤＰＡ［Ａ］．ＣＨＥＳ ２００９［Ｃ】 Ｃａｌｉｆｏｒｎｉａ ＵＳＡ．２００９．９７—１１１． ［９］ 李卷孺，谷大武．ＰＲＥＳＥＮＴ算法的差分故障攻击［Ａ］．中国密码学 会２００９年会［ｃ］．中国，北京，２００９．３－１３ ＬＩ Ｊ Ｒ，ＧＵ Ｄ、 Ｄｉｆｆｅｒｅｎｔｉａｌ ｆａｕｌｔ ａｎａｌｙｓｉｓ ｏｎ ＰＲＥＳＥＮＴ［Ａ】．ＣＨＩ・ ＮＡＣＲＹＰＴ ２００９［Ｃ１ Ｂｅｉｊｉｎｇ，Ｃｈｉｎａ，２００９．３－１３． 【１０１ ＺＨＡＯ Ｘ Ｊ．ＷＡＮＧ Ｔ Ｆａｕｌｔ ｐｒｏｐａｇａｔｅ ｐａｔｔｅｒｎ ｂａｓｅｄ ＤＦＡ ｏｎ ＳＰＮ ｓｔｒｕｃｔｕｒｅ ｂｌｏｃｋ ｃｉｐｈｅｒｓ ｕｓｉｎｇ ｂｉｔｗｉｓｅ ｐｅｒｍｕｔａｔｉｏｎ．ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ＰＲＥＳＥＮＴ ａｎｄ ＰＲＩＮＴｃｉｐｈｅｒ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１１／０８９． ｐｄｆ，２０１１． ＷＡＮＧＧＬ，ＷＡＮＧ Ｓ Ｓ Ｄｉｆｆｅｒｅｎｔｉｌａｆａｕｌｔａｎａｌｙｓｉｓ ｏｎ ＰＲＥＳＥＮＴｋｅｙ ｓｃｈｅｄｕｌｅ［Ａ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ Ｓｅｃｕｒｉｔｙ（ＣＩＳ ２０１０）［Ｃ１．２０１０．３６２—３６６． ［１２］ ＢＯＧＤＡＮＯＶ Ａ．ＫＮＵＤＳＥＮ Ｌ Ｒ，ＬＥＡＮＤＥＲ， 日ｆ．ＰＲＥＳＥＮＴ：ａｎ ｕｌｔｒａ—ｌｉｇｈｔｗｅｉｇｈｔ ｂｌｏｃｋ ｃｉｐｈｅｒｉＡ］．ＣＨＥＳ ２００７［Ｃ］．Ｖｉｅｎｎａ，Ａｕｓｔｒｉａ， ２００７ ４５０．４６６ ［１３ Ｊ 李伟博，解永宏，胡磊分组密码ｓ盒的代数方程［Ｊ１．中国科学院研究 生学报，２００８，２５（４）：５２４ ５２９． ＬＩ Ｗ Ｂ．ＸＩＥ Ｙ Ｈ．ＨＵ Ｌ．Ａｌｇｅｂｒａｉｃ ｅｑｕａｔｉｏｎｓ ｏｆ ｓｂｏｘ ｂｌｏｃｋ ｃｉｐｈｅｒ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ｇｒａｄｕａｔｅ Ｓｃｈｏｏｌ ｏｆ ｔｈｅ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ， ２００８，２５（４）：５２４—５２９． ［１４］ ＡＬＥＸ Ｂ．ＣＨＲＩＳＴＯＰＨＥ Ｄ Ｃ．Ｂｌｏｃｋ ｃｉｐｈｅｒｓ ａｎｄ ｓｙｓｔｅｍｓ ｏｆ ｑｕａｄｒａｔｉｃ ｅｑｕａｔｉｏｎｓ［Ａ］ＦＳＥ ２００３［Ｃ］２００３．２７４—２８９． ［１５］ ＧＩＲＡＵＤ Ｃ，ＴＨＩＥＢＥＡＵＬＤ Ｈ．Ａ ｓｕｒｖｅｙ ｏｎ ｆａｕｌｔ ａｔｔａｃｋｓ［Ａ］Ｉｎｔｅｒｎａ— ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｍａｒｔ Ｃａｒｄ Ｒｅｓｅａｒｃｈ ｎａｄ Ａｄｖａｎｃｅｄ Ａｐｐｌｉｃａｔｉｏｎｓ （ＣＡＲＤＩＳ’ｏ４）［Ｃ】Ｔｏｕｌｏｕｓｅ，Ｆｒａｎｃｅ，２００４．２２—２７ 【１６］ ＹＯＳＳＥＤ Ｏ，ＭＡＲＩＯ Ｋ，ＴＨＯＭＡＳ ｅｔ ａ１．Ｓｉｄｅ—ｃｈａｎｎｅｌ ａｎａｌｙｓｉｓ ｉｎ ｔｈｅ ｐｒｅｓｅｎｃｅ ｏｆ ｅｒｒｏｒｓ［Ａ］ＣＨＥＳ ２０１０［Ｃ］．Ｓａｎｔａ Ｂａｒｖａｒａ，Ｃａｌｉｆｏｒｎｉａ， ２０１０．４２８—４４２． 【１７】 ＣＯＵＲＴＯＩＳ Ｎ Ｔ，ＫＬＩＭＯＶ Ａ，ＰＡＲＡＲＩＮ Ｊ．Ｅｆｉｆｃｉｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｏｌｖｉｎｇ ｏｖｅｒｄｅｆｍｄ ｓｙｓｔｅｍｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｐｏｌｙｎｏｍｉｌａ ｅｑｕａｔｉｔｏｎ［ＥＢ／ＯＬ］． ｈｔｔｐ：／］ｗｗｗ．ｉａｃｒ．ｏｒｇ／ｒａｃｈｉｖｅ／ｅｎｒｏｃｒｙｐｔ２０００／１８０７／１８０７０３９８一ｎｅｗ／ｐｄｆ，２０００ ［１８１ ＫＩＰＮＩＳ Ａ，ＳＨＡＭＩＲ Ａ．Ｃｒｙｐｔａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ＨＦＥ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏ— ｓｙｓｔｅｍ ｂｙ ｒｅｌｉｎｅａｒｉｚａｔｉｏｎ［Ａ］．Ｃｒｙｔｏ９９［Ｃ］，Ｓａｎｔａ Ｂ￣ｂａｒａ，Ｃａｌｉｆｏｒｎｉａ， ＵＳＡ．１９９９ １９—３０ ［１９］ＳＥＧＥＲ Ａ Ｊ Ｍ．Ａｌｇｅｒｉａｃ ａｔｔａｃｋｓ ｆｒｏｍ ａ Ｇｒｏｂｎｅｒ ｂａｓｉｓ ｐｅｒｓｐｅｃ ｔｉｖｅｓ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ ｗｉｎ．ｔｒｕｅ．ｎｌ／ ２（ｘ）４ 作者简介 吴克辉（１９８６一），男，甘肃景泰人， 军械工程学院硕士生，主要研究方向为分 组密码旁路分析。 赵新杰（１９８６一），男，河南开封人， 军械工程学院博士生，主要研究方向为分 组密码旁路分析和故障分析。 王韬（１９６４一），男，河北石家庄人， 博士，军械工程学院教授、博士生导师， 主要研究方向为信息安全和密码学。 郭世泽（１９６９一），男，河北石家庄人，博士，北方电 子设备研究所研究员、博士生导师，主要研究方向为信息安 全和密码学。 刘会英（１９８４一），男，湖北黄石人，军械工程学院博 士生，主要研究方向为图像加密和密码旁路分析。
发布评论