密码学之前后向安全性

本文将讨论密码学中的 前向安全性(Forward Security) 与 后向安全性(Backward Security) ,希望读完本文后,你再也不会混淆这两个概念。

在开始本文之前,希望你有如下预备知识:

  • 密码学(Cryptography)是一门什么样的学科?
  • 单向函数(One Way Function)是什么?有哪些例子?
  • 密码算法与密钥是什么?敌手(Adversary)在密码学中是一个怎样的概念?

单向函数与密码算法

现代密码学的基石:伪随机性

Pseudorandomness,即伪随机性,是一个现代密码算法必须要具备的性质,因为从反面考虑,如果你设计的密码算法都做不到「看起来」是随机的,那岂不是很容易就被攻破了?当然,伪随机性在数学上有着更严格的定义与论证,在密码学中也有更深厚的历史背景(比如其实是姚期智院士率先给出的伪随机性正式定义[1])。伪随机作为现代密码学的核心要素,如何更好地实现它一直是许多科学家追逐的目标,比如采用物理的随机熵源(真随机数发生器),或者使用一个秘密的随机种子(密钥)等等。没有伪随机性作为算法的根基,Rivest也不能打包票对你说“哦我的老伙计,试试这个RSA吧,它真的很棒”。

在现代密码算法中,伪随机性可以由伪随机数发生器(PseudoRandom Number Generator,PRNG)来提供。这就是说,要设计一个具备伪随机性的密码算法,你可以先明确怎么得到一个PRNG。因此,PRNG这个部件的好坏,将直接决定了算法是否足够安全。PRNG在现代密码学语义中的定义如下:

令$G$为一多项式时间算法,其输入为$s\in \{0, 1\}^{n}$,即为一长度为$n$的01比特串,输出的长度记作$l(n)$;其中,$l(\cdot )$也为一多项式时间算法,但与$G$不同的是,$l(n)$只是表示是$n$的多项式界下的一个值,$l(\cdot )$可以等于$n^{2}$,也可以等于$n$,只要是多项式界内的即可。若G为一PRNG,则应同时满足如下两个条件:

  1. 对于任意的$n$,都有$l(n) > n$;
  2. 若此时对于任意一具有多项式资源的敌手$\mathcal{A}$,都存在一个可忽略(negligible)的概率$\epsilon $,使得下式成立:

$$ |\mathrm{Pr}[\mathcal{A}(r)=1] - \mathrm{Pr}[\mathcal{A}(G(s))=1]| \le \epsilon $$

其中,$r$为一随机比特串(不用管它从哪来的),而$G(s)$即为$G$的输出,为一伪随机比特串. 而$\mathcal{A}(r)=1$与$\mathcal{A}(G(s))=1$分别表示敌手$\mathcal{A}$能正确判断出所给比特串是真随机串还是伪随机串。因此,条件2表明敌手$\mathcal{A}$面对$G$的输出时,只能以一个可忽略的、极小的概率将其与真随机串区分开来,这保证了每个PRNG的输出都会足够贴近真实的随机输出。而对于条件1,如果我们先假设$l(n) \le n$,那这意味着输入与输出都不一定能满足双射的条件,即PRNG的一个输出甚至可能对应着多个输入。由此,这样的PRNG很容易就被攻击者猜解碰撞出来了;因此如果令$l(n) > n$,如$l(n)=2n$,那么一个输入$s$则平均对应着$2^{n}=2^{2n}/2^{n}$个PRNG输出,也就是这是一种非常稀疏的映射关系,这种「扩展性」保证了采取穷举手段从PRNG的输出空间来进行碰撞是困难的。

现在我们有了伪随机性这把(简陋)的螺丝刀,还能造出更好的工具吗?

单向函数

首先便是直接由伪随机性抽象而来的、更加直观的,但也非常重要的性质:One-Wayness,即单向性。顾名思义,再结合PRNG的定义,相信大家此时对单向性及单向函数(One-Wayness Function, OWF)也会有这样一个模糊理解:

给函数一个$x$,可以跟容易算出对应的函数值$y$,但是对于函数值$y$,很难逆推得到原来的$x$

这种理解其实已经非常接近单向函数的正式定义了,如下所示:

一个函数f若称为单向函数,则应满足如下两个条件:

  1. (容易计算)存在一多项式时间算法$A_{f}(\cdot )$,对于任意输入$x \in \{0, 1\}^{*}$,都能在多项式时间内输出$A_{f}(x)=f(x)$;
  2. (难以求逆)对于所有的多项式时间算法$D(\cdot )$,都存在一个极小的可忽略概率$\epsilon$,使得下式成立:

$$ Pr[D(f(x)) \in f^{-1}(f(x))] \le \epsilon $$

其中,$x$的选取是从$\{0,1\}^{n}$中随机均匀采样。在上述定义中,难以求逆这一性质只需要在输入是均匀选取的这一条件下成立即可,即对于极个别的输出点,攻击者还是有可能还原其对应的输入的。在某些比较极端的定义里,难以求逆这一性质甚至只要求在输入$x$足够长时才满足。

此时你可能会说,既然一个单向函数是容易计算的,那对于一个特定的输出$y$,那我为什么不能试着遍历所有$x_{i}$,从而找到$f(x^{*})=y$?没错,任何单向函数在给出足够时间和计算资源的条件下,都是可求逆的;但不要忘记条件2中面向的是多项式时间算法,对于那些指更高级的攻击算法,单向函数可能真的一下就被攻破了。因此,条件2所谓的难以求逆,实际上是难以「高效」求逆。

实际上,任意一个PRNG都可看作是一个单向函数 [2],而要证明这一点,即证「对于一个PRNG算法 $\mathcal{G}$,如果存在敌手$\mathcal{D}$能以不可忽略的概率对 $\mathcal{G}$的输出结果求逆,那么存在一敌手$\mathcal{D}^{'}$也能以不可忽略的概率分辨$\mathcal{G}$的输出与真随机串。一般而言这种证明采取“安全性归约”的方法即可,不过这和本文内容无关。总之,基于PRNG可以构造出单向函数,而有了单向函数这个「高级扳手」,我们就可以造出更方便的工具了,比如大名鼎鼎的(密码学安全的)哈希函数。

阿克琉斯之踵:密钥的管理

PRNG与OWF由于其简洁但重要的计算性质,常被用于生成密码算法的密钥,而PRNG这种「看起来」随机的特点,正是方便我们生成一些别人不想预测出的敏感信息。另外,OWF则能帮助我们为已有密钥提供一个「陷门」(Trapdoor),陷门的输出(通常为OWF的输出)可以作为新密钥、或者某个公开值,或者某个校验值等等。

二者的配合让一个系统中,密钥的在线更新成为了可能。如果一个OWF提供的伪随机性足够好,那我们是不是可以用它源源不断地生成新密钥呢?当然可以!

 

密码学之前后向安全性

 

如上图所示,系统管理员可以使用当前密钥$K_{i}$、当前时间戳$t_{i}$以及一个盐值Salt(如0x12345),在MD5这一哈希函数的帮助下源源不断的迭代出新密钥$k_{i + 1} = \mathrm{MD5}( K_{i} || t_{I} || Salt) $。当然,MD5可以替换为其他常见的,更安全的哈希函数。

可是,随着密码分析技术的不断增强,原来认为安全的MD5目前来看也不那么安全了,原本的单向函数也不再那么单向了。而管理员此时还觉得: 

反正我密钥一直都在给你们更新,况且MD5也没那么容易被攻击,这个方案又不是不能用

上一篇:H5播放器之——APlayer


下一篇:gym103428 部分题解