Information Technology Reference
In-Depth Information
regenerate the sequence. Tests based on complexity measures like linear com-
plexity, maximum order complexity can be given as examples.
These categories are closely related and obviously not disjoint. It is possible
to find randomness tests that can be included in more than one category. As an
example, consider the runs test which can be included to the category of tests
based on ordering of k =1 -tuples and also to the category of tests based on
k =2 -tuple pattern frequency since it actually counts the number of 01 and 10
patterns throughout the sequence.
Even for applications that do not require strong random numbers, generators
should produce uniform outputs, in other words, should pass the tests in the
first category. The tests in the second category usually take more time compared
to the first category, but they are more important for applications that require
strong randomness such as cryptographic applications where randomness is used
in key, nonce and initial vector generation.
Test Suites. A randomness test suite is a collection of randomness tests that
are selected to analyze the randomness properties of generators. Here we give
some information about widely used test suites.
- Knuth Test Suite [4], developed in 1998, presents several empirical tests
including frequency, serial, gap, poker, coupon collector's, permutation, run,
maximum-of- t , collision, birthday spacings and serial correlation.
- DIEHARD Test Suite [2] consists of 18 different, independent statistical
tests including; birthday spacings, overlapping 5-permutations, binary rank,
bitstream test, monkey tests on 20-bit Words, monkey tests OPSO, OQSO,
DNA, count the 1's in a stream of bytes, count the 1's in specific bytes,
parking lot, minimum distance, 3D spheres, squeeze, overlapping sums, runs
and craps.
- Crypt-XS [3] suite which was developed in the Information Security Research
Centre at Queensland University of Technology consists of frequency, binary
derivative, change point, runs, sequence complexity and linear complexity
tests.
- NIST Test Suite [1] consists of 16 tests namely frequency, block frequency,
cumulative sums, runs, long runs, rank, spectral, nonoverlapping template
matchings, overlapping template matchings, Maurer's universal statistical,
approximate entropy, random excursions, Lempel-Ziv complexity, linear com-
plexity, and serial. During the evaluation of block ciphers presented for AES,
Soto [6] proposed nine different ways to generate large number of data streams
from a block cipher and tested these streams using the NIST test suite to eval-
uate the security of AES candidates.
- TestU01 Sui te [5] is another test suite for empirical testing of random num-
ber generators. This suite consists of many randomness tests and it is also
suitable to test sequences that take real values.
Multi Level Testing. In [11], to increase the power of tests, it is proposed to
apply the test N times to disjoint parts of the sequence, yielding N different test
Search WWH ::




Custom Search