Ernest Hammingweight wrote:
>I was curious about how 'strong' other modes are
>(in particular CFB mode) so I searched Google for "IND-CPA CFB" and
>found very little.
>What I did find though was a project at UC Berkeley in which one could
>examine this particular mode and its resistance to chosen plaintext
>attacks. But I find the project description strange. Here's the
>description
>"Give a correct proof of security for CFB mode encryption. Handle the
>case of m-bit CFB mode, for small values of m, if you can. "
>The first thing that bugs me is the word "correct". Surely a proof
>is, by definition, "correct"? Are there a number of erroneous
>"proofs" for CFB mode out there?
That was my fault. Sorry for the confusion. That was from a course
I taught: it was on a list of potential research projects that students
could do for their term project.
The background is that the following paper claimed, at FSE 2001, to
have a proof that m-bit CFB mode is IND-CPA secure for all m:
A. Alkassar, A. Geraldy, B. Pfitzmann, A.-R. Sadeghi,
"Optimized Self-Synchronizing Mode of Operation", FSE 2001.
http://www.sirrix-ag.de/research/res.publikationen/ressource/AGPS_01O...
However, upon reading it carefully, I discovered that their proof is
bogus. That inspired my suggestion to look for a correct proof.
I have since discovered a more recent paper that appears to give a
correct proof of IND-CPA security for n-bit CFB mode (n = block width):
P.A. Fouque, G. Martinet, G. Poupard,
"Practical Symmetric On-line Encryption", FSE 2003.
http://www.di.ens.fr/~fouque/fse03.pdf
Strangely, the authors of the FSE 2003 paper did not seem to be aware
of the prior FSE 2001 work; it was not cited in their paper. Anyway,
the FSE 2003 security proof only applies to n-bit CFB mode, and requires
that the IV be random. That's good, because if the IV is not random,
there are attacks. See here for slides illustrating some of the attacks:
David Wagner, "New attacks on t-bit OFB and CFB modes:
A cautionary note regarding IV selection", CRYPTO 2002 rump session.
http://www.cs.berkeley.edu/~daw/talks/ofb-crypto02.ps
Meanwhile, one of the students in my class independently worked out a
proof of a similar result, which I also believe to be correct. So,
I now have confidence in the security of CFB, when used properly.
As far as I know, the historical comments above have never appeared
in the published literature. Perhaps I ought to get around to writing
this up someday, if I ever get time, but it just hasn't seemed that
important to me.
By the way, I'm not aware of anyone who has analyzed the security of
m-bit CFB for m < n, so this remains an open question as far as I know.
>The second thing that interests me is the phrase "for small values of
>m". Obviously if you've got a block cipher with block size n, then
>you can model the cipher when used in n-bit CFB mode as a PRP.
>However for m<n, the cipher cannot be modelled as a PRP and modelling
>it as a PRF is dubious since it's a very well-behaved PRF. Is the
>requirement "for small values of m" because the block cipher in m-bit
>CFB mode looks more like a PRF for small values of m?
It's still an interesting question even if we model the m-bit
truncated block cipher as a PRF. In fact, this is a pretty reasonable
assumption.
First, there is a standard result, known as the PRP/PRF
switching lemma, that says the following: if E is a (t,q,e)-PRP
with a n-bit block, then it is also a (t,q,e + q^2/2^n)-PRF. Obviously,
truncation of a PRF cannot hurt, so the consequence also applies to
truncated versions of E. Note that if the number q of chosen-plaintext
queries that an attacker can make to E is quite small, then this shows
that the strength of E as a PRF is almost as good as its strength as
a PRP. However, once q gets near 2^{n/2} (the "birthday bound"), this
lemma tells you essentially nothing about the strength of E as a PRF.
If you don't truncate, then this lemma is tight: there are attacks of
roughly matching complexity. However, there has been some more recent
work showing that truncation actually improves security. The following
two papers show that if E is a (t,q,e)-PRP and we truncate it down to
m bits, then the result will be a (t-O(q),q,e')-PRF, where
e' = O(n sqrt(q) 2^{m-n}) if 0 < q <= 2^m
e' = O(n q 2^{m/2 - n}) if 2^m < q <= 2^{n - m/2}
The result above is from the following two papers:
M. Bellare and R. Impagliazzo, "A tool for obtaining tighter
security analyses of pseudorandom function based constructions,
with applications to PRP to PRF conversion", eprint 1999/024.
http://eprint.iacr.org/1999/024/
The problem was previously analyzed in the previous paper
C. Hall, D. Wagner, J. Kelsey, B. Schneier,
"Building PRFs from PRPs", CRYPTO '98.
http://www.cs.berkeley.edu/~daw/papers/prf-crypto98-long.ps
which showed a corresponding result with
e' = 5 q^{2/3} 2^{(m-2n)/3} + q^3 2^{-2k-1}
I'm not aware of any subsequent work on this topic; attention on the
topic of building PRFs out of PRPs has moved on to other constructions
with better properties than simple truncation.
