encrypted using a block cipher in CBC mode. The IV for encryption is not sent as part
of the ciphertext but is agreed on in other ways, not detailed here.
The protocol is typically used in a client/server setting. On the server side we will find
e.g. a web server or a mail server. The attack will be performed against the server by an
active adversary, who intercepts client messages, modifies them and sends the modified
message to the server. It is thus a chosen ciphertext attack.
The server, on receipt of a ciphertext, performs the following steps:
1. The message is decrypted, using the CBC decryption algorithm.
2. The padding is checked to be correct and removed.
3. The MAC is checked to be correct and removed.
4. The remaining message MES is handed over to the application.
If either of the checks in steps 2 or 3 fails, an error message is sent (over the secure channel,
i.e. MACed, PADded and encrypted) and the session is aborted. This behaviour is typical
for cryptographic protocols: any failed check is an indication of an attack and the protocol
should be immediately aborted.
In this assignment, for concreteness we make the assumption that the block size is 64 bits
= 8 bytes (as is the case e.g. for 3DES).
We will need to be specific about how padding is done. Let the length in bytes of MES
|| MAC be n. The padding then consists of 8 − (n mod 8) bytes, each with the value
7 − (n mod 8) (as an eight-bit integer). So if n is a multiple of 8, padding consists of eight
bytes, each with value 7 (= 000001112 ).
We now introduce some notation: With capital letter variables (S,C,. . .) we will always
refer to blocks. We will need to describe blocks also as sequences of eight bytes, for which
we will use the notation < b1 , b2 , b3 , b4 , b5 , b6 , b7 , b8 >.
The last block of a full message, i.e. the one that contains the padding, we will call the
pad block. The pad block thus has one of the following eight forms, where the ?:s represent
the last bytes of the unpadded message:
<?, ?, ?, ?, ?, ?, ?, 0 >
<?, ?, ?, ?, ?, ?, 1, 1 >
<?, ?, ?, ?, ?, 2, 2, 2 >
<?, ?, ?, ?, 3, 3, 3, 3 >
<?, ?, ?, 4, 4, 4, 4, 4 >
<?, ?, 5, 5, 5, 5, 5, 5 >
<?, 6, 6, 6, 6, 6, 6, 6 >
< 7, 7, 7, 7, 7, 7, 7, 7 >
(Remark: SSL actually allows longer padding than necessary, in order to hide message
length, but we will ignore that.)
We will later construct random blocks and need to have an idea about the probability
that a random block is actually a valid pad block. So, let’s for a moment just consider
randomly constructed blocks of 64 bits. Note that in the next three questions we look just
at randomly constructed blocks and some probabilities when such blocks are chosen; you
do not need to think about the wider context to answer these questions.
Question 1: What is the probability that such a random block (uniform distribution over
all 64 bit blocks) is a pad block of type 0 (i.e., of the form in the first line above)?