2
$\begingroup$

I have an algorithm that encrypts large text. I want to test this algorithm on statistical tests. The ciphertext contains ~10,000,000 bits. I decided to test the algorithm in two different ways, I took the ciphertext and passed it to the input of statistical tests:

  1. The first parameters were as follows: /assess 1000000 and How many bitstreams? 10
  2. The second parameters were as follows: /assess 100000 and How maney bitstreams? 100

In firt scenario i got following results:

------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
   generator is <data/encode.txt>
------------------------------------------------------------------------------
 C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
------------------------------------------------------------------------------
  0   1   1   1   0   2   2   2   0   1  0.739918     10/10      Frequency
  0   1   1   0   0   2   2   3   0   1  0.350485     10/10      BlockFrequency
  0   1   1   0   1   1   1   1   2   2  0.911413     10/10      CumulativeSums
  0   1   0   1   1   4   1   1   1   0  0.213309     10/10      CumulativeSums
  1   1   0   0   0   1   2   1   3   1  0.534146     10/10      Runs
  2   0   1   1   1   0   2   1   1   1  0.911413     10/10      LongestRun
  1   2   1   1   0   1   0   0   2   2  0.739918     10/10      Rank
  1   4   0   0   1   0   2   1   0   1  0.122325     10/10      FFT
  1   1   0   2   0   0   1   3   0   2  0.350485     10/10      NonOverlappingTemplate
  2   0   1   0   2   1   1   1   0   2  0.739918      9/10      NonOverlappingTemplate
                    a lot of passed tests...
  1   0   0   2   2   1   2   1   1   0  0.739918     10/10      NonOverlappingTemplate
  0   0   1   0   7   1   0   0   1   0  0.000003 *   10/10      NonOverlappingTemplate
  1   4   1   0   1   2   1   0   0   0  0.122325     10/10      NonOverlappingTemplate
                    a lot of passed tests...
  0   0   0   3   0   0   3   1   1   2  0.122325     10/10      NonOverlappingTemplate
  0   1   3   0   0   2   1   1   1   1  0.534146     10/10      OverlappingTemplate
  1   0   0   3   2   1   1   0   1   1  0.534146      9/10      Universal
  0   0   1   2   2   3   0   0   1   1  0.350485     10/10      ApproximateEntropy
  1   0   0   0   1   1   2   1   1   1     ----       8/8       RandomExcursions
  0   1   1   1   0   1   1   1   2   0     ----       8/8       RandomExcursions
  1   0   1   1   0   2   1   1   0   1     ----       7/8       RandomExcursions
  0   1   2   1   2   1   1   0   0   0     ----       8/8       RandomExcursions
  0   3   0   0   0   1   1   0   1   2     ----       8/8       RandomExcursions
  0   2   0   0   0   0   1   1   2   2     ----       8/8       RandomExcursions
  0   0   1   2   3   0   1   0   0   1     ----       8/8       RandomExcursions
  1   1   1   0   1   1   1   1   1   0     ----       8/8       RandomExcursions
  2   0   0   3   0   0   0   0   1   2     ----       8/8       RandomExcursionsVariant
  2   1   1   0   1   0   0   1   1   1     ----       8/8       RandomExcursionsVariant
  0   1   3   0   0   1   0   2   1   0     ----       8/8       RandomExcursionsVariant
  0   1   1   1   0   3   1   0   0   1     ----       8/8       RandomExcursionsVariant
  0   0   0   4   2   1   1   0   0   0     ----       8/8       RandomExcursionsVariant
  0   2   0   1   1   1   0   3   0   0     ----       8/8       RandomExcursionsVariant
  1   0   2   0   0   0   0   0   1   4     ----       8/8       RandomExcursionsVariant
  0   1   0   2   2   0   1   0   0   2     ----       8/8       RandomExcursionsVariant
  1   0   2   0   1   0   1   1   0   2     ----       8/8       RandomExcursionsVariant
  2   0   1   1   0   1   0   0   1   2     ----       8/8       RandomExcursionsVariant
  0   2   1   2   0   1   2   0   0   0     ----       8/8       RandomExcursionsVariant
  1   0   2   2   1   1   1   0   0   0     ----       8/8       RandomExcursionsVariant
  0   2   3   1   0   0   0   0   1   1     ----       8/8       RandomExcursionsVariant
  0   1   3   1   1   0   0   1   1   0     ----       8/8       RandomExcursionsVariant
  0   3   1   0   0   2   0   0   0   2     ----       8/8       RandomExcursionsVariant
  1   2   0   1   0   0   0   1   2   1     ----       8/8       RandomExcursionsVariant
  2   1   0   0   1   1   1   0   2   0     ----       8/8       RandomExcursionsVariant
  2   1   0   1   0   0   1   2   1   0     ----       7/8       RandomExcursionsVariant
  1   1   0   0   2   3   0   1   1   1  0.534146     10/10      Serial
  0   1   0   1   4   1   0   2   1   0  0.122325     10/10      Serial
  2   0   1   1   0   2   1   0   2   1  0.739918     10/10      LinearComplexity


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 8 for a
sample size = 10 binary sequences.

The minimum pass rate for the random excursion (variant) test
is approximately = 7 for a sample size = 8 binary sequences.

For further guidelines construct a probability table using the MAPLE program
provided in the addendum section of the documentation.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

In the second scenario i got following results:

------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
   generator is <data/encode.txt>
------------------------------------------------------------------------------
 C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
------------------------------------------------------------------------------
  9  11   9  10   8   7  11  10  11  14  0.946308    100/100     Frequency
 10   8  10  10  11  10  15  10   8   8  0.924076    100/100     BlockFrequency
  9   9   9   7   8  13  11  15   8  11  0.779188    100/100     CumulativeSums
  6  12   7  12  11  12   9  11   8  12  0.851383    100/100     CumulativeSums
  8  11  15   8   6  15  10   4   8  15  0.122325    100/100     Runs
  9  10  14  14  11  11   4   7   9  11  0.514124     99/100     LongestRun
  9  13  12   9  13   9   8  11  12   4  0.637119    100/100     Rank
 14   6  11  10   6   8   8  13  10  14  0.514124    100/100     FFT
  9   7  12  11  13   8   9  11  12   8  0.924076     99/100     NonOverlappingTemplate
                     a lot of passed tests...
  8  16  16   3  10   9  12  11   6   9  0.096578     99/100     NonOverlappingTemplate
  6  12   6  11  12  11   7  11  14  10  0.657933     98/100     OverlappingTemplate
100   0   0   0   0   0   0   0   0   0  0.000000 *    0/100  *  Universal
  8  11   7  12  10  12   9  13  12   6  0.816537    100/100     ApproximateEntropy
  1   0   0   0   2   1   1   2   2   3  0.350485     12/12      RandomExcursions
  0   1   1   2   1   0   2   1   2   2  0.739918     12/12      RandomExcursions
  1   0   0   2   2   0   1   2   1   3  0.350485     12/12      RandomExcursions
  0   3   1   1   1   1   1   1   0   3  0.350485     12/12      RandomExcursions
  2   1   1   2   0   0   2   1   2   1  0.739918     11/12      RandomExcursions
  2   0   0   2   2   2   0   1   1   2  0.534146     12/12      RandomExcursions
  3   3   0   1   1   2   1   1   0   0  0.213309     12/12      RandomExcursions
  3   1   0   2   2   1   0   3   0   0  0.122325     11/12      RandomExcursions
  2   0   0   1   0   2   2   1   2   2  0.534146     12/12      RandomExcursionsVariant
  2   0   1   0   1   0   3   2   1   2  0.350485     12/12      RandomExcursionsVariant
  2   1   0   1   2   0   4   0   1   1  0.122325     12/12      RandomExcursionsVariant
  2   0   2   0   2   1   1   3   0   1  0.350485     12/12      RandomExcursionsVariant
  1   1   1   0   1   3   0   0   0   5  0.004301     12/12      RandomExcursionsVariant
  0   1   2   1   0   2   1   1   1   3  0.534146     12/12      RandomExcursionsVariant
  0   0   1   2   1   0   3   3   1   1  0.213309     12/12      RandomExcursionsVariant
  0   0   1   0   2   3   1   2   0   3  0.122325     12/12      RandomExcursionsVariant
  0   1   0   1   3   2   1   4   0   0  0.035174     12/12      RandomExcursionsVariant
  1   2   1   2   2   1   0   1   2   0  0.739918     11/12      RandomExcursionsVariant
  2   3   0   1   2   1   2   0   0   1  0.350485     11/12      RandomExcursionsVariant
  3   2   0   1   0   1   1   1   2   1  0.534146     11/12      RandomExcursionsVariant
  3   2   1   1   0   2   0   0   2   1  0.350485     12/12      RandomExcursionsVariant
  2   3   1   0   1   0   3   1   0   1  0.213309     12/12      RandomExcursionsVariant
  1   1   3   0   1   1   4   0   0   1  0.066882     12/12      RandomExcursionsVariant
  1   0   3   1   1   3   0   0   1   2  0.213309     12/12      RandomExcursionsVariant
  1   0   3   0   1   3   2   1   0   1  0.213309     12/12      RandomExcursionsVariant
  1   2   0   1   1   2   3   0   2   0  0.350485     12/12      RandomExcursionsVariant
 11  10  14  11   9   9   8  12   9   7  0.924076    100/100     Serial
 15   5  11   8   9  12   6  14  13   7  0.275709    100/100     Serial
 12  11   5  10  12  11   5  13   7  14  0.401199     98/100     LinearComplexity


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 96 for a
sample size = 100 binary sequences.

The minimum pass rate for the random excursion (variant) test
is approximately = 10 for a sample size = 12 binary sequences.

For further guidelines construct a probability table using the MAPLE program
provided in the addendum section of the documentation.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

How could it happen that when testing the same text, the algorithm failed two different tests? In the first case algorithm failed some NonOverlappingTemplate. In the second case algorithm passed all of the NonOverlappingTemplates, but failed Universal test.

Thank for yout help!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I'd ignore it.

Maurer's test is a compression test. Does your file compress with pkzip, 7z or stronger stuff like PAQ8 or cmix? No? Does it pass ent (the most trustworthy test in my opinion)?

Most randomness tests return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits. Those p-values are obtained by p = F(X), where F is the assumed distribution of the sample random variable X – often normal. But that assumed F is just an asymptotic approximation, for which the fit will be worst in the tails.

I've had the same kind of failures when testing plain /dev/urandom. It's a fault with the test code. If you think about it, when runs = 0.122325, how can compression be = 0.000000? It's nonsensical.

A good example of this flaw is below (from the horse's mouth, NIST Special Publication 800-22). All evidence leads us to conclude that the digits of an expansion of a Normal number are randomly distributed. Thus mathematically, philosophically and ecumenically, $e$ cannot fail a randomness test. Yet NIST testing does...

piccy

The contradiction can only lie with the test, and not the subject. The truth points to itself. Doesn't mean that your encryption is secure though. That can only be determined via inspection.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.