Post

加密算法和密码学

Posted Updated
By Evan
15 min read
加密算法和密码学

了解一些与安全和密码学相关的知识，有助于理解日常生活中接触到的一些工具是怎么运作的，比如 Git 中哈希函数的使用，或者 SSH 中的密钥导出函数（key derivation functions）以及对称/非对称加密系统。

熵（Entropy）

在密码学中，熵的概念非常重要，比如我们常常用它来衡量一个密码的强度。密码越随机，它的熵就越高，也就越难被猜到。

熵是以比特（bits）为单位衡量的，表示系统的随机性。在从一个可能的结果集里均匀地随机选择时，熵等于可能出现的结果数量的$log_2$。例如，一次公平的硬币抛掷给出的熵为 $log_2(2)=1$ 比特；而掷一个六面骰子的熵大约是 $log_2(6)=2.58$ 比特。

在实际应用中，你应该考虑攻击者知道密码的模式（比如字母、数字和符号的组合），但不知道用于选择特定密码的随机性（例如从骰子掷出的数字）。

那么，多少比特的熵才足够呢？这取决于你的威胁模型（threat model）。对于在线暴力破解，约 40 比特的熵已经相当不错了。而对于离线暴力破解，攻击者每秒可以尝试更多的可能性，因此需要更强的密码，比如 80 比特或者更多。

哈希函数（Hash Functions）

密码学中的哈希函数是将任意大小的数据映射到一个固定大小的输出，并具有一些特殊的性质。

一个哈希函数的例子是 SHA-1，它可以将任意大小的输入映射到 160 位的输出（可以表示为 40 个十六进制字符）。我们可以使用 sha1sum 命令尝试计算输入的 SHA-1 哈希值：

1
2
3
4
5
6

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

哈希函数可以被看作是一个难以反转的随机（但确定性）函数（这是哈希函数的理想模型）。哈希函数具有以下特性：

  1. 确定性（Deterministic）：相同的输入总是生成相同的输出。
  2. 不可逆（Non-invertible）：很难找到一个输入 m 使得 hash(m) = h，即给定一个哈希值，很难推算出原始的输入。
  3. 目标碰撞抗性（Target collision resistant）：给定输入 m_1，很难找到一个不同的输入 m_2，使得 hash(m_1) = hash(m_2)。
  4. 碰撞抗性（Collision resistant）：很难找到两个不同的输入 m_1 和 m_2，使得 hash(m_1) = hash(m_2)（请注意，这比目标碰撞抗性要强得多）。

值得注意的是，尽管 SHA-1 仍然在某些用途上有效，但它现在已不再被认为是一个强大的加密哈希函数。SHA-1 已经被发现存在一些安全漏洞，因此不推荐用于新的安全应用中。

密钥派生函数（Key Derivation Functions）

与加密哈希函数相类似，密钥派生函数（KDFs）用于多种应用，包括生成固定长度的输出，以作为其他加密算法中的密钥。通常，KDFs 故意设计为较慢的运行速度，以减缓离线暴力破解攻击的风险。

密钥派生函数的应用包括：

  1. 从密码短语生成密钥，用于其他加密算法，例如对称加密。
  2. 存储登录凭证。存储明文密码是危险的；正确的方法是为每个用户生成并存储一个随机的盐值 salt = random()，存储 KDF(password + salt)，并通过重新计算 KDF 来验证登录尝试。

对称加密

当想到加密时，隐藏消息内容可能是你首先想到的概念。对称加密正是通过以下功能集实现这一点：

  • keygen() -> key（此函数是随机的）
  • encrypt(plaintext: array<byte>, key) -> array<byte>（生成密文）
  • decrypt(ciphertext: array<byte>, key) -> array<byte>（还原明文）

对称加密的一个主流应用是为存储在不受信任的云服务中的文件进行加密，可以与密钥派生函数（KDF）结合使用，以便可以使用human-readable密码短语加密文件。具体操作如下：

  1. 生成密钥 key = KDF(passphrase)
  2. 加密文件 encrypt(file, key)。
  3. 上传加密后的文件到云服务器

非对称加密

非对称指的是存在两个密钥，且它们具有不同的作用。

  1. 私钥（private key），顾名思义，是应该保密的
  2. 公钥（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 （验证签名是否有效）

encrypt()/decrypt()函数具有与对称加密系统中类似的性质。可以使用公钥对消息进行加密。在给定输出（密文）的情况下，如果没有私钥，很难确定输入（明文）。解密函数具有明显的正确性属性，即 decrypt(encrypt(m, public key), private key) = m。

sign()/verify()函数具有与物理签名相同的性质，即难以伪造签名。无论消息是什么，如果没有私钥，很难生成一个签名使得 verify(message, signature, public key) 返回 true。当然，验证函数具有明显的正确性属性，即 verify(message, sign(message, private key), public key) = true。

非对称加密的典型应用包括：

  • PGP 邮件加密：人们可以将他们的公钥发布在网上，任何人都可以发送加密邮件给他们。
  • 私密消息传递：像 Signal 和 Keybase 这样的应用程序使用非对称密钥来建立私密通信通道。
  • 软件签名：Git 可以使用 GPG 签名提交和标签。通过发布的公钥，任何人都可以验证下载软件的真实性。

密钥分发

非对称密钥加密非常强大，但它面临一个重大挑战：如何分发公钥或将公钥映射到现实世界的身份（即确保公钥是正确的而没有被攻击者恶意劫持）。针对这个问题有许多解决方案。

  • Signal 采用了一种简单的解决方案：首次使用时信任，并支持 out-of-band 公钥交换，即线下通过扫二维码亲自交换公钥。
  • PGP 采用了另一种解决方案，即信任网络（Web of Trust）。
  • Keybase 提供了另一种基于社交网络的解决方案，即将公钥和多个社交账户相关联。

案例分析

密码管理器

每个人都应该使用的必备工具（例如 KeePass、pass、BitWarden 和 1Password）。

密码管理器可以方便地为所有登录使用唯一的、随机生成的高熵密码，并将所有密码保存在一个地方，使用对称加密算法加密，密钥由口令通过密钥派生函数（KDF）生成。

使用密码管理器可以避免密码重复使用（因此在网站被攻破时影响较小），使用高熵密码（因此被攻破的可能性较低），并且只需记住一个高熵密码。

双因素认证

双因素认证（2FA）要求你使用口令（”something you know”）和 2FA 认证器（如 YubiKey，”something you have”）来防止密码被盗和钓鱼攻击。

全盘加密

将笔记本电脑的整个磁盘加密是在设备被盗时保护数据的简单方法。你可以在 Linux 上使用 cryptsetup + LUKS，在 Windows 上使用 BitLocker，或在 macOS 上使用 FileVault。通过对称加密算法加密整个磁盘，密钥由口令保护。

私密消息传递

使用 Signal 或 Keybase。端到端的安全性基于非对称加密实现。获取联系人的公钥是关键步骤。如果你想要良好的安全性，需要通过 out-of-band 方式验证公钥（使用 Signal 或 Keybase），或信任社交证明（使用 Keybase）。

SSH

当你运行 ssh-keygen 时，它会生成一个非对称密钥对，包括公钥和私钥。这是随机生成的，使用操作系统提供的熵（从硬件事件等收集）。公钥按原样存储（因为它是公开的，保密并不重要），但私钥在存储时应加密保存。ssh-keygen 程序会提示用户输入口令，并将其通过密钥派生函数生成一个密钥，然后使用对称加密算法加密私钥。

在使用过程中，一旦服务器知道客户端的公钥（存储在 .ssh/authorized_keys 文件中），连接的客户端可以通过非对称签名来证明其身份。这是通过 challenge-response 机制完成的。简单来说，服务器选择一个随机数并发送给客户端。客户端对该消息进行签名，并将签名返回给服务器，服务器根据记录的公钥验证签名。这有效地证明了客户端拥有与服务器 .ssh/authorized_keys 文件中公钥对应的私钥，因此服务器可以允许客户端登录。

本地密码管理系统实战

参考视频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 使用brew安装pass和gpg

brew install pass, gpg

# 生成自己的gpg key-pairs，用于后面初始化pass的password store
gpg --gen-key

# 复制粘贴上一步生成的primary key的ID，开始初始化pass
pass init <primary-key-id>

# 使用git管理pass
pass git init

# 为 git 添加一个远程仓库
pass git remote add origin <repo-url>

# 撤回到之前的更改
pass git log
pass git revert <commit-id>

# 手动添加一条已经存在的密码
pass insert general/amazon

# 自动生成新的密码，-c可以直接复制到剪切板，-n表示生成的密码不包含特殊符号
pass generate general/amazon

# 编辑指定的条目，可以在首行下面添加账户等其他信息作为metadata
pass edit general/amazon

# 快速查找条目的metadata
pass grep "xxxx@gmail.com"

# 显示指定条目的密码，pass show 可以展示指定条目的所有信息，包括matadata
pass -c general/amazon

# 删除一个条目
pass rm genral/amazon
SWE
cryptography encryption security bitcoin MIT
This post is licensed under CC BY 4.0 by the author.