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 R&D 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
Re: Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use
On Wed, Sep 1, 2010 at 2:55 PM, Ben Laurie wrote: >> >> Therefore, you would end up hashing your messages with a >> secure hash function to generate "message representatives" short >> enough to sign. > Way behind the curve here, but this argument seems incorrect. Merkle > signatures rely on the properties of chained hash functions, whereas > RSA, for example, only needs a single iteration of the hash function to > be good. All digital signatures, including RSA and including the hash-based signatures that I am advocating, require a "message representative" which is a small fixed-length thing, and since your message is an arbitrarily large thing we need to use a compressing function, which we do today with Merkle-Damgård chaining and in the future with SHA-3 (which will probably have some mechanism that looks a little bit like a Merkle-Damgård chain if you squint at it just right). A Merkle-Damgård chain is definitely relying on the properties of chained "inner compression functions", and several practical and theoretical weaknesses of this reliance have been identified (length extension, herding, multi-collisions, entropy-loss). The Merkle Trees which are used in hash-based signatures don't seem obviously weaker than normal linear hashes and indeed seem stronger in at least some theoretical ways against collisions (they should not suffer from entropy-loss, for example). In addition, using a full hash function with initialization and finalization on larger inputs instead of a inner-compression-function on smaller inputs is almost certainly safer against preimage attacks. Oh, but there's the rub! The security of the message-representative depends on collision-resistance, but the security of the hash-based signature depends only on pre-image resistance! This is a vast gulf both practically and theoretically. Consider: MD5: collisions: seconds on your laptops; pre-images: perhaps in a hundred years if we make more progress [1] SHA-1: collisions: a year or two of great expense and effort; pre-images: perhaps never unless we have a breakthrough SHA-3-256: collisions: 2¹²⁸; pre-images: 2²⁵⁶ > Or, to put it another way, in order to show that a Merkle signature is > at least as good as any other, then you'll first have to show that an > iterated hash is at least as secure as a non-iterated hash (which seems > like a hard problem, since it isn't). I'm not sure that I agree with you that security of a hash function used once on an arbitrarily large message is likely to be better than security of a hash function used a few times iteratively on its own outputs. But regardless of that, I think the fair comparison here is: ... show that an iterated hash is more likely to have preimage resistance than a non-iterated hash is to have collision-resistance. And I think it is quite clear that for any real hash function such as MD5, SHA-1, Tiger, Ripemd, SHA-2, and the SHA-3 candidates that this does hold! What do you think of that argument? Regards, Zooko [1] http://www.springerlink.com/content/d7pm142n58853467/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
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 R&D 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 H
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
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 R&D in early 2009, they have continued to provide servers, bandwidth, small personal gifts as tokens of apprecia
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
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 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
Re: [cryptography] What's the state of the art in factorization?
On Fri, Apr 23, 2010 at 3:57 AM, Paul Crowley 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?
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: What's the state of the art in factorization?
On Wed, Apr 21, 2010 at 5:29 PM, Samuel Neves 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: What's the state of the art in factorization?
On Wed, Apr 21, 2010 at 8:49 PM, Jerry Leichter 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: 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: entropy depletion
I would love to have an information-theoretic argument for the security of my PRNG, but that's not what we have, and I don't think reducing the entropy_count by one bit per output bit gets us any closer to such an argument. For starters, the entropy_count value before you output the bit is obviously not a measure of the real information-theoretic entropy in the PRNG's state. It is a guess implemented by a simple algorithm (the "entropy estimator"). So if we set the resulting entropy_count after outputting one bit to be equal to the previous entropy_count - 1, we really have no justification for thinking that the resulting entropy_count is any closer to the true information-theoretic entropy than if you had set it equal to the previous entropy_count - 2. On the other hand, I've haven't heard an information-theoretic argument that the output bit contains a whole bit of entropy. There is a nice practical-cryptography argument that an observer gains a whole bit of information from seeing that output bit, but in pure information-theoretic terms an observer gains less than one bit of information from seeing that output. So perhaps when you output a bit from /dev/random you ought to decrement entropy_count by 0.9 instead? In general, I've heard no persuasive information-theoretic argument to justify the practice of decrementing the entropy_count by 1 bit per bit. If that practice does indeed ever protect someone from a cryptanalytic attack on their PRNG, it will not be because the practice is Information Theoretically Correct, but because the entropy_count-bits-added-per-input-bit minus the entropy_count-bits-subtracted-per-output-bit were an engineering fudge factor that was turned up high enough to drown out the cryptanalytic weakness in the PRNG. Of course using such a fudge factor has some other costs, including the cost of introducing new security risks. I estimate that the chance of a successful attack due to timing attacks, induced failure, taking advantage of accidental failure, social engineering, etc. outweighs the chance of a successful attack due to cryptanalysis of the PRNG, which is why I use /dev/urandom exclusively [*, **]. You may weigh those trade-offs differently, but you shouldn't think that by decrementing entropy_count you are achieving information-theoretic security. Regards, Zooko [*] Of course I have to be aware of the regrettable possibility that /dev/urandom has *never* been properly seeded and protect against that in user space. [**] ... and the possibility that the operating system is re-using stored random state which it already used just before an unclean shutdown. - 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]
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: how to defeat MITM using plain DH, Re: anonymous DH & MITM
Ed Gerck wrote: > > It's possible to have at least one open and anonymous protocol > immune to MITM -- which I called multi-channel DH. This is a good idea! I used to advocate it on the cypherpunks list (e.g. [1]). Later I learned that it is called a "Merkle Channel". From _MOV_ [2], page 48: """ One approach to distributing public keys is the so-called Merkle Channel (see Simmons, p.387). Merkle proposed that public keys be distributed over so many independent public channels (newspaper, radio, television, etc.) that it would be improbably for an adversary to compromise all of them. """ Regards, Zooko [1] http://cypherpunks.venona.com/date/1995/10/msg00668.html [2] http://www.cacr.math.uwaterloo.ca/hac/ - 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]
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
> 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]
Full-Duplex-Chess Grandmaster (was: anonymous DH & MITM)
It's clear that my challenge about the Chess Grandmaster Problem has thrown more shadow than light. This is partly because it is an inherently tricky problem, but also because I confused the issue by talking about both traditional Chess Grandmaster (a problem that I am interested in) and Full-Duplex-Chess Grandmaster (a problem that is more or less solved by the Interlock Protocol). So allow me to try again, focussing solely on one case: the Full-Duplex-Chess Grandmaster Attack. Full-Duplex-Chess is a funny chess variant that isn't much played. In Full- Duplex-Chess each player chooses a move to make from the current position, writes down the move on a slip of paper, and holds the slip of paper out face down over the board. This commits the player to that move. Once both players are committed to their moves, then both moves are revealed, and both moves are made on the chess board simultaneously. The rules of chess have to be amended to handle cases such as "we both tried to move into the same square", but that doesn't concern us. Now, here's the Full-Duplex-Chess Grandmaster problem: Alice and Bob are each grandmasters at Full-Duplex-Chess. They each wish to play a game against another player -- they don't care who. At the beginning of the game, each player will generate a new public key pair, and during the game, that public key will be used to encrypt and verify that player's moves. Afterwards, the losing player is going to send a message, encrypted with his or her opponent's public key, that says "Wow, you sure are a good Full-Duplex- Chess player!". (If the game is a draw, each player will send such a message to the other.) Now Mitch's goal is to acquire such a message from one of the players. (Why he wants this isn't clear to me. I've never understood why some people enjoy winning by cheating.) Alice's and Bob's goals are that whoever actually plays the best game of Full- Duplex-Chess receives the congratulatory note. I reiterate that Alice and Bob share no shared state at the beginning of the protocol nor do they have any friends in common whom they can trust. The only things that they have in common are knowledge of the rules of Full-Duplex- Chess, and knowledge of how to perform a cryptographic protocol of your choice. Now it is essential to differentiate between Mitch winning a congratulatory note by proxying the moves from Alice and Bob while replacing their public keys, which is the "(Full-Duplex) Chess Grandmaster Attack", and Mitch winning a congratulatory note by playing a game of Full-Duplex Chess against one of them and winning. I certainly don't claim that the Interlock Protocol can prevent Mitch from playing a game with one person and also playing a game with a second person, but I do claim that it can prevent Mitch from pulling the "Full-Duplex-Chess Grandmaster" trick. Regards, Zooko http://zooko.com/log.html - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: anonymous DH & MITM
Bear wrote: > > If it's an anonymous protocol, then "credit" for being a good chess > player is a misnomer at best; the channel cannot provide credit to > any particular person. I understand the objection, which is why I made the notion concrete by saying that Mitch wins if he gets the first player to accept the second player's move. (I actually think that you can have some notion of "credit" -- for example a persistent pseudonym linked to a longer-term public key, but that isn't necessary to appreciate the current challenge.) > > 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. > > Public key? I thought we were talking about an open protocol between > anonymous entities. If Alice and Bob can identify each other's public > keys, we're not talking about anonymous entities. Right. I proposed that the first player send a public key even though the second player has no way to authenticate it. The effect of this is that Mitch can no longer act as a purely passive proxy (i.e., he can't act like an Eve), because if he does the second move will be encrypted so that he can't read it. Oh -- whoops! This doesn't suffice to deter Mitch from acting as a passive proxy, since we didn't specify that he had to actually see the second move in order to win. Maybe we should add the requirement that for Mitch to win he has to know what the second player's move was. Sorry about the incorrect detail. > > 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. > > Hmmm. I'll go read, and thanks for the pointer. But I'm confident > that if Mitch can be kept out, then either it's not fully anonymous > participants, or it's not a fully open protocol. I understand where you are coming from. Your intuition about this is usually right (i.e., for pretty much all protocols that you have ever actually encountered), and it is an intuition that you share with most thinkers, even those who are brilliant and well-read cryptographers. However the Interlock Protocol provides a counter-example to that intuition! (Not for Chess Grandmaster, but for a full-duplex protocol such as Bughouse Grandmaster). There are other counter-examples in the literature, which I would be happy to enumerate. :-) Please let me know if you find an on-line copy of Rivest & Shamir Interlock Protocol 1984. I had to walk down to a library to read it. Regards, Zooko http://zooko.com/log.html - 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]
