与所有已知的密码分析相比，我们的密码分析技术的效率（包括关键的穷举搜索）是不透露所使用的密码分析技术的理由。我们采用了一种基于零知识的举证方法，该方法始于[11]。
仅鉴于目前所知，这种攻击的含义是什么？它适用于任何类似于SIMON的分组密码，还是适用于大量不同密码的通用技术？
#1 楼
TL; DR：这篇论文似乎是在开玩笑，或者是妄想。该“零知识证明”一无所获。该报告声称已在SIMON-32 / 64（一种小块密码）上找到了一种有效的密码分析方法。确切的细节是故意的，没有透露。但是，为了使读者相信该方法确实存在，在第4节中介绍了所谓的“零知识证明”（顺便说一句，实际上并不是通常所说的零知识）。该证明无能为力，并且具有相同块大小的任何块密码都可以相对实现相同的壮举。
SIMON是一个块密码家族。在这里，我们讨论其中的“最小” SIMON-32 / 64，它具有32位的块和64位的密钥。块大小在这里很重要：这意味着当本文显示64位明文和密文时，它们实际上是成对的明文块和成对的密文块，并以ECB模式加密。
让我们看看第一种“证明”：本文显示了一些密钥，这些密钥将明文“ YHWHYHWH”加密为密文“ YHWHYHWH”（两者均使用ASCII编码）。如上所述，这些实际上是将“ YHWH”（32位明文块）加密为“ YHWH”（32位密文块）的密钥。重复只是分散注意力。如果找到将给定的32位块$ P $加密为给定的32位密文块$ C $的密钥，则当然，相同的密钥会将$ P \ mathbin \ | P $加密为$ C \ mathbin \ | C $和$ P \ mathbin \ | P \ mathbin \ | P $转换为$ C \ mathbin \ | C \ mathbin \ | C $，依此类推。这就是ECB模式的含义。
现在，获取给定的明文块$ P $和给定的密文块$ C $。找到匹配的密钥有多难？如果使用随机密钥$ K $，则用密钥$ K $加密$ P $会生成密文块$ C'$，其大小为32位。因此，具有$ C'= C $的概率约为$ 2 ^ {-32} $。这意味着，如果您尝试使用随机密钥，则平均需要尝试大约$ 2 ^ {32} $个密钥才能找到匹配项。任何体面大小的笔记本电脑都应该能够每秒尝试大约$ 2 ^ {25} $个密钥（我在这里假设加密一个块需要400个时钟周期，CPU运行在3.2 GHz上，并且有四个内核；我们可能可以比使用AVX2扩展功能要好得多，但让我们关注愚蠢的基本软件）。因此，将在大约两分钟内尝试$ 2 ^ {32} $键。换句话说，如果您要求我找到将“ YHWHYHWH”加密为“ YHWHYHWH”的密钥，那么我应该每两分钟找到一个。本文提供的六个键代表一台笔记本电脑的工作时间不到15分钟！所有这些都使用SIMON-32 / 64作为黑匣子，即假设它是完美的理想分组密码。
现在，让我们研究第二个“证明”：作者采取了摘自《英王钦定版圣经》的64位消息的大主体（成对的块）。在原始UTF-8文本中（实际上是ASCII，全部为英语，并且不包含café这个词），这是一个4452069字节的文件。这意味着其中有4452062个8字节的序列。让我们将这个整数舍入到$ 2 ^ {22} $可以使计算更容易。 “证明”是它们显示了将这些块中的一个映射到这些块中的另一个的键；表6显示了18个这样的纯文本/密文/密钥三元组（文章的文本为“ 19”，但表中只有18个）。
采用具有64位块的理想密码（此处我们甚至不使用SIMON-32 / 64使用32位块并且64位消息实际上是32位块对的事实）。取一个随机密钥。将$ 2 ^ {22} $纯文本块之一加密为64位块。输出的64位块是列表中的$ 2 ^ {22} $之一的概率是多少？它是$ 2 ^ {-42} $（因为可能有$ 2 ^ {64} $个64位块和$ 2 ^ {22} $个目标）。这意味着，如果您尝试使用随机键，则平均每$ 2 ^ {42} $个随机键都会有一个匹配项。以每秒2 ^ {25} $的价格，我们每两天谈论一次密钥；那么18个键将花费一个多月的时间。作者声称需要120天，所以这里有些滞后。同样，将分组密码作为理想的黑匣子，基本的野蛮攻击要比密码分析声称的要好。以32位块开头，并且仅在与第一个匹配时对第二个块进行加密；此外，仅当输出块为ASCII时（例如，如果每个字节的最高位为零，因此对于每个密钥，我们最终得到一个SIMON-32 / 64加密，对输出字节的最高位进行测试，仅在1/16情况下查找RAM，以及仅在1/64的情况下在内存中进行了第二次块加密；因此，我们可以很容易地将成本估算为“每次尝试1 SIMON-32 / 64加密”。）
所以不管他们在做什么，似乎都没有比与分组密码的内部结构无关的蛮力更好的东西。是蓄意的恶作剧，是企图损害电子版维护者声誉的歪曲尝试，还是一种自欺欺人的情况。我不会尝试回答这个问题。
评论
$ \ begingroup $
我检查了表5和6中的示例。我无法复制表5。它不是Simon-32 / 64 ECB。
$ \ endgroup $
–未来的安全性
19年5月11日15:32
$ \ begingroup $
本文是一个精心设计的笑话。似乎就像现代密码学家的死亡和指南针一样。看看作者的名字！约翰·马修，詹姆斯·路加和马克？
$ \ endgroup $
–吱吱作响的s骨
19年5月11日在17:41
$ \ begingroup $
此外，他们的名字似乎与大学或学院中的任何人都不匹配。实际上，卢克·门齐斯（Luke Menzis）是一名职业摔跤手。可能需要帮助破坏加密算法:)并且他们在Protonmail上只有一个邮件地址，这是一家瑞士组织，将对其实际身份保密。请注意，其中一些组织要求您发表论文才能访问他们的图书馆（如果您不直接隶属于大学或类似机构）...
$ \ endgroup $
–马腾·博德威斯♦
19年5月11日在18:29
$ \ begingroup $
娃哈哈，我们要感谢奥列格·波波夫先生的贡献。就是这样，我出去了。哦，是的，姓氏是3位“专业”摔跤手的。因此，除了Squamish已经发现的福音传教士以外，我们还有3个摔跤手和世界上最著名的小丑。
$ \ endgroup $
–马腾·博德威斯♦
19年5月11日在18:47
$ \ begingroup $
@kelalaka：不是SCI-GEN；该论文具有比您从计算机生成的论文中所期望的更高的全局连贯性
$ \ endgroup $
–雨披
19年5月11日23:26
#2 楼
除了Thomas Pornin所做的出色的数学分析完全揭露了这种攻击的预期好处之外，似乎在整篇论文中还出现了许多笑话或疏忽，从而清楚地表明这只是恶作剧，而不是专业的研究论文：作者的姓氏是职业摔跤手的名字。
作者的姓氏和中间名是圣经中福音的名称。
他们声称加入名为Alba3的小组，该小组不会出现在任何搜索中。这些都表明它是骗局或模仿纸。在一起，看起来绝对是假货。
评论
$ \ begingroup $
没有明显的证据显示任何一家名为Alba3 Group的公司，但据称有三位合著者，“ Alba”是苏格兰盖尔语（及上古）中苏格兰的名字。
$ \ endgroup $
–吱吱作响的s骨
19年5月12日在2:59
$ \ begingroup $
@SqueamishOssifrage是的，当我第一次阅读本文时，我搜索了Alba3，但找不到任何东西。
$ \ endgroup $
–森林
19年5月12日在3:00
$ \ begingroup $
他们感谢“ Oleg Ivanovich Popov”，这可能是Oleg Ivanovich Yankovsky和Oleg Konstantinovich Popov的组合。
$ \ endgroup $
–纳特
19年5月12日下午4:14
$ \ begingroup $
除了指向一个笑话的答案之外，我还要补充一点，Alba3听起来也有点像信天翁。也许这只是一个巧合。我不知道它的含义是什么。
$ \ endgroup $
– mocenigo
19年5月12日在14:58
$ \ begingroup $
@MartinBonner：说到奇怪的单词选择，在引言的开头还有可疑的“ SIMON et SPECK”，这可能暗示了一位法国作家。 （也许巧合的是，在摘要中被引用为“零知识证明”的论文的作者也是法国人。）但是，当然，这也可能是故意的红色鲱鱼。
$ \ endgroup $
–伊尔马里·卡洛宁
19年5月13日在10:55
评论
@kodlu他们找不到找到选择有效排列的“密钥”的可能性更高的“密钥”。如果给定了实际数量的明文/密文对，那么确定在这种情况下恢复“密钥”是否可行只是一个简单的计算。特别是，有必要找出其中一个键实际上是原始键的可能性。@kodlu：假设Simon-32 / 64的行为就像一个随机排列族，那么存在一个预期的错误密钥，它将两个（P，C）对映射在一起（除了正确的密钥之外）。因此，如果能够找到密钥，则Simon可能具有意外的属性，或者它们确实有很大的可能性找到正确的密钥。
我不知道将代码样本合并到加密中的做法，但实际上我编写了一个程序来产生更多类似于“表6”的C / E / K值。在我的i7上，一分钟的CPU可以产生大约1000个这样的东西。 emergent.unpythonic.net/files/sandbox/search.c-将语料库“ pg10.txt”的副本放在当前目录中并运行它。由于无需破坏SIMON即可轻松生成类似于“表6”的数据，因此无需认真对待其秘密方法。
相关的“ Hacker新闻”主题，提到了此站点，并对该书的出版者进行了更多研究（双关语意）。
该纸张似乎在链接的位置不再可用。但是，可以通过Internet存档访问它。