基于多项式拟合频率重构的物理不可克隆函数优化*

2021-04-25黎帮梅陈怀新刘小宇王成刚李思奇

电讯技术 2021年3期

黎帮梅，陈怀新，刘小宇，王成刚，李思奇

(1.电子科技大学资源与环境学院，成都611731；2.中国西南电子技术研究所，成都610036)

0 引言

近年来硬件安全不断受到挑战，硬件保护技术获得了研究者更多的关注，例如比特流配置加密技术[1]。但由于配置比特流需要引入额外的解密单元，所以导致了额外的硬件和功率开销。此外，解密的密钥常常被存储在非易失性存储器中，在解密过程中容易被窃取，攻击者可以轻松获得配置数据[2]。在芯片领域，现场可编程门阵列(Field Programmable Gate Array，FPGA)凭借其可编程灵活性高、开发周期短、并行计算效率高的显著优势在各领域得到了广泛应用。因此，采用FPGA的物理特性参量进行硬件加密算法的设计是研究硬件安全保护的有效手段。物理不可克隆函数(Physical Unclonable Function，PUF)是一种从制造变化中提取信息的电路，可以利用集成电路制造过程的固有变化为各种与安全相关的应用生成安全的密钥[3]，攻击方若想篡改密钥，必须破坏其硬件物理特征，故可以有效防止篡改。PUF大致可分为三类[4]：非电子类、模拟电子类、数字电路类。在数字电路PUF中，仲裁器PUF[5]的布局布线要求高对称性，基于静态随机存取存储器(Static Random Access Memory，SRAM)的PUF[6]每次生成响应都要求重启一次电路，而环形振荡器(Ring Oscillator，RO) PUF[7]克服了前两者的缺点，能够灵活地应用于信息安全领域[8]。因此，RO PUF一直是硬件安全领域的研究热点。

在RO PUF的多个性能指标中，随机性能够衡量PUF生成的密钥是否足够安全，而熵密度是表征随机性好坏的重要度量标准[9]。目前，针对RO PUF随机性优化的研究主要分为两个方向：一是在频率产生后对频率进行处理；二是改进RO PUF的结构从而直接改变原始频率，如使用非线性组合生成器结构[10]，但是这样的方法对于硬件资源的需求更大，且实现复杂度更高。因此，本文选择从第一个方向入手对随机性进行优化。该方向上的典型方法主要有随机补丁混合方法(Radom Path Mix,RPM)[11]和基于回归的熵蒸馏法[12]，但存在不足之处：RPM通过外在添加随机矩阵对RO阵列原始频率分布进行改变，因此这种方法过于依赖随机矩阵；基于回归的熵蒸馏法将残差项作为被比较的对象，虽然表现出了与原始频率分布相似的分布特征，但随机性优化能力并不突出。针对以上问题，本文提出一种频率重构的方法，生成具有高随机性响应的RO PUF，并采用熵密度进行评估。

1 RO PUF原理方法

1.1 RO PUF的电路结构及比较策略

RO PUF是一种典型的硅物理不可克隆函数，由RO 阵列、选择器组、计数器组和比较器组四个部分构成[13]，RO PUF原理的电路结构如图1所示[14]。

图1 RO PUF原理电路结构

RO阵列由一定数量的电路结构完全相同的RO构成，RO通常是一个由奇数个反相器构成的振荡环路。输入的激励信号通过选择器从RO阵列中选择一对 RO 连接到两个计数器中，两个计数器分别统计两个RO在一定时间间隔内的振荡次数。计数结束后，振荡次数被输入到比较器中，最后由多个比较结果构成一串二进制响应比特序列，可作为表征硬件身份的物理指纹[15]。

RO PUF比较策略是生成随机响应的方式，链式相邻比较[16]是当前硬件利用率较高的一种比较策略，也是最常见的一种比较策略。设有3个相邻RO，即RO1、RO2、RO3，RO1与RO2相邻，构成一个比较对，RO2与RO3构成一个比较对。因此，N个RO构成的RO阵列，能够产生N-1位响应[17]。在这种比较策略下，除了链首尾的两个RO频率仅被比较1次之外，其他RO的频率均会被比较2次。响应产生的依据[18]可以表示为

(1)

1.2 熵密度计算

RO PUF产生的响应随机性可采用熵密度值来定量评估，对RO PUF的攻击和防护可以理解为降低和提高响应所携带熵的过程。因此，计算熵密度[19]通常是在不同的芯片上选择相同的RO得到的响应位为0或1的概率均为0.5。在本文研究中，将区域中的6列RO等价于6个芯片中的RO阵列。如果相邻6列RO所产生的响应都具备了良好的熵密度，那么在不同芯片上必定会具备更理想的熵密度。

在链式相邻比较策略中，根据每列RO的频率集合生成的密钥Xl可以表示为

(2)

式中：Xl(r)代表Xl中的第r位，Cntl(m,r)和Cntl(m+1,r)表示生成的Xl中的第r位所使用第m个RO和第m+1个RO的计数器输出值。在链式相邻比较策略中，第m个RO和第m+1个 RO是相邻的。

对于熵密度计算而言，建立平均响应集十分关键。对于每一列第m个RO的平均计数值Cntavg(m)可以表示为

(3)

式中：M是RO阵列的行数，N是列数。

根据每一列第m个RO的平均计数值Cntavg(m)生成的平均响应集Xavg可以表示为

(4)

式中：Xavg(r)是Xavg的第r位，用于产生Xavg(r)的第m和第m+1个RO的平均计数值由Cntavg(m,r)和Cntavg(m+1,r)表示。

评估Xl中预测的每个比特的概率P(r)可以表示为

(5)

式中：P(r)表示X中第r位响应可由Xavg成功预测的概率，⊙为异或操作。

熵密度Hden是随机变量统计分布的函数，表示不确定性大小。熵密度Hden可以表示为

(6)

当P(r)接近0.5时，Hden(X)的值将接近最大值0.5，说明PUF更加安全，随机性更好。这样的值将保证在不同FPGA之间相同位置的位之间没有相关性[20]。

2 基于多项式拟合的RO频率重构方法

2.1 RO硬宏设计及其阵列频率采集分析

本研究在Xilinx Artix 7103 FPGA上进行实验，芯片上共有7 925个可配置逻辑块(Configurable Logic Blocks，CLB)，1个CLB由2个slice组成，其在芯片上的排列如图2所示，图2中的CLB位于CLB资源的左下角。

图2 CLB与slice的关系示例图

RO的硬宏设计是实现RO电路的第一步。1个slice内部有4个逻辑函数发生器(或查找表)。1个3阶RO由3个反相器组成的回路构成，1个反相器将占用1个查找表，那么在同一CLB内，1个3阶RO的分布主要是两种情况，即3个反相器均位于1个slice和3个反相器分别以2∶1的比例分布在2个slice中。

3个反相器同在一个slice中，可能出现频率过高无法正确测量频率的情况，如图3所示。在Xilinx Artix 7103 FPGA上进行实例化时，实验数据表明占用1个slice的3阶RO频率可达1 000 MHz，超过了FPGA的最高工作频率，同时在示波器上跳变范围较大，难以得到一个稳定的频率值。

图3 3阶RO占用一个slice的硬宏设计

相反地，占用2个slice的3阶RO频率始终在FPGA的工作频率内，且在示波器上显示较为稳定，因此选择占用2个slice的3阶RO作为本文研究的频率来源。1个3阶RO占用2个slice中的硬宏设计如图4所示。

图4 3阶RO占用两个slice的硬宏设计

在CLB资源中实现一个50行×6列的3阶RO阵列，实测阵列频率均值分布如图5所示。

图5 50行×6列的3阶RO频率分布图

图5的RO阵列可拆分为独立的6列，每一列RO在链式相邻比较策略下，可得到6×49位响应。RO PUF的随机性好坏最直接的表现为响应中的0和1分布是否均匀，而影响响应比特的直接原因就是频率，相邻RO的频率大小比较结果在链式相邻比较策略下总是为“1”或者“0”导致了响应均匀性较差，进而表现为随机性较差。6×49位响应的均匀性如表1所示。

表1 50行×6列的RO阵列的响应均匀性

由表1最后一列中的平均值可以看到，在6组响应中，“1”平均占比为53.74%，“0”平均占比为46.26%。这说明了在相邻RO的频率进行比较时，偏向“1”的可能性更大，并不满足随机性的初步条件。

观察图5可以看出，RO的频率存在一定系统特性，高频率总是出现在下方，低频率总是出现在上方，因此推测RO的频率与所处的物理位置存在一定关系。若将所选矩形区域左下方看作坐标零点，那么RO的频率大体上沿y坐标轴呈下降趋势。对于x坐标轴，无明显变化趋势，但对于不同的x，相同y坐标位置的RO的频率也是不相同的。因此，从行列方向上对频率进行重构是我们的着力点。

2.2 基于多项式拟合的频率重构方法

针对相邻RO频率具有严重偏向性而带来的RO PUF随机性低的问题，本文提出一种基于多项式拟合的频率重构方法，关键步骤是对每一个RO实测频率与行列方向的频率中值的差值进行多项式拟合，从而构建重构项。具体算法处理如下：

首先计算各行RO的频率中值fmedi和各列RO的频率中值fmedj。中值的计算公式如下：

(7)

式中：f(1),f(2),…,f(s)以从小到大的顺序排列。选择中值的原因是不受偏大或偏小数据的影响，均值则容易受到影响。而硬件实验中会因为芯片长时间工作或外在环境的突发状况而出现频率值过高的情况，从而导致某个RO的频率均值明显高于实际频率，所以用它代表全体数据的一般水平更合适。

RO的原始频率值与对应行或列的频率中值的频率差值矩阵计算公式如下：

(8)

(9)

式中：1≤i≤M,1≤j≤N，M是RO阵列的行数，N是列数。

再将行编号和列编号分别作为自变量，将差值矩阵作为因变量进行多项式拟合，计算公式如下：

(10)

(11)

(12)

3 实验与结果分析

3.1 定性比较分析

3阶RO的实例化在软件ISE 14.7中完成，每个RO的频率均被测量5次，取其平均值，其平均频率分布如图5所示。响应采集则在串口程序中实现，在上位机中存储起来，便于后续分析。

选择图5中的50行6列区域的3阶RO阵列，设置1～5阶的拟合阶数，对频率进行重构，结果如图6所示。

图6 应用1～5阶拟合的频率重构方法后的频率分布

由图6可看出，从1阶开始，上半部分的频率明显增大，有效减缓了频率“上低下高”的分布特性。需要注意的是，对于5阶而言，得到的新的频率矩阵虽直观上看来与原始频率矩阵相似，但是色度条范围并不一致，因此基于5阶拟合的RO频率矩阵，相邻RO频率差异必然大于原始频率矩阵。尽管色度条范围大小不一致造成了这样的视觉效果，但是从频率变化趋势而言，与未重构之前的RO阵列的频率相比仍然相似。通常情况下，攻击方在获得多个未经重构的同一型号芯片后，可掌握芯片上的RO阵列的分布规律。但是，对于重构以后的RO阵列，由于都具有“上低下高”的分布规律，攻击方很有可能会误把重构过后的RO阵列当做原始RO阵列，从而降低了被攻击的风险。

对比随机补丁方混合法和基于回归的熵蒸馏法，对同一RO阵列任意进行5次RPM方法处理，结果如图7所示。

图7 任意5次应用RPM方法后的RO阵列频率分布

由图7可以看出，RO频率的分布规律被打破，甚至呈现“上高下低”的分布规律。可以看到，RPM方法使原始RO阵列中的低频区域变换为高频区域，将高频区域换为低频区域。若攻击方在掌握多个原始RO阵列后，观察其分布规律为“上低下高”，再观察RPM方法处理后的RO阵列，得出“上高下低”的分布规律，显然与原始分布规律不同，那么很有可能对RPM方法进行建模学习，从而实现有效的攻击。

对同一RO阵列进行1～5阶的熵蒸馏处理，结果如图8所示。

图8 经过1～5阶回归熵蒸馏后的残差频率分布

由图8可以看出，基于回归的熵蒸馏法有效减缓了原始RO阵列“上低下高”的分布频率。因为熵蒸馏法得到的是残差频率，结果有正有负，绝对值大小仅为个位数，而对应位置的RO原始频率均在400 MHz以上，因此与原始RO阵列频率比较并无意义。由图8(b)～(f)对比发现，不同阶数的熵蒸馏对于分布规律并无显著影响。

对于RO PUF响应的随机性而言，需要经过计算熵密度来定量评估。

3.2 定量比较分析

对RO阵列的频率采用不同阶数的多项式拟合的频率重构方法进行处理，再经过链式相邻比较得到响应并进行熵密度计算，结果如表2所示。

表2 原始响应与1～5阶频率重构后的响应熵密度

由表2可以看出，在应用多项式拟合方法之后的响应熵密度都更接近0.5，而1阶拟合就可以达到0.50，而未应用随机性优化方法的响应熵密度为0.46，有了明显的改善。熵密度的大小与多项式拟合时的阶数并无线性关系，重构的频率并不会因为阶数上升而进行同方向的增加或者减少。5个不同阶数的频率重构法得到的熵密度均值为0.50，达到熵密度的理想值。

对任意5次处理后的RO阵列经过链式相邻比较得到的响应进行熵密度计算，结果如表3所示。

表3 原始响应与应用RPM方法后的响应熵密度

由表3可以看出，应用RPM方法并不能百分百提高熵密度，甚至会出现熵密度降低的情况，5次的熵密度均值为0.46。

对经过1～5阶回归熵蒸馏处理的RO阵列通过链式相邻比较得到的响应进行熵密度计算，结果如表4所示。

表4 原始响应与应用1～5阶熵蒸馏后的响应熵密度

由表4可以看出，熵蒸馏法对于响应的熵密度提高仅为2个百分点，均为0.48。同样地，不同阶数的熵蒸馏并不会导致熵密度呈现对应的变化。5个不同阶数的熵蒸馏法得到的熵密度均值为0.48。

比较表2与表3、表4，三种方法的熵密度对比如图9所示。

图9 三种方法的熵密度比较

对于基于多项式拟合的频率重构和基于回归的熵蒸馏法而言，横坐标表示多项式阶数，而对于RPM方法而言，则表示实验编号。可以看出本文提出的方法得到的熵密度始终大于其他两种方法，更接近甚至等于理想值0.5。产生这种结果的原因在于，本文方法对频率的重构是利用原始频率来进行频率重构的，而RPM方法的频率改变是基于外在产生的随机矩阵的，因此这种方法的随机性优化能力并不稳定。基于回归的熵蒸馏法通过对残差项进行比较来获得响应，残差项完全代替原始频率值进行比较。而不管是几阶多项式，使用本文方法得到的响应都具有更高的熵密度。