Path: cactus.org!milano!cs.utexas.edu!news-server.csri.toronto.edu!bonnie. + concordia.ca!thunder.mcrcim.mcgill.edu!mouse From: mouse@thunder.mcrcim.mcgill.edu (der Mouse) Newsgroups: sci.crypt Subject: Re: Braided Stream Communication Multiplexer Message-ID: <1991Jun17.155825.1019@thunder.mcrcim.mcgill.edu> Date: 17 Jun 91 15:58:25 GMT References: <13451@pt.cs.cmu.edu> <1991Jun15.213424.5917@thunder.mcrcim. + mcgill.edu> Organization: McGill Research Centre for Intelligent Machines Lines: 62 In article <1991Jun15.213424.5917@thunder.mcrcim.mcgill.edu>, I wrote: >> The Braided Stream (used to be known as: Entropy Insertion) >> Communication Multiplexer is a simple and fast system which allows >> for high levels of confidence without having recourse to weak, >> dubious, or controlled, technologies. > I'll summarize. The essence of the system is to interleave data > streams, with key bits choosing which stream to take the next bit from. > This strikes me as dreadfully insecure. [...] After an email exchange with Alain, I would like to publicly apologize to him for criticizing his system before actually thinking about it. What happened was that I mentioned, in passing, that his system had the advantage that one could pull almost any desired cleartext out of almost any ciphertext by a careful choice of the key. What I didn't notice was that this implies the system verges on unbreakable - for how would you know when you've got the right cleartext? Just to make sure I was right, I wrote a program. This program takes "real" cleartext and interweaves it with noise, using a noise key. It then takes a "desired" cleartext and deduces keys that would generate the "desired" cleartext from the ciphertext. Here is a sample run, truncated at the end because it produces great quantities of output. The "real cleartext" corresponds to "cleartext " and the "desired clear" to "junk junk.". The key and noise streams were generated with a PRNG. The "false key" streams were deduced from the "cipher" and "desired clear" streams by a simple greedy algorithm, with backtracking to generate multiple streams; this could be improved to generate "better" false key streams. real clear : 110001100011011010100110100001100100111000101110101 00110000111100010111000000100 key : 000001111100000011111101001101111100101011111001100 0111100101111010010001011001000011100100010001101101000011111011010 1100110001111010101000011011111100 noise : 111101101101100100111101000010000010111000011100010 000010001011100101111 cipher : 111101100011011011000111100101010110000111010110010 1011000001001011010000000101111001100101101001001010000011000001110 1100001010101111100010100100010011 desired clear : 010101101010111001110110110101100000010001010110101 01110011101101101011001110100 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000110101001100111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000110101001010111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000110101001001111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000101101001100111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000101101001010111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000101101001001111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000011101001100111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000011101001010111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111111000011101001001111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111110100110101001100111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111110100110101001010111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111110100110101001001111 false key : 000011010010111110100100010101011001000111110101010 1110100001001100101111000110000111010111111101101010000010110001111 11100010111110100101101001100111 In view of this, I retract my earlier criticism. Alain's scheme is, I now feel, approximately as secure as its key. der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu