Choosing a Good Constant in the Logistic Map PRNG

Introduction

The problems of using certain constants in pseudo-random number generators (PRNG) is a problem that is still not very known among developers. Recent events regarding the NSA and their presumable attempt to weaken the Dual_EC DRBG algorithm have shown one of the major flaws in modern days cryptography.

This example will demonstrate the effects of choosing a weak parameter in the Logistic Map, a mathematical function that is known from chaos theory and which can be used to implement a PRNG.

Background

The Logistic map is a simple non-linear equation that is defined as:

x_n+1 = a * x_n* (1- x_n)

The parameter a determines the behaviour of the map. If a > 3.57, the map shows chaotic properties which means that even a slight change of the original input value x_0 leads to a complete different set of output values. The closer a gets to 4, the greater the chaotic effect will become (i.e., if a >= 3.9, then the logistic map is considered to be very chaotic).

This effect can be used to design a PRNG.

Using the Code

package chaoticprng;

import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;


public class ChaoticPRNG {

    static double logisticMap(double a, double x) {

        double retVal = a * x * (1 - x);

        return retVal;
    }

    static int flipBit(int n, int pos) {
        return (n | (1 << pos));
    }

  
    public static void main(String[] args) throws IOException {
        

        double x = Math.random();
        double y = Math.random();

        Writer wr = new FileWriter("C:\\tmp\\DiehardSuite\\prng397");

        for (int i = 0; i < 5000000; i++) {

            Integer number = 0;
           
            for (int k = 0; k < 32; k++) {

                x = logisticMap(3.9, x);
                y = logisticMap(3.9, y);

                Long xToLong = Double.doubleToLongBits(x);
                Long yToLong = Double.doubleToLongBits(y);

                int bitCount = Long.bitCount(xToLong ^ yToLong);

                //System.out.println(bitCount);
                if (bitCount % 2 == 1) {
                    number = flipBit(number, k);
                }

            }

            wr.write(number);
        }

        wr.close();
        System.out.println("Finished");
    }

}

Statistical Tests using the Diehard Battery

We implement a simple Java method that calculates two long numbers x and y using the Logistic map with parameter a=3.9 (the seed is provided by the Math.random() method).

From x and y, we determine an integer number using the bit operator (^) and write it into a file.

For statistical purposes, we want to create 5 million of theses integer values and store them in a file called logmap.dat.

// Logistic map

The Diehard battery of tests is a toolkit to determine the quality of a random number sequence. It is publicly available and uses a set of statistical tests to check whether a given sequence of integer numbers shows specific patterns. Using this tool, we get the following result file (the following output is just one of the 15 tests of the suite):

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

:: The OVERLAPPING SUMS test ::

:: Integers are floated to get a sequence U(1),U(2),... of uni- ::

:: form [0,1) variables. Then overlapping sums, ::

:: S(1)=U(1)+...+U(100), S2=U(2)+...+U(101),... are formed. ::

:: The S's are virtually normal with a certain covariance mat- ::

:: rix. A linear transformation of the S's converts them to a ::

:: sequence of independent standard normals, which are converted ::

:: to uniform variables for a KSTEST. The p-values from ten ::

:: KSTESTs are given still another KSTEST. ::

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

Test no. 1 p-value 1.000000 

Test no. 2 p-value 1.000000

Test no. 3 p-value 1.000000

Test no. 4 p-value 1.000000

Test no. 5 p-value 1.000000

Test no. 6 p-value 1.000000

Test no. 7 p-value 1.000000

Test no. 8 p-value 1.000000

Test no. 9 p-value 1.000000

Test no. 10 p-value 1.000000

Results of the OSUM test for prng

KSTEST on the above 10 p-values: 1.000000

A p-value of 1.0 means that the sequence shows strong non-random patterns, each of the other 14 tests fail the same way. So we can deduce that the Logistic map with a=3.90 simply does not generate enough entropy although mathematicians consider it to be „highly chaotic“.

However, if we change the parameter to a= 3.97 (instead of 3.90) it seems that the amount of entropy becomes sufficient. The nature of non-linear maps is that their behaviour is hard to grasp even when the algorithms are Open Source. By modifying these constants, a backdoor can be implemented that is somehow „hidden“ even though the source code is public.