A new criterion for avoiding the propagation of linear relations through an Sbox

Abstract : 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 $(v,w)$-linearity, which means that $2^w$ components of an Sbox are affine on all cosets of a $v$-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 $(v,w)$-linearity of the involved Sbox.
Type de document :
Communication dans un congrès
Fast Software Encryption - FSE 2013, Mar 2013, Singapore, Singapore. Springer, 8424, pp.585--604, 2014, LNCS
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00931535
Contributeur : Anne Canteaut <>
Soumis le : mercredi 15 janvier 2014 - 14:17:18
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 15 avril 2014 - 22:46:44

Fichier

iacr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00931535, version 1

Collections

Citation

Christina Boura, Anne Canteaut. A new criterion for avoiding the propagation of linear relations through an Sbox. Fast Software Encryption - FSE 2013, Mar 2013, Singapore, Singapore. Springer, 8424, pp.585--604, 2014, LNCS. 〈hal-00931535〉

Partager

Métriques

Consultations de la notice

182

Téléchargements de fichiers

135