Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:11:01
Mok-Kong Shen (mok-kong.shen@stud.uni-muenchen.de)
Mon, 24 Aug 1998 18:48:57 +0100
A couple of comments received sometime ago have rightly criticized
the absence of an appropriate summary of the rationale of design
of my encryption algorithm WEAK3. I am taking the liberty of
presenting it below.
Hopefully this would lead to additional comments and critiques.
M. K. Shen
________________________________________________
The system can be divided into two cleanly separated units, the first
being a compound PRNG producing real-valued pseudo-random numbers in
the range [0, 1) and the second being the encryption processing part
that utilizes the output from the compound PRNG in diverse different
ways.
We start with one standard PRNG that is known to have good statistical
properties. (I use the one by Park and Miller. I don't use more than
one of these, in order to simplify the programming of the user. See
below.) Using a number of seeds we obtain a corresponding number of
pseudo-random number sequences. These are drawn upon in round robin
fashion to fill a shuffling buffer (of Bays and Durham, see the book
of Knuth). This output, from which the origin of each element (i.e.
the particular sequence to which it belongs) is difficult to identify,
since their order is mixed up through the shuffling process, is then
post-processed with addition mod 1. (Two successive numbers output
from the shuffling buffer are added mod 1, which is a method first
employed by Wichmann and Hill to obtain better statistical qualities
from outputs of a number of PRNGs but is used by us here mainly for
the purpose of enhancing complexity against analysis. This method
will be used a second time below.) This assures that it is quite hard
for the analyst to go backwards from the resulting output to infer the
seeds (of the standard PRNG) which together form the key of the system.
Note that the user decides how many seeds are to be used, meaning that
a very large effective key can be employed to defeat any brute force
attempts.
The sequence of pseudo-random numbers thus obtained is not directly
used for encryption in WEAK3 (in contrary to WEAK1 where it is so
used), but only employed to construct the constituent generators of
the compound PRNG which delivers, after it is fully built, all
pseudo-random numbers needed in the encryption process. The number
of constituent generators of the compound PRNG is user determined and
is practically unlimited. So the state of the compound PRNG can be
arbitrarily huge. Since the algorithm of the compound PRNG (see
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper9 for details) is
such that its constituent generators are fairly randomly activated,
there appears to be not of much value to pass the output of the
compound PRNG through any shuffling buffer as is done above with the
output of the standard PRNG. On the other hand post-processing with
addition mod 1 does appear to be a feature that may be advantageously
exploited to impart more complexity against analysis to the output of
the compound PRNG (albeit with doubling of computing cost). This
feature has been added as an option in the most recent version of
WEAK3.
Looking back, there can be seen to be a two staged process in the
built-up of the compound PRNG. Consequently the analyst has also to
work through two stages. In order to infer the keys entered by the
user, the analyst, if he has the exact (post-processed) output
sequence of the compound PRNG (which is highly unlikely in view of
the structure of the encryption processing part that uses this
output), has to infer the parameters of the constituent generators
of the compound PRNG. To do that, he has first to overcome the barrier
posed by the addition mod 1 processing. There appears to be no
effective way of doing that. Note, for example, 0.3 can be the result
of addition mod 1 of (0.1, 0.2), or (0.4, 0.9) or ......, in fact of
a practically infinite number of pairs of possible summands. After
passing that barrier, i.e. having obtained the sequence entering the
addition mod 1 processing step, he has to face the difficult task of
determining the activation sequence of the constituent generators,
without which inferring their parameters is infeasible. But the
algorithm of the compound PRNG has been purposedly designed such that
the activation sequence of the constituent genrators is fairly random
so that the analyst has no clue of finding it. (To put it another way,
there is no linearity in the sequence entering the addition mod 1
processing step that he can possibly exploit.) Finally, starting from
the parameters of the constituent generators he has to overcome another
barrier posed by a combination of a shuffling buffer and an addition
mod 1 processing in order to successfully gain access to the seeds of
the standard PRNG that the user has entered. (The shuffling leads
to non-linearity, while addition mod 1 adds complexity as explained
above.) It should now be obvious that this whole work can be
arbitrarily hard, if the number of contituent generators is chosen to
be sufficiently large.
This final pseudo-random number sequence as described above is
utilized to encrypt records (of 80 bytes or 160 hexs) according to a
mixed scheme of stream and block encoding with variable number of
rounds (This encryption part is the same as that for WEAK1.) In the
following the individual steps, done sequentially in each round, are
explained:
a. Pseudo-random permutation of the hex digits.
We generate a (user determined) number of pseudo-random permutations
of [1, 160]. In each round of each record to be processed a pseudo-
random number is generated to select one of these to permute the 160
hexs. One could instead have generated an entirely new pseudo-random
permutation of [1, 160] for each round of each record. However, that
would be very expensive in computing cost without achieving
proportionately higher complexity against analysis.
b. Transformation of the hex digits with pseudo-randomly selected
substitution tables.
We generate a (user determined) number of substitution tables (I call
them level 2 tables). Then we generate a (user determined) number of
index tables (I call them level 1 tables), with each index table
containing 160 pointers to the level 2 tables. During encryption in
each round (of each record to be processed) a pseudo-random number is
generated to select one of the index tables. Then the first hex of the
(160 hex) record uses the pointer in the first entry of the selected
index table to retrieve the level 2 table being pointed to (which is
a substitution table for hex to hex) to do the substitution. The other
hexs are similarly substituted. The level 2 tables (and level 1 tables)
are generated at initialization time and are fixed during the whole
encryption process. However, through the runtime dynamic selection of
these one achieves nevertheless some good approximation of a totally
dynamic generation of substitution tables at fairly acceptable
computing cost. (A totally dynamic generation would require for
processing of each hex in each round the pseudo-random generation of
a new mapping of [0,15] to [0,15].)
c. Circular shift of the words (groups of 8 hexs) by pseudo-
randomly determined number of bit positions.
Each group of 32 bits are shifted circularly a number of positions
so that the analyst, since he does not know the number of shifts,
cannot trace back from the shifted bits to the bits before the shift,
resulting in confusion.
d. Auto-keying of the words with a pseudo-randomly determined key.
There are 10 words of 32 bits in each round to be processed. At first
a pseudo-random number is generated (the auto-key) and is added to
the first word mod 2^32. The sum is added to the second word mod 2^32,
and so on. The resulting words are hence such that each word is a
function of, i.e. is dependent on, all words on its left. Thus a
diffusion of the bits of the record is achieved.
e. Another circular shift of the words.
Explained in c.
f. Another auto-keying of the words (in the opposite direction to
d in the word sequence).
The diffusion obtained in d is in one direction. There is for example
dependence of word 10 from word 1 but not the other way round. Hence
we do here the same processing in the opposite direction to ensure a
more thorough resulting diffusion.
g. Addition modulo 2^32 of the words with words of pseudo-random
bits obtained from the compound PRNG.
This is stream encoding. We generate 10 pseudo-random words (24 bits
are obtained from each pseudo-random number in [0,1) by multiplication
with 2^24) and add these mod 2^32 to the 10 words of the record in the
round. Addition mod 2^32 has the advantage over the commonly employed
XOR in that there is some diffusion of bits within groups of 32 bits
due to carry-overs at the bit level that happen in the addition process.
There are several basic principles underlying the design and
implementation of WEAK3. Firstly, the algorithm should be very easy to
understand (by laymen, including myself) and should be independently
implementable from scratch by any user having average programming
experience without too much effort. This excludes from consideration
techniques that demand deep theoretical backgrounds or that require
complicated formalisms to describe. Secondly, there should be as much
variability in the algorithm as possible so as to defeat the analyst
from the outset. Note in particular that he has to guess the number of
rounds employed by the user before starting with any more detailed work.
On the other hand, the user can tune the number of rounds to the
security level desired in order to optimize his computing cost. Thirdly,
the algorithm is to embody both stream and block encoding techniques,
a combination which appears to be novel, challenging the analyst to
devise new ways to lauch effective attacks. Fourthly and lastly, the
reference implementation is to be as simple and as clear as possible
in program sturcture, leaving optimizations to those users who
unconditionally wish to maximize the runtime efficiency.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:11:01