(Review questions) Cryptography

Cryptography

1. How many permutations are possible over n-bit messages? Permutations are invertible functions, also known as bijection. E.g., there are 2 permutations that are possible over 1-bit message. {1->0, 0->1}, {1->1,0->0}. How many functions are possible over n-bit messages? (Functions take an n-bit message and output an n-bit message.) Remember functions do not have to be invertible, so the number better be more than the number of permutations.
2. The last output block in CBC-mode encryption depends on all the earlier blocks of the message. Changing any message block, therefore, would change the last output block. But it is told in the class that it is not sufficient for integrity. Why is it so? To provide integrity, a scheme should ensure an attacker cannot come up with a valid message, tag pair without having access to the key. So, for CBC mode can you create a valid message, tag pair without knowing the key? You can assume you have access to the encryption/MAC oracle.
3.  What will be the security game for the chosen-ciphertext attack (CCA)? Assume the attacker can only access the oracles before producing the challenge.
4. Consider a New-AES-CBC mode encryption technique, that works almost like the normal CBC mode, except for the following change. The key size is 256 bit instead of 128 bit. And instead of picking a random initialization vector (IV), it uses half of the key as IV. The IV is then not prepended to the ciphertext, because it is already part of the key and the recipient already has it. Is tthis New-AES-CBC cipher mode secure? If yes, why? If not, can you give an attack on this mode? Related question: What will go wrong if the IV is set to NULL? For full credit need to show an attack that recovers a plaintext (or part of it) in a chosen-plain text attack (CPA) attack.
5. Given a plaintext, do you think encrypting iteratively increases the security guarantees? If E denotes an encryption algorithm and m is the message, do you think E(k1, E(k1, m)) stronger than E(k1, m)? Why or why not?  A slightly related question:  3DES is a technique which applies the DES algorithm 3 times to the same data block. The steps involved are encrypt-decrypt-encrypt: E(k1, D(k2, E(k1, m))). Can you think of a reason why a decrypt operation is used instead of an encrypt-encrypt-encrypt?
6. What are the advantages and disadvantages of counter mode over the CBC mode of encryption?
7. Among the different crypto operations, which ones would you like to be fast and why: encryption, MAC, hashing, digital signature? Give scenarios where you want an operation to be fast (or slow, if applicable).
8. Suppose c is one block long, a and b are strings that are a multiple of the block length, and M(a||c) = M(b||c), where M is CBC-MAC. Then M(a||d) = M(b||d) for any block d. Explain why this claim is true.
9. Authenticated Encryption (AE)
   
   1. What are the security requirements for a secure authenticated encryption scheme? (Hint: it should be a union of the security requirements of a secure encryption scheme and a secure MAC.)
   2. Why MAC-and-Encrypt way of combining encryption and MAC is not secure?
   3. Why do we have to use different keys for MAC and Encrypt in encrypt-then-MAC approach? 
   4. Refer to the authenticated encryption with associated data (AEAD), can you give two examples of the associated data that you think should not be encrypted but need to be authenticated? 
10. How will Alice and Bob share a secret key? Here is an approach, analyze it's security. Bob has a public key pk, which Alice got from the "internet telephone directory". Alice generates a random 256-bit key  k, encrypts k using RSA encryption procedure, and send the ciphertext c to Bob. Bob then decrypts c using the secret key (sk) it holds and obtains the k. What are the security issues with this approach of key negotiation? Give two possible attacks on this.  Hint: Can Eve pretend to be Alice to Bob? Can Eve manage to get them to pick an insecure key k'?