Note: There are two labtainer exercises below (questions 4 and 5). One is very brief, but you still need to submit the ZIP file, so that means you’ll be doing three submissions for this assignment (written solutions and two labtainer ZIP files).
Joe Crypto always loved playing the “guess which hand is holding a prize” game, so proposes the following guessing game: You can give him two files, containing whatever data you want them to contain, but with the restriction that they must be the same length. He will then pick one of them, encrypt it with a secret key, and then give you the resulting ciphertext. You have to guess which file he encrypted! Joe’s crypto knowledge isn’t so great, however, and he uses AES in ECB mode. How can you play this game so that you can always win? Be very specific, including a clear explanation of why your strategy allows you to win. (Hint: What is the main weakness of ECB mode, and how can you create a file that displays this weakness?)
The previous question was really about the IND-CPA (in)security of ECB mode. In this question we’ll be a little more direct about IND-CPA security. Refer back to our class slides on how the IND-CPA “game” works, and put yourself in the shoes of the adversary, and your goal is to design a strategy where you win this game. Remember that you get to make as many encryption queries as you want, so in both cases below describe any queries you might want to make, how you will pick the challenge plaintexts \(p_0\) and \(p_1\), and then how you’ll decide on your guess \(g\) at the end. I’m looking for careful thinking and reasoning here, not a formal mathematical proof (if you want a more rigorous treatment of this, take the crypto class!).
Consider a cipher that has the following property: When you view the plaintext bits and ciphertext bits as binary numbers, the cipher preserves the evenness of the number. In other words, if the plaintext is an even number then the ciphertext will also be an even number, and if the plaintext is odd then the ciphertext will also be odd. However, the encryption algorithm is not deterministic, nor does it reveal any information other than evenness/oddness.
Prove that such a cipher cannot be IND-CPA secure (in other words, describe how you as the adversary can play the game so that you can always win).
Joe decides to “fix” the cipher by doing the following: he extends the key by adding one more bit. Now this bit, representing 0 or 1, is added to any plaintext by the sender before encryption and subtracted after decryption by the receiver. If this key bit is chosen randomly, then half the time even numbers map to even numbers before encryption, and the other half of the time even numbers map to odd numbers. “HA HA,” Joe thinks (accompanied by him rubbing his hands together in a mildly disturbing way) – now the information about whether the plaintext is even or odd no longer follows from the evenness or oddness of the ciphertext, so he thinks he has foiled your evil scheming! Your task here is to show that you’re smarter than poor Joe: devise and describe a winning strategy for the adversary in this case, showing that this new scheme is still not IND-CPA secure.
Consider adding a special-purpose chip to a computer (or phone) that internally stores a random 256-bit secret \(k\) in such a way that the secret can only be used as the key for executing HMAC (using SHA-256) in the chip. Specifically, all the user can do is send a bitstring \(x\) to the hardware so that it computes and returns HMAC(\(k,x\)). Consider a system that uses this hardware to create a 256-bit key for AES for data storage (a separate device): The user supplies a (possibly low-entropy) password or PIN as \(x\), and then the output of the hardware HMAC is used as an AES key to encrypt and decrypt all data stored on the storage device. We can quickly test whether the hardware gives the correct key by attempting a decryption using it. For this problem, assume that HMAC with SHA-256 satisfies the following property: Without knowing the key \(k\), no information about the value HMAC(\(k,x\)) can be predicted. The only way to get this value is to ask the chip to compute it for you, or to get lucky and guess the output.
What if the storage device is removed from the system and then stolen or sold? In addition to having the encrypted data, the attacker knows the algorithm that the chip uses and knows that \(x\) is some unknown 4-digit PIN, but doesn’t have access to the security chip. How secure is this? Reason about the “best possible attack,” and give some indication of how much time this would take. Informal reasoning is OK, but make sure the logic of your reasoning is clear!
If the entire device (the security chip and the storage device) is captured, so that the attacker can access the HMAC-computing hardware device, what is the best attack in this case? How much time would this take (state any assumptions you need to make about the speed of the hardware device, etc.).
If the hardware deletes the secret \(k\), then the attacker is basically back at the situation in part (a), even if they have the entire device. How could you improve the system so that it can detect and delete the secret \(k\) after a certain number of failed attempts (your goal is to stop brute-force attacks on the PIN). Note that the security chip needs some way of knowing when a use has been successful or not, and an attacker should not be able to trick this detection.
The “capabilities” labtainer exercise is brief and can be completed in under 30 minutes, but it demonstrates a very important security feature of modern Linux systems. Complete the labtainer exercise, with the following change: you do not need to submit the lab report it refers to under “Submission,” nor do you have to answer the questions at the end of Task 2, but you still need to submit the ZIP file which documents your work. Hint for Task 1.2: You may need to refer to the man page “cap_from_text” to see how to format the capability-setting command.
You should also answer this question as part of your written problem submission: What results did you see from Task 2? In other words, which open calls failed? Answer honestly: Did you correctly predict what was going to happen? Then explain in your own words why some calls failed and others succeeded.
Complete the “pass-crack” labtainer exercise, including the lab report and spreadsheet (which are submitted as part of the labtainer ZIP file – there’s nothing to submit as part of the written problems).