12
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ For what it's worth, a (tiny) bit more info can be found in the "Algorithm" section at cryptography.wikia.com/wiki/BassOmatic but that's about all I could find about that 80s cipher thingy. If all fails, you could of course extract the exact workings of the cipher from the old PGP sourcecode (<= version 1). $\endgroup$
    – e-sushi
    Sep 1 '18 at 10:12
  • $\begingroup$ @e-sushi Yep, that does have a bit more info about the control bits, but it's just an exact copy of the Wikipedia page, so nothing I haven't already seen (I just didn't quote it). $\endgroup$
    – forest
    Sep 1 '18 at 19:21
  • 9
    $\begingroup$ For reference, everyone can download the original PGP 1.0 source code from pgpkeys.org/bin/unix_pgp10.tar.gz, the BassOmatic implementation is available in basslib.c. $\endgroup$ Nov 8 '18 at 19:28
  • $\begingroup$ The Bass-O-Matic is a good example of how one sturdy piece of information can get copied and proliferate across dozens of websites--which makes it much harder to find any new information that is relevant. $\endgroup$
    – Patriot
    Jul 21 '19 at 5:11
6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ There is a common thread in the stories of Diffie and Zimmermann--stubborn perseverance, tenacity. $\endgroup$
    – Patriot
    Feb 22 at 17:33
  • 1
    $\begingroup$ This is interesting background for the cipher and an explanation of its timeline but doesn't really describe its properties or what made it weak cryptographically, other than stating that it was vulnerable to differential cryptanalysis and had "an embarrassing error" involving certain bits' encoding. $\endgroup$
    – forest
    Feb 23 at 1:55
  • $\begingroup$ @forest I completely agree. It is going to take further research. I would like to know more about the symmetric cipher that Merritt made for the U.S. Navy because that was the backbone of the Bass-O-Matic--or so it seems. $\endgroup$
    – Patriot
    Feb 23 at 11:14
  • $\begingroup$ @forest As you probably know, the Bass-O-Matic was amateurish, and Zimmermann wasn't too proud of it. We have evidence that the Bass-O-Matic was Merritt's Navy cipher plus several rounds of substitution. Hopefully, I can dig into this more deeply sometime. $\endgroup$
    – Patriot
    Feb 23 at 13:05

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .