[tahoe-dev] 100-year cryptography

[Samuel Neves]

Today's SSDs have roughly 250 MB/s of read/write throughput. By the same
reasoning, you need at most 12 clock cycles to keep up. Clock rates are
unlikely to go up, being replaced by N-core CPUs with more or less
constant frequency.

Since the topic is '100-year cryptography', let's make some wild
predictions. SSD throughput today is already bounded by the SATA
interface [1]. It is not completely insane to expect solid-state memory
to eventually become as fast as RAM is today. CPUs are also becoming
fast, but not in the same way: we can expect to have a multiple TFlop
general purpose processor in the coming few years, with dozens of cores.
So we end up with very fast storage, and very little time to process it.
Suppose that accessing solid-state memory takes around 200 cycles, which
is pretty OK even for current RAM. Hashing a single block of SHA-512
takes roughly 2000 cycles on a Core 2. Any application that requires a
decent latency will be dependent on the implementation of SHA-512. One
solution is, of course, to adopt parallel modes of operation (e.g., tree
hashing) in this case. The CPU time will still be 2000*log2(n) cycles
for n blocks.

This is not to say SHA-512 is a bad idea. If we can assume it will
remain secure 100 years from now, we can replace it with (faster?) SHA-3
anytime we want. Or we can use Zooko's combiner idea, which makes
everything slower, but gives us some more guarantees than simply
choosing a believed-to-be-strong hash function. Ideally, we'd want a
hash function that could be provably reduced to an NP-complete problem
(FSB claimed to do this). This is highly unlikely to happen (or to be
possible even) and such proofs are often dubious.

The fact is, while 100-year security is an idea worth pursuing, no one
(but the most paranoid people) will use an overly slow system, if there
are faster alternatives. Today, LAFS is (relatively) a novelty. In 5-10
years, when it begins to be acceptably fast, will it still be? Or will
everyone already be using solution X, Y or Z?

[1] http://www.anandtech.com/showdoc.aspx?i=3702&p=9

Chris Palmer wrote:
> 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."""
>
>
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at allmydata.org
> http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
>
>