Path: cactus.org!milano!cs.utexas.edu!usc!rpi!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: Re: Braided streams
Message-ID: <1991Jun24.033238.6456@elevia.UUCP>
Date: 24 Jun 91 03:32:38 GMT
References: <1991Jun23.042445.9676@elevia.UUCP>
Organization: The W.A.Simon Wild Life Fund
Lines: 196
In
consp04@bingsuna.bingsuns.cc.binghamton.edu (Dan Boyd) writes:
>In article <1991Jun23.042445.9676@elevia.UUCP>
>alain@elevia.UUCP (W.A.Simon) writes:
>> At best, you will match a plaintext and a key to a given ciphertext,
>> but you will have achieved no progress whatsoever towards breaching
>> the security of the link, because a) you knew and expected the
>> plaintext, b) the key it does allow you to extract won't be used
>> right away, but at an undetermined time in the futur, depending on
>> the available store of key material, and on the volume of traffic,
>> c) you have no certitude that the known plaintext was in fact sent
>> at that particular time, since you can retrieve it from any other
>> traffic intercept just as well anyway.
> You don't understand what a known-plaintext assumption is.
>It means, "Not only do I know that they sent this message though the
>pipeline at some time, I also know when." It means you know where
>they enciphered that plaintext.
In a typical known plaintext attack, you have a good idea of
all the pertinent details and, possibly, a perfect knowledge
of what the plaintext was to be. This means that when a
ciphertext comes through, you can try to find the key by working
from the plaintext. That key being a one-time pad, in the case
of braided systems, you have learned nothing that will be useful
next time around. BTW, yes, I know what a plaintext attack is.
As to using the known plaintext attack to extract the key management
stream, read on, for exciting news...
> With your system, that means you can recover the key stream
>for that stretch of the message.
Granted, if you know that you are dealing with two streams
only; but this decison is not part of the system, it is
dependant on the key. And even then, we have shown that
a sufficiently long ciphertext can be made to give out any
arbitrary plaintext we might want (see below for reference).
But, let's go back to the known plaintext attack for a minute.
The French Ambassador in London is given the text of a prepared
statement by HM's G, regarding the adoption of a common currency.
The Elint people hiding somewhere in Scotland, where they share
NSA facilities, know the text, and they expect it to come on
the air. In the meantime, in the French Embassy, Mrs Embassador
finds out she won't have enough Roquefort, and that Champagne
stocks are dangerously low. She sends an order to Fauchon, in
Paris, through the Quai d'Orsay. Her message, you can believe
me, will go before anything else does. Since she is passing an
order, and the diplomatic pouch is not due for another three days,
she does her full shopping at one shot. It is a rather long message.
It is intercepted, and the spooks treat it as if it were the real
McCoy. Lo and behold, it jives! The Braided Stream system strikes
again: for any target plaintext, one can reconstruct a key that
will allow for its extraction from the cipher text (message length
allowing). You get it? Whatever ciphertext you intercept, it will
allow a match with your "known" plaintext. Even random noise would.
So the "key", that they think they have recovered, is useless. I will
refer you to <1991Jub17.155825.1019@thunder.mcrcim.mcgill.edu>, in
sci.crypt, for a convincing demo.
In an added twist of fate, the cipherclerk in the Embassy decides
the two messages are equally important (smart kid, he'll go far),
so he decides that instead of noise in the second and third channel
the second message will take another channel, and noise only one.
There will be at least two plaintext streams braided together with
some noise and some key management material.
So we now have only one ciphertext transmitted within the time frame
of our known plaintext attack parameters. The opposition are now
certain they have extracted the real key when, in fact, it is a mix
of the key and the shopping list. At this point not only they could
be fooled by the fact that they think they now own the real key, but
they could also be fooled by the fact that what they think is the key,
is only an artifact of the system. Things are not getting any better
for them.
>> To breach the security, you would have to hit on a correct plaintext
>> and key combination and keep hitting correctly until you intercept
>> the portion of message where the compromised key starts being used.
>> A tall order.
> No, you don't have to keep hitting correctly. You can just
>hop along trying the key stream you found until you find a place where
>you start recovering plaintext with it again. You could go along for
>days until it matches again, but you would eventually find a match.
In view of what I just explained above, you might want to
rethink this argument.
>> I don't, so far, provide a satisfying key management system.
>> I do provide a channel for doing it. That's also part of the
>> novelty. I may not have to "pin myself down", since any
>> system that uses a fully secure seed, may be used to generate
>> a fully secure sequence, as long as the choice of algorithm
>> used to expand the seed is itself dependant on the key. In
>> [ ... ]
> You're breaking the fundamental assumptions here. All these
>many different ideas for getting sequences of numbers are part of the
>SYSTEM, not part of the key.
> You have to assume that the enemy knows
>what those tokens mean. When you send a token through saying 'use the
>Nth prime number' you have to assume the enemy knows what that token
>means.
> An analyst of your system has to assume that the enemy knows
>what the sequences, algorithms and combinations are, because they're
>not part of the KEY, they're part of the SYSTEM.
Normally, you would be right. But say we have a long list of
recipes (say 127). Since our language uses up all possible values
(by design) of the seven (arbitrary, but reasonable choice) bits
[0-127], there is no unused bit combination to give away the
presence of a key management stream. Each recipe may require one
or more parameter; for the same reasons as before, we structure the
parameters so their value use up all possible values of the scale
we allow them (say [0-3] if we allow 2 bits for the first parameter,
and [0-7] if we allow 3 bits for the second parameter). So, now we
have a language that's part of the system, but the program is a
string borrowed from the key stream. The key stream is used up to
drive the braiding algorithm, AND to generate a program for the
purpose of key management. This should use up the key stream quite
rapidly, but now we have ways to refresh it in an unlimited
fashion. We have fallen out of the system, it is all key driven.
The opposition doesn't have a leg to stand on.
If that was not clear: I was trying to say that one could not
find a subset of the stream that could match a key management
stream any better than any other subset. The key management
stream is not distinguishable from the rest of the stuff, be it
noise, or plaintext.
>> You are confusing a book, the text of which educated guesses
>> can be made about, and files containing random garbage, which
>> you could try to grok out until you are blue in the face.
> Your idea of 'random garbage' is incorrect. Random number
> [ ... ]
Give me credit for knowing the difference between pseudo-random
and random, please.
> [ ... ]
> So then we keep trying that stretch of recovered key against
>everything that comes though the net. Eventually we hit a point where
>that key comes around again in your key-rotation sequence, and we're
>reading more, different plaintext. We can again guess what came next
>in the plaintext, with some degree of accuracy, which means we can
>again recover some more key material. We keep going on like this,
>accumulating key material.
You would have so many plausible keys that they'd come out of
your Cray's ears... forget it. For each bit, you'd have to
slide a window, and apply all you possible keys... and at each
bit, your number of possible keys would increase. Good luck.
>> And the ciphertext being longer (by an amount
>> that varies according to the statistical profile of the
>> key) than the plaintext, this is HARD work for the
>> opposition.
> It's not NP-hard. It's not hard enough to make it unfeasible.
I was tempted to say it is NP-hard, but my academic background
is rather weak around these edges... I'll let others decide.
>> > (Jerry Leichter) I don't remember which cryptographer first
>> > stated that he would never accept a new cryptosystem from
>> > anyone who had not already broken a strong one, but this is (in
>> Some great people have said a number of equally self serving
>> things in the past. I try to avoid adopting this kind of
>> inbred thinking.
> You're calling this statement self-serving. You're calling
>the cryptographic community inbred. You're arguing emotionally here.
>This doesn't inspire confidence.
I am not calling the profession inbred. You are not deciphering
my mind here, so I would appreciate if you kept your "educated"
guesses for yourself. Read my words: "inbred thinking". If the
shoe fits, wear it, but don't pretend it fits the whole trade.
The community as a whole doesn't necessarily accept this smart
aphorism as the gospel, nor does it need dogmas. That quote is
dogma. No scientific trade can afford dogma. So who is being
emotional? Should this attempted manipulation inspire confidence?
What is your particular problem here?
> [ ... ]
> What does the ciphertext look like if I send a block of nulls?
> And what does it look like if I send, with the same key, a
>block where all the bits are 1?
A block of nulls/ones would result in a definite skewing
of the statistical profile, for a burst of bits as long as
the ciphertext needed to include the braid. But the larger
the number of streams, the least sensitive. However, remember
that our noise channel(s) could contain bursts of nulls, or
bursts of ones, as well; so the opposition is up shit creek again.
> Dan
--
William "Alain" Simon
UUCP: alain@elevia.UUCP