SRG | Security Research Group

RFID PRNG

INTRODUCTION

This work presents a pseudo-random number generator for low-cost RFID tags. The scheme is simple and sequential, yet its performance equals similar previous works. With equal performance, our proposal uses less die area and clock cycles, proving more suitable for low-cost tags. The scheme is inspired from the well founded pseudo random number generator, the Mersenne Twister. The proposed generator takes low-entropy seeds extracted from a physical characteristic of the tag and produces output that passes popular randomness tests. On the other hand, previous works’ tests are based on random number inputs used from a popular online source, which are not available to tags. The results of previous work repeated with low-entropy inputs are not satisfactory. The performance and randomness claims of our scheme are supported by extensive test results, accompanied by comparisons with previous works.

Algorithm:

x := TRN input
x:= ROTl(x,x)          
y := x ⊕ ROTr (x,u)
y := y ⊕ (ROTl (y,s) & b)
y := y ⊕ ( ROTl (y,t) & c)
y := y ⊕ ROTr (y,l)
z := y ⊕ROTl (yb, p)
The coefficients are := u = 7, (sb) = (3, 9D2C568016), (tc) = (5, EFC6000016), l = 18, p=7

EPC GEN2 Standards PRNG Results

UHF C1G2 Standard

Our Results

1st test (Probability of a single RN16) for 3051*65536 numbers

Lower 16 bits

Higher 16 bits

XOR

Lower limit

0.926

0.919

0.923

Upper limit

1.073

1.075

1.071

2nd test (Probability of simultaneously identical sequences)

Lower 16 bits

Higher 16 bits

XOR

Our test result

0.04

0.04

0.04

EPC Gen2 Standard

0.1

0.1

0.1

3rd test (Probability of predicting an RN16)

Serial Correlation (16 bit values)

Xor

0.000008

Lower 16 bits

0.000070

Higher 16 bits

0.000021

 

ENT TEST RESULTS

ENT Test Results

Lamed

Akari-1/Akari-2

Ours

Entropy (bits/byte)

7.999999

8.000000 / 8.000000

7.999999

Compression Rate

0%

0% / 0%

0%

X2 Statistics

256.90 (50%)

259.09 (41.70%) / 250.99 (55.93%)

212.60 (97.52%)

Arithmetic Mean

127.5024

127.4976 / 127.5031

127.5002

Monte Carlo Estimation

3.141474228

3.141447036 / 3.141512474

3.141529759

Serial Correlation Coefficient

-0.000023

-0.000026 / 0.000013

0.000009

 

DIEHARD1 RESULTS

Diehard1 Input:

Diehard1 Output:

 

Test

Extra Rotation Added Values

Input

birthday spacings,

1.00

0.00

overlapping permutations,

0.25

0.00

ranks of 31x31 and 32x32 matrices

0.00

0.00

ranks of 6x8 matrices

1.00

0.00

monkey tests on 20-bit Words (bitstream)

0.60

0.00

monkey tests OPSO, OQSO, DNA

0.62

0.00

count the 1's in a stream of bytes

0.50

0.00

count the 1's in specific bytes

0.72

0.00

parking lot

1.00

0.00

minimum distance

1.00

0.00

random spheres

1.00

0.00

squeeze

1.00

0.00

overlapping sums

0.50

0.00

runs

0.75

0.00

craps.

1.00

0.00

SUM

10.94

0.00

 

 

 

DIEHARD2 RESULTS

Diehard2 Input:

Diehard2 Output:

 

NEW DIEHARD2 TEST DETAILS

p-value

Birthday spacings

0.721339

Tough Birthday spacings

0.547000

GCD

0.732103

Gorilla

0.119000

Overlapping Permutations

0.4208, 0.6911, 0.6770, 0.6521, 0.6798

Ranks of 31×31 and 32×32 Matrices

1

Ranks of 6×8 Matrices

0.909593

Monkey tests on 20-bit words

0.51857165 (Average)

Monkey Test OPSO

0.549708522 (Average)

Monkey Test OQSO

0.454735393 (Average)

Monkey Test DNA

0.603586871 (Average)

Count the 1's in a stream of bytes

0.249728

Count the 1's in specific bytes

0.44275264 (Average)

Parking lot test

0.682237

Minimum distance test

0.682303

Random spheres test

0.870077

The squeeze test

0.217116

Overlapping sums test

0.773786

Runs up and down test

0.673000

The craps test

0.785901

Craps Test With Different Dice

0.945402

Overall KS p-value

0.223461

 

DIEHARD2 COMPARISON AMONG AKARI-X, LAMED AND OURS

Test Name

Akari-1A/Akari-1B

Akari-2A/Akari-2B/Akari-2C

Lamed

Ours

Birthday spacings

0.494

0.053

0.261

0.721

GCD and Gorilla

0.524

0.114

0.778*

0.426

Overlapping Permutations

0.597

0.465

0.311*

0.624

Ranks of 31×31 and 32×32 Matrices

0.735

0.739

0.699*

1.000

Ranks of 6×8 Matrices

0.798

0.139

0.521

0.910

Monkey tests on 20-bit words

0.462

0.471

0.312*

0.519

Monkey Test OPSO

0.462

0.387

0.436*

0.550

Monkey Test OQSO

0.448

0.520

0.742*

0.455

Monkey Test DNA

0.510

0.527

0.688*

0.604

Count the 1's in a stream of bytes

0.237

0.107

0.664

0.250

Count the 1's in specific bytes

0.420

0.607

0.586*

0.443

Parking lot

0.233

0.511

0.433

0.682

Minimum distance

0.253

0.121

0.411

0.682

Random spheres

0.713

0.168

0.788

0.870

The squeeze

0.729

0.003

0.841

0.217

Overlapping sums

0.311

0.000

0.173

0.774

Runs up and down

0.368

0.771

0.191

0.673

The craps

0.608

0.046

0.443*

0.786

Overall KS p-value

0.353

0.082

0.778

0.224

 

 

Comparison of Diehard tests

Scheme

Diehard1 Score

Diehard2 Score

Akari-1A

12.40

0.353

Akari-1B

12.40

0.353

Akari-2A

7.50

0.082

Akari-2B

7.50

0.082

Akari-2C

7.50

0.082

Lamed

13.00

0.778

Ours

10.94

0.224

 

 

NIST RESULTS

C6

C7

C8

C9

C10

P-VALUE

PROPORTION

STATISTICAL TEST

9

6

17

9

7

0.202268

1.0000

Frequency

9

5

14

13

12

0.366918

0.9900

BlockFrequency

14

9

7

12

9

0.224821

1.0000

CumulativeSums

13

12

8

11

9

0.455937

1.0000

CumulativeSums

12

7

7

8

10

0.437274

1.0000

Runs

15

10

15

5

8

0.075719

0.9800

LongestRun

0

0

0

0

0

0.000000

0.0000

* Rank

15

11

11

8

9

0.514124

0.9900

FFT

13

14

8

13

12

0.289667

0.9900

NonOverlappingTemplate

12

16

15

10

11

0.153763

1.0000

NonOverlappingTemplate

8

9

19

9

7

0.319084

0.9700

NonOverlappingTemplate

12

5

16

11

11

0.514124

0.9800

NonOverlappingTemplate

8

10

12

6

9

0.202268

0.9700

NonOverlappingTemplate

8

7

11

9

7

0.262249

0.9800

NonOverlappingTemplate

7

14

7

5

12

0.474986

0.9700

NonOverlappingTemplate

10

5

7

11

7

0.122325

1.0000

NonOverlappingTemplate

12

5

12

9

11

0.699313

0.9900

NonOverlappingTemplate

13

5

4

9

14

0.224821

1.0000

NonOverlappingTemplate

8

8

6

13

8

0.455937

0.9900

NonOverlappingTemplate

10

10

7

10

8

0.759756

1.0000

NonOverlappingTemplate

10

11

11

10

8

0.964295

0.9900

NonOverlappingTemplate

6

14

11

9

5

0.657933

0.9800

NonOverlappingTemplate

13

3

9

14

9

0.202268

0.9700

NonOverlappingTemplate

8

9

13

7

6

0.514124

0.9900

NonOverlappingTemplate

8

11

8

8

9

0.236810

0.9600

* NonOverlappingTemplate

11

10

14

13

6

0.419021

0.9900

NonOverlappingTemplate

12

9

12

9

7

0.719747

1.0000

NonOverlappingTemplate

9

12

10

13

11

0.935716

0.9800

NonOverlappingTemplate

10

10

16

12

9

0.699313

0.9900

NonOverlappingTemplate

10

6

16

8

6

0.062821

1.0000

NonOverlappingTemplate

8

7

12

13

6

0.437274

0.9600

* NonOverlappingTemplate

10

10

9

6

14

0.494392

1.0000

NonOverlappingTemplate

8

12

15

9

11

0.455937

1.0000

NonOverlappingTemplate

10

12

15

7

13

0.249284

1.0000

NonOverlappingTemplate

10

6

9

12

10

0.867692

0.9900

NonOverlappingTemplate

6

10

8

14

12

0.474986

1.0000

NonOverlappingTemplate

12

9

12

7

8

0.883171

0.9800

NonOverlappingTemplate

12

8

7

13

7

0.816537

1.0000

NonOverlappingTemplate

10

7

10

10

10

0.798139

0.9900

NonOverlappingTemplate

13

9

12

11

5

0.350485

0.9900

NonOverlappingTemplate

8

13

11

9

11

0.401199

0.9900

NonOverlappingTemplate

10

7

8

8

14

0.534146

0.9900

NonOverlappingTemplate

12

13

5

7

12

0.319084

1.0000

NonOverlappingTemplate

13

8

6

11

9

0.678686

0.9900

NonOverlappingTemplate

9

14

11

6

9

0.834308

0.9800

NonOverlappingTemplate

7

12

16

16

6

0.162606

0.9900

NonOverlappingTemplate

12

10

14

11

6

0.779188

0.9900

NonOverlappingTemplate

9

9

14

10

9

0.514124

0.9900

NonOverlappingTemplate

10

8

11

8

6

0.090936

0.9900

NonOverlappingTemplate

7

11

13

7

6

0.595549

0.9900

NonOverlappingTemplate

9

11

9

19

7

0.191687

1.0000

NonOverlappingTemplate

5

8

7

12

11

0.514124

0.9900

NonOverlappingTemplate

10

9

8

12

17

0.319084

0.9800

NonOverlappingTemplate

9

11

12

9

11

0.759756

0.9800

NonOverlappingTemplate

9

11

9

8

16

0.834308

1.0000

NonOverlappingTemplate

11

14

9

9

12

0.657933

0.9800

NonOverlappingTemplate

9

11

12

6

10

0.739918

0.9900

NonOverlappingTemplate

9

7

12

15

6

0.334538

0.9800

NonOverlappingTemplate

6

11

16

13

5

0.066882

0.9700

NonOverlappingTemplate

2

11

12

9

13

0.090936

0.9900

NonOverlappingTemplate

12

7

13

11

12

0.554420

0.9700

NonOverlappingTemplate

20

5

13

5

11

0.019188

1.0000

NonOverlappingTemplate

15

8

13

10

5

0.455937

0.9900

NonOverlappingTemplate

12

7

15

6

8

0.455937

0.9800

NonOverlappingTemplate

13

11

12

11

9

0.514124

1.0000

NonOverlappingTemplate

6

13

10

11

16

0.401199

0.9800

NonOverlappingTemplate

6

7

8

13

10

0.595549

1.0000

NonOverlappingTemplate

6

16

9

8

8

0.102526

0.9900

NonOverlappingTemplate

11

13

12

11

6

0.739918

0.9900

NonOverlappingTemplate

5

13

8

13

5

0.514124

1.0000

NonOverlappingTemplate

9

9

9

10

16

0.867692

0.9800

NonOverlappingTemplate

11

9

13

8

16

0.474986

0.9900

NonOverlappingTemplate

15

10

6

10

10

0.437274

0.9900

NonOverlappingTemplate

6

6

13

13

11

0.637119

1.0000

NonOverlappingTemplate

11

8

5

15

14

0.171867

0.9800

NonOverlappingTemplate

13

6

9

10

10

0.494392

0.9700

NonOverlappingTemplate

10

14

8

5

11

0.514124

1.0000

NonOverlappingTemplate

9

10

10

7

6

0.249284

0.9800

NonOverlappingTemplate

13

10

3

11

11

0.262249

0.9900

NonOverlappingTemplate

6

8

7

14

11

0.191687

0.9700

NonOverlappingTemplate

8

8

10

13

8

0.759756

1.0000

NonOverlappingTemplate

9

4

11

12

13

0.350485

0.9900

NonOverlappingTemplate

13

14

8

13

12

0.304126

0.9900

NonOverlappingTemplate

15

6

8

3

15

0.066882

1.0000

NonOverlappingTemplate

13

8

6

17

12

0.153763

1.0000

NonOverlappingTemplate

6

10

12

8

11

0.834308

1.0000

NonOverlappingTemplate

9

11

15

13

6

0.437274

0.9900

NonOverlappingTemplate

5

5

12

14

11

0.090936

0.9800

NonOverlappingTemplate

9

8

12

9

10

0.455937

0.9900

NonOverlappingTemplate

13

12

6

5

12

0.595549

1.0000

NonOverlappingTemplate

6

9

16

15

6

0.102526

0.9900

NonOverlappingTemplate

10

7

11

14

13

0.595549

0.9900

NonOverlappingTemplate

6

10

8

9

12

0.739918

0.9900

NonOverlappingTemplate

7

7

8

8

13

0.867692

0.9900

NonOverlappingTemplate

11

15

5

17

6

0.000474

0.9900

NonOverlappingTemplate

8

18

10

7

7

0.236810

0.9900

NonOverlappingTemplate

9

11

10

12

10

0.834308

1.0000

NonOverlappingTemplate

6

11

17

7

8

0.437274

1.0000

NonOverlappingTemplate

9

9

7

8

14

0.595549

0.9800

NonOverlappingTemplate

11

10

12

7

8

0.383827

1.0000

NonOverlappingTemplate

9

6

11

5

8

0.455937

0.9700

NonOverlappingTemplate

11

7

8

9

7

0.366918

0.9800

NonOverlappingTemplate

7

16

11

11

14

0.145326

1.0000

NonOverlappingTemplate

10

9

13

9

7

0.798139

1.0000

NonOverlappingTemplate

11

9

9

12

11

0.455937

0.9900

NonOverlappingTemplate

10

9

9

6

6

0.058984

1.0000

NonOverlappingTemplate

9

9

11

10

14

0.678686

0.9700

NonOverlappingTemplate

8

15

8

12

6

0.289667

0.9700

NonOverlappingTemplate

12

9

12

6

10

0.474986

0.9900

NonOverlappingTemplate

6

7

7

7

16

0.085587

0.9800

NonOverlappingTemplate

11

6

8

15

17

0.162606

1.0000

NonOverlappingTemplate

9

9

8

11

9

0.935716

0.9900

NonOverlappingTemplate

11

8

13

13

16

0.350485

0.9800

NonOverlappingTemplate

8

13

12

9

3

0.455937

1.0000

NonOverlappingTemplate

13

7

9

5

13

0.145326

0.9900

NonOverlappingTemplate

12

13

10

12

9

0.699313

0.9900

NonOverlappingTemplate

4

7

12

11

12

0.080519

0.9800

NonOverlappingTemplate

8

12

12

13

9

0.401199

1.0000

NonOverlappingTemplate

9

11

15

6

6

0.657933

1.0000

NonOverlappingTemplate

11

6

12

12

11

0.867692

0.9800

NonOverlappingTemplate

5

9

11

9

7

0.289667

0.9900

NonOverlappingTemplate

7

5

13

13

10

0.657933

0.9800

NonOverlappingTemplate

7

8

5

17

9

0.080519

1.0000

NonOverlappingTemplate

11

12

6

6

14

0.162606

0.9900

NonOverlappingTemplate

15

16

8

10

6

0.350485

1.0000

NonOverlappingTemplate

16

17

8

9

6

0.137282

0.9800

NonOverlappingTemplate

11

7

8

10

12

0.883171

0.9900

NonOverlappingTemplate

7

7

10

13

6

0.401199

0.9900

NonOverlappingTemplate

7

13

8

13

9

0.249284

0.9900

NonOverlappingTemplate

8

11

11

9

15

0.678686

1.0000

NonOverlappingTemplate

17

12

10

7

9

0.514124

1.0000

NonOverlappingTemplate

7

10

13

15

5

0.350485

0.9900

NonOverlappingTemplate

13

17

8

8

12

0.262249

1.0000

NonOverlappingTemplate

13

11

8

10

10

0.883171

1.0000

NonOverlappingTemplate

7

9

15

9

9

0.834308

1.0000

NonOverlappingTemplate

9

12

13

11

8

0.897763

1.0000

NonOverlappingTemplate

16

7

10

8

15

0.249284

0.9900

NonOverlappingTemplate

11

10

12

6

10

0.759756

0.9700

NonOverlappingTemplate

9

8

16

8

4

0.275709

0.9800

NonOverlappingTemplate

8

17

9

12

11

0.474986

0.9800

NonOverlappingTemplate

13

10

12

8

12

0.616305

0.9800

NonOverlappingTemplate

8

9

8

9

9

0.719747

0.9900

NonOverlappingTemplate

8

11

12

14

6

0.275709

1.0000

NonOverlappingTemplate

12

7

14

9

5

0.514124

0.9900

NonOverlappingTemplate

13

11

6

16

9

0.401199

0.9700

NonOverlappingTemplate

10

8

8

14

13

0.883171

0.9700

NonOverlappingTemplate

8

10

11

13

13

0.719747

0.9900

NonOverlappingTemplate

9

14

12

10

9

0.699313

1.0000

NonOverlappingTemplate

8

8

8

11

9

0.514124

0.9700

NonOverlappingTemplate

12

14

13

6

12

0.616305

0.9800

NonOverlappingTemplate

8

9

6

12

9

0.897763

1.0000

NonOverlappingTemplate

6

12

11

10

15

0.779188

1.0000

NonOverlappingTemplate

11

5

13

9

15

0.616305

0.9900

NonOverlappingTemplate

11

8

13

8

10

0.816537

0.9900

NonOverlappingTemplate

9

10

8

5

11

0.816537

1.0000

NonOverlappingTemplate

9

4

11

12

13

0.249284

0.9900

NonOverlappingTemplate

3

16

7

10

6

0.085587

1.0000

OverlappingTemplate

0

0

0

0

0

0.000000*

1.0000

Universal

9

15

7

7

12

0.616305

0.9800

ApproximateEntropy

0

1

1

2

1

0.739918

1.0000

RandomExcursions

0

1

5

1

1

0.035174

1.0000

RandomExcursions

3

0

0

1

1

0.122325

1.0000

RandomExcursions

2

1

3

1

0

0.534146

1.0000

RandomExcursions

0

3

0

1

1

0.213309

1.0000

RandomExcursions

0

3

1

1

1

0.534146

0.9167

RandomExcursions

1

1

1

1

2

0.991468

1.0000

RandomExcursions

0

5

1

1

3

0.002043

1.0000

RandomExcursions

3

2

1

0

0

0.213309

1.0000

RandomExcursionsVariant

2

2

0

2

1

0.739918

1.0000

RandomExcursionsVariant

2

1

0

2

3

0.350485

1.0000

RandomExcursionsVariant

3

1

1

2

2

0.534146

1.0000

RandomExcursionsVariant

0

2

0

3

3

0.122325

1.0000

RandomExcursionsVariant

1

0

1

1

3

0.534146

1.0000

RandomExcursionsVariant

1

0

2

1

2

0.534146

1.0000

RandomExcursionsVariant

2

1

2

1

2

0.911413

1.0000

RandomExcursionsVariant

2

2

3

1

1

0.534146

1.0000

RandomExcursionsVariant

1

4

1

0

2

0.122325

1.0000

RandomExcursionsVariant

1

1

2

3

1

0.739918

1.0000

RandomExcursionsVariant

1

2

3

1

0

0.534146

1.0000

RandomExcursionsVariant

1

0

2

1

1

0.534146

1.0000

RandomExcursionsVariant

3

1

1

0

2

0.534146

1.0000

RandomExcursionsVariant

1

0

2

2

0

0.213309

1.0000

RandomExcursionsVariant

3

0

1

2

0

0.213309

1.0000

RandomExcursionsVariant

1

1

1

0

2

0.739918

1.0000

RandomExcursionsVariant

0

1

1

1

1

0.739918

1.0000

RandomExcursionsVariant

13

7

8

8

10

0.834308

1.0000

Serial

8

12

7

10

9

0.779188

0.9900

Serial

7

4

6

13

9

0.122325

0.9900

LinearComplexity