Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

Choosing a Good Constant in the Logistic Map PRNG

, 6 Mar 2014
Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Dan Mihajlov
Systems Engineer
Switzerland Switzerland
I am a software developer with special interest in cryptography, mobile and network security. I like Linux related stuff and currently I try to get familiar with the interior of Android.

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web01 | 2.8.140926.1 | Last Updated 6 Mar 2014
Article Copyright 2014 by Dan Mihajlov
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid