Re: updated transport & userauth drafts

[Wei Dai <weidai%eskimo.com@localhost>]

On Sat, Mar 02, 2002 at 01:11:00AM +0100, Markus Friedl wrote:
> then why use CTR and not OFB or CFB?

http://saturn.tcs.hut.fi/~helger/papers/lrw00/html/ gives a good summary
of the advantages of CTR. Here are the ones that apply to SSH:

Software efficiency. Modern processors support some or all of the
following architectural features: aggressive pipelining, multiple
instruction dispatch per clock cycle, a large number of registers, and
SIMD instructions. By eliminating the computational dependency between Ci
and Cj, CTR-mode encryption enables effective utilization of the above
features. For many ciphers, a well-optimized implementation of CTR-mode
encryption on a processor such as an Pentium III, Itanium, Alpha, or a
Motorola AltiVec, may be substantially faster (even more than four times
[8]) than a well-optimized implementation of CBC-mode encryption. This is
greater than the gain obtained from switching from the slowest to the
fastest AES finalist on most platforms [7]. 


Hardware efficiency. Modes such as CBC encryption are limited in their
hardware speed by the maximal rate at which the underlying block cipher
can be computed. This is because one must complete the computation of
ciphertext Ci before one can begin to compute Ci + 1. Thus the maximal
throughput, in hardware, will be about the reciprocal of the latency for
E. In contrast, CTR model is fully parallelizable: one can be computing
blocks C1, C2,... all at the same time, limited only by the amount of
hardware that one throws at the problem. This has been shown to result in
30...100 times speedups for four of the AES finalists [6]. 


Preprocessing. Because the cryptographic work in enciphering a message M
is independent of M, preprocessing can be used, in some environments, to
increase speed. That is, one can compute the pad in ``spare cycles,'' even
before one knows the plaintext M. When M is known, it is XORed with the
already-computed pad. The latter can be done with throughput 10-25 Gbit/s
on a contemporary processor. 


Provable security. The above efficiency characteristics are not obtained
at the expense of security. In fact, the ``standard'' cryptographic
assumption about a block cipher's security--that it is a ``pseudorandom
permutation'' [9,4]--is enough to prove the security of CTR-mode
encryption. See [2], which shows that the concrete security bounds one
gets for CTR-mode encryption, using a block cipher, are no worse than what
one gets for CBC encryption. (Indeed there are approaches to get better
security bounds with CTR-mode encryption than with CBC mode, though these
do not directly use the block cipher E). See [4,3].) The security of CTR
mode is well-analyzed and well-understood.