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