Path: cactus.org!milano!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!
+ wupost!uunet!bonnie.concordia.ca!clyde.concordia.ca!altitude!elevia!
+ alain
From: alain@elevia.UUCP (W.A.Simon)
Newsgroups: sci.crypt
Subject: Braid Crumbs
Message-ID: <1991Jul18.033136.13720@elevia.UUCP>
Date: 18 Jul 91 03:31:36 GMT
Organization: The Electronic Path - Global Village
Lines: 148
Braid Crumbs
The various comments I received on the subject of the Braid have
resulted in my giving it the once over, in an effort to find lines of
reasoning which would provide, short of a formal system, at least some
kind of firm ground for discussion. It has helped me progress in my
own understanding of the idea, its consequences and its underlying
principles, but I still don't have a solid theory for it. At this
point in my reflexions, I must say that braiding, as an algorithm, is
smart, efficient, cute and convenient, but braiding per se is not where
the real strength of the system lies. Since I don't have a solid ground
for proof or disproof, I will just pass on to you the "state of the art",
as of today, and wait for the flames [ DON'T BE SHY |8-) ].
Introduction
I have shown, in "Eating Pretzels", the rather obvious fact that
braiding WITHOUT noise insertion is weaker than a Shuffle, which is in
turn weaker than a XOR. The strength of the proposed Braided Streams
Multiplexing System, resides in the injection of RANDOM QUANTITIES OF
RANDOM NOISE into the ciphertext, rather than in its specific
algorithmic power; more to the point, it resides in the synergy of the
algorithm with the insertion of noise. ANY encryption applied to the
aggregate of the plaintext and some noise would be stronger than the
same system applied to the plaintext alone; but one that distributes
the random bits throughout the plaintext is strongest. One other
useful feature of noise insertion is its ability to support a Key
Management System, as described earlier in sci.crypt, and so far
unchallenged; so we won't cover this here.
The reason for my continued interest in the Braid, is that it provides
a convenient device for noise injection and, while not forbidding it,
removes the need for encryption of the resulting aggregate. It is well
suited to a wide variety of effects, depending on a key, so providing a
large number of additional elements of incertitude, to throw opposing
cryptographers off with. Its capability for multiplexing several
streams makes it even more powerful, since the more unrelated streams
there are, the stronger the system. Also, it is very convenient when
encrypting on the fly, since processing can be performed, as we go,
even before the whole plaintext is known; an ideal quality for voice,
as well as remote sensing and control applications. High security
environments, where a permanent link is kept live at all times, would
equally benefit from this approach. Finally, when combined with noise
injection, its identified weakness ceases to matter. But let's first
recapitulate the virtues of noise insertion, then move on to the merits
of the Braid, before we can understand the synergy that arises from
their combination.
C=E(P+R,K)
We know that once we have combined a plaintext (P) with a random length
of random data (R), depending on an infinite length random key (K), any
reasonable encryption method (E) we may chose to apply to it will
result in a ciphertext (C) which is immune to the known plaintext
attack. This is due to the fact that just about any arbitrary
plaintext, shorter than the ciphertext, could be extracted (still not
proven, but reasonably demonstrated). The strength of the system
resides not in the encryption method, but in the application of any E
to the combination of R to P. It is expected that, adding yet more R
to P and going through E again, the resulting new C would be even more
secure; the more random additions, the stronger. It is also expected
than a single pass through the system, with a lot more random noise
added, would achieve the same result.
We could consider that doing a XOR on the aggregate (A) of R and P,
would be like doing a XOR with a one-time pad key that is longer than
the plaintext, without wasting the excess key. This is not a paradox;
we have essentially changed the situation from one in which the
attackers says "the next bit is either a 0 or a 1 of the plaintext", to
a situation in which "the next bit is either a 0 or a 1, or it doesn't
belong here; and if it doesn't, where does it?...". Since the farther
we are into C, the more likely it is that the bits under consideration
are noise, a Shuffle would be stronger than a XOR; with a Shuffle,
every bit of C is as likely to be a noise bit as any other. The
aggregation of P and R has changed, it seems, some of the rules of the
game.
The more R we add, followed by the required Shuffle, the easier it
becomes to cater to a larger scope of wishful thinking on the part of
attackers with a "known" plaintext, and the harder it gets to apply the
usual techniques of cryptography. The more random data is inserted
into C, the more likely two or more ciphertexts will resemble each
others in statistical terms; the more streams are braided together, the
more useless the statistical analysis. I also suspect that it could be
proven that ANY arbitrary plaintext, at most HALF as long as the
ciphertext, can be extracted (!flames expected!), and quite a large
number of longer ones as well (the closer we get to the length of C the
harder it becomes to find the desired P), therefore it is profitable to
inject as much of R as possible within the limits of bandwidth
availability. Now that we know the added strength comes from the
random quantity of added random noise, and its scattering throughout
the plaintext, with a Shuffle, the question is: what are the are the
consequences for the Braid?
If A=B(P,R,K) then C=A
Braiding is a multiplexing device, which can be used to entertwine the
bits of one or more P streams with the bits of one or more R streams.
We could say that it is equivalent to appending R to P and applying a
key dependant Shuffle, with a constrained key space, to A. Using the
Braid as an injection device, would therefore achieve two goals in one
operation: injection and shuffling. Because of the constrained key
space, it is rather obvious that a Braid is technically weaker than a
Shuffle but, due to the random presence of random bits, this gives no
handhold to the opposition; a bit is a bit is a bit. Whether it is a P
bit or a R bit is not known, can't be known, and any one guess must be
followed by as many lucky guesses as there are supposed P bits in the
balance of C. The probability for the next bit being from P is unknown
(it depends on the value of a bit in a random key), and it is equally
unknown for each bit (unlike the XOR case wherein an early bit is more
likely to be from P than a later one). In the case of multi-stream
braids, there would be the added uncertainty as to which of P or R the
bit would belong in. Braiding doesn't really produce some kind of C
but some A, with such interesting characteristics that any further
processing is not required. The opposition knows the value of every
bit (unlike in the case of a regular ciphertext), but it doesn't know
what each bit is for. When, in the past, the choice was between having
a 0 or a 1 solution, there are now solutions of the form "this bit
belongs to stream 1", "belongs to stream 2", "belongs to stream n",
etc... with an UNKNOWN maximum value for n, and with each successive
guess INDEPENDANT from the result of the previous one. Discipline
freaks, can always do a XOR or a Shuffle on A, with yet more K, if that
is what they want, but I rather doubt it is required... or useful;
after all, it only multiplies the amount of cryptographic sleuthing by
a power of two.
Conclusion
In the absence of a formal proof of the validity of the proposed
system, I kindly request, of those who can do so, that they provide
evidence (text or references), for or against the claim that adding
random noise to the plaintext before encryption adds strength to the
system. I suspect Shannon's name will be invoked, not in vain...
If this can be accepted, then we can start building a really good
public domain cryptographic system, with its own key management
functions. The choices of injection and encryption algorithms are
of secondary importance, here, even if I favor the Braid.
Thank you.
--
William "Alain" Simon alain@elevia.UUCP
Frank Zappa for President of the United States of North America!