CSPRNG和PRNG有什么区别?

它们之间是否存在性能差异?例如:我们使用PRNG生成密钥非常昂贵,而使用CSPRNG进行IV / nonce则使用快速分组密码?

两种RNG有什么区别?

评论

由于CSPRNG也是PRNG,因此,如果您选择的CSPRNG比选择的PRNG快,那么您最好将两者交换并使用CSPRNG(您几乎肯定应该这么做)

你做了什么研究?毕竟,Wikipedia的“加密安全的伪随机数生成器”和“伪随机数生成器”已经对两者之间的区别提供了很好的了解。

PRNG涵盖了所有伪随机数生成器,从适用于模拟的c语言中的rand调用,而不是适合于安全性的模拟(如mersenne twister),到最安全的加密PRNG。 CSPRNG仅是安全的PRNG的子集。每个流密码,包括AES-CTR都可以充当CSPRNG。根据上下文,可能还会在范围中包含适当的种子,这比实际数据生成要复杂得多。

@cpast,我认为该问题(或那里的答案)不会帮助人们解决我打算解决的问题。例如,想想一个典型的读者,他看到了一些很棒的统计PRNG(例如Mersenne twister),并且想,我敢打赌我可以将其用于加密!我认为那里的答案不会帮助他们理解为什么这是一个坏主意,而且我认为那里的问题对他们来说没有意义。这里的问题也有点困惑/不清楚(PRNG用于生成密钥吗?不,我们为此使用CSPRNG)。我认为这是一个更好的表述。

虽然我了解您的一般动机,但我必须同意@cpast的评论。您的问题确实可以归结为一个已有的已有一年历史的问题的重新表述。 Thomas Pornin提供的答案突出了这一点,它完美地解释了统计PRNG和密码PRNG之间的区别。从我的角度来看,这几乎使您的“配方”论点无效。

#1 楼

“ PRNG”表示“伪随机数生成器”,它表示数字(位,字节...)序列是由看起来随机但实际上是确定性的算法生成的(该序列是从某种未知的内部状态生成的),因此是伪随机。

这种伪随机可以通过密码保护安全性,也可以不加密。即使PRNG算法是众所周知的(但不是内部状态),也没有人能够可靠地将输出与真正的随机性区分开来,这在密码上是安全的。非加密安全的PRNG会使基本的统计测试变得愚蠢,但可以被聪明的攻击者与真正的随机性区分开。例如,考虑以下生成器:


内部状态s为20个字节的序列。
生成器按20个字节的块生成一个长字节序列。
要生成下一个块,算法为:输出s,然后将s设置为SHA-1(s)。查看第二个是否是SHA-1相对于第一个的结果。这不是加密安全的PRNG。

当然,每个CSPRNG都是PRNG,但并非每个PRNG都是CSPRNG。某些非CS PRNG(例如梅森扭曲器)可以实现很高的性能,并且在没有智能攻击者无法击败的非加密情况下(例如物理模拟)就足够了。尽管也存在一些已知的高性能CSPRNG(例如,这些流密码),但是在没有加密安全性不是问题的情况下,非CS PRNG可能会占优势。

评论


$ \ begingroup $
那么对于CSPRNG,我们仅使用流密码来处理种子?这个种子从哪里来? PRNG? (我的问题更多是关于实现的,为了安全性我们必须在代码中做什么?我的意思是问一个库给我们一个健壮的RN以CSPRNG处理它的最佳安全方法是什么?)
$ \ endgroup $
–随机性
2013年12月18日20:33



$ \ begingroup $
不幸的是,我们实际上有两个独立的问题,它们建议将您琐碎的示例作为安全流密码。一个基于SHA-256哈希函数的简单分组密码,从加密哈希函数构建流密码是否可行?
$ \ endgroup $
– CodesInChaos
13年12月18日在20:45

$ \ begingroup $
只是问如何播种CSPRNG?密码无法生成随机统计信息,因此我们必须首先生成一个种子,该种子来自何处以及我们如何命名?
$ \ endgroup $
–随机性
2013年12月18日20:54



$ \ begingroup $
CSPRNG的初始种子必须来自“攻击者无法得知”的东西。通常,这是从硬件事件中提取的“真实随机性”。通常,系统会花费发生硬件中断的时间(使用CPU周期计数器降低到十亿分之一秒),将所有这些时间值连接起来,然后进行大量处理。常见操作系统(在Linux上是/ dev / urandom,在Windows上是CryptGenRandom()...)提供的CSPRNG中也会发生类似的情况。
$ \ endgroup $
–托马斯·波宁(Thomas Pornin)
13年12月18日在20:58

#2 楼

PRG定义中的关键要素是PRG应该欺骗的观察者(又名区分符,算法,测试等)。
统计PRG欺骗特定的观察者集合,而密码PRG欺骗所有观察者。高效的观察者。
这个强大的定义对于密码学至关重要::
设计者对对手的唯一假设是其计算能力,而不是其策略。
相反,如果使用如果使用密码术中的统计PRG,您可能会遇到一个聪明的攻击者,他们采用了未预料到的新策略,而该策略不在统计PRG应该欺骗的特定策略集中,从而使该方案不安全。如果统计测试抵御了(例如)$ 5 $年的攻击,则仅表示攻击者尚未弄清这一点。但是你永远不知道明天!

评论


$ \ begingroup $
那么“战略”是什么意思?
$ \ endgroup $
–起搏器
18年2月17日在20:37

#3 楼

两者之间的主要区别在于,用于加密目的的随机数生成器必须承受攻击者的攻击。<​​br />
在统计中使用随机数时,您主要关心的是输出顺序“看起来随机”。实际上,这意味着它通过了一堆统计测试,表明它产生的数字分布是您对真正随机数的期望。您在统计中所关心的只是从生成器获得的序列,以及它是否像随机数一样分布。

密码PRNG具有不同的目标:它必须满足所有统计随机性检验PRNG可以,但是也需要不可预测的。 CSPRNG旨在抵抗攻击者预测其下一个输出的企图。即使攻击者知道用于生成随机密码的算法,也很难从真正随机的序列中分辨出来。例如,如果攻击者看到许多调用的结果,那么仍然很难预测任何将来的调用的结果-对于统计数据来说,这不是什么大问题(它引入了一些偏见,但是没什么大不了的) ,但是在密码学中,您经常会精确地使用该随机数生成器,这样没人会知道结果是什么。自然地,这也意味着您需要在某个地方将真正的随机性注入该过程中。

例如:一个具有固定种子的良好PRNG可以很好地进行统计,但是对于加密而言却是非常糟糕的(攻击者是被认为能够学习种子)。

#4 楼



统计PRNG旨在不显示任何统计异常。也就是说,对生成的输出进行统计分析的“对手”应该不会看到与均匀分布的随机源所期望的属性有显着差异。

出于性能原因,大多数统计PRNG基于在输出流中容易识别的简单重复(如果应用了有关算法的特定知识,这就是为什么它不违反统计不可区分性的要求)。在许多情况下,这会同时损害生成器的内部状态,从而有效地使攻击者可以预测将来的任何输出。如果有人想将统计PRNG用作流密码,这就是不这样做的原因。

另一方面,要求使用加密PRNG以避免任何形式的攻击可检测到的规律性,以使其能够使用算法的全部知识进行密码分析。因此,密码安全的PRNG的最重要属性是

不可区分性。将任何概率多项式时间算法应用于(a)用随机种子初始化的PRNG的输出,或(b)来自实际随机源的输出的攻击者,除概率可忽略外,不能区分这两种情况。

一个看似不同的安全概念实际上是等效的,它是不可预测的。给定使用随机种子初始化时生成器产生的伪随机比特序列,使用概率多项式时间算法的攻击者必须无法以不可忽略的大于$ 1/2 $的概率预测下一个比特。

由此可见,与统计PRNG相比,加密PRNG绝不能公开内部状态:否则,攻击者可以仅在泄漏状态下使用生成器(的副本),从而获得下一比特的知识。 (以及所有后续位)具有绝对的确定性。这立即取消了最广泛使用的统计PRNG的资格:线性同余生成器,线性反馈移位寄存器和广义反馈移位寄存器,例如Mersenne扭曲器;所有这些输出的本质上都是内部状态。


它尤其不可预测,它说明了使用加密PRNG的重要性:大多数利用随机性的加密协议都假定攻击者即使他们已经从同一来源观察到先前的(伪)随机值,也无法获得(伪)随机生成的随机数,IV,密钥等的知识。在这种情况下,协议往往会严重破坏。

评论


$ \ begingroup $
关于“任何概率多项式时间算法”;例子?
$ \ endgroup $
–起搏器
18年2月17日在20:41

#5 楼

仅出于简单起见:良好的统计PRNG可以没有显式种子或很小的种子空间(例如16位)。显然,这不足以进行冷冻检查。关键是统计PRNG不需要是不可预测的,加密PRNG则需要它

评论


$ \ begingroup $
实际上,统计PRG是无法预测的,但仅适用于一组区分符。密码PRG对于所有有效的区分符都是不可预测的。
$ \ endgroup $
– Epfoo
15年1月12日在18:15

$ \ begingroup $
@ epsfooling,Re“是不可预测的,但仅适用于一组区分符”;但是需要吗?我以为一旦通过x次统计,就可以确定它的正常,即使它不是不可预测的。
$ \ endgroup $
–起搏器
18年2月17日在20:46

$ \ begingroup $
为了澄清起见,良好的统计PRNG通常使用更长的种子。流行的Mersenne Twister MT19937版本使用32位种子(用于其他生成器)来生成MT的内部19968位种子,该种子由624个32位数字组成。从理论上讲,您可以提供自己的624个32位数字集作为MT19937的种子,而无需执行初始化步骤。
$ \ endgroup $
–火星
19年6月10日15:51