13,551,695 members
Tip/Trick
alternative version

#### Stats

3.7K views
4 bookmarked
Posted 6 Mar 2014
Licenced CPOL

# Choosing a Good Constant in the Logistic Map PRNG

, 6 Mar 2014
How a bad constant can cause a security breach

## 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.

## Share

 Systems Engineer Switzerland
This member doesn't quite have enough reputation to be able to display their biography and homepage.