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 identication (RFID) tags. In particular, the EPC Class 1 Generation 2 (EPC C1 Gen2) standard uses a pseudorandom number generator in the tag identication 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 dierent 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.