概念
证书透明日志使用特殊的加密算法有助于证书和日志的公共审查。这个特殊的加密算法称作默克哈希树(Merkle hash tree) ,一种包含哈希叶和结点的简单二叉树(图1)。叶子是已附加到日志中的单个证书的哈希。节点是成对的子叶或成对的子节点的哈希。所有叶子和结点的根,即根哈希称作默克树哈希(Merkle tree hash)。当日志服务器对默克树哈希(及其他信息)签名,称为签名树头(STH:signed tree head )。
定期地,可能一小时一次,日志服务器将新获取到的证书追加到日志中。通过新获取到的证书创建单独的默克树哈希,该哈希和之前已在哈希树中的旧默克树哈希结合成新的默克树哈希(图2)。对新的默克树哈希签名创建新签名树头。反反复复的持续,之前提交到日志中的所有证书形成了一个不断增长的默克树。
一致性证明和审计证明
因为这种构造方式,默克哈希树让日志高效迅速的证明两件事:
- 所有证书被一致性地附加到日志中
- 特定的证书附加到日志中
日志通过提供两个加密证明来支持:默克一致性证明和默克审计证明。
默克一致性证明
默克一致性证明验证一条日志的任意两个版本是一致的:即,新版本包含旧版本的一切,换句话说,所有新条目紧跟在上个版本的条目后。如果证明日志是一致的,意味着没有过期的证书且插入到日志中,日志中没有证书被修改,且日志也没有分支过。
为了演示默克一致性证明原理,假设要证明图2和图3中的日志是一致的。第一步,需要证明旧默克树哈希是新默克树哈希的子集。然后再证明新默克树哈希是旧默克树哈希加上所有中间新附加证书的结点哈希。一致性证明是计算这两者所需要的最少中间节点哈希集。
这种情形下,一致性证明由以下中间节点哈希组成:k
,l
和m
(见图4)。用k
和m
创建旧默克树哈希,因此证明旧树存在且没有被改变。然后用l
和k
创建n
,用n
和m
创建日志新默克树哈希。如果计算的默克树哈希和日志中的相匹配,则日志是一致性的。
监视器和审计定期使用一致性证明来验证日志是否正常。因为监视器通常有和日志中一样的证书列表,可以自行计算一致性证明,且验证日志中的一致性。设计可以简单的查询日志服务器,得到任意两个已签名树头的一致性证明。
默克审计证明
默克审计证明可以验证日志中是否有特定的证书。这是一项重要的证明任务,因为证书透明模型需要的是所有TLS客户端拒绝没有在日志中出现的证书。
为显示默克审计证明的原理,假设要验证d3
证书(d
叶子)已经附加到图3中里的日志中。默克审计证明是计算叶与树根之间的所有节点所需的缺少节点哈希。如果根据审计路径计算的根哈希和当前日志中的默克树哈希相匹配,则该叶子存在于树中(或换句话说,日志中存在该证书)。
这个例子中,默克审计证明包含以下节点哈希:c,i,n
(见图5)。以为d
已知,则可以用c
计算出j
。然后用i
和j
计算出m
,再用n
和m
计算出该日志的默克树哈希。同理,如果要验证证书d4
已经被附加到日志中,日志给你发送f, l, m
结点哈希的一致性证明。已知叶子哈希( e
),也就能用叶子哈希f
计算出结点哈希k
,然后用结点哈希l
计算出结点哈希n
,再用结点哈希m
和n
计算出日志的默克树哈希。
任何人都可以请求日志的默克树哈希,也能验证某个证书是否存在日志中。审计通常发送这些类型的请求到日志中,以便为TLS客户端验证证书。如果默克审计证明没有计算出和默克树哈希相匹配的根哈希,则意味着日志中不存在该证书。
使用证明
证明提供审计需要的加密数据。通知,审计了解日志的很少信息,但是尽管了解有限,证明能为审计验证日志的一致性和特定证书是否已附加到日志中。
若没有证明,审计可能访问或回去所有的日志记录,以行使其职责。证明让数据交换更高效,日志和审计交换的数据量也少的多。举个例子,包好1000万个证书的日志仅需要24个结点哈希一致性证明。如果日志中增加到2000万个证书,一致性证明的结点哈希数量才到25个。
证明对于监视器也很有用,尽管方式略有不同。监视器通常保存监控到的日志副本,以便检查日志的每个证书,且注意特定的证书。如果监视器检查监控到的特定日志的一致性,可以自己计算出一致性证明,然后验证日志的一致性。同样地,如果监视器总是需要特定的证书是否存在于日志中,也可以自己计算出审计证明,然后用该证明验证证书。