Linear cryptanalysis of reduced-round SPECK

•A new search method for linear approximations of the SPECK family.•The best known linear approximations of the SPECK family.•The best Linear attack on SPECK96 and SPECK128.•The same round numbers on SPECK96 and SPECK128 as the best key recovery attack.

SPECK is a family of lightweight block ciphers which was proposed by United States National Security Agency and designed for optimal performance in software. The paper gives the security of SPECK against linear cryptanalysis and introduces 9, 10, 12, 15 and 16 rounds linear approximations on SPECK for block sizes of 32, 48, 64, 96 and 128 bits, respectively. Partial linear mask table is used to speed up the search progress rather than the linear mask table. Using the structure of red-black tree to store the pLMT, we deduce the search time. Combining the Segment Searching with branch-and-bound method, the search time is further reduced. For 48-, 96- and 128-bit version the lengths of the linear approximations are 1, 9 and 10 rounds longer than the previous linear cryptanalytic. For SPECK64 the correlation of the linear approximation is twice as much as the previous linear cryptanalytic. As a result, we improve the previous linear cryptanalysis and gain more obvious advantage for block lengths of 96 and 128 bits. Especially, in aspect of SPECK96/144, SPECK128/192 and SPECK128/256 we can attack the same rounds as the best previous attacks.