Version 47 (modified by zooko, at 2009-12-09T14:03:46Z) (diff)

add link to google drive failure study

Here are some papers that are potentially of interest.


Symmetric Primitives

Salsa20 Design a fast and secure cipher

Salsa20 Security Arguments why Salsa20 is probably safe against this and that threat

The European Stream Cipher project which evaluated many stream ciphers including Salsa20 a table of semi-automated cryptanalysis results from the inventors of EnRUPT. This technique has not been peer-reviewed by other cryptographers. I (Zooko) can't judge how valid it is. Note that MD4, MD5, SHA-0, SHA-1, SHA-2-256, and GOST are predicted to be insecure, while Tiger is predicted to be secure. AES-128 is predicted to be insecure. Salsa20 is predicted to be secure.

HKDF full paper defines and analyzes the HKDF Key-Derivation Algorithm; A KDF is a linchpin component of our crypto schemes.

Elliptic Curve Cryptography

ECC Brainpool Standard Curves and Curve Generation new elliptic curve parameters which come with a proof that they were generated deterministically and pseudorandomly from the first few bits of pi, as well as proofs that they are immune to certain other potential cryptographic weaknesses.

On the Security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography crypto gurus try to predict whether 160-bit elliptic curve crypto can be brute-force-cracked in the next decade. They conclude: "Right now most certainly not: 2.5 billion PS3s or equivalent devices (such as desktops) for a year is way out of reach. In a decade, very optimistically incorporating 10-fold cryptanalytic advances, still millions of devices would be required, and a successful open community attack on 160-bit ECC even by the year 2020 must be considered very unlikely."

The Certicom Challenges ECC2-X other crypto gurus launch an effort to brute-force-crack 130-bit and 160-bit ECC.

Erasure Coding

a tutorial and some software for erasure coding. This isn't the software that we use because it isn't as fast as Rizzo's implementation, but the tutorial is nice.

A Performance Comparison of Open-Source Erasure Coding Libraries benchmarking some fec implementations including zfec

Direct Attached Storage

Local Filesystems

Model-Based Failure Analysis of Journaling File Systems PDF compares ext3, reiserfs, and JFS under conditions of latent sector errors. (Impatient people: read the Introduction and look at the table on page 9.)

IRON Filesystems PDF, a follow-on by the authors of "Model-Based Failure Analysis of Journaling File Systems" examines how ext3, reiserfs, xfs, and ntfs handle various sorts of errors (impatient people, see table on page 8, "File System Summary" on page 9, and table on page 10).

Using Model Checking to Find Serious File System Errors PDF analyzes ext3, JFS, and reiserfs (impatient: page 10).

eXplode: A lightweight, general approach for finding serious errors in storage systems, a follow-on by the authors of "Using Model Checking to Find Serious File System Errors", compares ext2, ext3, reiserfs, reiser4, jfs, xfs, msdos, vfat, hfs, and hfs+ to see if you sync them and then crash them if your allegedly synced data is actually recoverable (impatient: page 11)

(Summary: basically it looks to me (Zooko) like reiser3 is better-engineered for handling faults than are the other local filesystems. See also the recent revelation that ext3 has been running with write barriers turned off all this time: .)

Disk Failure Rates

Failure Trends in a Large Disk Drive Population by google engineers

P2P / Distributed Systems / Decentralization

Dynamo: Amazon's Highly Available Key-value Store -- sophisticated distributed hash table polished by extensive high-performance practical usage; An excellent paper!

Fixing the Embarrassing Slowness of OpenDHT on PlanetLab (2005) -- practical lessons in DHT performance that theoreticians learned by deployment

A brief history of Consensus, 2PC and Transaction Commit. -- a web page summarizing the evolution of the academic theory of decentralized, reliable systems.

See Also

This page is inspired by flud's Related Papers page, which is well worth reading.

See also Ludovic Courtès's excellent bibliography of cooperative backup.

See also our RelatedProjects page.

The Back Shelf

These are some references which are less interesting or relevant than the ones above.

POST: A Secure, Resilient, Cooperative Messaging System -- use a DHT for messaging; includes a suggestion to ameliorate the confidentiality problems of single-instance store by adding random bits to small text messages

Non-Transitive Connectivity and DHTs -- practical lessons in dealing with not-fully-connected DHTs that theoreticians learned in deployment

Measurement and Analysis of TCP Throughput Collapse in Cluster-based Storage Systems -- Hm... Could this happen to us?

Endomorphisms for faster elliptic curve cryptography on general curves techniques to compute elliptic curve cryptography significantly faster in software.

Some thoughts on Collision Attacks in the Hash Functions MD5, SHA-0 and SHA-1 general musings about design of secure hash functions

EnRUPT a very simple, fast, and flexible primitive which could be used as stream cipher, secure hash function, or MAC (the first two are primitives that we currently need, and the third one -- MAC -- is a primitive that we may want in the future) and which relies for its security on a large number of rounds. The question of how many rounds to use is decided by semi-automated cryptanalysis. (Note: the SHA-3 candidate version of EnRUPT in stream hashing mode was insecure. The current block cipher mode is insecure. There is a minor change (use a few more rounds) which is thought to fix the stream hashing mode. The author is apparently working on a fix for the block cipher mode.)

ChaChaCha20 even better stream cipher; It might be slightly safer than Salsa20 and it is certainly slightly faster on some platforms, but slightly slower on others. However, the author of Salsa20 and !ChaChaCha20, Daniel J. Bernstein, seems to have settled on using Salsa20 (or a tweak of it named XSalsa20), so probably that is the one to use.

Cryptanalysis of the Tiger Hash Function by Mendel and RIjmen