广告

验证小规模(IoT)硬件随机数生成器的挑战

开放获取
  • 5.4 k下载

摘要

本章主要介绍随机数生成器(RNG)的测试和认证。需要统计检验来确定RNG产生的序列是否具有非随机特征。这些可以包括输出中的结构、序列的重复和任何其他形式的可预测性。计算机安全系统的认证利用这种评估来确定给定的RNG实现是否有助于安全、健壮的安全系统。最近,小型硬件rng已被用于物联网设备,特别是那些需要安全的设备。然而,这带来了新的技术挑战;用于机载rng后处理和评估的低计算资源只是两个例子。我们能依靠目前的一套统计测试吗?在评估RNG时还会遇到哪些其他挑战?

10.1简介

随机生成的值在各种应用中都很受欢迎,在这些应用中它们通常是至关重要的。密码系统需要随机值来确保生成的密钥是不可预测的,因此对这些密钥进行暴力攻击是不可行的。即使在娱乐行业,也存在随机性需求:彩票和游戏都依赖于随机数生成来保证游戏的公平性。

然而,随机数的生成不是简单的任务。确定性随机数生成器(Deterministic Random Number generator, DRNG),也被称为伪随机数生成器(Pseudo-Random Number generator, PRNG),不能产生真正的随机输出[514].PRNG实现适当程度的随机性通过使用初始种子值来填充一个明显随机输出的按比例长得多的序列。这种形式的随机数生成只有在种子值未知的情况下才不可预测。为此,大多数PRNG算法定期从自然熵源重新播种。prng的主要好处是它们通常非常快,特别是与用于种子的自然熵源相比。这使得它们在计算机系统和需要大容量RNG的应用程序中具有很高的吸引力。

熵的物理来源可以提供所谓的真正的随机性.真实随机数生成器(TRNG)使用大量不同的熵源作为其关键组件,但具有几个共同的特征。它们不需要播种来产生随机性,而是使用自然现象作为熵源。trng可以进一步分类为经典或量子随机数生成器(qrng)。为了简化问题,TRNG将参考经典方法,QRNG将从这一点参考量子方法。TRNG利用微观现象产生统计随机噪声信号。光电效应和热噪声是经典熵源的两个例子。QRNG的原理与此类似,但它利用了量子现象。这些包括光子计数,使用分束器,或在MOS/CMOS器件中观察量子射击噪声。

所有随机数发生器都可以使用统计测试电池进行评估。Dieharder、联邦信息处理标准(FIPS) 140-1/2和美国国家标准与技术研究所(NIST) SP800-22 [448]代表用于随机数发生器专业测试的三种最常见的测试电池。制造商经常使用这种测试来证明其产品的正确功能,但第三方也会使用这种测试来独立验证设备的随机性。NIST及通用准则[407]提供了独立开发的指导方针和测试,以确定RNG是否是非随机的。这些测试通过识别RNG输出中是否存在任何可观察到的偏差、结构或可预测性来评估RNG。识别随机性是不可能的,但非随机性可以被检测到。认证方案利用这些测试来公开承认计算安全系统的健壮性。在RNG验证领域,已经设计了具体的方法来指导和确保这些评估的质量。

在统计测试中放置显著信任,以确定RNG是否提供足够随机的输出。本章的目的是证明随机性统计检验的挑战远未解决。我们评估了一些当代TRNG,以突出数据收集、测试相关性和过度使用旧测试电池而排除新测试方面的问题。随着微小的集成TRNG通过在物联网(IoT)产品中的使用而变得更加丰富,这些考虑因素变得更加重要。

以下各节将按顺序讨论:RNG的认证和适用的标准/测试程序,从RNG收集数据期间面临的挑战,以及两组实验结果,说明在为RNG评估适当选择统计检验方面存在的问题。

10.2认证、标准和测试

许多公司雇佣自己的测试团队,由他们负责执行公司规定的质量控制。ID Quantique (IDQ)和NXP就是两个例子,他们都对自己的产品进行不同程度的测试。对于实现密码学的产品,RNG测试对于验证所讨论的密码系统至关重要。但是,内部测试对于认证是不够的,除了自我认证(由IDQ执行)。测试必须由第三方进行,以确保公正性。

NIST是标准和测试机构的一个例子。这家美国机构致力于测量科学、标准和技术的发展。该机构本身不进行测试或奖励证书,但负责发布和公正地开发随机测试的统计测试套件。特别出版物(SP)的创建是为了传播RNG测试和RNG正式验证领域中公认的发展。特别值得注意的是SP800-90B [449]及SP800-22 [448].SP800-90B详细介绍了PRNG和TRNG的熵源和最终输出的具体测试。SP800-22详细介绍了适用于PRNG和TRNG(包括与TRNG关联的QRNG)的广泛测试电池。

通用标准(CC)是一个国际标准(ISO/IEC 15408)。与前面讨论的NIST SP文件不同,CC是用于验证计算机安全系统的广泛框架[407].功能、构造和保证需求是CC的核心原则。需要强调的是,这是一个完整的系统安全性验证:RNG测试只是更大的验证过程的一部分。然而,可以认为RNG验证是计算机安全系统认证的关键。如果RNG不能提供适当的输出,那么安全系统就不太可能健壮到CC所要求的程度。

为了区分不同的应用程序及其安全需求,中心制定了评估保证级别(EAL)计划。这些编号等级,从1到7,反映了日益增长的安全需求。在1级,测试是粗略的,制造商提供的报告是可以接受的。由于寻求更高的认证,需要更多的第三方和设计阶段的第三方测试。在5级以上,对制造工厂进行抽查,并实施关键安全系统。NXP生产两种CC EAL认证设备:DESFire EV1 (EAL4+)和DESFire EV2 (EAL5+)。

评估委员会在测试rng时所采用的测试方法载于AIS-31 [327].AIS-31概述了计算机安全系统中熵源的测试方法[327].AIS-20被称为TRNG评估推荐测试和参数的信息来源。这两个文档都关注TRNG,因为它们的目的是评估熵源的正式验证,而不是它们可能播种的PRNG算法。因此,硬件rng是这些文档的重点。

表格10.1显示了rng及其相关认证的选择。CC EAL、METAS、CTL、FIPS 140-2均为各自机构认证。NIST SP800-22表明在测试RNG时应用了NIST方法和测试电池(无论是内部还是外部)。任何RNG测试过程都需要一组统计测试。关于随机性的统计测试的最早例子之一便是Marsaglia的Diehard电池[393].NIST SP800-22提供了Rukhin等人开发的一系列更广泛的测试。[508].NIST电池包含15项测试,根据均匀性和比例进行评估p-values为每个测试。有人对这些结果的准确性提出了一些批评。Marton和Suciu观察到假警报很常见,SP800-22所表明的更多测试可能会被其他健壮的rng失败[396].NIST本身声明,任何失败都是进一步调查的原因,但没有建议任何具体的RNG测试后续程序。这意味着进一步的数据收集和测试更多的目标设备是解决这个问题的初步方法。
表10.1

所选可再生气体的测试所采用的标准

成本

制造商

设备

熵源

认证/测试

NXP

DESFire EV1

0.59

不披露

CC EAL4 +

NXP

DESFire EV2

1.25

不披露

CC EAL5 +

容器

Quantis 16米

2900

分束器

Nist sp800-22, metas, CTL

容器

Quantis 4米

1299

分束器

Nist sp800-22, metas, CTL

容器

数量USB 4M

990

分束器

Nist sp800-22, metas, CTL

Comscire

PQ32MU

1211

散粒噪声

NIST sp800 - 90 b / C

NIST SP800-22

顽固的

阿尔特斯Metrum

ChaosKey

45

RBSJ一个

FIPS 140 - 2

一个反向偏压半导体结

Dieharder是Diehard的扩展,集成了SP800-22测试和原来的Diehard测试[116].这使得该电池总共进行了30次测试,总共进行了76次变型测试。这种电池比以前的电池需要更大的测试数据。为了在套件中的每个测试中都不倒带地测试数据流,必须收集228 GB的数据。这远远超出了NIST和CC建议的推荐参数。在相同的测试条件下,一个4gb的样本可以倒带57次。如果在给定测试的一次执行过程中有一系列重复,则可能会引入1型错误。测试可能会报告这种重复违反了随机性的定义,并将序列识别为非随机的,而实际上它只是不够大。这就强调了适当收集数据的重要性。

由L 'Ecuyer和Simard开发的TestU01更像是RNG开发人员的工具箱,而不是测试电池[362].然而,它包含5个不同的测试电池:Alphabits, Rabbit, Small Crush, Crush和Big Crush。每个电池都有不同数量的测试。Alphabits和Rabbit在比特上操作,而Crush电池在0到1之间的浮点数上操作。Alphabits, Rabbit和Small Crush在2 GB大小的样本上在几分钟内完成。《Big Crush》需要大量数据(或来自目标设备的持续输入流),并且需要数小时才能完成。McCullough等人确定了这个工具集的一些潜在问题。一些测试只能读取32位,并且对最高有效位的错误比最低有效位的错误更敏感[403].为了解决这个问题,他们建议对序列进行前后测试。这里的问题是不能以这种方式对实时数据进行测试。这限制了许多测试,并阻止它们用作实时测试。

还有另一类测试;连续测试。这些测试旨在确定是否存在导致熵流损坏或停止的硬件故障。FIPS 140-1/2在设计时就考虑到了硬件[121].这两种测试套件都可以在RNG的电路中实现,提供一系列关于设备健康和功能的恒定结果。任何连续测试的核心要求是任何RNG都不应该输出两个相同的RNGN位块连续。如果不满足这一条件,设备应立即停止功能,并提醒用户它没有按预期工作。然而,这并不能检测到更细微的缺陷。精明的读者可能还推断出,不需要两个N位块相同实际上会降低熵。考虑到理想RNG的定义是完全不可预测的,这对此类测试的合法性产生了影响。这些测试很可能与物联网TRNG实现一起实现,因为它们在硬件上的有效实现,将之前的担忧带到数百万潜在设备上。

NIST, Dieharder, TestU01和其他统计测试电池的使用情况可能因机构而异。NIST SP800-22概述了最小样本量,如果提供的数据不足,Dieharder通过倒卷样本来暗示这些样本量。然而,在自我认证过程中,一些公司被发现测试小样本,低于建议的指导方针。这可能会使人们对他们发现的有效性产生怀疑。

10.3数据收集的挑战

对于独立的RNG,数据收集可能很简单。然而,目前还没有针对独立RNG的官方认证。FIPS和CC都认证整个安全系统,而不是单个的元素,所以即使RNG测试是这个过程的关键,一个独立的RNG通过这些测试仍然不能被认证。无论如何,RNG测试作为整个系统认证的一部分是一个关键的考虑因素。从某些集成的rng收集数据可能并不简单。由于物联网设备代表了整个系统的安全实现,它们可能需要认证;RNG评估是任何此类评估过程的关键部分。

黑盒设计通常被使用授权技术的公司使用,或者需要保护自己的知识产权(IP)的公司使用。这意味着它们的安全实现(包括RNG)的原理图可能无法被公开访问。对于较低的EAL奖励,这种技术细节的混淆可能扩展到检查员和CC官员。在更高层次上,要求保密协议作为请愿公司和评估机构之间认证合同的一部分。这样的安排代价高昂。检查人员和独立测试人员的时间必须得到补偿,费用落在要求在给定EAL进行评估的公司身上。因此,自我证明很常见。

RNG的读取速度取决于很多因素。在RNG完全集成的情况下,可能会有额外的开销,例如后期处理,使用PRNG清洁TRNG输出被用作熵源,或者只是对输出大小和速度的硬限制。一个尖锐的例子是DESFire EV1和EV2。这些RFID卡不直接将其内部TRNG暴露给用户,而是要求用户使用身份验证协议提取随机数。该协议要求卡和读卡器交换随机值作为验证握手的一部分[289].卡传输的16字节值可收集并存储在文件中,以便使用随机统计测试进行分析[288].这是一个耗时的过程,如Table10.2所示。为了从DESFire卡中收集64mb的数据,大约需要12天。这个过程中的主要瓶颈是需要在第二次握手开始收集额外的16字节序列之前完成身份验证协议。试图通过关闭读卡器来终止协议,从而重置卡,被证明是更加耗时的[288].物联网设备也存在这个问题,其中许多设备都实现了集成的trng。
表10.2

所选设备的RNG输出速度

样本量(MB)

平均数据速率(比特/秒)

DESFire EV1

64

4.93⋅102

DESFire EV2

64

4.90⋅102

Quantis 16米

2100

1.27⋅108

Quantis 4米

2100

3.08⋅107

数量USB 4M

2100

3.11⋅107

Comscire PQ32MU

2100

2.48⋅108

ChaosKey

2100

3.07⋅107

物联网设备可以通过多种方式实现PRNG和TRNG。FRDM K64F板实现了TRNG,但输出仅限于内部调用,或通过I/O引脚以无符号整数的形式输出值。虽然比EV1和EV2快得多,但仍然比大多数独立的trng慢得多。Red Bear Duo没有实现局部熵源。板载PRNG必须提供设备外熵,不进行设备上的检查或连续测试。在全系统实现中,这样的设备很难识别其RNG中的缺陷发生在哪里。

独立的生成器(Quantis, Comscire和ChaosKey表项)10.2)的速度要快得多,相比之下,数据收集就微不足道了。然而,这并不意味着测试了适当大小的样本。

SP800-90B规定熵源必须为测试提供1,000,000位连续输出[449].如果不可能连续输出到该大小,那么较小序列的连接是可以容忍的,但这是不可取的。根据NIST指南,必须将1000个这样的序列连接起来。SP800-22扩展了这些要求,建议对上述尺寸的100个样品进行测试以验证结果[508].AIS-31和AIS-20没有规定最小样本量。John Walker指出,在他们的默认配置中,死硬测试应该运行至少100mb的数据[568].

考虑到这一点,可以更彻底地分析几家TRNG制造商的测试报告。IDQ表示,他们的Quantis设备通过了Diehard和NISTSP800-22电池,没有任何故障。1SP800-22测试进行了超过1000个样本,长度为1,000,000位。在整个过程中保持1%的显著性水平。Diehard的使用比例为1⋅109位。我们自己的测试证实,IDQ的报告没有错误,即使对于较大的样本(我们的样本大小为2.1 GB)也是如此。在这种情况下,IDQ是测试协议的一个很好的例子,它符合测试开发人员的建议。

Comscire的PQ32MU,一个使用射击噪声作为熵源的QRNG,是一个不同的故事。他们的NIST-Diehard报告2显示测试数量已减少。样本量减少是一个问题,但减少测试数量可能会导致某些功能的丧失。除非删除的测试完全是多余的,否则很可能会影响电池检测某些类型的非随机性的能力。不包括这些试验的理由是样本量不足。Comscire仅使用2个样本测试该QRNG;8乘107位,再乘以1⋅106位。这远远低于铁杆粉丝的建议样本量。尽管这些样品在最基本的意义上满足了NIST SP800-90B的要求,但它们仍然没有达到SP800-22要求测试至少100个样品的额外建议。考虑到从这样的独立rng生成样本的容易程度,令人惊讶的是没有使用更健壮的测试过程。

10.4适当选择测试

如果评估方法涉及多个测试电池,则必须考虑电池内测试之间以及整个测试之间的相关性。统计测试能够在目标RNG中识别的问题范围有限。测试电池旨在通过提供许多统计测试来评估目标RNG的不同方面,从而提供更广泛的分析,从而缓解这一问题。

Hernandez-Castro等人确定了Ent电池测试之间的一定程度的相关性。Ent电池是大多数Linux发行版中包含的一组简单的测试,是一种简单的统计测试工具[568].Ent包括估计熵、压缩、χ 2,算术平均数,蒙特卡罗π,和序列相关性。位级和字节级测试可以在目标序列上运行。数字10.1以字节模式显示Ubuntu 16.04 Ent实用程序的输出。
图10.1

字节模式下Ent默认输出示例[272

Hernandez-Castro等人使用遗传算法退化初始随机序列,当序列慢慢变得更有序和可预测时,能够观察Ent的测试结果[272].结果表明,许多Ent测试具有一定程度的相关性。熵和压缩测试分析相同的一般属性,都对序列执行线性变换和上限操作。的χ2和多余的统计数据提供χ2考试也密切相关。本文的结论建议丢弃多余和压缩统计量。

Soto等人探究了NIST SP800-22电池测试之间的相关性程度。他们的工作发现SP800-22评估的属性范围可能不足以识别问题[538].TRNG和QRNG是特殊的问题,因为自SP800-22开发以来,已经开发了许多此类rng的示例。Soto将这种电池中测试的独立性描述为一个开放问题。

Turan等人提供了SP800-22的最新分析。他们的工作发现,频率、重叠模板(输入模板111)、1的最长运行时间、随机游走高度和最大阶复杂度检验产生了相关的统计量[560].当使用小样本或块大小时,这个问题最为明显。Georgescu等人以Turan的工作为基础,确定并检查了SP800-22测试相关性中的开放问题。发现样本量对检验之间的相关性有显著影响。图兰等人确定的相关性得到了证实,并对其与样本量的关系进行了更深入的探讨[226].这样的结果表明,RNG测试方法的每个元素都必须仔细检查,以确保有意义和公正的结果。Georgescu等人总结说,可能存在比SP800-22中实施的测试更好的测试,因为该电池现在已经相当旧了。

研究人员对SP800-22的假设和统计输出的模糊性进行了评论,指出需要更多的描述性测试输出。Zhu等人提出核反应能量,在整合到之前使用测试统计数据计算p值(601].该统计量对总变异距离和Kullback-Leiber散度更敏感。这克服了一些由非相关性引起的问题χ2SP800-22二级测试[601].

Dieharder实现了许多SP800-22测试。因此,它与SP800-22的许多批评意见相同[206].TestU01是一种较新的电池,旨在让研究人员开发和评估他们自己的rng,特别是trng。目前关于该电池的评论文献很少,因此TestU01中测试的独立性目前是一个悬而未决的问题。Turan等人评论了他们发现在TestU01的Crush电池中实施的一些相关测试[560].

测试方法的多样性与测试的独立性有关,但又独立于此。其中,独立性是衡量一组测试结果之间的相关性,多样性是衡量在RNG分析中使用了多少种评估方法。一种常见的观察是孤立地使用p-values不足以完全描述序列的随机性(或缺乏随机性)。Hurley-Smith等人的研究详细探讨了TRNG和QRNG,以确定最常用的测试电池未检测到的缺陷。在这些分析中,测试相关性和多样性是关键主题。

10.4.1数据采集约束下的随机性检验——以DESFire EV1为例

这些深入分析中的第一个是在NXP生产的RFID卡Mifare DESFire EV1上进行的[379].DESFire EV1被用作伦敦交通局(TfL)牡蛎卡计划的一部分,以及整个欧洲的其他忠诚和电子钱包计划。作为一种可以存储现金价值的设备,它需要强大的安全性来促进供应商和用户之间的信任。EV1已经获得了EAL4+认证,基于其完全的安全实现。

表格10.3显示了3 DESFire EV1卡的Dieharder结果。如前所述,从EV1收集数据具有挑战性,需要12天才能获得64 MB的数据。因此,这是能够收集到的最大数据量。总共测试了100张卡片,全部通过。本表中显示的3张卡片显示了p- Dieharder测试报告的所有测试的值,可以在64 MB的数据上执行,而不需要倒带。
表10.3

更顽固的结果[289

测试

卡1

卡2

卡3

生日间距

0.18194520

0.61105583

0.78263630

重叠排列

0.38044164

0.58693289

0.44201308

32 × 32二进制秩

0.42920693

0.23409500

0.55699838

6 × 8二进制秩

0.31311490

0.32387215

0.66137580

比特流

0.97724174

0.18743536

0.59532464

数1(流)

0.17108396

0.74984724

0.87214241

计数1(字节)

0.65870385

0.01287807

000020194

停车场

0.18078043

0.24200626

0.38128677

最小距离(2d球面)

0.76328000

0.95091635

0.34980807

三维球面(最小距离)

0.23871272

0.20826216

0.39340851

挤压

0.62598919

0.08843989

0.77057749

运行

0.99778832

0.62043244

0.90550208

0.44719093

0.91228597

0.04870531

掷骰子赌博

0.54077256

0.92769962

0.91803037

0.57614807

0.94245583

0.95209393

粗体值表示那些失败的测试,但它们远远超出了NIST建立的置信界限(或在Ent的情况下,我们对NIST SP800-22的置信界限的推断)一个= 0.01)

卡片3显示了Dieharder电池的单一故障,用于计数测试。然而,这是没有复制的任何其他卡的测试。因此,可以合理地得出结论,Dieharder电池在测试序列中没有识别出任何显著程度的非随机性。

表格10.4显示NIST测试的通过率。所有SP800-22测试都用于我们收集的EV1样本。
表10.4

NIST SP800-22结果[289

测试

卡1

卡2

卡3

频率

198/200

200/200

197/200

块的频率

196/200

199/200

194/200

累计金额

2/2

2/2

2/2

最长

196/200

198/200

198/200

排名

198/200

199/200

197/200

FFT

197/200

199/200

198/200

重叠的模板

147/148

148/148

148/148

重叠的模板

198/200

198/200

198/200

通用

198/200

198/200

198/200

近似熵

197/200

198/200

196/200

随机的远足

8/8

8/8

8/8

随机远足变量

18/18

18/18

18/18

串行

2/2

2/2

2/2

线性复杂度

199/200

197/200

199/200

粗体值表示那些失败的测试,但它们远远超出了NIST建立的置信界限(或在Ent的情况下,我们对NIST SP800-22的置信界限的推断)一个= 0.01)

卡片1和卡片3都显示了一些边缘结果,特别是在运行和非重叠模板测试中。然而,大多数卡片(100张中的98张)都通过了这个电池。这是一个值得关注的原因:正如SP800-90B所述,任何失败都是进一步调查的原因。因此,我们认为有必要进行进一步的分析,并将简陋的ENT电池作为EV1 TRNG评估更通用方法的起点。

考虑到Hernandez-Castro等人关于独立Ent检验的工作,压缩和多余的统计量应该被丢弃。然而,超过3个EV1卡的Ent电池的全部结果如表所示10.5为了完整起见。
表10.5

Mifare DESFire EV1 ENT结果64 MB TRNG输出[289

卡1

卡2

卡3

最优

7.999969

7.999989

7.999972

8

最佳的压缩。

0

0

0

0

χ2

2709.10

973.07

2470.32

256

算术。的意思是

127.492921

127.500582

127.5006

127.5

蒙特卡罗π美国东部时间。

3.14167

3.142019

3.141909

3.14159

美国相关

0.000008

0.000045

0.000093

0.0

粗体值表示那些失败的测试,但它们远远超出了NIST建立的置信界限(或在Ent的情况下,我们对NIST SP800-22的置信界限的推断)一个= 0.01)

通过了所有测试,但χ2测试。对于表中所示的3个64 mb样本10.5,χ2统计数据异常糟糕。通过比较,通过此测试的序列应该具有χ2统计数据在220到305之间。即使样本量为1 MB,也有100张DESFire EV1卡未能通过此测试。这些结果表明测试序列中的值不是均匀分布的:有偏向于某些字节值而远离其他字节值。考虑到χ2测试是这样一个微不足道(和广泛使用)的值分布在一个序列的测试,令人惊讶的是,它会突出EV1的TRNG输出的问题,而Dieharder和NIST SP800-22没有。

字节的不均匀分布并不是非随机性的自动指示器。这并不是随机性的一个很好的指标,但对于一个真正的随机性来源来说,也有可能产生一个略有偏差的序列。然而,根据AIS-20和SP800-90B的指导方针,TRNG应该提供与加密PRNG功能等效的输出。因此,不均匀的字节分布是一个问题。存在偏差的事实是一个重要的观察,但更重要的是对这种偏差的分析。

数字10.2提供了100个DESFire EV1卡的TRNG输出如何表达偏差的更深入的研究。数字10.2a为100个1mb样本的平均偏置。与预期值分布的极端偏差在图的方波中是明显的。预期的分布应该产生一个有噪声的、相对均匀分布的字节值集。偏差在10的数量级−5在高于或低于正常值的值之间几乎均匀分布的偏差。准确地说,127个值高于正常值,129个值低于正常值。
图10.2

DESFire EV1偏置分析[289].(一个) 100个1mb样本的平均偏置。(b)傅里叶平均近似。1mb的样本。(c掩模测试结果。(dχ2100个1mb样本的分数

数字10.2B细化了前一张图的观察结果。偏置的傅里叶近似表明字节值的分布有一个周期(w,−31.9918。这导致在256个可能的字节值中有8个振荡,在法线上有一个移位,每32个值(大约)观察到一次。对这些字节值中可能的位分布的统计分析表明,特定位序列的不存在会导致这种非常特殊的偏误形式。

数字10.2C提供了一个所谓的结果掩码测试.此测试的目的是用8位序列对序列的每个字节进行异或,范围为0000000通过一切干预价值来11111111.在异或操作后解析为零的所有序列的和记录了该位序列在整个样本中的出现。该图显示了以这种方式测试的100个1 mb序列的组合。很明显,这是一个明显的偏差,从正常的面具00011000.对于所有卡片,以及64 MB和1 MB样本,都观察到这种偏差。在我们向恩智浦负责任的披露之后,有人认为这种偏差可能是由不正确实现的增白函数引起的:该函数通常用于从TRNG输出中去除偏差。

数字10.2D表示分布χ2统计100个1mb EV1样本。统计数据在比例上低于64 MB样本的统计数据(表2)10.5).这是因为样本量对序列中偏差的表达有直接影响。Hurley-Smith等人进行的早期实验表明,在小于7.5 KB的样本量下,无法观测到DESFire EV1的偏置[288289].这强调了第3节中关于数据收集的观点。收集的数据量需要满足最小大小,以可靠地识别正在测试的rng中的问题。这一最低阈值是特定于测试的,要求分析师在对RNG进行评估之前确定最高最低样本量。此外,这些实验表明,即使是备受尊敬的、经过验证的统计测试电池,如Dieharder和NIST SP800-22,也无法识别DESFire EV1的问题。很明显,设计TRNG来通过这些测试是可能的,但是依赖于可以设计的测试是明智的吗?满足Dieharder和NIST SP800-22的有限和狭窄要求的设计实际上提供了随机性的任何保证吗?我们认为不是这样的。

10.4.2识别量子随机数发生器的问题

EV1实验介绍了使用完善的统计检验来识别TRNG中的非随机性的问题。目前,对于RFID卡或物联网设备的实现来说,QRNG太大了,但量子熵源的小型化正在迅速推进,物联网规模QRNG的建议已经发布。然而,目前的qrng及其评估还存在几个悬而未决的问题。

即使样本收集不是问题,也会有问题。IDQ的qrng的Quantis范围是基于光学量子熵源(分束器)。Comscire生产了一种竞争产品PQ32MU,它使用量子脉冲噪声作为熵源。这两家公司都提供多种不同速度的QRNG型号,所有型号都有与其设备相关的适当统计测试结果。如前所述,IDQ提供了一个相对可靠的测试报告,尽管它仅限于Diehard和NIST SP800-22测试。Comscire使用少量小样本,测试数量较少,极大地限制了其测试过程的严密性。作为这项工作的一部分,测试的设备都没有使用AIS-31方法进行验证,也没有获得认证(因为没有针对独立rng的官方认证)。

数据收集不是这些设备的问题,Quantis设备以4或16 Mb/s的速率提供数据,而PQ32MU的输出速度为32 Mb/s。因此,收集大量数据是微不足道的。这两个品牌的一个关键区别是Quantis发生器不实现板上后处理以消除偏差,而PQ32MU是一款一体化产品,在设备上执行后处理。

表格10.6显示了EV1、Quantis生成器和PQ32MU的结果。显示了原始和后处理的Quantis输出。EV1数据在100张卡上测试64 MB样本。Quantis和Comscire qrng从每种类型的设备中收集100个2.1 GB样本进行测试。理想情况下,更多的设备将被测试,但成本是一个限制因素(最便宜的设备,4M,售价900欧元)。
表10.6

Dieharder, NIST和TestU01结果

样品

顽固的

NIST SP800-22

Alphabits

兔子

小碎

粉碎

设备

通过了

通过了

通过了

通过了

通过了

通过了

DESFire EV1

One hundred.

One hundred.

98

0

0

- - - - - -

- - - - - -

Quantis 16米

One hundred.

One hundred.

One hundred.

54

60

93

47

文章16米

One hundred.

One hundred.

One hundred.

95

87

91

82

Quantis 4米

One hundred.

One hundred.

One hundred.

3.

7

91

3.

后4米

One hundred.

One hundred.

One hundred.

91

82

93

86

Quantis USB

One hundred.

One hundred.

One hundred.

3.

21

89

3.

USB后

One hundred.

One hundred.

One hundred.

90

81

97

80

Comscire PQ32MU

One hundred.

One hundred.

One hundred.

91

86

93

84

所有设备都通过了Dieharder测试,而除2辆EV1外,所有设备都通过了SP800-22测试。已经使用了TestU01工具包,其中4个统计测试单元用于评估所有测试设备,包括EV1。由于粉碎试验对样本量的要求,EV1数据没有进行粉碎试验。很快,EV1就出现了严重的问题,无法使用Alphabits和Rabbit电池。Alphabits的平均失败率为4次测试中的1次,Rabbit的平均失败率为16次测试中的5次。这表明,简单地添加一个新的测试电池可以立即发现更知名的电池无法识别的弱点。

原始Quantis样本,特别是4M及其USB变体,在Alphabits和Rabbit上也表现很差。它们在Crush测试中的表现也很差,但有相当数量的样本通过了Small Crush测试。这可能是因为Small Crush电池与SP800-22有许多相同的测试,导致结果之间的相关性。后期处理可以解决很多问题,但不能完全解决。最值得注意的是,Alphabits, Rabbit和Crush测试的结果显著提高,其中最剧烈的变化是在Alphabits下的4M从3次通过测试跳到91次通过。这表明,适当使用QRNG是另一个需要考虑的因素:设备的不当使用可能无法被更知名的测试电池识别出来,而不正确的配置可能与任何其他形式的非随机性一样具有破坏性。Comscire PQ32MU在大多数测试中表现良好,但在兔子和粉碎测试中挣扎。

表格10.7为QRNG的Ent结果。为了避免重复,没有显示DESFire结果。对测试的100个样本的总结表明,后处理Quantis数据和PQ32MU通过了测试χ 2和一系列相关测试都没有问题。所有设备都通过了其他测试,因此从该表中省略了它们。但是,原始Quantis数据失败χ 2测试显著。此外,4M及其USB变体在位级串行相关测试中表现相当差。这强调了跨多个块大小测试序列的必要性,以确定在低或高阶输出时可能发生的问题。与EV1不同的是,原始Quantis数据不能在样本之间提供易于识别或一致的偏差。偏差似乎在样本之间漂移,唯一不变的是表达10的趋势−6字节值0-5的偏置高于正常值。即使这也不是一个具有代表性的趋势,只有38%的样本显示出这种特殊的特征。
表10.7

ENT结果

字节

样品

χ2

序列相关系数。

χ2

序列相关系数。

设备

通过了

通过了

通过了

通过了

Quantis 16米

One hundred.

10

99

0

One hundred.

文章16米

One hundred.

One hundred.

96

One hundred.

96

Quantis 4米

One hundred.

0

99

0

49

后4米

One hundred.

One hundred.

99

One hundred.

One hundred.

Quantis USB

One hundred.

0

92

0

81

USB后

One hundred.

One hundred.

94

One hundred.

One hundred.

Comscire PQ32MU

One hundred.

One hundred.

99

One hundred.

One hundred.

数字10.3显示了χ 2统计所有16M和4M设备的原始Quantis样品。Quantis USB的结果被省略,因为USB在不同的包装中实际上是一个4M,并提供类似的结果。
图10.3

的分布χ2Quantis设备的分数。(一个16米。(b) 4米

16M (a)故障χ2对其90个样品进行测试。16M的平均统计量约为350。这超出了该测试可接受的最大阈值。4M明显更差,平均统计值为506。与16M不同的是,4M显示根本没有通过(USB报告类似的结果)。事实上,4M的最小统计值是407。这明显高于的最大阈值χ2测试。

在这些qrng上进行的实验表明,现有的测试并不总是能识别出最近(或不太知名)测试强调的问题。TestU01电池通过提供更广泛、更复杂的测试来加强Ent测试的结果,这些测试证明,在字节和位级别上,除了简单地偏离值的正态分布之外,还存在其他问题。由于TestU01旨在提供测试TRNG的工具,因此理想情况下,该电池将成为TRNG和QRNG测试的强制性建议。Dieharder和NIST SP800-22将继续使用,因为它们可以有效地识别RNG输出的严重问题,但目前非常需要延长最小推荐测试次数。应对后处理和原始数据进行测试,并清楚地标记结果,向用户展示如何识别和解决软件后处理配置不当的问题。人们还应该考虑,如果物联网qrng备受追捧,如何在如此小的包中实现后处理算法(以其高内存要求而闻名)?资源限制可能会阻碍对QRNG输出进行有效的后处理,其后果在前面的工作中已经说明。

10.5结论

在评估rng在安全系统中的使用时,有许多复杂的问题需要考虑。设备规格、设备外熵池的使用、后处理和输出速度都对评估过程至关重要。每个元素都应该单独测试,但只有整个设备可以通过认证,这导致在考虑黑盒设计理念和资源受限设备时出现问题。

DESFire EV1被发现从其TRNG输出有偏差的值,但这并不一定意味着RNG本身有问题。对EV2的后续工作没有发现其RNG有任何问题。结合与恩智浦工程师的对话,这表明问题可能在于用于消除原始TRNG输出偏差的美白功能。EV1的结果突出了两个关键问题;黑箱设计在复杂评估过程中的作用,以及小规模鲁棒trng面临的质量控制挑战。数量qrng还需要后处理,这从原始数据在各种统计测试中显示的异常差的结果中可以看出。对具有多个输入和处理依赖关系的RNG进行严格的测试,应该要求结果能够证明此类设备的原始输出和处理输出的性能。这将有助于识别实现错误。

对Dieharder和NIST SP800-22的依赖不能继续排除新的测试,例如TestU01所采用的测试。关于随机性的统计检验这一主题有大量的学术文献,必须努力确定哪些文献将提供下一波可靠的随机性检验。最后,重要的是要考虑如何通过操纵RNG输出来逃避测试;未来的工作将集中在一些简单的操作如何产生可预测的数据,这些数据通过了当前的随机性统计测试。

脚注

参考文献

  1. 116.
    Robert G Brown, Dirk Eddelbuettel和David Bauer。Dieharder:随机数测试套件。开源软件库,正在开发中, 2013年。谷歌学者
  2. 121.
    汤姆盒。Fips 140 - 2。在密码学和安全百科全书, 468-471页。beplay登入施普林格,2011年。谷歌学者
  3. 206.
    范利民,陈华,高思。评价随机性检验相关性的一般方法。在“信息安全应用国际研讨会”, 52-62页。beplay登入施普林格,2013年。谷歌学者
  4. 226.
    Carmina Georgescu, Emil Simion, Alina-Petrescu Nita和Antonela Toma。nist随机检验的相关性研究。在电子、计算机与人工智能(ECAI), 2017年第九届国际会议, 1-4页。IEEE 2017。谷歌学者
  5. 272.
    胡里奥·埃尔南德斯-卡斯特罗和大卫·F·巴雷罗。进化生成和退化的随机性来评估ent测试电池的独立性。在进化计算(CEC), 2017年IEEE大会, 1420-1427页。IEEE 2017。谷歌学者
  6. 288.
    Darren Hurley-Smith和Julio Hernandez-Castro。偏见在mifare desfire ev1 trng。在射频识别:第12届国际研讨会,RFIDsec 2016,中国香港,2016年11月30日至12月2日.beplay登入施普林格国际出版,2016。谷歌学者
  7. 289.
    Darren Hurley-Smith和Julio Hernandez-Castro。可证明的偏见:对通用标准eal4+认证trng的深入分析。IEEE信息取证与安全汇刊地球物理学报,13(4):1031-1041,2018。CrossRef谷歌学者
  8. 327.
    沃尔夫冈·基尔曼和维尔纳·辛德勒。Ais 31:真实(物理)随机数生成器的功能类和评估方法,3.1版。德国信息技术研究所,波恩, 2001年。谷歌学者
  9. 362.
    Pierre L 'Ecuyer和Richard Simard。Testu01: Ac库的经验测试随机数发生器。美国计算机学会数学软件汇刊地球科学进展,33(4):22,2007。谷歌学者
  10. 379.
    恩智浦半导体有限公司MF1PLUSx0y1 Public Datasheet.NXP半导体。谷歌学者
  11. 393.
    乔治马。一组随机数生成器的测试。光盘,美国佛罗里达州立大学统计与超级计算机研究所, 1995年。谷歌学者
  12. 396.
    金佳·马顿和阿林·苏丘。关于nist统计测试集结果的解释。科技岩石力学与工程,18(1):18 - 32,2015。谷歌学者
  13. 403.
    BD麦卡洛。testu01的回顾。应用计量经济学杂志地球物理学报,21(5):677-682,2006。CrossRef谷歌学者
  14. 407.
    丹尼尔·梅拉多,爱德华多Fernández-Medina和马里奥·皮亚蒂尼。安全信息系统开发的基于安全需求工程过程的通用标准。计算机标准与接口地球科学进展,29(2):244-253,2007。CrossRef谷歌学者
  15. 448.
    国家标准和技术研究所。NIST SP800-22修订1a -用于加密应用的随机和伪随机数生成器的统计测试套件.检索:https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf16:53 21/05/2018。
  16. 449.
    国家标准和技术研究所。NIST sp800 - 90b -用于随机位生成的熵源的推荐.检索:https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf十七33 21/05/2018。
  17. 508.
    安德鲁·鲁辛,胡安·索托,詹姆斯·纳赫瓦塔尔。用于加密应用的随机和伪随机数生成器的统计测试套件。Nist dtic文件。NIST SP800-22, 2010年。谷歌学者
  18. 514.
    沃纳·辛德勒和沃尔夫冈·基尔曼。用于密码学应用的真(物理)随机数生成器的评估标准。在密码硬件和嵌入式系统国际研讨会, 431-449页。beplay登入施普林格,2002年。谷歌学者
  19. 538.
    胡安索托。随机数发生器的统计检验。在第22届全国信息系统安全会议论文集第10卷,第12页。NIST, 1999年。谷歌学者
  20. 560.
    Meltem Sönmez Turan, Ali DoĞanaksoy, Serdar bozta。论统计随机性检验的独立性和敏感性。在序列及其应用国际会议, 18-29页。beplay登入施普林格,2008年。谷歌学者
  21. 568.
    约翰·沃克。Ent,一个伪随机数序列测试程序。Fourmilab, 2008年。谷歌学者
  22. 601.
    朱双义,马元,林景强,庄佳,景继武。nist sp 800-22更强大可靠的二级统计随机性检验。在密码学与信息安全理论与应用国际会议,第307-329页。beplay登入施普林格,2016年。谷歌学者

版权信息

©作者2021

开放获取本章根据创作共用属性4.0国际许可协议(http://creativecommons.org/licenses/by/4.0/),允许以任何媒介或格式使用、分享、改编、分发和复制,只要您适当注明原作者和来源,提供创作共用许可的链接,并注明是否有更改。

本章中的图像或其他第三方材料包含在本章的创作共用许可中,除非在材料的信用额度中另有说明。如果材料未包含在章节的创作共用许可协议中,并且您的预期使用不被法定法规所允许或超出了允许的使用范围,您将需要直接获得版权所有者的许可。

作者及隶属关系

  1. 1.肯特大学坎特伯雷英国

个性化推荐