Geekly articles weekly

关于GOST的代码，Grasshopper，其SBox和丢失的种子

嗨％用户名％！



我们最近从EuroCrypt 2019大会上回来了，在那里我们遇到了非常聪明的人，同时了解了有关GOST SBox的新的，令人反感的事实。

因此，这是射弹的第二种方法。 更正和补充。

这次将没有难以理解的红蓝色幻灯片，但是将会有ISO委员会的原始文件以及Grasshopper作者的解释。

甚至是最后的挑战！

走吧

第一个教育计划。 在上一篇文章中不是，这次我更正。

选择的纯文本攻击（CPA）


我们从块密码的基本攻击模型开始。

在此模型中，除了加密密钥之外，攻击者了解有关加密系统的所有信息。 他可以创建任何明文，获取相应的密文，并且他的任务是计算密钥，因为 这是唯一的变量。

在这种情况下，分组密码可以视为伪随机替换。 以无法确定它们之间的关系的方式将明文块与密文块匹配的功能。

理想的分组密码可以想象成一张大桌子，其中水平方向上将有所有可能的键，范围从000 ... 000到111 ... 111，垂直方向-所有可能的开放文本也从000 ... 000到111 ... 111 ，并在它们的交点处随机生成的密文将唯一地关联一对“密钥-明文”。 由于它的大小，不可能在现实生活中创建这样的表，因此使用各种块加密算法对其进行仿真。

如果我们可以确定算法选择与明文相对应的密文的“随机性”，那么对分组密码的攻击就可以称为成功。 这种随机性允许在最坏的情况下计算加密密钥。

（非）线性


分组密码中的加密过程可以用一个简单的公式表示
C = M x K
其中C是密文，M是明文，K是加密密钥，x是分组密码。

该公式在视觉上类似于线性方程y = kx + b的学校公式，其图形为直线。

任何一条直线仅需两点即可恢复。 同时， 我们确实不希望在两对明文（密文）中恢复加密密钥。 为此，将特殊层添加到负责非线性的加密算法中。 这些层旨在防止计算明文，密文和密钥之间的关系。

它们的质量对于算法的安全性至关重要。

什么是SBox？


这是相同的非线性层。 对于Grasshopper和其他一些密码，该函数将一个字节唯一地映射到另一个字节。

通常，它是由一个简单的对应表设置的，例如：



因为否则无法描述。 乍看之下。

为什么SBox很重要？


因为它是整个密码中唯一的非线性函数。 没有它，破解密码将很容易，但是非常简单，将其表示为线性方程组。 因此，替代功能备受关注。 甚至还有使用线性SBox破解AES的实践练习。

为什么根本无法创建一个安全的SBox？


问题在于密码学不是一门精确的科学。 唯一可证明强大的加密算法是一次性密码 。 所有其余的都是胆小的尝试，以适应我们可用的知识范围，但知识范围并不那么广。
我们不确定RSA或AES或椭圆曲线是否可以抵抗，但我们知道绝对不可能 。 两者之间只有创造力。

因此，关于各种“魔术常数”的常数偏执和其他观点被算法作者认为是安全的，但无法证明这一点 。

如何创建SBox？


各种SBox变体为256 !，大约为2 1684 。 选择是巨大的，并且经过多年的密码分析，已经开发出SBox应该具有的度量标准和特征，以抵抗当今的已知攻击。 当然，表格的创建者会思考未来几年，并尝试创建即使在5到10年内发明的攻击也可以抵抗的替代品。 但这更多来自魔术和萨满教。

创建SBox有两种根本不同的方法。

首先是随机搜索。 开发人员生成随机表，查看其特征并过滤出不合适的特征。 这一直持续到开发人员对所发现的内容感到满意为止。

在文明世界中，例如，发生以下情况：

  1. 取一些初始值，例如书中的报价或Pi的前几位数
  2. 遍历哈希
  3. 哈希结果用作形成SBox的数据。
  4. 如果SBox不适合，请使用当前的哈希值并返回到步骤2

因此，任何人都可以重现此过程，并确保至少满足伪随机搜索的最低要求。

您知道该国主要对称算法的种子在哪里吗？ 迷路了 ！ 我以为他们没有特别告诉他们，秘密在那儿还是什么，但是EuroCrypt的俄罗斯同事说，在2007年算法开发期间，出于某种原因，没有人认为有必要证明查找表的设计合理，并且从中得出的价值永远存在迷路了 故事是美丽的，只是不要忘记该算法不是在学校休息时而是在FSB的肠道中创建的。

第二种方法是在可用的数学仪器的指导下自己创建SBox。 这就是 AES 的作者所做的，而且他们做得很好。 如果我们比较SBox AES，SM4（中国标准）和Grasshopper（使用与Stribog哈希相同的SBox）的非线性，那么结果将不利于后者
AES非线性（最小值，最大值）=（112.0，112.0）
SM4非线性（最小值，最大值）=（112.0，112.0）
Streebog非线性（最小值，最大值）=（102.0，110.0）
非线性计算代码使用Walsh变换，可在此处获得。

文件


我从ISO获得了两个文档。 首先，草hopper设计师解释了他们如何创建SBox； 另一方面，委员会讨论了他们的论点。



从第一个文档开始，我们对两个引号感兴趣：



和



我希望“ Leo Perrin自己想到了作者随机搜索SBox的想法”这一主题现在已经结束。

从设计师的解释中可以得出以下结论：

  1. 他们确实以伪随机方式（根据安全标准）寻找SBox。
  2. 据称没有任何隐藏结构。

在这个地方，他们彻底搞砸了。

什么是结构？


应用于查找表的结构是描述该表的算法。

该文件提到了AES。 但是AES的替换表最初不是通过随机搜索创建的，而是借助几种数学技术的帮助，这些数学技术使得可以通过几种公式描述非线性层。 顺便说一下，这就是AES的独特性。

相反，如果您随机寻找SBox，则其中不应包含此类结构，而Grasshopper SBox的问题在于算法设计人员的措辞与事实大相径庭。 在上一篇文章中 ，我以TKLog的名义编写了蚱hopper结构本身，这一次让我们讨论一下结构。

柯尔莫哥罗夫的复杂性


这是Leo Perrin在Grasshopper上的最新文章的研究结果。

关于Grasshopper SBox中的结构的文章的主要反对意见是“如果需要，几乎在任何SBox中都可以找到某种结构”。 而且“即使发现Leo发现的结构的可能性微不足道，但是如果存在另一个SBox，那么将存在另一个可能性也很小的SBox。”

可以这样说。 但是 事实证明，有可能得出SBox的某个“结构化程度”，而这并不取决于陷入一个或另一个结构的可能性。

但这取决于生成此SBox所需算法的大小！

这称为Kolmogorov复杂度。

如果您将SBox想象为一个字节字符串，那么在使用随机字符串的情况下，不应有生成该字符串且同时小于该字符串的算法。

对于蚱hopper


因此，SBox的大小为256个字节。 这是Leo Perrin的作者代码的可读版本，它实现了Grasshopper表。 输入端是源字节，输出端是Grasshopper SBox的相应字节。 这种算法的主要条件是禁止使用会欺骗性地减小程序大小的语言或平台结构。 例如，如果在标准库中的某个地方有一个包含一半SBox的常量，那么您将无法使用它。

挑战-编写一个比SBox小的程序。

unsigned char p(unsigned char x){
    unsigned char
        s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
        k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};    
    if(x) {
        unsigned char l=1, a=2;
        while(a!=x) {
            a=(a<<1)^(a>>7)*29;
            l++;
        }
        if (l%17) return 252^k[l%17]^s[l/17];
        else return 252^k[l/17];
    }
    else return 252;
}

, SBox «» , , SBox. 416 , .

, :

p(x){
  unsigned char
      *t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
      a=2,l=0,b=17;
  while(x && (l++,a^x)) a=2*a^a/128*29;
  return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}

196 , 23% SBox. . , :

p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

SBox :

int main() {
   for(int i = 0; i < 256; i++){
       if (i % 16 == 0){
           printf("\n");
       }
    printf("%d, ", (unsigned char)p(i));    
   }
}

, SBox .
153 . — ANSI, 7 , 8. 1071 ~134 . , .

, Cortex-M4 80 ( ).

, 64 .

, ?


, , .

, 4 Sbox, SBox , .

. , « » AES (60 , GolfScript), .

— . , — .


— SBox. , . , .

( ), , 4 , SBox. , — , . 4 , , , . , , , 11 , , . , side project ¯\_(ツ)_/¯.


ISO . . .

, , , SBox . . , , .

Curve25519 Daniel J. Bernstein Tanja Lange, ISO . , , , SBox. . .

, .

, . ISO, , EuroCrypt.

, ( SBox), RFC 7801, .

, SBox, (, ). , , , . V2 .

. , « , ».

, ? , AES - .

, , , , . .

Challenge!


SBox , , . , 256 . . . — , .

— 58 Stax. « » SBox.

.

Source: https://habr.com/ru/post/zh-CN453254/

More articles:


All Articles