missing semester - Security and Cryptography

2024-02-11 13:13:52

熵

熵(Entropy) 度量了不确定性并可以用来决定密码的强度。

熵的单位是 bits(比特)。对于一个均匀分布的随机离散变量，熵等于 log_2(# of possibilities)。扔一次硬币的熵是1 bits，即log_2(2)。掷一次（六面）骰子的熵大约为2.58 bits，即log_2(6)。

使用多少比特的熵取决于应用的威胁模型。

XKCD漫画告诉我们，大约40比特的熵足以对抗在线穷举攻击（受限于网络速度和应用认证机制）。

而对于离线穷举攻击（主要受限于计算速度）, 一般需要更强的密码 (比如80比特或更多)。

missing semester - Security and Cryptography

散列函数

密码散列函数 (Cryptographic hash function) 可以将任意大小的数据映射为一个固定大小的输出。

hash(value: array<byte>) -> vector<byte, N>  (N对于该函数固定)

SHA-1是Git中使用的一种散列函数，它可以将任意大小的输入映射为一个160比特（可被40位十六进制数表示）的输出。

$ printf 'hello' | sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
$ printf 'hello' | sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
$ printf 'Hello' | sha1sum 
f7ff9e8b7bb2e09b70935a5d785e0cc5d9d0abf0

抽象地讲，散列函数可以被认为是一个不可逆，且看上去随机（但具确定性）的函数。一个散列函数拥有以下特性：

确定性：对于不变的输入永远有相同的输出。
不可逆性：对于hash(m) = h，难以通过已知的输出h来计算出原始输入m。
目标碰撞抵抗性/弱无碰撞：对于一个给定输入m_1，难以找到m_2 != m_1且hash(m_1) = hash(m_2)。
碰撞抵抗性/强无碰撞：难以找到一组满足hash(m_1) = hash(m_2)的输入m_1, m_2（该性质严格强于目标碰撞抵抗性，即Hash函数基本没有碰撞）。

密码散列函数的应用

Git中的内容寻址存储(Content addressed storage)：散列函数是一个宽泛的概念（存在非密码学的散列函数），那么Git为什么要特意使用密码散列函数？
- 普通的散列函数没有无碰撞性，Git 使用密码散列函数，来确保分布式版本控制系统中的两个不同数据不会有相同的摘要信息（例如两个内容不同的 commit 不应该有相同的哈希值）。
文件的信息摘要(Message digest)：例如下载文件时，对比下载下来的文件的哈希值和官方公布的哈希值是否相同来判断文件是否损坏或者被篡改。
承诺机制(Commitment scheme)：假设我希望承诺一个值，但之后再透露它—— 比如在没有一个可信的、双方可见的硬币的情况下在我的脑海中公平的“扔一次硬币”。
- 假定偶数r代表正面，奇数r代表反面。
- 我可以选择一个值r = random()，并和你分享它的哈希值h = sha256(r)。
- 这时你可以开始猜硬币的正反。
- 我告诉你值r的内容，得出胜负。同时你可以使用sha256(r)来检查我分享的哈希值h以确认我没有作弊。

密钥生成函数

密钥生成函数 (Key Derivation Functions) 与密码散列函数类似，用以产生一个固定长度的密钥。但是为了对抗穷举法攻击，密钥生成函数通常较慢。

密钥生成函数的应用

将其结果作为其他加密算法的密钥，例如对称加密算法
数据库中保存的用户密码为密文
- 针对每个用户随机生成一个盐，并存储盐，以及密钥生成函数对连接了盐的明文密码生成的哈希值 KDF(password + salt)。
- 在验证登录请求时，使用输入的密码连接存储的盐重新计算哈希值KDF(input + salt)，并与存储的哈希值对比。
- 盐（Salt），在密码学中，是指在散列之前将散列内容（例如：密码）的任意固定位置插入特定的字符串。这个在散列中加入字符串的方式称为“加盐”。
- 在大部分情况，盐是不需要保密的。
- 通常情况下，当字段经过散列处理，会生成一段散列值，而散列后的值一般是无法通过特定算法得到原始字段的。但是某些情况，比如一个大型的彩虹表，通过在表中搜索该SHA-1值，很有可能在极短的时间内找到该散列值对应的真实字段内容。
- 加盐可以避免用户的短密码被彩虹表破解，也可以保护在不同网站使用相同密码的用户。

对称加密

对称加密使用以下几个方法来实现这个功能：

keygen() -> key  (这是一个随机方法)

encrypt(plaintext: array<byte>, key) -> array<byte>  (输出密文)
decrypt(ciphertext: array<byte>, key) -> array<byte>  (输出明文)

加密方法encrypt()输出的密文ciphertext很难在不知道key的情况下得出明文plaintext。
解密方法decrypt()有明显的正确性。对于给定密文及其密钥，解密方法必须输出明文：decrypt(encrypt(m, k), k) = m。

AES 是现在常用的一种对称加密系统。在 Linux 下可以使用 openssl 工具：

# 加密
openssl aes-256-cbc -salt -in {源文件名} -out {加密文件名}
# 解密
openssl aes-256-cbc -d -in {加密文件名} -out {解密文件名}

对称加密的应用

加密不信任的云服务上存储的文件。对称加密和密钥生成函数配合起来，就可以使用密码加密文件：将密码输入密钥生成函数生成密钥 key = KDF(passphrase)，然后存储encrypt(file, key)。

非对称加密

非对称加密的“非对称”代表在其环境中，使用两个具有不同功能的密钥：一个是私钥(private key)，不向外公布；另一个是公钥(public key)，公布公钥不像公布对称加密的共享密钥那样可能影响加密体系的安全性。

keygen() -> (public key, private key)  (这是一个随机方法)

encrypt(plaintext: array<byte>, public key) -> array<byte>  (输出密文)
decrypt(ciphertext: array<byte>, private key) -> array<byte>  (输出明文)

sign(message: array<byte>, private key) -> array<byte>  (生成签名)
verify(message: array<byte>, signature: array<byte>, public key) -> bool  (验证签名是否是由和这个公钥相关的私钥生成的)

非对称的加密/解密方法和对称的加密/解密方法有类似的特征（公钥加密，私钥解密）：
信息在非对称加密中使用公钥加密，且输出的密文很难在不知道私钥的情况下得出明文。
解密方法decrypt()有明显的正确性。给定密文及私钥，解密方法一定会输出明文： decrypt(encrypt(m, public key), private key) = m。

签名/验证(sign/verify)：

在不知道私钥的情况下，不管需要签名的信息为何，很难计算出一个可以使 verify(message, signature, public key) 返回为真的签名。

非对称加密的应用

PGP电子邮件加密](https://en.wikipedia.org/wiki/Pretty_Good_Privacy)：用户可以将所使用的公钥在线发布，比如：PGP密钥服务器或 Keybase。任何人都可以向他们发送加密的电子邮件。
聊天加密：像 Signal 和 Keybase 使用非对称密钥来建立私密聊天。
软件签名：Git 支持用户对提交(commit)和标签(tag)进行GPG签名。任何人都可以使用软件开发者公布的签名公钥验证下载的已签名软件。

密钥分发

非对称加密面对的主要挑战是，如何分发公钥并对应现实世界中存在的人或组织。

Signal的信任模型：信任用户第一次使用时给出的身份(trust on first use)，支持线下(out-of-band)面对面交换公钥（Signal里的safety number）。
PGP使用的是信任网络。
Keybase主要使用社交网络证明 (social proof)。

码农公寓

熵