[tahoe-dev] 100-year cryptography

[Chris Palmer]

My favorite discussion of this topic:

http://download.microsoft.com/download/0/2/3/0238acaf-d3bf-4a6d-b3d6-0a0be4bbb36e/BitLockerCipher200608.pdf

The cost of AES is marginal when doing I/O:

"""A typical desktop machine today has a 3 GHz P4 CPU and a hard disk that
can read at about 50 MB/s. That means that the CPU has 60 clock cycles for
each byte that the disk reads. Laptops have slower CPUs, often around the 1
GHz mark. Laptop disks are also slower but not by nearly as much. (For
example, the Seagate Momentus 5400.2 laptop drive can read data at almost 50
MB/s.) Our data shows that laptops tend to have fewer CPU clock cycles per
byte read from disk, down to 40 or even 30 cycles per byte.  We cannot
predict what the CPU/disk speed ratio will be for the actual hardware that
BitLocker will run on, but these numbers are the best guidelines we have.

If decryption is slower than the peak data rate of the disk, the CPU becomes
the bottleneck when reading large amounts of data. This is very noticeable,
both because of the reduced performance and because of the reduced
responsiveness of the UI when all CPU time is being used to decrypt data.2
Therefore, decryption, including all overhead, must be faster than the disk
to get an acceptable user experience.

BitLocker is carefully designed to overlap the reading of data from disk
with the decryption of previously read data. This is only possible to a
limited extent, and when the disk finishes reading the data, the CPU still
has to decrypt (some of) the data. Thus the decryption time increases the
latency of the disk request and reduces performance accordingly. This
obviously argues for a fast decryption algorithm.

A software implementation of AES runs in around 20.25 cycles per byte on a
P4 class CPU.  (Synthetic benchmarks can achieve somewhat higher speeds, but
they exclude various overheads encountered in real system implementations.)
Other overhead adds around 5 cycles per byte for a total of 25.30 cycles per
byte.

Based on this data, our performance analysis concluded that a single pass of
AES, for example using AES in CBC mode, would have acceptable performance.
An algorithm twice as slow as AES (45.55 cycles/byte) would be on the edge
of being unacceptable, and a high-risk choice given the many uncertainties
in the analysis. Anything slower than that would be unacceptable."""