Exam 10 January 2012

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.

ID First Name Last Name Exam Chal. Grade
811848 Marco Signori 30L 7 30L
812773 Vito Capocchione 22 2 24
813917 Daniele De Rosa 24 2 26
817622 Lorenzo Donati 20 20
815361 Alessandro Frazza 25 25
812882 Andrea Gasparetto 25 2 27
810733 Davide Gastaldon 16 2 18
825210 Simone Golfetto 27 27
840168 Luca Pizzolato 24 24
816511 Francesco Pizzolon 19 1 20
817757 Alessandro Popaiz 29 2 30
820955 Andrea Pretotto 18 2.5 21
810881 Luca Zorzi 30L 7 30L

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.

Exercise 1

Consider a cipher such that {\cal P} = {\cal C} = \mathbb{Z}_{26}, {\cal K} = \{ (\rho,k) \ | \ \rho,\mathbb{Z}_{26} \rightarrow \mathbb{Z}_{26} \mbox{ bijective and } k \in \mathbb{Z}_{26} \}. Encryption function is defined as:

E_{(\rho,k)}(x) = \rho(x + k\!\!\!\mod 26) - k\!\!\!\mod 26
  1. Give the formal definition of decryption function D, proving its correctness: D_{(\rho,k)}(E_{(\rho,k)}(x)) = x;SOLUTION:Decryption is obtaining by reversing all the operations: D_{(\rho,k)}(y) = \rho^{-1}(y + k\!\!\!\mod 26) - k\!\!\!\mod 26 , where \rho^{-1} is the inverse of \rho substitution. Correctness is proved as follows (every operation done modulo 26):
    \begin{array}{rcl}D_{(\rho,k)}(E_{(\rho,k)}(x)) & = & D_{(\rho,k)}(\rho(x + k) - k)\\ & = & \rho^{-1}(\rho(x + k) - k + k) - k \\ & = & \rho^{-1}(\rho(x + k)) - k \\ & = & x + k - k\\ & = & x\end{array}
  2. Given \rho: 
    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 (\rho,3);

    SOLUTION: Since \rho^{-1} is the inverse of \rho substitution, reading \rho `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):

    \begin{array}{lclclclcl} D_{(\rho,3)}(\textrm{K}) &=& \rho^{-1}(\textrm{K} + 3) - 3\ &=& \rho^{-1}(\textrm{N}) - 3 &=& \textrm{V}- 3 &=& \textrm{S}\\ D_{(\rho,3)}(\textrm{Z}) &=& \rho^{-1}(\textrm{Z} + 3) - 3\ &=& \rho^{-1}(\textrm{C}) - 3 &= &\textrm{D}- 3 &= &\textrm{A}\\ D_{(\rho,3)}(\textrm{H}) &=& \rho^{-1}(\textrm{H} + 3) - 3\ &=& \rho^{-1}(\textrm{K}) - 3 &=& \textrm{L}- 3 &=& \textrm{I}\\ D_{(\rho,3)}(\textrm{M}) &=& \rho^{-1}(\textrm{M} + 3) - 3\ &=& \rho^{-1}(\textrm{P}) - 3& =& \textrm{O}- 3& =& \textrm{L}\end{array}

     

    The resulting plaintext is SAIL.

  3. Encryption/Decryption under (\rho,3) can equivalently be achieved with a simple substitution cipher under key \rho'. Show \rho' 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):E_{(\rho,3)}(x) = \rho(x + k) - k = \rho'(x) - k = \rho''(x)

    where \rho' is obtained by \rho 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 \rho'' 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 \rho'':
    \rho''(\textrm{S})\rho''(\textrm{A})\rho''(\textrm{I})\rho''(\textrm{L}) = \textrm{KZHM}.

  4. Show that if we use key (\rho, k) with the above fixed \rho and with k 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 |{\cal P}| = |{\cal C}| = |{\cal K}| = 26. We can then apply the characterization of perfect ciphers. Since we assume that k is picked at random (p_{\cal K}(k) = \frac{1}{|{\cal K}|}), we know that the cipher is perfect if and only if for any x \in {\cal P} and y \in {\cal C} there exists exactly one key k such that E_{(\rho,k)}(x)=y. Unfortunately this does not happen because some of the mappings in \rho shifts letter of the same quantity. For example \rho(\textrm{O}) = \textrm{P} and \rho(\textrm{Z}) = \textrm{A} which is a +1 shift modulo 26. Now take O and P as plaintext/ciphertext. It is clear that E_{(\rho,0)}(\textrm{O})=\textrm{P} but it is also true that E_{(\rho,11)}(\textrm{O})=\textrm{P} since E_{(\rho,11)}(\textrm{O}) = \rho(\textrm{O} + 11) - 11 = \rho(\textrm{Z}) - 11 = \textrm{A} - 11 = \textrm{P}. Intuitively, when \rho 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).

Exercise 2

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).

Exercise 3

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:

\begin{array}{rclll}{B} & \rightarrow & {A} &:{N_B} \\{A} & \rightarrow & {B}&:{E_{\mathit{MD5(PIN_A)}}(B,N_B,K_s)}\\{B} & \rightarrow & {A}&:{E_{K_s}(\mbox{``Hello Alice!''})}\\& & {}{}&:{\ldots \mbox{secure session} \ldots} \end{array}

 

where N_B is a nonce k_s is a fresh session key generated by Alice and \mathit{MD5(PIN_A)} is the MD5 hash of the a 5-digit \mathit{PIN_A} 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 2^{128}, thus infeasible.

Exercise 4

The RFID token of a coffee machine (as the one here in the department) is recharged with 1€ using the following protocol:

{M} \rightarrow {T} : {E_K(1\mbox{E})}

 

where K 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:

\begin{array}{rclll} T & \rightarrow & M &: N_T \\{M} & \rightarrow& {T} & : {E_K(1\mbox{E}, N_T)} \end{array}

 

Adding T 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

4 thoughts on “Exam 10 January 2012”

  1. On the 3rd exercise I proposed also a known-plaitext attack possible due to the way the third message is composed: we know that the text to be chiphered is always “Hello !”, and if we eavesdrop the relative ciphertext E(Ks, “Hello !”) we can try to exploit that kind of attack to find directly the key Ks.
    This attack is independent from the attack based on brute-forcing the 5-digits PIN.
    Is it a correct idea?
    Thanks in advance.

  2. Something was wrong with the previous message. The ciphertext would be like “Hello entity_name!”, where entity name depends exactly on the name of the entity (Alice for example).

  3. Luca, yes I’ve seen it in your solutions and the idea is correct. It is pretty common to send constant values in messages and this is why it is good to use ciphers that are believed to be secure against known-plaintext scenarios (and also use chained modes to avoid code-books). So in this cases it is good to say: “assumed the cipher is vulnerable to known-plaintext attacks, the protocol can be broken …”

Comments are closed.