357 views

Skip to first unread message

Dec 8, 1997, 3:00:00â€¯AM12/8/97

to

THE SCOP STREAM CIPHER

by Simeon V. Maltchev

Peter T. Antonov

ABSTRACT

This paper describes a software-efficient encryption algorithm

named SCOP. SCOP is a stream cipher specially designed for

optimal software performance on the Intel Pentium processor. The

computational cost of SCOP on this processor is 1.5 clock cycles

per byte of text. The cipher is designed around one key-dependent

S-box, one part of which dynamically changes during the encryption

process and the other part is static. The cipher works in internal-

feedback mode (IFB). The keystream consist of 32-bit words and is

generated independently from the encrypted message.

Key words -- Cryptography, Encryption, Fast encryption, Intel

Pentium Processor, Software encryption, Stream cipher.

INTRODUCTION

In the last few years the software-optimized cryptography is a

subject of active investigations. In 1991 Merkle described the

advantages of the encryption functions designed for software

implementation and he proposed a suite of three software-efficient

algorithms (two block ciphers named Khufu and Khafre, and a one-

way hash function named Snefru) [3].

In this paper we will discuss the software-efficient stream ciphers.

Such algorithms are SEAL [4], designed by Rogaway and

Coppersmith, RC4 [5] designed by Rivest, WAKE [5] designed by

Wheeler.

The advent of the Pentium processor established new rules for

designing encryption algorithms. Some of them are discussed in [6].

In [1] and [6] is shown that carefully coded implementations of some

of the encryption algorithms, designed without Pentium in mind, are

able to exploit his superscalar architecture almost to its maximum.

As it is shown above SCOP is specially designed to run on Pentium,

but he also can run very fast on other 32-bit processors. SCOP is

also designed to meet the following criteria:

* Work in IFB mode -- the keystream is generated independently

from the encrypted message.

* Compactness -- SCOP can run in less than 2.5 Kbytes of memory.

* Simplicity of software implementation -- SCOP uses only simple

operations like addition and subtraction modulus 2**32 (** ->

power) and table lookup.

* Variable security -- SCOP is a variable-key-size algorithm, with a

key size up to 384 bits.

SCOP is optimized for applications in which the key does not

change very often, e.g. a crypto-channel between two machines or a

file encryption/decryption program.

DESCRIPTION OF THE ALGORITHM

SCOP is a stream cipher working in IFB mode and uses a variable

size key. The keystream consist of 32-bit words and is independent

from the encrypted message. The algorithm has two parts: key

expansion and data encryption. The first one converts the key,

which is up to 48 bytes long, into an array of 1540 bytes.

The main operation used in the cipher is arithmetical addition of 32-

bit words. The additional operations are 4 table lookups, which are

performed for every word to be encrypted.

SCOP uses one 32-bit S-box (named V) with 384 entries, two 8-bit

indexes i and j, and three 32-bit temporary variables T1, T2 and T3.

The S-box V is conventionally divided into two parts: the first 128 32-

bit words of V form the first part which is static, and the next 256 32-

bit word of V form the second part which changes during the

encryption process. The index j addresses only the variable part,

while index i addresses the static part and the first half of the

changing part (the first 128 32-bit words of the changing part).

The S-box V is initialized with the first 1536 bytes of the expanded

key. The next three bytes of the expanded key are used to initialize

the indexes i and j, and the temporary variable T3 (the higher 24 bits

of T3 are initialized to 0). The usage of the last one byte of the

expanded key is a bit special: just the lower 7 bits of it are used.

They index a word into the static part of the S-box V. This word is

made to be odd without regard whether it is odd before that or not.

The 32-bit keystream word K is generated by the following steps:

1. T1 = V[128 + j]

2. j = (j + T3) mod 256

3. T2 = V[128 + j]

4. T3 = V[128 + j] + V[i]

5. V[128 + j] = T3

6. i = (i + 1) mod 256

7. j = (j + T2) mod 256

8. K = T1 + T2

K is added to the plaintext word to produce the ciphertext word or is

subtracted from the ciphertext word to produce the plaintext word.

Key Expansion

The main goal of the cipher design was the data encryption part of

the algorithm. On the preprocessing of the key to the array less

attention was paid. The array has no special properties and can be

regarded as an array of random numbers. For completeness,

definition of the key expansion part of the algorithm is given in

Appendix A.

DESIGN PRINCIPLES OF THE ALGORITHM

The main idea of the SCOP design is to use one or more S-boxes,

which are generated depending on the key and change dynamically

during the encryption process, in a manner, which can not be

determined from the generated keystream (IFB mode). The goal is

to make difficult to determine the internal state of the cipher and to

prevent crypto-attacks designed for fixed and static S-boxes.

To achieve high performance, the number of operations necessary

to implement the above idea must be minimized. Variants with one

or two S-boxes, as well as with one or two index variables are

considered.

Algorithm is designed with respect to the following security

requirements:

1. Every word from the S-box which changes during the

encryption, has to be changed in a way, which can not be

determined from the generated keystream (IFB mode).

2. Having in mind, that the i-th word (Ki) of the keystream is

function of a part of the i-th internal state (pISi) of the

keystream generator, then the pISi must be changed

immediately after computing the value of Ki.

3. The change in the values of the indexes of the S-box words,

that form the keystream, must be done in a way, which can

not be determined from the generated keystream, and the

values of these indexes must not form short cycles.

4. An internal state of the keystream generator after which it is

possible to generate only such numbers, the n-th bit of

which is always 0 or always 1 (in particular, only even or only

odd numbers), must be impossible to happen.

These security requirements of the algorithm will be explained

below.

Some performance-related design principles of the algorithm are

given:

1. Use of only simple operations. In the cipher are used

instructions only from the following types:

mov reg, reg; mov mem, reg; mov reg, mem;

add reg, reg; add reg, imm;

sub reg, reg; sub reg, imm;

2. The width of S-box word is equal to the width of processor

register. The width of indexes is chosen to be 8 bits having

in mind that the general-purpose registers EAX, EBX, ECX,

EDX give direct access to their lower 8 bits: AL, BL, CL, DL.

3. An additional effect from using some of the registers AL, BL,

CL, DL for storing of the indexes is the simplified realization

of steps 2, 6 and 7 of algorithm, i.e. these steps are coded

with only one addition instruction (the mask instruction AND

is not necessary).

4. The instruction sequence considered with regard to the

Pentium s abilities for concurrent instructions execution. As

will be shown below SCOP uses 100 % of those abilities.

EXPALANATION OF THE SECURITY REQUIRMENTS OF THE ALGORITHM

We believe that security requirements 1, 2 and the first part of

requirement 3 are general security requirements, which must be

implemented by all ciphers which uses variable S-box and work in

IFB mode.

The last part of security requirement 3 is fairly complex. It is of

critical importance for the cipher security, because the forming of

short cycles by the values of the indexes will cause the forming of

such cycles by the values of the generated keystream words. It is

hard to give a mathematical proof that the values of the indexes will

not form short cycles. Design heuristics will be explained.

One of the most important points of the algorithm is whether it is

secure if none of the indexes is altered through a constant

(regarding that when encrypting each plaintext word, in the

processor registers the values of T1, T2, S-box word indexed by i,

T3, i and j are loaded or calculated, then the new values of the

indexes can be formed as a function of some of these values). Two

basic variants of the algorithm are considered.

In the first variant only one entirely changing S-box (named V) is

used. In this variant there is one simple internal state of the

keystream generator after which it is possible to generate only

zeros: i = j = 0 and V[0] = 0. This seems to be a common problem

for all algorithms with similar design. Because of this problem this

variant of the algorithm should be discarded as not secure.

In the second variant of the algorithm two S-boxes are used. The

first S-box is entirely static (named C) and the second S-box is

entirely changing (named V). Index i is used for addressing words

only in the static S-box, and index j - only in the variable S-box. The

goal of the static S-box C is that it is possible to be guaranteed in

the key expansion part of the algorithm that C[0] # 0, which can be

used to solve the above problem.

It can be ascertained that it is possible to come to a cycle, not only

when C[0] = 0, but also when in C there are words the lower 8 bits of

which are zeros. To avoid these cycles there should not be such

words in C. In principle this is not difficult to be guaranteed by the

key expansion part of the algorithm, but the further investigations

showed that similar cycles are possible when the lower 8 bits of

certain words in C are a power of 2, e.g. 128. The absence of such

words can also be guaranteed by the key expansion part of the

algorithm, but on the whole this variant of the algorithm does not

seem to be very reliable.

Depending on the above problems is made the decision one of the

indexes to be altered through a constant. In the presented algorithm

the value of the constant is chosen to be 1, but it is quite possible to

choose any other number, which is a 255 divisor, e.g. 3, 5, 15, 17, ...,

51, 85, 255 (the index is 8 bit wide, so 255 = 2**8 - 1).

The security requirement 4 is not widely used principle of the design

of ciphers which use changing S-box, but we consider it is most

important for the cipher security.

The decision, that one of the indexes will be altered through a

constant makes the static S-box needless. So we can consider the

following working variant of the algorithm:

V - variable 32-bit S-box with 256 entries

i, j - 8-bit indexes

1. T1 = V[j]

2. j = (j + T3) mod 256

3. T2 = V[j]

4. T3 = V[j] + V[i]

5. V[j] = T3

6. i = (i + 1) mod 256

7. j = (j + T2) mod 256

8. K = T1 + T2

The critical step of this variant of the algorithm is step 4. Depending

on whether the addends which take part in it are even or odd, the

following cases are possible:

N: V[j] V[i] T3

--------------------------------------------

1. even + even = even

2. odd + even = odd

3. even + odd = odd

4. odd + odd = even

The first two cases are not interesting, because in them the

proportion between the even and the odd numbers in the S-box

does not change. This is not true for the last two cases. In the third

case in the S-box appears a new odd number, in the fourth - a new

even number.

The disappearing of the even numbers from the keystream is not

possible, because even if in a certain moment there are only odd

numbers in the S-box, the next generated keystream word, as well

as the next number to appear in the S-box (word T3) will be even.

The disappearing of the odd numbers from the keystream is

possible yet. If in a certain moment there are only even numbers in

the S-box, no odd keystream word will be generated any more. The

happening of such internal state is quite possible: only one odd

number is left in the S-box, and it is the word T2 for the current

encryption iteration, and i is equal to j. Then this number will be

added to itself and an even number will take its place.

Note that the solving of the problem with the disappearing of the

odd numbers from the S-box and respectively from the keystream,

will fully satisfy security requirement 4, because when two odd

numbers are added (arithmetical addition), there is a carry from the

lowest bits (these at position 0) to the next higher bits (these at

position 1), which means that the 1s can not disappear from position

1, and by analogy, the same is true for the bits at position 2, 3, 4,

..., 30, 31.

The main conclusion that can be drawn is that the variants of the

algorithm, in which only one variable S-box is used, are not quite

reliable, because of the possibility of the disappearing of the odd

numbers in the generated keystream. Here is implied that the

change of the S-box is such that a new number, probably not

present in the S-box, is created and a certain number in the S-box is

replaced with it. If the change consists only in the transposition of

the numbers in the S-box, the problem does not exist. Unfortunately

such a technique of alteration through transposition is not quite

applicable for generators that create keystream of 32-bit words,

because it should be possible for each 32-bit value to appear in it,

i.e. the S-box should consist of 2**32 32-bit words (16 GB).

An adequate solution for the problem is to use two S-boxes, just as

it is described above at the discussion of security requirement 3. To

prevent the disappearing of the odd numbers from the S-box and

respectively from the keystream it is enough to have at least one

odd number in the static S-box. This can be easily guaranteed by

the key expansion part of the encryption algorithm.

A potential problem of such a variant of the algorithm, compared to

the variant with only one variable S-box is that the word, which will

be added to V[j] (T2) in step 4 will be the same after each 256

encryption iterations, because C is static and the value of index i

changes in a cycle with period 256. This is probably not a serious

flaw, because after 256 iterations the word that will be T2 for the

current iteration will have with high probability different index and

different value.

This flaw can be partially compensated if two S-boxes are used,

which partially overlap, or in other words, one S-box which is

conventionally divided into two parts: the first part is static, the

second one changes during the encryption process. One of the

indexes addresses only the variable part (this is index j in our case),

while the other index addresses the static part and the first portion

of the changing part (this is index i in our case).

In this case the algorithm works in two different modes, as two

different algorithms: when index i addresses the static part, the

algorithm works as in the case with two separate S-boxes, and when

it addresses the variable part - as in the case with one variable S-

box. To prevent the disappearing of the odd numbers from the

keystream, it is enough to have at least one odd number in the static

part of the S-box, which can be easily guaranteed by the key

expansion part of the encryption algorithm.

When the static part of the S-box is of length 128 words, the

algorithm performs the same number of iterations in its two different

modes. But it is quite possible to choose a length different from 128.

The minimum allowed length is of 1 word, the value of which should

be odd.

Note that it is impossible zeros or ones that disappear from any bit-

position of the values of index j, because the value of j is addition

function of words of the S-box. This has direct relationship to the

problem with the forming of short cycles by the values of this index.

The security requirement 4, which is fully satisfied, and the

technique used for that, are some of the main features of the

presented in this paper encryption algorithm.

PERFORMANCE

The inner loop of SCOP can be coded with 15 instructions on every

32-bit processor, which has at least 6 registers and which has

instructions for: moving data from memory to register and from

register to memory; adding and subtracting of two registers; adding

register with immediate value and subtracting immediate value from

register; mask register with immediate value (AND instruction). If the

processor has registers (at least 4) which give direct access to their

lower 8 bits, like AL for EAX, the three mask instructions become

needless and the algorithm can be coded with 12 instructions. Note

that these 12 instructions include two instructions for reading and

writing from/to processing plaintext/ ciphertext stream and one

instruction for combining plaintext with keystream. These 12

instructions can be executed for at least 6 clocks on Pentium, which

is fully achieved. There are no AGI stalls, imperfect pairs or

problems with loop-unrolling (of course, there will be performance

penalty when the encrypting buffer or the internal table of SCOP are

out of on-chip cache). This means that SCOP encrypts data at 1.5

Pentium clocks per byte. So we can say that SCOP uses 100% of

the Pentium s abilities for concurrent instructions execution.

According to the performance times of SEAL [4] and RC4 [5]

presented in [6], SCOP is about 2.5 times faster than SEAL and

about 4.5 times faster than RC4. Having in mind, that there is no

matter on which kind of Pentium processor SCOP is running (i.e.

Pentium without MMX, Pentium with MMX, Pentium Pro or Pentium

II) we can say that this is the other main feature of the presented in

this paper encryption algorithm.

CONCLUDING REMARKS

It is easy to modify SCOP to get a cipher optimized for 64-bit

architectures. The inner table would be twice as wide. This would

nearly double the cipher s speed. It is also interesting to implement

the cipher using the new advantages of the Intel s MMX technology.

It is unclear whether security would be impacted in these cases.

One thing that the presented paper shows is that it is possible to

build a secure software-optimized cipher which is not closed, i.e. it

can run on a wide class of processors, but which also take the full

advantages of some particular hardware technology.

LEGAL ISSUES

The SCOP encryption algorithm may be used for any legal purpose

without payment of royalties to the author. The SCOP encryption

algorithm is the same as the encryption algorithm presented in [2]

with little changes in the key expansion part of the algorithm.

REFERENCES

1. A. Bosselaers, R. Govaerts, J. Vandewalle, Fast hashing on the

Pentium,

ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/bosselae/pentium.ps.gz

2. S. Maltchev, Analysis and software implementation of encryption

methods for communications protection, Master's Thesis at the

Technical University of Varna, Bulgaria, Summer 1997. Language:

Bulgarian.

3. R. Merkle, Fast software encryption functions,

ftp://rpub.cl.msu.edu/pub/crypt/docs/merkle-khufu-khafre-snefru.txt

4. P. Rogaway and D. Coppersmith, A software-optimized encryption

algorithm, http://www.cs.ucdavis.edu/~rogaway/papers/seal.ps

5. B. Schneier, Applied Cryptography, Second Edition: Protocols,

Algorithms, and Source Code in C, John Wiley & Sons, Inc., 1996.

6. B. Schneier and D. Whiting, Fast software encryption: Designing

encryption algorithms for optimal software speed on the Intel Pentium

processor, http://www.counterpane.com/fast_software_encryption.ps.zip

APPENDIX A

The key expansion part of the algorithm is based on one-way hash

function GP8.

Description of GP8:

GP8 consists of 8 polynoms of type:

Y = a*X**4 + b*X**3 + c*X**2 + d*X + 1, where:

- a, b, c and d are 8-bit numbers;

- X is 16-bit number;

- Y is 32-bit number.

Let us denote the first polynom with P0, the second with P1 and so

on, the eight with P7.

The hash value generated by GP8 is 128-bit and is computed in the

way described below. The eight 16-bit X values form the "internal

state" of the function, which is also a 128-bit number.

First, the key is expanded to 384 bits (48 bytes), using the algorithm

given below. The first 32 bytes of them are used for determining of

all 32 polynom coefficients and the next 16 bytes determine the initial

8 16-bit X values, i.e. the initial internal state of the function. The

output of the i-th polynom (32-bit Yi) is regarded as two 16-bit

numbers, where the lower 16 bits form the i-th 1/8 part of the

generated by GP8 hash value, and the higher 16 bits form 1/8 part of

the internal state which will be used by the function to generate the

next hash value, i.e. the input X for the polynom No. (i + 1) mod 8.

The initial expansion of the key to 48 bytes is done by the following

algorithm:

If k is the length of the key in bytes (k < 48), the i-th byte Pi

(k <= i <= 48) is calculated:

P[i] = P[i - k] + P[i - k + 1]

Next the zero bytes are removed, if there are such bytes in the first

32 bytes of these 48 bytes. To do this all bytes from the first to the

32-th byte are processed, and the first encountered 0 is replaced

with 1, the second one with 2, etc.

The key expansion algorithm is:

1. Initially 8 hash values are generated which are not used.

2. Then 8 hash values are generated (128 bytes). After that 1 hash

value is generated that is not used. These two steps are repeated 12

times and 1536 bytes are generated at all.

3. Finally, 1 hash value is generated from which only the 4 higher

bytes are used.

Totally 117 calls to GP8 are needed during the key expansion.

*********************************************************************

* Simeon V. Maltchev *

* E-Mail: smal...@yahoo.com *

* PGP-Fingerprint: 77 EA 58 22 D4 68 28 41 E6 CB B8 44 F6 CD FA 90 *

*********************************************************************

*********************************************************************

* Peter T. Antonov *

* E-Mail: anto...@tu-varna.bg *

*********************************************************************

SOURCES

/* Demo program of SCOP */

/* The original implimentation of data encryption part of SCOP (

functions encrypt/decrypt) is in Intel Assembler. Following are

given a partially optimized C versions of these functions.

SCOP is tested with MSVC 4.1 and 5.0, and with gcc 2.7.x.

Please be careful with Borland's 32-bit C compiler. Read the

comment in the encrypt/decrypt functions. */

#include <stdio.h>

#include <assert.h>

#define MESSAGE_WORDS 1024

typedef struct {

unsigned long v[384];

unsigned char i;

unsigned char j;

unsigned char t3;

} st_key;

typedef struct {

unsigned char coef[8][4];

unsigned long x[4];

} st_gp8;

st_key kt;

st_gp8 int_state;

unsigned long buf[MESSAGE_WORDS];

static void gp8 (unsigned long *out);

static void

expand_key (unsigned char *in, unsigned in_size)

{

unsigned i;

unsigned char *p;

unsigned char counter;

assert (in_size >= 2 && in_size <= 48);

p = (unsigned char *) &int_state;

for (i = 0; i < in_size; i++)

p[i] = in[i];

for (i = in_size; i < 48; i++)

p[i] =(unsigned char) (p[i - in_size] + p[i - in_size + 1]);

counter = 1;

for (i = 0; i < 32; i++)

{

if (p[i] == 0)

p[i] = counter++;

}

}

void

init_key (unsigned char *in, unsigned in_size)

{

unsigned long odd;

unsigned long t[4];

int i, j;

expand_key (in, in_size);

for (i = 0; i < 8; i++)

gp8 (t);

for (i = 0; i < 12; i++)

{

for (j = 0; j < 8; j++)

gp8 (kt.v + i * 32 + j * 4);

gp8 (t);

}

gp8 (t);

kt.i = (unsigned char) (t[3] >> 24);

kt.j = (unsigned char) (t[3] >> 16);

kt.t3 = (unsigned char) (t[3] >> 8);

odd = t[3] & 0x7f;

kt.v[odd] |= 1;

}

/* partially optimized version */

static void

gp8 (unsigned long *out)

{

unsigned long y1, y2, x_1, x_2, x_3, x_4;

unsigned long newx[4];

int i, i2;

for (i = 0; i < 8; i += 2)

{

i2 = i >> 1;

x_1 = int_state.x[i2] >> 16;

x_2 = x_1 * x_1;

x_3 = x_2 * x_1;

x_4 = x_3 * x_1;

y1 = int_state.coef[i][0] * x_4 +

int_state.coef[i][1] * x_3 +

int_state.coef[i][2] * x_2 +

int_state.coef[i][3] * x_1 + 1;

x_1 = int_state.x[i2] & 0xffffL;

x_2 = x_1 * x_1;

x_3 = x_2 * x_1;

x_4 = x_3 * x_1;

y2 = int_state.coef[i + 1][0] * x_4 +

int_state.coef[i + 1][1] * x_3 +

int_state.coef[i + 1][2] * x_2 +

int_state.coef[i + 1][3] * x_1 + 1;

out[i2] = (y1 << 16) | (y2 & 0xffffL);

newx[i2] = (y1 & 0xffff0000L) | (y2 >> 16);

}

int_state.x[0] = (newx[0] >> 16) | (newx[3] << 16);

int_state.x[1] = (newx[0] << 16) | (newx[1] >> 16);

int_state.x[2] = (newx[1] << 16) | (newx[2] >> 16);

int_state.x[3] = (newx[2] << 16) | (newx[3] >> 16);

}

/* partially optimized version */

void

encrypt (unsigned long *buf, int buflen, st_key *skey)

{

unsigned char i, j;

unsigned long t1, t2, t3;

unsigned long k, t;

unsigned long *word, *v;

i = skey->i;

j = skey->j;

t3 = skey->t3;

v = skey->v;

word = buf;

while (word < buf + buflen)

{

t1 = v[128 + j];

j += t3;

t = v[i];

t2 = v[128 + j];

/* If you want to compile with Borland's 32-bit C compiler using

optimizations, change the line below to:

i = (i + 1) & 255; */

i++;

t3 = t2 + t;

v[128 + j] = t3;

j += t2;

k = t1 + t2;

*word++ += k;

}

}

/* partially optimized version */

void

decrypt (unsigned long *buf, int buflen, st_key *skey)

{

unsigned char i, j;

unsigned long t1, t2, t3;

unsigned long k, t;

unsigned long *word, *v;

i = skey->i;

j = skey->j;

t3 = skey->t3;

v = skey->v;

word = buf;

while (word < buf + buflen)

{

t1 = v[128 + j];

j += t3;

t = v[i];

t2 = v[128 + j];

/* If you want to compile with Borland's 32-bit C compiler using

optimizations, change the line below to:

i = (i + 1) & 255; */

i++;

t3 = t2 + t;

v[128 + j] = t3;

j += t2;

k = t1 + t2;

*word++ -= k;

}

}

void

main (void)

{

unsigned char key[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,

14, 15};

unsigned long t;

int i, flag;

printf ("1\n");

init_key (key, sizeof (key));

printf ("2\n");

for (i = 0; i < MESSAGE_WORDS; i++)

buf[i] = 0L;

printf ("3\n");

encrypt (buf, MESSAGE_WORDS, &kt);

printf ("4\n");

t = 0L;

for(i = 0; i < MESSAGE_WORDS; i++)

t ^= buf[i];

printf ("XOR of buf is %08lx.\n",t);

init_key (key, sizeof (key));

decrypt (buf, MESSAGE_WORDS, &kt);

flag = 0;

for (i = 0; i < MESSAGE_WORDS; i++)

{

if (buf[i] != 0L)

flag = 1;

}

if (flag)

printf ("Decrypt failed.\n");

else

printf ("Decrypt succeeded.\n");

}

_________________________________________________________

DO YOU YAHOO!?

Get your free @yahoo.com address at http://mail.yahoo.com

Dec 10, 1997, 3:00:00â€¯AM12/10/97

to

The SCOP stream cypher recently posted to sci.crypt.research adds the

output of a keyed CPRNG to the plaintext stream in 32-bit words. This

generator is biased: the word output is even 1/512 too often.

This is because each output word is always the sum of two entries from

a 256-entry table. One time in 256, the same entry will be used

twice, forcing the output word to be even.

This means that the cypher as a whole leaks a little information about

the bottom bit of each plaintext word. I include a (short) program to

demonstrate the bias.

__

\/ o\ pa...@hedonism.demon.co.uk \ /

/\__/ Paul Crowley -+- DATA IS SACRED /~\

/* Program to demonstrate information leak in SCOP stream cypher.

* This program adapted from sources posted to sci.crypt.research.

* Copy my work freely; if you want to modify it, remove my name or

* ask me.

*

* The code isn't incredibly pretty, but I've generally avoided

* changing the original sources where I can.

*

* Paul Crowley, Tuesday 8 December 1997

* mailto:pa...@hedonism.demon.co.uk

* http://www.hedonism.demon.co.uk/paul/

*/

/* The original implimentation of data encryption part of SCOP (

functions encrypt/decrypt) is in Intel Assembler. Following are

given a partially optimized C versions of these functions.

SCOP is tested with MSVC 4.1 and 5.0, and with gcc 2.7.x.

Please be careful with Borland's 32-bit C compiler. Read the

comment in the encrypt/decrypt functions. */

#include <stdio.h>

#include <assert.h>

typedef struct {

unsigned long v[384];

unsigned char i;

unsigned char j;

unsigned char t3;

} st_key;

typedef struct {

unsigned char coef[8][4];

unsigned long x[4];

} st_gp8;

st_key kt;

st_gp8 int_state;

static void

count_evens (st_key *skey, long count, long *results)

{

unsigned char i, j;

unsigned long t1, t2, t3;

unsigned long k, t;

unsigned long *v;

i = skey->i;

j = skey->j;

t3 = skey->t3;

v = skey->v;

while (count--)

{

t1 = v[128 + j];

j += (unsigned char)t3;

t = v[i];

t2 = v[128 + j];

/* If you want to compile with Borland's 32-bit C compiler using

optimizations, change the line below to:

i = (i + 1) & 255; */

i++;

t3 = t2 + t;

v[128 + j] = t3;

j += (unsigned char)t2;

k = t1 + t2;

results[k & 1]++;

}

}

void

main (void)

{

unsigned char key[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

unsigned long results[2];

int i;

printf ("Scheduling key\n");

init_key (key, sizeof (key));

printf ("Counting even numbers\n");

results[0] = 0; results[1] = 0;

for (i = 0; i < 10; i++) {

count_evens(&kt, 5000000, results);

printf("Even: %ld Odd: %ld\n", results[0], results[1]);

}

}

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu