The following students have passed the first written exam. The table reports the grade for the written part, the extra bonus for the challenges and the final grade.
NOTE: this is the base for your final grade after the Lab of next semester. It is up to you to keep this score or repeat the written part.
Solutions to the exercises
As usual you are invited to post questions and comments.
Consider a cipher such that , . Encryption function is defined as:
- Give the formal definition of decryption function , proving its correctness: ;SOLUTION:Decryption is obtaining by reversing all the operations: , where is the inverse of substitution. Correctness is proved as follows (every operation done modulo 26):
- Given :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z R T F C I X J M E Z U K V Q P Y G O W B D N L H S A
decrypt the ciphertext KZHM under key ;
SOLUTION: Since is the inverse of substitution, reading `upside-down’ we get:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Z T D U I C Q X E G L W H V R O N A Y B K M S F P J
Decryption is then done as follows (to improve readability we write K to note the integer representing K and we assume everything is done modulo 26):
The resulting plaintext is SAIL.
- Encryption/Decryption under can equivalently be achieved with a simple substitution cipher under key . Show explaining the method to obtain it;SOLUTION:Intuitively, since shift is a particular substitution, the cipher is the composition of three substitutions, which is still a substitution. We can find it as follows (as usual we omit modulo 3 for readability):
where is obtained by shifting the lowest part to the left by 3 positions (to incorporate the right shift of the letter):
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z C I X J M E Z U K V Q P Y G O W B D N L H S A R T F
and is obtained by subtracting 3 to any single letter:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Z F U G J B W R H S N M V D L T Y A K I E P X O Q C
We can, for example, recompute the encryption of word SAIL by applying :
- Show that if we use key with the above fixed and with picked at random for each encryption, the resulting cipher is perfect.SOLUTION:This was, in fact, a trick question since the resulting cipher is NOT perfect. (None of you have solved the exercise. Retrospectively I have realised that this was a bit to catchy and difficult and I have basically evaluated only the way you have reasoned).If we only vary k we have that the number of possible keys is 26 meaning that . We can then apply the characterization of perfect ciphers. Since we assume that k is picked at random (), we know that the cipher is perfect if and only if for any and there exists exactly one key such that . Unfortunately this does not happen because some of the mappings in shifts letter of the same quantity. For example and which is a +1 shift modulo 26. Now take O and P as plaintext/ciphertext. It is clear that but it is also true that since . Intuitively, when shifts the letters of the same quantity the +k and -k simplify and we get the same mapping. Since we have shown that keys 0 and 11 both map O into P we have that the cipher is not perfect.
This is a good example showing that composition of ciphers might be worse than a single cipher (shift cipher alone is in fact perfect when k is picked at random).
Give the definition of ECB and CBC block cipher modes of operation and discuss why chained modes such as CBC are, in general, to be preferred to ECB ?
Solution: This was a theoretical question that is basically answered here (see the pros/cons paragraphs for the modes).
It is developed a web-based application over http (no TLS/SSL) that adopts the following protocol for authentication (and key exchange) of Alice with respect to Bob:
where is a nonce is a fresh session key generated by Alice and is the MD5 hash of the a 5-digit that Alice share with Bob. Discuss the (in)security of this protocol.
SOLUTION: The protocol is a standard ISO/IEC 11770-2 key exchange protocol (in particular it is the ‘two-pass unilateral key-establishment’). Thus, the protocol by itself is considered secure. The problem is using as a key the MD5 hash of a 5-digit PIN. This value can be easily brute-forced by trying all the possible 100000 values of the PIN in a few seconds. To check if the value is correct it is enough to try to decrypt the second message an see if the resulting ID and nonce match with the expected ones. The attacker thus intercepts a session and finds the PIN by brute-forcing. Once the PIN is known he can impersonate Alice in any subsequent session.
Many of you have missed this vulnerability and have instead based their proposed attack either on the recent vulnerabilities on MD5 collision resistance or on the birthday attack. Breaking collision resistance (directly or with birthday attack) is of no use here as it provides two values with the same hash and NOT a value that collides with a given one, i.e., the hash of Alice PIN. This latter task amount to find a second preimage and is strictly more difficult than breaking collision resistance. In particular MD5 is not known to be subject to this attacks and the complexity of a brute-forcing would be in the order of , thus infeasible.
The RFID token of a coffee machine (as the one here in the department) is recharged with 1€ using the following protocol:
where is a long term symmetric key shared among the machine and any token. Show an attack on this protocol and propose a solution.
SOLUTION: This protocol does not contain any time-variant parameter and any ID of the parties. These usually imply replay and reflection attacks, respectively. While reflection is not very interesting here (since the protocol is by its nature directional from the machine to the tokes) replays are of course critical. An attacker could recharge a token an unbounded number of times by simply intercepting the message and resending it as many times as he wants. Standard fixes are based on sequence numbers, timestamps and nonces. For this specific setting nonce-based solutions are more practical since the assume no synchronisation on clocks (that are not typical implemented on coffee machines tokens) on sequence numbers. The only assumption would be to have a pseudo-random number generator in the token. The protocol would be:
Adding identity would make the protocol compliant to the ISO ones, which is not a bad idea even if reflection is prevented by the ‘asymmetry’ of the application.
Exercise 5 (optional, gives extra score)
Illustrate how Rainbow Tables are used to break one-way hash functions.
SOLUTION: Rainbow tables are described and discussed here