| Problem Set 2 |
Out: 8 February 2005 Due: 15 February 2005 (beginning of class) |
Collaboration Policy
For this assignment you are encouraged to work with one other student (of your choosing). If you are looking for a partner, try the CS588 forum at http://www.cs.virginia.edu/forums/. You and your partner should contribute equally to the assignment and should turn in one assignment with both of your names on it. If you prefer, you may work alone.Problem set answers may be hand-written, but only if your hand writting is neat enough for us to read it. For full credit, answers must be clear, elegant and concise.You may consult any outside resources you wish including books, papers, web sites and people; the only resources you may not use without explicit permission are materials from previous offerings of this couse. If you use resources other than the class materials, indicate what you used along with your answer.
SpeedyPass
After reading this article, Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key (New York Times, 29 January 2005), Suv Phan, owner/operator of Charlottesville's local ExoffNoble station, decided he had better replace his SpeedPass system with a new, uncompromised design. He hired WillCodeForCurry, the cheapest consulting firm he could find to develop the new system since he did not want to pay the high consulting fees typically charged by CS588 graduates.The designers at WillCodeForCurry did not pay attention in their security course when they were told security through obscurity is rarely successful, and did not think it would be useful to read the technical paper on the DST break (you, on the other hand, may find the paper useful):
Steve Bono, Matthew Green, Adam Stubblefield, Ari Juels, Avi Rubin and Michael Szydlo. Security Analysis of a Cryptographically-Enabled RFID Device. Submitted to USENIX Security 2005. 28 January 2005.As a result, the SpeedyPass system they designed may not be very secure. WillCodeForCurry is keeping the implementation details of SpeedyPass secret, since they hope keeping their encryption algorithm secret will make it secure. (Strictly it is not an encryption algorithm — it is not invertible.) They did, however, send a memo to Suv Phan to convince him of the security of their design, which you intercepted. The memo is found at the end of this problem set.
As a loyal customer of Suv's gas station, you have purchased a SpeedyPass device. However, as a not-yet graduated CS588 student, you have limited income, and think it might be preferrable if the charges to your SpeedyPass go to some other account. (Of course, as an honorable UVa student, you wouldn't do this for real.)
The Java class linked here simulates the SpeedyPass device. Note that the easiest way to solve this problem would be to disassemble the Java class file and figure out what it does by examining the code. This is not permitted. You should treat the SpeedyClass as a black box: you may execute it as many times as you want and observe its output, but you may not examine it in any other way. (Note that the authors of the RFID paper faced this same requirement. Even though they could obtain access to software implementations of the DST algorithm, since it would have violated software licensing agreements if they attempted to reverse engineer the code.)
Download the SpeedyPass program: SpeedyPass.class
The SpeedyPass program can be run two ways:
- Sending a challenge to the device that is still containing your key: java SpeedyPass challenge. The SpeedyPass simulator will print out the response to the challenge using your secret key.
- Loading a given key and sending a challenge: java SpeedyPass -k key challenge. The key and challenge are four bit values, encoded as decimal numbers between 0 and 15. For example, java SpeedyPass -k 1100 0011 simulates loading 1100 into the SpeedyPass key register, and sending it the challenge 0011. The program will print out the SpeedyPass response to the challenge.
2. (10) Determine the secret key contained on your SpeedyPass.
3. (40) Determine everything you can about the functions implemented by the boxes labeled A, B, C, D and E in the Curry Cipher Schematic (in the Intercepted Memo below). A good answer will describe your strategy for determining the function of each box and express each box clearly as a function. (Even if you are not able to determine all the boxes, turn in an answer that explains what you attempted and what you were able to learn about them.)
4. (10) Are there any properties of the Curry Cipher that make it even less secure than one would expect based just on the small key length and small number of rounds? (Hint: can you be sure your answer to question 2 is actually the key stored in your SpeedyPass?)
5. (30) To be able to purchase gas from Suv, you would need to acquire the key stored in someone else's SpeedyPass device. If the device is near enough, you can do this by sending challenges to the device and analyzing its responses. What is the minimum number of challenge/response pairs you need to acquire the key? Explain how.
|
Dear Suv,
Please find enclosed our SpeedyPass implementation and invoice. You can be absolutely sure that SpeedyPass provides you with unbreakable security since I am the only person who knows the inner logic of our newly designed encryption algorithm. As you wisely requested, our "friends" have already "taken care of" the people we hired to fabricate the RFID devices. To calculate the challenge response, SpeedyPass uses a 2-round Feistel cipher with a structure similar to that used by the Kaiser Cipher in SpeedPass. Because our design uses only 2 rounds, however, our algorithm is much cheaper to implement than their design! It stores a 4-bit key, and receives a 4-bit challenge. The response is 4-bits. Since there are 24 (trust me, this is a very big number, but with your limited mathematical background you wouldn't be able to fathom it) different possible responses, there is no way anyone could guess the correct response unless they have a legitimate SpeedyPass. The structure of our cipher is shown below. The boxes labeled A, B, C, D and E perform very complicated operations with which I won't bore you, other than to mention they include more than one use of an operation that Claude Shannon proved can be used to provide theoretically perfect secrecy!
Sincerely, PS. If any of those pesky CS588 students try to convince you our design is insecure, keep in mind they are just trying to get you to pay their hefty consulting fees. I trust that you, like me, are a brilliant businessman, and would not waste your money on something so frivolous. They'll probably just give you some useless Scheme code anyway. PPS. I am anxiously awaiting your SpeedyPayment. Please make sure to send us the "Thai Spicy Hot" curry, as previously agreed (don't forget what happened to those RFID fabricators).
Curry Cipher Schematic |
Credits: Curry Cipher designed by Matt Spear. Problem Set tested by Nate Paul and Ana Nora Sovarel.
