内存完整性校验
最近在做内存完整性校验机制的相关研究，梳理一下内存完整性校验的原理。
背景
在可信执行环境（Trusted Execution Environment，TEE）的应用场景中，信息系统的可信范围缩小至片内（这里的片内是指片上系统（System On Chip，SoC）的内部），也就是数据只有在SoC上是处于明文状态，数据以密文的形式出SoC。其考虑到的攻击模型是：数据在主板总线传输的时候，也有被监听的可能，同时在内存中，也可能遭到冷启动攻击（考虑到攻击者能够在物理上接触到信息设备）。因此，在总线上传输和内存中的数据是均处于密文的状态。
内存加密能够确保数据的机密性，但是还缺乏对完整性的保护。攻击者有可能篡改密文数据，导致信息不正确。因此，TEE需要对内存数据的完整性也进行保护，确保下一次从内存取回的数据是上一次存放的正确数据。
这就引入了内存完整性校验技术，本文接下来讨论其原理和方法。
内存完整性校验原理
首先介绍完整性校验的原理，数据完整性最主流的校验机制是消息验证码（Message Authentication Code，MAC）。MAC是一种带密钥的散列函数（Hash Function, Hash），也就是说，只有拥有密钥才能够产生数据正确的散列值（“指纹”）。如果密钥存放在SoC中，就能保证攻击者无法拿到密钥，进而无法伪造数据的“指纹”，保证了数据的完整性。
（补图：MAC校验，密钥存放在SoC，攻击者无法获取）
内存完整性校验还需要考虑到重放攻击（Replay Attack）的可能性，也就是说，攻击者探测和保存过去的数据和“指纹”，在当前时刻进行重放（将数据篡改为过去的正确值），依然能够通过完整性校验，破坏正确的执行过程。
为了防止重放攻击，内存完整性校验需要将“时间”因素纳入到校验过程中。方法是，密钥随着“时间”的变化而变化，引入一个递增的计数器（COUNTER，CTR），作为加密密钥的一部分。在每次写入内存的时候，CTR的值加1，下一次的加密将会使用新的CTR，保证了过去的值在现在是无法通过内存完整性校验。
（补图：重放攻击，记录过去值，替换当前值）
同时，内存完整性校验还需要考虑数据交换攻击重定位攻击（relocation attack）的可能性（这里的用词可能不太专业，后续查证一下），也就是说，攻击者探测和保存多个地址的数据和“指纹”，将其他地址的数据以及指纹存放在目标地址中（做交换彼此而的数据），这样也能够通过完整性校验，破坏正确的执行过程。
为了防止数据交换攻击，内存完整性校验需要将“地址”因素纳入到校验过程中。方法和防止重放攻击的做法类似，将地址（ADDRESS， ADDR）作为加密密钥的一部分。在写入不同的地址的时候，校验机制将使用不同的密钥进行加密，防止了重定位攻击的可能性。
（补图：数据交换攻击，记录其他地址值，替换目标地址值）
以上就是完整性校验的原理，关键点在于保证密钥的安全（不能出SoC），同时防止重放攻击和数据交换攻击。
内存完整性校验过程
内存完整性校验机制包括在写内存的时候生成和部署校验码，以及读内存的时候读取和验证校验码。下文将分别从写内存和读内存两种模式，探讨内存完整性校验的过程。
写内存（加密和计算原始MAC值）
写内存的时候，首先需要写内存的内容进行加密，然后再对加密后的密文做MAC。
内存加密使用到的计数器模式加密算法（conter mode encryption），这种算法中用到了前面提到的counter和addr作为加密运算输入的一部分。具体的步骤是：在每次写回内存的时候，取到对应的计数器（C），并对其进行加1操作，然后取目标地址（A）和片上的加密密钥（K）。用AES算法得到一次性密码本（One-time pad，OTP），即OTP = AES(K, A || C) （这里的A、C之间是如何连接起来的还需要证实一下，不太确定是否是直接通过比特串拼接）。然后，AES引擎使用OTP与明文数据（P）做异或运算，得到密文数据（X），即X = OTP ⊕ P。X保证了数据的机密性，只要攻击者无法猜测到K，则无法计算出OTP，从而无法对数据进行解密（解密也是异或的过程，即P = OTP ⊕ X）。
（补图：OTP的计算，以及对P进行加密）
在保证了机密性之后，还需要对完整性进行保护。一般来说是对X做MAC，得到MAC值M，而MAC算法所使用到的密钥，正是前文提到的片上的加密密钥K，即 M = MAC(K, X)。由于攻击者概率上无法猜测到正确的K（其被安全的存放在片上），因此无法伪造M，保证了完整性。
注意的一点是，这里OTP通过AES(K, A || C)来生成的，引入了A、C来作为加密的要素，然后密文X =OTP ⊕ P。因此，我们的X中是包含了A、C的信息。正因此，保证了攻击者在交换不同地址的数据、输入历史旧值仍然无法通过校验。当我们能对X做MAC的时候，将A、C的信息也包括在了流程当中。下一节提到的数据解密和MAC验证过程中，用到了这一点。
这里有一点迷糊了，地址是是如何放置伪造的。应该是做MAC的时候，将A、C也包括进来才行。仅仅是生成OTP的时候用A、C，好像还是欠缺这个信息。
（补图：得到MAC值的过程）
上述过程中，后续在解密的过程，我们将详述这两种攻击无效的原因
读内存（解密和验证当前MAC）
当前内存中的值是一个密文的数据X，其有一个对应于自身的MAC值M。当CPU从内存中取数据时，需要解密和验证当前MAC，这两者互不干扰，可以并行执行。
首先讲解密过程，前面已经提到，通过密文数据X和OTP再做一次异或运算即可算出，但是OTP的重新生成是一个相对复杂的事情。片上的密钥K和数据存放地址A是容易获取的，但是对应地址的计数器值C不太容易。由于每个加密内存块X（512bit，64B）都对应一个C（原始的设计是64bit，8B），C有X的12.5%大小。CPU片上无法容纳所有的C，只能将其超出的部分放在内存中，这就导致了内存中C的完整性受到了安全威胁。
（补图：X解密过程，需要获取）
因此，TEE需要一套保护存放在内存上的C的完整性机制，著名的BMT（Bonsai Merkle Tree）就是C的完整性保护机制。BMT是一颗树，其根在CPU上，其他节点都在内存中。BMT要保证子节点的完整性，就需要先保证父节点的完整性。也就是说，BMT子节点的完整性由父节点的完整性保证。**由于根保存在片上的，根的完整性得到了保证，进而保证了整棵树的完整性。**但是，需要保证一个叶子节点的完整性，就需要遍历其所有祖先节点，引入了额外的数次访存。
（补图：BMT的架构图）
子节点的完整性由父节点的完整性保证这一特性的实现方式有两种。一种是BMT的实现方式，父节点是多个子节点的HASH值，只要HASH（父节点）是完整的（没有被篡改），那么数据（子节点）再进行一次HASH运算，和父节点比较（注意前提：父节点的完整性已经得到了保证）就能够校验数据完整性，这是第一种用父节点的完整性保证子节点完整性的机制。
第二种是SGX的实现方式，SGX使用了递归的方式，实现上更加优雅。在SGX的定义中，每个block都有对应着一个counter（每次写block，对应的counter的值需要+1），因此，若counter出CPU芯片存放在内存的一个block中，那么counter所在的这个block也对应一个counter（父counter）。按照树的结构将所有counter组织起来，同时，为了保证我们提到的特性，需要将父counter和这个子block中的所有子counter做一次hash，hash值存放在子block中（也就是子block中要预留一块区域放这个hash，而不是只存放子counters）。这样父节点的counter是真实性（完整性）就能够保证子节点的完整性（假如子block中的counter或者hash被修改，由于前提是父counter真实，重新校验hash得到的结果会与之前的不符合，能偶检测到子block数据被篡改）。
这里有一个思考：校验应该从根往下校验？还是叶子节点往上校验？
我的理解是，应该从根往下校验。根是确保真实的（根存放在片上保证），因此我们前面说到的前提条件在校验一开始是满足的。从根往下校验，就能够在发现第一个被篡改子节点的时候终止并返回异常。虽然这种方式校验成功需要的次数和反向的方式是一样的，即，都需要将所有层都访问一次。但是这种方式的的好处是能够从一开始就满足前提，并且cache存放顶层counter的概率会大一些，命中率比叶子节点高。如果从叶子节点往根上遍历，就会有其他的情况，没有这种方式简单直接。
（个人理解，如有不正，感谢指正）
（补图：SGX的Counter完整性校验）
可以这样说（有一点绕），主要的性能开销是由于在X解密过程中，AES引擎需要获取计数器C的值，C部分存放在内存上，引入了保证计数器值C自身完整性的开销，这时数次额外访存的开销，也就是上面提到对完整性树的访问。（C不需要保证机密性，仅有C不会泄漏机密数据X的值，因为K存放在片上是安全的）
以上就是内存完整性校验的基本原理和基本过程，这其中完整性树的访问是性能开销的主要来源，学术界针对这个问题已经提出了很多优化的方案，但在实际应用中，目前也只有SGX的方案较为成熟。对于未来的发展，将完整性保护和ECC校验（也就是内存纠错机制）结合起来可能能够进一步降低完整性校验的开销，让内存完整性的保护在更大的范围应用起来。