1 Introduction

Random Number Generators are an integral part of most cryptographic systems. However, due to inherent periodic characteristics in the world, there are believed to only a few sources of true randomness in the universe. A usual method for generating random numbers in a computing system involves using deterministic algorithms with the resultant numbers satisfying the properties of a true random number generator (TRNG) to a reasonable extent based on certain metrics. These algorithms are referred to as pseudo-random number generators (PRNGs). PRNGs are mainly used to generate secret keys, nonces, and challenges in the cryptography to provide security.

The security of the Electronic Product Code (EPC) Gen2 low-cost RFID System [1] relies primarily on its 16-bit PRNG and password protected operations. The outgoing sequences can be predicted easily if weak PRNGs mechanism is used which may introduce security flaws in EPC Gen2 communications. Such security flaw might allow the attacker to exploit the commands which are password protected in EPC Gen2 standard [2, 3]. Since RFID tags are low resource devices, implementation of resource intensive and complex mechanisms are also not possible. Thus, the proposed PRNG schemes must be secure, lightweight and fulfill randomness criteria required for the security.

Although various PRNG designs have been proposed in the literature for EPC Gen2 tags, the details of a very few have been disclosed. The PRNG designs whose details are available in the literature are not that much secure and have been found vulnerable to attacks.

The main objective of our work is to develop a more secure 16-bit lightweight PRNG for low resource device, mainly for use in the RFID generated EPC Gen2 tags. Our work is inspired by [4, 5] and we try to improve the security of their proposed model by adding more features. Also, to make the proposed PRNG scheme a lightweight, we try to lower the computation cost, which is measured in terms of gate equivalents (GE). Our model also uses a TRNG source like thermal noise to add true randomness.

The major contribution of our paper is two-fold:

  • We propose a more secure PRNG for EPC Gen2 RFID tags using a lightweight sponge function, named JSponge that prevents the cryptanalysis.

  • We implemented our proposal and the enhanced version of J3Gen proposed in [5]. We compared our scheme with the proposal one of [5] against NIST test suites and the EPC Gen2 randomness criteria to demonstrate the effectiveness of our proposed mechanism.

The rest of the paper is arranged as follows. Section 2 describes the related work. In Sect. 3, we discuss the PRNG designs of J3Gen and Proposal one. Section 4 presents our proposed PRNG design, JSpongeGen. In Sect. 5, we discuss the implementation of our design, and the comparative results obtained. We do the security analysis of our proposal in Sect. 6 and finally our work is concluded in Sect. 7.

2 Related Work

As it is shown in Fig. 1, there are two main approaches for random number generation. In the first approach, TRNGs are generated using the physical source such as the thermal noise of diodes. However, this method is not practical and bare a common drawback of the TRNGs. The other approaches are PRNGs, which uses some mathematical techniques such as Linear Feedback Shift Register (LFSR) and Congruential Generator (LCG) to generate the PRNGs inside the RFID tag artificially. However, we found very few good PRNG design proposals for low-resource RFID tags in the literature. In this section, we discuss those proposed PRNG mechanisms for low-cost RFID tags.

Fig. 1.
figure 1

Random number generation in RFID tags

Full size image

In 2007, Lee et al. [6] proposed the self-shrinking generator for RFID, which is an optimized version of the shrinking generator proposed in [7]. The proposed approach combines two clocked LFSRs in which an output sequence of the first LFSR discards some bits from the output sequence of the second LFSR. However, some of the techniques presented in [8] can be used to exploit the scheme.

In 2008, Che et al. [9] proposed another variant of the shrinking generator, which is based on TRNG (physical source: thermal noise) to handle the linearity of an underlying LFSR. However, in [10], the authors have shown that the scheme is vulnerable to attack and the PRNG configuration can be obtained with a confidence of 42 percent eavesdropping 128 bits of pseudorandom data only.

Some of the popular PRNG schemes proposed for low resource devices are Trivium (2005) [11], Grain (2007) [12], LAMED (2009) [13], and AKARI-X (2011) [14]. The manufacturers do not provide the design details of most of these schemes. There are very few PRNG designs whose details are present; however, various studies have raised concern related to their security claim.

J3Gen (2013) [2] and Warbler (2016) [15] are two other popular PRNGs for low resource devices. Although J3Gen fulfills the randomness criteria required by EPC Gen2 standard, the authors [16] questioned its security claims by performing two cryptanalytic attacks. These attacks are a probabilistic attack based on solving linear equation systems and a deterministic attack based on the decimation of the output sequence. In 2017, the authors of [17] claims that the Welch-Gong (WG) nonlinear feedback shift registers based schemes are vulnerable to linear attack, which is also a threat to the security of Warbler PRNGs that uses the same mechanism. In 2017, Nomaguchi et al. [18] proposed a new light-weight PRNG scheme which uses combination of NLFSR and DLFSR to achieve more efficiency and security than the existing approach. Authors have used larger key length and shown that their mechanism is resistant to existing attacks against Warbler and J3Gen.

In [5], an improvement was made on the approach of [4]. Two new proposals are made to solve the J3Gen security issues reported in [16]. One proposal involved replacing the final output logical AND gate with a logical XOR gate because the XOR operation provides less bias to the resultant bit value. The second proposal was inspired from a lightweight stream cipher called KATANTAN. In this work, there are two LFSR units with their output bits being combined using an XOR gate. The output bit value of one LFSR is instead used for increasing internal randomness of the PRNG. For testing the pseudo-randomness, tests from the NIST testing suite and tests for checking EPC Gen2 criteria for randomness were used.

Our work is inspired from [5], and we have tried to further improve the security by introducing additional cryptographic complexity using lightweight Sponge function.

3 Background

In this section, we discuss the two PRNG schemes for EPC Gen2 RFID tags, J3Gen [2], and its improved version, proposal one of [5], which are closely related to our proposal.

3.1 J3Gen

Figure 2 shows the block diagram of the J3Gen. The J3Gen is inspired from a dynamic LFSR (DLFSR) based testing selection scheme of Hellebrand et al. [19]. It uses DLFSR of n cells. The four main components of the J3Gen are as follows:

Fig. 2.
figure 2

Block diagram of J3Gen [2]

Full size image

  • n-cell LFSR: It produces good statistical values for pseudorandom sequences. Its hardware implementation is fast and efficient. Its computational requirements are also quite simple. Thus, it is well suited for the low resource or resource constrained environment (for both computational and energy constrained environments).

  • Thermal-Noise TRNG: The J3Gen technique uses the oscillator-based high-frequency sampler proposed in [9]. The output generated by the TRNG is fed into the Decoding Logic, which in turn, helps in managing the Polynomial Selector.

  • Decoding Logic: This module manages the internal PRNG clock of J3Gen. It activates and deactivates modules such as the LFSR or the TRNG for proper performance. For example, the sampling in the TRNG is activated only once for each PRNG output. It also manages the true random bit (trn) obtained from the TRNG and the corresponding output fed into Polynomial selector helps in rotating the polynomials.

  • Polynomial Selector: This module of J3Gen helps in avoidance of the linearity. A set of m primitive feedback polynomials are used as a wheel, and each one of them is selected depending on the value of trn of TRNG.

3.2 Proposal One by Chen et al.

To develop a more secure 16-bit LFSR-based PRNG Chen et al. [5] proposed a modified version of J3Gen. The authors designed two proposals, proposal one and two. Since our work is an extension of proposal one, we provide the details of this proposal only. Figure 3 depicts the block diagram of the Proposal One. The modifications done in the J3Gen are as follows:

Fig. 3.
figure 3

Block diagram of proposal one by Chen et al. [5]

Full size image

  • TRNG: The authors used the same approach and used the oscillator-based high-frequency sampler by Che et al. [9]. However, the authors suggested that the system works even if TRNG has failed.

  • Feedback Polynomial: In J3Gen, the feedback polynomials are implemented as wheels and rotates according to the r bits received from the decoder logic (shown in Fig. 2). However, in this mechanism, the selection of the multiple polynomials are more random. This approach makes it difficult for the adversary to predict the linear behavior of the random bit generation.

  • Output Computation: The authors replaced the output AND computation of J3Gen with an XOR computation. Since XOR is perfectly balanced if \(r = 1\), the output has less bias and it is independent of the seed bits value. Thus, enhances randomness property.

4 Proposed Method: JSpongeGen

In this section, we introduce our proposed mechanism JSpongeGen. The primary goal of our work is to propose a more secure PRNG than the J3Gen and the proposal of Chen et al. discussed in the previous section. To achieve that we increase cryptographic complexity by adding SPONGE function [20] in the model. Also, for a lightweight PRNG, we try to keep the computation resource cost (measured in terms of gate equivalents(GE)) as low as possible. Thus, the only additional component that we introduce is the SPONGE function. The TRNG in our proposed model is the same used in J3Gen, the oscillator-based high-frequency sampler proposed in [9] (Fig. 4).

Fig. 4.
figure 4

Block diagram of our proposed method: JSpongeGen

Full size image

The basic idea of the proposal is to make the key more strong and secure. In this model, the feedback polynomial used in the LFSR to generate the output is the key which is unknown to the attacker. The key strength should be at least 80 for low resource devices as found in previous works. In [2], the polynomial selector uses 16-degree polynomial functions which are primitive with a 16-bit LFSR and chooses eight random polynomial functions from the domain set. In [5], the domain set is increased for the 16-degree polynomial functions by including non-primitive polynomials, to increase the combinations. In our method, we propose to use polynomials of variable degree ranging from 12 to 16 and increase the domain set many folds. This increases the possible combination of 8 chosen polynomials exponentially making it more than \(2^{80}\) which makes it difficult for an attacker to crack the polynomials.

As discussed in [2], an attacker requires 2n output bits to crack the polynomial and the LFSR state. So if one of the above is already known, then the attacker requires only n output bits to find the other by brute force. To avoid this, we use the polynomial function to generate only L bits at a time by running L iterations of LFSR using that polynomial. As given the n bits generated by the model, L bits of which are generated by one polynomial, there can be \(2^{n-L+1}\) possible polynomials which can generate the remaining \(n-L\) bits in the output. So the attacker can brute force to guess the polynomial function. So the computation of brute force is dependent on the value of L (as computation will be \(2^{n-L+1}\)). We reduce the value of L to increase the uncertainty in cracking the feedback polynomial when the attacker has discovered n output bits. As the degree of the polynomial is variable which is n, thus, for a given n, we keep the value of L as n / 2. We don’t reduce the value of L further to prevent additional time complexity in changing polynomials.

As we discussed above, if the attacker has n bits and the feedback polynomial, then by brute force the state of the LFSR can be found. To prevent this, we change the contents of the LFSR after every L iterations of the model. While we change the polynomial function, we will also set a new value in the LFSR to include to prevent it from attacks. We use a sponge function, inspired from SPONGENT [21], every time we change the polynomial to reinitialize the contents in the shift register. As input to the sponge function, we use the 32-bit concatenation of the current LFSR contents and the bitwise representation of the coefficients of the previous polynomial.

In our sponge function, we use bitrate \(r=2\) and \(c=14\). We use a simple permutation function and simple 4-bit substitution function to transform the sponge state memory at each round of the sponge function.

Here, we present the working principle of the proposed model. The value in the LFSR is initialized to some value, and the polynomial selector chooses \(p_{1}(x)\) as the current polynomial, and the LFSR outputs random bits using the bit output by LFSR XORed with the random bit coming from the true random source. After L iterations of the LFSR, the true random source generates another bit (0 or 1) based on which the polynomial wheel rotates by 1 or 2 respectively to choose the next polynomial and contents of LFSR are changed using the sponge function. Now the LFSR is set with the new value, and another L bits are generated using the LFSR output bit XORed with the true random bit.

5 Experiment and Results

In this section, we present implementation details, our experimental results, and a comparison of our schemes with the proposal one of [5]. Table 1 shows the details of our experiment. We used the Linear Feedback Shift Register implementation given in [22] as our reference.

Table 1. Implementation details
Full size table

We test the working of our proposed PRNG on a desktop personal computer to check if it satisfies the randomness requirements that are expected for a PRNG in an RFID application as per the following standards:

  1. 1.

    NIST Randomness Tests (Minimum Set)

  2. 2.

    EPC Gen2 Randomness criteria

5.1 NIST Randomness Test

For NIST randomness test, we use the Minimum Set of NIST SP800-22 [23] that consists of the following:

  1. a.

    Frequency test

  2. b.

    Block Frequency test

  3. c.

    Linear Complexity Test

  4. d.

    Rank Test

  5. e.

    Cumulative Sums Test.

We took 20 million bits generated by the two generators, i.e., Proposal one and JSpongeGen and considered 100 binary streams of length 20000 each for input to the NIST test suite and compared the results. In the Table 2, the scores are given out of 100, which represents the correct proportion.

Table 2. NIST randomness tests score
Full size table
Table 3. EPC Gen2 randomness criteria 1
Full size table
Table 4. EPC Gen2 randomness criteria 2
Full size table

5.2 EPC Gen2 Randomness Criteria

The EPC Gen2 randomness criteria [1] consists of the following.

  1. a.

    Criteria 1: The probability that any single 16-bit number N drawn from the PRNG shall be bounded by the limits given below:

    \(1.22 e-5< P(N) < 1.9 e-5 \).

    We generate 30 million random numbers using the PRNG to calculate Probability using the frequency definition of it. The results are shown in Table 3 and are for the numbers that appeared at least once.

  2. b.

    Criteria 2: Probability of occurrence of same 16-bit sequence N in any two tags simultaneously shall be less than 0.1\(\%\) for a population of up to ten thousand tags.

    For testing this, 10000 instances of the PRNG are seeded randomly and then each of them generates 500 numbers. The probability is then calculated and listed in Table 4.

  3. c.

    Criteria 3: The probability of finding next 16-bit random number generated by the tag shall be less than 0.025\(\%\), given all previous random numbers generated by PRNG are known to an adversary.

    For satisfying this condition, we consider another metric distance correlation for comparing two PRNGs and present the results in Table 5 for the correlation scores of 10000 16-bit numbers generated by both the PRNGs.

Table 5. EPC Gen2 randomness criteria 3
Full size table

6 Security Analysis

The security of a PRNG lies in the unpredictability of numbers generated in the future given numbers generated in the past. Given that the algorithm is known to the public, the hidden key in our algorithm is the exact combination of m feedback polynomials that are used in the polynomial selection phase.

For a simple PRNG which uses a single polynomial based LFSR of size n and period \(2^{n}-1\), Berlekamp-Massey algorithm [24] can be used to find out the polynomial with only 2n bits of output. This is based on the solution to the system of equations that can be formed due to the consistent use of one polynomial in the feedback phase of the LFSR.

However, for a dynamic feedback shift register based PRNG as in our case, the computational difficulty for an attacker in determining these polynomials depends on both the size of the set from which these polynomials are chosen as well as the polynomial update rate L.

In [5], they have considered taking polynomials other than primitive polynomials but of degree n = 16. We choose polynomials of degree 12 to 16 for increasing the size of the set of the polynomials that can be chosen and hence have a domain size of polynomials D given by:

\(D=(2^{15}-1)+(2^{14}-1)+(2^{13}-1)+(2^{12}-1)+ (2^{11}-1)=63483\)

Choosing 8 polynomials from these can be done in (63483C8) ways i.e. approximately \(2^{120}/2^{16}= 2^{104}\), which is clearly greater than \(2^{80}\).

For RFID-based applications, a key strength of 80 has been found to be sufficient as mentioned in previous works [25] and [26]. Hence the key strength is adequate for the PRNG. We add more difficulties to the attacker’s efforts by re-initializing the LFSR contents during every change in the feedback polynomial. Even if an attacker keeps track of output bits of the LFSR, it will be difficult to predict the new LFSR contents due to the use of a sponge function in the re-initialization stage.

7 Conclusion

We designed a new lightweight PRNG, named JSpongeGen, which is an extension of the existing design. We introduced additional cryptographic features called sponge function, and it is used to change the state of the LFSR. It is a lightweight solution to prevent the cryptanalysis in the case of the polynomial is known. We found through experiments that we do better than proposal one on specific randomness metrics of the NIST test suite, and also in some criteria of the EPC Gen2 standard. Our scheme gives comparable results. We hope that JSpongeGen PRNG may get adapted for low resource devices such as RFID tag-based applications.