Simon's Braided Stream Cipher

William "Alain" Simons proposal for using a really-random stream to select between multiple data channels on a bit-by-bit basis. One or more of the channels might also be really-random, in which case new key material can be transported to the far end as a side-effect.

Of course, if we are allowed to expand the ciphertext by 2x, virtually any cipher can transport key material in a separate message.

1991-06-13 Relayed from William "Alain" Simon: The Braided Stream cipher
1991-06-15 der Mouse: der responds negatively
1991-06-17 der Mouse: der responds positively
1991-06-18 Alain Simon: Alain says the Braid is not "new"
1991-06-23 Alain Simon: Alain responds to Jerry Leichter. (Apparently a message was lost in which Jerry claims that a known-plaintext attack will converge into the correct key. But if the key is "really random" that would seem to be little help. Part of the problem here is an inability to pin down what the design really is.)
1991-06-23 Dan Boyd: Dan supports Jerry.
1991-06-23 Doug Gwin: Doug says that the scheme would be stronger if multiple keys could produce the same ciphertext.
1991-06-24 John Nagle: John enters the fray
1991-06-24 Alain Simon: Alain responds to Dan, basically saying that the key is "really random" so that recovering it with a known-plaintext attack is not much of an advantage.
1991-06-24 Dan Bernstein: Bernstein contributes his wisdom
1991-06-24 Peter Wayner: Peter jumps in
1991-06-24 Doug Gwin: Doug jumps on Bernstein
1991-06-24 Dan Bernstein: Bernstein points out that a key-bit is used up for every ciphertext bit. This means that the Braid apparently cannot add to the amount of key by transporting keying material in the second channel.
1991-06-24 Alain Simon: Alain responds to Doug, saying that different keys could produce the same ciphertext
1991-06-24 Alain Simon: Simon says: "take a break"
1991-06-26 Alain Simon: Alain proposes a scheme to increase the amount of transported key material
1991-06-26 Ken Shirriff: Ken thinks braiding is weaker than XOR
1991-06-27 Arthur Rubin: Arthur feels that braiding is a little stronger than XOR
1991-06-27 Alain Simon: Alain responds to Ken I
1991-06-28 Alain Simon: Alain responds to Ken II
1991-06-29 der Mouse: der responds to Dan
1991-07-02 Alain Simon: Alain responds to Arthur I
1991-07-02 Alain Simon: Alain responds to Arthur II: "Eating pretzels." Braiding is weaker than XOR.
1991-07-12 David Seal: David jumps in
1991-07-15 Alain Simon: Alain responds to David
1991-07-17 David Seal: David responds to Alain
1991-07-18 Alain Simon: Alain recapitulates the wandering scheme: "Braid Crumbs"
1991-07-21 Alain Simon: Alain responds to David
1991-07-21 Alain Simon: Alain responds to himself
1991-07-23 David Seal: David responds to Alain
1991-07-24 Terry Ritter: After showing unusual forbearance, Terry can resist no longer and finally responds with some results from balanced combiner theory
1991-07-24 Alain Simon: Alain responds to Terry

[Here at least one Simon and Ritter exchange was lost.]

1992-08-18 Ross Anderson: Ross feels that the Braid was "demolished" in: Anderson, R. 1990. Solving a Class of Stream Ciphers. Cryptologia 14(3): 235-238. But the referenced article attacks multiplexed RNG's, whereas the Braid multiplexes data.
1992-11-05 Alain Simon: Alain points out that the Braid can contain multiple different ciphertexts, a characteristic which could be useful in forced contact with law-enforcement.

Terry Ritter, his current address, and his top page.

Last updated: 1995-10-31