Re: [Cryptography] Crypto Standards v.s. Engineering habits - Was: NIST about to weaken SHA3?
I like the ideas, John. The idea, and the protocol you sketched out, are a little reminiscent of ZRTP ¹ and of tcpcrypt ². I think you can go one step further, however, and make it *really* strong, which is to offer the higher or outer layer a way to hook into the crypto from your inner layer. This could be by the inner layer exporting a crypto value which the outer layer enforces an authorization or authenticity requirement on, as is done in ZRTP if the a=zrtp-hash is delivered through an integrity-protected outer layer, or in tcpcrypt if the Session ID is verified by the outer layer. I think this is a case where a separation of concerns between layers with a simple interface between them can have great payoff. The lower/inner layer enforces confidentiality (encryption), integrity, hopefully forward-secrecy, etc., and the outer layer decides on policy: authorization, naming (which is often but not necessarily used for authorization), etc. The interface between them can be a simple cryptographic interface, for example the way it is done in the two examples above. I think the way that SSL combined transport layer security, authorization, and identification was a terrible idea. I (and others) have been saying all along that it was a bad idea, and I hope that the related security disasters during the last two years have started persuading more people to rethink it, too. I guess the designers of SSL were simply following the lead of the original inventors of public key cryptography, who delegated certain critical unsolved problems to an underspecified Trusted Third Party. What a colossal, historic mistake. The foolscap project ³ by Brian Warner demonstrates that it is possible to retrofit a nice abstraction layer onto SSL. The way that it does this is that each server automatically creates a self-signed certificate, the secure hash of that certificate is embedded into the identifier pointing at that server, and the client requires the server's public key match the certificate matching that hash. The fact that this is a useful thing to do, and inconvenient and rare thing to do with SSL, should give security architects food for thought. So I have a few suggestions for you: 1. Go, go, go! The path your thoughts are taking seems fruitful. Just design a really good inner layer of crypto, without worrying (for now) about the vexing and subtle problems of authorization, authentication, naming, Man-In-The-Middle-Attack and so on. For now. 2. Okay, but leave yourself an out, by defining a nice simple cryptographic hook by which someone else who *has* solved those vexing problems could extend the protection that they've gained to users of your protocol. 3. Maybe study ZRTP and tcpcrypt for comparison. Don't try to study foolscap, even though it is a very interesting practical approach, because there doesn't exist documentation of the protocol at the right level for you to learn from. Regards, Zooko https://LeastAuthority.com ← verifiably end-to-end-encrypted storage P.S. Another example that you and I should probably study is cjdns ⁴. Despite its name, it is *not* a DNS-like thing. It is a transport-layer thing. I know less about cjdns so I didn't cite it as a good example above. ¹ https://en.wikipedia.org/wiki/ZRTP ² http://tcpcrypt.org/ ³ http://foolscap.lothar.com/docs/using-foolscap.html ⁴ http://cjdns.info/ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Tahoe-LAFS developers' statement on backdoors
http://tahoe-lafs.org/trac/tahoe-lafs/browser/trunk/docs/backdoors.txt Statement on Backdoors October 5, 2010 The New York Times has recently reported that the current U.S. administration is proposing a bill that would apparently, if passed, require communication systems to facilitate government wiretapping and access to encrypted data: http://www.nytimes.com/2010/09/27/us/27wiretap.html (login required; username/password pairs available at http://www.bugmenot.com/view/nytimes.com). Commentary by the Electronic Frontier Foundation (https://www.eff.org/deeplinks/2010/09/government-seeks ), Peter Suderman / Reason (http://reason.com/blog/2010/09/27/obama-administration-frustrate ), Julian Sanchez / Cato Institute (http://www.cato-at-liberty.org/designing-an-insecure-internet/ ). The core Tahoe developers promise never to change Tahoe-LAFS to facilitate government access to data stored or transmitted by it. Even if it were desirable to facilitate such access—which it is not—we believe it would not be technically feasible to do so without severely compromising Tahoe-LAFS' security against other attackers. There have been many examples in which backdoors intended for use by government have introduced vulnerabilities exploitable by other parties (a notable example being the Greek cellphone eavesdropping scandal in 2004/5). RFCs 1984 and 2804 elaborate on the security case against such backdoors. Note that since Tahoe-LAFS is open-source software, forks by people other than the current core developers are possible. In that event, we would try to persuade any such forks to adopt a similar policy. The following Tahoe-LAFS developers agree with this statement: David-Sarah Hopwood Zooko Wilcox-O'Hearn Brian Warner Kevan Carstensen Frédéric Marti Jack Lloyd François Deppierraz Yu Xue Marc Tooley - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
ANNOUNCING Tahoe, the Least-Authority File System, v1.8.0
ANNOUNCING Tahoe, the Least-Authority File System, v1.8.0 The Tahoe-LAFS team is pleased to announce the immediate availability of version 1.8.0 of Tahoe-LAFS, an extremely reliable distributed storage system. Get it here: http://tahoe-lafs.org/source/tahoe/trunk/docs/quickstart.html Tahoe-LAFS is the first distributed storage system to offer provider-independent security — meaning that not even the operators of your storage servers can read or alter your data without your consent. Here is the one-page explanation of its unique security and fault-tolerance properties: http://tahoe-lafs.org/source/tahoe/trunk/docs/about.html The previous stable release of Tahoe-LAFS was v1.7.1, which was released July 18, 2010 [1]. v1.8.0 offers greatly improved performance and fault-tolerance of downloads and improved Windows support. See the NEWS file [2] for details. WHAT IS IT GOOD FOR? With Tahoe-LAFS, you distribute your filesystem across multiple servers, and even if some of the servers fail or are taken over by an attacker, the entire filesystem continues to work correctly, and continues to preserve your privacy and security. You can easily share specific files and directories with other people. In addition to the core storage system itself, volunteers have built other projects on top of Tahoe-LAFS and have integrated Tahoe-LAFS with existing systems, including Windows, JavaScript, iPhone, Android, Hadoop, Flume, Django, Puppet, bzr, mercurial, perforce, duplicity, TiddlyWiki, and more. See the Related Projects page on the wiki [3]. We believe that strong cryptography, Free and Open Source Software, erasure coding, and principled engineering practices make Tahoe-LAFS safer than RAID, removable drive, tape, on-line backup or cloud storage. This software is developed under test-driven development, and there are no known bugs or security flaws which would compromise confidentiality or data integrity under recommended use. (For all important issues that we are currently aware of please see the known_issues.txt file [4].) COMPATIBILITY This release is compatible with the version 1 series of Tahoe-LAFS. Clients from this release can write files and directories in the format used by clients of all versions back to v1.0 (which was released March 25, 2008). Clients from this release can read files and directories produced by clients of all versions since v1.0. Servers from this release can serve clients of all versions back to v1.0 and clients from this release can use servers of all versions back to v1.0. This is the eleventh release in the version 1 series. This series of Tahoe-LAFS will be actively supported and maintained for the forseeable future, and future versions of Tahoe-LAFS will retain the ability to read and write files compatible with this series. LICENCE You may use this package under the GNU General Public License, version 2 or, at your option, any later version. See the file COPYING.GPL [5] for the terms of the GNU General Public License, version 2. You may use this package under the Transitive Grace Period Public Licence, version 1 or, at your option, any later version. (The Transitive Grace Period Public Licence has requirements similar to the GPL except that it allows you to delay for up to twelve months after you redistribute a derived work before releasing the source code of your derived work.) See the file COPYING.TGPPL.html [6] for the terms of the Transitive Grace Period Public Licence, version 1. (You may choose to use this package under the terms of either licence, at your option.) INSTALLATION Tahoe-LAFS works on Linux, Mac OS X, Windows, Cygwin, Solaris, *BSD, and probably most other systems. Start with docs/quickstart.html [7]. HACKING AND COMMUNITY Please join us on the mailing list [8]. Patches are gratefully accepted -- the RoadMap page [9] shows the next improvements that we plan to make and CREDITS [10] lists the names of people who've contributed to the project. The Dev page [11] contains resources for hackers. SPONSORSHIP Tahoe-LAFS was originally developed by Allmydata, Inc., a provider of commercial backup services. After discontinuing funding of Tahoe-LAFS RD in early 2009, they continued to provide servers, bandwidth, small personal gifts as tokens of appreciation, and bug reports. Google, Inc. sponsored Tahoe-LAFS development as part of the Google Summer of Code 2010. They awarded four sponsorships to students from around the world to hack on Tahoe-LAFS that summer. Thank you to Allmydata and Google for their generous and public-spirited support. HACK TAHOE-LAFS! If you can find a security flaw in Tahoe-LAFS which is serious enough that feel compelled to warn our users and issue a fix, then we will award you with a customized t-shirts with your exploit printed on it and add you to the Hack Tahoe-LAFS Hall Of Fame [12]. ACKNOWLEDGEMENTS This is the fifth release of Tahoe-LAFS to be created solely as a labor of love by volunteers. Thank you very
ANNOUNCING Tahoe, the Least-Authority File System, v1.7.1
ANNOUNCING Tahoe, the Least-Authority File System, v1.7.1 The Tahoe-LAFS team is pleased to announce the immediate availability of version 1.7.1 of Tahoe-LAFS, an extremely reliable distributed storage system. Tahoe-LAFS is the first distributed storage system which offers provider-independent security—meaning that not even the operators of your storage servers can read or alter your data without your consent. Here is the one-page explanation of its unique security and fault-tolerance properties: http://tahoe-lafs.org/source/tahoe/trunk/docs/about.html Tahoe-LAFS v1.7.1 is the successor to v1.7.0, which was released June 18, 2010 [1]. v1.7.1 is a stable minor release which adds several bugfixes and improvements in security, forward-compatibility, packaging, usability, and portability. See the NEWS file [2] for details. WHAT IS IT GOOD FOR? With Tahoe-LAFS, you distribute your filesystem across multiple servers, and even if some of the servers are compromised by by an attacker, the entire filesystem continues to work correctly, and continues to preserve your privacy and security. You can easily share specific files and directories with other people. In addition to the core storage system itself, volunteers have built other projects on top of Tahoe-LAFS and have integrated Tahoe-LAFS with existing systems. These include frontends for Windows, Macintosh, JavaScript, iPhone, and Android, and plugins for Hadoop, bzr, mercurial, duplicity, TiddlyWiki, and more. See the Related Projects page on the wiki [3]. We believe that strong cryptography, Free and Open Source Software, erasure coding, and principled engineering practices make Tahoe-LAFS safer than RAID, removable drive, tape, on-line backup or cloud storage systems. This software is developed under test-driven development, and there are no known bugs or security flaws which would compromise confidentiality or data integrity under recommended use. (For all currently known issues please see the known_issues.txt file [4].) COMPATIBILITY This release is fully compatible with the version 1 series of Tahoe-LAFS. Clients from this release can write files and directories in the format used by clients of all versions back to v1.0 (which was released March 25, 2008). Clients from this release can read files and directories produced by clients of all versions since v1.0. Servers from this release can serve clients of all versions back to v1.0 and clients from this release can use servers of all versions back to v1.0. This is the tenth release in the version 1 series. This series of Tahoe-LAFS will be actively supported and maintained for the forseeable future, and future versions of Tahoe-LAFS will retain the ability to read and write files compatible with this series. LICENCE You may use this package under the GNU General Public License, version 2 or, at your option, any later version. See the file COPYING.GPL [5] for the terms of the GNU General Public License, version 2. You may use this package under the Transitive Grace Period Public Licence, version 1 or, at your option, any later version. (The Transitive Grace Period Public Licence has requirements similar to the GPL except that it allows you to delay for up to twelve months after you redistribute a derived work before releasing the source code of your derived work.) See the file COPYING.TGPPL.html [6] for the terms of the Transitive Grace Period Public Licence, version 1. (You may choose to use this package under the terms of either licence, at your option.) INSTALLATION Tahoe-LAFS works on Linux, Mac OS X, Windows, Cygwin, Solaris, *BSD, and probably most other systems. Start with docs/quickstart.html [7]. HACKING AND COMMUNITY Please join us on the mailing list [8]. Patches are gratefully accepted -- the RoadMap page [9] shows the next improvements that we plan to make and CREDITS [10] lists the names of people who've contributed to the project. The Dev page [11] contains resources for hackers. SPONSORSHIP Tahoe-LAFS was originally developed by Allmydata, Inc., a provider of commercial backup services. After discontinuing funding of Tahoe-LAFS RD in early 2009, they have continued to provide servers, bandwidth, small personal gifts as tokens of appreciation, and bug reports. Thank you to Allmydata, Inc. for their generous and public-spirited support. Google, Inc. is sponsoring Tahoe-LAFS development as part of the Google Summer of Code 2010. Google suggested that we should apply for the Summer of Code program, and when we did they generously awarded four sponsorships to students from around the world to hack on Tahoe-LAFS this summer. Thank you to Google, Inc. for their generous and public-spirited support. HACK TAHOE-LAFS! If you can find a security flaw in Tahoe-LAFS which is serious enough that feel compelled to warn our users and issue a fix, then we will award you with a customized t-shirts with your exploit printed on it and add you to the Hack Tahoe-LAFS Hall Of Fame
Re: 1280-Bit RSA
Dan: You didn't mention the option of switching to elliptic curves. A 256-bit elliptic curve is probably stronger than 2048-bit RSA [1] while also being more efficient in every way except for CPU cost for verifying signatures or encrypting [2]. I like the Brainpool curves which comes with a better demonstration that they were generated with any possible back door than do the NIST curves [3]. Regards, Zooko [1] http://www.keylength.com/ [2] http://bench.cr.yp.to/results-sign.html [3] http://www.ecc-brainpool.org/download/draft-lochter-pkix-brainpool-ecc-00.txt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
What's the state of the art in digital signatures? Re: What's the state of the art in factorization?
By the way, the general idea of One Hundred Year Security as far as digital signatures go would be to combine digital signature algorithms. Take one algorithm which is bog standard, such as ECDSA over NIST secp256r1 and another which has strong security properties and which is very different from ECDSA. Signing is simply generating a signature over the message using each algorithm in parallel. Signatures consist of both of the signatures of the two algorithms. Verifying consists of checking both signatures and rejecting if either one is wrong. Since the digital signature algorithms that we've been discussing such as [1] are related to discrete log/Diffie-Hellman and since an efficient implementation would probably be in elliptic curves, then those are not great candidates to pair with ECDSA in this combiner scheme. Unfortunately I haven't stumbled on a digital signature scheme which has good properties (efficiency, simplicity, ease of implementation) and which is based on substantially different ideas and which isn't currently under patent protection (therefore excluding NTRUSign). Any ideas? [1] http://eprint.iacr.org/2007/019 Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [cryptography] What's the state of the art in factorization?
On Fri, Apr 23, 2010 at 3:57 AM, Paul Crowley p...@ciphergoth.org wrote: My preferred signature scheme is the second, DDH-based one in the linked paper, since it produces shorter signatures - are there any proposals which improve on that? http://eprint.iacr.org/2007/019 Has one. Caveat lector. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
What's the state of the art in digital signatures? Re: What's the state of the art in factorization?
On Thu, Apr 22, 2010 at 12:40 PM, Jonathan Katz jk...@cs.umd.edu wrote: On Thu, 22 Apr 2010, Zooko O'Whielacronx wrote: Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! … The paper you cite reduces security to a hard-on-average problem, whereas all that P \neq NP guarantees is hardness in the worst case. I see. I did misunderstand. So although cracking the Lyubashevsky, Palacio, Segev encryption scheme [1] doesn't mean that you've proven P=NP, because NP is about worst-case rather than average-case, it *does* mean that you've solved the subset sum problem for a random instance. If you can do that for all keys that people use in real life then you can solve the subset sum problem for almost all random instances, which seems like it would still be a breakthrough in complexity theory. If you can do it for only a few keys then this means that the Lyubashevsky, Palacio, Segev scheme is susceptible to weak keys. Is that right? Anyway, although this is not one, there do exist proposals for public key crypto schemes where breaking the scheme implies solving a worst case instance of a supposedly hard problem, right? Here is a recent paper which surveys several of them (all lattice-based) and estimates secure key sizes: [2]. None of the signature schemes mentioned therein appear to have the sort of efficiency that we are used to. For example the ecdonaldp (ECDSA) signature schemes measured on http://bench.cr.yp.to/results-sign.html have key sizes on the order of tens of bytes, where the most efficient digital signature algorithm described in [2] has key sizes on the order of thousands of bytes. (And that one is a one-time signature scheme!) Okay, so I'm still searching for a signature algorithm which has the following properties (or as many of them as I can get): 1. efficient (signing time, verification time, key generation time, key size, signature size) 2. some kind of strong argument that it really is secure (the gold standard would be reduction to a worst-case instance of an NP-complete problem) or, if we can't have (2) then at least we want (3) and (4): 3. rather different from ECDSA, so that a breakthrough is unlikely to invalidate both ECDSA and this other scheme at once and 4. not known to be vulnerable to quantum computers and finally but importantly: 4. easy to understand and to implement Suggestions welcome! Regards, Zooko Wilcox-O'Hearn [1] http://eprint.iacr.org/2009/576 [2] http://eprint.iacr.org/2010/137 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use
Folks: Regarding earlier discussion on these lists about the difficulty of factoring and post-quantum cryptography and so on, you might be interested in this note that I just posted to the tahoe-dev list: 100-year digital signatures http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004439.html Here is an excerpt: As David-Sarah [Hopwood] has pointed out, a Merkle Signature Scheme is at least as secure as *any* other digital signature scheme, even in the long-term—even if attackers have quantum computers and the knowledge of how to solve math problems that we don't know how to solve today. If you had some other digital signature scheme (even, for the sake of argument, a post-quantum digital signature scheme with some sort of beautiful reduction from some classic math problem), then you would probably start wanting to digitally sign messages larger than the few hundreds of bits that the digital signature algorithm natively handles. Therefore, you would end up hashing your messages with a secure hash function to generate message representatives short enough to sign. Therefore, your system will actually depend on both the security of the digital signature scheme *and* the security of a hash function. With a Merkle Signature Scheme you rely on just the security of a hash function, so there is one less thing that can go wrong. That's why a Merkle Signature Scheme is at least as secure as the best digital signature scheme that you can imagine. :-) In that note I go on to talk about more Tahoe-LAFS-specific engineering considerations and expose my ignorance about exactly what properties are required of the underlying secure hash functions. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
ANNOUNCING Tahoe, the Least-Authority File System, v1.7.0
Dear people of the cryptography mailing lists: We just released Tahoe-LAFS v1.7. The major new feature is an SFTP server. This means that (with enough installing software and tinkering with your operating system configuration) you can have a normal-looking mount point backed by a Tahoe-LAFS grid. Google is sponsoring us through Google Summer of Code. The next release after this one will include the resulting improvements. One of those improvements is the One Hundred Year Cryptography project, with student Yu Xue and mentor Jack Lloyd. I'll post to these lists about the progress they make. Regards, Zooko ANNOUNCING Tahoe, the Least-Authority File System, v1.7.0 The Tahoe-LAFS team is pleased to announce the immediate availability of version 1.7.0 of Tahoe-LAFS, an extremely reliable distributed storage system. Tahoe-LAFS is the first distributed storage system which offers provider-independent security—meaning that not even the operator of your storage server can read or alter your data without your consent. Here is the one-page explanation of its unique security and fault-tolerance properties: http://tahoe-lafs.org/source/tahoe/trunk/docs/about.html Tahoe-LAFS v1.7.0 is the successor to v1.6.1, which was released February 27, 2010 [1]. v1.7.0 is a major new release with new features and bugfixes. It adds a fully functional SFTP interface, support for non-ASCII character encodings, and a new upload algorithm which guarantees that each file is spread over multiple servers for fault-tolerance. See the NEWS file [2] for details. WHAT IS IT GOOD FOR? With Tahoe-LAFS, you distribute your filesystem across multiple servers, and even if some of the servers are compromised by by an attacker, the entire filesystem continues to work correctly, and continues to preserve your privacy and security. You can easily share specific files and directories with other people. In addition to the core storage system itself, volunteers have built other projects on top of Tahoe-LAFS and have integrated Tahoe-LAFS with existing systems. These include frontends for Windows, Macintosh, JavaScript, iPhone, and Android, and plugins for Hadoop, bzr, mercurial, duplicity, TiddlyWiki, and more. See the Related Projects page on the wiki [3]. We believe that strong cryptography, Free and Open Source Software, erasure coding, and principled engineering practices make Tahoe-LAFS safer than RAID, removable drive, tape, on-line backup or cloud storage systems. This software is developed under test-driven development, and there are no known bugs or security flaws which would compromise confidentiality or data integrity under recommended use. (For all currently known issues please see the known_issues.txt file [4].) COMPATIBILITY This release is fully compatible with the version 1 series of Tahoe-LAFS. Clients from this release can write files and directories in the format used by clients of all versions back to v1.0 (which was released March 25, 2008). Clients from this release can read files and directories produced by clients of all versions since v1.0. Servers from this release can serve clients of all versions back to v1.0 and clients from this release can use servers of all versions back to v1.0. This is the ninth release in the version 1 series. This series of Tahoe-LAFS will be actively supported and maintained for the forseeable future, and future versions of Tahoe-LAFS will retain the ability to read and write files compatible with Tahoe-LAFS v1. LICENCE You may use this package under the GNU General Public License, version 2 or, at your option, any later version. See the file COPYING.GPL [5] for the terms of the GNU General Public License, version 2. You may use this package under the Transitive Grace Period Public Licence, version 1 or, at your option, any later version. (The Transitive Grace Period Public Licence has requirements similar to the GPL except that it allows you to wait for up to twelve months after you redistribute a derived work before releasing the source code of your derived work.) See the file COPYING.TGPPL.html [6] for the terms of the Transitive Grace Period Public Licence, version 1. (You may choose to use this package under the terms of either licence, at your option.) INSTALLATION Tahoe-LAFS works on Linux, Mac OS X, Windows, Cygwin, Solaris, *BSD, and probably most other systems. Start with docs/quickstart.html [7]. HACKING AND COMMUNITY Please join us on the mailing list [8]. Patches are gratefully accepted -- the RoadMap page [9] shows the next improvements that we plan to make and CREDITS [10] lists the names of people who've contributed to the project. The Dev page [11] contains resources for hackers. SPONSORSHIP Tahoe-LAFS was originally developed by Allmydata, Inc., a provider of commercial backup services. After discontinuing funding of Tahoe-LAFS RD in early 2009, they have continued to provide servers, bandwidth, small personal gifts as tokens of appreciation, and
Re: What's the state of the art in factorization?
On Wed, Apr 21, 2010 at 8:49 PM, Jerry Leichter leich...@lrw.com wrote: There are some concrete complexity results - the kind of stuff Rogoway does, for example - but the ones I've seen tend to be in the block cipher/cryptographic hash function spaces. Does anyone one know of similar kinds of results for systems like RSA? There is some interesting work in public key cryptosystems that reduce to a *random* instance of a specific problem. Here is a very cool one: http://eprint.iacr.org/2009/576 Public-Key Cryptographic Primitives Provably as Secure as Subset Sum Vadim Lyubashevsky and Adriana Palacio and Gil Segev Abstract: We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, as well as an oblivious transfer protocol that is secure against semi-honest adversaries. Unless I misunderstand, if you read someone's plaintext without having the private key then you have proven that P=NP! Nice. :-) Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: What's the state of the art in factorization?
On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves sne...@dei.uc.pt wrote (on the cryptography@metzdowd.com list): [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf I've been looking at that one, with an eye to using it in the One Hundred Year Cryptography project that is being sponsored by Google as part of the Google Summer of Code (see recent discussions on the tahoe-dev archives for April 2010 [1]). Later I discovered this paper [2] which appears to be an improvement on that one in terms of performance (see Table 1 in [2]) while still having a tight reduction to the Computational Diffie-Hellman (CDH) problem. Strangely, this paper [2] doesn't appear to have been published anywhere except as an eprint on eprint.iacr.org. I wonder why not. Is there something wrong with it? I still have some major questions about the funky hash into a curve part of these schemes. I'm hoping that [3] will turn out to be wrong and a nice simple dumb efficient hack will be secure for these particular digital signature schemes. Of course if the newfangled schemes which reduce to a random instance of a classic hard problem work out, that would provide an even stronger assurance of long-term safety than the ones that reduce to CDH. See for example the paper [4] that I mentioned previously on the cryptography@metzdowd.com mailing list. Unless I misunderstand, if you can break that scheme by learning someone's plaintext without knowing their private key, then you've also proven that P=NP! Unfortunately that one in particular doesn't provide digital signatures, only public key encryption, and what I most need for the One Hundred Year Cryptography project is digital signatures. Regards, Zooko [1] http://allmydata.org/pipermail/tahoe-dev/2010-April/date.html [2] http://eprint.iacr.org/2007/019 [3] http://eprint.iacr.org/2009/340 [4] http://eprint.iacr.org/2009/576 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Proof of Work - atmospheric carbon
On Jan 26, 2009, at 13:08 PM, John Levine wrote: If only. People have been saying for at least a decade that all we have to do to solve the spam problem is to charge a small fee for every message sent. I was one of those people, a decade and a half ago, on the cypherpunks mailing list. In fact, as I recall I once discussed with John Gilmore after a Bay Area Cypherpunks Physical Meeting whether he would pay me to implement some sort of solution to spam, but we didn't agree on a strategy. Unfortunately, there's a variety of reasons that's never going to work. Hey, the future is long. (We hope.) One of the larger reasons is that despite a lot of smart people working on micropayments, we have nothing approaching a system that will work for billions of tranactions per day, where 90% of the purported payments are bogus, along with the lack of any interface to the real world financial system that would scale and withstand the predictable attacks. Coincidentally, I just blogged today about how we are much closer to this now than we were then, even though none of the smart people that you were probably thinking of are involved in the new deployments: http://testgrid.allmydata.org:3567/uri/URI:DIR2-RO:j74uhg25nwdpjpacl6rkat2yhm:kav7ijeft5h7r7rxdp5bgtlt3viv32yabqajkrdykozia5544jqa/wiki.html#%5B%5BDecentralized%20Money%5D%5D WoW-gold, for example, appears to have at least millions of transactions a day. Does anyone have more detail about the scale and scope of these currencies? My white paper could use a little updating, but the basic conclusions remain sound: http://www.taugh.com/epostage.pdf Thanks! I'll read this. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
switching from SHA-1 to Tiger ?
Hal: Thanks for the news about the planned NIST-sponsored hash function competition. I'm glad to hear that it is in the works. Yesterday I profiled my on-line data backup application [1] and discovered that for certain operations one third of the time is spent in SHA-1. For that reason, I've been musing about the possibility of switching away from SHA-1. Not to SHA-256 or SHA-512, but to Tiger. The implementation of Tiger in Crypto++ on Opteron is more than twice as fast as SHA-1 and almost four times as fast as SHA-256 [2]. I hope that the hash function designers will be aware that hash functions are being used in more and more contexts outside of the traditional digital signatures and MACs. These new contexts include filesystems like ZFS [3], decentralized revision control systems like Monotone [4], git [5], mercurial [6] and bazaar-ng [7], and peer-to-peer file-sharing systems such as Direct Connect, Gnutella, and Bitzi [6]. The AES competition resulted in a block cipher that was faster as well as safer than the previous standards. I hope that the next generation of hash functions achieve something similar, because for my use cases speed in a hash function is more important than speed in encryption. By the way, the traditional practice of using a hash function as a component of a MAC should, in my humble opinion, be retired in favor of the Carter-Wegman alternative such as Poly-1305 AES [7]. Regards, Zooko [1] http://allmydata.com/ [2] http://www.eskimo.com/~weidai/amd64-benchmarks.html [3] http://www.opensolaris.org/os/community/zfs/ ZFS offers the option of performing a SHA-256 on every block of data on every access. The default setting is to use a non-cryptographic 256-bit checksum instead. [4] http://www.venge.net/monotone/ [5] http://git.or.cz/ [6] http://en.wikipedia.org/wiki/Tiger_(hash) [7] http://cr.yp.to/mac.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: The Pointlessness of the MD5 attacks
Something that is interesting about this issue is that it involves transitive vulnerability. If there are only two actors there is no issue. If Alice is the user and Bob is the software maintainer and Bob is bad, then Alice will be exploited regardless of the hash function. If Alice is the user and Bob the maintainer and Bob is good then Alice will be safe, regardless. However if there is a third actor, Charles, from whom Bob accepts information that he will use in a limited way (for example an image or sound file, a patch to the source code which contains extensive comments and whitespace), then whether the hash function is collision-resistant becomes an issue. If Alice and Bob use a collision-resistant hash function, they can rest assured that any software package matching the hash is the package that Bob intended for Alice to use. If they use a hash function which is not collision-resistant they can't, even if the function is second pre-image resistant. This is interesting to me because the problem doesn't arise with only Alice and Bob nor with only Bob and Charles. It is a problem specific to the transitive nature of the relationship: Alice is vulnerable to Charles's choice of package because she trusts Bob to choose packages and Bob trusts Charles to provide image files. And because they are using a non-collision-resistant hash function. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: potential new IETF WG on anonymous IPSec
On 2004, Sep 11, , at 17:20, Sandy Harris wrote: Zooko O'Whielcronx wrote: I believe that in the context of e-mail [1, 2, 3, 4] and FreeSWAN this is called opportunistic encryption. That is certainly not what FreeS/WAN meant by opportunistic encryption. http://www.freeswan.org/freeswan_trees/freeswan-1.99/doc/ glossary.html#carpediem That link leads to the following definition: A situation in which any two IPsec-aware machines can secure their communications, without a pre-shared secret and without a common PKI or previous exchange of public keys. This is one of the goals of the Linux FreeS/WAN project, discussed in our introduction section. Setting up for opportunistic encryption is described in our configuration document. This definition is indeed consistent with the concept that we are discussing. If FreeS/WAN's implementation boils down to using DNS as a common PKI that is too bad, but their definition (which explicitly excludes a common PKI) seems to be the same as mine. This concept is too important to go without a name. Currently the best way to tell your interlocutor what concept you are talking about seems to be you know, the way SSH does it, with the first-time-unauthenticated public key exchange. I heartily approve of Peter Gutmann's suggestion to write an RFC for it. Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Simple SSL/TLS - Some Questions
Jill Ramonsky [EMAIL PROTECTED] wrote: I confess ignorance in matters concerning licensing. The basic rules which I want, and which I believe are appropriate are: (i) Anyone can use it, royalty free. Even commercial applications. (ii) Anyone can get the source code, and should be able to compile it to executable from this. (iii) Copyright notices must be distributed along with the toolkit. (iv) Anyone can modify the code (this is important for fixing bugs and adding new features) and redistribute the modified version. (Not sure what happens to the copyright notices if this happens though). #include disclaimers/legalty #include disclaimers/truth #include disclaimers/appropriateness #include disclaimers/miscellaneous I entered your preferences (I think) into the handy dandy interactive license chooser at http://pgl.yoyo.org/lqr/, and it said the following. I may have misunderstood your desiderata though, so don't take my word for it. ;-) Regards, Zooko License | Hackers like accepting code under it | | Combine with proprietary and redistribute | | | Combine with GPL'ed code and redistribute | | | | Can redistribute binaries without source | | | | | Required to include patent license with contrib | | | | | | | | | | | | v v v v v v --- --- --- --- --- --- permissive - Y - Y - GNU LPGPL -2 Y1 - N - GNU GPL -2 N - N - Mozilla PL 1.1 -2 Y -3 N - notes: 1. The LGPL imposes some conditions on redistributing a combination of LGPL'ed and proprietary code, including some requirement on how the LGPL'ed code and the proprietary code are linked at run-time on the user's machine. It appears to me that these clauses are intended to prevent people from violating the spirit of the LGPL by using an obfuscating linker which prevents the user from swapping in alternative versions of the LGPL'ed code. Read Section 6 of the LGPL for details. 2. Some members of the community refuse to accept GPL'ed source code into their projects, although other members of the community strongly prefer GPL'ed source code over other licenses. Contrast with code under permissive licenses such as BSD, X11, MIT, and expat, which nobody refuses to accept. Almost nobody refuses to accept LGPL'ed code, except the Apache Foundation so refuses, saying that they think it would impose LGPL requirement upon the proprietary code (when they are linked via the Java class-loading mechanism). The FSF disagrees with this statement, asserting that such linking falls under section 6 of the LGPL. As far as I know, nobody refuses to accept code which is licensed under the Mozilla PL 1.1-plus-GPL-compatibility-clause (see note #3). 3. MPL 1.1 can be specifically amended to allow combining with GPL, according to the FSF's license list. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Strong-Enough Pseudonymity as Functional Anonymity
I can think of three different goals one could have for identifying the person behind a name. If goal A is possible, I say that the name was a verinym. If goal C is possible, I say that the name was a pseudonym. If none of the goals are possible, the transaction was anonymous. Unfortunately, there's no word for the kind of name where goal B is possible but goal A isn't. Suppose Alice the Argulant visited the tavern that you own and operate in a virtual reality MUD world, and behaved badly and you had her thrown out. Goal A: figure out the real human who operates the Alice persona, and break his or her kneecaps, or at least threaten to do so, while making it clear that you have the ability to make good on your threat. Goal B: make sure that the real human who operates the Alice persona doesn't come back the next day under a different name: Bobo the Burbulant. Goal C: make sure that the real human who operates the Alice persona suffers a loss of reputation capital or escrowed gold pieces or something, thus deterring him or her from behaving badly. I imagine it might be nice to have Goal B achievable in a certain setting where Goal A remains unachievable. Regards, Zooko the Zoogulant - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: anonymous DH MITM
(about the Interlock Protocol) Benja wrote: The basic idea is that Alice sends *half* of her ciphertext, then Bob *half* of his, then Alice sends the other half and Bob sends the other half (each step is started only after the previous one was completed). The point is that having only half of the first ciphertext, Mitch can't decrypt it, and thus not pass on the correct thing to Bob in the first step and to Alice in the second, so both can actually be sure to have the public key of the person that made the other move. That sounds like an accurate summary to me. I think that the important thing is that the first message commits the sender to the contents while withholding knowledge of the contents from the recipient. The second message reveals the contents to the recipient. The fact that this is implemented by sending half of the ciphertext at a time seems peripheral. The same qualities would arise if this were implemented with a different commitment protocol, such as sending a secure hash of the tuple of (my_message, a_random_nonce). Regards, Zooko http://zooko.com/log.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: OOAPI-SSL/TLS (Was: Simple SSL/TLS - Some Questions)
Rich Salz wrote: You know about Wei's Crypto++, right? I use it and like it. I don't have to dig into the guts very often, which is good because I don't like mucking around in C++. You have to understand templates to understand the API. The docs are spartan, but the design is clean so it is okay. It's difficult to compile on new platforms, new versions of compilers, etc., but that's probably true of any C++ library that doesn't deliberately restrict itself to a small subset of C++'s features. If you keep our C++ reasonably simple (no templates) then SWIG (http://www.swig.org) will make the scripting language glue code for you automatically. I use SWIG and like it. They say that the new SWIG handles templates better than good old 1.1. I haven't tried SWIG on Crypto++. I would really *like* for someone else to do so and share the results... Regards, Zooko - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: anonymous DH MITM
Perhaps I spoke too soon? It's not in Eurocrypt or Crypto 84 or 85, which are on my shelf. Where was it published? R. L. Rivest and A. Shamir. How to expose an eavesdropper. Communications of the ACM, 27:393-395, April 1984. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: anonymous DH MITM
Bear wrote: DH is an open protocol; it doesn't rely on an initial shared secret or a Trusted Authority. There is a simple proof that an open protocol between anonymous parties is _always_ vulnerable to MITM. Put simply, in an anonymous protocol, Alice has no way of knowing whether she is communicating with Bob or Mallory, and Bob has no way of knowing whether an incoming communication is from Mallory or from Alice. (that's what anonymous means). If there is no shared secret and no Trent, then nothing prevents Mallory from being the MITM. You can have anonymous protocols that aren't open be immune to MITM And you can have open protocols that aren't anonymous be immune to MITM. But you can't have both. I'd like to see the proof. I think it depends on what you mean by MITM. Take the Chess Grandmaster Problem: can Alice and Bob play a game of chess against one another while preventing Mitch (the Man In The CHannel) from proxying their moves to one another while taking the credit for being a good chess player? To make it concrete, suppose we limit it to the first two moves of a chess game. One player is going to make the first move for White, and the other player is going to make the first move for Black. Now, obviously Mitch could always act as a passive proxy, forwarding exactly the bits he receives, but in that case he can be defeated by e.g. DH. To make it concrete, suppose that the first player includes both his move and his public key (or his public DH parameters) in his message, and the second player encrypts his message with the public key that arrived in the first message. Mitch wins if the first player accepts the second player's move (the first move for Black). The players win if the first player accepts a different move that the second player didn't make. (This is the case where Mitch is no longer doing the Chess Grandmaster Attack, but is instead just playing two games of chess, one game with the first player and another game with the second player.) If the players reject a message and end the protocol, then neither Mitch nor the players win -- it is a tie. (A denial-of-service situation.) Now, you might intuitively believe that this is one of those situations where Mitch can't lose. But there are several protocols published in the literature that can help the players against Mitch, starting with Rivest Shamir's Interlock Protocol from 1984. The funny thing is that all of these published protocols seem to require a constraint on the game of chess. For example, the Interlock Protocol works only with full duplex games where both sides are making a move at the same time. You can't obviously apply it to chess, although you *could* apply it to a full-duplex game like chess variant Bughouse, or, um, children's card game War. Or a Real-Time Strategy computer game where both players are sending moves to one another simultaneously. Now, you might go back to the beginning of this message and say Well, Chess Grandmaster isn't MITM!. In that case, I would like to see a definition of what exactly is this MITM which can't be countered in the no- shared-trust setting. I'm not saying that there isn't such a thing -- indeed I can think of a definition of MITM which satisfies that requirement, but I'm not sure it is the same definition that other people are thinking of. Anyway, it is a funny and underappreciated niche in cryptography, IMO. AFAIK nobody has yet spelled out in the open literature what the actual theoretical limitations are. Regards, Zooko http://zooko.com/log.html - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
