𝖄𝕺🌎𝕿𝕽𝕺¥

𝖄𝕺🌎𝕿𝕽𝕺¥

𝕴 𝖉𝖔 𝖒𝖆𝖌𝖎𝖈
github

计算机安全与取证之哈希函数和公钥加密

哈希函数的介绍#

Screenshot_2024-03-14_at_20.37.50!

  • 哈希函数是一种将任意长度输入字符串映射到固定长度哈希值(有时称为消息摘要)的高效可计算函数。不管输入几位,输出都是 N bits。
  • 哈希函数不是 keyed primitive 基于密钥的原语。

哈希函数的应用#

包括 message fingerprinting 消息指纹生成、 file integrity checking 文件完整性检查、signature schemes (hash-then-sign paradigm) 签名方案(先哈希后签名范式)、message authentication codes 消息认证码(例如 HMAC)、key derivation 密钥派生(例如,在 Diffie-Hellman 密钥交换中从 “原始数据” 派生密钥)、password hashing 密码哈希、commitment schemes 承诺方案、pseudorandom number generators 伪随机数生成器、stream ciphers 流密码(计数器模式下的哈希函数)、bitcoin 比特币(工作量证明方案)、post-quantum signature schemes 后量子签名方案等。

哈希函数的标准#

NIST 的 SHA-1(直到 2010 年)、SHA-2(SHA-224、SHA-256、SHA-384、SHA-512)、SHA-3(Keccak);NESSIE 的 SHA-2(SHA-256、SHA-384、SHA-512)、WHIRLPOOL;CRYPTREC 的 SHA-2(SHA-256、SHA-384、SHA-512)。

password hashing 密码哈希#

加密散列函数可用于多种安全环境,但最著名的是密码 hash。

  • 服务器中密码是明文,服务器被入侵直接泄漏,攻击者冒充。
  • 在数据库中只存储密码哈希值。
  • 为每个用户存储 H (password) 而不是密码。
  • 服务器对收到的密码进行 Hash,并与表进行比较。匹配成功则验证成功。
  • 直觉:攻击者必须逆向散列才能恢复密码。

Salting#

  • 在每次散列计算中添加一个随机的、账户专用的值,称为盐。
  • 典型的盐值为 64 位,足够防止碰撞。

服务器存储 (salt, H (salt||password),而不是 H (Password),salt 时特定账户的随机值。

Iteration#

  • 典型的迭代次数: 10000,即每尝试一个密码都要算 10000 次,安全性更高。

哈希函数的安全属性#

定理#

碰撞:hash 后的值相等,但 hash 前的值不等。

抗碰撞性意味着抗第二预映像性,任何 collision resistance 抗碰撞性的哈希函数都是 second pre-image resistance 抗第二预映像性的。

pre-image resistance 抗预像和 collision-resistance 抗碰撞#

  • pre-image resistance 抗预像(单向性):有 h 不能找到 m

  • second pre-image resistance 抗二次预像:给定 m1,若另一个 m2 的 hash 等于 m1 的 hash,m2 也不等于 m1

  • collision resistance 抗碰撞:在 m 对(pair)中,若有 H (m1)=H (m2),m1 也不等于 m2

  • Near-Collision Resistance: hash 值大部分相同的 m1 和 m2 也不相同,体现在信号中的公钥验证。

  • Partial Pre-Image Resistance 1:无法从给定 hash 值中恢复任何信息。

  • Partial Pre-Image Resistance 2:给定一个长度为 l 的 hash 值,无法在 2l 次尝试内获取到其 message。

    Screenshot_2024-03-14_at_21.28.45

    Screenshot_2024-03-14_at_21.36.37

    对于在 t 时间内运行的所有 A,A 输出碰撞的概率的边界是 e

    Screenshot_2024-03-14_at_21.41.46

生日约束的含义#

  • N 位散列函数只能提供 N/2 位的安全性 *,以抵御一般碰撞攻击。e.g. 我们需要 256 位输出的散列函数来实现 128 位的。

  • 但目前还没有比一般生日攻击(2^128)更快的碰撞 inding 攻击。

  • 在某些成本模型中,攻击成本为 2^(N/2) 个 "操作"+ 内存。

普通散列函数并不好用(对于加密来说!)。非加密哈希函数(在加密方面)很弱!#

Merkle-Damgård iterated hashing#

  • 用压缩函数 h 构建哈希函数。

  • 将 message 分成固定长度为 k 的 blocks (e.g. m1, m2),其中包括了填充。

  • 引入 IV 对 m1进行hash。。。然后引入m2重复步骤

    Screenshot_2024-03-14_at_23.37.04

  • 如果压缩函数 h 是抗碰撞的,那么 H 也是抗碰撞的。

    length-extension 长度扩展特性#

    本来在 tu 就该输出了,但作为输入进入下一个块了。

    在某些应用中存在问题,如 MAC 或密钥推导通过连接密钥和信息,从散列值函数构造出的函数。

    Screenshot_2024-03-14_at_23.45.09

    主要问题是散列输出大小 = 区块密码块大小,因此需要较大的块大小 N,以避免 2N/2 生日攻击。

    从块密码构建压缩函数#

    Davies-Meyer 戴维斯 - 迈耶:#

    Screenshot_2024-03-15_at_03.09.26

    连锁变量变为信息输入;信息输入变为密钥。

    给出了一种抗碰撞。

SHA-2#

使用了戴维斯 - 迈耶模式的 256 位块密码建立压缩功能。

速度是 SHA-1 的两倍

SHA-3#

允许可变长度输出,在密钥推导等应用中非常有用。

SHA3-256 比 SHA-256 稍慢(10-15%)。

Public Key Encryption (PKE)#

公钥加密技术的基础是非对称加密机制,与传统的对称加密不同,非对称加密使用一对密钥:公钥和私钥。公钥用于加密信息,而私钥用于解密信息,这两个密钥是数学上相关联的,但是从公钥不能轻易计算出私钥,这就确保了信息传输的安全性。

三重算法:#

  • KGen: 随机 key pair (sk,pk) sk is private key, pk is public key
  • Enc: 一般是随机的,pk + m → c
  • Dec: sk + c → m
![Screenshot_2024-03-15_at_03.28.22](https://file.yotroy.cool/Screenshot_2024-03-15_at_03.28.22.png?x-oss-process=style/1)

过程#

实际应用中不应该像教科书 RSA 这样直接使用。

Screenshot_2024-03-15_at_03.35.19

Screenshot_2024-03-15_at_03.45.11

Screenshot_2024-03-15_at_03.48.42

破解关键点#

  • 不仅要保护秘密密钥难以猜测,更要确保信息的机密性,更确切地说,是在选择密文攻击(IND-CCA)下的不可区分性。
  • 即使敌手能够获取任意消息的解密,也不应该有任何关于明文的信息泄露给敌手。
  • 敌手能够访问加密和解密的预言机,分别用于密钥对 (sk, pk)。
  • 敌手可以提交任意消息对 (m0, m1) 到加密预言机,并接收加密消息 c。
  • 敌手还可以提交任意密文 c' 到解密预言机,并接收解密消息 Dec_sk (c')。
  • 敌手的目标是恢复比特 b。
  • 这个定义与 IND-CPA 的定义进行了比较,但敌手在这里不能提交来自加密预言机的输出,否则他们可以轻易地赢得比赛。

IND-CCA 选择密文攻击下的不可区分性#

Indistinguishable (IND) under Chosen Ciphertext Attack
(CCA)

Screenshot_2024-03-15_at_03.55.17

  • 如果攻击者可以以某种方式从公钥 (pk) 恢复私钥 (sk),该 PKE 方案就不是 IND-CCA 安全的。
  • 一个方案是 IND-CCA 安全的,它必然是 IND-CPA 安全的
  • 如果一个 PKE 方案有一个确定性加密算法,它就不是 IND-CPA 安全
  • 教科书中的 RSA 是确定性的,所以它既不是 IND-CPA 安全也不是 IND-CCA 安全。在现实应用中,RSA 需要采用像 OAEP 这样的填充方案来增加随机性,以达到 IND-CPA 和 IND-CCA 安全性。

使用例子#

RSA 因数分解,ElGamal 离散对数,McEliece 基于代码的加密法,NTRUEncrypt 基于网格加密法

擅长?#

  • PIN code 如支付用
  • 比对称加密贵
  • PKE 通常用于传输对称密钥,用于加密批量或有效载荷数据。
  • PKE 的这种用法通常被称为混合加密。
  • 对称密钥在对称加密方案中用于加密实际数据。

关键封装机制 KEM#

体现了在选择密文攻击(CCA)下的不可区分性(IND),也称为 IND-CCA 安全性。

Screenshot_2024-03-15_at_04.05.22

Hybrid Encryption 混合加密#

  • 一般称为 KEM/DEM 范式。

  • 简化了开发过程,因为开发者不需要配对加密原语,从而减少了复杂性和出错的可能性。

  • 它利用密钥封装机制(KEM)来安全传输一个对称密钥,以及数据封装机制(DEM)来用对称密钥加密数据。

    Screenshot_2024-03-15_at_05.17.21

    Screenshot_2024-03-15_at_05.17.35

    Screenshot_2024-03-15_at_05.24.12

定理#

PKE 系统是从密钥封装机制(KEM)和数据封装机制(DEM)构建的,如果 KEM 是抗选择密文攻击(IND-CCA)安全的,同时 DEM 也是 IND-CCA 安全的,那么整个 PKE 系统也是 IND-CCA 安全的。

对称加密方案的核心问题在于需要预先共享加密密钥。为了解决这个难题,我们还有公钥加密机制。通过将 PKE 作为密钥封装机制来形式化使用,并且建立了混合加密,使用 KEM/DEM 范式,并展示如何证明其安全性。简要概括如下:

  1. 对称加密(SE)需要提前分享密钥,这在分布式环境中是不方便的。这就是为何需要引入公钥加密(PKE),它解决了密钥分发的问题。
  2. 然而,PKE 相比于对称加密来说计算成本很高。为了保持效率,我们使用 PKE 加密一个较短的密钥,然后使用这个密钥通过对称加密(SE)来加密有效载荷数据。这种做法通常称为混合加密。
  3. 我们将 PKE 的使用形式化为密钥封装机制(KEM),并通过 KEM/DEM 范式构建混合加密,并展示如何证明其安全性。

总结来说,混合加密结合了 PKE 的安全性和 SE 的效率,通过密钥封装和数据封装两个步骤,以安全且高效的方式传输加密密钥和数据。

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。