Subject: Re: [dsfjdssdfsd] software tools for testing entropy (was: Any plans for drafts or discussions on here?)

From: =JeffH <[email-masked]>
Date: Thu, 23 Jan 2014 16:32:25 -0800

> are there good software tools for testing entropy, that could help
 > applications determine if the underlying system is giving them good
 > input?

well, from..

[0] Akram, Raja Naeem, Konstantinos Markantonakis, and Keith Mayes.
"Pseudorandom Number Generation in Smart Cards: An Implementation,
Performance and Randomness Analysis." New Technologies, Mobility and
Security (NTMS), 2012 5th International Conference on. IEEE, 2012.
http://digirep.rhul.ac.uk/file/315c7a7e-4963-4a62-189f-4ad198a79f30/5/Paper.pdf

..there's the sections reproduced at [1] below which may (or may not) be 
helpful.

also, NIST has these resources..

NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom
Number Generators for Cryptographic Application.
http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf

Random Number Generators (RNG) Testing Requirements:
http://csrc.nist.gov/groups/STM/cavp/index.html#04

RNG Test Vectors
http://csrc.nist.gov/groups/STM/cavp/documents/rng/rngtestvectors.zip

One could also ask the authors of [0] if they might share their impl.

hth,

=JeffH

[1]
E. Experimental Proof

To provide experimental proof, the NIST statistical test suite
was applied. Each algorithm was provided with a common
seed file, and generated sequences from it were saved in a
binary file. This binary file was used as input to the statistical
test. Point to note here is that seed files given to all algorithms
were the same. The reason for doing so was to analyse
differences in the quality of output while using the same
entropy source.

For statistical analysis, each algorithm was executed to
generate 1,048,578 pseudorandom sequences of 128 bits.
Concatenating the outputs into a binary file that was then used
for NIST SP 800-22 statistical analysis. The results of each
algorithm are listed in Appendix A. Taking into account the
Common Criteria AIS 20 [18], our implementation fulfils the
requirements for the K4 DRNG. Below is the discussion on
how our implementation satisfies these requirements.

1) K1 DRNG: Its a simple requirement that states that if
the generated values is of set C =f c1, c2, c3, .., cm g
then all members of the set should be distinct regardless
of the statistical properties.

2) K2 DRNG: Requires that the implementation should
satisfy the statistical properties such as monobit test,
poker test and tests on runs. Our implementations were
subjected to the NIST SP 800-22 test suite.

3) K3 DRNG: This requires that the entropy of the PRNG
is at least 80. All SHA based algorithms has 440 bits
seed and block cipher based algorithms has 128 bits
seed. All of the seed values were chosen from an
external high entropy source that is carefully tested.

4) K4 DRNG: This level requires that the PRNG should be
forward-secure. A PRNG is forward-secure if after n iteration
of the PRNG, a malicious user is unable to guess
the internal state of the generator. The implemented
PRNG feed back to the internal seed that is changing in
each of the iterations. Furthermore, block cipher based
implementation of the PRNG use different key in each
of the iterations. Even retrieving a cryptographic key
would not help a malicious user to successfully know
the entire state of the seed file.

In our implementations we tested SHA and block cipher
based algorithms for the PRNGs. In general block cipher based
algorithms, only a single key is used for the entire lifetime of
the generator. However, we have tested that a PRNG could be
modified to use a new key on each execution of the generator.
The internal key generation mechanism of the block cipher
based PRNG implementations are light weight and they do not
hamper the overall performance of the generator. Therefore, it
could be argued that it provides a more secure block cipher
based PRNG then an PRNG that only uses a single key for
entire lifetime.

Table IV details the percentage of passing sequences pro
duced by individual algorithms. As it is evident from table III
and IV, there is not a big difference between the implemented
algorithms both in terms of performance and percentage of
sequence passing the NIST statistical tests. Of particular note,
if we take the accumulated average of the passing sequences
percentage in the table IV an interesting result emerges. The
SHA-1 performs comparative better than other algorithms
and AES based PRNG has the least accumulated average
of passing sequence as illustrated in figure 4. This measure
represents the randomness of the generated sequences - not
the security of the algorithm. If we also account for the
performance, SHA based algorithms perform better than the
encryption based algorithms (e.g. DES and AES).

V. CONCLUSION AND FUTURE RESEARCH DIRECTIONS
...
Our research into the possibility of using a test suite like
NIST SP 800-SP to check pseudorandom number generators in
smart cards has showed that it is a workable concept. The tests
listed in the NIST SP 800-22 are substantially more then the
one recommended for the smart card pseudorandom number
generators in AIS20 [18] and AIS31 [13]. This research has
demonstrated that even with limited resources and an entropy
constrained environment like a smart card, good quality pseudorandom
sequences can be generated that can satisfy all the
requirements for a PRNG even the ones that are used for
general purpose computers.
...

---
end

---

From: Michael Hammer <[email-masked]>
Date: Fri, 24 Jan 2014 00:41:00 +0000

Thanks.  This is useful to me.

Michael Hammer
Principal Engineer
[email-masked]
Mobile: +1 408-202-9291
500 Yosemite Drive Suite 120
Milpitas, CA 95035 USA

-----Original Message-----
From: dsfjdssdfsd [mailto:[email-masked]] On Behalf Of =JeffH
Sent: Thursday, January 23, 2014 4:32 PM
To: IETF Pseudorandom Number Generator PRNG discussion list
Subject: Re: [dsfjdssdfsd] software tools for testing entropy (was: Any
plans for drafts or discussions on here?)

 > are there good software tools for testing entropy, that could help  >
applications determine if the underlying system is giving them good  >
input?

well, from..

http://digirep.rhul.ac.uk/file/315c7a7e-4963-4a62-189f-4ad198a79f30/5/Paper.
pdf

NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom Number
Generators for Cryptographic Application.
http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf

RNG Test Vectors

hth,

=JeffH

[1]
E. Experimental Proof

To provide experimental proof, the NIST statistical test suite was applied.
Each algorithm was provided with a common seed file, and generated sequences
from it were saved in a binary file. This binary file was used as input to
the statistical test. Point to note here is that seed files given to all
algorithms were the same. The reason for doing so was to analyse differences
in the quality of output while using the same entropy source.

For statistical analysis, each algorithm was executed to generate 1,048,578
pseudorandom sequences of 128 bits.
Concatenating the outputs into a binary file that was then used for NIST SP
800-22 statistical analysis. The results of each algorithm are listed in
Appendix A. Taking into account the Common Criteria AIS 20 [18], our
implementation fulfils the requirements for the K4 DRNG. Below is the
discussion on how our implementation satisfies these requirements.

1) K1 DRNG: Its a simple requirement that states that if the generated
values is of set C =f c1, c2, c3, .., cm g then all members of the set
should be distinct regardless of the statistical properties.

2) K2 DRNG: Requires that the implementation should satisfy the statistical
properties such as monobit test, poker test and tests on runs. Our
implementations were subjected to the NIST SP 800-22 test suite.

3) K3 DRNG: This requires that the entropy of the PRNG is at least 80. All
SHA based algorithms has 440 bits seed and block cipher based algorithms has
128 bits seed. All of the seed values were chosen from an external high
entropy source that is carefully tested.

4) K4 DRNG: This level requires that the PRNG should be forward-secure. A
PRNG is forward-secure if after n iteration of the PRNG, a malicious user is
unable to guess the internal state of the generator. The implemented PRNG
feed back to the internal seed that is changing in each of the iterations.
Furthermore, block cipher based implementation of the PRNG use different key
in each of the iterations. Even retrieving a cryptographic key would not
help a malicious user to successfully know the entire state of the seed
file.

In our implementations we tested SHA and block cipher based algorithms for
the PRNGs. In general block cipher based algorithms, only a single key is
used for the entire lifetime of the generator. However, we have tested that
a PRNG could be modified to use a new key on each execution of the
generator.
The internal key generation mechanism of the block cipher based PRNG
implementations are light weight and they do not hamper the overall
performance of the generator. Therefore, it could be argued that it provides
a more secure block cipher based PRNG then an PRNG that only uses a single
key for entire lifetime.

Table IV details the percentage of passing sequences pro duced by individual
algorithms. As it is evident from table III and IV, there is not a big
difference between the implemented algorithms both in terms of performance
and percentage of sequence passing the NIST statistical tests. Of particular
note, if we take the accumulated average of the passing sequences percentage
in the table IV an interesting result emerges. The
SHA-1 performs comparative better than other algorithms and AES based PRNG
has the least accumulated average of passing sequence as illustrated in
figure 4. This measure represents the randomness of the generated sequences
- not the security of the algorithm. If we also account for the performance,
SHA based algorithms perform better than the encryption based algorithms
(e.g. DES and AES).

V. CONCLUSION AND FUTURE RESEARCH DIRECTIONS ...
Our research into the possibility of using a test suite like NIST SP 800-SP
to check pseudorandom number generators in smart cards has showed that it is
a workable concept. The tests listed in the NIST SP 800-22 are substantially
more then the one recommended for the smart card pseudorandom number
generators in AIS20 [18] and AIS31 [13]. This research has demonstrated that
even with limited resources and an entropy constrained environment like a
smart card, good quality pseudorandom sequences can be generated that can
satisfy all the requirements for a PRNG even the ones that are used for
general purpose computers.
...

---
end

_______________________________________________
dsfjdssdfsd mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dsfjdssdfsd