消息认证码预计算在安全存储器中的应用

摘要

一种方法，包括以下步骤：通过执行伪随机置换(PRP)和伪随机函数(PRF)中的至少一个从数据输入创建数据的随机置换；通过组合数据的随机置换和所接收的第二数据块并且在组合的结果上执行ε差分均匀函数，以创建第一数据块；将ε-DU函数评估的结果与秘密密钥进行异或；以及将第一数据块变为第一消息认证码。

说明书

技术领域

本发明涉及预计算认证码在安全存储器中应用的方法和装置。

背景技术

消费产品、商业产品甚至是军用设备日益地变得依赖于计算机系统。当产品与计算设备结合时，人们可以设法利用产品的弱点来免费使用产品或者破坏该产品。在计算世界中，黑客、侵权者或者对手试图利用通过篡改设备的存储器来使用计算设备的产品。典型地，在保护计算完整性时有两个主要的安全领域：基于软件和基于硬件。基于软件的安全性涉及软件的完整性。基于硬件的安全性假设黑客已经完全进入计算系统并且可能使用示波器和逻辑分析仪来观察计算系统。

通过将全部系统集成在芯片上(SoC)，芯片上的超大规模集成电路的发展已经提供防止篡改的硬件计算系统。因此将整个计算系统集成到芯片上可以阻止对手的攻击。然而，在大部分实际方案中，片上存储器的不足致使该方案无法实现。程序和数据必需存储在片外存储器中。这为对手通过篡改片外存储器来破坏计算设备打开了道路。

对存储器进行签名和加密是阻止对手成功篡改片外存储器的一种方式。消息签名类似于校验和，可以用于验证一块存储器自从上一次读取以来没有发生变化。当数据写入片外存储器时，产生签名并连同该数据进行存储。当从片外存储器读取数据时，通过签名验证来确保数据没有发生变化。产生签名可能是昂贵的操作。需要使用许多时钟周期来产生签名。因此，产生和校验存储器签名必须高效。

消息认证已经成为大量研究的一个课题。虽然大部分普通的MAC方案包括对与冗余数据(例如，32个0的字符串)连接的消息上的伪随机置换(PRP)进行简单的评估，但是这种方案没有给它们自己提供预计算。

MAC计算的另一方法使用通用哈希函数(UHF)。从UHF获得MAC的想法首先由Carter和Wegman提出(Wegman，Carter，新哈希函数以及它们在认证和集合相等性上的使用(New Hash Functions and Their Use in Authentication and Set Equality)，JCSS，22：265，1981)。Brassard稍后提出了使用伪随机发生器以减小MAC密钥的大小(Gilles Brassard，请求短秘密共享密钥的用于计算的安全认证标签(On computationally secure authentication tags requiring short secret shared keys)，Crypto’82，79-86)。相应的结构如下：MAC(m，r)＝h(m)XOR F(r)，其中h是UHF，以及F是伪随机发生器。自此，大量的研究集中在所使用的函数h和F的速度和其它方面的提高上。

MAC预计算结构与之前提出的结构不同，同时拥有在利用预计算的短消息认证中所特别期望的属性。

发明内容

在一个实施方式中，一种方法包括以下步骤：通过执行伪随机函数(PRF)和伪随机置换(PRP)中的至少一个，从数据输入创建数据的随机置换；通过组合数据的随机置换和所接收的第二数据块以及执行ε-差分均匀(ε-DU，ε-Differentially Uniform)置换，以创建第一数据块。将ε-DU函数评估的结果与密钥进行异或，并将第一数据块变为第一消息认证码。

在另一个实施方式中，一种系统包括MAC计算机，其中MAC计算机通过执行伪随机函数(PRF)和伪随机置换(PRP)中的至少一个，对来自输入的数据创建数据的随机置换，其中MAC计算机通过组合数据的随机置换和所接收的第二数据块以及执行ε-差分均匀(ε-DU)置换，以创建第一数据块，其中MAC计算机将ε-DU评估的结果与密钥进行异或，以及其中MAC计算机将第一数据块变为第一消息认证码。

附图说明

通过说明书、权利要求和附图，本发明示例实现方式的特征将变得显著，其中：

图1是计算机系统的实例框图，其中可以具有用于MAC预计算的装置和方法；

图2是可以用于使用MAC预计算来写入和读取数据的方法的实例；

图3是使用MAC预计算将数据写入存储器的方法；

图4是使用MAC预计算将数据从存储器中读取并进行认证的方法；

图5是可以包括用于执行MAC预计算装置的系统的实施方式。

具体实施方式

正如所讨论的，计算机安全的弱点区域是片外存储器。对手可以改变或者重放包含在片外存储器中的信息以破坏计算机系统。一种限制对手的方法是对片外存储器进行签名和加密。计算存储器上的签名可能需要产生消息认证码(MAC)。可利用密钥和作为输入的数据或者存储器的块来运行MAC算法。MAC算法可以输出签名或者MAC。MAC可以是一个数值。MAC可以是16比特或者32比特。然而，MAC可以更大或者更小。利用写入到片外存储器的数据来计算第一MAC。将第一MAC连同数据进行存储。当从片外存储器读取数据时，从所读取的数据产生第二MAC。如果第一MAC与第二MAC不匹配，系统可以复位和/或丢弃该数据。

转向图1，图1是系统100的实例框图，其中可以具有用于MAC预计算的装置和方法。系统100的主要组件是在片上或者片外的。系统的片外组件是动态随机存取存储器(DRAM)115形式的存储器。DRAM可以存储由驻留在系统的片上部分的软件或者程序所使用的数据。尽管在这个实施方式中描述为DRAM，也可使用DRAM、随机存取存储器、或者任意其它存储器或存储数据的方法来存储系统100中的片外数据。

属于片上的组件可以包括DRAM控制器120、加密认证单元125、总线接口逻辑130、总线135、中央处理单元140和高速缓存145、以及直接存储器存取(DMA)引擎150。

CPU 140和DMA引擎150可以通过总线135与总线接口逻辑130进行通信。总线接口逻辑130可以与EAU 125通信地耦合。EAU 125可以进一步与DRAM控制器120通信地耦合。DRAM控制器可以与DRAM 115通信地耦合。

CPU 140和DMA 150可以从DRAM 115读取数据或者将数据写入DRAM 115中。当CPU 140或DMA 150从DRAM 115读取数据或者将数据写入DRAM 115中时，读取或者写入的数据流经总线接口逻辑130、EAU125和DRAM控制器120。在读取和写入数据时，总线接口逻辑130处理所有大小的业务。然而，EAU 125只从片外DRAM 115读取固定大小的数据块并将固定大小的数据块写入片外DRAM 115中。可以将固定大小的块称为加密块或者数据块。在一个实施方式中，一个数据块包括256个比特。加密块可以是从存储器115读取数据或者将数据写入存储器115的最小单元。由于总线接口逻辑130处理所有大小的业务，EAU 125不得不管理对大于或者小于加密块的数据的读取或写入请求。

在一个实施方式中，用于消息认证码预计算的方法和系统可以驻留在EAU 125上。EAU 125可以执行对向DRAM 115写入或者从DRAM 115读取的数据的加密/解密和认证。在去往DRAM 115的途中可以对写入业务进行加密。在从DRAM 115读取信息时，可以对读取业务进行认证和解密。从而，EAU 125向存储器写入或者从存储器读取的任意数据块可以包括加密的数据。

在认证数据或存储器时，EAU 125可以产生用于数据块的第一MAC，其中EAU 125将该数据块写入存储器。第一MAC于是与该数据块相关联。当从存储器读取数据块时，EAU 125可以根据所读取的数据来产生第二MAC。可以将第二MAC与第一MAC进行比较。如果第一MAC和第二MAC不匹配，则存储器可能已经被破坏或损坏。如果存储器被破坏，EAU125可以执行存储器破坏(corruption)过程。这可能需要使系统复位，或者发送消息给CPU以通知CPU存储器异常。CPU随后可以将系统复位或者采取一些其它的保护动作。

具体地，在与存储器业务相关联的数据到达之前，EAU 125接收存储器业务的地址。从而可以在数据到达前执行包括加密数据和产生MAC的大量计算。

转向图2，图2是用于使用MAC预计算写入和读取数据的方法200在安全存储器中应用的一个实施例。方法200可以驻留在加密认证单元125上。该方法首先处理请求210。该请求可以是读取数据或写入数据的请求。该请求可以来自总线接口逻辑130。当总线接口逻辑130发送读取数据或写入数据的请求时，总线接口逻辑130可以将地址传递给方法200。如果请求是写入请求，则地址可以是数据将要写入的地址。如果请求是读取请求，则地址是从其中读取数据的地址。

方法200随后确定请求是否是写入请求215。如果请求是写入请求，方法200调用写入处理器(handler)220。由于这是个写入请求，总线接口逻辑130可以将写入地址传递给方法200。当方法200调用写入处理器时，方法200可以将地址或者写入地址传递给写入处理器。在完成了写入处理器之后处理请求，方法200继续处理请求210。

如果输入的请求不是写入请求，方法200确定该请求是否是读取请求225。如果请求不是读取请求，方法200返回到处理请求210。如果请求是读取请求，方法200可以调用读取处理器230。当方法200调用读取处理器时，方法200可以将地址或者读取地址传递给读取处理器。

转向图3，在一个实施例中，一种使用MAC预计算可以将数据写入DRAM 115的方法。写入处理器方法或者写入处理器300可以驻留在片上以作为EAU 125的一部分。当EAU 125接收数据时，EAU 125可以产生MAC并且还可以对数据进行加密。当写入处理器接收地址310时该处理开始。地址可以是DRAM 115中的位置，其中假设EAU 125写入数据。地址可以是32比特的地址、16比特的地址或者可以用于对DRAM 115进行寻址的任意其它大小的地址。为了便于说明，我们将假设地址的长度为32比特。此时，数据可能还没有到达。

由于地址现在是可用的，MAC计算就可以开始了。方法300不必等到数据到来才开始进行MAC计算。EAU 125可以通过连接208比特的0(填充)、32比特的地址和16比特的随机数(0、地址、和随机数)来创建256比特的数据块。256比特的数据块可以是数据输入。部分计算MAC可以包括使用数据输入来评估PRF或PRP或随机性。对本领域技术人员来说明显的是，PRF/PRP是理想化的分组密码，其中密码导致不能从随机性中识别出来的比特图样。部分计算MAC还可以包括评估epsilon差分均匀(ε-DU)函数。对本领域技术人员来说明显的是，ε-DU函数可以是导致随机比特图样的分组密码。然而，由ε-DU函数创建的比特图样的随机性不如由PRP创建的比特图样的随机性好。从而，由ε-DU函数创建的比特图样可能不如由PRP创建的比特图样安全。本领域技术人员还可以认识到，随机数(nonce)，或者使用一次的数，即使重复使用也是很少的数。在该实施方式中，随机数可以是每次执行写入时增加的计数器。

PRP或者PRF函数F可以用于创建在对随机数、地址和0进行加密时所需要的随机水平。方法300可以运行Rijndael(或者它是最流行的示例，高级加密标准或AES)F 320。方法300可以在数据输入(0、地址和随机数)上运行14次Rijndael以获得随机的256比特。随机的256比特可以是Rijndael写入块或Rijndael块。例如，随机值或随机性可以是一连串1和0。注意，在一些实施方式中，PRP F可以通过在两组128比特上运行10次AES版本的Rijndael来实现。将两组128比特进行连接以形成256比特的块。当运行Rijndael时，方法300选择随机密钥k1。Rijndael算法可以使用密钥k1作为Rijndael算法的输入。随机或秘密的密钥是随机选择的密钥。例如，随机数发生器可以用于选择随机密钥。可以使用随机发生的其它形式来选择随机密钥。

方法300接收写入数据330。当方法300接收写入数据时，方法300可对数据进行加密。方法300可以通过使用AES、或者任意其它对数据进行加密的方法对数据进行加密。加密数据可以与Rijndael写入块335进行异或335。结果可以是异或的Rijndael写入块。异或的Rijndael写入块可以包括256比特。

方法300可以计算ε-DU函数族的函数G。方法300可以选择第二随机密钥k2，其中k2用作ε-DU函数族的输入。ε-DU函数G可以在异或的Rijndael写入块上运行340。函数G可以是在异或的Rijndael写入块上2次或4次Rijndael的评估，从而结果是256比特的G写入块。G写入块可以与256比特的密钥k3进行异或345，其结果是256比特的M块。通过使用异或树，可以将M块从256比特分解为32比特的MAC或者第一MAC350。加密数据块可以存储在DRAM 360中。32比特的第一MAC和随机数也可以存储在DRAM 360中并与加密数据块相关联。因此，当需要对加密数据进行认证时，可以取回执行认证所需的信息。密钥k1、k2和k3可以存储在EAU中。

尽管在该实施例中，用于预计算MAC的方法和装置用于将数据写入到存储器中，但是该方法和装置还可以用于包括写入数据和发送数据的任意应用中。在其它实施方式中，不使用存储器地址来预计算MAC，而是使用其它值来计算MAC。例如，如果该方法和装置用在消息应用中，可以使用消息上下文识别符来代替地址。此外，地址的大小、随机数和其它变量可以根据用户需求和使用该方法的应用进行变化。

转向图4，图4是在一个实施例中可以从DRAM 115读取数据的方法400。在从DRAM 115读取数据的过程中，方法400可以认证数据。认证数据可能需要根据所存储的数据产生第二MAC，并将第二MAC与初始连同数据进行存储的第一MAC进行比较。方法400可以从总线接口逻辑130接收地址或者读取地址410。

方法400可以检索认证数据所需的信息420。该信息可以包括可能驻留在片上的诸如密钥k1、k2和k3的信息。此外，该信息可以包括可能驻留在片外的诸如第一MAC、随机数和驻留在读取地址上的读取数据的信息。该读取数据可以是加密数据。

方法400可以如图3所述的根据地址、随机数和0(0填充)计算PRPF 430。需要用密钥k1来计算PRP F。注意，当认证或读取数据时，用于计算PRP F的密钥k1可以与当写入数据时用于计算PRP F的密钥k1相同。如上所述，通过关于随机数、地址和208比特的0运行14次Rijndael来得到PRP F。14次Rijndael的结果可以是可能是Rijndael块的随机的256比特。还可以通过并行运行的两个示例来获得F，其中该示例为10次128比特AES版本的Rijndael。在读取数据时，Rijndael块可能指的是Rijndael读取块。

在计算G 440时，Rijndael读取块可以与读取数据进行异或。结果可以是异或的Rijndael块或异或的Rijndael读取块。可以通过在异或的Rijndael读取块上运行2次或4次Rijndael来获得G。计算G 440的结果可以是256比特的G块或G读取块。注意，用于计算G写入块的相同密钥k2可以用于计算G读取块。

G读取块可以与密钥k3进行异或以得到256比特的M读取块。通过异或树450可以将M读取块变为为32比特的第二MAC。可以将第二MAC与第一MAC进行比较470。回想到第一MAC是在将数据初始写入DRAM115时产生的。如果第一MAC和第二MAC不相等，则数据可能已经被破坏或损坏。方法400通过执行存储器破坏响应程序来处理该失配490。如果第一MAC和第二MAC相等，方法400可以将读取数据返回给总线接口逻辑130。由于MAC失效可能导致系统复位，因此还可以先于MAC认证将数据传递给CPU。可以将所描述的方法300和400称为浅MAC(shallow MAC)或者shMAC。

转向图5，图5描述了可以包括用于执行MAC预计算的装置的系统550的实施方式。系统500可以由总线接口逻辑单元130、DRAM控制器120和EAU 125组成。EAU 125可以进一步由数据处理器530、MAC计算机535和数据加密器540组成。MAC计算机535可以进一步由MAC PRPF计算器545和ε-DU计算器550组成。

如上所述，EAU 125可与DRAM控制器120和总线接口逻辑130通信地耦合。DRAM控制器120和总线接口逻辑130可以与数据处理器530通信地耦合。数据处理器530可以是能够与EAU 125的外部进行数据读取和写入的节点或组件。节点或组件可以是软件、固件、硬件或者能够执行计算的任意其它类型的装置。

数据处理器530还可以与MAC计算机535和数据加密器540通信地耦合。MAC计算机535可以是能够预计算MAC的节点或组件。数据加密器540可以是能够对数据进行加密的节点或组件。

MAC计算机535可以进一步由PRP F计算器545和ε-DU计算器550组成。PRP F计算器545是能够计算PRP F函数的组件或节点。ε-DU计算器550是能够计算ε-DU函数的组件。

总线接口逻辑130可以发送请求以从DRAM 115读取数据或向DRAM115写入数据。数据处理器530可以接收该请求。写入数据的请求可以来自两部分。首先，总线接口逻辑130可以将地址发送给数据处理器530。在典型的系统中，2个或多个时钟周期后，数据处理器530可以接收与地址相关联的写入数据。在读取数据时，总线接口逻辑130可以发送读取地址。数据处理器通过将读取数据发送给总线接口逻辑130来进行响应。

如果数据处理器530接收到写入请求，数据处理器530可以将写入地址转发给MAC计算机535和数据加密器540。在一些实施方式中，写入地址可以是32比特。数据加密器540可以用写入地址作为加密数据过程的一部分。MAC计算机535可以将写入地址和和随机数转发给PRP F计算器545。在一些实施方式中，随机数可以是16比特。PRP F计算器545可以产生随机密钥K1以用于执行Rijndael函数。PRP F计算器545可以使用K1在256比特的数据输入上运行14次Rijndael(或者两个并行的示例，其中该示例为2次128比特AES版本的Rijndael)。数据输入可以由208比特的0、32比特的地址和16比特的随机数组成。在数据输入上运行14次Rijndael的输出可以是可被称为Rijndael块或Rijndael写入块的256比特的随机数。PRP F计算器545可以将Rijndael写入块传递给ε-DU计算器550。在一些实施方式中，此时写入数据已经到达。然而，PRP F计算器545已经运行Rijndael并创建了Rijndael写入块。

当写入数据到达时，数据处理器530可以将写入数据转发给数据加密器540。数据加密器540可以对数据进行加密并将加密数据传递给ε-DU计算器550。ε-DU计算器550可以将加密数据与Rijndael写入块进行异或。结果可以是256比特的异或Rijndael块或异或Rijndael写入块。ε-DU计算器550可以在初始时产生或选择随机密钥K2。ε-DU计算器550可以使用K2在异或的Rijndael写入块上运行2次或4次Rijndael。在异或的Rijndael写入块上运行4次Rijndael的结果可以为256比特的G写入块。G写入块可以与256比特的密钥K3进行异或以得到256比特的M块。

通过使用异或树，可以将256比特的M块分解为32比特MAC或者第一MAC。可以将加密数据写入DRAM 115中。随机数和第一MAC还可以存储在片外，同时可以与写入到DRAM 115的加密数据相关联。随机数

当数据处理器530接收读取请求时，数据处理器530可以利用读取请求接收读取地址。数据处理器530可以将读取地址传递给MAC计算机535。MAC计算机535可以从片外存储器取回第一MAC、随机数和读取数据。在将读取数据写入DRAM 115时，MAC计算机535还可以取回存储在片上的密钥K1、K2和K3。MAC计算机535可以将密钥、第一MAC、随机数和读取数据传递给PRP F计算器545。PRP F计算器545可以利用K1在由208比特的0(0填充)、32比特的地址和16比特的随机数组成的256比特的数据块上运行14次Rijndael。或者，与写入处理器相关，PRP F计算器545可以并行运行2个示例，其中该示例为2次运行128比特AES版本的Rijndael。运行Rijndael的输出可以为被称为Rijndael块或者Rijndael读取块的256比特的随机数据。PRP F计算器545可以将Rijndael读取块传递给ε-DU计算器550。

ε-DU计算器550可以将加密读取数据与Rijndael读取块进行异或。结果可以是256比特的异或Rijndael块或异或Rijndael读取块。ε-DU计算器550可以在异或Rijndael读取块上使用K2运行4次Rijndael。运行2次或4次Rijndael的结果可以是256比特的G块或G读取块。可以将G读取块与256比特的密钥K3进行异或以得到256比特的M块或M读取块。

通过异或树，可以将256比特的M读取块分解为32比特的第二MAC。可以将第二MAC与第一MAC进行比较。如果第二MAC与第一MAC不相同，则读取数据可能已经被损坏或破坏。如果存储器被损坏或破坏，MAC计算机535可以执行存储器破坏响应程序。

用于消息认证码预计算的系统和方法可以是无状态的。无状态的认证和加密算法可能将存储器对重放攻击开放。例如，对手可以利用之前存储在存储器相同存储单元中的值来替换该存储器的存储单元。相似地，对手在写入业务中可能完全不更新DRAM。这些攻击会导致存储器在解密和认证后将错误认为是正确的。

为了提高效率起见，可以为全部存储器或者大部分存储器创建加密和认证密钥。为了抵制上述的重放攻击，与存储器相关联的加密和认证密钥可以周期性地进行更新。

存储器密钥更新的实施方式可以包括将存储器分为2个区域。存储器是可以被分为第一区域和第二区域的有序阵列。通过边界地址可以将第一区域和第二区域进行分隔。可以利用密钥的第一集合对第一区域进行加密和认证。可以利用密钥的第二集合对第二区域进行加密和认证。更新方法包括牺牲其它区域来增加存储器的一个区域。从而在第二区域的边界到达存储器的末端之前第二区域可以增加。存储器的末端可以是最高可寻址的地址或最低可寻址的地址。

在将数据写入存储器的第二区域时，可以使用密钥的第二集合对数据进行解密和认证。当边界到达存储器的末端时，例如边界到达最低可寻址的地址时，用于存储器的第一区域的密钥可以退役(retired)，并可以产生用于存储器第一区域的密钥的新的第三集合。在将数据写入存储器时，使用密钥的第三集合对数据进行加密和认证，并将数据放置在存储器的第一区域。牺牲存储器的第二区域可以增加存储器的第一区域。这一直持续到边界再次到达存储器的末端，例如存储器的最高可寻址的地址。该方法通过产生密钥的第四集合而继续。在将新数据写入存储器时，使用密钥的第四集合对数据进行加密和认证，并将数据放置在存储器的第二区域。重新产生密钥以及写入存储器的不同区域的该方法继续。

在一个实施例中，系统500包括多个组件，例如一个或多个计算机软件组件。在系统500中多个这样的组件能够进行合并或拆分。系统500的一个示例性组件利用和/或包括一组和/或系列利用任意或多个编程语言所书写或者执行的计算机指令，这对于本领域技术人员来说是显而易见的。在一个实施例中，为了便于解释的目的，系统500包括垂直方向，这里的说明书和附图描述系统500的一个示例性方向。

在一个实施例中，系统500利用一个或多个计算机可读信号承载媒介。计算机可读信号承载媒介存储用于执行本发明的一个或多个实现的一个或多个部分的软件、固件和/或汇编语言。在一个实施例中，用于系统500的计算机可读信号承载媒介包括一个或多个磁、电、光、生物和原子数据存储媒介。例如，计算机可读信号承载媒介包括软盘、磁带、CD-ROM、DVD-ROM、硬盘驱动器和电子存储器。

这里所描述的步骤或操作仅用作示例。在不偏离系统500和方法200、300、400的精神下，可以对这些步骤或操作进行多种改变。例如，可以按不同的顺序执行步骤，或者可以增加、删除或修改步骤。

尽管这里详细描述和说明了系统500和方法200、300、400示例性的实现，但是在不偏离方法200、300、400的精神下能够进行各种修改、增加、替代以及类似操作，这对所属领域的技术人员来说是显而易见的，并且因此被认为是落在系统500和方法200、300、400的、如下列权利要求所限定的范围内。