The Guac Bug

Emil Kintsch

“Your full name,” said Alfrey, “and the city where you reside?”

“Dr. Emil Kintsch, Columbia, Maryland.”

“Are you presently employed?”

“Yes. I own and operate Kintsch Associates, a cryptology service.”

“And what does that involve?”

“Two things, basically. We prepare encryption algorithms for clients, and we attempt to decrypt encrypted messages submitted to us by clients.”

“What exactly is an ‘encryption algorithm’, Dr. Kintsch?”

“It’s a computer program organized around a key. Say you want to send a secret message, such as ‘We bid ten million dollars. ’ Now if the key is two digits, say ‘25’, the programwould add 2 to the first letter in the message, and ‘w’ becomes ‘y’. To the next letter we add 5, and ‘e’ becomes ‘j’, and then repeat. To recover the message, the receiver decrypts in reverse.”

“How long would it take a computer to crack that code?”

“An ordinary P.C.? Nanoseconds.”

“Not very secure?”

“No, but of course it was only a two-digit key, about ten bits on the computer. Since a bit would be either zero or one, that key would have two to the tenth bits, or only 1,024 possibilities. To achieve anything approaching even semi-security, one would need a key exceeding 128 bits. That would give a total of two to the power of 128 possible keys—which calculates to 3 followed by 38 zeros. The average mainframe processing a million possibilities a second would need 10 to the twenty-fifth years to try all key variations, with a fifty percent chance of success by the quadrillionth year. And yet the National Security^ Agency permits export of encryption software using a 128-bit key, so we must assume the government has computer capacity in the basements of Fort Meade that can readily decrypt algorithgms using a 128-bit key. Aside from that, we have been able to confirm that a student at the University of California, Berkeley, broke a 128-bit key in three and a half hours using a number of parallel work stations at the college.”

“Are you saying that any code can be broken if given enough time and computer capacity?”

“Most can be broken, not all. They present varying degrees of security. In the extreme case, security can be unconditional, total. Brute force won’t work. For example nobody can break a one-time pad unless he has the key.”

“Explain one-time pad.”

“It’s a key that’s used only once. Both sender and receiver have a sheet with the same random key numbers. The sheet is used once, then destroyed, and they go on to the next sheet. Or instead of a pad of sheets they can use a book. For example ‘201-46’ would mean page 201, line 4, 6th word in the line. They say Rommel used a book in his African campaign.”

“But a key can be useful, even though not totally secure?”

“Oh, absolutely. In fact, that’s the situation with most keys. Security can be only partial, yet adequate, where commercially available computer capacity and time are insufficient to crack the algorithm. We call such algorithms computationally secure’. They can be broken, but not with resources available to the decrypter. For example a megacomputer within the budget of most large corporations can crack a 56-bit key in an average of three and a half hours, seven hours guaranteed. And yet such algorithm can be considered secure from most hackers and private citizens. To be secure from corporate competitors, a much longer key would be required, of course, and to defeat NSA, certainly one considerably longer than 128 bits. Actually, probably no repetitive code can be considered safe from NSA computers. The best the code user can hope for is to delay solution for a few days.”

“Doctor, does your organization have access to megaframe computers?”

“Yes, several. In our own shop, of course, and on loan-time access in over forty universities.”

“All told, roughly comparable to NSA’s computers?”

“We’re getting there.”

“Dr. Kintsch, I hand you a one-page print-out. Can you identify it?”

“Yes. This is the message said to be encoded in ATCC 06. It consists of several thousand letters, G, U, A, and C, in apparently irregular order. You asked Kintsch Associates to decrypt the message.”

“And did you?”

“No. We tried, but we failed.”

“Explain how you tackled the problem.”

“Our major efforts were based on the feet that since there were only four letters in the target message, a simple substitution code—letter for letter—was not indicated. So we asked the computers to try doublets—AC, AG, AU, and so on, looking for repetition and frequencies. This didn’t help. We were able to set up a frequency table, and the computers worked at it for a couple of hours, but no English sentences popped up. Then we went to triads, such as UUU, CCC and so on. We knew, of course, that on a gene each triad made an amino acid in a human cell. But all we got was a string of amino acids. Well, of course we weren’t looking for amino acids, that was a blind alley. It was as though the encrypter was teasing us. We went on to sets of quadruplet letters, then quintuplets, and so on. We ran over fifty megaframes in parallel for seven days and nights.”

“And?”

“Nothing.”

“You tried other systems?”

“Yes. Our associates worked simultaneously, while we were working in our own shop.”

Alfrey returned to his table and picked up a sheaf of papers. He handed one set to Judge Grant, another to Thomas, and the third he handed to the witness. He addressed Grant. “Your honor, these are affidavits of experts in the cryptology field. I would like to describe them briefly for the record.”

“Go ahead, Mr. Alfrey.”

“First, affidavit of Dr. Marvin Mallory, now retired, formerly employed in the CIA Code Office. Dr. Mallory attempted to solve the message with known commercial algorithms, including DES, LOKI 91, IDEA, GOST, and Blowfish. Next—”

“Wait a minute,” Thomas said. “They all say, they used their best efforts, and could not decrypt the target message?”

“Yes.”

“Respondent has no objection to their admission.”

“Thank you. Then I think we’re about through on direct. Just one more question for Dr. Kintsch. Sir, in light of your own work and the findings of these twelve outsider experts, what do you conclude as to decryptability of the message alleged for ATCC 06?”

“Sir, I cannot swear that it is unconditionally secure. If it is decryptable, the key must be quite long, perhaps running to 512 bits or more. By way of comparison, we bear in mind that the Pentagon’s H-bomb secrets and the CIA’s roster of American spies uses only 128 bits. That leaves us with three possibilities. The target message is either computationally secure, or the encryptor used a one-time pad, or it’s a bunch of gobble-de-goop nonsense.”

“In plain English, the solution, if any, is beyond the skill of the art?”

“Yes.”

“Nothing further,” Alfrey said. “Your witness, counselor.”

“Just one question,” Thomas said. “Dr. Kintsch, were you aware that if you or any associates solved the message, you would thereby destroy your client’s patent?”

The cryptographer stared owl-eyed at the lawyer. “Really? I had no idea!”

Thomas grinned. “Nothing further.”

Dr. Kintsch was excused. He bowed sternly to all and left the room.

“And that completes my testimony,” said Alfrey. “It’s only eleven thirty. I’d like to reserve my final half hour for dosing.”

“No objection,” Thomas said. He glanced at his opponent from the comer of his eye. The man radiated victory. Not so last, thought Thomas. It’s not over yet. The arbitrator looked about the room. “Seems a bit early to recess for lunch. Are you ready with your case, Mr. Thomas?”

Respondent’s lawyer was silent.

“Mr. Thomas?” repeated Grant.

“A moment please, your honor. I think—yes—”

There was a knock at the door. Everyone looked around.

Quentin Thomas called out, “Come in!”

The door opened, a girl in a checkered uniform entered, carrying a flat square box. The odor immediately filled the room. Her eyes connected with Thomas’s. She smiled. “Pizza, anyone?”