Design and Analysis of Cryptographic Pseudorandom Number/Sequence Generators with Applications in RFID
Abstract
This thesis is concerned with the design and analysis of strong de Bruijn sequences and span n sequences, and nonlinear feedback shift register (NLFSR) based pseudorandom number generators for radio frequency identification (RFID) tags. We study the generation of span n sequences using structured searching in which an NLFSR with a class of feedback functions is employed to find span n sequences. Some properties of the recurrence relation for the structured search are discovered. We use five classes of functions in this structured search, and present the number of span n sequences for 6 <= n <= 20. The linear span of a new span n sequence lies between nearoptimal and optimal. According to our empirical studies, a span n sequence can be found in the structured search with a better probability of success. Newly found span n sequences can be used in the composited construction and in designing lightweight pseudorandom number generators.
We first refine the composited construction based on a span n sequence for generating long de Bruijn sequences. A de Bruijn sequence produced by the composited construction is referred to as a composited de Bruijn sequence. The linear complexity of a composited de Bruijn sequence is determined. We analyze the feedback function of the composited construction from an approximation point of view for producing strong de Bruijn sequences. The cycle structure of an approximated feedback function and the linear complexity of a sequence produced by an approximated feedback function are determined. A few examples of strong de Bruijn sequences with the implementation issues of the feedback functions of an (n+16)stage NLFSR are presented.
We propose a new lightweight pseudorandom number generator family, named Warbler family based on NLFSRs for smart devices. Warbler family is comprised of a combination of modified de Bruijn blocks (CMDB) and a nonlinear feedback WelchGong (WG) generator. We derive the randomness properties such as period and linear complexity of an output sequence produced by the Warbler family. Two instances, WarblerI and WarblerII, of the Warbler family are proposed for passive RFID tags. The CMDBs of both WarblerI and WarblerII contain span n sequences that are produced by the structured search. We analyze the security properties of WarblerI and WarblerII by considering the statistical tests and several cryptanalytic attacks. Hardware implementations of both instances in VHDL show that WarblerI and WarblerII require 46 slices and 58 slices, respectively. WarblerI can be used to generate 16bit random numbers in the tag identification protocol of the EPC Class 1 Generation 2 standard, and WarblerII can be employed as a random number generator in the tag identification as well as an authentication protocol for RFID systems.
Collections
Cite this version of the work
Kalikinkar Mandal
(2013).
Design and Analysis of Cryptographic Pseudorandom Number/Sequence Generators with Applications in RFID. UWSpace.
http://hdl.handle.net/10012/7730
Other formats
Related items
Showing items related by title, author, creator and subject.

Optimizations and Hardware Implementations for Composited de Bruijn Sequence Generators
Yang, Bo (University of Waterloo, 20160121)A binary de Bruijn sequence with period 2^n is a sequence in which every lengthn subsequence occurs exactly once. de Bruijn sequences have randomness properties that make them attractive for pseudorandom number generators. ... 
Lehmer Numbers with at Least 2 Primitive Divisors
Juricevic, Robert (University of Waterloo, 20071024)In 1878, Lucas \cite{lucas} investigated the sequences $(\ell_n)_{n=0}^\infty$ where $$\ell_n=\frac{\alpha^n\beta^n}{\alpha\beta},$$ $\alpha \beta$ and $\alpha+\beta$ are coprime integers, and where $\beta/\alpha$ is ... 
Discriminators of Integer Sequences
Haque, Sajed (University of Waterloo, 20170828)The discriminator of an integer sequence \textbf{s} = $(s(n))_{n \geq 0}$, first introduced by Arnold, Benkoski and McCabe in 1985, is the function $D_s (n)$ that maps the integer $n \geq 1$ to the smallest positive integer ...