如果当今的密码分析家想要破解原始的Enigma机器,他们会做到“有多快”或“有多容易”?他们将使用什么方法?假设没有发生此类操作员错误。

评论

问题是否还假设按照Kerckhoffs的原理,密码分析员可以使用Enigma机器(所有版本)的工作原理?

即使攻击者选择了纯文本格式,AES也被认为是(IND-CPA)安全的文件,那么为什么还要包含没有操作员错误的限制?

@vsz,这些错误是有帮助的,但是请记住,该机制是作为商业产品出售的,因此Enigma的“方式”是公开记录的问题。最初的第二次世界大战军事机器是从商业产品衍生而来的,而最初的解决方案原则上是在战前由两名波兰情报人员制定的。 e-sushi的所有评论都非常正确,但是我会再进一步​​拉一下。大卫·卡恩(David Kahn)的书“ The Codebreakers”,尤其是他后来的“ Seizing The Enigma”,涉及了历史解决方案的细节。知道实际情况如何

答案很大程度上取决于什么才算是“操作员错误”,以及在多大程度上已知这些错误。假定是什么“原始的Enigma机器”(有多个变体,甚至转子的数量是可变的);以及是否假定转子(和插板,如果有)的接线是已知的。

“破解谜”并不是一个单一的事件。 3种不同的德国军事武器以3种不同的方式使用了机器。破解1并不能从其他2产生可操作的情报。 OP询问在没有操作员错误的情况下,现代加密分析人员如何破解Enigma。而且,隐含地,它不了解机器本身。但是哪个谜呢?什么是“裂纹”?了解一些历史记录可以使问题更集中,并使答案更有用。

#1 楼


他们将使用什么方法?



自第二次世界大战以来,我们知道Enigma机器的安全性被反射器削弱了,从而导致两个问题:


加密和解密之间没有区别,这意味着,如果K↦T,则T↦K。
由于电不能以相同的方式返回,因此无法对自身进行加密。

另外,历史表明Enigma还有另一个安全问题:与Kerckhoffs原则“系统的安全性不应该取决于算法的私密性。

Enigma弄错了,原因是:


Enigma的安全性取决于转子的接线,
接线是算法的一部分,而不是密钥的一部分,
从1920年代到1945年,接线从未改变。

(来源:https://www.infsec.cs.uni-saarland。 de / teaching / SS07 / Proseminar / slides / maurer-Enigma.pdf)

自您今天要问的问题,因此,我假设我们知道第二次世界大战以来Enigma的内部运作情况。

基于您的假设和已知的Enigma弱点,这是众所周知的攻击之一破解Enigma的方法是使用一致性指数(简称:IC),这是一种文本的统计量度,它可以将用替代密码加密的文本与纯文本区分开来。

将Enigma放入公式中:$ IC = \ frac {{\ textstyle \ sum_ {i = 0} ^ {25}} f_i(f_i-1)} {n(n-1)} $其中$ x_1,...,x_n $是字母字符串, $ f_0,...,f_ {25} $该字符串中字母的频率。对于一个可以简化为$ IC≈0.038 $的随机字符串,对于一个自然语言$ IC≈0.065 $。

我将跳过一些细节,只给您一些原始数字,同时总结一下IC的方式可以用于对Enigma的攻击:



查找转子订单
尝试所有转子订单和位置以寻找最高的IC花费$ 60 * 26 ^ 3≈2 ^ {20} $操作。

转子起始位置的近似值
从步骤$ 1 $和$ w $的转子顺序开始,仅尝试第一环的所有转子位置和环位置,再次搜索最高IC。这需要$ 26 ^ 4≈2 ^ {19} $的运算。

找到环和转子的起始位置
我们有第一环和转子的起始位置,近似值
环和从1和2开始的位置。首先搜索第二个环和转子的位置,然后对剩余的最后一个转子使用相同的步骤。这将需要$ 26 ^ 2≈2 ^ 9 $操作。

查找插头设置
我们有转子的顺序,位置和环位置。现在,我们可以再次将IC用作统计测试,从而获得基础语言的三字母组合信息。



他们能做到多快/多么容易?


通常,如果没有关于攻击者可能拥有的可用资源的任何特定信息,这很难说。

一台计算机可能要花一些时间,具体取决于计算机的年限(就CPU能力而言),但是诸如分布式网络之类的事情可能会让您在眨眼间成功攻击Enigma而使您哭泣眼。如果您碰巧想到任何特定的计算设置,则可以采用上述提供的操作数,并且只需进行相关的数学运算即可计算相关的速度。

最后但并非最不重要的-回答您的问题的标题也是如此...


从现代的角度来看,原始的WW2 Enigma机器在密码学上有多安全?


完全不安全。上述弱点为该主张提供了充分的证据。

另一方面,我们无法真正将今天与第二次世界大战期间的情况进行比较。他们使用的机器主要是机械的(例如Bletchley Park Bombe),而我们所使用的计算机具有强大的CPU。第二次世界大战的密码分析家可能会被杀掉,以获取如此具有未来主义意义的“奇妙的机器”,而我们通常用它来做诸如上网冲浪之类的简单事情。谜,您可能想查看国家安全局密码历史中心A. Ray Miller博士的“谜的密码数学”。

上述出版物当然提供了与以下内容有关的更多见解Enigma背后的内部原理和数学知识比通常的NSA“ freebee”资料(PDF)更为局限,它只限于谈论历史而不是密码学。


编辑:最后两个链接是现在离线,似乎已从nsa.gov网站上删除。由于仍可以通过web.archive.org使用,因此链接已在此处更新。

评论


$ \ begingroup $
@vsz在谈论Enigma时,这是一个相当假想的问题,因为我们都知道真正发生了什么,但是我会尽其评论地回答它:假设他们对密码算法还一无所知,并假设我们说到今天,他们将从走频分析和合作的通常路径开始。最终,诸如Enigma的“没有字母不能被自己加密”之类的事情将打开小裂缝,使密码分析师能够了解密码的特征。在Enigma的情况下-借助当今的计算机,这最终将使他们能够破解密码。
$ \ endgroup $
– e-sushi
2014年1月27日15:58

$ \ begingroup $
@frgieu至于布线,甚至密码博物馆都说:“…M3在功能上与Heer和德国空军使用的兼容Enigma I相同。”只有一些制造差异。另外…`M3的接线在下表中给出。 I至V的车轮与Enigma I的车轮相同。UKWB和C也是如此。另外三个车轮(VI,VII和VIII)仅由海军使用。”但是增加3个轮子并没有改变Enigma的接线(就象1-5轮子一样)。
$ \ endgroup $
– e-sushi
16年5月20日在11:16



$ \ begingroup $
@fgrieu加密版本(Enigma 1,Enigma M3“ Kriegsmarine”和Enigma M4“ u-boot”)的接线方式相同,也可以从密码博物馆的接线表中获取,该接线表显示ETW,I,对于所有涉及的版本,II,III,IV和V都相同(也称为“不变”)。浏览时,我注意到cryptomuseum有一个不错的谜之类的家族树,它似乎也证实了布线不变……看着不变的“ 26个触点”等。 (此外:i.imgur.com/ZA4ysQo.jpg)
$ \ endgroup $
– e-sushi
16年5月20日在11:30



$ \ begingroup $
@fgrieu最后但并非最不重要的一点:陆军版和海军版之间唯一明显的区别是,后者的轮子带有字母(A-Z)而不是数字。 (这不是“接线”的变化)实际上,“…该机器向后兼容M3机器。换句话说:M4 UKW +第四个车轮(设置为A)的组合与M3 UKW相同。 …当UKW-B与4轮Beta结合使用时,它等于M3 UKW-B。 UKW-C和伽玛轮也是如此。 ”
$ \ endgroup $
– e-sushi
16年5月20日在11:48



$ \ begingroup $
@Patriot那PDF链接?对我有效,只需尝试一下,它就可以在台式机上使用Chrome和Firefox完美下载,甚至在Android上使用最新的FF时也可以完美下载。也许广告阻止了您?无论如何,这是我刚刚下载的副本…为了您的个人方便;)— dropbox.com/s/zc3gav41is​​nd7gb/maurer-Enigma.pdf?dl=0
$ \ endgroup $
– e-sushi
19年7月8日在13:31



#2 楼

有关“ Enigma Machine的技术细节”的网站,有完整的密钥大小明细。总结一下:


如果包括所有转子组合,则您可能有$ 3 * 10 ^ {114} $个可能的键。但是,这种情况并没有发生(如果操作员不允许重复,则必须将$ \ frac {26!} {26} = 1.5 * 10 ^ {25} $转子放在手边)。
从现有的$ 5 $转子中选择$ 3 $,您有60个组合,每个转子有$ 26 $的位置,前两个转子还具有可设置的前进环,可用于另外26种可能的设置。这给出了$ 60 * 26 ^ 3 * 26 ^ 2 = 712,882,560 $,相当于一个30位密钥。
这没有插板(带有10条电缆)增加了$ 150,738,274,937,250 $的系数,从而产生了一个77位密钥。
如果消息超过$ 17576 $个字符,则密钥将循环回到开头。因此,如果有更长的消息,您会知道在哪里重叠。
然后就是字母永远不会映射到自己的问题。如婴儿床攻击网站所描述的那样,对于已知的明文来说,婴儿床攻击对一系列密文来说,其谜团也较弱。


#3 楼

看起来没有泄漏或错误,Enigma仍然安全。

引用Enigma @ Home项目网站:


Enigma @ Home是BOINC之间的包装和斯特凡·克拉(Stefan Krah)的M4项目。 “ M4项目致力于借助分布式计算打破3条原始的Enigma消息。信号在1942年于北大西洋被截获,并被认为是完整的。”


鉴于战争如何结束,似乎所有加密细节在1945年都已被捕获-尽管德国人可能会销毁一些有关密钥更改的秘密文件。


http://cryptocellar.web.cern.ch/cryptocellar/bgac/GArmy_messages.html

我认为,短消息和真实消息(转子位置未知)将使您有效地进行牢不可破的通信。
但是,在当前的数字时代,使用原始的Enigma并不是一个好主意。

评论


$ \ begingroup $
如果消息足够简短,则任何密码都是“牢不可破的”。
$ \ endgroup $
– Dillinur
15年4月13日在7:04

$ \ begingroup $
从今天的角度来看,您不能称其为“安全”,因为它只能承受仅密文攻击或短消息,很少消息等其他不切实际的假设。
$ \ endgroup $
– tylo
17年2月7日在12:01

$ \ begingroup $
说Enigma仍然安全是一个令人惊讶的评论,不是吗?
$ \ endgroup $
–爱国者
19年7月7日在12:32