Path: cactus.org!milano!radar!cs.utexas.edu!sun-barr!olivea!samsung!think.com!
+ snorkelwacker.mit.edu!thunder.mcrcim.mcgill.edu!mouse
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: sci.crypt
Subject: Re: Braided streams
Message-ID: <1991Jun29.182711.595@thunder.mcrcim.mcgill.edu>
Date: 29 Jun 91 18:27:11 GMT
References: <1991Jun23.042445.9676@elevia.UUCP>
Organization: McGill Research Centre for Intelligent Machines
Lines: 85
In article , consp04@ bingsuna.bingsuns.cc.binghamton.edu (Dan Boyd) writes:
> In article <1991Jun23.042445.9676@elevia.UUCP> alain@elevia.UUCP (W.A.Simon) w rites:
[about known-plaintext attack on braided streams]
> 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.
> With your system, that means you can recover the key stream for that
> stretch of the message.
No. If you're lucky, you can determine what the braid would be with
the plaintext deleted, but even that can't be determined with certainty
unless you're very lucky. You cannot tell what the key stream was
unless you are unbelievably lucky (as in two-braiding a stream of 0s
with a stream of 1s).
>> 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.
> 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.
Unfortunately, when you don't have any reason to prefer one key over
another, you can recover any reasonable plaintext you please from any
reasonable ciphertext. ("reasonable" is intended to suppress quibbles
over such cases as a ciphertext of all-0s.) Even if you know
everything but following key bits at some point in the stream, you
can't even tell where your known-plaintext stops in the ciphertext!
(Again, unless you are insanely lucky.)
>> [...] files containing random garbage [...]
> Your idea of 'random garbage' is incorrect. Random number generators
> don't generate real random numbers.
Alain said files of random garbage, not pseudo-random garbage.
> [T]heir numbers are really no more random than the sequence 1 2 3 4 5
> ... because any random number generator you write in software is
> going to be deterministic once you know the seed.
> People can grok out pseudorandom numbers more easily than they can
> invert DES or factor large primes.
Hmmm, just feed your PRNG output through DES in some way! Say, through
a UNIX-password-style scrambler.
>> 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.
Would you care to prove that? (I wouldn't, admitted - but is DES
NP-hard? Is the term even applicable?)
> The trouble with your system is that you don't do anything that's not
> recoverable by the enemy.
That's what I thought, until I made that revealing slip in email to
Alain, which prompted me to think about it a bit.
The statistical properties which seem to me to be relevant in making
braids hard unbraid are
- The statistics of the streams are approximately equal (though even
for the worst reasonable case - plaintext braided with a constant
stream - it's still not trivial to deduce the key stream, though it
certainly is much easier).
- The density of each unit (bit in Alain's scheme) in the plaintext is
(approximately) at least as high as the density of plaintext in the
ciphertext.
The second property seems to me to be the more important.
I'll deal with this a bit further when I get back from lunch.
der Mouse
old: mcgill-vision!mouse
new: mouse@larry.mcrcim.mcgill.edu