密码学中的时间

大家好！我是大聪明-PLUS！

时间及其测量对于应用密码学至关重要，它影响着密码系统应用的各个方面。有时这种影响是最直接、最明显的，有时则是隐蔽、难以察觉的。

破解时间

除了绝对强大的密码之外，任何密码都可能被破解。破解过程需要一些时间。如果您每秒尝试一万亿次128位对称密钥，则需要花费地球一百万年（约10万亿次）的时间来验证所有2^128个密钥。通常，即使误差达到数量级，破解过程也会花费很长时间。但几秒、几年——这些都是时间间隔。

对于一个完美的密码来说，为了有较高的概率猜出密钥，你需要尝试一半的密钥空间。对于2,128来说，这并没有多大帮助：2,127仍然需要“数万亿”。但如果密码设计存在缺陷，导致漏洞允许将搜索空间细分为更小的区域，那么成功的搜索就可以花费更少的时间。例如，上一段中提到的万亿功率机器可以在不到五分钟的时间内耗尽 2,48 个密钥。

在评估密码学的抗攻击性时，通常使用时间这样的参数。时间简单地用操作次数来衡量。因为很难确定标准的密码学“枚举秒”，但可以确定实现密码数学变换的基本操作。然而，我们讨论的仍然是与时间相对应的特定计算量。这就是破解时间。或者说，以高概率解密所需的操作次数。

实际上，所需的密码强度与受保护消息中信息的相关时间有关。如果消息中的信息在一天内过期，那么原则上可以使用保证需要一个月才能破解的密码来保护此消息。好吧，或者十亿年。实用的互联网密码，例如 TLS/HTTPS 中的 AES，估计强度需要数十亿年的计算。这肯定足够了。虽然，至于“肯定”，没有人知道确切时间。但是，不清楚数据需要保密多长时间的情况时有发生。更糟糕的是：25 年前需要数年才能破解的东西现在只需要几天——嗯，只要进入超级计算机，它就会在一分钟内给出答案。

计算加速。这也是一个时间问题。量子计算机的出现已经期待了很多年，甚至很长一段时间了。它们至今仍未出现，但现在记录的通信量可能在五十年后被量子计算机解密，这种威胁是存在的。事实上，你可以自信地说，距离必要的量子计算机的诞生还有二十年——这是一个非常好的策略，完全有博弈论的支持。

如果你认为量子计算机对 AES 之类的对称密码效果不大，那你就错了。是的，已知的通用算法只能将搜索速度提高一半——平方根，即 2128会变成 264 ，所以只需要2256就足以保证抵抗攻击。然而，这些都是通用算法，但对于特定的密码，并非一定不会出现一些改进的量子算法，能够在合理的时间内破解这些密码。

量子计算机的主要发展方向并非攻克对称密钥系统，而是攻克用于密钥交换的非对称密钥系统。也就是说，为了获取共用的对称密钥，需要使用非对称加密系统（通常是Diffie-Hellman协议）。如果在可预见的未来能够建造出量子计算机，那么Shor的量子算法就能攻破该加密系统。目前，量子计算机甚至还没有学会分解任意数，而同一传输层安全协议（TLS）中的密钥交换已经受到具有后量子抗性的加密系统的保护，目前还未发现量子算法能够快速攻破这些加密系统。

时间作为坐标

物理学中没有时间的概念，但存在周期性事件的计数器。如今，地球上不同地点的精确时间几乎同步，因此计数可以得到一个稳定的递增序列。在应用密码学中，这样的序列被称为计数器。它们可用于创建通用坐标系，例如在计算一次性密码时。

一个常见的例子是 TOTP（基于时间的一次性密码）协议：该协议的各方拥有一个共同的秘密，并根据当前时刻计算令牌。因此，为了使该方法有效，各方也必须拥有共同的时间。如果您使用 TOTP（这是目前非常流行的“第二因素”来源，由于某种原因它被认为是可靠的），那么一旦令牌生成系统和验证系统中的时钟出现显著差异，令牌就会失效。这是联系一次性密码技术支持的最常见原因之一：“哦，我的令牌不能用了！别生气：我们还是同步一下时间吧！”

时间在这里再次直接影响加密操作：一次性代码（令牌）值的计算需要使用时间戳；时间坐标的稳定性对于该方案的有效性至关重要。如果有人窃取了 TOTP 密钥，那么这个人就能在任何时间（甚至是未来）获取令牌。

要理解某个动作先于某个时间点发生，需要采取特殊的行动。在古代，为了确保一项发现的优先权，人们甚至会公开发表字谜，以便后来能够被掌握关键信息（即一项重要发现的构成要素）的人成功破译。就连牛顿也做到了。事实上，关键信息和字谜就是密码学。

可信时间戳用于数字签名基础设施，以验证给定签名是否在给定时间之前存在。通常，此类确认由专门的时间戳提供商提供，这些提供商会以加密方式验证其签发的时间戳。正确“处理过去”通常是数字文档管理中的一个大问题。假设有一份文档使用一对密钥中的某个密钥签名，该密钥的公共部分已由证书认证。但该密钥的证书五年前就已过期。我们还能信任这份文档上的签名吗？

看起来我们应该相信这一点，因为我们不是在签名，而是在检查签名，而且在签名时，证书是有效的。但如果十年过去了，这一切都只是猜测：密钥之所以会过期是有原因的——也许在过去，有人建造了一台量子计算机，窃取了链上的所有密钥，并对文档进行了签名，从而追溯性地签发了伪造的证书。所以你不能再相信签名了。由于文档流的数字化程度越来越高，这真是令人沮丧。这就是为什么我们需要一些哈希函数值链和类似的解决方案，其中最前沿的被称为“区块链”：区块链的主要作用是严格固定记录的顺序——什么先出现，什么后出现。例如，谁先使用了一部分比特币。时间坐标对于其稳定性至关重要。然而，谁能保证哈希函数链的安全性呢？有人说，合成黄金的难度背后的数学原理比SHA-256更强大。是的，即使有魔法石的存在，也是如此。

时间间隔的准确性

在应用密码学中，时间计算的准确性同样重要。TLS 证书中的有效期就是一个最简单的例子。它指定了两个值：不早于此，不晚于此。如果在验证过程中时钟显示的时间与预期不符，则可能是证书尚未在本地运行。这就是狭义相对论。

本地时钟落后于 CA 时钟的问题被认为非常普遍，例如，Let’s Encrypt CA 故意将证书生效时间设置为比证书颁发时间早一个小时！这就像一台时光机，加密的，但虚拟的。不仅 Let’s Encrypt 这样做，而且强行“回溯” TLS 证书的做法也不受欢迎。对于像 Let’s Encrypt 这样的快速证书颁发自动化系统来说，合理的“回溯”非常重要，因为新颁发的证书已经到达服务器，而时钟滞后的用户无法访问网站，因为在他们的“时间范围”内，证书尚未开始生效。在验证证书时，这两个时间界限都很重要，正如：不早不晚。

确定证书中设置的时间是否落后并不难：证书透明度日志可以解决此问题。日志会提供其时间戳，即所谓的 SCT 标记。这些时间戳包含在证书中，指示日志服务看到证书数据的时间，每个人都可以独立比较时间（例如，TCI网站分析服务会输出 SCT 值）。

证书透明度 (CT) 是各种应用密码学方法的大规模实施案例之一。证书的时间间隔会产生一种有趣的效果。在 CT 中，所有已颁发的证书都必须写入日志。更准确地说，必须写入专门设计的预证书，但在这里我们将所有内容都称为证书，因为这对密码学中关于时间的叙述意义不大。任何人都可以从日志中读取证书——这就是 CT 的意义所在。但是，现在很多 TLS 证书都是按单位时间颁发的——它们的流量如此之大，以至于 CT 日志膨胀得太快。日志膨胀会导致存储日志的磁盘空间耗尽。这就是时间分片被发明的原因。

CT日志中的时间分片是指为每个时间间隔的证书维护单独的日志。例如，假设我们为2026年7月至12月期间创建一个单独的日志。现在，每个证书都会按照证书到期时间戳指示的时间间隔写入日志。请注意，这一点很重要：证书按到期日期而非生效日期排序，这使得日志能够提前计算。同样，时间在这里起着主要作用。

时间维度的泄漏

还有另一方面：密码系统实现内部状态的信息泄露，与密码操作的不同执行时间有关。这是什么意思？让我们采用一些有效的信息密码保护手段，并测量这种保护手段在使用不同数据执行相同操作时花费了多少微秒。例如，让我们签署不同的文件，测量签名时间。如果我们设法找到数据和密码操作执行时间之间的相关性，那么我们可能能够泄露密钥，因为签名算法是已知的。因此，关键操作的实现方式是，无论输入数据如何，它们都在固定的时间内执行。这需要特殊的算法，并且并不总是可行的。请注意，该方案不仅适用于计算机系统，也适用于机电机器。

一个教科书式的案例，现在应该作为应用密码程序开发专门课程的开篇，就是由于位串比较操作执行不当而导致的机密泄露。“正面”执行意味着两个字符串的比较在检测到第一个差异时停止。实际上，对于不同的字符串，一位差异就足够了。此时，输出与机密值的比较结果所需的时间（更准确地说，是周期数）取决于输入字符串的组成。

假设一个存在漏洞的系统在指定了正确的 128 位密钥字符串后会发出身份验证令牌。然后，攻击者可以向存在漏洞的系统发送任意数据，并测量每个字符串变体的处理时间。看起来，在保证密钥搜索的情况下进行完整的搜索仍然需要 2,128 个请求。这看起来很长。但这只是看起来如此。此漏洞的巧妙之处在于它通过泄漏来“压缩”时间：攻击者可以确定位发生分歧的位置。如果系统的响应尽可能快，则第一位不匹配。我们反转这位 - 现在它是正确的。我们将修改后的字符串发送出去进行验证，并测量验证时间。根据收到的时间值，我们确定哪一位与密钥不匹配。依此类推。如果比较存在漏洞，则可以在 128 个请求中以位分辨率搜索 128 位。同样的方法也适用于更实际的选项 - 使用字节：泄漏允许您确定最后一个匹配字节的位置。但在这里您必须花更长时间进行排序，因为一个字节可以容纳 256 个值。

此类泄漏属于侧信道泄漏，因为尽管它们本质上是算法性的，但它们需要测量相对于密码系统的外部参数。观察到的操作执行时间恰恰是一个外部参数。当然，不仅比较有效，这里还有许多算法选项。另一方面，在所有情况下都以足够的精度测量响应时间是远远不可能的。有时一切都进展顺利，即使算法基础存在漏洞，时间噪声也能可靠地隐藏漏洞。但情况往往恰恰相反。

记录时间。时间并不存在，但正因如此，它才如此重要。作为一个概念。