|
Cryptome DVDs. Donate
$25 for two DVDs of the Cryptome collection of 47,000 files from June 1996
to January 2009 (~6.9 GB). Click Paypal or mail check/MO made out to John
Young, 251 West 89th Street, New York, NY 10024. The collection includes
all files of cryptome.org, cryptome.info, jya.com, cartome.org,
eyeball-series.org and iraq-kill-maim.org, and
23,100 (updated)
pages of counter-intelligence dossiers declassified by the US Army Information
and Security Command, dating from 1945 to 1985.The DVDs will be sent anywhere
worldwide without extra cost. |
|
19 January 1999
Date: Tue, 19 Jan 1999 14:29:41 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Organization: Studenten; LRZ; Universitaet Muenchen
To: aucrypto@suburbia.net
Subject: AUCRYPTO: Some Thoughts on the Design of a Proposed Stream Cipher
I. INTRODUCTION.
While the general tendency of modern developments in cryptography has been
towards block ciphers of increasingly larger key length, with, e.g., AES
demanding a minimum of 128 bits, a recent agreement of the Wassenaar countries
to restrict export of crypto products to those having key length not exceeding
56 bits will invariably lead to a more or less long-durated very undesirable
situation where innocent and law-obeying people outside of the 33 signatory
nations will have only relatively weak ciphers at their disposal that are
insufficient to offer an adequate level of security of their private
confidential communications (either with themselves or with people of
the 33 countries). For eventually illegally imported strong crypto products
could have problems of general availability, cost, maintenance, integrity
(virus/bugs implanted by malicious agencies) and, last but not least, legal
issues. (The maintenance and integrity issues apply also to crypto archives
having stuffs that have been legally imported before regulations come into
force.) On the other hand, their countries are on the average fairly poor
in scientific and technical know-how currently, so that it would be extremely
difficult to bring up there in short terms an adequate crypto infrastructure
comparable to that of the technically superior export-regulating nations.
One viable way for people in the said technically underdeveloped region to
escape from the dilemma appears to be to resort to superencipherment, i.e.
an encryption system consisting of a combination of an easily implementable
algorithm with a sufficiently good 56-bit algorithm (which can be legally
obtained from the 33 countries) with the hope that the resulting strength
will exceed the computational capability of the mighty eavesdroppers.
It is the purpose of this paper to present some preliminary ideas on the
realization of such an easily implementable complementary algorithm in the
form of a stream cipher having the property that its keystream can be easily
generated by both partners of a given communication connection without involving
any problems of transport and secure storage, thus possessing the advantages
of immunity to
(whatever) export controls and of simplicity of handling by (eventually
unsophisticated) users of the encryption scheme. (This is to be contrasted,
in particular, with keystreams obtained from physical random processes, which
normally incur severe management problems of transport and secure storage.)
II. RAW MATERIALS FOR OBTAINING KEYSTREAMS.
For good cryptological security of a stream cipher, the keystream generated
should be hard to infer, i.e. it should be difficult for the analyst to predict
any bit of the keystream from the other bits. As is well-known, this very
crucial problem is unfortunately extremely difficult to deal with. We regret
(as the reader may have foreseen from our introduction) not being able to
offer any satisfactory solution to that in the present paper. Instead we
suggest to appeal to the admittedly crude (imprecise) heuristic argument
that by rendering each bit of the keysteam somehow to be a sufficiently complex
(complicated) function of a sufficiently large set of independent and
sufficiently random values (variables) the dependency of any bit from the
other bits of the entire sequence obtained can be made to be arbitrarily
small so as to be beyond the inference capability of the analyst.
Assuming that the above heuristic argument can be accepted and noting that
the dependency can be expressed in terms of auto-correlations, we suggest
using the following coarse plan to generate keystreams for our purpose: Start
with some more or less random raw materials (sequences of bits/bytes) that
are easily available albeit inherently poor (i.e. comparatively strongly
auto-correlated) and apply a sequence of suitably chosen refining processes
(to be treated in the next section) aimed to reduce the correlations such
that the end-stage output will be of satisfactory quality (progressive
refinement).
Conceptually this is akin to obtaining potable water from a muddy source
through employing a series of differeent filtering and disinfecting processes,
with each augmenting the functionality of the others such that the end product
will hopefully be sufficiently free of ingredients that are detrimental to
human health.
Thus said, we shall presently look for ensembles of fluctuating quantities
that can be easily and perfectly leagally acquired by both communication
partners in identical copies independent of geographical locations and that
are apparently in some sense random, i.e. roughly speaking non-systematic,
disordered and without a discernable periodicity. The following materials
suggest themselves:
1. Natural language texts (books, news, public documents, etc.)
2. Artificial language texts (source programs, digit sequences of transcendental
numbers, postcript files, etc.)
3. Sequences of data (physical measurements, economic time series, telephone
numbers, results of numerical computations (with identical input, algorithms
and computational accuracy), scientific data bases, etc.)
4. Other digitalized materials (voice, sound, photos, pictures, graphics,
satellite and medical images, binary program files, etc.)
With the possible exception of the digit sequences of transcendental numbers,
these items are mostly fairly strongly auto-correlated. In fact, some well-known
methods of analysis are based on the frequency distributions of bigrams,
trigrams, etc. of the natural languages in which the plaintext messages are
written. In the next section we shall therefore deal with a number of techniques
aimed to efficiently reduce the auto-correlations, hopefully leading to
keystreams that are
of satisfactory quality for our purpose. (The envisaged, though certainly
not fully attainable, goal is of course the white noise, whose auto-correlation
function is defined to have the value zero everywhere excepting at a singular
point.)
III. TECHNIQUES FOR REDUCING AUTO-CORRELATIONS.
For simplicity of presentation we shall confine ourselves in this section
to natural language texts (sequences of characters in 8-bit bytes) as raw
materials for obtaining keystreams, since these are very easily available
and since the other sources can be treated in essentially the same manner.
The following techniques, being largely taken from classical elementary
cryptography and readily implementable by persons of modest programming
proficiency, appear to be promising candidates for reducing the auto-correlations
that are present in the
texts:
1. Apply substitutions, e.g. polyalphabetic substitutions of bytes.
2. Apply permutations, i.e. transpositions, including reversal.
3. Apply homophones, utilizing the fact that the alphabet of the texts is
smaller than the full 256 character set.
4. Combining two text streams through:
a. Bitwise XOR.
b. Addition mod 2^32 (assuming 32 bit word length).
c. Substitution, e.g. mapping a pair of bytes (or halfbytes), one from each
stream, to a pair of bytes (or halfbytes).
5. Compression through:
a. Commonly available data compression algorithms.
b. XORing groups of bits, e.g. 32 bits, i.e. taking their parity.
6. Use every second or third character of the texts.
7. Apply other simple encryption techniques, e.g. auto-keying applied to
a group of words and circular shift of bits in a word.
Note that with (4) an arbitrary number of text streams can be combined and
that all techniques can be applied recursively, for example (4b) can be applied
after (5b). Thus the proposed scheme for the generation of keystreams
can apparently indeed be made to be arbitrarily complex, satisfying the
requirement mentioned in our heuristic argument of Section II. Of course,
at this point one naturally tends to recall the efficiency issue of processing
which is up till now among the essential selection criteria of modern encryption
algorithms. However, as the author recently pointed out [1,2], one practical
and simple way of coping with the 56-bit limitation is to make use of a new
paradigm, namely 'security through inefficiency', i.e. paying the price of
some tolerable longer precessing time. This can certainly be justified in
a substantial part of civilian applications, e.g. encrypting e-mails, and
can evidently be applicable even to certain relatively time-critical encryptions
as well, if multiple hardware is available for processing parallel jobs.
IV. MISCELLANEOUS REMARKS.
The 'key', i.e. the secret information to be kept by both communictaion partners,
consists of the names or ISBNs of the texts being used and the arbitraily
chosen initial offsets from the beginning of the texts. The keystream is
preferably to be generated online rather than generated once in great length
and used for a
number of subsequent sessions, since otherwise it would have to be securely
stored, resulting in substantial management problems. This means that the
user keeps a running record of the offsets to the individual texts, i.e.
the character positions of the texts after the previous message has been
processed. (As a variation one could introduce some amounts of skips after
each message processed.) No other informations need be securely stored. (The
texts can in fact be freely displayed and read by the user for entertainment
when he is not doing encryption.)
Since one's library may contain quite a large number of texts (possibly also
of several different languages which is advantageous from the point of view
of combination), each having the potential of being combined together to
generate the keystreams for encryption, the mere knowledge of the content
of the library of the user is virtually useless to the analyst. Simple
combinatorical considerations
indicate that an almost unlimited number of keysteams (or equivalently a
non-repeating (non-periodic) keystream of practically infinite length) can
be generated from a library of non-trivial size. This is to be contrasted
with keystreams obtained from one or a few pseudo-random number generators
(LFSRs etc. see [3]) that normally have fairly limited period lengths. (For
a compound PRNG designed to accept an arbitrarily long seed and produce
pseudo-random number sequences of arbitrarily long period lengths, see [4].)
In other words, on the assumption that the user commits no procedural errors,
the keystream obtained is of 'one-time' nature.
Note: The above said 'one-time' qualification should not be mis-understood
by the reader to induce conceptual associations with the one-time pad (OTP).
Our proposed scheme is simply a stream cipher. OTP is on the other hand an
ideal and purely theoretical concept that is never fully realizable in practice,
though it is commonly believed that OTP can be approximated to satisfactory
degree through adequately post-processing bit sequences obtained from some
physical random processes. (Our comparatively much less ambitious goal, though,
is to be able to approximate the white noise well.)
Maurer's universal statistical test [5], being fairly easily implementable,
appears to be particularly recommendable for testing the quality of the
keystreams obtained with a given design configuration.
More than one offsets can be applied to the same text. This may be useful
in the special case where only a single text is availble. (As a matter of
interest, we mention that the same technique can be applied to a single record
of hardware generated keystream, enabling through combination (with e.g.
XOR) of the subquences thus obtained the derivation of a number of different
keystreams from the same record.)
It is not necessary to maintain a large library at the user's place. Certain
texts may be downloaded from publically accessible servers, if care is taken
not to leak thereby sufficient amount of exploitable informations to the
analyst as to which texts actually participate in the keystream generation
process.
Pi appears to have an advantage over the other transcendental numbers
in the present context in that one can compute its digits starting from
arbitrarily given offsets, thus dispensing with the need to store its digit
sequence (albeit at the price of higher computing cost).
Text file compression software are easily obtainable and not subject to export
regulations. Self-implementation of these may however incur some non-trivial
programming expenditure. Note that such compressions are reversible (through
the corresponding decompression processes). For multi-media applications,
a large number of methods, some involving sophisticated mathematical
transformations, are available that are irreversible but ensure reproduction
of acceptable visual quality (see [6,7]). It should be noted however that
in our case we need to care neither reversibility nor satisfactory reproduction.
(Likewise we are not concerned at all with error detection/correction of
codes.) Hence the extremely simple compression technique of (5b) of Section
III appears to be particularly valuable for our purpose. (It may be mentioned
that (5b) is utilized in author's humble design WEAK4-EX [8], a stream cipher
based on psuedo-random number generation with a 56-bit key as seed.)
We take this opportunity to raise a question that could be of some indirect
relevance to our topic: Suppose there are three character strings as follows:
1. Purchase 500 million Yens.
2. Sell all Microsoft shares.
3. Cut UK offer by 7 percent.
Suppose string 1 is the proper message to be communicated. Using (4a) of
Section III we obtain a keystream from strings 2 and 3 and XOR it with string
1 to produce the ciphertext, i.e. the result of XORing all three strings
together. Suppose now that the analyst has a method to systematically obtain
all meaningful possible plaintexts corresponding to the given ciphertext.
Then all three character strings above are certainly among the set of candidate
plaintexts found. How can he know which is the true message? This ambiguity
seems to imply that it may not be unconditionally necessary to strive to
achieve a very excellent approximation to the white noise but that certain
comparatively inferior quality could be sufficient. The author is ignorant
of an answer to this seemingly paradoxical issue and should very much appreciate
hints and explanations from the experts.
V. CONCLUSION.
As our title clearly indicates, this paper does not aim to present any finalized
design but simply sketches some apparently promising techniques of realizing
such. Based on our more or less fuzzy heuristic argument (as given in Section
II) alone it is evidently entirely futile to predict which of the techniques
(listed in Section III) are efficient and which (eventually recursive)
combination out of them will actually lead to an optimal and practically
useful stream cipher. Only actual experiments will be able to tell this.
However, it is the author's intuitive conviction (partly based on some test
results of his WEAK-series of algorithms [1,8,9] that utilize part of the
techniques listed in this paper) that the direction we have been persuing
is a rewarding one worthy of serious further investigations.
The author wishes to thank CWL for reading a draft of the present paper.
Comments, critiques and suggestions for improvement are sincerely solicited.
M. K. Shen
LITERATURE.
[1]
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper13
[2]
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper17
[3] A. J. Menezes et al., Handbook of Cryptography. CRC Press, 1997.
[4]
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper9
[5] U. M. Maurer, A Universal Statistical Test for Random Bit Generators.
J. Cryptology (1992) 5:89-105.
[6] W. Kou, Digital Image Compression. Kluwer, 1995.
[7] V. Bhaskaran, K. Konstantinides, Image and Video Compression
Standards. Kluwer, 1995.
[8]
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper16
[9]
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper15