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