Analyzing Non-linear Shift Register Transformations in the Design and Cryptanalysis of Espresso
摘要
The stream cipher Espresso was proposed by E. Dubrova and M. Hell as a hardware-efficient candidate for providing security in 5G communication. Its design has two components - a 256-bit binary non-linear feedback shift register (NFSR) in the Galois configuration and a 20-variable non-linear output function. However, the security estimates of Espresso with regard to several standard cryptanalytic attacks are actually based on an alternate NFSR, which has less number of feedback taps than the design NFSR. The validity of such an analysis rests on the claim that this alternate NFSR is obtained using a transformation algorithm that preserves the output sequence of the design NFSR. This claimed equivalence of NFSRs, crucial to the security evaluation of Espresso, is yet to be rigorously established. This issue has become all the more significant in the light of recent results comparing the FPGA performance of these two configurations, which assume that the stated equivalence holds. The present article revisits several existing transformation algorithms in the context of settling the question of Espresso NFSR equivalence. First, we identify and correct a critical flaw in the proof of a foundational result for the first transformation algorithm of Dubrova. Next we establish a unified framework for Dubrova’s transformation algorithms and those of Yao and Parampalli, applicable to the class of NFSRs used in Espresso. Based on the above development, we propose an algorithm to obtain a possible equivalent design using the Espresso alternate NFSR from an LFSR-based design reported by Yao and Parampalli.