Changes between Version 65 and Version 66 of Bibliography


Ignore:
Timestamp:
2012-08-08T07:09:13Z (12 years ago)
Author:
zooko
Comment:

asterisks make bullet points, bullet points don't

Legend:

Unmodified
Added
Removed
Modified
  • Bibliography

    v65 v66  
    99==== Hash Functions ====
    1010
    11  [http://tuprints.ulb.tu-darmstadt.de/2094/1/thesis.lehmann.pdf On the Security of Hash Function Combiners] Anja Lehman's dissertation on hash function combiners
     11* [http://tuprints.ulb.tu-darmstadt.de/2094/1/thesis.lehmann.pdf On the Security of Hash Function Combiners] Anja Lehman's dissertation on hash function combiners
    1212
    1313==== Ciphers ====
    1414
    15  [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.8477 Chosen-Ciphertext Security of Multiple Encryption] by Dodis, Katz 2005 ; combining two or more ciphers together
    16  [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.9522 Salsa20 Design] a fast and secure cipher
    17  [http://cr.yp.to/snuffle.html#security Salsa20 Security Arguments] why Salsa20 is probably safe against this and that threat
    18  [http://www.ecrypt.eu.org/stream The European Stream Cipher project] which evaluated many stream ciphers including Salsa20
     15* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.8477 Chosen-Ciphertext Security of Multiple Encryption] by Dodis, Katz 2005 ; combining two or more ciphers together
     16* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.9522 Salsa20 Design] a fast and secure cipher
     17* [http://cr.yp.to/snuffle.html#security Salsa20 Security Arguments] why Salsa20 is probably safe against this and that threat
     18* [http://www.ecrypt.eu.org/stream The European Stream Cipher project] which evaluated many stream ciphers including Salsa20
    1919
    2020===== Cipher Combiners a.k.a. Multiple Encryption a.k.a. Cascade Ciphers =====
    2121
    22  [http://www.ciphersbyritter.com/GLOSSARY.HTM#MultipleEncryption John Ritter's web page on the topic]
     22* [http://www.ciphersbyritter.com/GLOSSARY.HTM#MultipleEncryption John Ritter's web page on the topic]
    2323
    2424=== Public Key Cryptography ===
     
    2626==== Hash-Based Digital Signatures ====
    2727
    28  [http://eprint.iacr.org/2011/484 XMSS - A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions] by Buchmann, Dahmen, Hülsing; “the first provably forward secure
     28* [http://eprint.iacr.org/2011/484 XMSS - A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions] by Buchmann, Dahmen, Hülsing; “the first provably forward secure
    2929and practical signature scheme with minimal security requirements: a pseudorandom and a second preimage resistant (hash) function family. Its signature size is reduced to less than 25% compared to
    3030the best provably secure hash based signature scheme.”
     
    3232==== Elliptic Curve Cryptography ====
    3333
    34  [http://tools.ietf.org/html/draft-lochter-pkix-brainpool-ecc-03 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 Π, as well as proofs that they are immune to certain other potential cryptographic weaknesses.
    35  [http://eprint.iacr.org/2009/389 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."
    36  [http://eprint.iacr.org/2009/466 The Certicom Challenges ECC2-X] other crypto gurus launch an effort to brute-force-crack 130-bit and 160-bit ECC.
     34* [http://tools.ietf.org/html/draft-lochter-pkix-brainpool-ecc-03 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 Π, as well as proofs that they are immune to certain other potential cryptographic weaknesses.
     35* [http://eprint.iacr.org/2009/389 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."
     36* [http://eprint.iacr.org/2009/466 The Certicom Challenges ECC2-X] other crypto gurus launch an effort to brute-force-crack 130-bit and 160-bit ECC.
    3737
    3838== Erasure Coding ==
    3939
    40  [http://www.cs.utk.edu/~plank/plank/gflib/index.html 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.
    41  [http://www.cs.utk.edu/~plank/plank/papers/CS-08-625.pdf A Performance Comparison of Open-Source Erasure Coding Libraries] benchmarking some fec implementations including zfec
     40* [http://www.cs.utk.edu/~plank/plank/gflib/index.html 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.
     41* [http://www.cs.utk.edu/~plank/plank/papers/CS-08-625.pdf A Performance Comparison of Open-Source Erasure Coding Libraries] benchmarking some fec implementations including zfec
    4242
    4343== Direct Attached Storage ==
     
    4545=== Local Filesystems ===
    4646
    47  [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.8911 Model-Based Failure Analysis of Journaling File Systems] [http://www.cs.wisc.edu/wind/Publications/sfa-dsn05.pdf 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.)
    48  [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.3785 IRON Filesystems] [https://www.cs.wisc.edu/wind/Publications/iron-sosp05.pdf 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).
    49  [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.8142 Using Model Checking to Find Serious File System Errors ] [https://www.stanford.edu/~engler/osdi04-fisc.pdf PDF] analyzes ext3, JFS, and reiserfs (impatient: page 10).
    50  [https://www.stanford.edu/~engler/explode-osdi06.pdf 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)
     47* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.8911 Model-Based Failure Analysis of Journaling File Systems] [http://www.cs.wisc.edu/wind/Publications/sfa-dsn05.pdf 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.)
     48* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.3785 IRON Filesystems] [https://www.cs.wisc.edu/wind/Publications/iron-sosp05.pdf 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).
     49* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.8142 Using Model Checking to Find Serious File System Errors ] [https://www.stanford.edu/~engler/osdi04-fisc.pdf PDF] analyzes ext3, JFS, and reiserfs (impatient: page 10).
     50* [https://www.stanford.edu/~engler/explode-osdi06.pdf 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)
    5151
    5252(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: http://lwn.net/Articles/283161 .)
     
    5454=== Disk Failure Rates ===
    5555
    56  [http://labs.google.com/papers/disk_failures.pdf Failure Trends in a Large Disk Drive Population] by google engineers
     56* [http://labs.google.com/papers/disk_failures.pdf Failure Trends in a Large Disk Drive Population] by google engineers
    5757
    5858== P2P / Distributed Systems / Decentralization ==
    5959
    60  [http://conferences.sigcomm.org/co-next/2009/papers/Jacobson.pdf Networking Named Content] -- "Content-Centric Networking" is decentralized storage as envisioned by networking experts
    61  [http://s3.amazonaws.com/AllThingsDistributed/sosp/amazon-dynamo-sosp2007.pdf Dynamo: Amazon's Highly Available Key-value Store] -- sophisticated distributed hash table polished by extensive high-performance practical usage; An excellent paper!
    62  [http://citeseer.ist.psu.edu/rhea05fixing.html Fixing the Embarrassing Slowness of OpenDHT on PlanetLab (2005)] -- practical lessons in DHT performance that theoreticians learned by deployment
    63  [http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html  A brief history of Consensus, 2PC and Transaction Commit.] -- a web page summarizing the evolution of the academic theory of decentralized, reliable systems.
     60* [http://conferences.sigcomm.org/co-next/2009/papers/Jacobson.pdf Networking Named Content] -- "Content-Centric Networking" is decentralized storage as envisioned by networking experts
     61* [http://s3.amazonaws.com/AllThingsDistributed/sosp/amazon-dynamo-sosp2007.pdf Dynamo: Amazon's Highly Available Key-value Store] -- sophisticated distributed hash table polished by extensive high-performance practical usage; An excellent paper!
     62* [http://citeseer.ist.psu.edu/rhea05fixing.html Fixing the Embarrassing Slowness of OpenDHT on PlanetLab (2005)] -- practical lessons in DHT performance that theoreticians learned by deployment
     63* [http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html  A brief history of Consensus, 2PC and Transaction Commit.] -- a web page summarizing the evolution of the academic theory of decentralized, reliable systems.
    6464
    6565== See Also ==
    6666
    67  This page is inspired by [http://flud.org flud]'s [http://flud.org/wiki/index.php/RelatedPapers Related Papers] page, which is well worth reading.
    68  See also Ludovic Courtès's excellent [http://www.laas.fr/~lcourtes/ludo-1.html bibliography of cooperative backup]. ''Whoops, broken link!''
    69  See also our [wiki:RelatedProjects RelatedProjects page].
     67* This page is inspired by [http://flud.org flud]'s [http://flud.org/wiki/index.php/RelatedPapers Related Papers] page, which is well worth reading.
     68* See also Ludovic Courtès's excellent [http://www.laas.fr/~lcourtes/ludo-1.html bibliography of cooperative backup]. ''Whoops, broken link!''
     69* See also our [wiki:RelatedProjects RelatedProjects page].
    7070
    7171== The Back Shelf ==
     
    7575=== Public Key Cryptography ===
    7676
    77  [http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf Efficient Signature Schemes with Tight Reductions to the Diffie-Hellman Problems] Scheme 1 in this paper comes with a tight reduction to the Computational Diffie-Hellman problem, which means it is definitely at least as secure as any discrete-log-based scheme and could be more secure. It also has a good pedigree (having been suggested by David Chaum et al. in 1989 and having been proven to tightly reduce to Computational Diffie-Hellman by Katz et al. in 2003). It also has a nice short public key, which could be good for fitting it into our capability security schemes.
     77* [http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf Efficient Signature Schemes with Tight Reductions to the Diffie-Hellman Problems] Scheme 1 in this paper comes with a tight reduction to the Computational Diffie-Hellman problem, which means it is definitely at least as secure as any discrete-log-based scheme and could be more secure. It also has a good pedigree (having been suggested by David Chaum et al. in 1989 and having been proven to tightly reduce to Computational Diffie-Hellman by Katz et al. in 2003). It also has a nice short public key, which could be good for fitting it into our capability security schemes.
    7878
    7979=== Miscellaneous ===
    8080
    81  [http://citeseer.ist.psu.edu/mislove03post.html 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
    82  [http://srhea.net/papers/ntr-worlds05.pdf Non-Transitive Connectivity and DHTs] -- practical lessons in dealing with not-fully-connected DHTs that theoreticians learned in deployment
    83  [http://www.cs.cmu.edu/~dga/papers/incast-fast2008-abstract.html Measurement and Analysis of TCP Throughput Collapse in Cluster-based Storage Systems] -- Hm...  Could this happen to us?
    84  [http://eprint.iacr.org/2008/194 Endomorphisms for faster elliptic curve cryptography on general curves] techniques to compute elliptic curve cryptography significantly faster in software.
    85  [http://eprint.iacr.org/2005/391 Some thoughts on Collision Attacks in the Hash Functions MD5, SHA-0 and SHA-1] general musings about design of secure hash functions
    86  [http://enrupt.com 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.)
    87  [http://defectoscopy.com/results.html defectoscopy.com] 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.
    88  [http://webee.technion.ac.il/~hugo/kdf/kdf.pdf HKDF full paper] defines and analyzes the ''HKDF'' Key-Derivation Algorithm; A KDF is a linchpin component of our crypto schemes.
    89  [http://cr.yp.to/chacha.html 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.
    90  [https://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=81263 Cryptanalysis of the Tiger Hash Function] by Mendel and Rijmen
    91  [http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/DOTV08.pdf Digital Signatures out of Second-Preimage Resistant Hash Functions] by Dahmen, Okeya, Takagi, Vuillame; This scheme is secure as long as the underlying hash function has ''second-preimage resistance'', which real hash functions are a lot more likely to have than to have a stronger property like ''collision-resistance''.
    92  [http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/hashbasedcrypto.pdf Hash-based Digital Signature Schemes] by Buchmann, Dahmen, and Szydlo; A survey of why it might be a good idea.
    93  [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8AC81C407AA3CBF35093032BD01F3085?doi=10.1.1.95.1374&rep=rep1&type=pdf Merkle Signatures with Virtually Unlimited Signature Capacity] by Buchmann, Dahmen, Klintsevich, Okeya, and Vuillaume; includes treating the parameters as an optimization problem and solving it with various weights or constraints to find various good settings for the parameters. Unfortunately their weights and constraints are different from hours: they thought it was fine to let key generation time take tens of hours! We want key generation time to be as few milliseconds as possible. A good rule of thumb for us would probably be try to reduce the time of whichever of the three operations is the slowest: key-generation, signing, and verification.
    94  [https://www.minicrypt.cdc.informatik.tu-darmstadt.de/reports/reports/REDBP08.pdf Fast Hash-Based Signatures on Constrained Devices] by Rohde, Eisenbarth, Dahmen, Buchmann, and Paar; a case study of implementing hash-based digital signatures for a 8-bit microcontroller. Their implementation had some trade-offs that we wouldn't want: it is a "key-evolving" design (the signer has to maintain state in order to avoid a security failure), it can only handle a limited number of signatures, and they spent a lot of time in key generation. Hm, they don't say how long key-generation took in this paper—only that it took so long that they had to run it on a PC instead of on their microcontroller. In [Merkle Signatures with Virtually Unlimited Signature Capacity], the key-generation took tens of hours on a PC!!! On the other hand, they do show a digital signature scheme which is faster at signing and verifying and is also arguably safer than RSA or ECDSA on their 8-bit microcontroller.
    95  [http://www.cryptojedi.org/crypto/index.shtml#aesbs Bitsliced AES implementation] The faster and timing resistant implementation of AES-CTR in bitsliced mode by Peter Schwabe and Emilia Kasper.
    96  [http://crypto.stanford.edu/vpaes/ Vector permutations and AES] The fast and timing-resistant implementations of Mike Hamburg using vector permute instructions (read: pshufb and vperm).
     81* [http://citeseer.ist.psu.edu/mislove03post.html 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
     82* [http://srhea.net/papers/ntr-worlds05.pdf Non-Transitive Connectivity and DHTs] -- practical lessons in dealing with not-fully-connected DHTs that theoreticians learned in deployment
     83* [http://www.cs.cmu.edu/~dga/papers/incast-fast2008-abstract.html Measurement and Analysis of TCP Throughput Collapse in Cluster-based Storage Systems] -- Hm...  Could this happen to us?
     84* [http://eprint.iacr.org/2008/194 Endomorphisms for faster elliptic curve cryptography on general curves] techniques to compute elliptic curve cryptography significantly faster in software.
     85* [http://eprint.iacr.org/2005/391 Some thoughts on Collision Attacks in the Hash Functions MD5, SHA-0 and SHA-1] general musings about design of secure hash functions
     86* [http://enrupt.com 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.)
     87* [http://defectoscopy.com/results.html defectoscopy.com] 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.
     88* [http://webee.technion.ac.il/~hugo/kdf/kdf.pdf HKDF full paper] defines and analyzes the ''HKDF'' Key-Derivation Algorithm; A KDF is a linchpin component of our crypto schemes.
     89* [http://cr.yp.to/chacha.html 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.
     90* [https://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=81263 Cryptanalysis of the Tiger Hash Function] by Mendel and Rijmen
     91* [http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/DOTV08.pdf Digital Signatures out of Second-Preimage Resistant Hash Functions] by Dahmen, Okeya, Takagi, Vuillame; This scheme is secure as long as the underlying hash function has ''second-preimage resistance'', which real hash functions are a lot more likely to have than to have a stronger property like ''collision-resistance''.
     92* [http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/hashbasedcrypto.pdf Hash-based Digital Signature Schemes] by Buchmann, Dahmen, and Szydlo; A survey of why it might be a good idea.
     93* [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8AC81C407AA3CBF35093032BD01F3085?doi=10.1.1.95.1374&rep=rep1&type=pdf Merkle Signatures with Virtually Unlimited Signature Capacity] by Buchmann, Dahmen, Klintsevich, Okeya, and Vuillaume; includes treating the parameters as an optimization problem and solving it with various weights or constraints to find various good settings for the parameters. Unfortunately their weights and constraints are different from hours: they thought it was fine to let key generation time take tens of hours! We want key generation time to be as few milliseconds as possible. A good rule of thumb for us would probably be try to reduce the time of whichever of the three operations is the slowest: key-generation, signing, and verification.
     94* [https://www.minicrypt.cdc.informatik.tu-darmstadt.de/reports/reports/REDBP08.pdf Fast Hash-Based Signatures on Constrained Devices] by Rohde, Eisenbarth, Dahmen, Buchmann, and Paar; a case study of implementing hash-based digital signatures for a 8-bit microcontroller. Their implementation had some trade-offs that we wouldn't want: it is a "key-evolving" design (the signer has to maintain state in order to avoid a security failure), it can only handle a limited number of signatures, and they spent a lot of time in key generation. Hm, they don't say how long key-generation took in this paper—only that it took so long that they had to run it on a PC instead of on their microcontroller. In [Merkle Signatures with Virtually Unlimited Signature Capacity], the key-generation took tens of hours on a PC!!! On the other hand, they do show a digital signature scheme which is faster at signing and verifying and is also arguably safer than RSA or ECDSA on their 8-bit microcontroller.
     95* [http://www.cryptojedi.org/crypto/index.shtml#aesbs Bitsliced AES implementation] The faster and timing resistant implementation of AES-CTR in bitsliced mode by Peter Schwabe and Emilia Kasper.
     96* [http://crypto.stanford.edu/vpaes/ Vector permutations and AES] The fast and timing-resistant implementations of Mike Hamburg using vector permute instructions (read: pshufb and vperm).