Apologies for not updating sooner! In this post, I will give a description of the project I plan to be working on, but first! some background on cryptography!
Currently, the standard for symmetric block ciphers is AES (Advanced Encryption Standard). It is used in many security protocols today. This standard was selected by the National Institute for Standards and Technology for its security and efficient computation. However, since its selection in 2001, a number of attacks have been developed against AES. There is a collection of attacks called side-channel attacks, which have been shown in research to work well.
Side-channel attacks target information leaked from the the physical implementation of the cipher. By measuring side-channel information, like power consumption or computation time, the attacker can figure out what kinds of computation and what kinds of values were used by the encryption device, which leads to information about the secret key. (Note: many modern cipher attacks focus on extracting the key from the encryption. This will also be the goal of this project.)
The particular side-channel attack we will be focusing on is the cache-timing attack. Many software implementations of AES rely on table look-ups, which means that there will be a significant amount of memory accesses. Each memory access can result in a cache hit or a cache miss, events which take different amounts of time. Therefore, the total time taken for an encryption process can leak information about what kinds of values were looked up, leading to information about the key.
Our project goal is to formally analyze the cache-timing attack using ideas from information theory. So the cool part: we are dealing with code-breaking. (Yay code-breaking!) The hard part: The cache-timing attack has many different forms. Implementations of AES, hardware used, form of the attack, and the key information obtained vary significantly. It is difficult to isolate the particular problem we want to work on.
There is more to say about this project, but I don't want to squeeze everything into one post, so I will end here and add another brain teaser questions for readers to ponder about. This question is not so hard if you have some basic knowledge of number theory, otherwise the problem is pretty impossible.
Imagine that you are standing at the origin of the x and y plane. Suppose at every pair of integer coordinates, there is a pole extending up in the z direction. These poles are infinitely thin and extend way over your head. What is the probability that you can see a given pole selected at random?
Saturday, October 27, 2012
Thursday, October 4, 2012
Post 2
I met with my professor's grad student, Eva, last week and we discussed some possible ideas for a project. The conclusion of the meeting was that I still need to do more readings. The paper I am reading now is "The Wire-Tap Channel" by Wyner. It is a very old paper (from 1975), and since it has survived until today, it clearly is very influential. I'm guessing my project can relate to this paper in some way.
Something I found exciting this week was that in my probability class, we proved the law of large numbers and followed up with a corollary about entropy. The corollary was the asymptotic equipartition property. I had learned about this before, but it was cool to see it presented in another class.
Another thing I learned which I thought was interesting was how the information theory notion of entropy related with the notion of entropy defined in the second law of thermodynamics. The second law of thermodynamics states that entropy always increases, but when using Markov chains to analyze a physical system, the information theory entropy of the distribution over time can actually decrease. This was surprising.
Last week, I posted a trivia question. It would make sense for me to post the answer to the question this week, but I don't think anyone has actually read this blog yet. So I will postpone posting the answer.
In the meantime, here is another question which I thought was cute. It is not super difficult, but the idea is nice.
Suppose you have a box with N pieces of string. You reach into the box and randomly take out two ends and tie them together. These two ends can come from the same string or from different strings. You repeat this action until there are not more string ends to tie. What is the expected number of loops?
Something I found exciting this week was that in my probability class, we proved the law of large numbers and followed up with a corollary about entropy. The corollary was the asymptotic equipartition property. I had learned about this before, but it was cool to see it presented in another class.
Another thing I learned which I thought was interesting was how the information theory notion of entropy related with the notion of entropy defined in the second law of thermodynamics. The second law of thermodynamics states that entropy always increases, but when using Markov chains to analyze a physical system, the information theory entropy of the distribution over time can actually decrease. This was surprising.
Last week, I posted a trivia question. It would make sense for me to post the answer to the question this week, but I don't think anyone has actually read this blog yet. So I will postpone posting the answer.
In the meantime, here is another question which I thought was cute. It is not super difficult, but the idea is nice.
Suppose you have a box with N pieces of string. You reach into the box and randomly take out two ends and tie them together. These two ends can come from the same string or from different strings. You repeat this action until there are not more string ends to tie. What is the expected number of loops?
Subscribe to:
Posts (Atom)