我对密码学非常陌生(请客气),但我有一个似乎很愚蠢的问题。

如果一次性密码是完美的密码并且不可能破解,为什么以下算法不是最强的算法之一:

要加密:


使用带有密钥作为种子的伪数字生成器生成随机位数组使用简单的XOR加密生成的位数组

要解密:


伪随机数生成器将生成具有相同种子(密钥)的相同位数组
生成位数组的大小与加密数据的大小相同
使用生成的位数组对加密数据运行XOR

这非常简化,但是您可以想象对于更大的加密如何分解数据为了确保块位数组是随机的,可以从密钥派生每个块的新种子。因此,如果$ f(k)$是伪随机数生成器,b是块号,则可以使用$ f(k + b)$加密每个块。 ($ k $是关键)

可以使用某种哈希算法来生成填充,而不是使用伪随机数生成器。

Ceteris paribus(假设您可以使用等效的强密钥)这不是一个很强的密码方法吗?由于填充区需要是数据的大小,因此它可能在存储上既强大又沉重。因此,在加密和解密期间,您需要生成一个等于数据大小的填充。

该算法是否存在缺陷,或者这种方法不实用且比当前标准慢很多?

评论

显而易见:那不是一次性垫;以流密码这个名称而闻名;如果密钥是秘密的,则不能重用,并且伪随机数生成器是加密安全的,它可以确保消息的机密性(不是安全性)。

术语说明:OTP是填充,流密码的等效项是密钥流。

#1 楼

这是一个好问题。正如pg1989所说,这是流密码的基础,流密码在实践中非常快。

我认为我会很快就您的观点进行扩展:“一次性密码是完美的密码,不可能破解。”从某种意义上说,这是事实,但值得指出的是,有时攻击者想要做的事情比“破解”加密方案更简单,以便恢复所有明文。例如,攻击者可能只是想更改消息,以便诚实的收件人解密其他内容。举一个简单的例子,假设攻击者肯定知道该消息是“是”或“否!”。并且只想将消息更改为其他值。请注意:


对于使用一次性密码加密的邮件,此操作很简单。链接的Wikipedia页面描述了为什么这样做是正确的,但是亲自找出它可能会更有趣。
攻击者无需学习明文就可以做到这一点。因此,原先认为一次性垫子不可破裂的说法仍然成立。

一次性垫子的构造也存在其他一些问题,例如通常需要某些状态的事实。确保您在下一次加密过程中不会重复使用种子。因此,尽管您的问题绝对不是愚蠢的,并且流密码在某些情况下非常有用,但它们也有其局限性。

评论


$ \ begingroup $
很棒的答案。谢谢。但是,如果两方之间的密钥绝对是秘密的,那么攻击者如何更改消息? Wiki文章涉及RSA加密,其中除私钥外还存在一个共享的公钥。我可能会丢失连接。
$ \ endgroup $
–dardawk
2013年9月19日下午13:27

$ \ begingroup $
One Time Pads无法提供数据完整性。因此,攻击者可以更改消息,而接收方将不会知道数据已更改。攻击者无法恢复纯文本,但是他们可以更改密文。 Mayank的是/否就是一个例子。攻击者可以看到“是”或“否”的密文,并且可以更改此密文,以便在接收方解密时更改纯文本。我从pg1989推荐的课程中学到了这一点。
$ \ endgroup $
–瑞安
2013年9月19日13:41

$ \ begingroup $
嗯,但是如果使用填充板对“是”进行了加密,则攻击者将不知道消息或填充板,因此,如果他们尝试发送其他内容,使用原始填充板解密攻击者的消息肯定会产生垃圾吗?当然,这种方法对纯文本攻击毫无用处,因为用户gen非常容易地推断出该便笺簿。你是这个意思吗?同样,我才刚刚开始学习课程,所以也许我只需要耐心一点。 :)
$ \ endgroup $
–dardawk
2013年9月19日下午14:35

$ \ begingroup $
@dardawk好吧,让我们想象一下,您正在使用接收者和接收者之间共享的一次性填充发送正在加密的单位是/否消息。通过对该位与共享的秘密位进行异或运算,可以确保无论发送什么消息,在线路上侦听的人都不会知道该消息是是还是否。但是,仅通过反转消息位,攻击者就可以为相反的值得出有效的密码。然后他们可以将其发送给收件人,如果您发送“否”,收件人将看到“是”,而如果您发送“是”,则将看到“否”。
$ \ endgroup $
– AJMansfield
2013年9月19日15:03



$ \ begingroup $
设$ m \ in \ left \ {{\ text {yes},\ text {no!}} \ right \} $,$ k $为随机密钥,密文$ c = k \ oplus m $。您希望修改$ c $,以便将其解密为其他可能的明文。令$ x = \ text {yes} \ oplus \ text {no!} $。计算$ c ^ \ prime = c \ oplus x $。这是您的新密文。请注意,如果$ m = \ text {yes} $,则$ c'= k \ oplus \ text {yes} \ oplus \ text {yes} \ oplus \ text {no!} = k \ oplus \ text {no!} $,如果$ m = \ text {no!} $,$ c'= k \ oplus \ text {no!} \ oplus \ text {no!} \ oplus \ text {yes} = k \ oplus \ text {yes } $。
$ \ endgroup $
–斯蒂芬·托瑟(Stephen Touset)
2013年9月19日17:35



#2 楼

是的,这是一种广泛使用的密码结构,称为流密码。有关此加密方案和其他加密方案的更多信息,Coursera的密码学类是一个很好的资源。

#3 楼

恭喜,您刚刚重新发明了流密码。

一次性密码簿的主要优点是密钥空间与消息空间一样大。这意味着任何仅用于密文的攻击都将始终失败,因为所有明文均有效。

这自动意味着,任何减小密钥空间的结构(例如使用PRNG的种子)都会严重削弱密码结构。

除此之外,一次性密码(以及基于XOR的流密码)非常容易受到重复密钥攻击,而其他密码则(更)安全地对其进行保护。
/>

#4 楼

如果使用密码安全的随机数生成器,则结果是流密码。如果使用实际的随机数,那么它是一次性的。

从随机源获得的任何输出都必须以2:1的比例(无论是2位, 1位)。

别忘了提供带有密文的MAC,以防止攻击者更改消息。

如果要使用CSPRNG,请不要仅使用一种算法。强大的攻击者有可能从中确定模式。生成几个单独的密钥,每个密钥具有512位+长度的质量随机性。然后,使用不同的算法为每个密钥生成单独的密钥流。然后,可以通过XOR将流组合/混合在一起。

即使在网络出现故障时,也不要忘记需要一种与其他人保持同步的方式,因此您不必重用部分流/垫。

#5 楼

根据您对问题的了解,您正在描述流密码。


如果一次性密码是完美的密码并且不可能破解,为什么以下算法不是最强大的算法之一?


您的路线正确;一次性填充本质上是完美的(牢不可破的)流密码。

不涉及(任何)数学细节,平均流密码和一次性密码(OTP)之间的主要区别在于,理想的OTP至少需要与明文一样长的随机密钥,而您的平均流密码只要求N的密钥长度,而不管明文大小。 (假设这两种情况的密钥都是完全随机的。)

在理想的宇宙中,您的流密码将使用短密钥大小来得出一个不可猜测,不可预测,完全随机的长度,其长度等于纯文本和XOR两者一起。

但是,这样做的目的是什么?如果密码的最终结果不是确定性的,那么仅给定密钥就无法恢复原始消息。

那么我们需要的是确定性数学函数,我们可以在其中创建长整数。给定特定输入(键)的预定数字字符串,否则(非常)不可能在没有键的情况下被猜出。

我们的系统安全性现在是由我们的键大小中的弱者定义的,或我们数学函数中的缺陷。

评论


$ \ begingroup $
对。我所说的伪随机数生成器是确定性f'n,它将输出密钥唯一的长字符串。我使用伪随机数生成器只是因为它在我脑海中是新鲜的。感谢您的回答!
$ \ endgroup $
–dardawk
2013年9月19日下午13:31

#6 楼

我也想多谈一点-为什么您不想这样做。用类似于从国会大厦向外交使馆发送秘密消息的类比,它是一种很棒且安全的,有点“万无一失”的加密方法-但实际使用有一些缺点:


您将需要与传输一样多的随机数据(即“密码本”)。如果您发送的邮件足够多且大小足够,则说明您已经耗尽了随机池。您无法重复使用相同的随机数(“代码”),否则将不安全。
您现在需要一种安全可靠的方式来移交密码本。如果有任何窃听者,您将无法执行此操作。这意味着您不仅可以将密钥通过电子邮件发送给某人,还需要像将其戴在手腕上且带有防篡改(或防篡改)印章的带锁公文包一样进行运输。
您当地的使馆有密码簿。因此,使馆内部的间谍有可能利用它伪造给大使馆的信息,假装它来自国会大厦。 (即,它是一个对称密码,可以双向使用密码本。)因此,当您的随机数据池用完时,您需要发送一个新的附件,并且无法使用

使用其他方法,可以以明文形式发送公钥-如果窃听者要接收它,这将对他们没有多大帮助,并且没有“池”

尽管如此尴尬和严格,但我仍然相信,在高安全性应用程序中,它可以提供最强的加密。

评论


$ \ begingroup $
,布拉德,这就是为什么我提到伪随机数生成器(我应该将其称为确定性f'n,它基于短得多的输入键生成一个长而唯一的字符串-pad)。密钥仍然需要商定,“间谍”可以像使用任何(非RSA \公钥)密码一样获得密钥。当然,我想知道您的观点是,一次性键盘如果要重用该键将无用。我只是想将这种简单的算法与其他私钥密码进行比较:AES,蛇,Twofish等。
$ \ endgroup $
–dardawk
2013年9月19日下午14:41

$ \ begingroup $
啊,是的-我同意有关“重塑流密码”的评论;-)最大的要点是(我想说,但我认为它可能太明显了)是“安全性仅在于就像“密码本”数据不可破解的随机性一样。
$ \ endgroup $
–布拉德
2013年9月20日15:09

$ \ begingroup $
政府和外交官还可以选择使用外交邮袋将物品转移到其在另一个国家的使馆。根据《维也纳外交关系公约》,这些人享有免于搜查或扣押的外交豁免权。因此,它并不像您确定的那样困难。但是,可能仍需要使用防篡改(或防篡改)密封件将其戴在手腕上的带锁手提箱。显然,当您用完随机数据时就不会出现恐慌。您将有一个程序可以提前提醒您。
$ \ endgroup $
– NDF1
2015年1月14日在10:25



#7 楼

这确实是一个好问题;让我尝试使其更加精确。假设:


Alice有一些位数的纯文本消息,称为p。
Alice和Bob共享一个加密强度随机数生成器,该生成器生成n个真正的随机比特。
Alice和Bob共享一个伪随机数生成器,该伪随机数生成器可以获取大小为n的种子,并生成2n个p位序列之一。
Alice和Bob拥有不安全的信道和安全的信道。 br /> Alice(或Bob)创建一个大小为n的真正随机密钥KEY,并将其通过安全通道发送给Bob(或Alice)。
Alice创建一个大小为p的伪随机序列SEQ,并将其与纯文本进行异或以生成大小为p的密文。
Alice通过不安全的通道将密文发送给Bob。
Bob解密了
系统的细节不是关键。也就是说,应该假定攻击者确切了解PRNG的工作原理。

好吧,首先,显而易见的批评是:如果Alice和Bob拥有安全的渠道,那么他们为什么要搞砸了?加密吗?答案是:安全通道可能更昂贵,或者仅在不方便的时间提供。

第二个明显的批评是:如果爱丽丝和鲍勃拥有一个可以生成n个真正随机位的设备,那为什么不首先使用它来生成p个真正随机位并获得伪随机性呢?图片中的数字生成器?答案是:因为在安全通道上发送p位可能太昂贵了。

那么该系统可能受到哪些攻击?

公认的答案指出,该系统只能防御一次攻击,即,它使Eve很难解密所截取的密文。它没有为Bob提供任何机制来验证接收到的密文实际上是由Alice产生的。如果该密文的位被翻转,它们也将以明文被翻转,而鲍勃也无从得知。

另一种攻击是:假设n是一个相对较小的数字,例如32。这意味着KEY仅有40亿个可能值,因此只有那么多伪随机位序列SEQ。夏娃可以获得密文,只需尝试所有密文,直到其中一个将其解密为明智的密码即可。这意味着n最好相当大;足够大,以至于无法进行这种暴力攻击。 (当然,如果n必须很大以防止这种攻击,以至于它占p的很大一部分,那么再次将PRGN移出图片,并生成与明文中的位一样多的真正随机位。)

另一种攻击是:假设攻击者设法轻松地获取整个密文,并且设法获取或猜测了明文的k位。这并不像您想象的那么难。许多消息中都有共同的模式。 (第二次世界大战时代的同盟密码破解者通过假设很大一部分消息以对Führer的问候结束而取得了良好的进步;它们是正确的。)如果已知明文的k位和所有密文,则SEQ的k位为众所周知。现在的问题是:在给定SEQ的k位和PRNG的内部知识的情况下,攻击者能否对KEY的值做出很好的猜测?如果他们可以的话,那么生成SEQ的任务对攻击者来说将变得容易得多。 PRNG最好经过精心设计,以使这种密钥恢复不可行。

#8 楼

您将需要生成与数据大小和速率相同的随机数。真正的随机性可以治愈,您不应该重复使用它们。量子RNG可能是解决方案。

评论


$ \ begingroup $
接收者将如何解密数据呢? (不是我的不赞成。)
$ \ endgroup $
–用户
2013年9月19日9:31



$ \ begingroup $
@MichaelKjörling通过单独的渠道获得一次性垫的副本。这是一次性垫的问题:从某种理论上讲,它们最终是安全的,但不切实际。
$ \ endgroup $
–吉尔斯'所以-不再是邪恶的'
2013年9月19日上午11:53

$ \ begingroup $
@Gilles正是。如果您具有安全的通道来传输OTP,为什么不首先使用该通道来传输消息?另一方面,如果第二个通道不比第一个通道更安全,那么从机密性的角度来看,您没有解决任何问题-任何可以窃听一个通道的人也可以窃听另一个通道。它可能给花园变种攻击者带来一个问题,但对确定的对手却不是一个问题,并且为了保护自己免受花园变种攻击者的侵害,合理的AES-256模式已绰绰有余,仅需要安全分配32个字节的密钥即可。
$ \ endgroup $
–用户
2013年9月19日在12:23

$ \ begingroup $
@Gilles我确实在某个地方(可能是IT安全部门)评论说,OTP现在可以在您拥有安全通道的地方使用,但稍后需要传输可证明的安全消息。但是即使那样,您仍然至少有在需要之前存放垫子的问题。
$ \ endgroup $
–用户
2013年9月19日在12:24

$ \ begingroup $
@MichaelKjörling该频道可能很安全,但延迟较高。例如,考虑一个需要信任的快递员,他需要几个小时才能环游世界。或一些同谋者亲自会面以进行密钥设置,然后再交换加密的消息。一次性键盘可让您将消息交换的时间与拥有可信通道的时间分开。
$ \ endgroup $
– CodesInChaos
2013年9月19日15:52

#9 楼

我也不是专家,但是我认为一个明显的缺陷是,如果您使用带有已知常量的众所周知的PRNG算法,那么攻击者就有可能猜测伪随机数流。 />
我使用的方法与您描述的方法类似,但是我有4个PRNG,每个都有我自己选择的“非标准”常量。我生成伪随机密钥流,如下所示:


使用PRNG#4为PRNG#1生成随机种子#1,然后使用它生成密钥流1,同样长度为明文。
使用PRNG#4为PRNG#2生成一个随机种子#2,然后使用它生成与明文长度相同的密钥流2。
使用PRNG#4 generate PRNG#3的随机种子#3,然后使用它来生成密钥流3,其长度与明文相同。
XOR密钥流1、2和3一起创建最终的密钥流,即与明文进行XOR,以创建密文。将种子1,种子2和种子3附加到密文中,以通过完全相同的过程进行解密。

如果每个PRNG可以在重复之前生成(例如)64000个PRN,则将有64000 * 64000 * 64000 = 260000000000000个不同的最终密钥流。这将有助于确保任何特定的最终密钥流都很少被重用。我测试了3亿次加密的算法,没有重复任何最终的密钥流。因为我知道我每年执行的数字加密(大约一百万次),所以我有信心在300年之内不会重复使用最终的密钥流-远远超出了系统或其数据的生命周期。而且由于我选择了自己的PRNG常量,因此攻击者很难猜测它们。这里要说明的重要一点是,如果您决定选择自己的PRNG常量,则需要对生成的PRN流的随机性进行一些合理性检查-错误选择的常量可能导致完全可预测的“ PRN流”。我的系统取决于加密算法和实现代码的安全性和私密性,并且只有公开显示密文​​(是这种情况)。

通常的警告在这里适用...除非有很多理论上可用的加密算法可用,否则您需要设计自己的理由,除非只是为了好玩。

评论


$ \ begingroup $
1)任何体面的流密码只会在超过2 ^ 60个输出字节后重复,因此此限制与实际无关。2)不同流的数量和一个流的长度无关。典型的流密码将具有至少2 ^ 128个不同的流。 3)使用好的流密码比组合多个密码更为重要。自己修改常数的理由很少,只需选择一个随机密钥和IV作为种子即可。
$ \ endgroup $
– CodesInChaos
2014年1月29日上午10:19

$ \ begingroup $
我缺少什么吗?在第4步中,您将种子附加到密文中,并且显然以明文形式发送它们。为何攻击者无法使用这些种子来解密邮件?如果答案是“因为攻击者不知道密钥流中的'非标准'常量”,那意味着这些非标准常量实际上是该系统的密钥;使用固定在系统中的钥匙至少会带来非常可疑的安全性。
$ \ endgroup $
–雨披
2014年7月28日在17:29

$ \ begingroup $
要猜测用于加密明文的PRN流,攻击者需要猜测:-(a)我使用的PRNG算法,以及(b)我插入该算法的确切“非标准”常量。诚然,我生成的PRN流绝对不是严格的密码安全性,但是我认为它的安全性足以满足我的目的。如果我犯了一个错误并且有人犯了错,那么我将不得不承担责任。
$ \ endgroup $
–马克·泰勒(Mark Taylor)
2014年7月28日在17:33



$ \ begingroup $
PS ..如果有人认为自己可以打破它,我将非常有兴趣知道。
$ \ endgroup $
–马克·泰勒(Mark Taylor)
2014年7月28日在17:41



$ \ begingroup $
@MarkTaylor关于您…攻击者需要猜测:-(a)我使用的PRNG算法,以及(b)我插入该算法的确切“非标准”常量...以及您的“如果有人认为”可以打破它,我很想知道。 –也许您还不知道,但是密码学家采用了Kerckhoff的原理。其他所有内容都是“默默无闻的安全性”,而不是加密技术。在密码术中,假定完整的算法被攻击者/敌人/夏娃知道,并且只有密钥代表未知秘密。
$ \ endgroup $
– e-sushi
2014年7月28日在18:51