单向散列技术是为了保证信息的完整性, 防止信息被篡改的一项技术.
特点:
无论消息长度, 计算出的长度永远不变
快速计算
消息不同, 散列值不同, 需要具有抗碰撞性 Collision Resistance 具有单向性 one-way, 不可由散列值推出原消息
弱抗碰撞性: 给定散列值, 找到和该消息具有相同散列值的另一条消息是困难的
强抗碰撞性: 任意散列值, 找到散列值相同的两条不同的消息是困难的
具有单向性 one-way, 不可由散列值推出原消息
单向散列算法:
1MD(Message Digest)
MD 散列算法分为 MD4, MD5 两套算法, 都可计算出 128 bits 的散列. MD 系列算法已经被中国科学家王小云破解(可于有限时间内找出碰撞).
2SHA(Secure Hash Algorithm)
SHA 是单向散列算法的一个标准的统称, 其下又分为 SHA-1, SHA-2, SHA-3 三套算法.
其中 SHA-1 可生成 160 bit 散列值, 已被攻破, 不推荐使用.
SHA-2 可生成不同长度的散列, 如 256 bits (SHA-256), 384 bits (SHA-384), 512 bits (SHA-512), 同时对输入的消息长度存在一定限制, SHA-256 上限接近于 2^64-1 比特, SHA-384,SHA512 则接近于 2^128-1 比特.
SHA-3, 是 2012 年被采用的最新标准, 采用了 Keccak 算法.
Keccak 算法的优点:
采用与 SHA2 完全不同的结构
结构清晰, 易于分析
适用于各种硬件, 性能优越
可生成任意长度
对消息长度无限制
可采用双工结构, 输入同时输出, 提升效率
MD4,5, RIPEMD, RIPEMD-160, SHA-1, SHA-2 均采用 MD 结构(Merkle-Damgard construction)
SHA-3 采用海绵结构
算法 | 散列长度,bit | 输入长度 | |
---|---|---|---|
MD4 (Message Digest 4) | 128 | 已破解 | |
MD5 | 128 | 已破解 | |
SHA-1 | 160 | 2^64 = 2048 | 谨慎使用,不推荐 |
SHA2 (SHA-224) | 224 (32*8 - 32) | 2^64 | - 32 表示截去 32 bit,下同 |
SHA2 (SHA-256) | 256 (32*8) | 2^64 | |
SHA2 (SHA-512/224) | 224 (64*8 - 288) | 2^64 | |
SHA2 (SHA-512/256) | 256 (64*8 - 256) | 2^64 | |
SHA2 (SHA-384) | 384 (64*8 - 128) | 2^128 | |
SHA2 (SHA-512) | 512 | 2^128 | |
SHA-3 | 无限制 | ||
RIPEMD-128 | 已破解 | ||
RIPEMD-160 | 谨慎使用,是比特币采用的 | ||
RIPEMD-256 | |||
RIPEMD-320 |
对散列的攻击
暴力破解, 冗余碰撞
生日攻击, 针对强抗碰撞性
哈希碰撞是什么
所谓哈希(hash), 就是将不同的输入映射成独一无二的, 固定长度的值(又称 "哈希值"). 它是最常见的软件运算之一.
如果不同的输入得到了同一个哈希值, 就发生了 "哈希碰撞"(collision).
黑客攻击的一种方法, 就是设法制造 "哈希碰撞", 然后入侵系统, 窃取信息.
如何防止哈希碰撞?
防止哈希碰撞的最有效方法, 就是扩大哈希值的取值空间.
16 个二进制位的哈希值, 产生碰撞的可能性是 65536 分之一. 也就是说, 如果有 65537 个用户, 就一定会产生碰撞. 哈希值的长度扩大到 32 个二进制位, 碰撞的可能性就会下降到 4,294,967,296 分之一.
更长的哈希值意味着更大的存储空间, 更多的计算, 将影响性能和成本. 开发者必须做出抉择, 在安全与成本之间找到平衡.
生日攻击
哈希碰撞的概率取决于两个因素(假设哈希函数是可靠的, 每个值的生成概率都相同).
取值空间的大小(即哈希值的长度)
整个生命周期中, 哈希值的计算次数
这个问题在数学上早有原型, 叫做 "生日问题"(birthday problem): 一个班级需要有多少人, 才能保证每个同学的生日都不一样?
答案很出人意料. 如果至少两个同学生日相同的概率不超过 5%, 那么这个班只能有 7 个人. 事实上, 一个 23 人的班级有 50% 的概率, 至少两个同学生日相同; 50 人班级有 97% 的概率, 70 人的班级则是 99.9% 的概率(计算方法见后文).
这意味着, 如果哈希值的取值空间是 365, 只要计算 23 个哈希值, 就有 50% 的可能产生碰撞. 也就是说, 哈希碰撞的可能性, 远比想象的高. 实际上, 有一个近似的公式.
上面公式可以算出, 50% 的哈希碰撞概率所需要的计算次数, N 表示哈希的取值空间. 生日问题的 N 就是 365, 算出来是 23.9. 这个公式告诉我们, 哈希碰撞所需耗费的计算次数, 跟取值空间的平方根是一个数量级.
这种利用哈希空间不足够大, 而制造碰撞的攻击方法, 就被称为生日攻击(birthday attack).
给出生日攻击的数学推导.
至少两个人生日相同的概率, 可以先算出所有人生日互不相同的概率, 再用 1 减去这个概率.
我们把这个问题设想成, 每个人排队依次进入一个房间. 第一个进入房间的人, 与房间里已有的人(0 人), 生日都不相同的概率是 365/365; 第二个进入房间的人, 生日独一无二的概率是 364/365; 第三个人是 363/365, 以此类推.
因此, 所有人的生日都不相同的概率, 就是下面的公式.
上面公式的 n 表示进入房间的人数. 可以看出, 进入房间的人越多, 生日互不相同的概率就越小.
这个公式可以推导成下面的形式.
那么, 至少有两个人生日相同的概率, 就是 1 减去上面的公式.
哈希碰撞的公式
上面的公式, 可以进一步推导成一般性的, 便于计算的形式.
根据泰勒公式, 指数函数 ex 可以用多项式展开.
如果 x 是一个极小的值, 那么上面的公式近似等于下面的形式.
现在把生日问题的 1/365 代入.
因此, 生日问题的概率公式, 变成下面这样.
假设 d 为取值空间(生日问题里是 365), 就得到了一般化公式.
上面就是哈希碰撞概率的公式.
(6)消息认证码 Mac
单向散列可以解决篡改的问题, 但消息是来自可信一方, 还是来自伪装者, 却无法解决. 伪装者完全可以发送有害的信息和该信息的散列, 而接受者却无法分辨. 消息认证码技术可以解决此类问题.
消息认证码(Message Authentication Code), 简写为 Mac. 通过发送方与接收方共享密钥, 通过该共享密钥对计算 Mac 值.
Mac 使用步骤
消息认证码使用步骤:
发送方 A 与接收方 B 共享密钥
发送方 A 通过密钥计算 Mac 值 = Mac-A
发送方 A 发送原消息 + Mac-A
接收方 B 对原消息通过密钥计算 Mac 值 = Mac-B
接收方 B 比较 Mac-A 与 Mac-B, 若一致则成功.
Mac 实现
Mac 实现的关键, 是获得一串需要与共享密钥相关而且足够有区分度的串.
因此, 可以通过多种方式获得 Mac 值, 如单向散列, 分组密码截取最后一组作为 Mac 值, 流密码, 非对称加密等.
针对 Mac 的问题
密钥配送的问题, 因为 Mac 需要发送者与接收者使用相同的密钥
重放攻击, 窃取某一次通信中的正确的 Mac, 然后攻击者重复多次发送相同的信息. 由于信息与 Mac 可以匹配, 在不知道密钥的情况下, 攻击者就可以完成攻击. 以下方法可以避免: 暴力破解
序号, 约定信息中带上递增序号, Mac 值为加上序号的 Mac.
时间戳, 约定信息中带上时间戳
随机数 nonce, 每次传递前, 先发送随机数 nonce, 通信是带上 nonce
无法防止否认, 因为密钥是共享的, 接收者可以伪造对发送者不利的信息.
(7)数字签名
由于 Mac 无法解决否认的问题是由于采用的相同的密钥, 那么采用公私钥对就可以解决啦~
采用非对称加密的消息认证码的技术, 就是数字签名.
在非对称加密中, 私钥用来解密, 公钥用来加密.
在数字签名技术中, 私钥用来加密, 公钥用来解密.
数字签名步骤
签名方 A 生成非对称公私钥对 public-key,private-key
A 向消息接收方 B 发送公钥 publi-key
A 采用 private-key 加密(一般是对消息的散列值进行加密), 生成数字签名
A 将消息与数字签名发往 B
B 采用 public-key 解密数字签名
B 验证数字签名
由于用于解密的是公钥, 是公开的. 因此任何人都可以验证数字签名.
数字签名实现
数字签名的核心, 就是非对称加密, 在前文已经介绍了一些非对称加密算法, 均可用于数字签名之中.
常见的有如下几种:
RSA
ElGamal
DSA
ECDSA(Elliptic Curve Signature Algorithm), 结合椭圆曲线算法的数字签名技术
Rabin
数字签名的问题
数字签名由于采用了非对称加密, 因此可以防止否认. 但发送方怎么能知道所收到的公钥就是接收方私钥所对应的公钥呢? 如果不小心采用了攻击者的公钥, 然后接收了攻击者私钥签名的信息, 公私钥完全匹配, 于是信息就被接受了, 那么就 GG 了.
因此, 业界便推出了证书. 由权威机构颁布, 认证公钥的合法性, 那么就 OK 啦~
(8)证书
对数字签名所发布的公钥进行权威的认证, 便是证书. 证书可以有效地避免中间人攻击的问题.
PKC:Public-Key Certificate, 公钥证书, 简称证书.
CA:Certification Authority, 认证机构. 对证书进行管理, 负责 1. 生成密钥对, 2. 注册公钥时对身份进行认证, 3. 颁发证书, 4. 作废证书. 其中负责注册公钥和身份认证的, 称为 RA(Registration Authority 注册机构)
PKI:Public-Key Infrastructure, 公钥基础设施, 是为了更高效地运用公钥而制定的一系列规范和规格的总称. 比较著名的有 PKCS(Public-Key Cryptography Standards, 公钥密码标准, 由 RSA 公司制定),X.509 等. PKI 是由使用者, 认证机构 CA, 仓库 (保存证书的数据库) 组成.
CRL:Certificate Revocation List 证书作废清单, 是 CA 宣布作废的证书一览表, 会带有 CA 的数字签名. 一般由处理证书的软件更新 CRL 表, 并查询证书是否有效.
证书使用步骤
下图比较详细的阐述了证书的使用步骤
证书的层级
对于认证机构的公钥, 可以由其它的认证机构施加数字签名, 从而对认证机构的公钥进行验证, 即生成一张认证机构的公钥证书, 这样的关系可以迭代好几层, 一直到最高一层的认证机构时该认证机构就称为根 CA, 根 CA 会对自己的公钥进行数字签名叫做自签名.
针对证书的问题
公钥注册前进行攻击
注册相似信息进行攻击, 例如 Bob 和 BOB, 一旦没看清, 就会泄露信息
窃取 CA 的私钥进行攻击, CA 的私钥一旦被泄露, 需要通过 CRL 通知客户
伪装成 CA 进行攻击, 一般证书处理软件只采纳有限的根 CA
利用 CRL 发布时间差, 私钥被盗 - 通知 CA - 发布 CRL, 均存在时间差, 攻击者可以利用此时间差进行攻击
利用 CRL 发布时间差否认信息. 发布有害信息 - 通知 CA 作废证书 - 发布 CRL, 由于存在时间差, 恶意消息的发布者完全可以否认恶意消息是由其发出的.
来源: https://www.cnblogs.com/songyifan427/p/11170797.html