实际上的问题 II

15.1 大整数的运算

所有公钥中的计算都是基于大整数运算。如我们曾提及的，恰当地实现大整数运算并不是一件容易的事情。大多数的处理例程总是或多或少地与平台相关。能够通过平台特性得到的有效率提升总是难以发挥实际作用。比如，多数CPU有一种带进位加法运算（add-with-carry）功能来处理多字值的加法。但是在C语言或者几乎所有其他高级语言中，你是无法访问这个指令的在高级语言中进行大整数运算一般都比经过平台优化的实现速度慢几倍。这些计算也成了公钥性能的瓶颈，所以这个问题难以忽视。

15.1.1 woop技术

• woop技术的基本思想是为了验证对随机选择的小素数的取模计算。将这个问题作为密码学问题考虑。我们有一个大整数库，这个库试图欺骗我们，给出错误的结果。我们的任务是检查是否得到了正确的结果。如果只是检查这个结果和同一个库再计算一遍得到的结果是否一样，这不是一个
  好主意，因为这个库可能会一直错下去。使用woop技术，只要看看这个库是否会尝试修改我们验证计算的结果，就可以验证这个库的计算结果了。
• 我们也相信在已有的库中添加wo0p验证比在使用该库的应用中添加应用层面的验证所需要的工作量小一些。

15.1.2 检查

• 检查DH计算
  如果你没有一个使用了woop技术的库，就只能在没有woop验证的情况下工作。我们所描述的DH协议已经包括了许多检查，也就是说，结果不应该是1，结果的阶应该是q。不幸的是，这些检查不是由计算的一方来做的，而是由接收计算结果的一方进行的。总体上说，你不会想发送任何有错误的结果，因为可能会泄露一些信息，但是在这种特定情况下似乎没有什么危害。如果结果是错误的，协议不管怎样都会失败，所以这个错误会被注意到。协议不安全的时候是当你的运算库在要求计算g’的时候却返回了x，但是这种错误普通的测试很可能就会检测到。 必要的時候，我们可能會在一个没有woop验证的库上运行DH协议。我们所担心的非常罕⻅的运算错误类型不太可能从一个g’的运算中泄露x。其他的错误看起来没什么害处，尤其是当DH的计算没有⻓期秘密时。不过，我们仍然更愿意在可能的时候使用一个内置woop系统的库，只是因为安全一些。

15.1.3 检查

检查RSA加密
RSA加密更加脆弱，需要额外的检查。如果某一步出错了，可能会泄露你正在加密的秘密，或者你自己的密钥。如果不能使用woop验证，还有另外两种办法来检查RSA加密。假设实际的RSA加密包括计算c=m^mod n，其中m是消息，c是密文。为了验证这个结果，我们可以计算
c^mod n并且和m进行比较。这种方法的缺点在于计算过程很快，而验证过程很慢，并且它需要知道私钥，而我们正在进行RSA加密时通常不知道私钥。

15.1.4检查

检查RSA签名
RSA签名相当容易检查。签名者只需要运行签名验证算法即可。这是一个比较快的验证，如果有运算错误也很容易捕捉到。每个RSA签名计算都应当用这种方法去验证刚产生的签名。

15.2 更快的乘法

更快的乘法

• 有很多种方法可以让你实现模乘法，这个方法的乘法再跟一个⻓除法（long division）更快。如果你必须做很多次乘法，那么Montgomery方法是最广泛使用的方法
• Montgomery方法是一种计算(x mod n)的方法，其中x远大于n。传统的“⻓除法”是从x中减去n的倍数。Montgomery的想法更简单：重复地将x除以2。如果x是偶数，我们除以2的方法是将它的二进制表示右移一位。如果x是奇数，我们首先加一个n/2然 (当然这不会影响modn的结果)，然后将这个偶数结果除以2。(这个技术只适合n是奇数的情况，在我们的系统里通常如此。当n是偶数时可以进行一个简单的归纳。)如果n的⻓度是k位并且x不大于(n-1)²，我们总共进行k次除以2。这个结果总是在区0,...,2^n-1中，这几乎就是modn的约简结果。但是，等等！我们一直在除以2，所以这个结果还不对。 Montgomery的归约并没有给你实际的(x mod n)，而是对于某个合适的k值的x/2modn。这个归纳快一些，但是你额外地乘了一个2。有几种技巧来处理这个额外的因子。第一个不太好的主意是重
  新定义你的协议，在计算中纳人一个额外的2因子。这个方法不好，因为它混淆了不同的层次。

15.3 侧信道攻击

侧信道攻击
一些加密算法要求实现时使用不同的代码路径去处理特殊情况。
加密算法使用的CPU操作会因为处理的数据不同而造成时间消耗上的差异。在一些CPU上，乘法（RC6[108]和MARS使用）或重复数据(RC6和RCS[107]使用)的执行时间取决于输入数据。这可以导致时间攻击。

15.4 协议

协议
实现密码协议和实现通信协议区别不是那么大。最简单的办法是保持程序计数器的状态，然后简单地轮流实现协议的每一步。除非使用了多线程，否则这会使得你在等待一个回复时，程序其他部分都停止执行。这通常不是一个好主意。一个更好的解决方案是保持一个显式的协议状态，并且在每次一条消息到来时更新这个状态。这种消息驱动（message-driven）的方法在实现的时候需要稍微多花点功夫，但是它也提供了更多的灵活性。

15.4.1 安全信道上的协议

安全信道上的协议
多数的密码协议都是在非安全信道上执行的，但是有时候你需要在一个安全信道上运行密码协议。在一些情况下这是必要的。比如，每个用户都有一个和密钥分发中心（key distribution center）通信的安全信道，中心使用一个简单的协议来分发密钥给用户，允许他们之间互相通信。(Kerberos协议所做的事情与此类似。)如果你在和你已经交换过密钥的某一方运行一个密码协议，你应该使用全部的安全信道功能。并且，你需要实现重放保护。这非常容易做到，可以阻止大量针对密码协议的攻击。有
时安全信道会允许协议使用捷径。例如说，如果安全信道提供了重放保护，协议本身就不需要再次实现一次重放保护。不过，老的模块化规则认为，协议应该最小化其对安全信道的依赖程度。

15.4.2 接收一条消息

接收一条消息
当一个协议状态接收到一条消息时，需要进行若干个检查。第一个是检查这条消息是否属于这个协议。每条消息都应该由以下几个字段开头：
1)协议标识符(protocol identifier)：用来识别这是哪个协议和哪个协议版本。版本标识符是很重要的。
2)协议实例标识符(protocol instance identifier)：识别这条消息属于协议的哪个实例。 Alice 和 Bob可能同时在运行两个密钥协商协议，而我们不想混淆。
3)消息标识符(message identifier)：识别协议内部的消息。最简单的方法是给它们编号。
取決于具体情况，一部分标识符可能是隐式的。比如，对于那些在自己的TCP连接上运行的协议，端口号和相关联的套接字就可以识别出本地机器上的协议实例。协议标
识符和版本信息只需要交换一次。需要注意的是，这些信息至少需要交换一次以保证它们被包含在协议的所有认证或者签名中。
在检查了协议标识符和实例标识符之后，我们知道了一条消息应该发送给哪个协议状态。让我们假设这个协议状态刚刚接收了消息n-1并正在等待消息n。如果收到的这条
消息的确是消息n，事情很好办。只需要按照协议规则来处理即可。但如果是不同的消息号呢？
如果这条消息号比n大或者比n-1小，那么表明发生了一些奇怪的事情。不应该生成的消息，所以一定是某种伪造消息。你必须忽略这条伪造消息的内容。如果收到的是消
息n-1，可能是你发送的回复消息还没有到达。当协议运行在某种不稳定的传输系统上时，可能会发生这种事情。因为我们都知道最小化对系统其他部分的依赖，这正好满
足我们的假设。
首先，检查这条新收到的消息n-1是否和之前那条标号n-1的消息完全相同。如果它们不同，那么你必须忽略这条新消息。再次发送一条回复会被坏协议的安全性。如果消
息内容是相同的，那么只需要重发之前的回复。当然，回复的消息版本需要和之前回复的版本保持相同。
如果你由于任何一条规则忽略了这条收到的消息，就需要做第二个决定了。是否应该终止协议？答案在一定程度上取决于应用和具体情况。如果你一直在一个安全信道上
运行协议，事情就很不对了。要么是这个安全信道被破坏了，要么就是你正在交流的另外一方行为不正常。不论哪种情况，你都应该终止协议和信道。然后删除协议状态
和信道状态，包括信道密钥。
如果你在一个非安全信道上运行这个协议，那么任何一条被忽略的消息都可能是攻击者试图攻击协议的一次尝试。理想状态下你会忽略这条攻击者的消息，继续完成协
议。当然并不总是这样。比如说，如果攻击者伪造的消息n-1先到达，你会发送一条回复，而当“真正”的消息n-1来了的时候你被迫忽略它。这种情况是没有办法恢复的，
因为你没办法安全地发送第二个回复。你不知道收到的两条消息n-1中哪条是真的，所以为了能够尽可能地完成协议，你将第二条消息n-1记为一次错误，然后照常继续执
行协议。如果你回复的 消息来自于攻击者，协议最终仍会失败，因为密码协议的设计目的是正是阻止攻击者成功地和一个参与者完成协议。

15.4.3 超时设定

超时设定
任何协议都包括超时设定。如果你没有在一段时间内收到消息的响应，可以重新发送最后一条消息。在几次重发之后，你不得不放弃。当你无法和另一方通信时，继续执行协议是没有意义的。

第十六章 密钥管理

16.1 时钟的使用

16.1.1 有效期

有效期
在多数情况下，需要限制文件的有效期。在现实生活中，我们也通常会看到有限的有效期。支票、⻜机票、代金券、优惠券甚至是版权都有期限的有效期。限制数字文档
有效期的标准方法是在文档内部包含有效期。但为了检查一个文档是否到期，我们需要知道当前时间，因此就要用到时钟。

16.1.2 唯一值

唯一值
时钟另一个重要功能（如果它的精度足够高的话）是可以为单个机器提供一个唯一值。我们已经在几个地方用到了瞬时值(nonce)。瞬时值的主要特点是任何一个值都不会被使用两次。

16.1.3 单调性

单调性
时间的一个有用的性质是它会一直不断向前走，从来不会停止或倒退。有一些密码协议用到了这个性质。在密码协议中包含时间信息可以防止攻击者把旧的消息当作有效消息放到当前协议中。毕竟，编码在那些信息中的时间不在当前协议的时间跨度内。时钟的另一个非常重要的应用是审计和日志。

16.1.4 实时交易

实时交易为了支持实时支付，银行需要运行实时金融交易系统。为了让审计能够完成，应该有一个清晰的交易序列。给定两个交易A和B，了解两者哪个先发生是很重要的，因为其
中一个交易的结果取决于另一个是否已经完成。记录这一序列的最简单的方法是给每一个交易一个时间戳，但这需要在有可靠时钟的前提下才可行。一个不可靠的时钟也许会给出错误的时间。如果时钟只是偶然地向回移动的话，还不会有多大危险，因为很容易就能够发现当前时间比上次交易完成时的时间戳大。然而，如果时钟是向前移动的话，就会出现问题。假定当时钟设置为2020年时，完成了半个小时的交易。你不能只是改变那些交易的时间戳，人工修改金融记录是不能被接受的。问题是你在2020年之前不能进行任何新的交易，因为那将违反了由时间戳所决定的交易的顺序。对于这个问题有解决方案，但如果能有一个可靠的时钟肯定是最好的。

16.2 使用实时时钟芯片

• 使用实时时钟芯片
  大多数台式计算机包含一个实时时钟芯片和一块小电池，这是安装在你的机器中的一个非常小的数字钟。这就是为什么计算机会在你早上开机的时候知道现在的时间是几点。那么，为什么不就简单地使用这个时钟时间呢？实时时钟芯片对一般的普通应用来说是足够了，但在安全系统中，我们必须强制要求更高的标准。作为安全系统的一部分，即使攻击者试图去操纵时钟，它也应该给出正确的时间来。第二个原因是时钟有时会有故障。在一般的应用中，时钟显示错误的时间很恼人，但是并不危险。如果
  时钟是安全系统的一部分，那么它的故障就会带来更大的危害。在一般硬件中的实时时钟并不像我们所需要的那样可靠和安全。在过去的十年里，我们已经亲自经历了几次实时时钟芯片的故障。而且，那些故障都是自发的，没有恶意攻击者尝试去破坏它。大多数故障的原因很简单：在台旧机器上，由于电池电量不足，时钟就停止了或者被重新设置成1980年。或是有一天你启动机器，时钟已经设置成2028年的某一天了。有时候一个时钟可能会发生漂移，比实际时间慢一点或者快一点。除了实时时钟的
  意外错误，我们还必须考虑主动攻击。有些人可能尝试用某种方式操纵时钟。根据计算机的具体情况，改变时钟时间可能会容易也可能很困难，在有些系统中只有特定的管理员才有权限改变时钟，而这些系统的时钟可以被任何人修改。

16.3 安全性威胁

安全性威胁

16.3.1 时钟后置

时钟后置
假定攻击者能够把时钟设为过去的任何一个时间。这会导致各种可能的危害，机器会错误地相信自己生活在过去。

16.3.2 时钟停止

时钟停止
如果时钟停止了，时间似乎就静止了。这时事情可能就无法完成。而且很多系统可能会有无法预测的行为。这种情况引起的简单问题类似于交易记录和报告的时间错误了，一则交易的准确时间可以造成很严重的经济上的后果，发送一份印有错误时间和日期的正式报告可能导致严重的混乱情况。

16.3.3 时钟前置

时钟前置
把时钟向前设置会使计算机认为自己生活在将来，这会导致简单的拒绝服务攻击。

16.4 建立可靠的时钟

大多数计算机有或者可以实现某种计数器，在电脑启动的时候开始计数。这也许是CPU时钟循环的计数，也许是刷新计数器或其他类似的计数器。这个计数器能用来记录自从最后一次重新启动之后的时间。它不是时钟，因为它不能提供具体时间的信息，但它能用来测量两个事件（这两个事件都是在最后一次重启之后发生的）之间所经过的时间

第十七章 密钥服务器

17.1 基本概念

基本概念
我们假定每个人都与密钥服务器建立一个共享密钥。例如，Alice产生一个只有她和密钥服务器知道的密钥K4，Bob也建立一个只有他和密钥服务器知道的密钥KB。其他参与方都以同样的方式建立密钥。现在假定 Alice想与 Bob进行通信。她没有与 Bob 通信的密钥，但她可以与密钥服务器安全地通信。密钥服务器反过来也能与 Bob 安全地通信。我们能简单地把所有的通信传给密钥服务器，把密钥服务器当成一个巨大的邮局。但对密钥服务器来说存在一些困难，因为它将不得不处理大量的通信。一个更好的解决方案是，让密钥服务器建立一个 Alice 和 Bob 的共享密钥 KB。

17.2 Kerberos协议

协议
当 Alice 想与 Bob 对话时，她首先与密钥服务器联系。密钥服务器向 Alice 发送一个新的密钥 KAB 以及使用 Bob 的密钥 Kg 对 KAB 加密后的值。这些消息都用 K4 加
密，因此只有 Alice 能读。Alice 解密之后，再用 KB 加密之后的消息，这条消息称 为标签 (ticket)，发送给 Bob。Bob 对它解密，然后得到 KAB，这是只有 Alice 和
Bob 知道的会话密钥，当然，密钥服务器也知道。Kerberos 的一个特点是密钥服务器，在 Kerberos 协议的术语中叫作 KDC，KDC 不需要知道 Alice 或 Bob 的密码。
太经常地更新自己的状态。当然，密钥服务器要记住与每个用户共享的密钥。但当Alice请求KDC建立一个她和Bob之间的密钥时，KDC完成这个任务之后就把结果忘记
了。它并不记录用户之间建立了哪些密钥。这是一个很好的性质，因为它可以让密钥服务器以一种简单的方式把原本很重的负载分布在几个机器上。由于没有状态要更
新，Alice在某一个时候可与密钥服务器的一个副本进行交互，而下一时刻使用另一个副本。事实证明，Kerberos⻛格的系统所需的密码协议是很复杂的。刚开始，设计这
样的协议看起来很容易，但即使是经验丰富的密码学家提出的方案后来也被攻破了。悄悄混进去的那些缺陷都是很微妙的。我们在这里不打算解释这些协议，对它们做实
验和手动修改都太危险了。我们甚至不愿意重新去设计这种类型的协议。如果你想使用一种这样的协议，请使用Kerberos协议的最新版本。它已经存在很⻓时间了，并且
被很多专家研究过。

17.3 更简单的方案

更简单的方案
有的用户说：“标签”，每个参与者还需要一个可靠的时钟。这些要求有些时候是无法满足的。并且，我们发现去研究一个更简单的设计能够提供更多的有用信息。如果我们不是那么强调效率，可以给出一个更简单、更强壮的解决方案。事实证明允许密钥服务器来维护状态是很有用的。现在的计算机与Kerberos刚被设计出来的那个年代的机器相比要强大多了，它们可以没有任何困难地维护上万个参与者的状态。甚至对有十万级别参与者的大系统也不成问题：如果每个参与者的状态在密钥服务器中
需要占用1KB，那么存储所有的状态仅需要100MB的内存。密钥服务器需要足够快地建立所有这些请求的密钥，但对现代的快速计算机来说仍然不是个问题。我们这里仅讨论有单个密钥服务器的情况。有一些技术可以用来把密钥服务器状态分布几个计算机上，对此我们将不进行详细讨论，因为你并不会真的想用一个管理着上万参与者的密钥服务器，那样太冒险了。这样的大密钥服务器的⻛险在于，所有的密钥都放在一个地方。这样使得密钥服务器成为一个很有吸引力的攻击目标。这个密钥
服务器也必须一直在线，意味着攻击者愿意的时候能随时与它进行通信。当前的状态并不能很好地保护计算机免受网络的攻击，而把密钥都放在一个地方简直就是找麻烦。对更小的系统来说，被密钥服务器保存的密钥“总值”小，因此威胁也减少了。在后面的几章里，我们要讨论更适合大规模系统的密钥管理系统解决方案，我们这里仅讨论小系统的密钥服务器的设置和使用方法。

苏格拉底挑战

时钟

kerberos