A New Criterion for Avoiding the Propagation of Linear Relations Through an Sbox
A New Criterion for Avoiding the Propagation of Linear Relations Through an Sbox
复制标题
DOI：
10.1007/978-3-662-43933-3_30
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
Christina Boura;A. Canteaut
中科院分区：
文献类型：
--
作者：
Christina Boura;A. Canteaut
在几种加密原语中，使用小尺寸的Sbox来提供非线性。经过几次迭代后，理想情况下，基元的所有输出位都以非线性方式依赖于所有输入变量。然而，在某些情况下，如果其他输入比特被固定为适当选择的值，则可能找到以仿射方式依赖于少量输入比特的一些输出比特。例如，这种情况在立方体攻击或像Fuhr提出的针对散列函数Hamsi的攻击中被利用。在这里，我们定义了非线性Sbox的一个新性质-线性，这意味着一个Sbox的分支是仿射在a维子空间的所有陪集上的。这一性质与布尔函数的所谓Maiorana-McFarland结构的推广有关。我们证明了这个概念量化了Sbox传播仿射关系的能力。作为概念的证明，我们利用这一新概念分析并略微改进了Fuhr对Hamsi的攻击，我们表明它的成功很大程度上依赖于所涉及的Sbox的非线性。
In several cryptographic primitives, Sboxes of small size are used to provide nonlinearity. After several iterations, all the output bits of the primitive are ideally supposed to depend in a nonlinear way on all of the input variables. However, in some cases, it is possible to find some output bits that depend in an affine way on a small number of input bits if the other input bits are fixed to a well-chosen value. Such situations are for example exploited in cube attacks or in attacks like the one presented by Fuhr against the hash function Hamsi. Here, we define a new property for nonlinear Sboxes, named-linearity, which means thatcomponents of an Sbox are affine on all cosets of a-dimensional subspace. This property is related to the generalization of the so-called Maiorana-McFarland construction for Boolean functions. We show that this concept quantifies the ability of an Sbox to propagate affine relations. As a proof of concept, we exploit this new notion for analyzing and slightly improving Fuhr’s attack against Hamsi and we show that its success strongly depends on the-linearity of the involved Sbox.