Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Is there any probability/chances of repeated encrypted block in Output Feedback (OFB) mode? Is there any existing documentation/studies about that? If it is existing, can you please provide me a link for that documentation, I want to analyze it carefully, I can't find some documentation about the probability of repeated encrypted block in OFB, maybe it is existing but it is hard to find.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

Well, if the block cipher is modeled as a random $N$ bit permutation (that is, each permutation from the set of $2^N$ bit patterns to itself is equally probable), then the answer is really quite easy (and this answer is exact): the probability that we will repeat a block within $M$ outputs is precisely $(M-1) 2^{-N}$ (for $0 < M \le 2^N+1$).

The reasoning behind this is remarkably simple. First, when we consider the sequence $X, P(X), P(P((X)) = P^2(X), P^3(X), ...$, we see that the first pair of repeated elements must include the starting point $X$. Here's why: if we have the pair $P^i(X) = P^j(X)$ for $i, j \ne 0$, then we have $P^{i-1}(X) = P^{j-1}(X)$ (remember, $P$ is a permutation, that is, if $P(A)=P(B)$, then $A=B$), and so if we have a pair $i,j \ne 0$, that can't be the first pair.

Now, let us compute the conditional probability that, if we haven't had a repeat after $M-1$ outputs, we get a repeat after $M$ outputs. Now, after we have cycled through $M-1$ outputs, there are $2^N - (M-1)$ outputs we haven't generated before and $1$ output that we have that might be generated in the next step (the other outputs we have generated are impossible, by the reasoning in the above paragraph). If we've specified $(M-1)$ outputs of a permutation, the rest of the possible outputs are equiprobable, and hence the probability that we're generate the one output that would generate a repeat is $1 / (1 + 2^N - (M-1)) = 1/( 2^N-M)$

Now, the probability that we'll generate the first repeat at step $M$ is the probability that we'll not generate a repeat after $M-1$ steps, and then repeat at step $M$. This is:

$Prob(M) = (2^N-1)/2^N \cdot (2^N-2)/(2^N-1) \cdot ... \cdot (2^N-M) / (2^N-M+1) \cdot 1 / (2^N-M) = 1/2^N$

That is, the probability that we'll get a repeat after exactly $M$ steps is independent of the value of $M$ (as long as it is in range).

And hence, the probability we'll get a repeat after $M$ steps (or earlier) is just the sum of the probabilities that we'll generate the first repeat after $k$ steps for $1 < k \le M$, and that's $(M-1)/2^N$.

If you insist on a link, you can look at this one; this uses different logic to come up with the same result.

If the block cipher cannot be modeled as a random permutation (or a random even permutation; that answer differs only in the $M=2^N$ case), well, I don't know on any specific study; that would probably depend on the specific block cipher, and how it differs from a random permutation.

share|improve this answer
    
Nice answer, although I did understand the question a bit different ("what is the probability that ciphertext blocks repeat", which is harder, as it depends on the plaintext) - but your interpretation makes more sense. –  Paŭlo Ebermann Jul 2 '12 at 17:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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