信息安全技术丛书：密码旁路分析原理与方法

《信息安全技术丛书：密码旁路分析原理与方法》较为全面地介绍了密码旁路分析的基本原理和方法，以帮助读者系统地掌握典型密码旁路分析的研究现状、数学基础、基本原理、分析方法和应用实例，为深入理解其技术内涵和开展相关领域研究奠定基础。
《信息安全技术丛书：密码旁路分析原理与方法》共包括9章和附录。第1章概要介绍密码学的相关知识和密码旁路分析的研究现状。第2章和第3章分别介绍密码旁路分析的数学基础、旁路泄露与旁路分析建模。第4~7章分别阐述计时分析、功耗/电磁分析、Cache分析、差分故障分析4种经典的密码旁路分析原理与方法。第8章和第9章分别描述代数旁路分析、旁路立方体分析两种传统数学分析和经典旁路分析的组合分析方法。附录给出《信息安全技术丛书：密码旁路分析原理与方法》涉及的典型密码算法设计规范。

前言
缩略词表
第1章 绪论
1.1 密码学基础
1.1.1 密码编码学
1.1.2 传统密码分析学
1.2 密码旁路分析概述
1.2.1 发展历程
1.2.2 基本原理
1.2.3 发展动因
1.2.4 方法分类
1.2.5 威胁分析
1.2.6 研究热点
1.3 本书的章节安排

第2章 数学基础
2.1 代数学
2.1.1 数论
2.1.2 代数
2.2 信息论
2.2.1 信息和熵
2.2.2 互信息
2.3 计算复杂性
2.3.1 算法与问题
2.3.2 算法的计算复杂性
2.3.3 问题的计算复杂性
2.4 概率论
2.4.1 事件与概率
2.4.2 期望与方差
2.4.3 概率分布
2.4.4 中心极限定理
2.5 数理统计
2.5.1 参数估计
2.5.2 假设检验
2.6 注记与补充阅读

第3章 旁路泄露与旁路分析建模
3.1 密码算法设计与实现
3.1.1 密码设计
3.1.2 密码实现
3.2 旁路泄露
3.2.1 泄露特性
3.2.2 泄露分类
3.2.3 泄露模型
3.3 泄露分析策略
3.4 旁路分析建模
3.4.1 术语与定义
3.4.2 分析框架
3.4.3 分析模型
3.4.4 评估模型
3.5 注记与补充阅读

第4章 计时分析
4.1 时间泄露
4.1.1 泄露来源
4.1.2 采集方法
4.1.3 预处理方法
4.2 计时分析原理
4.3 模幂运算计时分析
4.3.1 模幂运算时间差异
4.3.2 计时信息分析方法
4.3.3 RSA计时攻击实例
4.4 乘法运算计时分析
4.4.1 乘法运算时间差异
4.4.2 计时信息分析方法
4.4.3 AES计时攻击实例
4.5 注记与补充阅读

第5章 功耗/电磁分析
5.1 功耗/电磁泄露
5.1.1 泄露机理
5.1.2 泄露采集
5.1.3 泄露模型
5.1.4 统计特性
5.2 旁路信号预处理方法
5.2.1 信号对齐方法
5.2.2 有效点选取方法
5.3 基于功耗/电磁旁路信号的密钥恢复问题描述
5.4 简单分析
5.4.1 简单功耗分析方法
5.4.2 RSA简单分析攻击实例
5.5 相关性分析
5.5.1 相关性分析方法
5.5.2 相关性系数计算方法
5.5.3 DES相关性分析攻击实例
5.6 模板分析
5.6.1 模板分析方法
5.6.2 常用判别分析方法
5.6.3 RC4模板分析攻击实例
5.7 注记与补充阅读

第6章 Cache分析
6.1 Cache访问泄露
6.1.1 Cache工作原理
6.1.2 Cache命中与失效
6.1.3 命中与失效泄露分析
6.1.4 Cache命中与失效采集
6.2 时序驱动Cache分析
6.2.1 基本原理
6.2.2 Cache碰撞计时分析方法
6.2.3 Cache计时模板分析方法
6.2.4 AES时序驱动攻击实例
6.3 访问驱动Cache分析
6.3.1 基本原理
6.3.2 查找表在Cache中分布分析
6.3.3 查找表在Cache中地址定位方法
6.3.4 Cache访问地址分析方法
6.3.5 AES访问驱动攻击实例
6.4 踪迹驱动Cache分析
6.4.1 基本原理
6.4.2 基于Cache命中与失效踪迹的分组密码密钥分析方法
6.4.3 基于平方和乘法踪迹的公钥密码幂指数分析方法
6.4.4 AES踪迹驱动攻击实例
6.4.5 RSA踪迹驱动攻击实例
6.5 注记与补充阅读

第7章 差分故障分析
7.1 密码运行故障
7.1.1 故障注入
7.1.2 故障模型
7.2 故障分析原理
7.3 通用的差分故障分析方法
7.4 分组密码差分故障分析方法与攻击实例
7.4.1 按块扩散SPN结构分组密码分析
7.4.2 按位扩散SPN结构分组密码分析
7.4.3 平衡Feistel结构分组密码分析
7.5 公钥密码差分故障分析方法与攻击实例
7.5.1 基于操作步骤故障的RSA密码分析
7.5.2 基于参数故障的RSA密码分析
7.5.3 基于乘法器故障的RSA密码分析
7.5.4 基于符号变换故障的ECC密码分析
7.6 注记与补充阅读

第8章 代数旁路分析
8.1 基本原理
8.1.1 代数分析
8.1.2 代数旁路分析原理
8.2 多推断代数旁路分析方法
8.2.1 问题提出
8.2.2 符号与定义
8.2.3 多推断代数旁路分析
8.2.4 开销分析
8.2.5 适用性分析
8.3 AES汉明重量代数功耗攻击实例
8.3.1 汉明重量推断与表示
8.3.2 数据复杂度评估方法
8.3.3 实验结果与分析
8.4 AES访问驱动代数Cache攻击实例
8.4.1 两种泄露模型
8.4.2 密码访问Cache地址推断与表示
8.4.3 数据复杂度评估方法
8.4.4 实验结果与分析
8.5 AES踪迹驱动代数Cache攻击实例
8.5.1 密码Cache访问事件序列推断与表示
8.5.2 数据复杂度评估方法
8.5.3 实验结果与分析
8.6 多种密码代数故障攻击实例
8.6.1 故障方程构建方法
8.6.2 密码攻击实例
8.6.3 其他应用
8.7 注记与补充阅读

第9章 旁路立方体分析
9.1 基本原理
9.1.1 立方体分析
9.1.2 旁路立方体分析
9.2 扩展的旁路立方体分析方法
9.2.1 非线性旁路立方体分析
9.2.2 分而治之旁路立方体分析
9.2.3 迭代旁路立方体分析
9.2.4 黑盒旁路立方体分析
9.3 密码旁路立方体攻击实例
9.3.1 单比特泄露模型分析
9.3.2 汉明重量泄露模型分析
9.3.3 汉明重量泄露模型攻击实验
9.4 注记与补充阅读

附录
附录A RSA公钥密码算法设计
附录B ECC公钥密码算法设计
附录C AES分组密码算法设计
附录D DES分组密码算法设计
附录E Camellia分组密码算法设计
附录F PRESENT分组密码算法设计
附录G EPCBC分组密码算法设计
附录H LED分组密码算法设计
附录I Piccolo分组密码算法设计
附录J GOST分组密码算法设计
附录K RC4序列密码算法设计
附录L Helix序列密码算法设计
参考文献
索引

《信息安全技术丛书：密码旁路分析原理与方法》：
第1章 绪论
随着计算机和通信技术的发展，人类社会在经历了机械化时代和电气化时代后，已经进入一个崭新的信息化时代。信息的获取、存储、传输、处理和安全保障能力已成为一个国家综合实力的重要组成部分。信息安全已成为影响国家安全、社会稳定和经济发展的重要因素之一，也是人们在信息化时代中生存与发展的重要保证。著名未来学家阿尔夫·托夫勒曾说过：“在信息化时代，谁掌握了信息，控制了网络，谁就将拥有整个世界。”[1]作为信息安全技术的核心，密码学在最近二十多年来越来越受到人们的重视。
密码学主要包括两个分支：密码编码学和密码分析学。密码编码学主要研究对信息进行变换的密码算法，以保护信息在传递过程中不被敌方窃取、解读和利用；而密码分析学则与密码编码学相反，主要研究如何分析和破解密码算法或密钥，达到信息窃取、解读和利用等目的。两者之间既相互对立又相互促进，一方面，针对已有的密码分析手段，密码编码者总希望设计出可以抵抗所有已知分析方法的密码算法，各种深思熟虑的设计给密码算法分析提出了严峻的挑战；另一方面，针对已有的密码算法，密码分析者总希望可以找到密码算法的某些安全缺陷，密码分析方法的发展为密码算法的设计提供了源源不断的动力和新鲜思想。这两方面的研究共同推动了密码学的发展。本书主要面向密码分析学。
传统密码分析学[2-5]主要关注密码算法的设计安全性，通过分析密码算法的输入和输出，利用强力攻击、数学分析等方法进行密码分析。随着密码编码水平的不断提高，应用传统密码分析学方法对密码算法分析的计算复杂度越来越高，已经难以对其实际安全性构成现实威胁。近年来，有研究者提出[6]，密码算法在设备（密码芯片①）上的实现安全性（或物理安全性）并不等价于密码算法设计方面的理论安全性，其实现过程中会产生执行时间、功率消耗、电磁辐射、故障输出等信息泄露，称为旁路泄露（side channel leakage）。密码分析者可利用旁路泄露结合密码算法的输入、输出和设计细节进行密码分析，此类方法称为旁路攻击（Side Channel Attack）或旁路分析（Side Channel Analysis，SCA）②，又称为“侧信道分析”[7]，本书主要沿用旁路分析的称谓。当前，旁路分析已对各类密码算法在设备上的实现安全性构成现实威胁[8]，本书主要研究密码旁路分析的原理与方法。
1.1 密码学基础
1.1.1 密码编码学
密码技术是一门古老的技术，自人类社会出现战争以来即产生了密码。密码技术的基本思想是隐藏秘密信息，隐藏就是对数据进行一种可逆的数学变换。隐藏前的数据称为明文，隐藏后的数据称为密文，隐藏的过程称为加密，根据密文恢复明文的过程称为解密。加解密一般要在密钥的控制下进行，将数据以密文的形式在计算机和网络中进行存储或者传输，而且只给合法用户分配密钥。这样，即使密文被非法窃取，攻击者由于未授权得到密钥从而不能得到明文，达到提供数据机密性的目的。同样，未授权者没有密钥无法构造相应的明密文，如果对数据进行删减或者篡改，则必然被发现，进而达到提供数据完整性和真实性的目的。
1．通信环境下的密码系统
首先给出通信环境下的密码系统相关术语。
术语1-1 发送者
指在双方通信中作为信息合法传送者的实体，通常用Alice表示。
术语1-2 接收者
指在双方通信中作为信息预定接收者的实体，通常用Bob表示。
术语1-3 攻击者
指既非发送者又非接收者的实体，可以是通信系统中的合法用户或非法用户，试图攻击保证发送者和接收者信息安全的服务，通常用Eve表示。
术语1-4 明文
指原始的需要为发送者和接收者所共享而不为攻击者所知的信息，通常用P表示。
术语1-5 密文
指加密后的消息，提供给接收者，也可能为攻击者所知，通常用C表示。
术语1-6 密钥
指一种参数，是在明文转换为密文或将密文转换为明文的算法中输入的数据。密钥分为加密密钥和解密密钥，通常分别用和来表示。
术语1-7 加密
指将明文使用密钥转换到密文的一种映射，通常用表示。
术语1-8 解密
指将密文使用密钥转换到明文的一种映射，是加密的反过程，通常用 表示。
理想通信环境下的密码系统模型如图1-1所示，主要由明文、密文、密钥（包括加密密钥和解密密钥）、加密算法、解密算法五元组构成。发送者将明文、加密密钥作为加密算法的输入得到密文并发送给接收者，接收者解密密文后得到明文。
图1-1体现了理想通信环境下的密码系统安全性确保假设，攻击者只能截获公开信道上传输的消息，结合密码算法设计进行密钥分析，这也是传统密码分析学方法的共性假设前提。
2．密码学发展历程
在战争年代，密码技术主要用于传递情报和指挥作战。在和平时期，尤其是人类进入信息社会的今天，密码技术已渗透到人们生活的方方面面，常用于提供机密性的信息，即保护传输和存储的信息。除此之外，密码技术还可用于消息签名、身份认证、系统控制、信息来源确认，以提供信息的完整性、真实性、可控性和不可否认性，是构建安全信息系统的核心基础。密码学的发展经历了由简单到复杂，由古典到近代的发展历程。纵观密码学发展历史，可将其发展历程主要归纳为以下4个阶段[9]。
（1）科学密码学的前夜发展时期。从古代到1948年，这一时期的密码技术可以说是一种艺术，而不是一种科学，密码学专家常凭直觉和信念来进行密码设计和分析，而不是推理和证明。在远古时代，加密主要通过手工方法来完成，典型加密方法包括公元前5世纪古希腊战争中斯巴达人的换位密码算法、公元前1世纪高卢战争中凯撒人的单字母替代密码算法、公元16世纪晚期法国的多表加密替代密码算法等。在近代，加密逐渐转向机械方法，如第二次世界大战时期美国发明的Sigaba密码机、英国发明的Typex密码机、德国发明的Enigma密码机、瑞典发明的Hagelin密码机、日本发明的九七式密码机等。
（2）对称密码学的早期发展时期。从1949年到1975年，这一时期的最具代表性工作是Shannon于1949年发表的论文《保密系统的通信理论》[10]，该文对信息源、密钥、加解密和密码分析进行了数学分析，用“不确定性”和“唯一解距离”来度量密码体制的安全性，阐明了“密码体制、完美保密、纯密码、理论保密和实际保密”等重要概念，使密码编码置于坚实的数学基础上，为对称密码学建立了理论基础，标志着密码学作为一门独立学科的形成，从此密码学成为一门科学。
然而对于对称密码算法，通信双方必须约定使用相同的密钥，而密钥的分配只能通过专用的安全途径，如派专门信使等。对于一个具有n个用户的计算机网络，如果使用对称密码确保任意两个用户都可进行保密通信，则共需 种不同的密钥进行管理。当n较大时，密钥管理的开销是十分惊人的，密钥管理的难度也随着密钥的经常产生、分配、更换变得越发困难。因此，对称密码在密钥分配上的困难成为其在计算机网络中广泛应用的主要障碍。
（3）现代密码学的发展时期。从1976年到1996年，这一时期密码学得到了快速发展，最有影响的两个大事件的发生标志着现代密码学的诞生。这一时期密码学无论从深度还是从广度上都得到了空前的发展。
一是Diffie和Hellman于1976年发表了论文《密码编码学新方向》[11]，提出了公钥密码的概念，引发了密码学上的一场革命，他们首次证明了在发送者和接收者之间无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元。公钥密码算法从根本上克服了对称密码算法在密钥分配上的困难，特别适合计算机网络应用，而且容易实现数字签名。在计算机网络中将公钥密码算法和对称密码算法相结合已经成为网络加密的主要形式，目前国际上应用广泛的公钥密码算法主要有：基于大整数因子分解困难性的RSA密码算法[12]、基于有限域上离散对数问题困难性的ELGamal密码算法[13]和基于椭圆曲线离散对数问题困难性的椭圆曲线密码算法（Eliptic Curves Cryptography，ECC）[14]。
……