Page translation

# ARCFOUR finite state machine model

Alexander Babash, doctor of mathematics and physics, full professor

Russian State Social University, Russia

Championship participant: the National Research Analytics Championship - "Russia";

Pseudorandom number generator ARCFOUR is modeled by two consecutively connected finite state machines. Using this model some characteristics of ARCFOUR internal permutation sequence period are calculated and provided.

Keywords: ARCFOUR, pseudorandom, generator, machine, model

ARCFOUR is a pseudorandom number generator known as RC4. The name RC4 is a trademark, so RC4 is often called ARCFOUR or ARC4 (Alleged RC4) to avoid trademark problems. [1]

Pseudorandom number generator RC4 was designed by Ron Rivest of RSA Security in 1987. The RC acronym usually understood by Ron’s Code. [1]

Initially RC4 was a RSA company's property, but In September 1994 a description of it was anonymously posted on the Cypherpunks web page and in sci.crypt newsgroup. Then this information spreaded in the Internet. The posted code provided the same output sequences that licensed RC4 did, so posted code was considered to be genuine. [2]

RSA hasn't officially published the algorithm yet. [1]

RC4 use is very wide because of such features as speed and simplicity.  It’s a part of standards like TLS, WEP and WPA. [2]

ARCFOUR is a set of pseudorandom number generators. It’s internal state depends on n parameter. ARCFOUR with n=8 is used in practical applications.

Let  be an internal state set, where ZN is a ring of integers modulo N, SN is a symmetric group and N=2n. So the internal state for n=8 is .

At a point of time t ARCFOUR internal state is

ARCFOUR include two stages, called Key Scheduling Algorithm (KSA) and Pseudorandom Generation Algorithm (PRGA). The first one is an algorithm, which derives the initial state of ARCFOUR from a key. PRGA is an algorithm, which generates output data on initial state basis.

Initial state of ARCFOUR is derived from internal state achieved after KSA and equals , where s is a permutation in internal state achieved after KSA.

At every moment of PRGA ARCFOUR turns into the new internal state and one output number Yt is generated:

where

- is addition modulo N operation,

- is a z-th number in permutation

- permutation composition operation in symmetric group

- is a transposition of x-th and y-th elements in symmetric group

- is identity permutation).

Let Zn be a set of possible internal states of Moore machine A,  is its transition function,  is its output function. Let B to be the Mealy machine, X is its input alphabet, ? is its state set,  are its partial transition functions,  are its partial output functions, Y is its output alphabet. We will use  to denote a B internal states sequence, derived from initial state ? and input sequence . c|u means c divides u.

We would remind that sequence b1,b2,…,bt,… of some alphabet elements is called periodic if there is a natural number d which fulfills the condition that  bt=bt+kd  for any natural numbers t, k. Minimal d that fulfills this condition is a period of the sequence.

Finite-state machine PRGA model is a consecutively connected machine A and B. Machine A input parameters are  . It’s clear, that ?=?. We should note, that if the initial state of machine A is i=0, then its output sequence is Q=1,2,…N-1,0,… with a period of N. Machine B parameters are

Further machine B with such parameters will be denoted as B*.

The initial state of PRGA is . So the output sequence is  and equals output sequence of machine B*, generated from the initial state (0,s0) and input sequence Q=1,2,…N-1,0,1,2….

We are interested in possible and impossible periods of B* output sequence ?(?). The information about B* internal state permutation  sequence ?(s) is also important. It’s clear that  ?(?)|?(s) and ?(s) divides internal state sequence period  of machine B* with internal state s0 and input sequence Q.

Statement 1. Sequences  are periodic.

Statement 1 proving. If we prove that B* internal state sequence  corresponded to initial state s0 is periodic we will prove the Statement 1. The proof that B* is a permutative machine (means that  are bijective) is enough to prove it.

Let’s prove that machine B* is permutative. Let’s assume that B* is not permutative machine. So for some input symbol  and some internal states (j,s), (j*,s*) from ZnxSn the equation  is true. So

It means that s=s* and consequently j=j*. It is a collision, which proves Statement 1.

Most valuable result of current article is contained in further theorem.

Theorem. If input sequence is Q=1,2,…N-1,0,1,2… then the permutation  sequence period  of machine B* is multiple of 2n-1 for any initial permutation S0. If inequality S0(1)≠1+2n-1 is satisfied for substitution S0 then the permutation  sequence period of machine B* is a multiple of N=2n.

We provide two lemmas in order to prove the theorem.

Lemma 1. There are two natural numbers n(1), n(2), which satisfy an(1)-bn(2)=d, for any two natural numbers a, b satisfied equality (a,b)=d.

Lemma 1 may be proven with the well-known statement about existence of two integers n(1), n(2)  fulfilled condition given above.

Let’s look at machine B defined earlier. Let B(?) be a connected component of machine B which contains state  is an output sequence of permutative machine  B with initial state ? and input sequence P. Denote Рj=х(j),х(j+1),…  forР=x(1),х(2),… .

Lemma 2.

Lemma 2 Proof. Machine B is permutative so for any machine B state ? and any periodic sequence P the output sequence B(?, P)=y1,y2,...yL, i,...s periodic.

Denote  further in this proof. It’s evident that if (w,W)=wthen lemma 2 is true.

Assume that (w,W)=d¹w. Let k is non-negative integer. In according to lemma 1 there are integers n(1), n(2) satisfied kn(1)w– kn(2)W=kd. So

Let’s choose natural number n(3) which fulfis the condition w|n(2)+n(3) and rewrite (1) (note that w(Pkd+1)=w):

So lemma 2 is proven too.

Let’s prove theorem 1. In order to apply lemma 2 to B* permutation  (generated from input sequence Q=1,2,…N-1,0,1,2,…) sequence period research we will review permutation  sequence of machine B* generated from input sequence Q=1,2,…N-1,0,1,2,… as output sequence of machine  differed from machine B* only by partial output functions  for any permutation . Let’s review internal states sequence  of machine  generated from initial state (0, So) and input sequence Q=1,2,…N-1,0,1,2,… with a period of N. Note that there is a shift of  output sequence

Equality (3) is possible just if  d=2-1. So the assumption (2n, W)=2m, m<n is possible just if S0(1)=1+2n-1.  The theorem is proven.

Literature:

1. Schneier, Bruce / «Applied cryptography Second Edition : protocols, algorithms, and source codes in C» / 1996.

2. Rivest, Ron L. «Ronald L. Rivest : FAQ» / MIT Computer Science and Artificial Intelligence Laboratory. http://people.csail.mit.edu/rivest/faq.html#Ron М. (30.08.2012).

The work is interesting

## Elena Artamonova

HOW TO UNDERSTAND: Kudiyarov Dmitry, postgraduate student, doctor of mathematical and physical sciences, full professor?

## Kudiyarov Dmitry

It's a site bug. The correct authors are: Alexander Babash, doctor, professor Russian State Social University, Russian Federation Dmitry Kudiyarov, postgraduate Russian State Social University, Russian Federation

## Elena Artamonova

By discussion: nondeterministic finite-state automata, deterministic finite-state automata, regular grammars, and regular expressions are all characterizations of the languages that finite-memory programs accept. Moreover, there are effective procedures for moving between the different characterizations. These procedures provide the foundation for many systems that produce finite-memory-based programs from characterizations of the previous nature.
The work is interesting

## Elena Artamonova

HOW TO UNDERSTAND: Kudiyarov Dmitry, postgraduate student, doctor of mathematical and physical sciences, full professor?

## Kudiyarov Dmitry

It's a site bug. The correct authors are: Alexander Babash, doctor, professor Russian State Social University, Russian Federation Dmitry Kudiyarov, postgraduate Russian State Social University, Russian Federation

## Elena Artamonova

By discussion: nondeterministic finite-state automata, deterministic finite-state automata, regular grammars, and regular expressions are all characterizations of the languages that finite-memory programs accept. Moreover, there are effective procedures for moving between the different characterizations. These procedures provide the foundation for many systems that produce finite-memory-based programs from characterizations of the previous nature.
PARTNERS

Would you like to know all the news about GISAP project and be up to date of all news from GISAP? Register for free news right now and you will be receiving them on your e-mail right away as soon as they are published on GISAP portal.