5
$\begingroup$

I was reading this paper which has a lot of references to the terms MEDP and MELP. Even though i think i got the general meaning, I could not verify that it is indeed correct.

For the MEDP, I would say that it is the maximum bias that can be achieved over k rounds of encryption.

For the MELP, respectively, I would say that is the maximum probability of an equation that holds over k rounds of encryption.

And both are used in order to evaluate the resistance of an encryption scheme against differential and linear cryptanalysis, for example by setting the upper bounds on those metrics. Is that right?

Also, I have noticed that those quantities are referred for 2 rounds of encryption in a lot of cases. (is various AES MEDP,MELP papers) Is there a particular reason why they choose only 2 rounds, or it's just matter of computational complexity?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The paper you link to gives precise definitions for the MEDP and MELP. I will attempt to explain the definitions more expansively & clearly.

First, the differential probability (DP) function with respect to a given block cipher takes an input difference $\Delta x$, an output difference $\Delta y$, and a key $k$ as inputs and generates a probability as the output. This probability can be understood to mean: “the number of pairs of plaintexts $(P_a, P_b)$ such that $P_a \oplus P_b = \Delta x$ and $E_k(P_a) \oplus E_k(P_b) = \Delta y$ (where $E_k(\cdot)$ is the encryption function of the given blockcipher under the key $k$) divided by the total number of possible pairs of plaintexts where $P_a \oplus P_b = \Delta x$ (which is just $2^B$ where $B$ is the block-size in bits of the blockcipher).”

The Expected Differential Probability (EDP) is a function that takes an input difference and output difference and finds the simple average DP of that input-output difference pattern (averaged over all possible keys). Expectation in this case reduces to the simple average because as the paper states we are assuming all keys are equiprobable. So in plain English, add up the DP of that difference pattern for every key and then divide the resulting sum by the size of the keyspace (e.g. $2^{128}$ for AES-128).

The MEDP is simply the maximum such EDP over all possible pairs of input difference and output difference, excluding the all-zero input/output difference (which if not excluded would trivially be the maximum, but which is not useful for cryptanalysis). In (hopefully) plainer English, this asks what pattern of input and output differences gives the attacker the best chance (averaged over all keys) of finding a pair of plaintexts that match that pattern, and how much of a chance is that best chance?

The MEDP is used to evaluate how resilient a block cipher is to differential cryptanalysis. If you can prove that a cipher has a very low MEDP then the cipher is provably secure against that type of attack (“very low” meaning something only slightly higher than the MEDP of a random permutation, i.e. $\dfrac{1}{2^B}$).

Switching to the linear probability (LP), with respect to a given block cipher this is a function that takes an input mask $a$ (a string of bits $B$ long), an output mask $b$, and a key $k$ and returns a probability. In terms of how these masks are used, $a \bullet X$ means taking the $B$-bit string $a$ and ANDing it with the $B$-bit string $X$, and then xoring together all $B$ bits of the resulting string to get a checksum bit. As section 5 of the paper describes, the probability generated by the LP function is: $2 \cdot$ “number of plaintext-ciphertext pairs $(P_i, E_k(P_i))$ for which $a \bullet P_i = b \bullet E_k(P_i)$ divided by the total number of possible plaintexts (i.e. $2^B$)” $-1$ all squared. For example, if the expression $a \bullet P_i = b \bullet E_k(P_i)$ is true for exactly half of the possible plaintexts $P_i$ then the LP would be $(2 \cdot \frac{1}{2} -1)^2 = 0^2 = 0$. If the number of plaintexts for which the expression is true deviates from 50% (either higher or lower than 50%) then the LP will be higher than 0, and the more the deviation the closer the LP will get to 1.

The ELP is very similar to the EDP in that for a particular pair of input and output masks the ELP gives the average LP (averaged over all possible equiprobable keys). Like the MEDP, the MELP is simply the maximum ELP over all possible input-output mask pairs (excluding the all zero masks). Similar to the MEDP, the MELP is used to evaluate how resilient a block cipher is to linear cryptanalysis (a provably very low MELP is a proof that the cipher is secure against that type of attack).

For the last part of your question, the reason why the paper focuses so much on finding the exact MEDP and MELP for 2 rounds of AES is that one can prove that the MEDP and MELP for 4 (or more) rounds of AES is upper bounded by the 2-round MEDP (respectively MELP) raised to the power 4. So if they find the 2-round MEDP/MELP they immediately can give an upper bound on the MEDP/MELP of the entire cipher.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Very helpful, thanks. I have some follow up questions on that. Is it enough in provable security to show that a scheme is safe for a single round? (or even two) For example, i was reading somewhere that some linear/differential properties may reveal only after multiple rounds are taken into consideration. Based on that, somebody could say that every combination of every round should be considered before a scheme is provably secure against differential/linear cryptanalysis. Isn't that right? $\endgroup$
    – Anton Paragas
    Mar 2, 2017 at 22:46
  • $\begingroup$ @AntonParagas - Unless something is very wrong with the cipher the MELP and MEDP should be monotonic - i.e. more rounds only makes them go lower, never higher. So if you can prove a sufficiently low MEDP/MELP for $n$ rounds that is also a proof that the MEDP/MELP for $n+k$ rounds is also sufficiently low. You may want to look at this paper: citeseerx.ist.psu.edu/viewdoc/… it shows how for an iterated "Markov cipher" you can prove using Markov chain theory that the MEDP will converge to the theoretical minimum given sufficiently many rounds. $\endgroup$
    – J.D.
    Mar 3, 2017 at 0:47
  • $\begingroup$ So why wouldn't they use just one round? Is it a trade off between computational complexity and accuracy? (1 round is too inaccurate but cheap, 3 or more rounds are too expensive but provide more accurate results, 2 is the middle ground). Is it something like this? $\endgroup$
    – Anton Paragas
    Mar 7, 2017 at 19:27
  • 1
    $\begingroup$ @AntonParagas - no, the proof that extends the 2 round MEDP/MELP into a 4+ round MEDP/MELP relies on the structure of 2 rounds of AES. See e.g. theorems 5 and 6 of this paper: iacr.org/archive/fse2003/28870263/28870263.pdf $\endgroup$
    – J.D.
    Mar 8, 2017 at 0:13
0
$\begingroup$

Your understanding is roughly correct but your terminology is switched, I believe.

Isn't it linear equations that hold with biases (since normally they hold with probability 1/2 and we don't know the sign of the difference with 1/2)?

Differential characteristics are normally mentioned as probabilities, since a differential over $n$ bits holds with probability at least $2^{-n+1}$ since $+$ equals $-$ modulo 2.

And finally, it is hard to theoretically or practically compute these quantities beyond 2 rounds in typical cases, as you suspected.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.