Authentication 身份认证：Admission and Access Control

Admission Control 准入控制：只与授权的对象通信

Access Control 访问控制：只能在授权的对象上执行操作

密码散列函数（Cryptographic Hash Function/哈希函数）

单向函数

对于单向函数f：

• 计算f(x) = y很容易
• 而计算f^{-1}(y) = x很难

密码散列函数是单向函数。

密码散列函数的属性

碰撞抗性 Collision resistance

很难找到一对x和y，使得h(y) = h(x)且y \not = x。

即无法从计算角度找到任何两个哈希值都相同的独特输入。

原像抗性 Preimage resistance

在集合论中，给定一个从集合X到集合Y的映射，x属于定义域X，y属于值域Y：

• x在该映射下有f(x)=y，则y称为x在该映射下的像
• x称为y的原像

此处原像指散列函数的输入。

因此原像抗性指：给定散列函数的输出y，从计算角度无法找到符合该输出的输入值x，即无法计算f^{-1}(y) = x。

第二原像抗性/弱碰撞抗性 Second-preimage resistance/Weak collision resistance

第二原像指另一个输入x’，使h(x') = h(x)，且x' \not = x。

因此第二原像抗性（或称之为弱碰撞抗性）指：给定x和散列函数h，从计算角度无法找到任何与x有着相同输出的二次输入值x’。

（强）碰撞抗性与弱碰撞抗性

强碰撞抗性（Collision resistance）与弱碰撞抗性（Weak collision resistance）——也即第二原像抗性的区别在于：强碰撞中攻击者需要找到任意两个原像，使散列结果相同；而弱碰撞中给定了一个原像，攻击者只需要找到另一个能使得散列结果相同的原像（第二原像）即可。我们可以将弱碰撞抗性理解为强碰撞抗性的一个特例，因为其中一个原像是给定的。
Collision resistance is stronger notion than preimage and second preimage resistance. Collision resistance always implies property second preimage resistance but does not imply preimage resistance.

因此，强碰撞抗性包含弱碰撞抗性。但强碰撞抗性不能保证原像抗性。

违反强碰撞抗性比违反弱碰撞抗性更容易（要求越高越容易被违反…有点绕）。一个直观的例子是生日悖论，从一群人中找出任意两个生日相同的人的概率大于从中找出和自己生日相同的人的概率。
Collision resistance is easy to breach, so most cryptanalysis target collision attack.

碰撞抗性与原像抗性

散列函数通常被设计为具有碰撞抗性和原像抗性的。 在实践中，由于较低的复杂性，碰撞攻击通常首先出现。 例如，MD5的碰撞理论上是在1996年构建的，2004年实现；而第一个复杂度为2^123的原像攻击出现在2009年，此后并没有太大改进。MD5可以被认为是抗原像的，但当时还不是抗碰撞的。

密码散列函数的例子

• MD5 (Message Digest Algorithm 消息摘要算法)
  可以处理任意长度的输入，产生一个128位的输出。
  已经被证实不安全，无法防止碰撞攻击。
• SHA-1 (Secure Hash Algorithm-1 )
  生成160位的散列值。
  不安全。
• SHA-2
  SHA-2是一组散列函数，使用224、256、384、512位散列值。
• SHA-3

基于密码的认证

认证过程的薄弱环节

课程中讲师提到了两种威胁：

1. 攻击者获得访问存储在系统中信息的权限（例如系统的密码文件，用户认证信息的数据库文件）
2. 拦截用户和系统间的通信

读了Leslie Lamport的Password Authentication with Insecure Communication之后他提到了第三种：

3. 用户无意识地泄露密码（例如选择容易被猜到的密码）

但是第三种可能性无法被任何密码协议防范，因为系统无法区分两个使用相同密码的人的身份。消除这种可能性的方法需要某些物理身份识别的机制，这些内容我们放在下一个部分“基于生物信息的认证中”说明，这部分主要讲解针对前两种威胁的应对方法。

对基于单向函数的密码认证的攻击和对抗

针对第一种威胁，相对于服务器直接存储用户的密码，更安全的方法是采用单向函数（one way function），例如哈希（散列函数）。服务器只存储用户密码的哈希值，接收到用户发送的密码后计算其哈希，与数据库中的值进行比对来决定是否授权访问。

Brute Force

当攻击者获取到服务器中的散列值之后，因为已知散列函数h，可以进行暴力枚举来找到对应的明文。

对抗方法：

• 限制错误尝试的次数
• 密码规则：
  • 使用更大的字符集（大小写、数字、特殊字符）
  • 使用更长的密码

增强计算能力

• 分布式方法
• GPU
• 摩尔定律

字典攻击

人们通常不会随机选择密码，通常使用名字、单词或可预测的数字。
攻击者基于字典进行暴力破解。

对抗方法：

• 强制某种密码规则（但会影响易用性）
• 预先检查密码（例如使用John the Ripper）
• 教人们生成好的密码

预计算

攻击者事先根据散列方法创建一张查找表。
搜索的时间复杂度远小于暴力攻击中的计算复杂度。
一个实际的例子是彩虹表攻击。

对抗方法：

• 加盐
• 提高计算难度（密钥扩展算法）

针对通信过程的攻击

对使用单向函数的认证存在以上攻击方法，而第二种威胁中，攻击者还可以针对通信过程发起攻击。通常的做法是加密通信内容，但是即使这样仍存在一些对应的攻击方法——如重放攻击和中间人攻击。

重放攻击（Replay Attack）

攻击者窃听用户和服务器之间的通信，获得用户加密后的用户名和密码，然后用该数据重新向服务器发起登录请求。

对抗方法：

• 挑战-应答协议（Challenge-response protocol）
• 时间戳
• 一次性密码（One Time Password, OTP）

中间人攻击（MITM, Man In The Middle）

中间人攻击指攻击者与通信的两方分别建立连接，交换收到的数据，使两方都认为正在通过一个私密的连接与对方通信。中间人攻击不仅应用于基于密码的认证过程，下面还给出了非对称密钥加密过程中的例子。

基于挑战-应答协议的一个中间人攻击：

1. 客户端A向服务端B发送登录请求
2. 中间人M此时重放A的登录请求
3. M拦截服务端B返回给A的挑战c
4. 将B返回给M的挑战c’转发给A
5. A认为这个挑战c’来自服务端，因此组合挑战和登录口令f(c’, secret)发送给B
6. M拦截f(c’, secret)并转发给B。
7. 此时A和B都认为正在和对方通信，实际会话由中间人控制

基于非对称密钥加密的中间人攻击：

1. M截获A对B的公钥请求，并转发给B
2. B认为该请求来自A（实际由M伪装），所以返回对应的公钥k_{pb}
3. M收到B的公钥，将其换成自己的公钥k_{pb'}发送给A
4. A认为该公钥来自B（实际由M伪装），因此用公钥k_{pb'}对消息进行加密
5. 此时M截获A使用自己的公钥加密的消息，他可以随意对消息进行修改，然后使用k_{pb}加密发送给B
6. 收到加密消息的B认为该消息来自A（实际由M伪装，消息可能已经被修改）

对抗方法：

• 中间人攻击利用了服务端并行协议的运行（parallel protocol runs），允许同一个用户建立多个连接，因此可以从服务端禁止同一用户多处登录
• 或者使协议运行可区分（distinguishable protocol runs），例如对消息进行签名
• 延迟测试
• 对密钥交换过程中中间人攻击的防御有一系列协议

攻击和对抗方法的详细说明

彩虹表攻击（Rainbow Talbe）

预计算的哈希链集（Precomputed hash chains）

定义一个约简函数R，定义域与值域和哈希函数正好相反，通过约简函数可以将哈希值映射到与原文格式相同的一个值上。以大量随机明文作为起始结点，对它们依次应用H（Hash）和R（Reduction）。重复一个特定次数k后，最后一个节点仍然是一个明文，然后将所有这些链的起始结点和末结点保存下来，得到一个哈希链集。

当得到某个哈希值时，对其应用一次R，若得到的明文与某条链的末结点相同，则明文极有可能存在于这条链中（并不是一定存在，因为H和R均有可能发生碰撞），因此从起始结点的明文开始计算，看是否能找到某个明文应用H后恰好得到目标的哈希值。

若应用一次R没有找到某条哈希链的末结点与它相同，则进行一轮H+R运算再进行比较。以此类推k轮，若仍未找到对应的哈希链，则可以断定，所需的明文不在这个集合中。

一个哈希链保存了一组属性相同的明文，由起始结点和末结点作为特征值保存在表中，每个明文都可以通过起始结点快速计算出，最大只需要k轮。

然而哈希链集中只使用一个R函数导致发生碰撞时，很容易出现从碰撞结点起后续结点都重复的情况。重复的链条造成冗余和浪费。

彩虹表

彩虹表对预计算哈希链集的问题进行了改进，使用R_1...R_k共k个约简函数。这样如果发生碰撞但不在同一序列位置（R_i, R_j, i \neq j），则会因为后续的R不同而得到不同的结果；当恰好在同一位置发生碰撞，则可以通过判断末结点是否相同来丢弃重复的链条。

使用时先对哈希值x应用最后一个约简函数R_k（即我们假设明文位于序列k-1的位置），检查产生的明文是否与某个末结点相同；若没有，则依次应用最后两个约简函数R_{k-1}和R_k，即R_k(H(R_{k-1}(x)))。以此类推，最差情况下，需要执行完整的从R_1到R_k的运算，以确定明文是否存在在这张彩虹表中。

盐

盐是一个较长（如128位）的随机数值，其中某些部分是与系统相关的独特值（如104位），另一些（剩下的24位）由系统为每一个密码表项随机选择（这一部分不存储在系统中）。验证时系统遍历所有可能的盐值来计算散列值，并与数据库中的值进行比较。

此处老师强调说随机的盐不存储在系统中，然而网络上可以找到的说法基本都认为盐和散列值一起存储在数据库中，具体的改日找论文或者再发邮件问一下。

加盐相当于改变了散列过程，使得预计算攻击需要针对每个不同的盐生成新的查找表。

密钥扩展算法

加盐方法能抵挡彩虹表攻击，但对暴力攻击和字典攻击效果不佳。因此采用密钥扩展算法来降低哈希函数的计算速度，从而提高暴力攻击和字典攻击计算的时间成本。密钥扩展算法的实现依靠CPU密集型哈希函数，标准算法如PBKDF2或bcrypt。

这类算法以一个安全因子或迭代次数作为参数，决定了哈希函数的速度。针对不同性能的设备应该选择恰当的值，以保证在攻击者难以破解的情况下，计算造成的延迟对用户来说是难以感知的或可接受的（例如0.5秒）。

挑战-应答协议

挑战-应答认证实际上指的是一个协议族，共同点是一方提出一个“挑战”（问题），另一方根据“挑战”提供一个有效的“应答”（回答）来获得认证。

一个简单的基于密码认证中的挑战-应答协议过程：

• 服务端向客户端发出一个挑战c
• 客户端计算挑战c和秘密secret组合后的哈希值f(c, secret)并发送给服务端
• 服务端用c和secret计算并验证结果与接收到的f是否一致

这样很多挑战-应答协议都存在一个问题：服务端需要存储这个秘密secret，而根据前面的讨论，这个秘密不能是用户的密码，所以服务端存储的是密码的哈希值。此时这个被存储的哈希值就会和真实的密码一样成为敏感数据，因为当攻击者获得数据库中的哈希值时，他就可以只使用这个哈希值来完成登录，而不需要使用真正的密码。

加盐的挑战-应答认证机制 SCRAM

有一些挑战-应答协议在设计中避免了这种问题，例如SCRAM (Salted Challenge Response Authentication Mechanism，加盐的挑战-应答认证机制)。

客户端和服务端有相同的AuthMessage，服务端存储着用户名及对应的存储的密钥（StoredKey）、服务端密钥（ServerKey）、随机的盐以及密钥扩展的迭代轮数。

• 客户端首先向服务端发送用户名
• 服务端返回对应用户的认证信息（Authentication Information），包含上面提到的四个信息
• 客户端可以根据存储的密钥和服务端密钥来验证服务端的身份，然后使用实际的密码、盐和迭代轮数对密码进行加盐扩展，最后结合服务端自己的密钥计算出客户端密钥（ClientKey）。实际发送给服务端的是结合存储的密钥和AuthMessage计算出的客户端证明（ClientProof）。
• 服务端先用存储的密钥和AuthMessage计算出客户端签名（ClientSignature），来和收到的客户端证明做异或运算，得到客户端密钥。再计算客户端密钥的哈希值来与存储的密钥进行比对。若一致则证明客户端拥有用户名对应的密码。

画了一个简要的示意图来说明几个关键值的计算方法：

这个图的整体是站在客户端角度来看的，使用最右侧Password、Salt、i、"Client Key"来计算出下方的ClientProof。

其中黄色部分是客户端从服务端收到的Authentication Information的一部分，蓝色部分是客户端自己知道的。红色部分是由客户端发送给服务端的。绿色部分是服务端已知的，StoredKey即为数据库中存储的密钥。紫色部分是服务端可以计算出的。

SCRAM的一些协议细节我目前还没看明白，具体内容参考：Salted Challenge Response Authentication Mechanism (SCRAM) SASL and GSS-API Mechanisms

一次性密码

一个密码，仅用于一次会话或事务的认证。优点是相对静态密码能抵御重放攻击，另外当用户在多个地方使用同一密码时，被攻击者获取到的一次性密码不会威胁用户其他系统账户的安全。

下面介绍几种常见的OTP的实现。

TAN，iTAN

TAN = Transaction Authentication Number 交易认证码
iTAN = indexed TAN

常用于网银系统提供两重认证（2FA, 2-Factor Authentication），需要同时使用静态口令和TAN才能完成交易，两者之一发生泄露不会威胁账户安全。

TAN是一个一次性密码的列表，由银行通过安全的方式提供给用户（带着证明身份的文件去银行领取或通过邮寄的方式），每次登陆时用户使用用户名（账户号）和PIN，从列表中选择一个未使用过的TAN来完成交易。

PIN，Personal Identification Number，个人识别码，用于网银账户登录的身份认证。通常由银行提供或个人设置。由银行提供时，为了保证两重认证的安全性，需要和TAN分开邮寄。

TAN容易受到钓鱼攻击（Phishing Attacks），攻击者通过仿造交易界面诱导用户输入登陆信息（用户名和PIN），同时获取用户的TAN。

iTAN与TAN的区别在于，银行会在交易时随机指定TAN列表中的序号。一定程度上防止了钓鱼攻击，因为攻击者不能确定银行指定的序号。

mTAN

用户创建交易时，银行通过短信发送一个包含交易信息的TAN到用户的手机上，用户可以确认交易没有被修改。

时间同步的（硬件）令牌

令牌中保存一个秘密s，使用f(s, time)生成一次性密码。

基于哈希链

由Leslie Lamport在文章Password Authentication with Insecure Communication中提出（这学期可算认识他了）。

原理是，由用户生成一条哈希链：
h^n(h^{n-1}...h^3(h^2(h^1(password))))
注册时将h^n作为密码发送，下一次登陆时使用h^{n-1}作为密码，此后依次减1。服务端在用户注册时收到h^n并保存下来，在用户第一次登陆时收到h^{n-1}，然后比对:
h(h^{n-1}()) = h^n()
若相等，则认证成功，保存h^{n-1}，以此类推。

长度扩展攻击和密钥哈希HMAC

长度扩展攻击

攻击者可以在不知道被散列消息的内容的情况下，对其添加内容，而生成一个有效的散列值。这样的攻击称为长度扩展攻击。基于Merkle-Damgård Construction构造的散列函数（如MD5, SHA-1, SHA-2）都容易受到这种类型的攻击。

对此我们使用消息认证码（MAC）来保护信息的完整性。

HMAC

带有密钥的哈希HMAC（Hash-based Message Authentication Code）是MAC的一种实现，它除了能够保证数据的完整性以外还支持发送者的身份验证，因为只有发送者持有HMAC的密钥（通常是对称密钥）。HMAC可以抵抗长度扩展攻击。

HMAC的计算方法：

HMAC(K, m) = H(（K' \oplus opad） || H（（K' \oplus ipad） || m）)

其中K' = \begin{cases} H(K) &\text{if K is larger than block size } \\ K &\text{otherwise} \end{cases}

opad和ipad分别是外部填充和内部填充，用于将不同长度的K’变成Block的大小，内部和外部指填充完是否与消息m连接求哈希。

opad = 0x5c
ipad = 0x36

MAC的实现方法除了HMAC以外还可以使用块加密（Block Cipher）或通用哈希（Universal Hashing）

基于生物信息的认证

衡量人类的生理（physiological）或行为（behavioural）特征，并与参考数值比较来：

• 验证
  verify, that a given subject is the one it claims to be
  验证是否与声称的一致
• 识别
  identify a subject within a given set of subjects
  基于生物信息来识别
  相对于验证来说更难

生理特征：

• 虹膜/视网膜
• 指纹
• 手几何学特征 (Hand Geometry)
• 面部几何学特征（Face Geometry）
• DNA
• 热成像
• 声谱

行为特征：

• 步态
• 签名（外观/书写动态：速度、压力）
• 键盘敲击（书写动态）

选择生物信息特征的需求

• 通用：每个人都有
• 独特
• 随时间变化稳定
• 可测量
• 可接受
• 可分析
• 防伪

优点及缺点

优点：

• 不会泄露（divulged）或丢失/遗忘
• 可以即时使用
• 难以复制

缺点：

• 无法更新
• 与人相关的数据需要特殊的保护（出于隐私需求）
• 侵犯隐私
• 错误率

所谓优点也只是理论上的，实际有很多反例。例如指纹可以被提取并仿制。

错误类型

False Accept Rate (FAR)/False Match Rate (FMR) 错误匹配率
FAR导致安全问题

False Reject Rate (FRR)/False Nonmatch Rate (FNR) 错误失配率
FRR导致易用性/用户接受度问题

当FAR=FRR时的错误率称为Equal Error Rate (EER)

Receiver Operating Characteristic (ROC) 接收器工作特性
ROC是一条FAR关于FRR的曲线
无法同时优化FAR和FRR，需要根据用例权衡。

多重生物信息系统

• 组合不同的生物信息特征（Multi-modal）
• 组合不同传感器的结果（Multi-sensor）
• 组合同一生物信息特征的多个样例（Multi-sample）：例如面部不同角度的采样
• 组合多个实例（Multi-instance）：例如左眼和右眼
• 组合多个算法（Multi-algorithm）

认证系统 Authentication System

根据密钥分发方式对密码系统（Cryptographic Systems）进行分类可以得到：

• Symmetric System
• Asymmetric System

根据使用目的对密码系统进行分类可以得到：

• Encryption System
• Authentication System

认证系统的目的是保护信息的完整性。
只能保证完整性而不能保证机密性。

对称密钥认证系统

认证系统使用的对称密钥生成与分发过程与对称加密系统一样。

发送方使用编码算法，使用密钥将明文编码为消息认证码（Message Authentication Code, MAC）。

发送方发送明文x和对应的MAC（无机密性）

接收方使用测试算法，重新计算明文x的MAC值并与接收到的MAC进行比较。若相同，接收方就认为消息没有被修改，接受。若不相同，则丢弃。

数字签名系统 Digital Signature System （也即非对称密钥认证系统）

数字签名系统利用非对称密钥中的私钥对明文进行签名，接收方使用公钥验证（测试）签名的有效性。

与非对称加密的过程相反：私钥加密，公钥解密。

除了完整性以外，数字签名系统还提供不可抵赖性（accountability）。

参考内容

Preimage attack

Rogaway, P.; Shrimpton, T. (2004). Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance

Merkle-Damgård Construction Method and Alternatives: A Review

【CN007】数据安全笔记7 —— 哈希函数与数字签名_YY同学的博客

Are there attacks that break collision resistance but not preimage resistance?

Leslie Lamport-Password Authentication with Insecure Communication

什么是彩虹表？ – Smallay的回答 – 知乎

Rainbow table

Salted Password Hashing – Doing it Right

Salted Challenge Response Authentication Mechanism (SCRAM) SASL and GSS-API Mechanisms

Transaction authentication number