Path: cactus.org!milano!cs.utexas.edu!news-server.csri.toronto.edu!bonnie.
+ concordia.ca!clyde.concordia.ca!altitude!elevia!alain
From: alain@elevia.UUCP (W.A.Simon)
Newsgroups: sci.crypt
Subject: braided out (WAS: Braided Streams)
Message-ID: <1991Jun24.191519.11491@elevia.UUCP>
Date: 24 Jun 91 19:15:19 GMT
Followup-To: sci.crypt
Organization: The Electronic Path - Global Village
Lines: 83
I guess it is time to take a break, and step back. The Braided
Streams system has had its day in Court. Those who think there
is matter for further exploration are welcome to go ahead, but
let's not hog anymore precious bandwidth, unless there are new
elements to bring to the discussion. So far, the argumentation
has been rather circular, or should I say triangular...
Whatever merits BS (!) may, or may not have, will not be decided
any time soon, through the current process. I have brought forth
a rather odd proposal; though none of its components are entirely
new, the composite system is definitely offering new avenues. For
its strength, I have provided no formal proof. I am unable to do
so, but I feel the ideas are intriguing enough that they would
whet the curiosity of a few among us, and that some kind of proof,
for or against, would be provided. It turns out that it is not that
easy, either way. I have received quite a volume of feedback, in
the news and by e-mail. Some of the e-mail stuff could be used as
a good approximation of a random key, that's how unexpected and
unconnected it was. But for the more rational replies, I could
make three categories:
- I am an amateur, therefore I should go play in my
sandbox and leave the grownups alone (a few insults were
also added here and there...). |8-)
- the braiding algorithm is not new, nor is it interesting,
and anyway it is weak; I saw that in two seconds flat, just
don't bother me.
- in the information theory sense, the idea stinks, here is why...
In order to focus the threads on the real problems, let me address the
points made in each category, in a generic manner.
Of course, I am an amateur, and it shows. Dismissing the idea on this
ground, or letting it affect one's judgement is a mistake. It does
nothing to advance one side or the other. It will certainly not dissuade
me from posting.
The weakness of the braiding algorithm is obvious for all to see, until
they actually devote some thinking to it. It turns out the braided stream
has an interesting quirk. In fact, there is little doubt that the system
is as strong as its key. A formal proof is still needed for this claim,
but there was a convincing demo provided. To recap, any arbitrary desired
plaintext can be extracted from the braid, given the proper key. In fact,
one plaintext can be extracted by many keys, and any other message could
be extracted from the same braid as well, given another set of keys. There
is no way to know that one has indeed cracked the cipher. Parallel thinking
and suggestions for thought experiments are welcome. For or against.
The key management aspect, without which the braiding would be only
slightly better than a regular XOR, is truly the weakest link. This
was correctly identified by a number of people who took the time to
think things through. Shannon's name has come up in just about every
message on this subject. Knuth has been invoked a couple of times too.
I wish to reassure you all that I am familiar with the problems (and
writers) you quoted, and that I am not quite satisfied with the answers
I am still working on. You have also helped me understand some aspects
of information theory which I had overlooked. I wish to thank you for
taking the trouble. The conventional wisdom here is that there is a
limit to what my key management stream can do for me (Shannon). There
is also a limit to the deviousness my key management language can
achieve (Knuth and Shannon). One aspect I have been studying, which
nobody raised, is that we could find ourselves with a dynamic system,
as the key that is generated will be used to program the key generator.
This could be a builtin limit to my approach. I still have to think
about it. On the other hand, if I could tune it for chaos...
My claim (one of a tall order), on which the value of the system as a
whole rides, is that due to the peculiar property of the braided stream
output (see above), a sloppy key management scheme would work just as
well as one which would be perfect (but impossible) in the information
theory sense. It would have to be prolific though.
Your comments and suggestions are welcome.
For now, I will cease posting followups, and I will work on the key
management scheme. I'll be back.
--
William "Alain" Simon
UUCP: alain@elevia.UUCP