计算机和网络安全 07

密码学协议与网络安全概述

秘密分割 (Secret Splitting)

问题背景

如何将一个秘密分割给多方，使得单独的每一份都没有用，但组合起来可以恢复秘密？ 例如，可口可乐公司 CEO 需要保护配方不被百事可乐的商业间谍获取 。如果将秘密告诉最信任的员工，他们可能会叛变或受到威胁而泄露秘密 。

基于异或 (XOR) 的秘密分割

Trent 想要保护消息 $m$：

1. 生成一个与 $m$ 等长的随机字符串 $r$ 。
2. 计算 $s = m \oplus r$ 。
3. 将 $r$ 交给 Alice，将 $s$ 交给 Bob 。

$r$ 和 $s$ 被称为消息 $m$ 的影子 (shadow) 。Alice 和 Bob 可以通过将他们的影子进行异或操作来重构 $m$：$s \oplus r = m$ 。如果 $r$ 是真正随机的，则该系统是完美安全的，类似于一次性密码本 (One Time Pad) 。

该方案可以扩展到 $n$ 个人，通过生成 $n-1$ 个随机字符串 $r_1, …, r_{n-1}$ 。将 $r_1$ 交给第一个人，$r_2$ 交给第二个人，以此类推，直到 $r_{n-1}$ 交给第 $n-1$ 个人，并将 $r_1 \oplus … \oplus r_{n-1} \oplus m$ 交给第 $n$ 个人 。

秘密分割旨在通过分散信任来增强可靠性，而不增加风险 。

基于异或 (XOR) 的秘密分割存在的问题

• 系统由 Trent 裁决 。
  • Trent 可以分发无用的信息并声称它是秘密 。
  • Trent 可以声称将秘密分成 4 份，但实际上只在前两个人之间分割 。
• 所有参与方都知道消息的长度 。
• 消息是可延展的：通过翻转任何部分的比特，恢复的消息会改变 。
• 需要所有参与方才能恢复消息 。

秘密共享 (Secret Sharing)

问题背景

公司资金管理：确保单个高管无法提取资金，确保任意两个高管无法提取资金，但希望至少有五分之三的高管同意才能发起资金提取 。这被称为 (3, 5)-门限方案 ((3, 5)-threshold scheme) 。

Shamir 秘密共享 (Shamir’s Secret Sharing, SSS) 是一种将秘密分成 $m$ 份的算法，其中只需要 $n$ 份就可以重构原始秘密 。

Shamir 秘密共享 (Shamir’s Secret Sharing, SSS) 原理

一个 $n$ 次多项式可以通过该多项式上的 $n+1$ 个点唯一确定 。 例如：$y = ax^2 + bx + c$ 。

• 只有 2 个点时，系数 $a, b, c$ 有无限多种可能性 。
• 有 3 个点时，系数可以唯一确定 。

Trent 希望将消息 $m$ 分发给 $n$ 个用户，其中任何 $t$ 个用户 ($1 \le t \le n$) 组成的群体都可以恢复 $m$ 。

1. 选择一个素数 $p > \max{m, n}$ 。
2. 创建多项式 $f(x) = m + a_1x + a_2x^2 + \dots + a_{t-1}x^{t-1}$，其中系数 $0 \le a_i < p$ 是随机且独立的 。
3. Trent 选择 $n$ 个不同的点 $x_i$，满足 $1 \le x_i < p$ 。
4. Trent 将 $(x_i, f(x_i))$ 交给第 $i$ 个人 。

一旦 $t$ 个人汇集了他们的 $(x_i, f(x_i))$ 点，就可以重构多项式 $f(x)$，并恢复 $m$ 。

承诺协议 (Commitment Protocols)

比特承诺方案 (Bit Commitment Schemes)

问题：Alice 想给 Bob 发送一个秘密消息，该消息只能在稍后由 Alice 提供进一步信息后才能由 Bob 揭示 。Bob 可以检查消息是否未被更改 。

承诺 (Commitment):

1. Bob 生成一个随机字符串 $r$，并发送给 Alice 。
2. Alice 生成一个随机密钥 $k$，并向 Bob 发送加密结果 $E_k(r||m)$ 。

揭示 (Revelation):

1. Alice 将密钥 $k$ 发送给 Bob 。
2. Bob 用 $k$ 解密消息，并验证承诺中的 $r$ 。

讨论:

• $r$ 用于保证新鲜度 (freshness)，并阻止 Alice 找到具有 $E_k(m) = E_{k’}(m_2)$ 的碰撞消息 。她需要在发送 $E_k(r||m)$ 时就承诺 $m$ 。
• Bob 在揭示阶段之前不知道 $k$ 。

非交互式比特承诺 (Non-interactive Bit Commitment)

承诺 (Commitment):

1. Alice 生成随机字符串 $r, s$，并计算 $x = h(r||s||m)$(也称为 blob)，其中 $m$ 是秘密消息 。
2. Alice 将 $(r, x)$ 发送给 Bob 。

揭示 (Revelation):

1. Alice 将 $(s, m)$ 的剩余数据发送给 Bob 。
2. Bob 验证 $h(r||s||m)$ 是否与他收到的 $x$ 相同 。

讨论:

• Bob 不需要发送任何消息 。
• Alice 发送一条消息进行承诺，再发送一条消息进行揭示 。
• 由于 $h$ 是一个密码学哈希函数 (crypto hash function)，Alice 无法找到 $t$ 使得 $h(r||s||m) = h(r||t||m)$ 。
• $s$ 保持秘密，这样 Bob 就无法在 Alice 发送 $m$ 之前暴力破解消息空间 。

使用承诺方案实现公平抛硬币 (Fair Coin Flipping using Commitment Schemes)

问题：Alice 和 Bob 想决定谁先在在线象棋游戏中走棋 。他们想通过抛硬币来解决这个问题 。但 Alice 不信任 Bob 抛硬币，Bob 也不信任 Alice 抛硬币 。如何公平地抛硬币？

1. Alice 使用承诺方案对比特 $b$ 进行承诺 。
2. Bob 尝试猜测该比特 。
3. Alice 揭示该比特：如果 Bob 猜对了，他赢得抛硬币；否则，Alice 获胜 。

讨论:

• 该算法的安全性取决于承诺方案的安全性 。
• 特别地，承诺方案的 blob 不应泄露任何关于内部消息的信息(例如低位比特) 。

使用公钥实现公平抛硬币 (Fair Coin Flipping using Public Keys)

我们需要一个可交换的公钥密码系统 (commutative public key cryptosystem)，使得 $E_A(E_B(m)) = E_B(E_A(m))$ 。

执行公平抛硬币的步骤：

1. Alice 和 Bob 分别生成可交换的公钥 A 和 B 。
2. Alice 生成两个秘密随机数 $r_T$ 和 $r_H$ 。
3. Alice 以随机顺序向 Bob 发送加密消息 $E_A(\text{heads}, r_H)$ 和 $E_A(\text{tails}, r_T)$ 。
4. Bob 选择 Alice 的一条消息，称之为 $E_A(x)$，并向 Alice 发送加密消息 $E_B(E_A(x))$ 。
5. Alice 解密 Bob 的消息并将结果 $E_B(x)$ 发回 。
6. 现在 Bob 可以解密 $E_B(x)$ 并看到他选择的是 $(\text{heads}, r_H)$ 还是 $(\text{tails}, r_T)$ 。然后 Bob 将结果发回给 Alice 。
7. Alice 验证 Bob 的响应是否与她的 $r_T$ 或 $r_H$ 匹配 。

讨论:

• 该算法是自洽的 (self-enforcing)：任何一方都可以检测到另一方作弊，而无需可信第三方 。
• Bob 比 Alice 先知道抛硬币的结果 。他不能改变结果，但他可能会延迟结果(“将硬币掷入井中”) 。
• 抛硬币可用于会话密钥生成 (session key generation)，因为任何一方都无法影响每次抛掷的结果 。例如，在 Diffie-Hellman 密钥交换中，一方在另一方之后选择指数 。

心理扑克 (Mental Poker)

如何使用可交换密钥对公平地向 Alice 和 Bob 发牌？

1. Bob 加密 52 条消息：(梅花二)，…，(黑桃 A)，使用他的私钥，并以随机顺序(洗牌后)全部发送给 Alice 。
2. Alice 随机选择 5 条加密消息并发送给 Bob。Bob 解密这些消息：这是他的手牌 。
3. Alice 再选择 5 条加密消息，用她的私钥加密后发送给 Bob 。Bob 解密这些消息并发回给 Alice。Alice 解密这些消息：这是她的手牌 。
4. (对于更多的牌，重复步骤 2 和 3)
5. ==游戏结束时，Alice 和 Bob 公开他们的私钥以确保没有人作弊 。==

隐蔽信道 (Covert Channels) 与隐写术 (Steganography)

隐蔽信道

Alice 和 Bob 想建立一个隐蔽(或潜意识)信道 (covert/subliminal channel)，以便在监视通信信道的看守 Walter 存在的情况下秘密通信 。Walter 可以看到他们的消息，并可能试图通过植入虚假消息来欺骗他们 。

最简单的层面：Alice 和 Bob 可以使用隐写术(信息隐藏)在没有人怀疑存在消息的地方发送隐藏消息 。隐写术不是密码学：它是“通过默默无闻实现安全”(security through obscurity) 。隐写术通常与密码学一起使用 。

文本隐写术 (Text Steganography)

使用文本发送比特的解决方案：

• 计算：句子中的单词数：如果为偶数 $\rightarrow 0$；如果为奇数 $\rightarrow 1$ 。
• 同义词替换 (Synonym substitution)：每句约 0.67 比特 。
• 句法替换 (Syntactic substitution)：每句约 0.5 比特 。
• 上下文同义词替换和顶点编码 (Contextual Synonym Substitution and Vertex Coding)：每句约 1 比特 。

例如，使用以下表格 ：

词 (Word)	值 (Value)
Labor	00
Project	01
Task	10
Undertaking	11

词 (Word)	值 (Value)
Complete	0
Finish	1

将 “He finished the project” 编码为 “010”，可以转换为 “He completed the task” 。

图像隐写术 (Image Steganography)

假设一个 $32 \times 32$ 像素的灰度图像，每个像素是一个 8 比特的值 (0-255) 。一个像素包含的比特如下 ：

128s	64s	32s	16s	8s	4s	2s	1s

如果我们愿意牺牲一点图像质量，我们可以舍弃最低有效位 (least-significant bit, LSB) ：

128s	64s	32s	16s	8s	4s	2s	消息 (msg)

对图像的更改对于随意观察者来说是难以察觉的 。我们现在可以编码一个 $32 \times 32 = 1024$ 比特(128 个字符)的秘密消息 ！

• 如果使用彩色图像 (RGB)，每个像素可以使用 3 个比特 。
• 将分辨率加倍，可隐藏的数据量会变为原来的四倍 。
• 如果容忍一些质量损失，甚至可以每个像素使用 6 个比特(每个颜色通道 2 个比特) 。
• 存在适用于有损重压缩甚至调整大小的技术 。

网络隐写术 (Network Steganography)

• Loki：使用 ICMP 类型 0(回显应答)和类型 8(回显请求)数据包中的数据字段的双向隐蔽 UNIX shell 客户端 。
• ICMP 后门 (ICMP Backdoor)：可重用的隧道库，消息被分段以使其看起来更像 ping 数据包(64 字节的倍数) 。
• Rwwwshell：后门将请求作为 HTTP 响应数据包发出，命令的输出作为 cgi 脚本的 HTTP GET 从从属端返回 。
• AckCmd：一个通过 TCP ACK 数据包发送所有流量的命令 shell 。仅用于允许客户端通过某些防火墙联系服务器 。

网络安全概述 (Network Security Overview)

网络安全产品与局限性

互联网安全供应商提供各种产品来帮助防御安全攻击，例如：

• 网络扫描工具 (Network Scanning Tools)
• 防火墙 (Firewalls)
• 虚拟专用网络 (Virtual Private Networks, VPN)
• 入侵检测系统 (Intrusion Detection Systems, IDS)
• 公钥基础设施 (Public Key Infrastructure, PKI)
• 生物识别技术 (Biometrics)

这些产品存在局限性：

• 黑客也运行网络扫描工具。
• 防火墙通常是带有漏洞的“墙”。
• VPN 工作在互联网之上。
• IDS 对旧攻击有效，对新攻击效果不佳。
• PKI 需要复杂的基础设施和管理。
• 生物识别技术可能被欺骗，并且无法撤销或颁发新密钥。

网络安全的挑战

• 互联网本身设计上不安全，存在许多漏洞：
  • 操作系统 (Operating systems)
  • IP 协议栈和 802.11/WEP
  • 用户协议，如 Telnet, FTP, RSH 和 HTTP
  • 网络协议，如 BGP 和 DNS
  • 网络管理协议，如 SNMP
  • 编程语言(如 C 语言)的安全特性
• 缺乏适当的基础设施
• 缺乏高质量的开发人员
• 糟糕的设计和编程实践(设计选择、实现、假设等)

分布式拒绝服务 (DDoS) 攻击

• 1999 年 7 月：计算机应急响应小组 (CERT) 发布关于拒绝服务攻击的警告。
• 2000 年 2 月：Yahoo(3 小时中断)、Ebay(5 小时中断)、Amazon(3 小时 45 分钟中断)、CNN(3 小时 30 分钟中断)、ZDnet(3 小时 15 分钟中断)、E*trade(2 小时 45 分钟中断)等网站遭受攻击 。
• 攻击方式：针对连接这些网站到互联网的路由器进行放大的拒绝服务攻击(放大的 Ping 和 SYN 洪水)。

僵尸网络 (Botnet) 攻击

• Conficker 蠕虫 (Conficker Worm) (2008) 针对微软 Windows 系统，创建了一个计算能力超过任何现有超级计算机的僵尸网络 。它可以通过创建多个变体来“反击”，这些变体修复了以前的漏洞，并且更难阻止 。
• Conficker 在针对该漏洞的补丁向公众发布三周后首次发布 。
• 在一个完美的世界里，一个已修补的漏洞怎么会引发问题？ 答案是并非所有系统都及时打补丁。
• 2008 年 10 月 23 日：针对该问题的补丁 (MS08-067) 发布。
• 2009 年 1 月：30% (或更多) 的 Windows 个人电脑仍未打补丁。
• 该漏洞影响 Windows 2000, Windows XP, Windows Vista, Windows Server 2003, Windows Server 2008 。

互联网经济带来的挑战

组织需要理解互联网带来众多优势的同时，也带来了同样巨大的劣势：

• 信息泄露(例如美国政府文件泄露给维基解密)
• $24 \times 7 \times 365$ 全天候向世界暴露内部运作
• 因泄露风险增加而导致的相关风险增加
• 攻击者发起攻击并逍遥法外的便捷性
• 没有统一的互联网警察，也没有国际管辖权

互联网安全漏洞

• 安全总是滞后的：发现、报告、建议和修复问题之间总是存在显著的时间延迟。
• 安全通常是被动的。
• 安全被视为成本中心，而非利润中心。
• 互联网的同质性 (Homogenous nature)。
• 互联网的异质性 (Heterogeneous nature)。
• 政治问题，出口限制。
• 专利。
• 使用互联网的人类本身就是问题。

互联网的单一培养皿 (Monoculture)

• 在整个互联网中，许多工具占据巨大的市场主导地位，例如 OpenSSL、运行 Windows 的计算机、运行 Bind 的域名服务器、运行 Apache 或 Nginx 的 Web 服务器等 。
• 软件在不同版本之间几乎总是完全相同的副本 。如果你能攻破一个版本，你就能攻破所有版本 。因此，针对这些工具中任何一个的攻击都将导致大量机器被控制 。
• 物联网 (IoT)：越来越多的设备(智能手机、平板电脑、手表、心脏起搏器、冰箱)正在联网，而安全性甚至不在其功能列表中 。

关于安全的普遍误解

• 普遍的安全理念是，如果你保护了边界，你就可以让内部保持柔软和黏糊糊(像棉花糖一样)。这一直是一个非常糟糕的假设 。
• 如今情况更糟：
  • 你的网络没有清晰的边界 。
  • 你不能相信任何人 。
  • 进入网络的途径太多了：
    • 互联网连接(T1、电缆、ADSL、帧中继等)
    • 每一台机器，包括四年前实习生设置的、运行着此后无人更新的系统或工具的机器
    • 802.11 无线网络(使用优质天线和放大器的记录远超 15 公里)
    • 第三方连接(供应商、合作伙伴、客户等)
  • 用户是 90% 问题的根源，而且他们已经在内部了！

安全缺陷 (Security Flaws)

现代安全仍然存在非现代安全的所有问题：唯一的区别是技术更加普遍，所以我们有更多的缺陷 。 OWASP Top 10 变化示例(2017 vs 2021)： 许多安全缺陷是由于缺乏强身份验证、糟糕的编程和薄弱的安全管理造成的 。

2017	2021
A01: 注入 (Injection)	A01: 失效的访问控制 (Broken Access Control)
A02: 失效的身份认证 (Broken Authentication)	A02: 加密失败 (Cryptographic Failures)
A03: 敏感数据泄露 (Sensitive Data Exposure)	A03: 注入 (Injection)
A04: XML 外部实体 (XML External Entities, XXE)	(新) A04: 不安全设计 (Insecure Design)
A05: 失效的访问控制 (Broken Access Control)	A05: 安全配置错误 (Security Misconfiguration)
A06: 安全配置错误 (Security Misconfiguration)	A06: 易受攻击和过时的组件 (Vulnerable and Outdated Components)
A07: 跨站脚本 (Cross-Site Scripting, XSS)	A07: 身份识别和身份验证失败 (Identification and Authentication Failures)
A08: 不安全的反序列化 (Insecure Deserialization)	(新) A08: 软件和数据完整性故障 (Software and Data Integrity Failures)
A09: 使用含有已知漏洞的组件 (Using Components with Known Vulnerabilities)	A09: 安全日志和监控失败 (Security Logging and Monitoring Failures)*
A10: 日志记录和监控不足 (Insufficient Logging & Monitoring)	(新) A10: 服务器端请求伪造 (Server-Side Request Forgery, SSRF)*

*来自调查 (From the Survey)

可能考点及示例考题

考点

• 秘密分割与秘密共享的区别与联系。
• 基于 XOR 的秘密分割的原理、优点和缺点。
• Shamir 秘密共享方案的核心思想(多项式插值)和步骤。
• 比特承诺方案的目的和两种实现方式(交互式与非交互式)的关键区别。
• 非交互式比特承诺中随机字符串 s 的作用。
• 使用承诺方案或公钥实现公平抛硬币的流程和安全性分析。
• 公平抛硬币方案中可能存在的作弊方式或延迟策略。
• 隐写术与密码学的区别。
• 至少列举两种文本隐写术或图像隐写术的基本原理。
• 网络隐写术的例子及其利用的网络协议。
• 互联网设计本身存在的安全缺陷。
• DDoS 攻击和僵尸网络攻击的基本原理和危害。
• Conficker 蠕虫案例揭示了哪些安全问题。
• “边界安全”理念的局限性。
• OWASP Top 10 中常见的安全漏洞类型。

示例考题

1. 问题： 解释为什么在 Shamir 秘密共享方案中，需要 $t$ 个份额才能恢复秘密，而少于 $t$ 个份额则无法获得关于秘密的任何信息。 参考答案：

   • 中文：在 Shamir 秘密共享方案中，秘密被编码为一个 $t-1$ 次多项式的常数项。根据代数基本定理，一个 $t-1$ 次多项式由其上的 $t$ 个不同点唯一确定。因此，拥有 $t$ 个份额(即多项式上的 $t$ 个点)足以通过插值法重构整个多项式，进而得到作为常数项的秘密。如果只有少于 $t$ 个份额(例如 $t-1$ 个点)，则存在无限多个 $t-1$ 次多项式通过这些点，因此无法唯一确定原始多项式，也就无法恢复秘密。每个少于 $t$ 个份额的组合都与所有可能的秘密值兼容。
   • English: In Shamir’s Secret Sharing scheme, the secret is encoded as the constant term of a polynomial of degree $t-1$. According to the fundamental theorem of algebra, a polynomial of degree $t-1$ is uniquely determined by $t$ distinct points on it. Therefore, possessing $t$ shares (i.e., $t$ points on the polynomial) is sufficient to reconstruct the entire polynomial through interpolation, and thus obtain the secret, which is the constant term. If there are fewer than $t$ shares (e.g., $t-1$ points), there are infinitely many polynomials of degree $t-1$ that can pass through these points. Consequently, the original polynomial cannot be uniquely determined, and the secret cannot be recovered. Every combination of fewer than $t$ shares is consistent with all possible secret values.

2. 问题： 在非交互式比特承诺方案 $x = h(r||s||m)$ 中，随机字符串 $s$ 的作用是什么？如果去除 $s$，即承诺变为 $x = h(r||m)$，会产生什么安全问题？ 参考答案：

   • 中文：随机字符串 $s$ 的主要作用是防止接收方(Bob)在发送方(Alice)揭示消息 $m$ 之前，通过暴力破解或猜测来提前获知消息 $m$。即使 Bob 知道 $r$ 和承诺值 $x$，由于 $s$ 是 Alice 保密的随机串，Bob 无法通过尝试不同的 $m’$ 来验证 $h(r||m’)$ 是否等于 $x$，因为他不知道正确的 $s$。如果去除 $s$，承诺变为 $x = h(r||m)$。如果消息空间 $m$ 较小(例如，一个比特或从一个小数目集合中选择)，Bob 就可以在收到承诺 $x$ 后，通过尝试所有可能的 $m_i$，计算 $h(r||m_i)$ 并与 $x$ 比较，从而在 Alice 揭示之前就可能猜出或确定 $m$。
   • English: The primary role of the random string $s$ is to prevent the receiver (Bob) from discovering the message $m$ by brute-forcing or guessing before the sender (Alice) reveals it. Even if Bob knows $r$ and the commitment value $x$, because $s$ is a random string kept secret by Alice, Bob cannot verify if $h(r||m’)$ equals $x$ by trying different $m’$ values, as he does not know the correct $s$. If $s$ were removed, and the commitment became $x = h(r||m)$, then if the message space for $m$ is small (e.g., a single bit or selected from a small set), Bob could, after receiving the commitment $x$, try all possible $m_i$, compute $h(r||m_i)$, and compare it with $x$. This could allow Bob to guess or determine $m$ before Alice’s revelation.

3. 问题： 描述一种利用图像最低有效位 (LSB) 进行隐写的方法，并讨论其优缺点。 参考答案：

   • 中文：基于图像最低有效位 (LSB) 的隐写方法是将秘密信息的比特嵌入到图像像素值的最低有效位中。例如，对于一个 8 位灰度图像，每个像素值范围是 0-255。我们可以用秘密信息的 1 比特替换每个像素值的 LSB。如果秘密信息是 ‘101’，我们可以依次修改三个像素的 LSB 为 1, 0, 1。
     • 优点： 实现简单，对图像的视觉改变通常非常微小，人眼难以察觉，尤其是在颜色丰富或纹理复杂的图像中。可以嵌入相对较多的数据量(例如，一个 $1024 \times 768$ 的 24 位彩色图像，每个像素的每个颜色通道修改 1 个 LSB，可以隐藏 $1024 \times 768 \times 3$ 比特的信息)。
     • 缺点： 非常脆弱，容易被检测和破坏。任何对图像的轻微处理，如图像压缩(尤其是有损压缩如 JPEG)、缩放、裁剪、滤波等，都可能轻易破坏隐藏的信息。隐写分析工具也相对容易检测 LSB 隐写。其安全性依赖于“默默无闻”，而非密码学的强度。
   • English: The Least Significant Bit (LSB) steganography method for images involves embedding bits of secret information into the least significant bits of the image pixel values. For example, in an 8-bit grayscale image, each pixel value ranges from 0-255. We can replace the LSB of each pixel’s value with 1 bit of the secret message. If the secret message is ‘101’, we can modify the LSBs of three consecutive pixels to 1, 0, and 1 respectively.
     • Advantages: It is simple to implement, and the visual changes to the image are typically very minor and imperceptible to the human eye, especially in images with rich colors or complex textures. A relatively large amount of data can be embedded (e.g., a $1024 \times 768$ 24-bit color image, modifying 1 LSB per color channel per pixel, can hide $1024 \times 768 \times 3$ bits of information).
     • Disadvantages: It is very fragile and easily detected and destroyed. Any slight processing of the image, such as image compression (especially lossy compression like JPEG), scaling, cropping, or filtering, can easily destroy the hidden information. Steganalysis tools can also detect LSB steganography relatively easily. Its security relies on “security through obscurity” rather than cryptographic strength.