很多计算机系统使用了可信平台模块(trust platform module, TPM)^[1-2]来维护密钥和进行加密操作。国际标准化组织(International Organization for Standardization, ISO)和国际电工委员会(International Electrotechnical Commission, IEC)的专家组在2015年将TPM 2.0纳入了国际标准，线上快速身份验证联盟(Fast IDentity Online, FIDO)也同样支持TPM中的认证功能，并将其作为密码运算的核心模块。近几年来，针对TPM的研究内容主要集中在TPM安全性的形式化分析^[3]、TPM电源管理安全性^[4]等，而本文主要关注外源密钥的销毁问题。

TPM的核心功能之一就是进行密码运算。为了增强扩展性和避免内部存储资源的不足，TPM中很多密钥都不存储在内部，而是以加密的形式存储在外部，针对这一部分密钥的管理称作外源密钥管理。密钥保存在外部可以减轻TPM的负担，但是TPM不能只撤销某一个密钥，只能一次性撤销所有密钥。即使一个外源密钥已经撤销了，攻击者仍然可以把这个密钥加载到TPM中并且正常使用。在多数情况下，撤销全部密钥的方法影响非常大，甚至是不可接受的，因此需要一种撤销单一外源密钥的方法。

Hao等^[5]提出了一种公开验证的密码方案来撤销TPM中的秘密数据，主要用来撤销TPM的内源密钥，不能撤销外源密钥，并且解决方案与TPM中现有的密钥管理方法不兼容。Cortier等^[6]提出了一种针对嵌入式设备密钥建立和撤销的对称密钥管理接口^[7]，其空间复杂度和密钥数量呈线性关系，时间复杂度和已销毁密钥数量呈线性关系。当密钥数量上升时，有可能带来很大的开销从而降低使用效率。Liu等^[8]提出了一种轻量级的固态硬盘数据删除方法ErasuCrypto，这种方法所要删除的数据是存储在固态硬盘内的，但是动态密钥管理方法中所要删除的数据是存储在TPM外部的。

Katzenbeisser等^[9]提出了针对TPM 1.2的2种密钥撤销方法，即黑名单的方法和白名单的方法。黑名单方法的开销和已经撤销的密钥数量呈线性关系，白名单的方法和未被撤销的密钥数量呈线性关系。

本文提出了一种撤销单一外源密钥的动态密钥管理方法，构建了动态密钥管理树，设计并实现了动态密钥管理方法的原型系统，并将其移植到TPM 1.2和TPM 2.0中；分析了动态密钥管理方法的存储开销、计算和通信复杂性和时间性能。结果表明：存储空间大小、计算和通信复杂性都只和密钥总数量呈对数关系。

1 变色龙散列函数和变色龙认证树 1.1 变色龙散列函数

变色龙散列函数(chameleon Hash function, CHF)^[10]是一个带随机值的散列函数，可以避免碰撞，但是存在一个私钥可以寻找碰撞。变色龙散列函数包含3个算法，用CHF= < ChGen, Ch, Col>表示^[10]。

ChGen(1^λ)：密钥生成算法，返回一个公私钥对 < cpk, csk>。

Ch(cpk, m, r)：变色龙散列算法对一个给定的二进制消息m∈{0, 1}ⁱⁿ和随机序列r∈{0, 1}ⁱⁿ，输出一个散列值h∈{0, 1}^out。

Col(csk, m, r, m′)：碰撞生成算法返回一个r′，满足Ch(cpk, m, r)=Ch(cpk, m′, r′)，或者表示为h=Ch(cpk, m′, r′)。

一个变色龙散列函数有如下性质：

1) 效率高：给定一个公开的散列密钥cpk和一个消息、随机值对 < m, r>∈{0, 1}ⁱⁿ×{0, 1}^λ，Ch(cpk, m, r)算法可以在多项式时间内计算出散列值。

2) 碰撞概率低：没有一个确定性的多项式复杂度的算法A，满足在同样cpk的情况下，存在2个消息、随机值对 < m, r>, < m′, r′>∈{0, 1}ⁱⁿ×{0, 1}^λ满足 < m, r>≠ < m′, r′>，但是Ch(cpk, m, r) =Ch(cpk, m′, r′)。

3) 私钥碰撞：存在一个确定性的多项式时间的算法Col，对于一组给定的公私钥对 < cpk, csk>，一个消息、随机值对 < m, r>∈{0, 1}ⁱⁿ×{0, 1}^λ(或者一个散列值h∈{0, 1}^out)，一个额外的消息m′∈{0, 1}ⁱⁿ，生成一个r′∈{0, 1}^λ满足Ch(cpk, m, r)=Ch(cpk, m′, r′)，或者表示为h=Ch(cpk, m′, r′)。

1.2 变色龙认证树

变色龙认证树(chameleon authentication tree, CAT)^[11-12]是一个二叉树，它每一层最左侧的节点是其2个子节点的变色龙散列值(如果是叶节点就是密钥的变色龙散列值)；其余左节点是其2个子节点的散列值(如果是叶节点就是密钥的散列值)；所有右节点是其2个子节点的变色龙散列值(如果是叶节点就是密钥的变色龙散列值)。变色龙认证树包含4个算法，用CAT= < CatGen, CatAdd, CatUpdate, CatVerify>表示。

CatGen(1^λ)：密钥生成算法以λ作为输入，输出一个私钥、验证密钥对 < sk, vk>。

CatAdd(sk, l, c)：添加算法以私钥sk、叶节点l(l∈L，L表示所有叶节点)和叶节点数量c作为输入，输出为一个新的密钥sk′和一个证明π_c。π_c是一个公开的验证数据，用来验证l是否变色龙认证树的第c个叶节点。

CatUpdate(sk, i, l′)：更新算法以密钥sk，索引i和一个新的叶节点l′(l′∈L)作为输入，用l′替换CAT中原来的第i个叶节点，并输出一个新的密钥对 < sk′, vk′>以及一个证明π_i′。

CatVerify(vk, i, l, π_i)：验证算法以验证密钥vk、索引i、叶节点l(l∈L)和证明π_i作为输入，如果l是CAT的第i个节点，输出true，否则输出false。

变色龙认证树是完备的，对于每一个由CatGen生成的 < sk, vk>，任意的l, l′∈L，下式成立：

如果CatAdd(sk, l, i)→ < sk′, i, π_i>，那么CatVerify(vk, i, l, π_i)=true；

如果CatUpdate(sk, i, l′)→ < sk′, vk′, π_i′>，那么CatVerify(vk′, i, l′, π_i′)=true。

2 动态密钥管理机制

动态密钥管理方法的存储空间由3部分组成：TPM内部存储空间、外部存储空间和应用存储空间，如图 1所示。动态密钥管理树是从变色龙认证树变化而来的，从叶节点开始自底向上生长。左叶节点保存密钥的散列值，右叶节点保存密钥的变色龙散列值，变色龙散列函数的私钥由TPM唯一保存。树中的节点有3种类型：每一层最左侧的子节点(存储在TPM内部存储空间中)、其余左节点和右节点(两者都存储在外部存储空间中)。密钥以加密的形式存储在应用存储空间中。动态密钥管理树提供4种操作：初始化、添加、更新和认证。初始化只执行一次，其余操作可以执行多次。

2.1 初始化操作

假设已经选定了一个散列函数Hash()和一个变色龙散列函数。TPM使用一个保密的参数λ来执行算法KtInit(见图 2)，生成一个变色龙散列函数使用的公私钥对 < cpk, csk>，初始化ρ和根节点使用的随机序列集合rdz。算法返回动态密钥管理方案的公钥pk、私钥sk以及密钥数量c。sk是受TPM保护的，pk和c是公开的。

2.2 添加密钥操作

添加密钥根据c值的不同分为3种情况，每种情况最后都会增加密钥总数量：

1) 当c=0时，算法KtAppend(见图 3)会为第1层的根节点生成一个供变色龙散列函数使用的随机值r_{1, 0}，并将它加入到rdz中，之后它将计算出根节点的值ρ，并将验证数据π₀置为空。

2) 当c=2^d-1时，此时动态密钥管理树变成了一个满二叉树，所以高度需要增加一层。首先创建一个新的根节点，值为Ch^d (ρ)，再创建一个哑节点v_{d, 1}作为新根节点的右节点，而原来以Ch^d-1 (ρ)为根节点的树就变成了左子树，最后执行算法KtApdNotFull完成添加操作。

3) 2^d-2 < c < 2^d-1时，此时动态密钥管理树中仍有空间可以添加新的密钥，直接执行算法KtApdNotFull(见图 4)完成添加操作：先找到最低层的没有子节点的右节点。如果该节点位于第1层，则直接将密钥的变色龙散列值添加到该节点中；否则为该节点下面的每一层生成一个新的最靠左侧的右节点，然后将密钥的散列值添加到第1层新生成的右节点的兄弟节点中，再递归向上补全每层缺少的左节点。

2.3 更新密钥和撤销密钥操作

撤销一个密钥时，需要为该密钥设置一个撤销标志位，然后将更新key_i为key'_i。更新和撤销都需要根据密钥索引值i执行算法KtGenAuthPath(见图 5)来生成key_i的认证路径ap_i，然后根据新的密钥key'_i索引i和认证路径ap_i执行算法KtUpdate(见图 6)。该函数将叶节点v_{1, i}的值更新为新的密钥值key'_i，然后将叶节点到根(不包括根)这条路径上的节点值进行更新，但是保证变色龙散列函数使用的随机值不变，而对于根节点，则保持节点值不变，更新随机值。

2.4 验证密钥操作

如果加载密钥key_i到TPM中，TPM就要检查这个密钥的有效性。为了证明key_i仍然是可用的，TPM就要执行算法KtGenAuthPath来生成一个认证路径ap_i。接下来TPM根据key_i、索引i、和认证路径ap_i执行算法KtVerify(见图 7)。该函数从树的叶节点开始，循着ap_i计算编号为偶数节点的普通散列值，编号为奇数节点的变色龙散列值。当返回true时，表示密钥是有效的；而返回false时，表示密钥已经被撤销。

3 安全性分析 3.1 安全模型

为了对动态密钥管理的安全性作出分析，本文引入如下模型：

1) 只有TPM保存变色龙散列函数的私钥，并使用此私钥来添加新的密钥或者撤销和更新就旧密钥；

2) 攻击者只能进行合法的添加和更新操作。

假设攻击者进行了q(λ)次添加和更新操作，最终得到的密钥和认证序列为Q={ < key₁, 1, ap_i>… < key_q(λ), q(λ), ap_q(λ)>}。此后攻击者根据Q计算得到了一个 < key^*, i^*, ap^*>，如果下面2个条件之一成立，则动态密钥管理方案是不安全的。

存在i^*∈{1, 2, …, q(λ)}且 < key^*, i^*, ap^*>∌Q使得算法KtVerify返回true；存在i^*> q(λ)使得算法KtVerify返回true。

如果攻击者不能随便修改任何一个密钥，或者不能在没有私钥的情况下添加一个新的密钥, 那么动态密钥管理方案就是安全的。

定义 动态密钥管理方案是安全的当且仅当对于任意的q∈N，不存在λ的多项式时间算法A，使得上述2个条件之一成立。

3.2 安全性证明

定理  如果所使用的变色龙散列函数是碰撞唯一的且散列函数是碰撞避免的，则动态密钥管理方案是安全的。

下面给出一个简短的证明。

证明：假设存在一个有效的算法A使得算法KtVerify返回true，那么会出现以下2种情况：

情况1   i^*∈{1, 2, …，q(λ)}。因为 < key^*, i^*, ap^*>∌Q，所以考虑 < key_i^*, i^*, ap_i^*>∈Q。

如果ap^*=ap_i^*，显然有key^*≠key_i^*。此时如果i^*为偶数，那么必然有Hash(key^*)=Hash(key_i^*)，否则在相同的认证路径上一定是无法认证通过的，因此找到了散列函数的一个碰撞。如果i^*为奇数，类似可以找到变色龙散列函数的一个碰撞。

如果ap^*≠ap_i^*，由于i是相同的，即使认证路径不同，但是认证路径最后都会达到同一层的最左侧节点，那么存在d∈{1, 2, …，D}, r，满足v_{d, r}^*=v_{d, r}且 < v_{d-1, 2r+1}^*, r_{d-1, 2r+1}^′*>≠ < v_{d-1, 2r+1}, r_{d-1, 2r+1}^′* >或者v_{d-1, 2r}^*≠v_{d-1, 2r}。此时如果r=0，则有v_{d, r}^*=v_{d, r}=Ch^d-1 (ρ)，v_{d-1, 2r}^*≠v_{d-1, 2r}=Ch^d-2 (ρ)，因此 < v_{d-1, 2r+1}^*, r_{d-1, 2r+1}^*′>≠ < v_{d-1, 2r+1}, r_{d-1, 2r+1}^′* >。从树的构建过程可知，Ch(cpk, Ch^d-2 (ρ)‖v_{d-1, 2r+1}^*, r_{d, r})=Ch(cpk, Ch^d-2 (ρ) ‖v_{d-1, 2r+1}, r_{d, r})=Ch^d-1 (ρ)，必然有v_{d-1, 2r+1}^*= v_{d-1, 2r+1}，而r_{d-1, 2r+1}^′*≠r_{d-1, 2r+1}^′*。由于v_{d-1, 2r+1}^*=Ch(cpk, x^*, r_{d-1, 2r+1}^′*)=v_{d-1, 2r+1}=Ch(cpk, x, r_{d-1, 2r+1}^′*)，故在不知道私钥的情况下，找到了x^*≠ x使得变色龙散列函数发生了碰撞。当r≠0时类似可以找到变色龙散列函数的碰撞。

情况2  i^*>q(λ)。这种情况下在ap^*中存在一个节点，该节点是当前根节点的兄弟节点。在树的构建过程中，这个节点一开始是哑节点，是由随机消息m和随机值r通过Ch(cpk, x, r)计算得到的。当攻击者使用 < key^*, i^*, ap^*>通过了验证后，那么就存在一个Ch(cpk, x^*, r^*)=Ch(cpk, x, r)，这里x^*是从i^*开始，依次通过它的2个子节点计算出来的，并且x^*≠x。这样就在不知道私钥的情况下使得变色龙散列函数发生了碰撞。

4 原型系统实现

先选定动态密钥管理方案中使用的一些算法，再描述对TPM的修改。

4.1 变色龙散列函数、根节点函数和相关安全参数

变色龙散列函数可以选取离散对数变色龙散列函数(DLCH)^[10]、简单因子分解变色龙散列函数(SFCH)^[13]和高级因子分解散列函数(AFCH)^[13]，这3个函数都满足变色龙散列函数的性质。在确定了变色龙散列函数、随机数算法ChRan(见图 8)后，动态密钥管理树中根的计算方法Ch^d(ρ)由式(1)定义，其余的安全参数根据文^[14]选取，如表 1所示。

$ {\rm{C}}{{\rm{h}}^d}\left( \rho \right) = \left\{ {\begin{array}{*{20}{c}} {{\rho ^{{2^d}}}\bmod p, }&{{\rm{DLCH;}}}\\ {{\rho ^{{2^d}}}\bmod n, }&{{\rm{SFCH;}}}\\ {{\rho ^{{m^{{2^d}}}||{r^{{2^d}}}}}\bmod n, }&{{\rm{AFCH}}{\rm{.}}} \end{array}} \right. $

(1)

4.2 对TPM的修改

本文设计的模型同时兼容TPM 1.2和TPM 2.0。对TSS 1.2的修改基于TrouSerS^[15]。在TPM 1.2中新增加和扩展的接口如表 2所示，新增加和扩展的命令如表 3所示。对于TPM 2.0，新增加和扩展的系统API如表 4所示，新增加和扩展的命令如表 5所示。

5 性能分析与测试 5.1 存储性能

动态密钥管理树的深度是随着密钥的数量增长的。如果树的深度是d，那么可以管理2^d-1个密钥，其中密钥存储在应用程序中，而1个ρ和d个变色龙散列函数的随机值存储在TPM中。外部存储空间存储的节点数目可以由式(2)计算的得到。变色龙散列函数随机值的数量可以由式(3)计算得到。TPM内部存储量、外部存储量和应用存储量的比值为(1+d):(2^d-1-d):2^d-1，可以表示为d:2^d:2^d-1。

$ 节点数目 = {2^d} - 1 - d, $

(2)

$ 随机值数量 = {2^{d - 1}} - 1. $

(3)

当d取值从1变化到12时，TPM内部存储、外部存储和应用存储分布如图 9所示。无论是内部存储还是外部存储，DLCH比SFCH和AFCH使用得更少。

5.2 通信开销

由于TPM多数使用的是慢速总线设备，因此总线上的通信决定了通信效率的高低。对于TPM 1.2来说，动态密钥管理方案带来的通信开销如表 6所示。对于TPM 2.0来说，动态密钥管理方案带来的额外通信开销如表 7所示。size(newPath)由算法KtAppend计算得到，size(authPath)由算法KtGenAuthPath得到，size(updatePath)由算法KtUpdate得到。当keyIndex从1变化到256时，3种路径的存储开销如图 10所示。

如果加载密钥时使用黑名单的方法^[9]，除了需要调用TPM_LoadKey2()，还需要调用一个新增的TPM指令TPM_ShowRevListElement()。这条指令的调用次数和已撤销的密钥数量一样多，记为n_r。对于TPM_KEY来说，这条指令的请求数据有952字节，响应有656字节；对于TPM_KEY12来说，分别是962字节和656字节。因此黑名单方式的额外通信负载是1 608 n_r/1 628 n_r。使用动态密钥管理方案时减小了TPM_LoadKey2()的通信开销为8+size(authPath)。假设1 608 n_r/1 628 n_r=8+size(authPath)，这样就能计算出n_r和keyIndex的关系，如图 11a所示。

如果撤销密钥时使用白名单的方法^[9]，应用程序必须调用一个新的TPM指令TPM_WhitelistTransformKey()(这条指令的调用次数和未被撤销的密钥数量一样多，记为n_nr)，还要调用一次TPM_WhitelistCommit()，所以总的通信开销是76n_nr+8字节。而使用动态密钥管理方案撤销密钥时，调用TPM_RevokeKey()的开销是1 406+size(authPath)+size(updatePath)。假设76n_nr+8=1 406+size(authPath)+size(updatePath)，这样计算出n_nr和keyIndex的关系如图 11b所示。

黑名单方法的通信开销和已销毁的密钥数量、白名单方法的通信开销和和未销毁的密钥数量都是线性相关的，但是动态密钥管理方法是对数相关的。除了通信开销外，黑名单和白名单的方法比动态密钥管理方法需要更长的传输时间和操作时间。

5.3 时间开销

动态密钥管理方案的原型系统运行在具有1 GB内存、Ubuntu 14.04.2 LTS Server AMD64操作系统的VMware 12.1.0的虚拟机上，物理机运行在一个2.6 GHz、Intel Core i7-4720HQ处理器、16 GB内存和Windows 10专业版操作系统的机器上。动态密钥管理方案添加、验证和更新所带来的时间开销如图 12所示，图中展示的都是5次实验的平均结果。

在黑名单方法中，密钥销毁是常量时间的，但是密钥的加载是和已经销毁的密钥数量线性相关的，这是因为TPM_ShowRevListElement()命令需要调用的次数是和已经销毁的密钥数量相同。

在白名单方法中，加载密钥是常量时间，但是密钥的销毁是和未销毁的密钥数量线性相关，这是因为TPM_WhiteListTransformKey()命令需要调用的次数是和没有被销毁的密钥相同。

在动态密钥管理方法中，而认证路径上节点的数量与密钥总量呈对数关系；密钥的销毁的开销与更新路径上节点的数量相关，而更新路径上节点的数量与密钥总量呈对数关系。因此动态密钥管理方案比黑名单和白名单方法的性能更好。

6 结论

通过引入动态密钥管理树，动态密钥管理方案可以单独撤销TPM中的外源密钥，并且只需要将动态密钥管理树中每一层的最左侧节点存储在TPM的内部存储空间中，因此所需要的空间与总密钥的数量呈对数关系。其他节点可以存储在TPM的外部存储空间中，而密钥以加密形式存储在应用程序中。在整个系统中只有TPM保存变色龙散列函数的私钥，并且可以在不影响其他密钥的情况下使用该私钥添加新密钥和撤销旧密钥。动态密钥管理方案进行添加、更新和撤销操作的性能与密钥总数量都呈对数关系。在接下来的研究中将会建立基于动态密钥管理的可信平台远程证明机制。