Linux随机数生成器的分析与应用

Linux随机数生成器的分析与应用 计 算 机 与 现 代 化 2007年第 9期 J ISUANJ I YU X IANDA IHUA 总第 145期 ( ) 文章编号 : 1006 22475 20070920137 203 L inux随机数生成器的分析与应用 武艳文 ()西安建筑科技大学网络中心 ,陕西 西安 710055 摘要 :介绍了 L inux随机数生成器的结构 、内部机理 ,分析了 L inux基于系统随机事件熵汇集的随机数提取和更新算法 。 基于算法分析了 Op enW R T的安全性 ,结果表明 Op enW R T存在安全隐患 ,并提出了改进途径 。 关键词 : L inux随机数生成器 ; L inux内核随机数算法 ; 熵 ; Op enW R T 中图分类号 : TP311 文献标识码 : A Ana ly s is an d A pp l ica t ion of L in ux Ran dom Num ber Gen era tor WU Yan2wen ( )Info rm a tion and N e two rk Cen te r, X i’an U n i. of A rch. & Tech. , X i’an 710055, Ch ina A b stra c t: Th is p ap e r in troduce s the in te rna l struc tu re and m echan ism of random num be r gene ra to r ba sed on en trop y co llec tion of system random even t, e sp ec ia lly focu se s on the random num be r gene ra ting and up da ting m echan ism , then p ropo se s a deep ana ly2 sis to the safe ty issue of Op enW R T, and po in ts ou t the h idden dange rs and the imp rovem en ts. Key word s:L inux random num be r gene ra to r; L inux e ssence random num be r a lgo rithm; en trop y; Op enW R T 过 两 个 设 备 驱 动 程 序 / dev / random 和 / dev / u random 0 引言 完成的 ,可以从这两个设备中读取伪随机位 ,两者的 生成随机数是构建密码的基本步骤 ,多数系统使 ( 差异在 于 安 全 级 别 和 延 迟 , 第 一 个 设 备 / dev / ran2 用伪随机数生成器 。计算机只能产生“伪随机数 ”, )dom 输出的比特极其安全 ,但会因等待系统比特而 绝对随机只是一种理想状态 ,无论技术怎样发展 ,也 ( )延迟 ,第二个设备 / dev / u random 输出的比特安全级 不会产生一串绝对随机的随机数 ,相对而言 ,只是随 别较低 ,但其输出过程无阻塞 。 机周期变大而已 。很多库例程产生的“随机 ”数仅考 2 L in ux随机数生成器的结构 虑用于仿真 、游戏等一般的应用 ,将它们用于密钥生 成一类的安全体制时远远不能满足要求 ,其问题在于 2. 1 基本结构 这些库例程使用的算法给出的未来值可以被攻击者 L inux随机 数 一 般 由 三 个 异 步 规 程 组 成 。第 一 轻易地推导出来 。 步 , 操作系统从各种各样的事件中收集熵到内核里 [ 5 ](面 。第二步 , 熵被注入到像 L FSR 受控线性反馈移 1 L in ux 伪随机数生成器 )位寄存器 的池中进行混合 。当任意位被请求 , 第三 L inux内核是开源项目 。内核是安装在各种类型 步发生 , 随机数产生并更新池中数据 。 设备中的不同 L inux发行版本的共同元素 ,生成的随 2. 2 池和计数器机数可以由任意位的内核使用 ,并能被应用程序编程 ()接口 A P I调用 。在内核中 ,从 L inux 伪随机数生成 用图 1描述 L inux伪随机数生成器 。内部状态被 ( 器接受 任 意 值 的 接 口 是 ge t _ random _ byte s 3 buf, 保留在三个熵池 : 主要 、辅池和 u random , 大小分别为 ) nbyte s。A P I对 L inux 伪随机数生成器的接口是通 512、128和 128字节 。熵源增加数据到主熵池 ;从主熵 收稿日期 : 2007206207 () 作者简介 :武艳文 19802,男 ,内蒙古赤峰人 ,西安建筑科技大学网络中心硕士研究生 ,研究方向 :网络系统安全分析与管理 。 计 算 机 与 现 代 化 138 2007年第 9期 3. 1 熵的收集池中提取并传送给辅池和 u random 池 , L inux 伪随机 数生成器从 u random 池或从辅池产生 。在随机数生成 熵的采集和增加的过程中 32 位的 typ e2va lue 在 期间 ,熵池的内在状态以反馈方式修正 。每个熵池都 各个不同的“噪声 ”源和各自的有效值 : 键盘操作 。合法的范围是 [ 0, 255 ]。有其特定的计数器 ,界于零和池大小之间的整数值 , 鼠标操作 。 32 位的鼠标数据是以移 动范围 作 为 它 的 主 表明池中当前的估计熵 。当熵从池中输出时计数器值 [ 7 ] 熵因子 。但是 , 其中只有 10 位用于标识移动 , 另外 2位标 被消减 ,当池中熵灌入时计数器值增加 。熵计数器随 识按钮状态 , 实际上 , 32 位中只有 12位是有效位 。 磁盘操提取位数量的增加而减少 ,计数器的增加更加复杂 。 作 。对完成磁盘 I/O 操作的计算 。它的值由 major 然后熵被估计 , 并且计数器相应地增加 ,熵的估计值 (与 m inor确定 major是类型 ,比如一个 block设备如果 majo r是 3,那么应该是硬盘 3, m ino r是编号 ,比如 m ino r是 4,那就是这个 使用同一熵源的最近几次事件的时间 。如果熵位从主 ) 硬盘上的第 4个分区 。。 池转移 , 接收池的熵计数器增加被移位的数量 。当提 ) (中断操作 。中断发生的结果是 IRQ 中断请求通道 数 取熵使 用 阻 拦 的 接 口 时 辅 池 熵 计 数 器 起 着 重 要 作 字 ,其合法范围是 [ 0, 15 ] 。值得注意的是 , 当前的内核版本 中硬件设备驱动对 L inux伪随机数发生器提供唯一有限的数 用 。 / dev / random 的任务是确定请求的池中是否有足 字中断值 。许多中断设定不会影响熵 。 够的熵 ,如果池中有足够的熵 ,那么 L inux 伪随机数生 3. 2 随机数的提取算法成器设法把熵从主池转移到辅池 ,否则 ,它将阻拦和等 [ 3 ]对于 SHA 21的说明 : SHA 21 是不可逆的 、防冲 待直到一些熵被输入 ,熵计数器增值 。 突 ,并具有良好的雪崩效应 。 SHA 21是联邦信息出版 ( )号 180 21和 180 22 F IPS 180 21 和 F IPS 180 22 指定的 标准 , SHA 21 的杂散序列在目前 F IPS推荐的各种方 法中 ,是目前唯一应用于实践的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。 L inux内核随机数提取及更新算法描述 : ( ) 算法变量 poo l , nbytes , j 说明 : poo l是提取熵 的一个 32 位的池 , nbyte s是请求的字节数 , j是当前在 池中的位置 。 SHA 21′表示 SHA 21的迭代作用 。 图 1 L inux伪随机数生成器 如图 2 , 在 u random 或辅池中始终保持 32 个字 2. 3 物理熵的增加 符 ,在这里不包含消耗熵 估计 步骤 和 熵再 装满 的 过 熵位主要是从池的外部源增加的 。个人计算机可 能有四个不同来源 : 鼠标活动 、键盘操作 、I/O 操作和中 断 。由于系统的异步特性 ,收集到的熵不能简单地添加[ 6 ] j。程 。算法前 16 位运用 SHA 21 ,产生结果到位置 到池 ,而是被收集然后再分批 ,几分钟后分批量化的数 然后申请 SHA 21 迭代 , 我们表示为 SHA 21 ′, 对池的 据添加到池中 ,缺省操作是将熵增加到主要池 ,如果主 右半部分运用 SHA 21 ′, 并产生结果到位置 j21 和 j22。 ()要池充满 熵计数器为 4096时 则加到辅池 。当辅池充 最后 , 它申请 SHA 21 ′对 16 字符结束在地点 j22 , 然 满时 , 输出随机数 ,熵被消耗 。然后再收集熵 ,如此循环 (后进行计算产生结果 。这结果被复制到目标 用 户 往复 。而 urandom 池中的熵并不增加 。该过程用估计 ) 或内核 缓冲池中 ,字节的数量被复制并更新 。如此 的熵值增加各池中的熵计数器 。 循环继续直到输出被请求的伪随机数 。 2. 4 随机数输出 从三个池的任何一个池中提取任意位 : 当用户 使用 / dev / u random 并 且 内 核 调 用 ge t _ random _ byte s 时从 u random 池 提 取 随 机 数 ; 当 用 户 使 用 / dev / ran2 dom 时从辅池提取随机数 ;当其它两个池中任何一个 不能提供足够的熵并且不需要再装满时从主池提取 随机数 。提 取 熵 的 过 程 包 括 三 步 : 更 新 池 的 内 容 , 提取任意位输出 ,消减池中熵计数器的值 。 3 对 L in ux 伪随机数发生器的分析 图 2 辅池算法结构图 2007年第 9期 武艳文 : L inux随机数生成器的分析与应用 139 辅池算法描述代码如下 : 以上是对 L inux内核伪随机数算法的描述分析 , W h ile nbyte s > 0 基于发布于 2006 年 1月的内核版本 2. 6. 15。对于所 )( . 15 ] temp = SHA 21 poo l [ 0 . 有发行使用同样内核的 L inux版本 ,除了内核以外的 ( )add poo l , j , temp [ 0 ] 应用程序外 , L inux随机数的生成完全相同 。)( 31 ] temp = SHA 21 ′poo l [ 16 . . [ 2] 3. 3 目前 L inux伪随机数生成器应用于 O penW RT路 )( ( ) temp [ 2 ] add poo l , j - 1mod 32 , 由器中的安全分析及可能的改进 ( ( ) )add poo l , j - 2mod 32 , temp [ 4 ] Op enW R T是基于 L inux系统的无 线路 由 器 , 它( ( ) temp = SHA 21 ′poo l [ j - 2 mod 32 提供许多密码服务 ,如 SSL、SSH、无线密码 。所有这 ( ) ). . . j - 2 - 15mod 32 ] 些服务安全都依赖于 L inux伪随机数生成器 。Op en2 ( )temp = fo ld ing temp [ 0 . . 4 ] W R T路由器熵来源非常有限 。在 Op enW R T路由器 ( ( ) ) ou tp u t temp , m in nbyte s , 10 () 中没有键盘 、鼠标 、硬盘 。使用闪存 大小 4,16 MB ( ) nbyte s = nbyte s - m in nbyte s , 10 ( ) 作为一 个 专 用 文 件 系 统 , 但 这 个 文 件 系 统 不 能 对 j = j - 3 mod 32 end wh ile L inux伪随 机 数 生 成 器 提 供 熵 。因 此 , 网 络 中 断 是 主池的算法与辅池 、u random 池略有 不 同 , 因 为 L inux伪随机数生成器唯一的熵源 , 而网络中断又是 ( ) 主池的位更长 128 位 。当需要更新其他任何一个 由无线网络活动引起的 。潜在入侵者只要监听从路 池时从主 池中 提 取比 特位 。在 这 种 情 况 下 , SHA 21 由器初始化开始时所有网 络信 息 流量 , 通 过本 文 对 () L inux伪随机数生成器的算法分析 ,经过计算得到的 或 SHA 21 ′操作应用于每 8 个在 16 字节大块的主 结果 ,就很容易攻击网络 。另外 , 在重新启动或断电 池 ,结束在 j28 。第一个 8位 SHA 21 操作更新池中八 重开的情况下不能恢复原有 L inux伪随机数生成器 个字节 ,最后操作引起所请求位的输出 。 (状态 ,而是被重新设置可预测的值 由时间和恒定的 主池算法描述代码如下 : W h ile nbyte s > 0 ) 字符串组成 ,导致入侵的人能计算和模仿 L inux伪 ( )temp = SHA 21 poo l [ 0 . . 15 ] 随机数 生 成 器 的 状 态 。潜 在 的 攻 击 者 只 要 能 获 得 ( )add poo l , j , temp [ 0 ] L inux伪随机数的生成器状态或者监听从路由器初始 ( )temp = SHA 21 ′poo l [ 16 . . 31 ] 化开始时所有网络信息流量 ,就可以很容易地达到目 ( ( ) )add poo l , j - 1mod 128 , temp [ 2 ] 的 。通过以上 的分 析 可以 发现 对 于单 熵 源 的 L inux ( )temp = SHA 21 ′poo l[ 32 . . 47 ] 伪随机数生成器应 用 于 Op enW R T来 说是 很不 安 全 ( ( ) )add poo l , j - 2mod 128 , temp [ 4 ] 的 。为了改善 Op enW R T的安全可以增加 L inux伪随 ( )temp = SHA 21 ′poo l [ 48 . . 63 ] 机数生成器的熵源 ,或者能在断电情况下保存 L inux ( ( ) )add poo l , j - 3mod 128 , temp [ 1 ] ( )temp = SHA 21 ′poo l [ 64 . . 79 ] 伪随机数生成器的状态 。 ( ( ) )add poo l , j - 4mod 128 , temp [ 3 ] 4 结束语( ) temp = SHA 21 ′poo l[ 80 . . 95 ] ( ( ) )add poo l , j - 5mod 128 , temp [ 0 ] 在这里没有考虑到多 CPU 硬件构造 , 或独特的 ( )temp = SHA 21 ′poo l [ 96 . . 111 ] 硬件构 造 的 操 作 和 熵 汇 集 方 法 。L inux 把 / dev / ran2 dom 作为一个接口提供给那些需要优质随机数的应 ( ( ) )add poo l , j - 6mod 128 , temp [ 2 ] ( 用程序 。它提供了一个大容量的信息熵集合 512 比 ( temp = SHA 21 ′poo l [ 112 . . )127 ] )特 以满足操作系统和各种软件的需要 。当信息 熵 ( ( ) add poo l , j - 7mod 128 , )temp [ 4 ] 的性质不太重要时 ,另一个设备 / dev / u random 可以用 ( ( ) add poo l , j - 8mod 128 , )temp [ 1 ] 作伪 随机 数 生成 器 , 提供 伪随 机 数 , 以 免 耗 费 / dev / ( ( ( ) temp = SHA 21 ′poo l [ j - 8 mod 128. . . j - 8 - random 里的信息熵集合 。基于 这 些分 析 , 可以 应 用 ) )15 mod 128 ] 于对 L inux随机数安全 、密码破译 、L inux 系统 Op en2 ( )temp = fo ld ing temp [ 0 . . 4 ] ( ( ) ) ou tp u t temp , m in nbyte s , 10 [ 8 ] W R T安全以及 DO S攻击等展开进一步的分析 , 提 ( ) nbyte s = nbyte s - m in nbyte s , 10 出解决相应问题的方法 ,改进 Op enW R T路由器乃至( ) j = j - 9 mod 128 ()end wh ile 整个系统的安全性 。 下转第 142页 计 算 机 与 现 代 化 142 2007年第 9期 ( ) id: = Gene ra te ID ; / /生成唯一的 ID 号 表 1 主要的 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 签域 ( re spon se: = TF ileStream. C rea te _ loca lp a th + id + ext, fm 2 书签名含义说明或例子 CH IN ESET IM E中文时间二 ??四年三月二十四日) C rea te; DOC_TO P IC标题对应于发文单的标题 ( ) reque st. A ddFo rm F ie ld ′ac tion′, ′temp la te′; YW FW _CO PYS印发分数 ( ) reque st. A ddFo rm F ie ld ′id′, temp la te Id; / /文档模板 YW FW _MA IN SEND主送单位( ) reque st. A ddFo rm F ie ld ′u se rid′, _u se rid; YW FW _CO PYSEND抄送单位( ) reque st. A ddFo rm F ie ld ′no tu sed′, ′′; YW FW _CORR ECT校对人 ( ) h ttp c lien t. Po st _u rl, reque st, re spon se; / /将参数传递到 _ YW FW _KEYWORD主题词 () 党 字 [ 2004 ]相当于“武滇边 u rl中 ,由对应的 _u rl根据 ac tion 的值进行处理并将所需要的 文号的一部分 YW FW _F ILENUM 第 19号 ”中的“武滇边 ”数据通过 re spon se传回 。 () 党 字 [ 2004 ]相当于“武滇边 文号的一部分 ( ) ( ) if reque st < > n ilthen F reeA ndN il reque st; YW FW _AWORD 第 19号 ”中的“党 ”( ) ( ) if re spon se < > n ilthen F reeA ndN il re spon se; () 党 字 [ 2004 ]相当于“武滇边 文号的一部分 YW FW _YEAR ( ) ( ) if h ttp c lien t < > n ilthen F reeA ndN il h ttp c lien t; 第 19号 ”中的“2004” 上述 A c tion的值按实际情况进行设置 。() 党 字 [ 2004 ]相当于“武滇边 文号的一部分 YW FW _INO 第 19号 ”中的“19” 3. 发文字号的处理 。 (发文字号有固定的模式 : 由发文单位代字 、年份 发文年 2. 正文信息的保存 。 ) () 度 、序号 发文顺序号 三部分 组成 , 如国 发 [ 1994 ] 3 号 , 因 根据用户对文件形式的需求 ,系统自动调出对应的 W o rd 此 ,发文字号根据不同单位不同部门都有所不同 ,为了系统的 模块 ,并通过前面的方法写入对应的书签 。发文单各字段信 通用性 ,用户可以根据需要修改模板定义文件 ,系统调用文件 息已经通过 书 签 替 换 到 对 应 的 占 位 符 中 , 用 户 可 以 直 接 对 模板时自动读取该文件 ,将对应字段作为下拉选择框的内容 W o rd文档进行编辑和修改 。系统自动将修改完毕并保 存后 供用户选择 。具体实现因限于篇幅不做进一步的介绍 。 的 W o rd文档传递到对应的服务器 和 发 文 单 对 应 的 正 文 中 。 正文 信 息 的 保 存 主 要 利 用 组 件 TidH ttp、T IdM u ltiPa rtFo rm 2 2 结束语 D a taStream 和 TF ileStream 来实现 ,具体程序如下 : va r 目前 ,已有很多政府部门和企业建立了自己的电 子公文系统 ,通过红头文件的自动生成实现真正的无 h ttp c lien t: T IdH ttp; 纸化办公 。文中论述了一个基于 J2 EE 应用的“红头 reque st: T IdM u ltiPa rtFo rmD a taStream; 文件 ”自动生成的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 和实现 ,该系统已经应用在 B / re spon se: TF ileStream; S模式 的 办 公 自 动 化 系 统 中 , 较 好 地 满 足 了 对 于 id: String; W o rd文档处理的需求 。 ext: String; / /文件后缀 doc: P trTDocum en ts; / /将所有变量打包传送给 h ttp 服务器 reque st: = n il; 参考文献 : re spon se: = n il; [ 1 ] 李冬梅 . 基于 W eb OA 的痕迹保留技术 [ J ]. 铁路计算 ( ) ( ) h ttp c lien t: = T IdH ttp. C rea te n il; 机应用 , 2003, 12 6: 41 243.reque st: = T IdM u ltiPa rtFo rmD a taStream. C rea te; 林瑾 . 网上作业批改系统痕迹保留的一种方法 [ J ]. 福 [ 2 ] ( ) ext: = ′. doc′建电脑 , 2002 9: 62 263. ( ) ()N a tiona l In stitu te of Standa rd s and Techno logy N IST . 上接第 139页 [ 6 ] A dvanced Enc ryp tion Standa rd [ DB /OL ]. h ttp: / / c src. 参考文献 : n ist. gov /C ryp toToo lk it / ae s / , 2006 207205. [ 1 ] Robe rto A rcom ano. 7 ———HOW TO V0. Ke rne l A na lysis [ DB /OL ]. h ttp: / /www. ke rne .l o rg, 2006 212 227. B Schne ie r. Sec re ts & L ie s: D igita l Secu rity in a N e two rked [ 7 ] Ka loz. Troub le shoo ting [ DB /OL ]. h ttp: / /www. op enw rt. W o rld [M ]. John W iley & Son s, 2000: 85 2101. [ 2 ] Tzachy R e inm an, D ah lia M a lkh i. O n L inux R andom N um 2 o rg, 2006 211225. [ 8 ] D Ea stlake, P Jone s. U S Secu re H a sh A lgo rithm 1 be r Gene ra to r [ D ]. Schoo l of Enginee ring and Comp u te r [ 3 ] ( ) SHA1 , R eque st fo r Comm en ts 3174 [ Z ]. In te rne t En2 Sc ience, The H eb rew U n ive rsity of J e ru sa lem , J e ru sa lem , Israe l. E lu l 5765 Sep tem be r 2005. ginee ring Ta sk Fo rce, Sep tem be r 2001. D avid A W hee le r. L inux和 U n ix安全编程 HOW TO [ DB / T N ylund, R R und s. Imp lem en ting a R andom D evice D riv2 [ 4 ] [ 9 ] OL ]. h ttp: / /m an. ch inaun ix. ne t, 2006 212215. e r U nde r So la ris 8 [ D ]. M a ste r’s The sis, D ep a rtm en t of Comp u te r Sc ience, U n ive rsity of Go thenbu rg, Sweden, T Ts’o. R andom. c—L inux Ke rne l R andom N um be r Gene r2[ 5 ] 2002. a to r[ DB /OL ]. h ttp: / /www. ke rne l. o rg, 2005209 212.