Page 1

1

Structural attack to a pseudo-random generator

Behrooz Khadem1, Ali Madadi

[email protected] , [email protected]

Imam Hussein Comprehensive University, Iran

Abstract

Time, data and memory trade off attack is one of the most important threats against pseudo-

random generators and resisting against it, is considered as a main criteria of designing such

generators. In this research, the pseudo-random GMGK generator will be addressed and

analyzed in details. Having indicated various weaknesses of this generator, we performed

three different versions of structural attack on this generator and showed that proposed

TMDTO attacks to this generator can discover blocks of plaintext with lower complexity

than exhaustive search of space of key generator. Results indicated that the mentioned

generator is lack of the security claimed by authors.

Keywords: Pseudo random generator, Time, memory tradeoff attack

1. Introduction

Today, satellite and cellular communication networks and internet play a main role in

providing global universal computation and communication. Based on this, using

communication tools in most cases resulted in sensitive and important data to be saved and

accessed and transferred which in turn makes privacy security as a main issue in those

networks. While several researches has been performed in fields like cryptography,

security protocols and standards to access to secure communication tools and

proportionate to application, there are problems in this regard yet to removing of which

appropriate solutions must be devised.

Sequence codes is one of symmetrical cryptography algorithms that is highly important

because of unique capabilities in communication and telecommunication networks like

internet and GSM. Stream ciphers are used to make secure and verify electronic data

transmission and are generally include a pseudo- random generator that generates a

sequence of pseudo-random numbers or bits. For example those numbers, have been used

in fuzzy cellular machines based on random numbers generators in [MSRB15].

Recently, several researches have been performed in field of pseudo-random generators in

particular chaotic pseudo-random generators and various designs have been proposed. For

further studies on design and security of chaotic generators see [AL06]، [PP10]، [FGBE13]

and [K16].

Structural attacks are those attacks that don’t concern the nature of cipher and its internal

components and finds its weaknesses just through unique links among its inputs and

outputs. Consequently, new information is detected on secure key or plain text. Time,

1 Corresponding Author: Behrooz Khadem, Faculty of Information and Communication Technology, IHC university, Iran

2

memory tradeoff attacks TMTO are common structural attacks on symmetric ciphers.

Those attacks are implementable in known (chosen)-plaintext attack model and known

(chosen)-cipher text attack model, if available under certain conditions. One of the methods

to reduce time of exhaustive key search attack in stream ciphers is TNDTO attack that

enables the attacker to tradeoff optionally time, memory and data resources required for

this attack together based on an equation named TMTO curve and as a result simplifies the

attack. After Hellman proposed general principles for block ciphers [He80], several studies

have also been performed on stream ciphers to adjust or generalize it. Those researches are

best exemplified by works including results obtained by Babbage on stream ciphers [B95],

Golic on A5 stream ciphers [G97], two considerable papers by Biryukov [BS00] and Biryukov

et.al. introducing TMDTO attack and attack to A5/1 [BSW00], Dawson et.al., evaluating LILI-

128 [DGMS00], Saarinen’s work to attack LILI-128 [S02], Hong et.al., introducing new

applications of TMDTO [HS05], Babbage et.al., for evaluating MICKEY [BD06], and

Dunkelman et.al. [DK08], for introducing role of IV in TMDTO attack. Readers are

recommended to study Krhovják et.al. In [KSN11] for quick review on theory and

application of TMDTO attacks to stream ciphers.

This paper focuses mainly on the structural attack to a pseudo-random generator and is

presented as follows. In Section 2 a new generator will be briefly described proposed in

[GMGK16] after providing a general definition of pseudo-random generator. Also some of

its most important weaknesses will be pointed out. Next three sections deal introduction of

the three different structural attacks, particularly TMDTO briefly and then several attacks

to the generator will be explained. The paper will be ended proposing summary of result

and conclusion.

2. Summary of pseudo- random generator GMGK

Generally, a pseudo-random generator (statefull and synchronous) is generally shown by a

quadruple ( , , , )

X S n

γ

where X is space of input and output alphabet, S is the internal state

space, :S

S X

γ

→ × is the generator function (state transition) and n is the maximum

number of output blocks for the generator (fig. 1) and is defined as[K16]:

(1.

1)

0

1

:

(

, ) .

( , )

( ), ( 1, , )

:

.

t

t

z

t

t

input s Init Key IV

s z

s

t

n

output z

γ

-

⎧

=

│

=

=

⎨

│

⎩

In this generator during initializing step, the initial state 0

s is calculated with a function

Init selecting secure key Key and a known initial value. Then, transition function for

generator state ( )z

γ according to definition is iterated for producing b

n blocks of key stream

sequence tz . In a stream cipher, a block of cipher text is generated by combination of a

block of plaintext and a block of key stream. In most cases of structural attacks to stream

ciphers, the state transition function ( )z

γ or composite function (

)

z

Init

γ Ο

is considered as

one-way function that must be inversed.

3

Figure 1: overview of a pseudo-random generator [K16]

2.1. A brief overview of GMGK and its main components

Gaeini et.al. have recently proposed a chaotic pseudo-random generator [GMGK16] (in this paper it

is referred to as GMGK). This generator uses a 128 bits secure key (

)

Key , an initial value of 128

bits ( )

IV , and a 128 bits internal state ( )L and includes a linear shift register, 3 linear congruence

generators (5,1) and 3 chaotic generator called Tent(1.2), and Logistic (1.3) and Chebyshev (1.4.). In

congruence generators ( 0)

t > and in chaotic maps ( 0)

t ≥ , it was assumed that:

)1.2(

1

1

1

1

1

, 0

1

,

1

1

0 , 0

1 ,

1

t

t

t

t

t

t

t

tent

t

x

x

x

x

x

x

b

x

α

α

α

α

α

α

+

+

+

+

+

⎧

≤

<

│

│

= ⎨

-

│

≤

<

│ -

⎩

≤

<

⎧

= ⎨

≤

<

⎩

)1.3(

1

1

1

3.9999 (1

)

0 , 0

0.5

1 , 0.5

1

t

t

t

t

t

lo

t

x

x

x

x

b

x

+

+

+

=

+

≤

<

⎧

= ⎨

≤

<

⎩

)1.4(

1

1

1

Cos(4*

Cos( ))

0 , -1

0

1 , 0

1

t

t

t

t

cheb

t

x

arc

x

x

b

x

+

+

+

=

≤

<

⎧

= ⎨

≤

≤

⎩

)1.5(

1

1

1

31

1

3

1

1

1

1

31

2

1

2

1

1

1

31

3

2

3

(

1)(

)mod (2 -

)

(

1)(

)mod (2 - )

(

1)(

)mod (2 -

)

t

t

t

t

t

tent

tent

t

t

t

t

t

lo

lo

t

t

t

t

t

cheb

cheb

Z

b

Z

Z

b

Z

b

Z

Z

b

Z

b

Z

Z

b

-

-

-

-

-

-

-

-

-

=

+

+

=

+

+

=

+

+

In case of GMGK, pseudo- random numbers are generated in two steps. Those numbers are

generated in the first step will be used as input of second step (fig.2).

4

Fig 2: overview of GMGK generator [G16]

First step of algorithm is based on linear congruence generators and chaotic maps while the

second step of algorithm is based on shift register whose feedback is formed in each step

using algorithm of first step. In following sections, we will call the first step algorithm as

setup algorithm and the second step algorithm as the generator algorithm. The structure of

setup algorithm is as follow. Its input contains three values:

1. One 128 bits Initial value ( )

IV

2. One 128 bits key(

)

Key

3. Three initial values of chaotic maps used in (1.5)

In setup algorithm, the value of 128 bits ( )

IV is encrypted as the plaintext block with

(

)

Key by AES and the block of output cipher text is considered as the initial state ( )L of shift

register. From this time on, AES is not used elsewhere. Three initial values of chaotic maps

according to (1.2), (1.3) and (1.4) are entered in chaotic generators and generate three

pseudo-random (chaotic) bits of 0

tent

b ، 0

lo

b and 0

cheb

b .

To calculate (1.6), the initial value 1

0

Z has been determined as first 32 bits, 2

0

Z as the second

32 bit and 3

0

Z as the third 32 bits of (

)

Key and numbers 1

2

3

, ,

t

t

t

Z Z Z are generated according to

(1.5). Then, values of 1

2

3

4

, , ,

t

t

t

t

P P P P are obtained based on (1.6). The symbol(

)n

<<

introduces

n shift bits to right. In the following section, an output bit is generated according to (1.7)

that makes the output sequence (key stream) of the generator algorithm.

Bit generator

5

)1.6(

mod

1

1

mod

2

2

mod

3

3

4

1

2

3

mod

(

(1

)) 128

(

(1

)) 128

(

(1

)) 128

min{ , , }

(

) 128

t

t

t

lo

t

t

t

cheb

t

t

t

tent

t

t

t

t

t

t

t

tent

lo

cheb

P

Z

b

P

Z

b

P

Z

b

P

Z Z Z

b

b

b

=

<< +

=

<< +

=

<< +

=

<<

+

+

)1.7(

*

*

*

1

2

3

1

2

3

4

( )

( )

( )

[ ]

[ ]

[ ]

[ ]

tz LSB Z

LSB Z

LSB Z

LP

LP

LP

LP

=

⊕

⊕

⊕

⊕

⊕

⊕

In (1.7),

( )t

i

LSB Z indicates the lowest value bit in t

i

Z and [ ]t

i

L P indicates the bit value that is

internal state of L in t

i

P -th position. The output value of the generator algorithm, ( tz ) is the

final generated bit that is added to the right side of internal state L when the generator

algorithm is executed and consequently the last 128 bits are considered as a new internal

state. This process continues to have all bits of key stream to be generated. After all stream

key sequence is generated, the first L bits of it (that has been generated once by AES) will

be disposed. Together with initial values of chaotic map, (

)

Key is transmitted to the

transmitter through a private channel and ( )

IV is transitioned through the public channel

at first of key stream to enable the receiver to decrypt data.

2.2. The main weaknesses of GMGK

Weaknesses of this generator are classified into two classes; weaknesses of chaotic

generator and structural weaknesses:

• Failing to use standard discretization method in chaotic map that causes the resulted

sequence to lose its chaotic properties (random) after a short term [K16].

• Uncertain bit size of initial values of chaotic map used in setup algorithm for the

receiver that makes calculation of key length difficult.

• The computational accuracy of machine when calculating values of chaotic

sequences isn’t expressed explicitly that makes decryption difficult.

• Size of IV is smaller than 3/2 of Keysize that indicates the generator isn’t able to

resist against TMTO attack [DK08].

• Size of ( L ) isn’t bigger than ( Key) that indicates the generator acts weak against

TMTO attack [G97].

3. Types of structural attacks to current ciphers

The basic idea of these attacks is belong to Hellman and has proposed two decades ago for

block ciphers [He80] that generalized by Biryukov and Shamir proposed to stream ciphers

in [BS00] and they called it TMDTO. The basic idea in this attack is that the adversary

attempts to find a one-way function and a heuristic method to inverse it effectively and to

reduce time complexity for discovering secure key. This attack is always performed in two

steps as offline (pre-processing) and online (main). In case of stream ciphers, the pre-

processing step first calculates the output corresponding to a number of inputs of one-way

function and then these pairs of inputs and outputs are saved in a relatively large table. The

time and memory of preprocessing step is not important and is generally neglected. Then

in the main step, the adversary searches the output which is obtained from a small piece of

6

real key stream sequence to find at least one of the saved outputs. As a correspondence is

detected between real output of the generator (key stream sequence) and one of

predetermined outputs, the input related to this output is obtained from table and the

adversary is allowed to generate complete output key stream sequence of the generator

and to discover remaining blocks of plaintext using sequence of cipher text blocks. Before

studying proposed attacks, we introduced some notations which are used in this paper in

table 1.

Table 1: notations

Concept

Symbol

Concerned one-way function

f

Size of search space

N

Time of execution of pre-processing step

P

Memory of execution of pre-processing step

M

Number of f outputs owned by the adversary

D

Time needed for executing the main step

T

Babbage, Golic, Biryukov and Shamir have used separately TMDTO attack for a pseudo-

random generator in a stream cipher. In this attack, they all have considered a function that

maps the internal state space of the generator on a piece of key stream sequence. Having

inversed this function, they discovered main part of the plaintext. The important notes of

TMTO curve and related conditions in these attacks are presented in table 2.

4. First proposed attack

In case of GMGK, the size of internal state is equal to the size of secure key. In various

researches this weakness have considered as one of insecurity factors against a TMDTO

attack. We used this weakness to implement our first proposed attack. Now we describe

the attack scenario.

Let

128

{0,1}

S =

is the set of possible states of GMGK and :f S Y

→

is a function that maps

each state of S to the first 128 bits of a key stream sequence produced from that state.In the

preprocessing step, the adversary wishes to generate a large table in two columns (of 128

bits) and m rows (table 3). In order to create each row, it selects a 128 bits randomly (or

intelligently in some of advanced methods) as an internal state value of GMGK and places

it in first column ( is

) and then 128 times executes function f iteratively on it to generate an

output of 128 bits (key stream sequence). It places the output in the second column

0

127

i

i

y

b b

=

and saves in the table in the ascending order of outputs. In the main step,

(supposing that secure key is fixed) the adversary has D pieces of a real key stream

sequence and searches for similar piece for each of them in second column of table 3.

Provided that D and m are large enough, regarding to the birthday problem, the attack

success probability will be large and increasing number of columns of this table will

increase this probability. In case that it succeeds to find such piece it will determine the

internal state corresponding to it as the targeted internal state and using it and repeating

iteratively f can generate rest of bits of key stream. Consequently, it will discover a large

part of plain text blocks.

7

Table 2: The important notes of previous attacks

Size of a sample value suitable

on TMTO curve

TMTO curve and

related conditions

Reference

T M D

N

=

= =

,

,

TM

N

ND

M

P

N

=

=

=

[B95]

T M D

N

=

= =

,

1

,

( )

TM

N

T D

P O M

=

≤ ≤

=

[G97]

2

2

3

3

1

1

3

3

,

,

,

P N T N

M N

D N

=

=

=

=

2 2

2

,

2

1

,

TM D

N

D T N

N

P

D

=

≤

≤ ≤

=

[BS00]

1

4

,

T M

N

D N

=

=

=

2 2

2

,

2

,

TM D

N

D

N

N

P

D

=

≤

=

[BSW00]

( )

( )

( )

2

2

2

2

,

TM

DR

NR

DR

T N

N

P

D

=

≤ ≤

=

[BSW00]

Table 3: generated memory during preprocessing step

0

127

i

i

y

b b

=

is

i

1

y

1

s

1

2

y

2

s

2

m

y

m

s

m

In the main step, (supposing that secure key is fixed) the adversary has D pieces of a real

key stream sequence and searches for similar piece for each of them in second column of

table 3. Provided that D and m are large enough, regarding to the birthday problem, the

attack success probability will be large and increasing number of columns of this table will

increase this probability. In case that it succeeds to find such piece it will determine the

internal state corresponding to it as the targeted internal state and using it and repeating

8

iteratively f can generate rest of bits of key stream. Consequently, it will discover a large

part of plain text blocks.

Based on ideas discussed by Biryukov and Shamir in [BS00] , this attack is possible with

TMTO curve

2

2

2

TM D

N

=

. Regarding the value of

128

2

N =

and 3rd row of table 2,

complexity of the abovementioned attack can be seen from 1st column of table 6. As seen,

all resources of attack are separately smaller than search space of secure key. It indicates

that the mentioned generator lacks 128 bits of security claimed by authors.

5. Second proposed attack

While Values of complexity obtained in the first step are smaller than that of exhaustive

search of secure key space, it is probably impossible functionally. Because of this, we

describe a second attack to GMGK generator. Biryukov, Shamir and Wagner indicate a

weakness related to Rivest sampling method in TMDTO attack and proposed a new

sampling method (BSW method in this paper) [BSW00]. In this method, each of outputs of

the one-way function with a certain state (e.g. starts with k zero bits) is called special

output and the internal state corresponding to it, is called special state. Its idea was to

restricting the memory of preprocessing step to special states and outputs so that in the

main step it was sufficient that only these outputs to be examined. Therefore, memory and

time required for preprocessing and main attack time used to decrease with a known

factor. They found that because the internal state in most of stream ciphers changes slightly

after each output bit generated, this type of attack succeeds more likely, in practice.

Babbage and Dad in [BD08] used this type of attack.

Let

128

{0,1}

S =

be the set of all possible states of GMGK and

:f S

Y

′

′

→

where

S

S

′ ⊂

andY

Y

′ ⊂

, and S′ is the set of those 128 bits which their least significant 64-bits are

different.

In the preprocessing step, the adversary also wishes to generate a large table consisting of

two 128 bits columns and m rows (table 4). But instead of random selection of 128 bits as

the internal state of GMGK is′

, the adversary here just generates those 128 bits which their

least significant 64-bits are different and then executes function f 128 times iteratively on

each of them to generate a 128 bit output

0

127

i

i

y

b b

′ =

and saves in the table in the

ascending order of outputs.

Since each internal state of GMGK generator, shifts one bit left side in each cycle and the

generated bit is added to its right most place, it is seen that each two sequential states have

a set of common 127 bits and also each 128 sequential states have at least a set of 64

common bits, so it will be sufficient to save an index member of each set to reduce the

search memory and time. Thus, our second attack will decrease time and memory of

preprocessing step of attack with a reduction factor of

8

2

R

-

=

.

Suppose the adversary have D pieces of a real key stream sequence in this step, so in the

main step, she seeks for each of them a target state in table 4. Again provided that D and

m′

are large enough, regarding to the birthday problem, the attack success probability will

be large and increasing number of columns of this table will increase this probability... If

the adversary could find such a piece, she will be able to find a target internal state form

9

table 4 and using it she can generate remaining of the real key stream sequence by

repeating iteratively f and finally discovers the main part of plaintext as a result.

Table 4: generated memory during preprocessing step

0

127

i

i

y

b b

′ =

is′

i

1

y′

1

s′

1

2

y′

2

s′

2

m

y ′′

m

s ′′

m′

The second proposed attack is practical based on BSW sampling method. Regarding one of

sample points of this curve with values contained in 5th row of table 2, the complexity of

the abovementioned attack can be observed in 2nd column of table 6. As seen from table 6,

all used resources of the attack are separately smaller than the size of search space for

secure key of GMGK and they indicate that the mentioned generator doesn’t have 128

security bits that claimed by authors.

6. Third proposed attack

This section deals third proposed attack to GMGK and will be discussed in two steps. Let

:f S

S

→

be one-way function and the adversary wishes to make its inverse from 1

is +

to is

.

In the preprocessing step, if the adversary has

2

log N

bits of a real key stream sequence,

then she will be able to search for one of intermediate states of the generator in the state for

known plain text [BSW00]. Supposing that 1

j

b

b

is a piece of real key stream sequence,

the adversary creates a table in preprocessing step and occupies m input state is

and

calculates with a known value IV and a large number of random keys Key , their

corresponding 1

is +

output states saves in the table in the ascending order of outputs.

Table 5: created memory in preprocessing step

( )

i

i

u

f s

=

is′

i

1

u

1

s

1

2

u

2

s

2

D

u

D

s

D

M D

u -

M D

s -

M D

-

M

u

M

s

M

10

In the main step, the adversary has a real key stream sequence of

(

)

2

log

1

D

N +

bits. She

considers each piece of 1

j

b

b

from this sequence (called a window). Then she considers

1

j

u

u

in table 5 and compares theirs corresponding output bits with 1

j

b

b

.

Since conditions of the proposed attack conforms to conditions of the 3rd column of table 2,

the adversary will be able to find at least one window coinciding to sequence 1

j

b

b

.

Having find this window and referring to table 5, the adversary achieves the state placed in

1st row of this window which is her target state.

The third proposed attack is practical with TMTO curve

2

2

2

TM D

N

=

. The complexity of the

attack is seen from 3rd column of table 6 regarding 5th row in table 2. The attack time

complexity is considerably lower than that of exhaustive search of key space and thus is

considered as a successful attack. It can be indicated that if size of input data doubles (key

stream sequence ) then time complexity of the preprocessing step will decrease to half and

complexity of processing step to quarter.

7. Summary and conclusions

This paper evaluated and analyzed the GMGK pseudo-random generator in details. We

indicated weaknesses of this generator as well as three versions of different structural

attacks to it and indicated that proposed TMDTO attacks to it can discover a large part of

the plain text with lower complexity compared to exhaustive search of key space which in

turn demonstrates that the mentioned generator lacks the security claimed by the authors.

Table 6 summarize results of data, memory, and time complexity for three above proposed

attacks. It allows the reader to use one of those methods to attack this generator

proportionate to his or her resources and computational tools.

Table 6: complexity of proposed attacks

3rd attack

2nd attack

1st attack

Parameter

128

2

128

2

128

2

N

48

2

48

2

42.6

2

P

64

2

52

2

85.2

2

M

32

2

40

2

85.2

2

D

64

2

40

2

42.6

2

T

References

[AL06] Alvarez, Gonzalo, and Shujun Li. "Some basic cryptographic requirements for chaos-based

cryptosystems." International Journal of Bifurcation and Chaos 16.08 (2006): 2129-2151.

[B95] Babbage, S. H. "Improved “exhaustive search” attacks on stream ciphers." Security and

Detection, 1995, European Convention on. IET, 1995.

[BS00] Biryukov, Alex, and Adi Shamir. "Cryptanalytic time/memory/data tradeoffs for stream

ciphers." International Conference on the Theory and Application of Cryptology and Information

Security. Springer Berlin Heidelberg, 2000.

11

[BSW00] Biryukov, Alex, Adi Shamir, and David Wagner. "Real Time Cryptanalysis of A5/1 on a

PC." International Workshop on Fast Software Encryption. Springer Berlin Heidelberg, 2000.

[BD06] Babbage, Steve, and Matthew Dodd. "The MICKEY stream ciphers." New Stream Cipher

Designs. Springer Berlin Heidelberg, 2008. 191-209.

[DK08] Dunkelman, Orr, and Nathan Keller. "Treatment of the initial value in time-memory-data

tradeoff attacks on stream ciphers." Information Processing Letters 107.5 (2008): 133-137.

[DCGMS00] Dawson, E., Clark, A., Golic, J., Millan, W., Penna, L., & Simpson, L."The LILI-128 key

stream generator." Proceedings of first NESSIE Workshop. 2000.

[FGBE13] Francois, Michael, et al. "A new pseudo-random number generator based on two chaotic

maps." Informatica 24.2 (2013): 181-197.

[G97] Golic, J. "Cryptanalysis of Alleged A5 Stream Cipher, proceedings of EUROCRYPT’97."

Lecture Notes in Computer Science: 239-255.

[GMGK16] Gaeini, Ahmad, et al. "A New Pseudo-Random Number Generator Based on Chaotic

Maps and Linear Feedback Shift Register." Journal of Computational and Theoretical Nanoscience

13.1 (2016): 836-845.

[G16] Gaeini, Ahmad. "Design and analysis of a new efficient PRNG for cryptography", PhD Thesis,

IHU university, (2016).

[He80] Hellman, Martin. "A cryptanalytic time-memory trade-off." IEEE transactions on

Information Theory 26.4 (1980): 401-406.

[HS05] Hong, Jin, and Palash Sarkar. "New applications of time memory data tradeoffs."

International Conference on the Theory and Application of Cryptology and Information Security.

Springer Berlin Heidelberg, 2005.

[K16]Khadem, Behrooz. "A chaotic self synchronizing stream cipher and its application in image

encryption", PhD Thesis, kharazmi university, (2015).

[KSN11] Krhovják, Jan, Jiří Kůr, Ondřej Šiler, and Paul Leyland."TMTO attacks on stream ciphers–

theory and practice.” Security and Protection of Information, Brno, (2011).

[MSR15] Manikandan, G., et al. "Random Noise Based Perturbation Approach Using Pseudo

Random Number Generators for Achieving Privacy in Data Mining." Journal of Computational and

Theoretical Nanoscience 12.12 (2015): 5463-5466.

[PP10] Pareek, Narendra K., Vinod Patidar, and Krishan K. Sud. "A Random Bit Generator Using

Chaotic Maps." IJ Network Security 10.1 (2010): 32-38.

[S02] Saarinen, Markku-Juhani Olavi. "A time-memory tradeoff attack against LILI-128."

International Workshop on Fast Software Encryption. Springer Berlin Heidelberg, 2002.