Enhanced certificate transparency and end-to-end encrypted mail

论文笔记 Authentication

作者：Mark D. Ryan

单位：University of Birmingham, CloudTomo Ltd.

Abstract & Introduction

传统的使用公钥认证的CA模型，除去一些可能存在的密码学上的问题，还有2个非常重要的问题：

1. CA必须是可信的——这一前提条件通常被默认是成立的，但是在实际情况中却未必如此
2. 被撤销的证书——现在浏览器通常要求CA来验证证书是否被撤销，然而这未必能起到作用

文章主要关注了一种名为Certificate Transparency的解决方案，该方案主要解决了第一个问题，并在后来推出了一个名为Revocation Transparency的扩展，用来解决第二个问题。

Certificate Transparency

Certificate Transparency的目的在于，让网站的用户和拥有者都能够识别出不正确的证书以及不再受信的CA。

Certificate Transparency依赖于一份可验证的Certificate Transparency Log，这份Log使用一棵不断增长的Merkle Hash Tree来添加新证书，新添加的证书必须保证其证书链可信，存储时会将整个证书链添加到Log中，并且可以通过请求查询得到。

其还有一个名为Revocation Transparency的扩展，用来解决证书撤销的问题。

虽然Certificate Transparency的效率很高（就算有10⁹份证书，用来验证的数据也只有1KB-2KB），然而其Revocation Transparency的效率非常低（O(n)），所以本文的主要目的就在于提高其效率。

文章提出了一种Certificate Transparency的扩展，名为Certificate issuance and revocation transparency（CIRT），来使其对于撤销证书的效率和颁发证书效率一样高。文章还将这一方法用到了电子邮件中，创建了一种不需要任何可信方，用户也不需要做任何额外操作的加密邮件方式。

Background

Merkle Tree

对于检验一个叶子节点是否存在于树中，只需要O(logn)的复杂度，即每一层只需要提供一个节点信息，就可以完成验证。

端至端的邮件加密

• S/MIME——只能用于企业级的加密邮件，成本高，配置复杂
• PGP——配置也很复杂
• IBE（Identity-based encryption）——IBE使用像email地址这样的字符串作为公钥，从而对用户而言更加友好，但问题在于，IBE体系中有一个IdP用来向所有注册用户颁发私钥，这就造成了这个IdP可以解密任何注册用户的邮件。
• CE（Certificateless encryption）——通过为用户增加另外的密钥对解决了这一问题，然而这带来了新的问题，攻击者可以伪造这个额外的公钥，发起主动攻击。

CIRT

CIRT使得用户的公钥可以依赖于CA，却未必一定要相信他们，它要求CA证明自己的一切操作都依然正常。
CIRT的很多想法都来自于CT，比如log中包含了一个给定CA的所有证书，不同的是，CT的log持有者只需给出一张证书是否在log中，而CIRT不仅能给出其是否存在于log中，还能保证它没有被撤销或替换。

首先定义CP，即Certificate Prover，是拥有log的实体，其log可以被定义为：
db=[cert(Alice,pk_Alice),cert(Bob,pk_Bob),...]

为了维护其正确性，CP还必须提供以下服务：

CIRT构建了两棵Merkle树，一棵根据时间顺序，从左到右排列，取名为ChronTree。对于这棵树来说，要撤销一张证书，就是在这张证书的密钥后再增加一个密钥（比如说null），也就是说，每个证书的key指的是其最后一个。这样的做法使得对于查询证书是否撤销的复杂度保持在O(logn)，而不是像CT中的O(n)（在CT中要检查一个证书是否被撤销，需要列举在其之后的所有记录，以查看是否存在撤销行为）。在这棵树中，插入、撤销和扩展都只需要O(logn)的复杂度

另一棵Merkle树按照二叉查找树的方式进行构建，也就是从左到右，按照字典顺序排列，称作LexTree，示例如下。

对于其中的每一个d_i可以表示为：d_i = (subj_i, (cert_i,1, cert_i,2, ...))
其中，(cert_i,1, cert_i,2, ...)是一个定长序列，也就是说，LexTree只保留有限个被撤销的证书，正在使用的就是最后一个公钥。
LexTree使得检查缺少的凭据的算法复杂度也降到了O(logn)。比如说Bob不存在于这棵树中，那只要证明在subj_i ≤ Bob ≤ subj_j的条件下，subj_i和subj_j是相邻的即可。
但是在LexTree中，扩展这一功能就需要O(n)的复杂度。

所以为了达到最高效率，一个db可以定义为(ChronTree, LexTree)。因为LexTree对于扩展操作比较慢，所以可以用ChronTree来辅助完成，比如要增加一张证书c到(ChronTree, LexTree)上：

• 将c加到LexTree上，如果c已存在，则为已存在的列表增加一个新密钥，否则就为该树增加一个新节点，令h_l为新的LexTree的根Hash
• 将(c,h_l)添加到ChronTree

h(db)就是一对ChronTree和LexTree的根，为了保持两者的一致性，需要对此做检查，这个检验需要O(n)复杂度的时间和空间。

• 用户客户端的随机检查：客户端随机选取ChronTree里的一条路径，比如说最后结束在了(c_i,h_i)，那这就要求LexTree提供证据，即由h_i代表的那棵LexTree正是由h_i-1和证书c_i组成的。
• 公共审查：审查员可以收到所有从CP那儿收到的更新，并保存有自己的两棵树的版本，他比较h(db)和由日志中汇报的h(db)。所有人都可以是公共审查人。

Application to email

一些定义如下：
MP——mail provider，CP——certificate provider

用户拥有由邮件客户端生成的公私钥对，CP验证用户的公钥，并维护一个公钥和邮件地址的数据库，用CIRT来维护一个只能增加信息的证书增删日志文件。

注册

比如说Alice要注册一个账户，并下载了正确的客户端。

1. 客户端应用从CP获得现在的h(db)，并存储在本地
2. Alice输入用户名，比如“Alice@example.com”，并设置了新密码pw，应用选择一个加密密钥k
3. CP以此为Alice创建一个账户
4. 应用创建公私钥对pk_Alice和sk_Alice
5. 应用和CP一起存储(Alice,pk_Alice,{h(db), sk_Alice}_k)
6. 应用对日志文件的一致性做一个随机检查

发送邮件

1. 在CP验证Alice之前，Alice的应用需要首先从CP获得最新版本的h(db')
2. 应用找到他本地存储的h(db_s)
3. Alice在db'中请求并验证cert(Alice,pk_Alice)
4. 应用验证Alice，并从CP获取(Alice,pk_Alice,{h(db), sk_Alice}_k)
5. 应用需要验证h(db_s)≤h(db)≤h(db')
6. 应用在db'中找到pk_Bob，并请求检查是否现在还在使用
7. 应用使用Bob的公钥对消息进行加密后发送给他
8. 应用对日志文件的一致性做一个随机检查

收取邮件

基本和发送邮件类似

一些实现上的考虑

以上方法的好处在于，不像S/MIME和PGP，用户不需要知道关于公私钥的技术细节就可以使用加密邮件。
使用上述方法时，邮件界面上并不会存在加密或者解密的选项，所有的加解密操作由软件自身完成。

密钥与口令管理

1. 密钥在服务器
   密钥需要用户通过口令来换得，这一方式比较灵活，但是要求用户口令足够灵活，而且一旦口令丢失，则无法再获取到密钥。

2. 密钥在本地
   密钥在本地的话要比上一种更加安全，因为服务器不会遭受到口令猜解攻击，然而也有一个问题，就是如何在多个设备上迁移密钥，研究者目前开发了一套协议用来解决这个问题。