Augmented sets of output differences and new distinguishers for SPN ciphers

We introduce augmented vector spaces of output differences, new generic and black-box distinguishers for Substitution Permutation Network (SPN) ciphers. Our distinguishers are based on a novel method of constructing a vector of size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> </mml:math> bits from a given vector of size n bits, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msup><mml:mi>n</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> <mml:mo>=</mml:mo> <mml:msubsup><mml:mo>∑</mml:mo> <mml:mrow><mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn></mml:mrow> <mml:mi>d</mml:mi></mml:msubsup> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr><mml:mtd><mml:mi>n</mml:mi></mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd><mml:mrow><mml:mrow></mml:mrow> <mml:mi>i</mml:mi></mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> and d is a positive integer. We list all such <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> </mml:math> -bit vectors into a set called the corresponding <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>d</mml:mi> <mml:mrow><mml:mi>th</mml:mi></mml:mrow> </mml:msup> </mml:math> -order augmented set and define its linear span as the corresponding <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>d</mml:mi> <mml:mrow><mml:mi>th</mml:mi></mml:mrow> </mml:msup> </mml:math> -order augmented vector space . These sets are related to Reed-Muller codes and we prove that the rank of linear span of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>d</mml:mi> <mml:mrow><mml:mi>th</mml:mi></mml:mrow> </mml:msup> </mml:math> -order augmented set is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:msup> </mml:math> using Reed-Muller codes. We then experimentally estimate the number of n-bit vectors required to span augmented vector spaces of output differences. Following these results, we give a generic and efficient algorithm to compute <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>d</mml:mi> <mml:mrow><mml:mi>th</mml:mi></mml:mrow> </mml:msup> </mml:math> -order augmented vector space (of difference sets) for substitution permutation network ciphers. We apply our algorithm to lightweight ciphers GIFT, PRESENT and SKINNY and provide in-depth comparison of round-reduced ciphers' distinguishers with random sets. Most notably, our new distinguishers for these ciphers cover more rounds than the subspace trails.