你好,密码学(5):伪随机数生成器和攻击OTP密码

上节回顾

在上一节中,我们讨论了第一个完整的密码OTP密码,并以通过香农提出的密码安全理论衡量了OTP的安全性是完美的。

本节我们将对收尾上节,并讨论一些必要的知识PRG和针对OTP密码的攻击。

“OTP密码是最优情况”

引语

上节提到,OTP密码由于密钥长度需等于明文长度,因此在实际中很难实现

那么,有没有一种密码,既具有完美安全,密钥长度又没有那么长呢?

为什么这么说?

因为当然没有啊!(///ω///)

没想到吧

没想到吧!

怎么样!没想到吧!

让我们再次请出克劳德·香农教授:

克劳德·香农 来源:a0.att.hudong.com

怎么样!帅不帅!

香农在论证完“OTP密码具有完美安全性”之后,又论证了一个非常重要的命题:

若一个密码完美安全,则其全体密钥的数量的必须不少于全体明文的数量

即:
$$
|\mathscr K|\ge |\mathscr M|
$$
也就是说… …
$$
\mathtt{for \;\: perfect \;\: key,}\quad len(k)\ge len(m)
$$
因此,OTP密码的密钥长度等于明文长度,其实是完美密码中的最优情况

因此,对于上篇文章中评论提出的问题:对于“足够长的PSK”没有足够长的PSK,最“足够”长就是和明文一样长。

(注:香农完整论文请见(PDF) A Mathematical Theory of Communication by C.E. Shannon hosted by the Harvard Mathematics Department at Harvard University

所以… …

伪随机数生成器(PRG)

在攻击OTP密码(嗯?)和讨论流密码(下篇讲)之前,我们需要了解一个相当重要的玩意:伪随机数生成器(Pseudo-random Generator, PRG)

这有啥用?

本篇不会涉及到流密码。但为了说明PRG的用途,在这里还是要提一下。

流密码实现的基本思路,就是将随机的密钥换成伪随机的密钥;即对输入的密钥$k$应用一个伪随机数生成器$G$,将其扩充为一个长得多的伪随机密钥$G(k)$,随后使用这个$G(k)$完成加密过程。

定义

本质上讲,PRG就是一个高效的、确定的、不可预测的函数$G$,能将一个长度为$s$的二进制数字符串,扩充为一个长得多的、长度为$n$的二进制数字符串。即:

不可预测性

我们提到,PRG必须具有一个性质,叫做不可预测性。

这是个啥玩意呢?

简单来说,“不可预测”就是“不”“可预测”。

所以,下面我们将讨论可预测性

想不到吧

(其实这么安排是为了便于理解。真的,你们要相信我)

如果一个“PRG”函数$G$是可预测的,那么说明存在一个高效的函数$A$,能过通过$G$的输出的前1位字符串,还原出余下的位。即:
$$
\exists \:i:\quad G(k)|{1,…,i} \overset{A}\longrightarrow G(k)|{i+1}
$$
如果一个“PRG”是可预测的,那么若一个攻击者截获了密文,并且事先知道明文的前缀;(例如必须以“Dear Ray Eldath: ”开头,哈哈)那么他可以将截获的密文与该前缀异或,得到的就是$G(k)$的前缀。由于该“PRG”是可预测的,因此该攻击者就能通过$G(k)$的前缀,还原出整个$k$。

严格地讲(有兴趣的阅读,跳过此部分对后续内容理解没有影响),不可预测性阐述对于所有的$i$,没有有效的破解算法$A$,能以不可忽略的概率预测出第$i+1$位。

  • 不可忽略:可理解为函数值大于某个特定概率值$\varepsilon$(例如$\varepsilon\gt {1 \over 2^{30}} $);或对于函数$\varepsilon:Z^{\ge0}\rightarrow R^{\ge0}$,函数值大于$1$除以某个多项式的值的可能性无限大(即$\exists \:d:\varepsilon(\lambda) \ge {1 \over {\lambda^d}}\quad \mathtt{inf.\;\: often}\quad(\varepsilon > {1\over \mathtt{poly}},\; \mathtt{for \;\: many\;\:}\lambda)$)(别问窝后面的定义啥意思,自己想。窝也看不懂)。

典型的弱PRG实现

这是反例!!请勿在要求密码学强度的系统中使用这些实现!!

这是反例!!请勿在要求密码学强度的系统中使用这些实现!!

这是反例!!请勿在要求密码学强度的系统中使用这些实现!!

  • 线性同余方法:该方法被广泛应用于统计学强度的系统中。关于线性同余方法,维基百科的解释已经很清楚了,在此不过多解释:

    维基百科 - 线性同余方法#随机性 摘自zh.wikipedia.org

    此外,对线性同余方法的改进,请见清华大学学报(自然科学版)# 2009.02 - 改进线性同余法随机数发生器

  • GNU C Library中提供的random()实现:该生成器每轮输出几位相同数据;每轮应用相同的线性变换,因此非常容易预测。要构建密码学强度的系统,请使用C++标准库中头文件random提供的各种random_engine

  • 自Java 7起提供的Random类及使用该类的Math.random()方法:从该Random.nextDouble()的实现可以看出,尽管使用了各种运算,但该方法依然是可预测的。要构建密码学强度的系统,请使用SecureRandom类

  • … …

一般来说,各大编程语言提供的伪随机数通用实现出于效率方面的考量,都达不到密码学强度的要求。请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现。请查看使用的编程语言是否有提供密码学强度的伪随机数生成器实现。没有就自己实现一个吧。

咳咳。我再强调一下:

请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现!!

请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现!!

请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现!!

请查看使用的编程语言是否有提供密码学强度的伪随机数生成器实现。没有就自己实现一个。

这点相当重要。类似Kerberos 4的系统就因为伪随机数生成器实现的问题而被攻破。(参见维基百科 - Kerberos#历史

攻击OTP密码

看到这个标题,我不确定会不会有人心生疑问:

OTP密码不是完美安全的吗?又怎么能被攻破呢?

是的!OTP密码确实完美安全,但“完美安全”指的是免疫任何唯密文攻击。而本节所述的攻击大多是针对密码实现的攻击。(也就是说这些实现或多或少的不严格符合OTP密码的定义)

。。。。。。

好啦!让我们开始吧!

Attack 1:使用相同密码本加密多于一个的不同密文

我们来通过一个例子看看,当使用同一密码本加密两条(此处以两条为例)的不同密文时会发生什么:

由于上文已经介绍了PRG的相关知识,因此下文中将使用$PRG(k)$代替前文中的$k$,从而使论述更为可信。

首先,我需要得到这两个消息的加密结果(密文):
$$
c_1=m_1\oplus PRG(k)\\
c_2=m_2\oplus PRG(k)
$$
Q1:那么,当我计算$c_1\oplus c_2$时,会得到什么呢?

先不要往下看,先自己想想!

由于$PRG(k)\oplus PRG(k)=0$,因此$c_1\oplus c_2$的结果就为$m_1\oplus m_2$

震惊!将使用相同密码本加密两条密文的结果异或,得到的竟然是… …

得到了$m_1\oplus m_2$,由于语言本身(如英语)或编码方式(如ASCII)本身就提供了额外的信息,我们很轻易的就能分开$m_1$和$m_2$,从而得到明文。

这么明显的错误,难道不是很容易避免吗?

当然不是!

著名的WEP协议(已过时)就因为这个问题(和其他一些严重的安全问题)最终被取代。

说句题外话:在无线局域网络环境的配置中请勿使用WEP协议!推荐使用安全得多的WPA2/PSK协议。

在WEP协议中,用于加密(可简单理解为携带无线局域网数据的单位)的密钥为$PRG(\theta \;||\;k)$,(其中$||$表示“拼接”,$\theta$表示“帧计数器”,即初始时为$0$,每多发送一个帧的计数器时$+1$s的计数器)我们可以看到WEP协议为了使每个帧使用不同的密钥加密引入了$\theta$这个帧计数器。但是由于密码的长度是固定的,因此$\theta$并不能无限增大,必须在约$10^{24}$后重置到$0$。于是… …

问题就发生了。

基于一些其它的WEP协议的重大安全缺陷,我们最少可以在监听$40000$个帧后得到用于加密的主密钥$k$。至此,WEP系统已经可被认为是“易被攻破的”了。

那有没有更好的实现方案?

Attack 1:更好的实现

从本质上看,Attack 1的出现是由于“不同明文使用不同密钥加密”的实现不正确导致的。因此下面将给出此类问题的通用实现(可能不是最好的):

在上文对PRG的讨论中,我们指出PRG函数输出的是一个比输入长得多的字符串,(请允许我去掉那一长串形容词)因此我们可以直接将该长输出分段,然后每段加密不同的明文:

capture1

从而为每个明文分配不同的伪随机密钥。

Attack 2:不完整的密文

上篇文章对OTP密码的讨论中可以看出,OTP密码并没有提供对密文的完整性保护;也就是说,攻击者可以不被发现地修改密文,从而对明文造成特定影响

Q2:我们使用OTP加密明文$m$将得到$m\oplus k$,但若攻击者截获此密文,并对其施加$\oplus p$,再解密被施加了操作的密文,我会得到什么?

通过OTP密码的定义和异或运算的定义,我们可以知道$D(k,\: (E(m,\:k)\oplus p)\:)=(\:(m\oplus k)\: \oplus p)\oplus k$将得到$m\oplus p$

问题就出现了。

在预知$m$中部分消息和消息位置(比如$m$中一定在位置$(i,\:i+10)$($i$已知)包含字符串Ray Eldath)的情况下,我可以通过计算 我想替换上去的消息 和 已知明文中消息 的异或得到$p$,再在对应位置替换,则可以完成对消息的“不被发现的”篡改。

那有没有更好的实现方案?

Attack 2:更好的实现

答案是:没有!

因为Attack 2完全是由于“OTP密码不提供完整性保护”导致的,因此只有为OTP密码增添完整性保护,才能解决这个问题。

关于如何为密码增添完整性保护,请期待以后的文章。(意思就是先坑着)

<完>

=。=
0%