Har*_*mes 13 random microcontroller avr arduino entropy
我听说人们使用光传感器,盖革计数器和其他物理传感器来生成随机数,但我持怀疑态度.有没有办法通过测量物理世界(使用Arduino或任何其他微控制器)生成随机数？如果是这样,这些数字是否真的是随机的？
澄清:问题是关于使用微控制器收集的数据生成随机数的可行性,这些随机数可以合理地应用于密码学 - 是依赖设备熵的替代方案.
Jim*_*myB 22
采用模拟"真实世界"测量通常是熵的良好来源(也称为真实随机数据).模拟源总是有一些不可预测的叠加噪声,可以"收获".但是,如前所述,测量数据很少没有偏差.
模拟电测量还可以或多或少地受到不可控制的影响或甚至来自外部的攻击,例如通过引起传感器的饱和.EMI也可能干扰测量; 在通话过程中放置在距离电路较近的普通手机上,很可能会对任何模拟信号造成严重破坏.
无偏,均匀分布的高熵数通常是人们想要的,因为它们的属性(非值)在某种程度上是标准化的,因此可以更可靠地预测.
当测量模拟输入,例如10位分辨率时,理想情况下,从测量中收集的数字范围将覆盖0到1024之间的所有值,并且每个值将以与该范围内任何其他值相同的频率(或概率)发生.
实际上,这些值通常(或多或少)正常分布(高斯分布)围绕某些平均值具有一些特征标准偏差,例如每个样本约500个@ 10位.
因此,为了生成具有所需属性的随机值(见上文),需要进行一些去偏置:需要某种随机性提取器.
使用加密函数,如(单向)散列函数或密码算法,通常也很容易产生所需的结果; 这需要付出代价:这些功能的"混合"设计极其强大,这使得无法确定转换后源数据的质量(=随机性).即使是最简单的确定性值序列,如{1,2,3,4,5 ...},当散列产生的数据很可能会很好地通过任何和所有统计随机性测试,尽管它不是"随机"的所有.
在微控制器环境中,很少考虑的一个很好的熵源是事件的时间.使用高速定时器,可以通过响应某些异步事件读取定时器值来收集真熵.这种与运行计时器不相关的事件可以是用户按下按钮,由另一(子)系统或IC发起的通信的开始,或者基本上不由μC触发的任何其他事件(或任何同步子系统)本身.
实际上,熵甚至可以从两个独立的时钟源中获取; 例如,通过另一个时钟的一个时钟的定时周期.这开启了Atmel AVRμC(在Arduino中使用)的几个非常有趣的可能性,具体取决于μC的功能:
大多数AVR都有内部EEPROM存储器.对该存储器的写操作由专用定时器定时,该定时器独立于主系统时钟( - 据报道有一些芯片(不是类型!),其中测量表明可能不是这种情况)(编辑:注意在某些AVR中)例如,ATTiny25/45/85,EEPROM时序源自内部RC振荡器,因此当该振荡器也被选为系统时钟源时,不能收集熵 ; 这可能取决于主时钟源(内部R/C与外部晶体/谐振器).因此,相对于主系统时钟,在写入EEPROM所需的时间内存在一些(真正随机的)抖动,这也可以通过高速定时器/计数器来测量.
较新的AVR能够让看门狗定时器产生软件中断而不是硬件复位.看门狗定时器的设计由其自己独立的时钟源控制,从而产生可以测量的相对抖动.
许多AVR能够使用外部32kHz晶振为专用定时器/计数器提供时钟,以提高实时测量的准确性.这种外部晶体是与主时钟不相关的另一个事件来源.(否则首先在额外的水晶中没有用...)
后者似乎有望承受相对较高带宽的潜力:当每个32kHz时钟周期定时,系统定时器运行速度明显加快(当前AVR @ 20 MHz时可实现600+倍!)并保守地假设只有1位每次测量熵的,这导致在熵32000+比特每秒 -远远超过了μC将永远消耗由本身.
编辑:同时,我已经对32kHz定时器方法进行了一些简单的测试,短期结果似乎质量很差.每个样本生成的熵的上边界似乎非常低,而我甚至没有测试样本是否有源于或多或少有规律相移的非显而易见的模式.这个结果可能是由于我的DUT的主时钟由外部晶体驱动,可以预期(在测量的精度范围内)在32kHz石英频率下在有限时间范围内观察时的频率同样稳定.延长两个样本(几分钟？)之间的时间可能会返回良好的熵,但带宽非常低.(Nb:测量的抖动也可能部分是由于中断延迟的变化,这取决于触发中断时执行的机器指令.)
编辑#2:看来我的DUT(ATmega1284)的内部RC振荡器会产生很大的频率抖动(几kHz/s); 当外部32kHz晶振定时时,运行在这个振荡器上似乎确实产生了相当多的熵(kBits/s).
在一个小实验中,我最近研究了前两种方法.在我的DUT上,EEPROM时序通常优于WDT:
定时EEPROM写操作每次写操作产生约4.82位熵,而看门狗定时器在频率方面似乎更稳定,每个看门狗超时产生约3.92位.此外,EEPROM的写入时间看起来更加平滑高斯分布,其中WDT的分布似乎有些不对称并且有很多像差.
Nb:聚合用于单个熵测量的多个"随机"事件实际上可能降低所获得的熵:源中的快速随机波动可以部分地相互补偿,产生具有与平均值的较低偏差的结果值.因此,代替定时,例如,一个实时秒(RTC晶体的32k 周期),在同一时间内采取32k定时(晶体的每个周期一个)可以预期更多的熵.
Avr-gcc编译的应用程序通常在执行用户代码之前将整个片上RAM清除为0x00,即main().将代码放入早期.init部分可以在gcc的初始化例程覆盖之前访问原始未初始化的RAM内容.
由于RAM的物理存储单元(位)中的微小差异以及取决于一些真正的随机热噪声(和其他效应),当电源(重新)应用于芯片时,并非每个单元都将其自身初始化为相同的已知状态.在加电后立即将芯片RAM的内容与某些功能相结合可以产生大量的熵,以便以后使用. - 这样做的缺点是它只能在电源关闭一段时间后可靠地工作,然后再打开.通过硬件,软件或外部信号进行的正常芯片复位将保留RAM的先前内容,因此不是(始终)良好的熵源.然而,由于在复位时很难预测复位时整个系统(RAM)的状态,因此无论如何都可以在复位后立即收集一些熵.
必须从与其应用的带宽和熵使用带宽相关的角度来看待熵源的质量.一些熵收集方法在某些秒时间内不会产生多于一位的熵,而其他方法(实际上不在μC上......)可能产生100 kbit/s或更多.
必须注意的是,人们无法通过算法从现有的熵中"创建"新的熵! - 一位熵不能被计算地转换为两位熵.
因此,每个时间单位不能(平均)消耗比在同一时间从熵源收集的更多(实际)熵.
当需要强随机数时,将一个或多个真实熵源与强PRNG组合使用每次新熵可用时收集的熵(重新)播种PRNG 并不罕见.
PRNG可用于生成比熵源实际上同时提供的基本上不可预测的数据.
作为一种特殊的PRNG,可以使用加密密码函数,其中使用熵来初始化和更新密码密钥.
Linux /dev/urandom通常以这种方式实现.
如上所述,在公共微控制器上生成真正的随机数是非常可行的.对于所有其他熵源,需要分析熵源提供的原始数量,包括它们包含的实际熵量以及每个时间单位产生的熵量,以确定源是否适合于用例与否.
真正的熵源和强大的PRNG的组合是通常实现的方法,并且应该在微控制器上使用.
编辑:
PRNG方法可能不是加密密钥生成的最佳选择.为此,应该只使用真正的随机位来产生安全密钥.收集这个数量的熵可能需要一些时间(可能是几秒),但由于密钥生成通常不会在μC上非常频繁地执行,因此这可能是可接受的.(在负载很重的服务器上,每秒有数百或更多的SSL(HTTPS)连接,这将是另一个问题...)
为了产生适合于密钥生成的高质量高熵比特流,应该采用如上所述的随机性提取器.
(另一方面,如果可以测量或估计源输出中的熵量,可以简单地将密钥长度缩放因子,(bitlength of key)/(entropy per bit sampled)然后直接使用来自熵源的原始低熵数据来生成这个更长的密钥,然后,它将具有与原始长度的完全随机密钥相同的整体熵.但是,这确实取决于密码如何处理不同长度的密钥.)