S-box应该具有哪些理想的属性?

我当前的标准选择过程是随机选择它们,并确认它们符合以下条件: >任意两个随机位$ S [a] _b $和$ S [c] _d $相等(对于任何随机$ a $,$ b $,$ c $和$ d $)的概率为50%。 br />任意两个随机位$ S [a] _n $和$ a_n $相等(对于任何随机$ a $和$ n $)的概率为50%。
没有条目存在$ S [a] = a $
没有条目可导致$ S [a] = \ bar {a} $

还有其他重要属性需要应用吗?

编辑我问的原因是,我希望将此S-Box设计与针对此问题讨论的CBC模式密码结合起来。

评论

我的合理性是S [a] = a不提供任何好处,而S [a] =!a将始终保持与输入相同的位“模式”。由于S-box的想法是提供“混乱”(由Shannon定义),因此确保两种情况都不被允许似乎是合理的。但是,我可能不正确。

密码的输出具有雪崩特性,并且看起来是随机的,但是S-box的构造不是随机的。这是不允许任何关联的情况,而不是指定不允许特定的输出。

这似乎是有关s-box的好论文:sans.org/reading_room/whitepapers/vpns / ...

但是,它并不能真正解释他们为什么做出选择。它只是说:“这是S-box,这是我们所做的选择”。我真正在寻找的答案既能说明事实,又能提供做出选择的理由。

让我们继续在聊天中进行讨论

#1 楼

以下有关DES S-Box的信息可能有用(从此处获取):

DES设计标准


使用了12条标准,因此大约1000个可能的S-Box,实施者选择了8个


这些标准是保密的






其中的一些已经众所周知


以下是设计准则:
R1:S-Box的每一行是从0到15的排列
R2:没有S-Box是线性的输入的仿射功能的说明
R3:将一个输入位更改为一个S-box会导致更改至少两个输出位
R4:S(x)和S(x + 001100)必须在至少2位
以下是由于设计准则引起的
R5:对于e和f的任意选择,S(x)[π] S(x + 11ef 00)
R6:选择S盒是为了在任何单个输入保持恒定的情况下最小化任何S盒输出中1和0的数量之间的差异
R7:所选择的S盒需要更多的时间术语比随机选择需要的

对于Rijndael来说,情况有所不同,因为Rijndael中的S-Box必须在数学和密码分析方面满足某些要求

评论


$ \ begingroup $
请您解释一下标准R5和R7吗?并且标准R2是否实质上是“对于x旋转,例如01010010-> 10010100的x,必须不存在S [x]”?
$ \ endgroup $
–多项式
2011年11月24日在6:58

$ \ begingroup $
@多项式:除了旋转以外,还有更多的线性和仿射函数。基本上,R2说(假设在$ \ {0,1 \} $上的平均线性/仿射),没有任何S盒可以写成$ S(x)= a_0 \ oplus a_1x_1 \ oplus \ dotsb \ oplus a_nx_n $,其中$ x_1 \ dotsc x_n $是$ x $的位,而$ a_0 \ dotsc a_n $是任意的位串。
$ \ endgroup $
–伊尔马里(Ilmari Karonen)
2011年11月24日12:16



#2 楼

理想的属性

为简单起见,我在这里略过了一些细节……但是,优质s盒的主要标准是:平衡的分量函数,
其分量函数的非线性度应高,
其分量函数的非零线性组合应平衡,且
高度非线性,
它应该满足SAC(严格的雪崩准则),
它应该具有很高的代数程度。尽管如此,对于“理想的S-Box属性”将具有哪些属性还是有一些共识的。
s-box XOR表中的所有条目均为0或2。
s-box满足MOSAC(又称“最大订单SAC”)。
s-box满足MOBIC(又称“最大订单BIC”)。
行的权重集具有二项分布,均值$ m / 2 $。
所有行对的权重集具有一个平均数为$ m / 2 $的二项式分布。
各列的汉明权重为$ 2 ^ {(n-1)} $。一个理想的世界。

实际上,确保s盒满足所有期望的特性已经很困难,并且努力满足所有“理想”的特性无疑是一个目标,但是您可能无法达到自己的所有“理想”的目标完全满意。特别是当加密不是您的日常工作时,您恰巧拥有大量的研发资源来支持您的工作。

我想这也向您解释了为什么他们称其为“设计” S盒。事实是,您不能只是将一些经过改组的字节值放入2D数组中,并期望S盒创建完成。 S盒是您为其创建密码的一部分。 S盒旨在增加安全性。根据个人密码算法的设计,低质量的S盒可能会折断每个可能使用密码的人的脖子。因此,绝对不要把事情弄糟,“哦,二维值数组对我来说足够随机”。

您必须意识到s盒添加到分组密码中最重要的事情是“非线性”。而且,您可以相信,通过使用当前条件来随机创建一个好的s-box的机会非常小……非常非常小! box不仅是一组随机排列的值(可以是位,单词,整数等),还带有一些相等的位,以使其看起来有些平衡。创建s盒可以看作是数学设计步骤。它涉及使用和检查布尔函数,真值表,汉明权重,函数与所有仿射函数集之间的距离等内容。

简而言之:一个S盒不是您可以在一个下午快速打包的东西,当然也不是您可以“随机”创建或使用您定义的细节创建的东西。原因很简单:整个分组密码取决于该s盒的非线性和其他特征。这样的s盒很少见,而其余的潜在组合要么是线性的,要么完全可以与随机性区分开。正如您可能在这里和那里已经读到的:如果对手可以查明一个或多个区分符,则对手会获得知识,可以将其成功地用于破解密文。使用s-box的密码算法依靠s-box的非线性来保证安全。如果您在不知道自己正在做什么的情况下替换了s-box,则可能会冒着失去心脏的危险而打破曾经安全的密码。

个人建议

请不要简单地创建一个符合您列出的条件的随机S盒并将其放入某种密码算法中。为攻击者打开一个敞开的门的机会太大了,甚至都无法考虑。

文献资料

为确保您正确了解什么是s-盒是什么以及如何创建s盒,我想向您介绍以下论文:



Jennifer Miuling Cheung设计的S盒(2010年)

Serge Mister和Carlisle Adams的实用S-Box设计(1996)

我个人建议我开始阅读“ S-Box的设计”由Cheung撰写,因为这很可能使您更容易掌握整个概念……同时清晰地了解您可能已经知道的知识以及仍需要进行一些研究的东西。毕竟,有数十篇论文处理S-box设计。根据您的个人知识水平,您一定会发现自己正在阅读有关S-box设计和分析某些特定内容的其他论文。

获取图片

如果您想直接学习并快速了解我在说什么,请访问YouTube,网址为“ Mod-01 Lec-17 S-Box设计原则概述”,其中Mukhopadhyay教授(IIT计算机科学与工程系Kharagpur)对此做了大致解释。即使您无法跟随他,也肯定会给您一个很好的第一印象,即为什么S-box设计比随机改组数组要复杂一些。

评论


$ \ begingroup $
我还没有看到一个满足SAC的s盒,目标是最大程度地减少与SAC负向的距离,并最大化严格雪崩表中达到或超过$ 2 ^ {n- 1} $
$ \ endgroup $
– Richie车架
2014年9月2日,下午3:45

$ \ begingroup $
@RichieFrame:老实说,您还没有看过它们就不足为奇了(例如:DES和AES S盒不满足SAC)。但是,尽管如此,我认为我们在这里谈论的是同一件事。看,我从未说过可以达到所有标准的最大效果。众所周知,我们无法获得想要的所有优良性能。实际上,我们必须决定哪些属性更重要。 (正如D.W.在他的回答中正确指出的:这取决于应用程序。)但这并不会更改所需属性的列表。
$ \ endgroup $
– e-sushi
2014年9月2日15:29



$ \ begingroup $
“组件功能”是什么意思?
$ \ endgroup $
– Melab
18年1月19日,2:12

$ \ begingroup $
@Melab组件函数是S盒坐标函数的线性组合(具有非全零系数)。它们的集合是由坐标函数跨越的向量空间,如果坐标函数是F2线性独立的,则剥夺null函数。若要进一步阅读,请使用您喜欢的搜索引擎并查找“ s-box组件功能”。
$ \ endgroup $
– e-sushi
18年1月19日在5:05



#3 楼

答案是:取决于。

取决于您打算如何使用S-box。大概您将在某种分组密码中使用S-box。在这种情况下,您必须查看S-box所需的属性,然后相应地生成S-box。

您无法将S-box的设计与其余密码的设计。没有通用的标准可以构成一个好的S-box。例如,AES对于他们的S盒有一套标准。 DES的标准完全不同。

#4 楼

合格的S-Box的标准
**•平衡的组件函数

•组件的非线性
函数高

•非零线性组合平衡的组件函数和
高度非线性

•满足SAC

•高代数****

希望对您有帮助

评论


$ \ begingroup $
如果您不提供任何支持您主张的信息,我认为这没有帮助。
$ \ endgroup $
– Miracle173
16年7月20日在10:19

$ \ begingroup $
该列表不仅缺少任何逻辑推理,而且关键字也过于具体,无法添加任何新信息。考虑到已经有写得很好的答案,并且这是问题的第三次复兴(请参阅回答日期),在问题五年后,这似乎毫无意义。
$ \ endgroup $
– tylo
16年7月21日在13:38

#5 楼

我想补充一点,当直接在输入上使用S盒时(例如在替换置换网络中),S盒的另一个重要特性是可以抵抗差分密码分析。差分密码分析取决于以下事实:两个选定输入(I0I1)之间的某个差分特性会传播为两个输出之间的差分特性。在这里可以看到一个精彩的演示和易于理解的解释,其中生成了有缺陷的S盒来演示这一事实。好的S-box很少,例如,对4位S-box都进行了加密,只发现了16个最优的S-box(其中有几个最优的),这意味着在可能的16!中(大约。2^44.2)仅找到2^4个可接受的代码。