Friday, April 20, 2018

Book review. Crypto: How the code rebels beat the government---saving privacy in the digital age.

In graduate school, I had read "Hackers: Heroes of the Computer Revolution" from Steven Levy and enjoyed it a lot. (I still keep the dog eared paper copy with affection.) So, I should have read Steven Levy's Crypto book a long time ago. But for some reason, I didn't...even though I was aware of the book. I guess that was due to a stupid quirk of mine; I had some aversion to the security/cryptography research. I don't know why. Maybe it was because I had sat through a couple of bad security/cryptography talks (a similar aversion happened to me after a bad networking course). Another reason, I regret to admit, may be that I had some distributed systems snobbery going on that time. I was so into the distributed systems/algorithms area that I was quick to label AI, security, and this, and that as uninteresting or useless *to me*. I wish I could have been more open minded. I am sure reading this book then would have changed my outlook toward security and cryptography.

(Side Remark: The lesson, kids, is to always keep an open mind. Being a snob is stupid. I have been seeing snobbery against blockchain work among some systems researchers, and that is wrong. I have criticized some parts of blockchain and fully-decentralized approaches many times on this blog, but I know better than being a snob. My brain is open, I am reading about it, and when I find something interesting and suitable for my skillset, I will be happy to work more on it and contribute.)

Coming back to the book, I recommend this book very highly. The book skillfully combines very personal stories of the researchers involved in crypto work with simple explanations of the important technical materials. Levy sure knows how to tell stories.

Now to be hypercritical and to nitpick, I thought the writing felt somewhat rushed in some places. I thought the writing in the Hackers book was more skilled and better refined. My guess is Levy had to rush this to publication. There were occasional ambiguous sentences, which a careful editor and proofreader would have caught.

Some selected parts from the book

I am not going to do a proper book review. Instead I find it more fun to include tidbits from the book without providing any context.

Pages 21&24: Whit Diffie is a careful reader

By now Diffie had finally gotten around to reading David Kahn's The Codebreakers. Since Diffie was a very slow, methodical reader, tackling a book of a thousand densely packed pages was a major undertaking for him. "He traveled everywhere with that book in hand," says his friend Harriet Fell. "If you invited him to dinner, he'd come with The Codebreakers." But Diffie found the hundreds of hours he spent on the book to be well worth the trouble.
"I read it more carefully than anyone had ever read it. Kahn's book to me is like the Vedas," he explains, citing the centuries-old Indian text. "There's an expression I learned: 'If a man loses his cow, he looks for it in the Vedas.' "
Why had Diffie's once-intermittent interest become such a consuming passion? Behind every great cryptographer, it seems, there is a driving pathology. ... "I had been looking all my life for some great mystery. ... I think somewhere deep in my mind is the notion that if I could learn just the right thing, I would be saved."

Pages 31-33. Diffie meets Hellman

"It was a meeting of the minds," says Hellman.
The half-hour meeting went on for an hour, two hours, longer. Hellman simply didn't want it to end, and Diffie, too, seemed eager to continue as long as possible. Hellman had promised his wife he'd be home by late afternoon to watch their two small children while she went off, so finally he asked Diffie back to his house. No problem! Diffie called Mary and she came over to have dinner with Whit and all the Hellmans, and it wasn't until 11:00 or so that night that the dialogue broke up.

Page 67. Diffie's existential crisis

Mary Fischer recalls the lowest point. One day she walked into the McCarthys' bedroom and found Diffie with his head in his hands, weeping. "I asked him what was wrong," she says, "and he told me he was never going to amount to anything, that I should find someone else, that he was --and I remember this exact term-- a broken-down old researcher."

Page 69. Diffie's breakthrough

That spring, Diffie had settled into a routine at the McCarthy house. Every morning he would make breakfast for Mary and Sarah, McCarthy's fourteen-year-old daughter. Then Mary would go off to work, Sarah would go off to school, and Diffie would stay home. One day in May 1975, he spent the morning hours thinking. After a lunch break, he returned to his mental work. For the umpteenth time, he had been thinking about the problem of establishing a secure log-in password on a computer network. Again, there was that old problem of having to trust the administrator with the secret password. How could you shut that third party out of the scheme entirely? Sometime in the afternoon, things suddenly became clear to Diffie: devise a system that could not only provide everything in Diffie's recently envisioned one-way authentication scheme but could also deliver encryption and decryption in a novel manner. It would solve the untrustworthy administrator problem, and much, much more.
He would split the key.

Pages 77-78. Merkle the Berkeley undergraduate student

Instead, for reasons that remain unclear but are probably related to Merkle's unconventional mind, he fixated on what struck him as a weird, somewhat challenging aspect of a more basic dilemma. The essential cryptographic scenario assumed that the channel of communication was vulnerable. ... But what measures could you exploit if you wanted to communicate with someone who wasn't already in possession of a pre-arranged, secure symmetrical key?
Merkle, unpolluted with knowledge about theory or history of crypto, was unaware of the apparent impossibility of his mission. He simply tried to solve the problem.

Pages 90-100. Enter Ron Rivest and the RSA algorithm

Even so, "New Directions in Cryptography" [Diffie-Hellman 1976 paper] turned out to be more than interesting to Rivest: it thrilled him. Ultimately, it changed his life.
The paper appealed to Rivest's heart as well as his head. Rivest was a theoretician, but one for whom simple abstractions were not enough. The ideal for him was actually putting the ethereal mechanics of math to work, of making a tangible difference in the world of flesh and dirt.

On April 3, 1997, a graduate student named Anni Bruce held a Passover seder at her home. Rivest was there, and Shamir, and Adleman. For several hours ideas of mathematical formulas and factoring were put aside for a recapitulation of the escape of the Jewish peopole from Egypt. As is customary with seders, people downed a lot of wine. It was nearly midnight when Rivest and his wife returned home. While Gail Rivest got ready for bed, Ron stretched out on the couch and began thinking about the problem that had consumed him and his colleagues for months. He would often do that---lie flat on the sofa with his eyes closed, as if he were deep in sleep. Sometimes he'd sit up and flip through the pages of a book, not really looking, but reworking the numbers. He had a computer terminal at home, but that night he left it off. "I was just thinking," he says.

That was when it came to him---the cognitive lightning bolt known as the Eureka Moment. He had a scheme! It was similar to some of their more recent attempts in that it used number theory and factoring. But this was simpler, more elegant. Warning himself not to get overexcited---Shamir and Adleman, after all, had broken many of his previous proposals---he jotted down some notes. He did allow himself the luxury of saying to his wife that he'd come up with an idea that just might work. He doesn't remember phoning the guys that night. Adleman, though, insists that he received a call sometime after midnight.

Rivest insisted that it was a joint project, that Shamir's and Adleman's contributions were crucial, that the scheme was the final point in an evolutionary process. To Rivest, it was as if the three of them had been in a boat together, all taking turns rowing and navigating in search of a new land. Rivest might have stepped out of the boat firs, but they all deserved credit for the discovery.

Where is the sequel?

OK, I am tired of typing. The book is 300 pages, and I only wrote a few of the most interesting parts in the first 100 pages. Please go read the book, I think you will like it.

I hope Steven Levy writes a followup book on Bitcoin and blockchain. The book stops around 2000 after discussing David Chaum's Digicash. So cryptocurrencies and blockchain would be a natural sequel to this one. 

MAD questions

Both Diffie's and Rivest's breakthroughs came after many months of intense work and thinking. But after the breakthrough insight, the schemes become easy to derive and explain. That is sort of like a one-way trapdoor function, isn't it? A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". Trapdoor functions are widely used in cryptography.

I don't think there was chance involved in these discoveries. It seemed like those ideas were up in the air, vaguely hovering, and they had to go through a laborious condensation period before they materialized.

But here is an interesting page on the role of chance/serendipity in scientific discoveries.  Psychologist Kevin Dunbar and colleagues estimate that between 30% and 50% of all scientific discoveries are accidental in some sense.

Here is another interesting page on multiple discoveries / simultaneous invention. Merton believed that it is multiple discoveries, rather than unique ones, that represent the common pattern in science.

No comments:

Two-phase commit and beyond

In this post, we model and explore the two-phase commit protocol using TLA+. The two-phase commit protocol is practical and is used in man...