# Probability of Repeated Encrypted Block In Output Feedback (OFB) Mode

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.

-

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.

-
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9703871011734009, "perplexity": 261.07094724347843}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-32/segments/1438042988718.8/warc/CC-MAIN-20150728002308-00198-ip-10-236-191-2.ec2.internal.warc.gz"}