Filtering Nonlinear Feedback Shift Registers using Welch-Gong Transformations for Securing RFID Applications

Abstract

Pseudorandom number generators play an important role to provide security and privacy on radio frequency identi cation (RFID) tags. In particular, the EPC Class 1 Generation 2 (EPC C1 Gen2) standard uses a pseudorandom number generator in the tag identi cation protocol. In this paper, we rst present a pseudorandom number generator family, we call it the ltering nonlinear feedback shift register using Welch-Gong (WG) transformations ( ltering WG-NLFSR) and propose an instance of this family for EPC C1 Gen2 RFID tags. We then investigate the periodicity of a sequence generated by the ltering WG-NLFSR by considering the model, named nonlinear feedback shift registers using Welch-Gong (WG) transformations (WG-NLFSR). The periodicity of WG-NLFSR sequences is investigated in two ways. First, we perform the cycle decomposition of WG-NLFSR recurrence relations over different nite elds by computer simulations where the nonlinear recurrence relation is composed of a characteristic polynomial and a WG transformation module. Second, we conduct an empirical study on the period distribution of the sequences generated by the WG-NLFSR. The empirical study shows that a sequence with period bounded below by the square root of the maximum period can be generated by the WG-NLFSR with high probability for any initial state. Furthermore, we study the cycle structure and randomness properties of a composited recurrence relation and its sequences, respectively over nite elds.

Keywords

• Nonlinear feedback shift registers
• pseudorandom sequence generators
• stream ciphers
• WG-7 stream cipher
• RFID