## Lecture 11

October 7, 2009

In this lecture we continued our discussion of “crypto pitfalls”, focusing on several case studies that I hope you found interesting. As examples of bad crypto, we covered the flaws in WEP and the gross mistakes in the Diebold e-voting system. We also highlighted the recent attack on SSH as an example of where even the best crypto can potentially be “broken” when the system does not match the ideal model in which security is proved.

At the end of class, we looked at the recent “cold boot” attacks that demonstrate how crypto is worthless if the adversary can extract the keys.

I was planning on covering timing/power attacks in today’s lecture, but will pick up with this next time. Then we will move on the a few lectures on “system security”.

I’d love to hear people’s reactions to the articles, once you have read them.

## Lecture 10

October 5, 2009

In today’s lecture we continued to cover “crypto pitfalls”, and also began discussing some case studies from the paper “Why Cryptosystems Fail” (linked from the course website).

Several students raised some interesting points in class, and I hope those students will provide pointers to the examples they mentioned.

## HW2

October 2, 2009

Homework 2 is now out. Start early! Note also that this homework must be done in teams of 2 students. You can use the class forum if you need help finding a partner. (I believe there are an even number of students in the class, so it should be possible for everyone to pair up.)

## Lecture 9

September 30, 2009

Today we covered public-key encryption schemes secure against chosen-ciphertext attacks as well as digital signature schemes. This concludes our discussion of the low-level details of cryptography, though we will continue to see applications of cryptography throughout the rest of the course.

At the end of today’s lecture I mentioned some ‘pitfalls’ that can arise when using cryptography. In the next 1-2 lectures we will see some case studies of things that can go wrong. Please try to read the essays/papers assigned to today’s lecture and next Monday’s lecture in time for Monday’s class. I will also post papers for next Wednesday’s lecture. (One is already there.) These papers are required reading for the midterm exam.

## On symmetric-key sizes

September 30, 2009

Bruce Schneier has a post to which I couldn’t resist linking. He discusses why a 49,000-bit key is ridiculous, the dangers of using “home-brewed” cryptography, and the thermodynamic limits of brute-force search (much better than I did in class).

## Encryption and authentication protocols

September 29, 2009

In case you missed it, a question I asked on this blog way back in lecture 4 has generated a bit of discussion (which I am glad to see!). I’ll try to come up with similar questions on other lectures…

## Lecture 8

September 29, 2009

Because of Yom Kippur, we had a guest lecturer (Prof. Arbaugh) talk about malware and rootkits. I hope you found the subject interesting!

After speaking with Prof. Arbaugh, and because some students had to miss class also, I have decided that this lecture will not be considered ‘required material’. (I.e., it will not be covered on the midterm or final exams.)

## Announcements, week of Sept. 28

September 26, 2009

On Monday, I will miss class due to Yom Kippur. There will be a guest lecture by Prof. Bill Arbaugh on rootkits (not wireless security as I announced in class).

In Wednesday we will pick up where we left off in the last lecture. I have also listed some reading that should be done before class. We will begin discussing those articles in Wednesday’s class and continue next Monday. (Although it looks like a lot, the first three links are short essays and at least two of the final three links should be fun to read.)

I have also posted some articles to read for next Monday’s lecture, and I may add 1-2 more.

In addition to the above, I have listed several optional articles. In some cases we will discuss these briefly in class but I thought the articles themselves were too technically difficult to make required reading. In other cases we will not have time to discuss them in class but they reinforce the material or are just plain interesting. Feel free to discuss or ask questions about any of them on the blog.

## Textbook RSA examples

September 23, 2009

I will give one worked out example, followed by a partial one. (Recall that textbook RSA encryption is insecure and should not be used. This is just for illustration.)

Say the receiver chooses $p = 137$ and $q = 127$. Then $N=pq=17399$ and $\phi(N)=136 \cdot 126 = 17136$. Take public exponent $e=5$ (one can verify that $gcd(5, 17136)=1$). Then $d=13709$ because $5 \cdot 13709= 1 \bmod 17136$. The receiver publishes the public key $(N=17399, e=5)$.

Say the sender wants to send the message $m=16410$. She would compute $c=m^e \bmod N$ or $16410^5 = 8321 \bmod 17399$ and send the ciphertext 8321 to the receiver.

The receiver can decrypt the ciphertext 8321 by computing $8321^d \bmod N$ or $8321^{13709} = 16410 \bmod 17399$. (Note: these numbers were already too large to be handled by ‘bc’ directly. One can compute the result in several steps, using the fact that $8321^{13709} \bmod 17399 = 8321 \cdot (((8321^2 \bmod 17399)^2 \bmod 17399)^{23} \bmod 17399)^{149} \bmod 17399$. (Why?))

Now I’ll try a smaller example. Choose $p=17$ and $q=23$, and take $e=3$. What will the receiver’s public key be? What will it’s private key be?

Say the sender wants to send the message $m = 257$. What will the ciphertext be?

Verify that the receiver can correctly recover the message from the ciphertext.

## El Gamal examples

September 23, 2009

I will give one worked out example, followed by a partial one. As in class, this example is not entirely accurate and you should not rely on it to implement El Gamal encryption for real.

Note that you can easily perform modular arithmetic (on “small” values) using the ‘bc’ command on unix. E.g., you can compute $5^2 \bmod 24$ by typing ‘bc’ at the unix command line and then typing $\verb+5^2 % 24+$.

Say the receiver chooses prime $p = 71$, and $g=33$ (one can check that 33 is a generator of ${\mathbb Z}_{71}^*$), and secret exponent $x=62$. Then $h = g^x \bmod 71 = 10$. (I won’t explicitly write the “$\bmod 71$” anymore.) The receiver would publish the public key $(p=71, g=33, h=10)$.

Say a sender wants to send the message $m=15$. It chooses random exponent $r=31$, say, computes the ciphertext $(g^r, h^rm) = (62, 18)$, and sends this to the receiver.

To decrypt the ciphertext $(62, 18)$, the receiver needs to compute $18/62^x = 18/62^{62}$. Recall that dividing by 62 modulo 71 really means to multiply by $62^{-1} \bmod 71$. We did not discuss how to compute multiplicative inverses in class, but one can verify that $62^{-1} = 63 \bmod 71$ because $62 \cdot 63 = 1 \bmod 71$. Thus, the receiver will compute $18 \cdot (62^{-1})^{62} = 18 \cdot 63^{62} \bmod 71 = 15$. Of course, this was exactly the message sent by the sender!

Now a partial example. Let’s take $p=107$ and $g = 2$. (One can check that 2 is a generator of ${\mathbb Z}_{107}^*$.) Say the receiver chooses secret exponent $x=29$. What would the receiver’s public key be?

Now say a sender wants to send the message $m=100$ using random exponent $r=19$. What would be the ciphertext computed by the sender?

Finally, verify that decryption successfully recovers the message. (You may have difficulty finding the correct multiplicative inverse. Hint: $2^{-1} = 54 \bmod 107$.)