一种基于线性反馈移位寄存器的轻量级强PUF设计

侯 申 ， 郭 阳 ， 李 暾 ， 李少青

(1. 国防科技大学计算机学院，湖南 长沙 410073；2. 信息工程大学洛阳校区基础系，河南 洛阳 471003)

近年来，随着无线互联的发展，移动互联网和物联网(internet of things，IoT)设备迅速增加，进入到工业和生活的各个方面。Gartner预测，到2020年IoT设备总数将达到204亿[1]。作为IoT设备核心的嵌入式微处理器，面临着过度制造、软件篡改、物理侵入式攻击等新的安全挑战[2]。由于IoT架构与传统互联网的区别，其安全问题很难利用传统手段解决。同时，对于大部分IoT设备有限的硬件资源来说，集成安全模块要增加硬件开销，可能会引起一些问题[3]。因此，发展新型的轻量级硬件安全原语，为资源集约型设备提供密钥生成和认证等安全服务，成为研究的热点。

数字电路在制造过程中，每个器件的尺寸、门限电压、栅氧厚度等参数不可能做到完全相同，均存在微小的、随机的工艺偏差。工艺偏差不会对器件的功能产生影响，也不会影响电路的正确性。通过一些特殊的设计手段将这些工艺偏差提取并数字化，可以作为电路和芯片专有的可精确辨识的特征，从而防止其被非法克隆或过度制造，这类物理系统称为物理不可克隆函数(physical unclonable function，PUF)。PUF采用了一种称为“激励-响应”的工作机制，只有在施加一个特殊激励时，其独特的数字化特征(响应)才会生成。得益于该机制，PUF也可用来为加密算法产生更安全的密钥。密钥可以实时生成，且无需在非易失性存储器(non-volatile memory，NVM)中存储。PUF作为一种新兴的硬件安全原语，在密码学、硬件安全、特别是嵌入式IoT设备安全等领域有着无可比拟的优势和广泛的应用前景。

一个PUF可能对不同的激励具有不同的响应，每个激励和其对应的响应称为 PUF的一个“激励-响应”对(challenge-response pair，CRP)。根据CRP的数量与PUF物理实体大小之间的关系，PUF可分为弱PUF和强PUF[4-5]。弱PUF仅有少量CRP，常用于加密算法的密钥生成。强 PUF具有较大的CRP空间，适用于设备认证[6]。2种PUF均需要有很好的随机性、唯一性和可靠性来保证自身安全，在用于IoT设备时还需有较小的硬件开销。然而，目前多数强PUF设计较为复杂，硬件开销较大。而线性反馈移位寄存器(linear feedback shift register，LFSR)作为一种随机性能好、逻辑简单的伪随机数产生电路，可以用做构造低开销强PUF。

本文首先介绍了PUF和LFSR方面的研究现状，然后描述了基于LFSR的轻量级PUF设计原理和其在Xilinx公司最新的28 nm FPGA上的实现，最后测试并评估了该 PUF的性能并与一些经典设计进行了比较。

1 研究背景

1.1 物理不可克隆函数

2002年，PAPPU[7]提出 PUF的概念，同时还提出了一种基于光学系统的PUF。此后，各种不同种类的PUF相继被提出。按照PUF的实现方式，可分为非电子、模拟和数字 3类。其中，数字类PUF直接以数字方式进行响应测量，不需要进行模数转换，其设计符合标准IC设计制造流程，可以整体集成到IC器件中，具有最广泛的研究和应用前景。而其中最具代表性的设计有基于环形振荡器(ring oscillator，RO)的 PUF[8]和基于仲裁器(arbiter)的PUF[9]。

RO是一种以特定频率振荡的简单电路，其受工艺偏差影响而变化。通过对比2个相同RO的实际振荡频率来构造PUF，其实际振荡频率由于工艺偏差而存在微小差异，通过比较可以产生响应输出。图1为一个简单的基于RO的PUF。

图1 基于RO的PUF结构

一种经典的仲裁器 PUF由一个多级交叉开关链构成，其基本结构如图2所示。同样的输入连接到上下2个路径中，每条路径的连接方式由作为激励的每一级中2个多路开关的控制信号决定。在同一个激励下，虽然2个路径的布局完全一致，但工艺偏差的存在会导致 2个路径的延时存在微小时差。通过仲裁器判定路径延时快慢，从而输入逻辑0或1。

图2 仲裁器PUF结构

1.2 利用弱PUF构建强PUF

仲裁器PUF作为一种经典的数字式强PUF结构，具备强 PUF的所有特点，但其缺点也同样突出。首先，仲裁器 PUF的面积开销较大，且随着需要响应位数的增加，其面积迅速增大。其次，从一些实现了的仲裁器PUF来看，CRP空间虽然足够大，但其响应的唯一性较差。第三，通路延时由通路上多个反相器延时线性叠加构成，容易遭受机器学习类攻击。这些问题限制了仲裁器PUF的应用。对于IoT设备其资源有限、部署数量巨大的应用，硬件开销小、唯一性好的强PUF设计非常必要。

通常来说，弱 PUF的稳定性和响应唯一性要好过现有的强PUF设计，通过组合弱PUF和混淆逻辑来构造强 PUF成为一种可行的设计思路。前端使用弱 PUF提供不可克隆特性，后端使用轻量级伪随机数发生器对弱 PUF的响应进行混淆。混淆逻辑有多种选择，如AES[10]、神经网络[11]等。

1.3 线性反馈移位寄存器

反馈移位寄存器通常由移位寄存器和反馈函数组成，当反馈函数为线性时，相应的反馈移位寄存器称为 LFSR。最常用线性函数是 XOR。LFSR作为一种可以产生伪随机数序列的电路，在密钥生成、通信领域应用广泛[12-13]。LFSR电路构成简单，可配置性强，本身作为时序电路工作性能很高，在占用硬件资源很少的前提下可以提供优秀的随机数序列输出，虽然其寄存器状态输出有重复周期，但其理论周期长度与移位级数成指数函数关系，足够支撑应用需求。

2 PUF设计

本节通过使用较为成熟稳定的弱 PUF来构建具有良好可用性的强PUF设计方法。存储器PUF是最具代表性的弱 PUF。然而，由于仿真验证在FPGA平台上进行，而主流的FPGA开发平台都会在启动时初始化片上存储器，从而导致存储器PUF很难在FPGA上实现。因此，本设计选取并改进了一种基于FPGA结构的弱PUF作为强PUF前端。

2.1 总体结构

图3为基于LFSR的强PUF(L-PUF)结构。前端弱PUF的输出响应为LFSR提供设备唯一的反馈函数，使得每个设备的LFSR结构均有差别。通过为不同的LFSR提供同样的种子作为激励，在运行固定周期数后，产生设备唯一的响应。

图3 基于LFSR的强PUF结构

2.2 FPGA上弱PUF的设计

近年来，通过对FPGA底层结构的研究，一些专用于FPGA芯片的PUF设计被提出来。其中，ANDERSON[14]称第一次在FPGA上实现了PUF结构。该设计参考了延时类 PUF的基本思想，利用Xilinx系列 FPGA芯片中可配置为移位寄存器的LUT和进位逻辑中的级联二选一开关，搭建出互相竞争的2条通路，并使用SLICE内部的一个触发器进行输出值的仲裁，从而实现一位响应输出。面积开销极小，最少2个SLICE就能实现1位响应。

图4描述了Xilinx最新的7系列28 nm FPGA芯片的底层架构。其基本组成逻辑单元称为CLB(configurable logic block)，在芯片上以二维阵列排布，可以通过可编程的互连矩阵相连。一个CLB包含2个SLICE，每个SLICE主要包含4个6输入LUT，一个进位器链(CARRY4)和8个触发器。SLICE有2种类型：SLICEM中的LUT可以根据需要配置为移位寄存器(shift register LUT，SRL)或通用逻辑，而SLICEL中的LUT只能配置为通用逻辑。2种SLICE通常按列交叉排布。

图4 Xilinx 7系列FPGA底层结构

Anderson的设计中，一位PUF响应电路如图5所示。其核心SLICEM中的2个LUT配置为SRL工作模式。寄存器内容预先初始化为：

LUT A：0101010101010101(0x5555)

LUT B：1010101010101010(0xAAAA)

图5 Anderson设计中的1位响应

2个SRL由同一个时钟控制，因此，LUT A的输入到N2通路的延时，理论上应该等于LUT B的输入到N1通路的延时。但工艺偏差会导致2个延时不同。假设LUT B通路快，则第2个周期上升沿时，N1值先变0，而N2持续为0；假设LUT A通路快，则第2个周期上升沿时，N1变0之前N2已经等于N1，N2的值在变0之前将会出现一个尖峰。将N2连接到一个异步Preset触发器的PRE端，并将该触发器初始化为0，输出Q反馈到输入D。如果N2产生尖峰，该触发器状态将会被置1，否则，其值保持为0。是否产生尖峰可以作为1位响应输出。

但是，该设计是在 Xilinx上一代 FPGA芯片Virtex-5上实现的。而Xilinx的新一代FPGA芯片7系列(包括Virtex-7、Kintex-7、Artix-7等)与 5系列和以前的产品有所不同。对于7系列芯片，MUX A和MUX B的逻辑0输入端口在LUT A和LUT B被配置为 SRL时无法一直保持低电平，导致该设计无法实现。为了解决该问题，本文对原设计进行了改进。一个通路由一个 SLICEM中配置为 SRL的LUT，与相邻SLICEL中对应位置的二选一开关连接组成。SLICEL中的任意一个触发器作为响应输出。同时，调整A、B 2条通路的相对距离，以提高PUF的性能(2通路距离过近会导致尖峰过窄而被误过滤掉)。实验结果表明，A和B之间相隔5或6个LUT时，结果最好。因此，最终前端1位弱PUF的设计如图6所示，4个相邻的SLICE可以提供1位响应。

图6 Xilinx 7系列FPGA上1位响应实现

对于LFSR来说，在寄存器链的初始值种子相同的情况下，抽头数和位置的不同，会生成不同的移位输出序列，这是本设计的基本思想。通过与弱PUF输出响应中对应位进行逻辑AND实现抽头位置的选择。其结构如图7所示。

对于输出响应为m位的前端弱PUF来说，其第n位输出响应为 puf[n]，其中 0＜n≤m。若一个L-PUF实例的puf[n]=0，则该位对应的LFSR中的异或逻辑不工作，即该位没有抽头。反之，若puf[n]=1，则该位有抽头(图7中虚线框1中部分功能)。如果弱PUF的唯一性足够理想，使用不同的种子作为激励，就可以保证整个 L-PUF具有不可克隆性和唯一性。

2.3 其他功能

然而，需要考虑2个问题：①LFSR在任何状态下的值均不能全为0，否则LFSR将无法跳转到其他状态；②对于该设计中使用的LFSR结构，当反馈输出为0时，系统会变为普通移位器。因此种子序列的前导0会导致所有L-PUF的输出都一样，从而失去PUF功能。对问题1，可以通过图7中虚线框2和3中的附加逻辑实时检测LFSR的状态，若发现全0状态，则改变反馈值，跳出全0状态。对问题2，有2种解决方法：①加入前导0检测和计数控制逻辑，若给L-PUF加载的激励前导0有n位，则控制L-PUF在n个时钟周期后再输出响应；②仅加入计数控制逻辑，对于一个m位的L-PUF，控制其在m-1个时钟周期之后输出即可确保功能正确。对于大多数IoT设备而言，硬件开销的优先级高于延时开销，第2种方法是更好的选择。

图7 8位L-PUF电路实现

3 实验和结果分析

3.1 FPGA实现

L-PUF的设计和实现在一块 Alinx开发板(核心为Zynq-7000 XC7Z020 SoC芯片，该芯片包含一个双核ARM处理器和一个Virtex-7 FPGA)上进行。Xilinx公司提供了完整而强大的物理约束方法，可以对用VHDL或Verilog完成的设计进行多层次的物理位置约束。通过使用宏和设置标签的方式，可以将该 PUF按照上述结构进行精确定位。并将Zynq-7000芯片上的FPGA部分分成16个区域，使用Vivado 2017.1开发环境中的RLOC_RANGE属性进行约束，在每个区域上分别实现一个64位L-PUF实例。然后，将每个PUF封装为IP核，挂载到Zynq-7000芯片内部的AXI总线上，通过芯片上ARM端的UART接口进行激励的写入和响应的读取。实验数据的记录和处理在 PC机上通过python语言实现。

3.2 硬件开销

一个64位L-PUF设计一共使用了Zynq-7000 XC7Z020 FPGA上53 200个纯逻辑LUT中的210个(0.4%)，17 400个可作存储器的 LUT中的 128个(0.8%)，13 300个SLICE中的316个(2.4%)。实验结果显示，本文中的强PUF设计硬件开销很小，足够轻量级(表1)。

表1 硬件使用情况(个)

3.3 性能分析

3.3.1 随机性

随机性表征了PUF响应中0和1的分布情况。随机性的理想值是50%，意味着 PUF响应中的0和1出现的概率应该完全相同。对前端弱PUF和整个L-PUF输出响应的随机性分别进行统计。在2个通路相对距离为5个LUT时生成的1 024位PUF响应中，1的位数为396，随机性为38.7%。相对于其他相对距离的结果，最接近于理想值。而且，由于该设计对弱 PUF均匀度要求不高，该值已经可以确保为LFSR提供有效的反馈函数。

对16个L-PUF实例分别施加同样的4组64位激励，每个L-PUF记载前100个时钟周期的输出。根据设计，取第63个时钟周期之后所有的输出响应，共得到 4×64×16×38=155648位输出响应，其中1的位数为77 488，整个L-PUF输出响应的随机性为49.8%。

3.3.2 唯一性

PUF的唯一性是指在不同的设备上实现该PUF不同实例时，对于同样的激励，不同实例输出响应的差异程度。唯一性可以通过响应的片间汉明距离(hamming distance，HD)进行评估，即

其中，Ri和Rj为2个芯片i和j对同一个激励C生成的n位响应。

理想情况下，PUF电路的不同实例平均片间HD应该是50%。即不同实例对同一组激励生成的响应中应该有半数位的值不同。

分别测试了16个L-PUF实例对4组激励的响应，每个实例记录前100个时钟周期的输出结果，每个周期的16组响应共有480个HD值。对第63个时钟周期输出的响应进行统计，片间HD的最大值为43，最小值为22，平均值为32.16，接近于理想值为32。即该强PUF的唯一性为50.25%，HD的概率直方图如图8所示。

图8 L-PUF的片间汉明距离分布

3.3.3 可靠性

理想的 PUF设计，在任何工作环境中，其输出响应都应该是完全可再生的，即任何时候任一个实例对同一个激励生成的响应都应该完全一致。通常用可靠性表示 PUF响应的可再生性能。对于一个 PUF实例，可靠性可以用计算其平均片内 HD评估，即

对一个n位PUF实例施加s个激励，每个激励在不同工作条件下测t组。其中，Ri是正常工作条件下的响应，R′i是不同供电电压或温度下的响应，R′i,t是第t组响应，可靠性等于100%-HDintra。片内HD越小越好，理想值为0。

对于L-PUF利用弱PUF加上混淆逻辑构造强PUF的设计来说，其可靠性主要取决于前端弱PUF的可靠性。Anderson在Xilinx Virtex-5上测试了前端弱 PUF的可靠性，实验结果表明，在不同供电电压和温度下平均错误位数为 2.38，即可靠性为96.3%。

3.3.4 可重配置性

进一步统计了L-PUF从第63个时钟周期到第100个时钟周期的HDinter平均分布。平均HD随周期增加略有波动，最小为31.32，最大为32.78，平均值为 31.97。均方差和标准差分别为 31.97和0.148。实验结果表明，该64位L-PUF的唯一性随时间变化非常稳定，且接近理想值。

由于 L-PUF在每个时钟周期的输出均是不同的，只要统一在不同的时钟周期后输出响应，一个PUF实例可以等效为多个可用的PUF。该特性适用于多个 PUF来提升系统安全性的应用场景，且可以进一步提升 PUF的安全性，因为对于攻击者来说，克隆所有周期的CRP空间并不现实。

3.3.5 与其他工作的比较

表2列出了L-PUF与几种经典强PUF设计的比较。与先前的强PUF设计相比，L-PUF设计在FPGA上实现了更好的硬件开销，并且几乎具有相同的唯一性。特别地，利用可变输出周期，2个PUF都可以提供多种配置选项，这可以指数地增加使CRP数量呈指数增加。

表2 L-PUF与其他强PUF设计的比较

4 结 束 语

本文改进了一种利用 FPGA逻辑单元结构以及布局布线方法的PUF，并与经典的LFSR架构结合提出了一种新型的、可动态重配置的强 PUF。L-PUF结构简单，可以用ASIC和FPGA实现，与传统的仲裁器 PUF相比性能具有较大提升。并且面积开销很小，非常适用于对硬件开销敏感的物联网设备。该设计在28 nm的FPGA上进行了实现。实验结果表明，L-PUF的随机性、唯一性和可靠性均较好。下一步，将使用更多的FPGA设备建立更大规模的测试集，提升系统的可靠性。同时，还要分析评估该设计的抗机器学习攻击能力。