Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

The SN3 Stream Cipher

4 views
Skip to first unread message

Simeon Maltchev

unread,
Oct 17, 2002, 10:46:59 PM10/17/02
to


The SN3 Stream Cipher
---------------------

SN3 is a software-efficient stream cipher, optimized for execution on 32-bit
micro processors. It is designed around one key-dependent S-box, which
dynamically changes during the encryption process. Secret key is up to 768
bytes long. The keystream consists of 32-bit words and is generated
independently from the encrypted message. This algorithm can be used not only
as a stream cipher, but also as a general purpose pseudorandom number generator.

Algorithm description:
----------------------

The algorithm is designed with respect to be efficient for software
implementation. It uses only simple mixing operation like "xor" and cyclical
rotation and generates keystream, which is unbiased and uncorelated.

The S-box V (192 32-bit values) is conventionally divided into three equal
parts, named V1, V2 and V3, where V1 consists of the first 64 32-bit words
of V, V2 of the next 64 32-bit words of V, and V3 of the last 64 32-bit
words of V. Index i addresses only the V1 table, j only the V2 table and
m only the V3 table.

To generate the first 64 32-bit keystream words Ki (i = 1..64), do the following

10 steps repeatedly 64 times:

Note: "<<<" denotes cyclical left rotation;
">>" denotes non-arithmetical right shift;
"^" denotes exclusive bitwise or operation;

(Indexes i and j are initially set to zero.)

1. T1 = V1[i]
2. T2 = V2[j]
3. m = T1 mod 64
4. T3 = V3[m]

5. V1[i] = (T1 <<< 1) ^ T2
6. V2[j] = (T2 <<< 5) ^ T3 ^ 0x8c591ca1
7. V3[m] = (T3 <<< 17) ^ T1 ^ 0xab8ec254

8. i = (i + 1) mod 64
9. j = (T1 >> 8) mod 64

10. Ki = T1 ^ T2 ^ T3

After that, do a cyclical left rotation of S-box V on 64 32-bit words left and
continue to generate the next 64 keystream words.

Speed:
------
The cyclical rotation of S-box V, which is as far as I know a novel stream
cipher design pattern, may at first seem to be a time consuming operation,
but in fact it can be very easily and inexpensively implemented in software.
The assembler implementation of the algorithm takes about 19 inner processor
clocks (Intel Pentium processor class) to generate one 32 bit keystream value.
The C version given below, when compiled with speed optimizations, gives
usually 15 to 20 percents worse speed results.

Analysis:
---------
One important idea around which algorithm was built is that every internal seed
word, depending on which the current keystream word is generated, is changed
immediately after its use in a non-linear and unpredictable from the keystream
way. The next keystream word is a function of at least one inner seed word,
which is not a simple function of the seed's words used in the generation of
the previous one (keep in mind index i, which walks with step 1 via the V1
table). Another base idea is the combination of the cyclical rotation operations

in steps 5, 6 and 7 with the cyclical rotation of the S-box V, which allows
every particular bit of V to be mixed with every other bit of V. This has direct

relationship to the random properties of the generated keystream. Another
important point is that T1, T2 and T3 words are chosen form three different and
non-overlapping tables (V1, V2 and V3).

The values for the constants used in steps 5, 6 and 7 of the algorithm were
tuned by performing a lot of tests with George Marsaglia's 'DIEHARD' test suite
and with Bob Jenkins' chi.c program. With the chosen values, the algorithm
passed all tests with all examined initial seeds, even with all zeros, all ones
and similar bad seeds. This is not a proof for the security of the algorithm,
but it can be regarded as a necessary, but non-sufficient condition for such
a proof. Suggestions and opinions on how to improve the heuristical
determination of these values, and on the algorithm as a whole, are welcome.

Legal issues:
-------------

The SN3 algorithm is free and may be used for any legal purposes without
payment of royalties to the author.

Sources:
--------

The C Sources included below implement the algorithm given above and also
contain the key-expansion routine, although it is believed that the SN3
strength does not depend on it.


/* SN3 implementation. Public Domain. No warranty of any kind. */
/* Author: Simeon Maltchev, smal...@yahoo.com */

#include <stdio.h>
#include <string.h>

typedef unsigned long int u32;

#define TABLE_SIZE 64
#define SBOX_SIZE (3 * TABLE_SIZE)
#define INDEX_MASK (TABLE_SIZE - 1)

#define rotl(a, b) (((a) << ((b) & 31)) | ((a) >> (32 - ((b) & 31))))

u32 keystream[SBOX_SIZE];
u32 seed[SBOX_SIZE];

char *simple_key = "abcdefgh";

void sn3();
void init_seed(char *key, u32 key_len);
void print_keystream();

int main()
{
init_seed(simple_key, strlen(simple_key));

sn3();
print_keystream();

sn3();
print_keystream();

return 0;
}

/* Call this function to generate 192 random 32-bit values. */
void sn3()
{
u32 *v1, *v2, *v3, *temp;
u32 t1, t2, t3, i, m, k, n, n1, n2;
static u32 j = 0;

v1 = seed;
v2 = v1 + TABLE_SIZE;
v3 = v2 + TABLE_SIZE;
i = n = 0;
for (n1 = 0; n1 < 3; n1++)
{
for (n2 = 0; n2 < TABLE_SIZE; n2++)
{
t1 = v1[i];
t2 = v2[j];
m = t1 & INDEX_MASK;
t3 = v3[m];

k = t1 ^ t2 ^ t3;

v1[i] = rotl(t1, 1) ^ t2;
v2[j] = rotl(t2, 5) ^ t3 ^ 0x8c591ca1;
v3[m] = rotl(t3, 17) ^ t1 ^ 0xab8ec254;

i++;
i &= INDEX_MASK;
j = (t1 >> 8) & INDEX_MASK;

keystream[n++] = k;
}

temp = v1;
v1 = v2;
v2 = v3;
v3 = temp;
}
}

void init_seed(char *key, u32 key_len)
{
u32 i, j;
char *char_seed = (char *) seed;

for (i = j = 0; i < SBOX_SIZE*sizeof(u32); i++, j++)
{
if (j == key_len)
j = 0;
char_seed[i] = key[j];
}

sn3();
for (i = 0; i < SBOX_SIZE; i++)
seed[i] = rotl(seed[i], 19) ^ keystream[i];
}

void print_keystream()
{
u32 i;

for (i = 1; i <= SBOX_SIZE; i++) {
printf("%08x\t", keystream[i - 1]);
if (i % 4 == 0)
printf("\n");
}
printf("\n\n");
}


__________________________________________________
Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com


Tom St Denis

unread,
Nov 11, 2002, 11:38:25 AM11/11/02
to

[ I'm posting this here to start discussion, even though I don't
believe it is true that the stream cipher is linear. -- moderator ]


Simeon Maltchev <smal...@yahoo.com> wrote in message news:<uquth35...@corp.supernews.com>...

This cipher is horribly linear. Aside from the state of the V tables
there is no non-linearity in the design. Also 6x32 sboxes will tend
to be very linear as well [see Biham for references]. How you say
this is non-correlated is beyond me. The output is HIGHLY correlated
to the initial state of the V table.

Tom

Simeon Maltchev

unread,
Nov 17, 2002, 8:13:09 PM11/17/02
to


tomst...@yahoo.com (Tom St Denis) wrote in message news:<aqome1$dl0$1...@mozart.cs.berkeley.edu>...

> This cipher is horribly linear. Aside from the state of the V tables
> there is no non-linearity in the design. Also 6x32 sboxes will tend
> to be very linear as well [see Biham for references]. How you say
> this is non-correlated is beyond me.

I don't know what you mean under "liner cipher", but:
In the last weeks I produce the given below test results (which I
recently discuss with Bob Jenkins) of ISAAC and SN3 using DIEHARD
suite. I run the PRNG algorithms 100 times, starting from different
random seeds. After that, extract the p-values from all DIEHARD
tests and compute their average and sample standard deviation
(expected values are 0.5 and 0.289). The idea to make such one kind
of tests comes from here:
ftp://ftp.rsasecurity.com/pub/pdfs/bulletn8.pdf. I currently
prepare to post freely C sources via which these results was taken
and hope will be able to do this in few days - one source file must
be rewritten. Detailed description how to reproduce the given below
results and how to make similar tests not just for ISAAC or SN3, but
also for many other PRNG will be given. I hope these sources will
be very useful. Comments on the test results are desired and are
welcome. There is one interesting fact about Rank31x31 and Rank32x32
tests: for both algorithms (and also for KISS) tests produces
p-values only in range 0.32 to 0.999, which is whether something test
specific or more probably test bug - I suggest to don't regard these
two results. And it is hard for me to believe that DIEHARD will give
such test results for someone "linear" or "correlated" algorithm.


>The output is HIGHLY correlated to the initial state of the V table.

I probably don't understand rightly what exactly you mean - the output
of every one PRNG depends on it initial state. SN3 is tested starting
from all zero, all ones and similar initial states - it just pass all
DIEHARD tests.

Test results:


===== ISAAC test results set 1 ======

BirthdaySpacing.txt Average 0.503
BirthdaySpacing.txt Std Dev 0.283
=====================================
FivePermutations.txt Average 0.446
FivePermutations.txt Std Dev 0.341
=====================================
Rank31x31.txt Average 0.559
Rank31x31.txt Std Dev 0.209
=====================================
Rank32x32.txt Average 0.624
Rank32x32.txt Std Dev 0.210
=====================================
Rank6x8.txt Average 0.493
Rank6x8.txt Std Dev 0.286
=====================================
Missing20bitWords.txt Average 0.505
Missing20bitWords.txt Std Dev 0.288
=====================================
Missing10bitPairs.txt Average 0.508
Missing10bitPairs.txt Std Dev 0.288
=====================================
Missing5bitQuads.txt Average 0.496
Missing5bitQuads.txt Std Dev 0.289
=====================================
Missing2bitTens.txt Average 0.499
Missing2bitTens.txt Std Dev 0.289
=====================================
CountOnesAllBytes.txt Average 0.498
CountOnesAllBytes.txt Std Dev 0.291
=====================================
CountOnesSpecific.txt Average 0.530
CountOnesSpecific.txt Std Dev 0.296
=====================================
ParkingLot.txt Average 0.497
ParkingLot.txt Std Dev 0.287
=====================================
MinimumDistance.txt Average 0.497
MinimumDistance.txt Std Dev 0.284
=====================================
Smallest3DSphere.txt Average 0.502
Smallest3DSphere.txt Std Dev 0.285
=====================================
SqueezeIterations.txt Average 0.483
SqueezeIterations.txt Std Dev 0.303
=====================================
OverlappingSums.txt Average 0.500
OverlappingSums.txt Std Dev 0.283
=====================================
UpDownRuns.txt Average 0.501
UpDownRuns.txt Std Dev 0.306
=====================================
CrapsGame.txt Average 0.519
CrapsGame.txt Std Dev 0.291
=====================================


===== ISAAC test results set 2 ======

BirthdaySpacing.txt Average 0.505
BirthdaySpacing.txt Std Dev 0.281
=====================================
FivePermutations.txt Average 0.433
FivePermutations.txt Std Dev 0.350
=====================================
Rank31x31.txt Average 0.593
Rank31x31.txt Std Dev 0.211
=====================================
Rank32x32.txt Average 0.586
Rank32x32.txt Std Dev 0.219
=====================================
Rank6x8.txt Average 0.507
Rank6x8.txt Std Dev 0.286
=====================================
Missing20bitWords.txt Average 0.501
Missing20bitWords.txt Std Dev 0.285
=====================================
Missing10bitPairs.txt Average 0.506
Missing10bitPairs.txt Std Dev 0.291
=====================================
Missing5bitQuads.txt Average 0.488
Missing5bitQuads.txt Std Dev 0.287
=====================================
Missing2bitTens.txt Average 0.498
Missing2bitTens.txt Std Dev 0.288
=====================================
CountOnesAllBytes.txt Average 0.519
CountOnesAllBytes.txt Std Dev 0.270
=====================================
CountOnesSpecific.txt Average 0.536
CountOnesSpecific.txt Std Dev 0.288
=====================================
ParkingLot.txt Average 0.501
ParkingLot.txt Std Dev 0.288
=====================================
MinimumDistance.txt Average 0.490
MinimumDistance.txt Std Dev 0.293
=====================================
Smallest3DSphere.txt Average 0.506
Smallest3DSphere.txt Std Dev 0.284
=====================================
SqueezeIterations.txt Average 0.512
SqueezeIterations.txt Std Dev 0.283
=====================================
OverlappingSums.txt Average 0.494
OverlappingSums.txt Std Dev 0.289
=====================================
UpDownRuns.txt Average 0.498
UpDownRuns.txt Std Dev 0.294
=====================================
CrapsGame.txt Average 0.547
CrapsGame.txt Std Dev 0.284
=====================================


===== SN3 test results set 2 ========

BirthdaySpacing.txt Average 0.515
BirthdaySpacing.txt Std Dev 0.288
=====================================
FivePermutations.txt Average 0.486
FivePermutations.txt Std Dev 0.347
=====================================
Rank31x31.txt Average 0.589
Rank31x31.txt Std Dev 0.209
=====================================
Rank32x32.txt Average 0.560
Rank32x32.txt Std Dev 0.196
=====================================
Rank6x8.txt Average 0.490
Rank6x8.txt Std Dev 0.292
=====================================
Missing20bitWords.txt Average 0.513
Missing20bitWords.txt Std Dev 0.285
=====================================
Missing10bitPairs.txt Average 0.515
Missing10bitPairs.txt Std Dev 0.288
=====================================
Missing5bitQuads.txt Average 0.498
Missing5bitQuads.txt Std Dev 0.289
=====================================
Missing2bitTens.txt Average 0.501
Missing2bitTens.txt Std Dev 0.287
=====================================
CountOnesAllBytes.txt Average 0.489
CountOnesAllBytes.txt Std Dev 0.279
=====================================
CountOnesSpecific.txt Average 0.525
CountOnesSpecific.txt Std Dev 0.289
=====================================
ParkingLot.txt Average 0.504
ParkingLot.txt Std Dev 0.288
=====================================
MinimumDistance.txt Average 0.502
MinimumDistance.txt Std Dev 0.291
=====================================
Smallest3DSphere.txt Average 0.505
Smallest3DSphere.txt Std Dev 0.288
=====================================
SqueezeIterations.txt Average 0.496
SqueezeIterations.txt Std Dev 0.297
=====================================
OverlappingSums.txt Average 0.497
OverlappingSums.txt Std Dev 0.285
=====================================
UpDownRuns.txt Average 0.524
UpDownRuns.txt Std Dev 0.282
=====================================
CrapsGame.txt Average 0.505
CrapsGame.txt Std Dev 0.283
=====================================


===== SN3 test results set 2 ========

BirthdaySpacing.txt Average 0.519
BirthdaySpacing.txt Std Dev 0.287
=====================================
FivePermutations.txt Average 0.483
FivePermutations.txt Std Dev 0.340
=====================================
Rank31x31.txt Average 0.628
Rank31x31.txt Std Dev 0.206
=====================================
Rank32x32.txt Average 0.608
Rank32x32.txt Std Dev 0.212
=====================================
Rank6x8.txt Average 0.503
Rank6x8.txt Std Dev 0.292
=====================================
Missing20bitWords.txt Average 0.502
Missing20bitWords.txt Std Dev 0.290
=====================================
Missing10bitPairs.txt Average 0.507
Missing10bitPairs.txt Std Dev 0.285
=====================================
Missing5bitQuads.txt Average 0.507
Missing5bitQuads.txt Std Dev 0.289
=====================================
Missing2bitTens.txt Average 0.502
Missing2bitTens.txt Std Dev 0.288
=====================================
CountOnesAllBytes.txt Average 0.517
CountOnesAllBytes.txt Std Dev 0.304
=====================================
CountOnesSpecific.txt Average 0.536
CountOnesSpecific.txt Std Dev 0.292
=====================================
ParkingLot.txt Average 0.507
ParkingLot.txt Std Dev 0.280
=====================================
MinimumDistance.txt Average 0.508
MinimumDistance.txt Std Dev 0.293
=====================================
Smallest3DSphere.txt Average 0.507
Smallest3DSphere.txt Std Dev 0.292
=====================================
SqueezeIterations.txt Average 0.506
SqueezeIterations.txt Std Dev 0.321
=====================================
OverlappingSums.txt Average 0.506
OverlappingSums.txt Std Dev 0.283
=====================================
UpDownRuns.txt Average 0.503
UpDownRuns.txt Std Dev 0.299
=====================================
CrapsGame.txt Average 0.486
CrapsGame.txt Std Dev 0.286
=====================================

Simeon Maltchev

unread,
Nov 27, 2002, 12:16:42 AM11/27/02
to

The C Sources, mentioned in my previous post, can be found here:
http://www.geocities.com/smaltchev/dmt.tar.gz
0 new messages