Some applications require high-speed encryption even at the expense of reduced security. With a xed secure, but slow cryptographic algorithm, there still is an appealing possibility for encryption speedup by encrypting only some portion of data. In this paper we analyze the ciphertext security obtained this way. We show that it is not possible to exclude from encryption even a small constant fraction of data without signicantly compromising security.
Volume of data is nowadays bigger than ever. Multimedia are a typical example. Fast real-time on-demand encryption of multiple multimedia streams requires specialized powerful hardware.
It is sometimes not possible (or economical) to use powerful enough hardware solution. Then we can replace the encryption algorithm with a faster although maybe less secure one. Another possibility is to use selective encryption with the original secure algorithm. In this case we encrypt only some fraction of plaintext. Let p denote the fraction of encrypted plaintext. The parameter p ranges between 0 (no encryption) and 1 (full encryption) and is used to control the balance between the encryption speedup and the security.
For example, selective encryption is used for
online encryption of MPEG video [
We formally analyze security of selective encryption in this paper. As we are interested in a general case, we make no assumptions on the internal data structure or on statistical properties of the plaintext.
We originally hoped that it could be possible to selectively encrypt portion of plaintext while maintaining reasonable security. However, we show that this ? Supported by VEGA grant No. 1/3106/06. does not work. Since we prove a negative result, it is only better if assumptions are more disadvantageous for the attacker than in practical usage: 1. One-time pad is used as the encrypting algorithm.
One-time pad is the rst and only encryption algorithm for which there is a proof of perfect secrecy if the key is truly random, never reused, and kept secret. We choose this cipher to abstract from eventual weaknesses of the actual cipher which can be exploited by attacker. Theoretical results obtained this way can be used in practice as upper bounds for security of any other selected encryption algorithm. 2. Attacker can manage no more than ciphertext-only attack.
The attacker is assumed to have access only to a ciphertext and full description of selective encryption algorithm. This means that the attacker knows the enciphering algorithm and also the method of bit selection for enciphering. 3. Attack is peformed using brute force.
Key space is searched from the most probable key to the least probable key omitting impossible keys to minimize the attacker’s work. We assume that the selection algorithm chooses bits for encrypting independently from plaintext content (besides its length). In general it cannot be expected that a better attack is possible. However in actual situation specic properties 1 of plaintext can lead to a more ecient attack. 4. Attack complexity measure is dened as a fraction of key space that attacker has to search in average to nd the key.
Attacker tries every possible key until he nds one that deciphers to the desired plaintext. We ignore the complexity of verifying whether deciphered plaintext is the original one. For selective encryption with p = 1 (one-time pad), the expected attack complexity is 1=2. For selective encryption with p = 0 expected complexity is 0. We 1 E.g. high redundancy of plaintext poses an even greater risk for selective encryption then for full text encryption. consider every cipher for which attack complexity approaches 0 as plaintext length goes to +1 insecure.
We assume that encrypting p percent of plaintext bits with selective encryption reduces sender’s work to p percent omitting overhead necessary for selecting those bits. In this situation we will be satised with (and accept this as reasonable degradation of security) reduction of attack complexity from 1=2 to p=2, because this means that attacker’s work is in average also reduced to p percent but no more. 2
Selectors
In this paper we will assume that plaintext is a bit
sequence sequence of zeros and ones. Let n > 0 denote
plaintext sequence length. If we want to selectively
encrypt p 2 (0; 1) percent of plaintext, then we have to
choose k = np bits of plaintext for encryption. In [
Because we are interested in the values of p < 1=2 we relax the assumption that exactly k = np bits have to be selected, and we only require that in average k bits have to be selected. This relaxation allows for using a selector which for every bit ips a biased coin one falls with probability p, zero with probability 1 p. Lets call this selector coin ipping selector. We hope that this step allow us to go with p below 1=2 because it introduce more uncertainty to attacker as all plaintext are now possible. For that reason we have to also change our attack complexity measure and we choose one mentioned in previous section. 2 Xor them with truly random noise. 3 For example, let p = 1=2. For a random bit selector there are 2n 1 possible plaintexts for every ciphertext. If the selector do not use randomness and deterministically selects every even bit, there are only 2n=2 possible plaintexts.
The coin ipping selector analysis In the rest of the paper we will show the behavior of the attack complexity for the coin ipping selector for large messages (we will assume that n goes to innity). 3.1
Average fraction of key space equation Firstly we need to determine the probability of the key of length n with exactly k ones on xedly chosen positions if in the selective encryption the coin ipping selector is used. Let denote this probability as PK(n; k; p), where p is probability of encrypting.
PK(n; k; p) = p k 2 1 p n k 2
n k PK(n; k; p) = X i=0 n i k pk+i(1 p)(n k) i 1
2k+i ; because we can get the key with exactly k ones on xedly chosen positions from any selection with exactly k + i ones with k ones on those xedly chosen positions and i ones arbitrarily chosen from remaining n k positions. Also one-time pad has to select for those k positions bit 1 and for remaining i positions bit 0 (thus we get 2 (k+i)). We can simplify the last equation as follows: p k nXk 2
i=0 p k p 2
2 = + (1 n i k p) p i 2 n k = (1
p)(n k) i = p k 2 1 p n k 2 :
tu
Derivative of the function PK(n; k; p) with respect to k is:
PK(n; k; p) ln
p 2 p
: Since for all studied n > 0 and 0 < p < 1 expression ln( 2 p p ) is negative and PK(n; k; p) is positive we know, that PK(n; k; p) is strictly decreasing function with respect to k 2 h0; ni. Thus eective attacker will start searching key space from the most probable 0n key to the least probable 1n key in direction of increasing number of ones in the key. Sort all 2n keys in this order4 in an array with indexes from 1 to 2n. Then denote L(n; k) index of rst key of length n with k 4 Ordering of keys with equal number of ones is irrelevant since all have the same probability. It can be arbitrary but xed. ones and U (n; k) will denote index of the last key of length n with k ones. It can easily be seen that:
L(n; k) = 1 + kX1 n , U (n; k) = Xk i n i 2 k=0
p 2 p k n Xk n + 1 k i i=0
=
Let us denote average fraction of key space which attacker has to search before he nds the key as F (n; p).
Now, when we have I(n; p), equation for F is obvious:
F (n; p) = 2n Although we have assumed that p < 1 we can verI(n; p) = X i Pr(n; p; i): ify, that F (n; 1) = 1=2 as expected. We can not use i=1 F (n; 0) because Pr(n; 0; k) is not a valid probability Since Pr(n; p; i) is constant for all i between L(n; k) distribution over keys of length n. and U (n; k) we can write: Since PK(n; k; p) does not depend on i we can move it in front of inner sum. The inner sum then reduces to: i = [U (n; k)
L(n; k) + 1]
L(n; k) + U (n; k)
2 Thus equation for I(n; p) changes to: k=0 Xn PK(n; k; p) 1 n "1 2 k n + 2 Xk k i=0 n # i It is obvious that x(n; 0) = 2 and x(n; k+1) x(n; k) = nk++11 . So x(n; k) = 1 + Pik=0 n +i1 . After substituting x(n; k) and PK(n; k; p) we can write I(n; p) as: p k 2 1 p n k n 2 k "
k 1 + X
i=0 p n we get: 2 n + 1 # i Based on Figure 1 we will now try to show that for all p < 1 holds limn!1 F (n; p) = 0. This will be unwelcome result. It means that even if we encrypt nearly the entire plaintext up to some small fraction, this small fraction is still sucient to reduce attack complexity to a negligible fraction compared to full text encryption.
Since we want to prove that the limit goes to zero, it is possible to simplify the proof by realizing that F (n; p) 0 and show that some simpler upper bound f0(n; p)+f1(n; p)+f2(n; p) F (n; p) goes to zero too.
We choose fi(n; p) as follows
1 f0(n; p) = 2n+1 ;
1 f1(n; p) = 2n+1
1 f2(n; p) = 2n+1 2 2 2 2 p n X
k=0 p n n
X k= 2 p p p 2 p k n Sn+1;
k k k n Sn+1;
k k where Skn+1 denotes Pik=0 n +i1 and is n2 12 n 58 . To prove the main limit it is sucient to show that for all i 2 f0; 1; 2g limn!1 fi(n; p) equals to zero. For i = 0 it is trivial so we move to i = 1. In the proof we will use following lemma.
lim n!1
Pn=2 '(n)pn n k=0 k = 0:
2n Theorem 3. Let p < 1. Then limn!1 f1(n; p) = 0.
Proof. Firstly we replace f1(n; p) with even simpler upper bound: f1(n; p)
1 2n+1 1 2n+1 1 5 2 n 8 : ak > ak+1: Proof. We rewrite theorem inequality as a fraction. So we get 8p 2 (0; 1) 9m 8n > m 8k n2 21 n 58 : ak+1 < 1 , 2 ak p n k n k p k + 1 < 1 , k + 1 < 2 p
: p Because nk+1k < nk k it is sucient to nd an arbitrary m that 8n > m 8k n2 12 n 58 : n k k < 2 p p , n < k + k 2 p p
2 , n < k
p Now we have showed that for all p 2 (0; 1), if we set
8 m to 1 1 p 3 , then 8n > m 8k
Now we are able to proof the last theorem on the limit of function f2.
Theorem 4. Let p < 1. Then limn!1 f2(n; p) = 0.
Proof. Again we replace f2(n; p) with even simpler upper bound:
1
2n+1
2
By solving this inequality we get that it holds for every
Lemma 1 (for proof see [
In the proof for i = 2 we will utilize another two lemmas.
Now we use lemma 3 and the fact that we are
interested in limit for n ! 1. Thus for large enough n we
Lemma 2 (for proof see [
2n p 2 n e 2 kn2 1 + O n 8 1 = 2 10 125 = ak 100 75 50 25 0 50 45 40 35 15 10 5 0
= = p n n2 In the sequel we get rid of binomial coecient by ap
1 plying lemma 2. We omit the 1 + O(n 8 ) factor from following equations to save space. We want to prove now that the last equation goes to zero as n approaches 1. We will do so by showing that logarithm of the equation goes to 1. We also omit constant factor p2= as it is irrelevant in this context. Since n2 ln(2 p)p is most inuencing summand as n goes to innity and ln(2 p)p < 0 we have proved that the equation goes to 1. If we again omit the 1 +
1 O(n 8 ) factor from the right-hand side of inequality we get for large enough n that f2(n; p) r 2 [(2
n
p)p] 2
2
p
In this paper we have showed that even the coin
ipping selector tremendously decreases the security of
selective encryption for any p < 1. In other words it
means that even if we encrypt nearly the entire
plaintext up to some small fraction, this small fraction is
still enough to reduce attack complexity to negligible
fraction compared to full text encryption. The same
result holds for random bit selector from [