Fork Consistency 证书透明性（Certifica

这篇文章是基于Certificate Transparency 来写的。

之前我们介绍了一些内部系统的分布式设计，比如RAFT，比如SPANNER 或者DYNAMO。里面有一个假设所有节点都是值得信任的。
当一个系统是开放的时候，这个假设可能就不对了。当有节点存在欺骗的时候，我们要引入拜占庭协议。这是个复杂的协议，代价很高。据我所知，现在只有在航空航天领域被运用。

同时我们知道现在我们在互联网上冲浪时，大多数网站都会采用HTTPS。
这个协议通过证书随后走非对称加密随后交换密钥，所有通信都可以加密传输。使得中间人攻击可以很大程度的预防。这里我们要介绍的这个系统就是要解决证书不可信的问题的。在此之前，让我们先回到1995年，那时还没有证书和HTTPS，那时会发生什么？

1.A发送给B一条消息，却被H（坏人）截获：

A“嗨，B，我是A。给我你的公钥” --> H --x--> B

2.H将这条截获的消息转送给B；此时鲍伯并无法分辨这条消息是否从真的A那里发来的：

A --x--> H “嗨，B，我是A。给我你的公钥” --> B

3.B回应A的消息，并附上了他的公钥：

A<--x--- H<-- [B的公钥]-- B

4.H用自己的密钥替换了消息中B的密钥，并将消息转发给A，声称这是B的公钥：

A<-- [H的公钥]-- H <--x--B

5.A用她以为是B的公钥加密了她的消息，以为只有B才能读到它：

A“我们在公共汽车站见面！”--[使用H的公钥加密] --> H --x-->B

6.然而，由于这个消息实际上是用H(坏人)的密钥加密的，所以H可以解密它，阅读它，并在愿意的时候修改它。他使用B的密钥重新加密，并将重新加密后的消息转发给B：

A--x--> H“在家等我！”--[使用B的公钥加密] --> B

7.B认为，这条消息是经由安全的传输通道从A那里传来的。

这个例子显示了A和B需要某种方法来确定他们是真正拿到了属于对方的公钥，而不是拿到来自攻击者的公钥。否则，这类攻击一般都是可行的，在原理上，可以针对任何使用公钥——密钥技术的通讯消息发起攻击。

那么如何防护这种攻击呢？

公钥可以由"数字证书认证机构"验证，这些公钥通过安全的渠道（例如，随Web浏览器或操作系统安装）分发。公共密钥也可以经由Web在线信任进行在线验证，可以通过安全的途径分发公钥（例如，通过面对面的途径分发公钥）

如何做呢？

• 当客户端连接到支持TLS协议的服务器要求创建安全连接并列出了受支持的密码包（包括加密算法、散列算法等），握手开始。

• 服务器从该列表中决定密码包，并通知客户端。

• 服务器发回其数字证书，此证书通常包含服务器的名称、受信任的证书颁发机构（CA）和服务器的公钥。

• 客户端确认其颁发的证书的有效性。

• 为了生成会话密钥用于安全连接，客户端使用服务器的公钥加密随机生成的密钥，并将其发送到服务器，只有服务器才能使用自己的私钥解密。

• 利用随机数，双方生成用于加密和解密的对称密钥。这就是TLS协议的握手，握手完毕后的连接是安全的，直到连接（被）关闭。如果上述任何一个步骤失败，TLS握手过程就会失败，并且断开所有的连接。

证书包含什么信息呢？

一个证书里通常会包含DNS名，比如（gmali.com），这个服务器的公钥，CA的identity, 和一个用这个CA私钥签的名。
浏览器会包含一组授信的CA的公钥当浏览器使用HTTPS发起连接。
服务器会发来证书，浏览器会检查这个证书，随后会用证书里的公钥去加密来确保那个服务器具备私钥。这样引入了CA的概念就可以防止中间人攻击了。因为中间人要扮演B，就必须要知道B的私钥。因为B的私钥是注册在CA里的。

证书为什么还不够？

因为如何决定谁持有一个DNS NAME，不是那么直接的事情。比如我告诉CA，我是‘xy.com’的持有人，我需要申请一个证书。CA怎么认证我是真的持有人呢
更加严重的情况是，一般浏览器里会有100多个授信CA，不是所有的CA都能规范的运作（比如有一个不值得信任的员工进入某个CA，就可以上传坏人的证书进去）
所以整个CA的体系的健壮程度就取决于它最薄弱的一环。

Certificate Transparency 如何解决问题

首先要介绍2个组件。一个是CT LOG SERVER。这个组件当一个用户向CA申请证书之后，都会往CT LOG里写一条记录。
同时又另外一个监控组件，专门用来发现一个DNS NAME 是否被不合法的人注册了，如果发现就立刻报警。
所以浏览器去连接一个服务器的时候，拿到了那个服务器的证书，他还回去LOG SERVER 去求证一下，是否这个证书在LOG SERVER里存在。 存在才继续连接。
而MONITOR会时刻监控这个LOG SERVER的LOG，来发现有可疑的证书注册进去。
因为有监控保护，所以浏览器可以认为被LOG SERVER认证了的证书可以安全使用，如果不安全我会收到报警。

下面就是一个新的问题，如何确保所有人看到同样的LOG。

因为一些恶意的CA，可以搭配恶意的日志操作者来继续做坏事。
比如恶意的CA委托日志操作者帮他写假CA进LOG SERVER，当浏览器验证完，再立刻把他删除。这样有个窗口可能监控还没来得及发现那条记录就被删了。那么浏览器就拿着假CA在通讯，就会被中间人攻击。
还有一种攻击手段就是日志操作者使得日志服务器让浏览器看到的是带问题的日志的LOG。让监控者看到的是不带问题的LOG。这样做也可以达到之前说的效果。

要防止第一点，我们必须构建一个不可修改（删除）的日志，这个日志要求只可以APPEND。

如何来做到这一点呢，万一就是有个人去修改了日志的中间部分呢？

merkle tree

image.png

可见其子节点是每个数据项或者一批数据项（数据块）对应的哈希值，中间节点则保存对其所有子节点哈希值再次进行哈希运算后的值，依次由下往上类推，直到根节点，其保存的Top Hash代表整棵树的哈希值，也就是所有数据的整体哈希值。具体使用的时候，既可以像例子中一样是一个二叉树，也可以是多叉树。

Merkle树常用于快速侦测部分数据正常或者异常的变动。当某个底层数据发生变化时，其对应Merkle树的子节点哈希值会跟着变化，子节点的父节点哈希值也随之变化，依此类推，直到根节点，其间经过的节点哈希值都发生变化，但是其他无关树节点哈希值并不发生改变。通过Merkle树，可以O(log(n))时间内快速定位变化的数据内容。

有这样一棵树，只要你修改了之前的某个LOG，那么树的根节点的HASH必然会改变。
LOG SERVER 会对树的根做签名，一旦LOG SERVER 把这个签名的树根HASH给到我，之后他就无法抵赖了。
随着新的LOG不断进来，可能会产生新的根。比如有N个条目在LOG里组成了一个树。后面的N个LOG又会组成另一个树。这时需要把这2个树的根合并起来，那么就会产生一个新的根。

浏览器会问LOG SERVER，证书A 是否在LOG 中。 如果LOG SERVER承认的话，他必须要给出这个A的位置，以及对应需求用到的验证HASH值的一组HASH
比如证书的位置在下图红圈中，那么LOG SERVER 要恢复的位置是3，然后和绿色圈出来的这组HASH值给浏览器。
浏览器可以根据自己手里的证书自己算出一个HASH值，然后一直往上求出根节点的HASH，再去和服务器签名的那个根节点的HASH做比较。如果一致，就代表数据没有被修改过。

image.png

这个验证的过程还是比较快的，比如说有N个LOG，只需要LOG(N) 次HASH就可以得到结果。这个非常重要，因为对浏览器来说他也不想从LOG SERVER那边去下载所有的LOG，来判断LOG 是不是被篡改。

服务器有没有可能撒谎

比如他自己维护了一个假的STH，里面也包含了那个非法的证书，然后把假的STH告诉浏览器，之后验证就可以用改过的HASH了。同时还要不被监控者发现。
这里就类似于GIT的分支，出现了分叉。两个人在不同的版本上。如何防止这种问题呢？

这里就要引入另一个技术叫GOSSIP

GOSSIP PROTOCOL

更新的信息经过一定轮数（Round）的传播后，集群内所有节点都会获得全局最新信息。节点P随机选择集群中另外一个节点Q，然后与Q交换更新信息；Q如果信息有更新，则类似P一样传播给任意其他节点（此时P也可以再传播给其他节点），这样经过一定轮数的信息交换，更新的信息就会快速传播到整个网络节点。其传播过程就是我们常说的“一传十，十传百”的模式。

有了这个协议后，所有节点都可以交换服务器告诉他们的ROOT HASH值，这个值可能会合法的不一样，也就是说有一个节点的HASH值是另一个的前缀（也就是我们上文提到的，ROOT HASH随着LOG增多可能会扩展一层上去）
如果不是前缀，还不一样，那么一定代表有FORK问题发生了（出现了2个分支）
这的正确性是基于加密型HASH，LOG SERVER找不到另一个错误的值使得和正确的值都能够HASH出同一个ROOT HASH。
同时前缀问题是这样，如果CLIENT发现2个ROOT HASH值不一样，那么就需要LOG SERVER 提供，一组右侧根的HASH，使得一个ROOT HASH可以被算出来。
如下图。
前缀的证明方法就是要求LOG SERVER 提供2个绿色的HASH值，使得CLIENT可以验证。

image.png

此外如果LOG SERVER 对LOG 做了手脚。
比如正确的右侧绿色的HASH值为X。做手脚那块区域的的正确的HASH 为H1。
那么另一个不一样的正确的ROOT HASH为H2
有H2 = H(H1, X)
如果要对H1做手脚，H1会变成H11
那么就要求LOG SERVER 能找到一个Y使得 H2 = H(H11, Y)
不然没法向CLIENT交代这个前缀正确性。
根据加密型HASH，这给反向计算也是做不到的。

所以只要基于这个算法，只要浏览器和监控器做了足够多GOSSIP。最终他们能确保他们看到相同的LOG。

LOG SERVER 最后能使的坏就是，他在一开始给了CLIENT一个错的ROOT HASH，和一个错的证书，及一组错的认证。然后他用了之后，LOG SERVER 要赶在他能和MONITOR通信GOSSIP之前，立刻去更新这个ROOT HASH 和正确的证书。这样他之后在和MONITOR 同步的时候，就不会发现问题。

为了防止这种情况，所以CLIENT必须要记录下之前LOG SERVER给的每一个签名的ROOT HASH。然后更新的时候必须要求使用前缀认证算法。就是你要更新的ROOT HASH，得证明是我当前这个ROOT HASH基础上生成出来的。

这样LOG SERVER 就没法FORK一个分支出来了。这个又被成为FORK CONSISTENCY。

当这个证明被违反时，就代表这个LOG SERVER可能是不怀好意的，或者被污染的。这时候就需要下线这个LOG SERVER。

总结

1. 这套系统的核心就是使得所有人看到同样的日志，可以防止坏人篡改。
2. 如果浏览器能看到假证书，那么DNS NAME OWNER也可以发现，并报警。
3. 如果预防很困难，事后监控就值得被考虑。
4. 哈希树+gossip是经常组合使用的分布式技巧。