Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Thu, Sep 12, 2013 at 1:11 PM, Nico Williams wrote: > - Life will look a bit bleak for a while once we get to quantum machine > cryptopocalypse... Why? We already have NTRU. We also have Lamport Signatures. djb is working on McBits. I'd say there's already many options on the table if you want to build a "quantum-proof" system. -- Tony Arcieri ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Mon, Sep 09, 2013 at 02:48:56PM -0400, Jeffrey I. Schiller wrote: > I don’t believe you can do this without using some form of public key > system. My $.02: - protocols based entirely on symmetric keying are either PSK or a flavor of Needham-Schroeder (e.g., Kerberos) - neither PSK nor Needham-Schroeder scale - PSK fails to scale for obvious reasons - Kerberos could scale if there were TLD realm operators, but there aren't any, and there can't be because they would have too much power, thus no one would trust them (see below) - Kerberos could scale with a web of trust (PGP-like), but managing that web would be difficult, and realms that are widely trusted are... much too powerful (see below) - Kerberos KDCs have even more privileged a position than PKIX CAs: they can impersonate you to others and vice-versa (therefore they can MITM you) and they can recover all your session keys (unless you use PFS) even when they don't MITM you. This is necessarily so for any symmetric key only protocol. - To get past this requires PK crypto. It's unavoidable. - Life will look a bit bleak for a while once we get to quantum machine cryptopocalypse... Nico -- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
zooko writes: >I agree that randomness-reuse is a major issue. Recently about 55 Bitcoin >were stolen by exploiting this, for example: > >http://emboss.github.io/blog/2013/08/21/openssl-prng-is-not-really-fork-safe/ Was that the change that was required by FIPS 140, or a different vuln? Peter. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 11, 2013, at 1:53 AM, zooko wrote: > DJB's Ed25519 takes [using message context as part of random number > generation one step further, and makes the nonce determined *solely* by the > message and the secret key, avoiding the PRNG part altogether: This is not *necessarily* safe. In another thread, we discussed whether choosing the IV for CBC mode by encrypting 0 with the session key was sufficient to meet the randomness requirements. It turns out it does not. I won't repeat the link to Rogoway's paper on the subject, where he shows that using this technique is strictly weaker than using a true random IV. That doesn't mean the way it's done in Ed25519 is unsafe, just that you cannot generically assume that computing a random value from existing private information is safe. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
I agree that randomness-reuse is a major issue. Recently about 55 Bitcoin were stolen by exploiting this, for example: http://emboss.github.io/blog/2013/08/21/openssl-prng-is-not-really-fork-safe/ However, it is quite straightforward to make yourself safe from re-used nonces in (EC)DSA, like this: https://github.com/trezor/python-ecdsa/commit/8efb52fad5025ae87b649ff78faa9f8076768065 Whenever the public-key crypto spec says that you have to come up with a random number, don't do it! Instead of just pulling a random number from your PRNG, mix the message into your PRNG to generate a random number which will therefore be unique to this message. Note that you don't have to get anyone else's cooperation in order to do this -- interoperating implementations can't tell how you chose your "random" number, so they can't complain if you do it this way. Wei Dai's Crypto++ library has done this for ages, for *all* nonces generated in the course of public-key operations. DJB's Ed25519 takes this one step further, and makes the nonce determined *solely* by the message and the secret key, avoiding the PRNG part altogether: http://ed25519.cr.yp.to/papers.html In my opinion, that's the way to go. It applies equally well to (EC)DSA, and still enjoys the above-mentioned interoperability. There is now a standard for this fully-deterministic approach in the works, edited by Thomas Pornin: https://tools.ietf.org/html/rfc6979 . Therefore, Ed25519 or RFC-6979-enhanced (EC)DSA is actually safer than RSA-PSS is with regard to this issue. Regards, Zooko ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Just to throw in my two cents... In the early 1990’s I wanted to roll out an encrypted e-mail solution for the MIT Community (I was the Network Manager and responsible for the mail system). We already had our Kerberos Authentication system (of which I am one of the authors, so I have a special fondness for it). It would do a fine job of helping people exchange session keys for mail and everyone at MIT has a Kerberos ID (and therefore would permit communication between everyone in the community). However, as Network Manager, I was also the person who would see legal requests for access to email and other related data. Whomever ran the Kerberos KDC would be in a position to retrieve any necessary keys to decrypt any encrypted message. Which meant that whomever ran the KDC could be compelled to turn over the necessary keys. In fact my fear was that a clueless law enforcement organization would just take the whole KDC with a search warrant, thus compromising everyone’s security. Today they may well also use a search warrant to take the whole KDC, but not because they are clueless... The desire to offer privacy protection that I, as the administrator, could not defeat is what motivated me to look into public key systems and eventually participate in the Internet’s Privacy Enhanced Mail (PEM) efforts. By using public key algorithms, correspondents are protected from the prying eyes of even the folks who run the system. I don’t believe you can do this without using some form of public key system. -Jeff – ___ Jeffrey I. Schiller Information Services and Technology Massachusetts Institute of Technology 77 Massachusetts Avenue Room E17-110A, 32-392 Cambridge, MA 02139-4307 617.910.0259 - Voice j...@mit.edu http://jis.qyv.name ___ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (GNU/Linux) iD8DBQFSLhgY8CBzV/QUlSsRAoQ8AKDBC/y/qph+HpE11a+5d7p6a6DqyQCgiN/f 3Dcsr8wLR1H+J9gzz31n4ys= =84A0 -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 >> I am certainly not going to advocate Internet-scale KDC. But what >> if the application does not need to scale more than a "network of >> friends?" > > A thousand times yes. There is however a little fly in that particular ointment. Sure, we can develop system that manage pairwise keys, store them safely, share them between several user devices. But what about PFS? Someday, the pairwise key will be compromised, and the NSA will go back to the archives to decrypt everything. We could certainly devise a variant of DH that use the pairwise key to verify the integrity of the session keys, but that brings the public key technology back in the picture. Maybe I am just ignorant, but I don't know how to get PFS using just symmetric key algorithms. Does someone know better? - -- Christian Huitema -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.20 (MingW32) Comment: Using gpg4o v3.1.107.3564 - http://www.gpg4o.de/ Charset: utf-8 iQEcBAEBAgAGBQJSLU6uAAoJELba05IUOHVQ32QH/jVt7j/FpZXc7G07fvfu8/ij 4h53Vn0dfNZmX+XLNX3yILizSz712bGEGWVnq7nPh1IB9JEbYu0lFJxzXbZB6Cv1 Owu+QKnJ1NgctggwKkaCwOELFPNEZ1amzu3f+Haxrq9knv/H2/mykpLPyRR0IU8T 8KFoud1rg7nffIW+flkEGVGgcExibjXOd8H7+/q6Mu6u4/aVJ4O3m2c1sv0kLhl3 gPIeoD8LlRBERUslkqF/jEv6PVgByLD8D94/f7wJ34e9RZQNILPH2dGdck02G/vK IimsR7K/9cB0KhNnIIqCnmxYSvm7KU97h6ejm5lyyZPTtnoDPjfEU+0w7vl5uMs= =ze/o -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 9/7/13 9:06 PM, Christian Huitema wrote: >> Pairwise shared secrets are just about the only thing that >> scales worse than public key distribution by way of PGP key >> fingerprints on business cards. > The equivalent of CAs in an >> all-symmetric world is KDCs. Instead of having the power to >> enable an active attack on you today, KDCs have the power to >> enable a passive attack on you forever. If we want secure crypto >> that can be used by everyone, with minimal trust, public key is >> the only way to do it. >> > > I am certainly not going to advocate Internet-scale KDC. But what > if the application does not need to scale more than a "network of > friends?" A thousand times yes. One doesn't need to communicate with several billion people, and we don't need systems that scale up that high. Most folks just want to interact (chat, share photos, voice/video conference, etc.) with their friends and family and colleagues -- maybe 50 - 500 people. IMHO we only need to scale up that high for secure communication. (I'm talking about individual communication, not enterprise stuff.) What about talking with someone new? Well, we can design separate protocols that enable you to be introduced to someone you haven't communicated with before (we already do that with things like FOAF, LinkedIn, Facebook). Part of that introduction might involve learning the new person's public key from someone you already trust (no need for Internet-scale certificate authorities). You could use that public key for bootstrapping the pairwise shared secrets. Another attractive aspect of a network of friends is that it can be used for mix networking (route messages through your friends) and for things like less-than-completely-public media relays and data proxies for voice, video, file transfer, etc. And such relays might just live on those little home devices that Perry is talking about, separate from the cloud. Peter - -- Peter Saint-Andre https://stpeter.im/ -BEGIN PGP SIGNATURE- Version: GnuPG/MacGPG2 v2.0.19 (Darwin) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJSLQDNAAoJEOoGpJErxa2phHAQAJ76DfrFmz6Sv+HkczOgxJA1 v0kqmLphDhzgT/9eUiF1cCkowF0HE1l84DTuMefrwT2DmOLZJVQANy0Tg/CzWLRu 3JBDkPRQ/cdlfDyy1ZHNb4bsGWyxHIXViQg2sNQZ9KB8yRF4pouYewXOpoJDIabN G40mVlWzuO5cTUWLColwDCaoR20Q+04Ln19BAiJi58d2UT4c55ZyF45hbbQSYL7T bl1JQkvZdtp2Syn4DaGS+WmCUIGsv5KpdXmZv0ljKXoRqsOW7GjaiaQz84MMMQg9 EHZIDnAetTXdfbEki8AsO5PlGRmi944tHL7DtvXJKd76CY5dIZ6kywMU2g+/LrIn 1uWwTSogu4n4yiQrLyYfOnsttkzJWC9BE9YJXXeH0IN6VRvkC710zphCZLVw6LZJ TsNvtskigIQ9jnPO1le1zkHIagXHhns6fVTURFuWd9ZHCOOdbNT7h6Lj+I8OGCkp KFAbRfXzAQDZgVrl42IZ8Sn4DioCLGbscP3maU/C8J3s1+ega3lxfX3DNbJpX+id FtnaXHfushv9xIkoNT/sBJrg79BblU5ZOH/GUBMwV+rFlWA0ofvIrhkaSnRUPFTI gq2C913YWQfyybolHKRNsZ/JpYjarZAJ5eJdW9ALo3xrCxlTr/EcIek7hCVKBK1o d7FvIpkYoexTO08AKfcZ =GRXj -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 8, 2013, at 1:08 PM, Jerry Leichter wrote: > On Sep 8, 2013, at 1:06 PM, Jerry Leichter wrote: >> There was a proposal out there based on something very much like this to >> create tamper-evident signatures Jonathan Katz found the paper I was thinking of - http://eprint.iacr.org/2003/031 -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 8, 2013, at 1:06 PM, Jerry Leichter wrote: > There was a proposal out there based on something very much like this to > create tamper-evident signatures. I forget the details - it was a couple of > years ago - but the idea was that every time you sign something, you modify > your key in some random way, resulting in signatures that are still > verifiably yours, but also contain the new random modification. Beyond that, > I don't recall how it worked - it was quite clever... ah, here it is: > http://eprint.iacr.org/2005/147.pdf Spoke too quickly - that paper is something else entirely. I still can't locate the one I was thinking of. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 8, 2013, at 10:45 AM, Ray Dillinger wrote: >> Pairwise shared secrets are just about the only thing that scales >> worse than public key distribution by way of PGP key fingerprints on >> business cards. >> If we want secure crypto that can be used by everyone, with minimal >> trust, public key is the only way to do it. >> >> One pretty sensible thing to do is to remember keys established in >> previous sessions, and use those combined with the next session. > > You've answered your own conundrum! > > Of course the idea of remembering keys established in previous > sessions and using them combined with keys negotiated in the next > session is a scalable way of establishing and updating pairwise > shared secrets It's even better than you make out. If Eve does manage to get hold of the Alice's current keys, and uses them to communicate with Bob, *after the communication, Bob will have updated his keys - but Alice will not have*. The next time they communicate, they'll know they've been compromised. That is, this is tamper-evident cryptography. There was a proposal out there based on something very much like this to create tamper-evident signatures. I forget the details - it was a couple of years ago - but the idea was that every time you sign something, you modify your key in some random way, resulting in signatures that are still verifiably yours, but also contain the new random modification. Beyond that, I don't recall how it worked - it was quite clever... ah, here it is: http://eprint.iacr.org/2005/147.pdf -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 7, 2013, at 11:06 PM, Christian Huitema wrote: >> Pairwise shared secrets are just about the only thing that scales worse than >> public key distribution by way of PGP key fingerprints on business cards. > >> The equivalent of CAs in an all-symmetric world is KDCs If we want >> secure crypto that can be used by everyone, with minimal trust, public key >> is the only way to do it. > > I am certainly not going to advocate Internet-scale KDC. But what if the > application does not need to scale more than a "network of friends?" Indeed, that was exactly what I had in mind when I suggested we might want to do without private key cryptography on another stream. Not every problem needs to be solved on Internet scale. In designing and building cryptographic systems simplicity of design, limitation to purpose, and humility are usually more important the universality. Most of the email conversations I have are with people I've corresponded with in the past, or somehow related to people I've corresponded with in the past. In the first case, I already have their keys - the only really meaningful notion of "the right key" is key continuity (combined with implied verification if we also have other channels of communication - if someone manages to slip me a bogus key for someone who I talk to every day, I'm going to figure that out very quickly.) In the second case - e.g., an email address from a From field in a message on this list - the best I can possibly hope for initially is that I can be certain I'm corresponding with whoever sent that message to the list. There's no way I can bind that to a particular person in the real world wit hout something more. Universal schemes, when (not if - there's no a single widely fielded system that hasn't been found to have serious bugs over its operation lifetime, and I don't expect to see one in *my* lifetime) they fail, lead to universal attacks. I need some kind of universal scheme for setting up secure connections to buy something from a vendor I never used before, but frankly the NSA doesn't need to break into anything to get that information - the vendor, my bank, my CC company, credit agencies are call collecting and selling it anyway. The other thing to keep in mind - and I've come back to this point repeatedly - is that the world we are now designing for is very different from the world of the mid- to late-1990's when the current schemes were designed. Disk is so large and so cheap that any constraint in the old designs that was based on a statement like "doing this would require the user to keep n^2 keys pairs, which is too much" just doesn't make any sense any more - certainly not for individuals, not even for small organizations: If n is determined by the number of correspondents you have, then squaring it still gives you a small number relative to current disk sizes. Beyond that, everyone today (or in the near future) can be assumed to carry with them computing power that rivals or exceeds the fastest machines available back in the day - and to have an always-on network connection whose speed rivals that of *backbone* links back then. Yes, there are real issues about how much you can trust that computer you carry around with you - but after the recent revelations, is the situation all that different for the servers you talk to, the routers in the network between you, the crypto accelerators many of the services use - hell, every piece of hardware and software. For most people, that will always be the situation: They will not be in a position to check their hardware, much less build their own stuff from the ground up. In this situation, about all you can do is try to present attackers with as many *different* targets as possible, so that they need to split their efforts. It's guerrilla warfare instead of a massed army. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
> > Symetric cryptography does a much easier thing. It combines data and some > mysterious data (key) in a way that you cannot extract data without the > mysterious data from the result. It's like a + b = c. Given c you need b to > find a. The tricks that are involved are mostly about sufficiently mixing > data, to make sure there's enough possible b's to never guess it correctly > and that all those b's have the same chance of being the one b. Preferably > even when you have both A and C, but that's really hard. > > So I'd say Bruce said that in an effort to move to more well understood > cryptography. It is also a way to move people towards simply better > algorithms, as most public key systems are very, very bad. Funny. I would have said exactly the opposite: public key crypto is much better understood because it is based on mathematical theorems and reductions to (admittedly presumed) hard problems, whereas symmetric crypto is really a black art that mixes some simple bit wise operations and hopes for the best (yes, I know this is a bit of caricature...) Jaap-Henk ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On 09/07/2013 07:51 PM, John Kelsey wrote: Pairwise shared secrets are just about the only thing that scales worse than public key distribution by way of PGP key fingerprints on business cards. If we want secure crypto that can be used by everyone, with minimal trust, public key is the only way to do it. One pretty sensible thing to do is to remember keys established in previous sessions, and use those combined with the next session. You've answered your own conundrum! Of course the idea of remembering keys established in previous sessions and using them combined with keys negotiated in the next session is a scalable way of establishing and updating pairwise shared secrets. In fact I'd say it's a very good idea. One can use a distributed public key (infrastructure fraught with peril and mismanagement) for introductions, and thereafter communicate using a pairwise shared secret key (locally managed) which is updated every time you interact, providing increasing security against anyone who hasn't monitored and retained *ALL* previous communications. In order to get at your stash of shared secret keys Eve and Mallory have to mount an attack on your particular individual machine, which sort of defeats the "trawl everything by sabotaging vital infrastructure at crucial points" model that they're trying to accomplish. One thing that weakens the threat model (so far) is that storage is not yet so cheap that Eve can store *EVERYTHING*. If Eve has to break all previous sessions before she can hand your current key to Mallory, first her work factor is drastically increased, second she has to have all those previous sessions stored, and third, if Alice and Bob have ever managed even one secure exchange or one exchange that's off the network she controls (say by local bluetooth link)she fails. Fourth, even if she *can* store everything and the trawl *has* picked up every session, she still has to guess *which* of her squintillion stored encrypted sessions were part of which stream of communications before she knows which ones she has to break. Bear ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sat, Sep 07, 2013 at 08:45:34PM -0400, Perry E. Metzger wrote: > I'm unaware of an ECC equivalent of the Shor algorithm. Could you > enlighten me on that? Shor's algorithm is a Fourier transform, essentially. It can find periods of a function you can implement as a quantum circuit with only polynomially many invocations. In particular, when that function is exponentiation in a group, it can find the orders of group elements. This allows finding discrete logarithms in BQP for any group in which exponentiation is in P. -- Andrea Shepard PGP fingerprint (ECC): 2D7F 0064 F6B6 7321 0844 A96D E928 4A60 4B20 2EF3 PGP fingerprint (RSA): 7895 9F53 C6D1 2AFD 6344 AF6D 35F3 6FFA CBEC CA80 pgpv_iM3WRwuC.pgp Description: PGP signature ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
Public key depends on high level math. That math has some asymetric property that we can use to achieve the public-private key relationships. The problem is that the discovery of smarter math can invalidate the asymetry and make it more symetrical. This has to do with P=NP, which is also less trivial than a first explaination makes it seem. If it becomes even effectively symetrical (P is that) it will stop having the nice useable property. Symetric cryptography does a much easier thing. It combines data and some mysterious data (key) in a way that you cannot extract data without the mysterious data from the result. It's like a + b = c. Given c you need b to find a. The tricks that are involved are mostly about sufficiently mixing data, to make sure there's enough possible b's to never guess it correctly and that all those b's have the same chance of being the one b. Preferably even when you have both A and C, but that's really hard. So I'd say Bruce said that in an effort to move to more well understood cryptography. It is also a way to move people towards simply better algorithms, as most public key systems are very, very bad. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
> Pairwise shared secrets are just about the only thing that scales worse than > public key distribution by way of PGP key fingerprints on business cards. > > The equivalent of CAs in an all-symmetric world is KDCs. Instead of having > the power to enable an active attack on you today, KDCs have the power > to enable a passive attack on you forever. If we want secure crypto that > can be used by everyone, with minimal trust, public key is the only way to do > it. I am certainly not going to advocate Internet-scale KDC. But what if the application does not need to scale more than a "network of friends?" -- Christian Huitema ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 7, 2013, at 3:25 PM, "Christian Huitema" wrote: > Another argument is “minimal dependency.” If you use public key, you depend > on both the public key algorithm, to establish the key, and the symmetric key > algorithm, to protect the session. If you just use symmetric key, you depend > on only one algorithm. > > Of course, that means getting pair-wise shared secrets, and protecting them. > Whether that’s harder or more fragile than maintaining a key ring is a matter > of debate. It is probably more robust than relying on CA. Pairwise shared secrets are just about the only thing that scales worse than public key distribution by way of PGP key fingerprints on business cards. The equivalent of CAs in an all-symmetric world is KDCs. Instead of having the power to enable an active attack on you today, KDCs have the power to enable a passive attack on you forever. If we want secure crypto that can be used by everyone, with minimal trust, public key is the only way to do it. One pretty sensible thing to do is to remember keys established in previous sessions, and use those combined with the next session. For example, if we do Diffie-Hellman today and establish a shared key K, we should both store that key, and we should try to reuse it next time as an additional input into our KDF. That is, next time we use Diffie-Hellman to establish K1, then we get actual-key = KDF(K1, K, other protocol details). That means that if even one session was established securely, the communications are secure (up to the symmetric crypto strength) forevermore. > - -- Christian Huitema --John___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sat, 7 Sep 2013 20:43:39 -0400 I wrote: > To my knowledge, there is no ECC analog of Shor's algorithm. ...and it appears I was completely wrong on that. See, for example: http://arxiv.org/abs/quantph/0301141 Senility gets the best of us. Perry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sat, 7 Sep 2013 13:06:14 -0700 Tony Arcieri wrote: > In order to beat quantum computers, we need to use public key systems > with no (known) quantum attacks, such as lattice-based (NTRU) or > code-based (McEliece/McBits) algorithms. ECC and RSA will no longer > be useful. I'm unaware of an ECC equivalent of the Shor algorithm. Could you enlighten me on that? Perry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sat, 07 Sep 2013 13:01:53 -0700 Ray Dillinger wrote: > I think we can no longer rule out the possibility that some attacker > somewhere (it's easy to point a finger at the NSA but it could be > just as likely pointed at GCHQ or the IDF or Interpol) may have > secretly developed a functional quantum computer with a qbus wide > enough to handle key sizes in actual use. In the same sense that we can no longer rule out the possibility that, given modern synthetic biology techniques, someone has already come up with a way to create pigs with wings. I see the possibility of the quantum computer as slightly smaller, however. > And IIRC, pretty much every asymmetric ciphersuite (including all > public- key crypto) is vulnerable to some transformation of Shor's > algorithm that is in fact practical to implement on such a machine. To my knowledge, there is no ECC analog of Shor's algorithm. Perry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sat, Sep 7, 2013 at 1:01 PM, Ray Dillinger wrote: > And IIRC, pretty much every asymmetric ciphersuite (including all public- > key crypto) is vulnerable to some transformation of Shor's algorithm that > is in fact practical to implement on such a machine. Lattice-based (NTRU) or code-based (McEliece/McBits) public key systems are still considered "post-quantum" algorithms. There are no presently known quantum algorithms that work against these sorts of systems. See http://pqcrypto.org/ -- Tony Arcieri ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 6, 2013, at 11:51 PM, Marcus D. Leech wrote: > The other thing that I find to be a "dirty little secret" in PK systems is > revocation. OCSP makes things, in some ways, "better" than CRLs, but I still > find them to be a kind of "swept under the rug" problem when people are > waxing enthusiastic about PK systems. Well, there are other saddles, as it were. SPKI/SDSI both offer a path forward without needing a trusted CA... signature.asc Description: Message signed with OpenPGP using GPGMail ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On 7/09/13 09:05 AM, Jaap-Henk Hoepman wrote: Public-key cryptography is less well-understood than symmetric-key cryptography. It is also tetchier than symmetric-key crypto, and if you pay attention to us talking about issues with nonces, counters, IVs, chaining modes, and all that, you see that saying that it's tetchier than that is a warning indeed. You have the same issues with nonces, counters, etc. with symmetric crypto so I don't see how that makes it preferable over public key crypto. At 12:57 AM 9/7/2013, ianG wrote: It's a big picture thing. At the end of the day, symmetric crypto is something that good software engineers can master, and relatively well, in a black box sense. Public key crypto not so easily, that requires real learning. I for one am terrified of it. Public-key crypto requires learning math, and math is hard (or at least ECC math is hard, and even prime-number-group math has some interesting tricks in it.) Symmetric-key crypto is easy in a black-box sense, because most algorithms come with rules that say "You need to do this and not do that", yet the original PPTP did half a dozen things wrong with RC4 even though the only rule is "never use the same state twice." But if you want to look inside the black box, most of what's there is a lot of bit-twiddling, maybe in a Feistel network, and while you can follow the bits around and see what changes, there can still be surprises like the discovery of differential cryptanalysis. Public-key crypto lets you use math to do the analysis, but [vast over-simplification] symmetric-key mostly lets you play around and decide if it's messy enough that you can't follow the bits. But there are other traps that affect people with either kind of system. Once PGP got past the Bass-o-matic stage, the biggest security problems were mostly things like variable-precision numbers that were trying so hard to save bits that you could trick the program into interpreting them differently and accepting bogus information. Fortunately we'd never have problems like that today (yes, ASN.1 BER/DER, I'm looking at you), and nobody ever forgets to check array bounds (harder in modern languages than in C or Fortran, but still quite possible), or fails to validate input before using it (SQL injections), etc. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On 09/06/2013 06:13 AM, Jaap-Henk Hoepman wrote: In this oped in the Guardian http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance Bruce Schneier writes: "Prefer symmetric cryptography over public-key cryptography." The only reason I can think of is that for public key crypto you typically use an American (and thus subverted) CA to get the recipients public key. What other reasons could there be for this advice? I think we can no longer rule out the possibility that some attacker somewhere (it's easy to point a finger at the NSA but it could be just as likely pointed at GCHQ or the IDF or Interpol) may have secretly developed a functional quantum computer with a qbus wide enough to handle key sizes in actual use. And IIRC, pretty much every asymmetric ciphersuite (including all public- key crypto) is vulnerable to some transformation of Shor's algorithm that is in fact practical to implement on such a machine. Bear ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Fri, Sep 6, 2013 at 6:13 AM, Jaap-Henk Hoepman wrote: > Bruce Schneier writes: "Prefer symmetric cryptography over public-key > cryptography." The only reason I can think of is that for public key crypto > you typically use an American (and thus subverted) CA to get the recipients > public key. > As soon as someone builds a large quantum computer (probably at least 10 years away, even for the NSA) most of the public key cryptosystems we use today will be easily breakable with e.g. Shor's algorithm. Symmetric algorithms will take a hit as well, with their keyspace cut in half, but that's the equivalent of going from 256-bit keys to 255-bit keys, so symmetric crypto will weather the post-quantum era just fine. In order to beat quantum computers, we need to use public key systems with no (known) quantum attacks, such as lattice-based (NTRU) or code-based (McEliece/McBits) algorithms. ECC and RSA will no longer be useful. -- Tony Arcieri ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Another argument is “minimal dependency.” If you use public key, you depend on both the public key algorithm, to establish the key, and the symmetric key algorithm, to protect the session. If you just use symmetric key, you depend on only one algorithm. Of course, that means getting pair-wise shared secrets, and protecting them. Whether that’s harder or more fragile than maintaining a key ring is a matter of debate. It is probably more robust than relying on CA. - -- Christian Huitema -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.20 (MingW32) Comment: Using gpg4o v3.1.107.3564 - http://www.gpg4o.de/ Charset: utf-8 iQEcBAEBAgAGBQJSK32sAAoJELba05IUOHVQYEQH/iugLUvpdwZoNbtZCXFoB4O8 yP+h6RdcKIraCZww/vrUeXYodfqn9AHWHfQmf0Gx6VlEpXMasJqi8DMR4Fyy4iAk kq5GfuGITBZjeN3gW2Xf20wK0P5nFCgD0sK0sDwuYVZmx6K5Qc4uFt4VNooCoewe rDk48vMRkJnz409M0YXU6Fnxrl7Tm0Tuk513HwAJjNetO1OLH7vznP+iGkZjdbxp CzGuqZuEFwl2gm7TT0I+sciTRoRiVSBmNu+fxNOai9bo2vMUG4eVjSLX+mqRcAbe fVmpSCf9BcA01DLUlRgHityfM9HzdEbQKjdX8QvT4YCI6X7wZ21zTKB2G8ISiwI= =d5yn -END PGP SIGNATURE- Another argument is “minimal dependency.” If you use public key, you depend on both the public key algorithm, to establish the key, and the symmetric key algorithm, to protect the session. If you just use symmetric key, you depend on only one algorithm. Of course, that means getting pair-wise shared secrets, and protecting them. Whether that’s harder or more fragile than maintaining a key ring is a matter of debate. It is probably more robust than relying on CA. -- Christian Huitema PGPexch.htm.sig Description: Binary data ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
it boils down to this: symmetric crypto is much faster than asymmetric crypto. Asymmetric crypto should only be used to exchange symmetric keys and signing. On Sat, Sep 7, 2013 at 11:10 AM, Jaap-Henk Hoepman wrote: > > > I have also, in debate with Jerry, opined that public-key cryptography > is a powerful thing that can't be replaced with symmetric-key cryptography. > That's something that I firmly believe. At its most fundamental, public-key > crypto allows one to encrypt something to someone whom one does not have a > prior security relationship with. That is powerful beyond words. > > I share that belief. Hence my desire to fully understand Bruce's remark. > > Strictly speaking you need some kind of security relationship: you need to > be sure the public key belongs to the intended recipient (and is under his > sole control). So public key crypto allows you to bootstrap from some > authentic piece of information (public key belongs to X) to a confidential > communication channel (with X). > > Jaap-Henk > ___ > The cryptography mailing list > cryptography@metzdowd.com > http://www.metzdowd.com/mailman/listinfo/cryptography > ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sat, Sep 07, 2013 at 10:57:07AM +0300, ianG wrote: > It's a big picture thing. At the end of the day, symmetric crypto > is something that good software engineers can master, and relatively > well, in a black box sense. Public key crypto not so easily, that > requires real learning. I for one am terrified of it. Don’t be. There is no magic there. From what I can tell, there are two different issues with public key. 1. Weaknesses in the math. 2. Fragility in use. The NSA (or other national actors) may well have found a mathematical weakness in any of the public key ciphers (frankly they may have found a weakness in symmetric ciphers as well). Frankly, we just don’t know here. Do we trust RSA more then Diffie-Hellman or any of the Elliptic Curve techniques? Who knows. We can make our keys bigger and hope for the best. As for fragility. Generating random numbers is *hard*, particularly on a day to day basis. When you generate a keypair with GPG/PGP it prompts you to type in random keystrokes and move the mouse etc., all in an attempt to gather as much entropy as possible. This is a pain, but it makes sense for one-lived keys. People would not put up with this if you had to do this for each session key. Fragile public key systems (such as Elgamal and all of the variants of DSA) require randomness at signature time. The consequence for failure is catastrophic. Most systems need session keys, but the consequence for failure in session key generation is the compromise of the message. The consequence for failure in signature generation in a fragile public key system is compromise of the long term key! I wrote about this in NDSS 1991 I cannot find an on-line reference to it though. Then if you are a software developer, you have the harder problem of not being able to control the environment your software will run on, particularly as it applies to the availability of entropy. So my advice. Use RSA, choose a key as long as your paranoia. Like all systems, you will need entropy to generate keys, but you won’t need entropy to use it for encryption or for signatures. - -Jeff ___ Jeffrey I. Schiller Information Services and Technology Massachusetts Institute of Technology 77 Massachusetts Avenue Room E17-110A, 32-392 Cambridge, MA 02139-4307 617.910.0259 - Voice j...@mit.edu http://jis.qyv.name ___ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (GNU/Linux) iD8DBQFSKzKi8CBzV/QUlSsRAhoSAJ98g7NreJwIK+aYODM1zDsVsreMCQCcD2R9 vnvmNc4Uo45+ckUFQafuE4U= =x9bK -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
> I have also, in debate with Jerry, opined that public-key cryptography is a > powerful thing that can't be replaced with symmetric-key cryptography. That's > something that I firmly believe. At its most fundamental, public-key crypto > allows one to encrypt something to someone whom one does not have a prior > security relationship with. That is powerful beyond words. I share that belief. Hence my desire to fully understand Bruce's remark. Strictly speaking you need some kind of security relationship: you need to be sure the public key belongs to the intended recipient (and is under his sole control). So public key crypto allows you to bootstrap from some authentic piece of information (public key belongs to X) to a confidential communication channel (with X). Jaap-Henk ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On 7/09/13 09:05 AM, Jaap-Henk Hoepman wrote: Public-key cryptography is less well-understood than symmetric-key cryptography. It is also tetchier than symmetric-key crypto, and if you pay attention to us talking about issues with nonces, counters, IVs, chaining modes, and all that, you see that saying that it's tetchier than that is a warning indeed. You have the same issues with nonces, counters, etc. with symmetric crypto so I don't see how that makes it preferable over public key crypto. It's a big picture thing. At the end of the day, symmetric crypto is something that good software engineers can master, and relatively well, in a black box sense. Public key crypto not so easily, that requires real learning. I for one am terrified of it. Therefore, what Bruce is saying is that the architecture should recognise this disparity, and try and reduce the part played by public key crypto. Wherever & whenever you can get part of the design over to symmetric crypto, do it. Wherever & whenever you can use the natural business relationships to reduce the need for public key crypto, do that too! iang ps; http://iang.org/ssl/h2_divide_and_conquer.html#h2.4 ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sep 6, 2013, at 11:05 PM, Jaap-Henk Hoepman wrote: >> >> Public-key cryptography is less well-understood than symmetric-key >> cryptography. It is also tetchier than symmetric-key crypto, and if you pay >> attention to us talking about issues with nonces, counters, IVs, chaining >> modes, and all that, you see that saying that it's tetchier than that is a >> warning indeed. > > You have the same issues with nonces, counters, etc. with symmetric crypto so > I don't see how that makes it preferable over public key crypto. Point taken. Bruce made a quip, and I offered an explanation about why that quip might make sense. I have also, in debate with Jerry, opined that public-key cryptography is a powerful thing that can't be replaced with symmetric-key cryptography. That's something that I firmly believe. At its most fundamental, public-key crypto allows one to encrypt something to someone whom one does not have a prior security relationship with. That is powerful beyond words. If you want to be an investigative reporter and want to say, "If you need to talk to me privately, use K" -- you can't do it with symmetric crypto; you have to use public-key. If you are a software developer and want to say say, "If you find a bug in my system and want to tell me, use K" -- you can't do it with symmetric crypto. Heck, if you want to leave someone a voicemail securely you've never talked to, you need public key crypto. That doesn't make Bruce's quip wrong, it just makes it part of the whole story. Jon -BEGIN PGP SIGNATURE- Version: PGP Universal 3.2.0 (Build 1672) Charset: us-ascii wj8DBQFSKsy0sTedWZOD3gYRAm9wAJ9k8cASoXlfYOK/d0jrMtXQ8N/XegCg3ikv miKwWy0D+O8JGF+6hh1Y3oU= =msNM -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
> > Public-key cryptography is less well-understood than symmetric-key > cryptography. It is also tetchier than symmetric-key crypto, and if you pay > attention to us talking about issues with nonces, counters, IVs, chaining > modes, and all that, you see that saying that it's tetchier than that is a > warning indeed. You have the same issues with nonces, counters, etc. with symmetric crypto so I don't see how that makes it preferable over public key crypto. Jaap-Henk ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
The magic of public key crypto is that it gets rid of the key management problem -- if I'm going to communicate with you with symmetric crypto, how do I get the keys to you? The pain of it is that it replaces it with a new set of problems. Those problems include that the amazing power of public-key crypto tempts one to do things that may not be wise. I find public-key cryptography to be full of "dirty little secrets". Some of the notions inherent in public-key *infrastructure* are, on the face of them, preposterous. Consider the notion of a certificate authority. I am to trust some third party (the CA) that I've never met, and have not the slightest reason to trust, is able to make a "believable" assertion about the identity (and corresponding public-key binding), of some *other* party I've never met, and have no real reason to trust. It always struck me as another instance of "there's no problem in CS that can't be solved by adding another layer of abstraction". I think this is an instance of a general problem with digitally-signed documents of all kinds: confusion about exactly what they are--a signature on a document (like a certificate) says nothing about the *essential truth* of the statements contained within the document. When SlushySign issues a certificate for "www.crowbars-r-us.com", there's a subtle distinction between "we believe this to be the appropriate binding between this public-key, and an entitity known as www.crowbars-r-us.com" and "this really is the binding between this pubic-key, and the entity you all know as www.crowbars-r-us.com". I started thinking about the "essential truth" problem back when the whole TPM thing was popular, and proponents were talking as if the digital signature of a computer stating that it was "sane" was somehow the same is said computer actually being "sane". Absent independent verification, there's no way to distinguish a strongly-signed "lie" from a strongly-signed "truth". That isn't necessarily a problem that's confined to PK systems. Any digital-signature scheme has that problem. The other thing that I find to be a "dirty little secret" in PK systems is revocation. OCSP makes things, in some ways, "better" than CRLs, but I still find them to be a kind of "swept under the rug" problem when people are waxing enthusiastic about PK systems. However, PK is the only pony we've managed to bring to this circus, so, we we "make do" with making the "dirty little secrets" as inoffensive as we can. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Why prefer symmetric crypto over public key crypto?
On Sep 6, 2013, at 6:13 AM, Jaap-Henk Hoepman wrote: > In this oped in the Guardian > > http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance > > Bruce Schneier writes: "Prefer symmetric cryptography over public-key > cryptography." The only reason I can think of is that for public key crypto > you typically use an American (and thus subverted) CA to get the recipients > public key. > > What other reasons could there be for this advice? Public-key cryptography is less well-understood than symmetric-key cryptography. It is also tetchier than symmetric-key crypto, and if you pay attention to us talking about issues with nonces, counters, IVs, chaining modes, and all that, you see that saying that it's tetchier than that is a warning indeed. The magic of public key crypto is that it gets rid of the key management problem -- if I'm going to communicate with you with symmetric crypto, how do I get the keys to you? The pain of it is that it replaces it with a new set of problems. Those problems include that the amazing power of public-key crypto tempts one to do things that may not be wise. Jon PGP.sig Description: PGP signature ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
