对称密钥加密方案 – 流密码

基本理念:用一个伪随机的密钥来代替在一次性密码本中使用的随机密钥

  • 伪随机位生成器Pseudorandom Bit Generator (PRBG)是一个确定性算法,将(随机)种子作为输入,并输出更长的“伪随机”序列称之为密钥流
  • 这个随机的种子就是密钥,他在Alice和Bob之间共享,他们可以通过这个种子+PRBG来生成伪随机序列从而加密解密信息
  • 不再需要完美的保密性-安全性取决于PRBG的质量
  • 我们又称PRBG为 Keystream generator 流生成器

伪随机位生成器的安全要求

  • 密钥流应与一个随机序列“无区别“(不可区分性)
  • 如果对手知道密文的c1部分,和对应的明文m1,那么她就可以轻松找到密钥流的对应部分k1 = c1⊕m1。 从而给定密钥流的一部分,不应该知道有关其余密钥流的任何信息(不可预测性)

密钥流生成器Keystream generator 是流密码的关键安全组件

将生成器视为一个有限状态机 Finite state machine

  • 状态:存储的内部值
  • 状态更新函数:在每个时间间隔更改存储的内部值
  • 输出函数:密钥流输出是现在存储值的函数值

设计限制

  • 效率
    • 输出密钥流的速度
    • 对于实时应用,必须不对数据传输和恢复产生延迟
  • 实施要求
    • Footprint(硬件/软件)
    • 内存 Memory
    • 功率 Power
  • 保持同步 Maintaining synchronization
    • 高效的处理失去同步的问题

带有1个输入的密钥流生成器

  • 初始流密码的设计包括了只有1个输入(key)的密钥流生成器
  • 优点
    • 密文和明文长度相同
  • 缺点
    • 密钥和密钥流之间一一对应
    • 不能使用相同的密钥来加密不同的密文

带有2个输入的密钥流生成器

  • 现代流密码设计包括了具有2个输入(key, initialisation vector)的密钥流生成器
  • 优点
    • 可以搭配不同的初始化向量(IV)重复使用一个密钥
  • 缺点
    • 需要跟密文一起传输这个初始化向量IV -> 常量开销

基于帧的加密

  • 将每个通信视为一系列帧或数据包,并且使用由相同密钥构成的密钥流依次进行加密,但是有不同的帧号。
  • 失去同步只会导致在该数据包中剩余的数据丢失,但下一帧将重新获得同步
  • A5/1 算法应用了此加密方式用于GSM电话通讯
    • 每一个交流使用一个64 bits的密钥加密
    • 把这个交流分割为228 bits长度的帧
    • 使用22 bit 的帧编号去生成228位的密钥流
    • 在4.6毫秒内完成加密

线性反馈移位寄存器(LFSR)

  • LFSR是流密码设计中的常见组件。
  • LFSR简单,快速地在硬件和软件中实现,并具有良好的伪随机性。
  • 任何无限周期序列递归关系定义
  • The vector (s0; s1; : : : ; sn−1) is called the initial state vector 初始状态向量
  • 初始状态向量与上面的关系可以定义序列的所有项。
  • 幻灯片P26-30包括了一个例子
  • LFSR的属性-有三个属性来测量密钥流生成器的强度,序列应该有
    • 尽可能大的周期 Large Period
    • 尽可能大的线性复杂度 Large Linear complexity
    • 随机噪音般的特征 random noise-like characteristics
  • LFSR的周期
    • 确定性伪随机二进制数生成器会产生一个周期性序列,这意味着它会在一段时间后重复。
  • 举例:011101110111011101110111…的周期为4
  • 针对于小周期的攻击 Attack on small period
    • 对于良好的流密码,我们期望密钥流的长度大于明文的长度。
    • 如果密钥流的周期小于明文的长度,那么将有2部分信息使用密钥流的相同部分加密
    • 通过对这两个部分进行异或XOR运算,密钥流将抵消,就可以获取明文字符串的XOR结果。
    • 然后可以通过利用明文的冗余来攻击。
  • 我们不想直接使用LFSR的输出来形成密钥流。所以我们有以下两种基本方法
    • 可以对序列的多个输出进行采样并通过非线性滤波器。
    • Multiple outputs from the sequence can be sampled and passed through a non-linear filter.
    • 多个LFSR的输出可以通过一个非线性组合器。
    • The outputs from multiple LFSRs can be passed through a non-linear combiner.
      • 应用:A5 cipher

A5 Cipher

  • A5密码是二进制同步流密码,今天在大多数GSM移动电话中应用。
  • A5有三个变体:
    • A5 / 1是1987年定义的原始算法
    • A5 / 2是A5 / 1的弱化版本,最初旨在在欧洲以外部署,但在GSM标准下不再允许
    • A5 / 3是用于第三代移动系统(3G)的最新算法
  • 设计师最初对A5 / 1的设计保密,但在1994年公开
  • A5 / 1算法使用了3个LFSR,并组合他们的输出。
  • 这三个LSFR的时钟是不规则的(irregularly clocked),这意味着总输出不是线性的
  • 每个LFSR都有一个时钟位(下图中的橙色)。 如果每个LFSR的自己的时钟位与其他LFSR的时钟位多数一致,则对每个LFSR进行时钟控制(更新)。
  • 密钥长度为64位,用于定义每个LFSR的状态向量。 在部署中,据说密钥的10位是固定的。 (请注意,每个LFSR必须具有非零的初始状态。)
  • A5 / 1密码分析
    • 1997年,Golic发表了首次A5 / 1密码分析,所需时间()比暴力搜索()少得多
    • 已经发布了一些改进,但是都需要一些已知明文。 其中最好的方法是需要“不到一分钟”的已知语音。
    • 2003年,Barkan,Biham和Keller基于GSM中的实现细节破解了了A5 / 1。
    • 在2011年,具有快速GPU和TB级闪存的普通PC可以在几秒钟内破解A5 / 1加密的GSM会话,概率超过90%
  • 用于现代GSM和GPRS通信的A5 / 3(KASUMI)目前基本安全(尽管理论上的弱点是已知的)。

RC4 Stream Cipher

  • 由Ron Rivest 发明于1987年
    • 直到最近,被广泛用于商业产品,包括Adobe Acrobat,Windows密码加密,Oracle安全SQL,SSL / TLS等
    • 优点:非常简单; 极快 可变密钥长度,没有发现灾难性的弱点。
    • 缺点:设计标准是专有的;直到2001年为止没有太多的公众审查
    • RC4有两个组成部分:一个密钥调度算法和一个密钥流生成器。

无线安全 Wireless Security

  • 无线网络已经变得普遍。
  • 无线网络的流行标准:
    • IEEE 802.11(范围更大,速度更高,通常用于无线局域网)。
    • 蓝牙(短距离,低速)。
  • 新的安全问题:
    • 更多攻击机会(无需物理访问)。
    • 可远程攻击(在高性能天线下可超过1公里)。
    • 无法取得攻击的物理证据。
志远

志远

一枚苦逼的大三技术狗,目前就读于加拿大滑铁卢大学,擅长C++/Python,现在没事研究研究Linux服务器运维和PHP网站开发。...

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>