What was the BassOmatic cipher, and what made it so weak?

Question

According to Wikipedia, this homebrew cipher was originally used in PGP, before Phil Zimmermann replaced it with IDEA. Supposedly, insecurities in the algorithm were pointed out to him, leading to this change. While I have read the PGP 1.0 source code and saw the implementation of the cipher, that didn't help me actually understand it. I can't seem to find any complete description of the algorithm or, particularly, its weaknesses other than what is provided on Wikipedia:

The chosen key schedule produces a total of 8 permutation tables, each a permutation of the numbers 0 to 255. Each round consists of 4 operations: XORing the block with one of the permutation tables, shredding or permuting individual bits throughout the block, an unkeyed diffusion called raking, and a substitution step using the permutation tables as S-boxes. The shredding step can either permute all 8 bit-planes independently, or in groups of 4, depending on control bit 3. The permutation tables stay the same through all rounds of encryption on a given block, but if control bit 5 is set, then the tables are regenerated after each block.

I could also find a published quote from the book which Wikipedia used as a citation:

After Biham and Zimmermann go their food and sat down, Zimmermann took out a few pages of computer listings. Within minutes, Birham was finding fundamental flaws in Bass-O-Matic. Some of the flaws were subtle-weaknesses that made the algorithm susceptible to differential cryptanalysis, which was Birham’s speciality. Others were more embarrassing, like a conceptual error in Zimmermann’s algorithm that prevented the last bit of each byte from being properly encrypted. After ten minutes of Birham’s onslaught, Zimmermann realized that Bass-O-Matic was a lost cause.

How did BassOmatic work, and what were the weaknesses that lead to its replacement?

Answer 1

Phil Zimmermann did not use DES or the RSA-owned RC-2 as models for the Bass-O-Matic cipher.

For the basis of that symmetric cipher, he used the work of a man named Charlie Merritt. Zimmermann's strong suit was not mathematics but programming in C, so he needed help. Merritt had called Zimmermann by phone (at Metamorphic Systems, a 1980 startup by Zimmermann), and after that fortunate call, they talked more than once a week for several years.

Merritt, a computer programmer from Arkansas,

specialized in writing public-key cryptography implementations. Merritt wrote the first commercially successful implementation of RSA for a personal computer and taught Phil Zimmermann how to do arithmetic with hundred-digit numbers on a personal computer. [1]

Merritt was an expert in assembly language. He had developed an implementation of RSA that was running on Z-80 computers with the CP/M operating system. It took, by the way, ten minutes to generate a 256-bit key. In 1980, Merritt's success in doing this inspired Zimmermann. They talked about Zimmermann putting crypto on his 8088 card for the Apple II, and everything else having to do with cryptography.

Merritt and Zimmermann, "PRZ," got along over the phone. Merritt said,

He began talking about protocols, in great detail. For hours, on the phone. I hate protocols, that's for the Phone Company. But he needed a brick wall. Then he began asking exactly how math was implemented on a Z80. I mean detailed stuff about memory allocation, and adding two giant numbers and what about the carry bit. We were back in my territory. [2]

They finally met face-to-face in the summer of 1986.

Zimmermann labored in the wilderness for years. In November 1986, Merritt was working on a conventional cipher for the U.S. Navy, and this cipher was the basis for the Bass-O-Matic. Zimmermann then made it stronger by adding several rounds of substitution.

Time for the character in black to enter the stage: the NSA periodically threatened Merritt at this time. "They always travel in pairs," Merritt said. Unworried, Merritt started selling his encryption system, the DEDICATE/32, which used 256-bit keys.

Merritt's DEDICATE/32 was slow, and this convinced Zimmermann to create a hybrid system: slow RSA to exchange keys and something quicker for the bulk encryption.

The plot thickens: in 1991, a U.S. Senator sneaked this into a draft bill (S.266):

It is the sense of Congress that providers of electronic communications services and manufacturers of electronic communications service equipment shall ensure that communications systems permit the government to obtain the plaintext contents of voice, data, and other communications when appropriately authorized by law. [3]

Thank you, Senator Joe Biden.

Interestingly, Biden's clause in the draft bill got removed because of the outrage it caused. The furor pushed Zimmermann to release PGP 1.0. PRZ was angry.

Zimmermann let PGP 1.0 loose upon the word, but he said, "the Bass-O-Matic has not yet (in 89) been through a formal security review and has had only limited peer review."

Zimmermann needed to get an expert opinion on the Bass-O-Matic, so he attended Crypto '91 in Santa Barbara, California, in August. He and Eli Biham sat down in the UCSB cafeteria, and Biham told him that the Bass-O-Matic was vulnerable to differential cryptanalysis attack (Biham's specialty). Additionally, the most embarrassing error "prevented the last bit of each byte from being properly encrypted." So, the Bass-O-Matic was unceremoniously thrown into the trash.

Biham had destroyed the Bass-O-Matic in ten minutes over lunch.

Zimmermann then took up IDEA, added key certification, and PGP 2.0 was born.

[1] Garfinkel, Simson (December 1, 1994). PGP: Pretty Good Privacy. O'Reilly Media. p. 372, ISBN 978-1-56592-098-9.

[2] Ibid., 90.

[3] Ibid., 97.