Cryptography Reference
In-Depth Information
C or C
y
x
Distinguisher
0or1
Figure 4.10. Distinguisher between C and C .
We say that a block cipher is secure if it cannot be distinguished from a truly random
permutation. This is actually a quite strong model of security since if we can break a
block cipher by decrypting a fresh ciphertext, we can a fortiori distinguish it from a
truly random permutation by checking that the decryption is correct with the oracle.
Distinguishers are also the basic tool for differential and linear cryptanalysis.
Linear cryptanalysis actually uses an approximation with an unexpectedly large bias
which can be used to distinguish the cipher from a truly random permutation. Similarly,
differential cryptanalysis uses a differential characteristic with an unexpectedly large
probability.
We can modelize a differential distinguisher as depicted in Fig. 4.11.
Theorem 4.7. Given two random permutations C and C over the same message space
{
C ) be the difference in the
probability that the above distinguisher outputs 1 when the oracle implements the
distributions of C and C . We have
m , where C is uniformly distributed, we let Adv ( C
0
,
1
}
,
max
b )
nE DP C ( a
n
C )
|
Adv ( C
,
|≤
1 ,
,
.
2 m
Therefore the attack is meaningless until the number of chosen plaintext pairs n reaches
the order of magnitude of 1
E (DP C ( a
/
,
b )).
Parameters: a complexity n , a characteristic ( a , b )
Oracle: a permutation c
1: for i from 1 to n do
2: pick uniformly a random X and query for c ( X ) and c ( X + a )
3: if c ( X + a )= c ( X )+ b , output 1 and stop
4: end for
5: output 0
Figure 4.11. Differential distinguisher.
Search WWH ::




Custom Search