Mike Markowitz writes:
At 12:43 PM 4/30/2003 -0700, Hal Finney wrote:
CFB has two advantages over CBC that might have led to its choice.
Hal: While we're on the subject of CFB can you possibly share with us the
argument
you used to convince NIST the method is good?
In http://cert.uni-stuttgart.de/archive/ietf-openpgp/1999/05/msg00005.html
you wrote:
"The "pseudo IV" we have now is hard to explain. I had to go to some
lengths in
getting our FIPS 140 certification (a standard security certification) to show
that our way was just as good as the regular way."
The problem was that PGP uses a fixed IV of 0 and then prepends some
random data to the plaintext. Basically anything non-standard like this
had to be justified.
The way FIPS 140 certification works, you don't deal directly with NIST
or NSA. Instead there are a few companies which are authorized to do
a sort of pre-screening of your application and who then present it for
certification. In practice you have to hire one of these companies to
work with you and help you get your application into shape. There was
a consultant who was assigned to our case and who reviewed it and worked
with us. He was the one we had to convince about any questionable issues.
So he brought up this issue about the IV, and we basically had to show
that the purpose of the IV was satisfied by our approach.
In CFB or CBC, the point of the IV is to make sure that the first block of
the ciphertext will be different even though the first block of plaintext
is the same. We get the same effect because for us, the first block of
ciphertext comes out to be Enc(0) ^ randomddata. This then acts as a
de facto IV, as it is then encrypted and xored with the first block of
true plaintext. Basically our random data prefix acts as an IV, except it
gets xored with the encryption of zero, which won't hurt its randomness.
Anyway, our consultant was knowledgeable enough that after some extended
discussion about this, drawing some diagrams on the whiteboard and showing
how it worked, he was convinced that it was as good as the regular IV.
BTW, this reminds me of another advantage of CFB over CBC. In CBC,
the IV gets XOR'd with the plaintext and then encrypted. This means that
there is a greater chance that IV and plaintext changes can cancel each
other out.
For example, if you do something simple with the IV like increment it
for each message, only a few bits change each time. Half the time, only
the low order bit of the IV changes. It might happen that the plaintext
changed in a similar small way, say with just the low order bit changing.
Like, if the plaintext changed from "Dear Casper" to "Dear Cathy", that is
a change of just the low order bit in the first block of 8 bytes. If you
sent these two messages consecutively using CBC, with the IV incrementing
between them, and it happened to be even for the first block, then the
first ciphertext blocks would be identical, thereby leaking information.
In CFB the IV gets encrypted and then XOR'd, so in general half the bits
will change each time, and it is exceedingly unlikely that this would
produce any patterns in the ciphertext.
Hal Finney
P.S. Here is a list I made a couple of years ago illustrating some
similarities and differences between CBC and full-width CFB:
- With CFB if you flip a bit in block N of ciphertext, the same bit gets
flipped in block N of the plaintext, but block N+1 of the plaintext
becomes garbage.
- With CBC if you flip a bit in block N of ciphertext, the same bit gets
flipped in block N+1 of the plaintext, but block N of the plaintext
becomes garbage.
- With CFB you can flip a bit in the last block of the ciphertext and
have the same bit get flipped in the last block of plaintext, without
producing any garbage.
- With CBC you can flip a bit in the IV and have the same bit get flipped
in the first block of plaintext, without producing any garbage.
- With CFB you can handle messages that are an uneven multiple of block
size without using padding, by truncating the last block of ciphertext.
- With CBC you can handle messages that are an uneven multiple of block
size without using padding, by doing ciphertext stealing.
- With CFB you can handle messages that are shorter than one block without
using padding, by truncating the one block of ciphertext.
- With CBC you can handle messages that are shorter than one block without
using padding, by involving the IV in the ciphertext stealing algorithm.
This requires altering the IV in the encryption phase.
- With CFB decryption runs the base cipher in its encrypting direction.
- With CBC decryption runs the base cipher in its decrypting direction.
- With CFB encrypting does the following steps in order: encrypt the IV,
XOR plaintext block 1, encrypt the result, XOR plaintext block 2,
encrypt the result, XOR plaintext block 3, .... The ciphertext is
what results after each encrypt step.
- With CBC encrypting does the following steps in order: start with IV,
XOR plaintext block 1, encrypt the result, XOR plaintext block 2,
encrypt the result, XOR plaintext block 3, .... The ciphertext is
what results after each XOR step.
In many ways CFB and CBC are very similar. It follows from the last
two points that except for the first block, a CBC ciphertext stream can
be turned into CFB mode (and vice versa) by XORing the plaintext into
the ciphertext.