Path: cactus.org!milano!cs.utexas.edu!uunet!bonnie.concordia.ca!IRO.UMontreal.
+ CA!matrox!altitude!elevia!alain
From: alain@elevia.UUCP (W.A.Simon)
Newsgroups: sci.crypt
Subject: a key management scheme (longish)
Message-ID: <1991Jun26.171120.3653@elevia.UUCP>
Date: 26 Jun 91 17:11:20 GMT
Organization: The Electronic Path - Global Village
Lines: 246
Introduction
"Braided Streams" has been abundantly exposed in this
newsgroup in the past. It has also been trashed, bashed,
and flamed. So far, no formal proof was offered for a
against it, but there were convincing evidences that it
has surprising benefits. The following proposal relies
on a different application the same algorithm to perform
its work.
Even for those of us who accept that the braiding
algorithm is at least as strong as an XOR, there still is
a big problem: key exhaustion.
I proposed to deal with this, through the use of a key
management language that would be compact enough to use
the available bandwidth, in such a way that new key bits
can be generated faster than they are used up. One of
the difficulties I encountered was that the programming
of the language was itself taken from the output of the
system. I was creating a situation in which key strength
could possibly degrade, due to the dynamic behaviour of
the system. Although I did not reject this approach, I
had to admit I was not equipped to deal with it, for now.
I had to look for a simpler solution, in the short term.
Here is an idea which I would like to trash out over the
net. It relies on the fact that random material, if
shuffled at random, is still random (I don't mean pseudo-
random).
Objective
Design a method which would allow for the availability of
an infinite length random key (automated one-time pad
generation), from a finite store of random material.
Constraints
- The method must not introduce any new information,
into the key store.
- At best, the only fresh random material, available
for refreshment of the key, is only about half as
long as the discarded key material.
Premises
- We have, at each end of the link, a large store of
random data to be used as key, at the start of
operations. This store is many times larger than any
one given message is anticipated to be. The larger the
store, the stronger the system. We call this store
Current Key (CK).
- A perfect random number generator is assumed to be
available, the nature of which is not specified.
This generator is used to create the initial key
stores, then to generate fresh key material during
operations.
- Once operations have started, the only way to
communicate fresh key material (FK) is through the
system, under the protection of the existing key
material, braided through the plaintext (PT).
- The contents and the length of the key store are
unknown to the opposition.
- The contents and the exact length of the transmitted
fresh key material are unknown to the opposition (we
have a secure channel to transmit fresh key
material).
- Keys are dealt with on a bit by bit basis. There
are no obligation to work in byte or word multiples.
This is not necessarily true of the communication
system.
- All operations are performed at both ends of the
link, in order to keep the keys synchronized.
- An error free communication channel is assumed.
Extra design goals
- The system should provide an extra incertitude: the
length of the key. This means the size of the key
store is elastic, but it should not run away in any
direction, up or down. The more elastic the key,
within limits, the stronger the system.
- The system should be entirely automated. Human
intervention could be possible, but the long term
viability of the system should not depend on it (I
am thinking of remote sensing and remote
manipulations).
General discourse
As key bits are used up, they are placed in a temporary
store named Spent Keys (SK). The PT and the FK streams
are extracted into their respective stores.
As a consequence of the braiding algorithm, there are as
many SK bits as there are PT and FK bits together. If we
were to replace the SK with FK + PT (throughout this
text, "+" indicates concatenation), we would effectively
have brought the key store back to its original size.
Both FK and PT are secure. Unfortunately PT is less than
random, and this solution doesn't provide for key length
elasticity.
Re-appending SK to CK, as is, of course is out, for a
number of reasons which have been abundantly covered in
other works (the first one who asks for references gets
clubbed with a fully chaotic, braided rubber truncheon).
Doing the shuffle
Given that SK has only been used once, and that it is
assumed not to have been compromised, and given that we
know it to be random, we could use it as a key to apply
some processing to some other random material. Let's
temporarily assume CK to be the result of braiding two
random streams (why not?). We use the unbraiding recipe
to split a length of material (KM1) taken from CK
(stripped of SK), of same length as SK, in two parts
named Temporary Keys One (TK1a and TK1b), using SK as
key. We then cut out another length (KM2) of the
remaining CK, of same length, which we use as a key to
unbraid SK into TK2a and TK2b. We could now re-append
the four temporary pieces of key material to the
considerably shortened CK (CK <-- CK + TK1a + TK2a + TK1b
+ TK2b) and we would have recycled SK in a randomized and
diluted fashion. Random material was shuffled in a
random manner, it is still random, but different. An
added twist would be to rebraid TK1a with TK2b, using KM1
as key, and TK1b with TK2a, using KM2 as key, before re-
appending. Using more than two braids (4, 8, etc...)
would add even more strength, if that were required.
So far we have not used the FK stuff, and we have not
addressed the elasticity issue.
Elasticity
If we append FK to CK, then do the reshuffling and
appending act, we will have increased the length of CK by
the length of FK. We will also have added fresh random
material to the key, ahead of the recycled material,
so postponing its reuseage by a random number of bits.
If the last bit of FK is "1", we decide not to do the
reshuffling steps specified above, and the material from
SK is not re-appended. This shortens CK by the
approximate size of FK (actually SK - FK, which is about
half of SK, which is about equal to FK), one time in two.
We have still added fresh random material to CK.
In all cases, the length of CK is randomized. The
elasticity is predicted by the contents and the length of
FK.
Due to variations from a perfect 50-50 ratio of 0's to
1's, as would be expected in any random bit stream, the
[un]braiding of key material, for the purpose of
shuffling the spent key, could result in truncations;
therefore, a few bits will be lost now and then. These
random losses are acceptable (even desirable). But a
safeguard could be built in the system to watch for a
decrease of the running average of the length of CK, past
a threshold, and compensate for it with a dummy
transmission, large enough to contain enough FK to catch
up; the trailing bit would be twiddle to 1, to force a
concatenation of a shuffled SK as well.
Anticipated attacks
From a known plaintext attack, it would be possible to
extract the SK and the FK materials. The Braided Streams
system is such that a known plaintext attack yields a
number of "possible" solution, for any one "known"
plaintext, in any one ciphertext. These are all more or
less equally [im]probable, except one, when the known
plaintext is actually sent. Possession, by the
opposition, of a number of SK and FK solution pairs, of
unknown probability, while we still have a fully unknown
(length and contents) CK store, would not constitute an
immediate threat to the system's strength.
The only way this could happen is if the opposition
accumulated an uninterrupted series of intercepts, enough
to cycle through the whole CK, at least once, with ALL
TRAFFIC BEING KNOWN PLAINTEXT. Even then, it must be
remembered that each message adds another factor of
incertitude (multiplies, really) as to which FK-SK pair
is the proper one. So all possible solutions must be
considered... And then, one must take into consideration
that some message do not contain the expected "known"
plaintext, but that the opposition will find there anyway.
And, finally and crucially, there is no way to know that
one has cycled through the entire CK.
A different type of attack would consist in provoking repeated
transmission errors in the hope that one would remain undetected,
to lose the synchronicity of the keys at each end of the link,
so forcing the system to reset the keys to the values they had
at the start of operations. This would afford the opposition
a second (at least) look on the same key material. This is not
a big threat, but it could be an annoyance. In order to remove
the motivation, we could prevent this by forcing a shuffle, of
an arbitrary length of CK, treated as if were SK, without the
benefit of FK, at every reset.
Conclusion
The proposed solution is simple, and strong. If we
remove the requirement for fresh random material, and for
key elasticity, we have a very good (but not quite as
strong) scheme that is applicable to any cryptographic
system requiring infinite length keys (one-time pad).
A frequency hopping broadcast system could also benefit
from a perpetually changing frequency list pattern.
A system composed of the Braided Streams Multiplexer, and
the Braided Streams Key Management is as strong as the
stronger of the two, as each relies on the strength of
the other. One could reasonably argue that it makes it,
at most, as strong as the weakest of the two, but that's
not how it turned out, because the weaknesses of each are
hidden by the strengthes of the other.
--
William "Alain" Simon
UUCP: alain@elevia.UUCP