Re: [Cryptography] NSA and cryptanalysis
On 6/09/13 04:44 AM, Peter Gutmann wrote: John Kelsey crypto@gmail.com writes: If I had to bet, I'd bet on bad rngs as the most likely source of a breakthrough in decrypting lots of encrypted traffic from different sources. If I had to bet, I'd bet on anything but the crypto. Why attack when you can bypass [1]. Peter. [1] From Shamir's Law [2], crypto is bypassed, not penetrated. [2] Well I'm going to call it a law, because it deserves to be. [3] This is a recursive footnote [3]. It looks like it is all of the above. These are the specific interventions I have seen mention of so far: * weakened algorithms/protocols for big players (e.g., GSM, Cisco) * weakening of RNGs * inside access by 'covert agents' to hand over secrets (e.g., big 4) * corruption of the standards process (NIST 2006?) * corruption of certification process (CSC) * crunching of poor passwords * black ops to steal keys * black ops to pervert systems Which makes sense. Why would the biggest player just do one thing ? No, they are going to do everything within their power. They'll try all the tricks. Why not, they've got the money... What is perhaps more interesting is how these tricks interplay with each other. That's something that we'll have trouble seeing and imagining. iang ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Aloha! Jerry Leichter wrote: On Sep 1, 2013, at 2:11 PM, Perry E. Metzger wrote: On Sun, 1 Sep 2013 07:11:06 -0400 Jerry Leichter leich...@lrw.com wrote: Meanwhile, just what evidence do we really have that AES is secure? The fact that the USG likes using it, too. We know they *say in public* that it's acceptable. But do we know what they *actually use*? That's also evidence for eliptic curve techniques btw. Same problem. (Slightly tangential but on topic I hope) Am I the only surprised that the NSA designed block ciphers SIMON and SPECK is vulnerable to differential attacks? http://eprint.iacr.org/2013/543 If I understand the history correctly NSA supported the development of DES as well as SHA-0/SHA-1 and their contributions shows knowledge about differential attacks at least as far back as 1977. - -- Med vänlig hälsning, Yours Joachim Strömbergson - Alltid i harmonisk svängning. -BEGIN PGP SIGNATURE- Version: GnuPG/MacGPG2 v2.0.18 (Darwin) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAlIoTj4ACgkQZoPr8HT30QH91gCg4aRb6tf1d6a5mOnBrF0/GP6c NwIAnRuB99lNpz04/WG0trIQU9ZKnW9A =4r0M -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
John Kelsey crypto@gmail.com writes: If I had to bet, I'd bet on bad rngs as the most likely source of a breakthrough in decrypting lots of encrypted traffic from different sources. If I had to bet, I'd bet on anything but the crypto. Why attack when you can bypass [1]. Peter. [1] From Shamir's Law [2], crypto is bypassed, not penetrated. [2] Well I'm going to call it a law, because it deserves to be. [3] This is a recursive footnote [3]. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Tue, Sep 3, 2013 at 12:49 AM, Jon Callas j...@callas.org wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sep 2, 2013, at 3:06 PM, Jack Lloyd ll...@randombit.net wrote: On Mon, Sep 02, 2013 at 03:09:31PM -0400, Jerry Leichter wrote: a) The very reference you give says that to be equivalent to 128 bits symmetric, you'd need a 3072 bit RSA key - but they require a 2048 bit key. And the same reference says that to be equivalent to 256 bits symmetric, you need a 521 bit ECC key - and yet they recommend 384 bits. So, no, even by that page, they are not recommending equivalent key sizes - and in fact the page says just that. Suite B is specified for 128 and 192 bit security levels, with the 192 bit level using ECC-384, SHA-384, and AES-256. So it seems like if there is a hint to be drawn from the Suite B params, it's about AES-192. The real issue is that the P-521 curve has IP against it, so if you want to use freely usable curves, you're stuck with P-256 and P-384 until some more patents expire. That's more of it than 192 bit security. We can hold our noses and use P-384 and AES-256 for a while. Jon What is the state of prior art for the P-384? When was it first published? Given that RIM is trying to sell itself right now and the patents are the only asset worth having, I don't have good feelings on this. Well apart from the business opportunities for expert witnesses specializing in crypto. The problem is that to make the market move we need everyone to decide to go in the same direction. So even though my employer can afford a license, there is no commercial value to that license unless everyone else has access. Do we have an ECC curve that is (1) secure and (2) has a written description prior to 1 Sept 1993? Due to submarine patent potential, even that is not necessarily enough but it would be a start. -- Website: http://hallambaker.com/ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 What is the state of prior art for the P-384? When was it first published? Given that RIM is trying to sell itself right now and the patents are the only asset worth having, I don't have good feelings on this. Well apart from the business opportunities for expert witnesses specializing in crypto. The problem is that to make the market move we need everyone to decide to go in the same direction. So even though my employer can afford a license, there is no commercial value to that license unless everyone else has access. Do we have an ECC curve that is (1) secure and (2) has a written description prior to 1 Sept 1993? Due to submarine patent potential, even that is not necessarily enough but it would be a start. My understanding is that of the NIST curves, P-256 and P-384 are unencumbered and that P-521 was dropped from Suite B because of IP concerns along with MQV. I don't pretend to speak with authority on any of it. The niggling things often don't make sense. I'm just saying what my understanding is. Jon -BEGIN PGP SIGNATURE- Version: PGP Universal 3.2.0 (Build 1672) Charset: iso-8859-1 wj8DBQFSJg4vsTedWZOD3gYRAka/AKChFoqbDL35bwkrSkeUWdLckNnh5QCfU2mh 7fBzDMh5JKvCI8Hu/AuIuk8= =dv6q -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On 2013-09-01 9:11 PM, Jerry Leichter wrote: Meanwhile, on the authentication side, Stuxnet provided evidence that the secret community *does* have capabilities (to conduct a collision attacks) beyond those known to the public - capabilities sufficient to produce fake Windows updates. Do we know they produced fake windows updates without assistance from Microsoft? ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sep 1, 2013, at 6:06 PM, Perry E. Metzger wrote: We know what they spec for use by the rest of the US government in Suite B. http://www.nsa.gov/ia/programs/suiteb_cryptography/ AES with 128-bit keys provides adequate protection for classified information up to the SECRET level. Similarly, ECDH and ECDSA using the 256-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-256 provide adequate protection for classified information up to the SECRET level. Until the conclusion of the transition period defined in CNSSP-15, DH, DSA and RSA can be used with a 2048-bit modulus to protect classified information up to the SECRET level. AES with 256-bit keys, Elliptic Curve Public Key Cryptography using the 384-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-384 are required to protect classified information at the TOP SECRET level. Since some products approved to protect classified information up to the TOP SECRET level will only contain algorithms with these parameters, algorithm interoperability between various products can only be guaranteed by having these parameters as options. We clearly cannot be absolutely sure of what they actually use, but we know what they procure commercially. If you feel this is all a big disinformation campaign, please feel free to give evidence for that. I certainly won't exclude the possibility, but I find it unlikely. I'll make just a couple of comments: - Given the huge amount of material classified these days, SECRET doesn't seem to be a very high level any more, whatever its official definition. TOP SECRET still means a great deal though. But the really important stuff is compartmented (SCI), and Suite B is not approved for it - it has to be protected by unpublished Suite A algorithms. - To let's look at what they want for TOP SECRET. First off, RSA - accepted for a transition period for SECRET, and then only with 2048 bit moduli, which until the last year or so were almost unknown in commercial settings - is completely out for TOP SECRET. So clearly they're faith in RSA is gone. (Same for DH and DSA.) It looks as if they are betting that factoring and discrete logs over the integers aren't as hard as people had thought. The whole business of AES-128 vs. AES-256 has been interesting from day one. Too many recommendations for using it are just based on some silly idea that bigger numbers are better - 128 bits is already way beyond brute force attacks. The two use the same transforms and the same key schedule. The only clear advantage AES-256 has is 4 extra rounds - any attack against the basic algorithm would almost certainly apply to both. On the other hand, many possible cracks might require significantly heavier computation for AES-256, even if the same fundamental attack works. One wonders NSA also wants SHA-384 - which is interesting given recent concerns about attacks on SHA-1 (which so far don't seem to extend to SHA-384). I don't want to get into deep conspiracy and disinformation campaign theories. My read of the situation is that at the time NSA gave its approval to this particular combination of ciphers, it believed they were secure. They seem to be having some doubts about RSA, DSA, and DH, though that could be, or could be justified as, ECC being as strong with much smaller, more practical, key lengths. Now, imagine that NSA really did find a way in to AES. If they were to suddenly withdraw approval for its use by the government, they would be revealing their abilities. A classic conundrum: How do you make use of the fruits of your cryptanalytic efforts without revealing that you've made progress? England accepted bombing raids on major cities to keep their crack of Enigma secret. So the continuation of such support tells us little. What will be interesting to see is how long the support continues. With work under way to replace SHA, a new version of the NSA recommendations will eventually have to be produced. Will it, for example, begin a phase-out of AES-128 for SECRET communications in favor of requiring AES-256 there as well? (Since there's no call so far to develop a cipher to replace AES, it would be difficult for NSA to recommend something else.) It's indeed a wilderness of mirrors, and we can only guess. But I'm very wary of using NSA's approval of a cipher as strong evidence, as the overall situation is complex and has so many tradeoffs. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Mon, 2 Sep 2013 00:06:21 -0400 Jerry Leichter leich...@lrw.com wrote: - To let's look at what they want for TOP SECRET. First off, RSA - accepted for a transition period for SECRET, and then only with 2048 bit moduli, which until the last year or so were almost unknown in commercial settings - is completely out for TOP SECRET. So clearly they're faith in RSA is gone. That is a misunderstanding. If you look at the way that the NSA specs these things, they try to keep all portions of a system of equal security so none is the weak point. A 2048 bit RSA key is factored vastly more easily than a 256 bit AES key is brute forced (that's just public knowledge -- try doing the back of the envelope yourself) so that size key would be insufficient. However, a sufficiently large RSA key to be correctly sized for 256 bit AES is totally impractical for performance reasons, see: http://www.nsa.gov/business/programs/elliptic_curve.shtml So clearly the purpose of pushing ECC for this application is that they want the public key algorithm and its key size to have comparable security while both performing reasonably well. (Same for DH and DSA.) It looks as if they are betting that factoring and discrete logs over the integers aren't as hard as people had thought. Not at all, and the rationale is public and seen above. I believe you're incorrectly claiming that we know much less than we actually do here. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sep 1, 2013, at 10:35 PM, James A. Donald wrote: Meanwhile, on the authentication side, Stuxnet provided evidence that the secret community *does* have capabilities (to conduct a collision attacks) beyond those known to the public - capabilities sufficient to produce fake Windows updates. Do we know they produced fake windows updates without assistance from Microsoft? For some version of know. From http://arstechnica.com/security/2012/06/flame-malware-was-signed-by-rogue-microsoft-certificate/: Microsoft released an emergency Windows update on Sunday after revealing that one of its trusted digital signatures was being abused to certify the validity of the Flame malware that has infected computers in Iran and other Middle Eastern Countries. The compromise exploited weaknesses in Terminal Server, a service many enterprises use to provide remote access to end-user computers. By targeting an undisclosed encryption algorithm Microsoft used to issue licenses for the service, attackers were able to create rogue intermediate certificate authorities that contained the imprimatur of Microsoft's own root authority certificate—an extremely sensitive cryptographic seal. Rogue intermediate certificate authorities that contained the stamp were then able to trick administrators and end users into trusting various Flame components by falsely certifying they were produced by Microsoft Based on the language in Microsoft's blog posts, it's impossible to rule out the possibility that at least one of the certificates revoked in the update was ... created using [previously reported] MD5 weaknesses [which allowed collision attacks]. Indeed, two of the underlying credentials used MD5, while the third used the more advanced SHA-1 algorithm. In a Frequently Asked Questions section of Microsoft Security Advisory (2718704), Microsoft's security team also said: During our investigation, a third Certificate Authority has been found to have issued certificates with weak ciphers. The advisory didn't elaborate. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
recent post with email discussing PGP-like implementation ... a decade before PGP in financial crypto blog http://www.garlic.com/~lynn/2013i.html#69 and then a little later realizing there were 3-kinds of crypto (when I was told I could make as many boxes as I wanted ... but could only sell to a certain gov. agency). In the late 90s, I worked on crypto chip for financial applications ... I would facetiously talk about taking a $500 mil-spec chip and cost reduce by 2-3 orders of magnitude while making it more secure (final objective was well under a dollar). Part of the objective was also to eliminate all the vulnerabilities that payment chips being done primarily in Europe were prone too. Long winded thread in financial crypto blog http://www.garlic.com/~lynn/subintegrity.html#yescard About that time, I was also approached by the transit industry to make the payment chip meet transit turnstyle requirements (while not reducing any security) ... this was a contactless chip being able to do crypto operation in 1/10th sec elapsed time and power profile of contactless transit turnstyle operation. RSA chips at the time were really large implementing 1024-bit arithmatic requiring enormous power and contact operation to get time in a few seconds. It turns out I could have a AADS chip strawman with ECC that was higher integrity *AND* could meet the transit industry turnstyle contactless power elapsed time profile. some past references to AADS chip strawman http://www.garlic.com/~lynn/x959.html#aadsstraw I was also asked to give presentation at Intel trusted computing ... gone 404 but lives on at wayback machine http://web.archive.org/web/20011109072807/http://www.intel94.com/idf/spr2001/sessiondescription.asp?id=stp+s13 one of the problems in the early part of the century was that I wanted to go for higher than EAL4+ evaluation ... but NIST(somebody) pullled the ECC evaluation criteria ... and since ECC was part of the chip silicon ... w/o the ECC evaluation criteria ... I had to settle for EAL4+. Possibly part of the issue with AADS chip strawman was I approached it as purely a cost issue ... and the objective was to eliminate all possible costs from the whole infrastructure ... the side effect of course, it also eliminated all related profit. -- virtualization experience starting Jan1968, online at home since Mar1970 ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Mon, 2 Sep 2013 15:09:31 -0400 Jerry Leichter leich...@lrw.com wrote: On Sep 2, 2013, at 1:25 PM, Perry E. Metzger wrote: On Mon, 2 Sep 2013 00:06:21 -0400 Jerry Leichter leich...@lrw.com wrote: - To let's look at what they want for TOP SECRET. First off, RSA - accepted for a transition period for SECRET, and then only with 2048 bit moduli, which until the last year or so were almost unknown in commercial settings - is completely out for TOP SECRET. So clearly they're faith in RSA is gone. That is a misunderstanding. If you look at the way that the NSA specs these things, they try to keep all portions of a system of equal security so none is the weak point. A 2048 bit RSA key is factored vastly more easily than a 256 bit AES key is brute forced (that's just public knowledge -- try doing the back of the envelope yourself) so that size key would be insufficient. However, a sufficiently large RSA key to be correctly sized for 256 bit AES is totally impractical for performance reasons, see: http://www.nsa.gov/business/programs/elliptic_curve.shtml a) The very reference you give says that to be equivalent to 128 bits symmetric, you'd need a 3072 bit RSA key - but they require a 2048 bit key. Only as a legacy you can do this for a while but please switch. And the same reference says that to be equivalent to 256 bits symmetric, you need a 521 bit ECC key - and yet they recommend 384 bits. So, no, even by that page, they are not recommending equivalent key sizes - and in fact the page says just that. I'd say they're judging a balance between security and performance while attempting not to leave particularly bad holes. b) Those comparisons long ago became essentially meaningless. On the symmetric size, it's using brute force attack strengths. But no one is going to brute force a 128-bit key with any known or suggested technology, and brute force attacks against 256-bit keys are way beyond what physics says is even remotely possible. I believe that is indeed a factor here, and is probably part of why the asymmetric key lengths aren't a bit longer. It is also possible they've been selected based on knowledge that AES keys are slightly weaker than we expect, but not radically so. As an aside, I'm reminded of the fact that there were certificational weaknesses in Skipjack that meant it was only more or less as potentially secure as the number of bits available in they key length. When this was pointed out to someone in the know, the mumble back I remember was in other words, they did the engineering correctly. Anyway, as I've said, I'm paranoid, but I operate under the assumption the counterparty is a reasonably rational actor that understands the very limited duration of secrets. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sep 2, 2013, at 1:25 PM, Perry E. Metzger wrote: On Mon, 2 Sep 2013 00:06:21 -0400 Jerry Leichter leich...@lrw.com wrote: - To let's look at what they want for TOP SECRET. First off, RSA - accepted for a transition period for SECRET, and then only with 2048 bit moduli, which until the last year or so were almost unknown in commercial settings - is completely out for TOP SECRET. So clearly they're faith in RSA is gone. That is a misunderstanding. If you look at the way that the NSA specs these things, they try to keep all portions of a system of equal security so none is the weak point. A 2048 bit RSA key is factored vastly more easily than a 256 bit AES key is brute forced (that's just public knowledge -- try doing the back of the envelope yourself) so that size key would be insufficient. However, a sufficiently large RSA key to be correctly sized for 256 bit AES is totally impractical for performance reasons, see: http://www.nsa.gov/business/programs/elliptic_curve.shtml a) The very reference you give says that to be equivalent to 128 bits symmetric, you'd need a 3072 bit RSA key - but they require a 2048 bit key. And the same reference says that to be equivalent to 256 bits symmetric, you need a 521 bit ECC key - and yet they recommend 384 bits. So, no, even by that page, they are not recommending equivalent key sizes - and in fact the page says just that. b) Those comparisons long ago became essentially meaningless. On the symmetric size, it's using brute force attack strengths. But no one is going to brute force a 128-bit key with any known or suggested technology, and brute force attacks against 256-bit keys are way beyond what physics says is even remotely possible. (I posted on this a long time back: Any theory even vaguely consistent with what we know about quantum mechanics places a limit on the number of elementary bit flips in a finite volume of space-time. If you want an answer in 100 years, your computer is at most a sphere in space-time 100 light-years cubed by 100 years in diameter - and that's a gross overestimate. My quick calculation showed that the quantum limit for that sphere is not far above 128 bits.) In any real terms, *if you're talking brute force*, 128 bits and 256 bits - and a million bits, if you want to go nuts about it - are indistinguishable. For the other columns, they don't say where the difficulty estimate comes from. (You could get a meaningless estimate by requiring that the number of primes of the size quoted be equivalent to the number of symmetric keys, but I'm assuming they're being more intelligent about the estimate than that, as a brute force attack on primes makes no sense at all. What makes more sense - and what they are presumably using - is the number of operations needed by the best known algorithm. But now we're at point of comparing impossible attacks against 128- and 256-bit symmetric keys with impossible attacks against 3072- or 15360-bit RSA keys - a waste of time. The relevant point is that attacks against RSA keys have been getting better faster than predicted, while the best publicly known attacks against AES have barely moved the needle from simple brute force. Given *currently publicly known algorithms*, a 2048 bit RSA key is still secure. (The same page shows that as equivalent to a 112-bit symmetric key, which is not only beyond any reasonable-term brute force attack, but longer than the keys used - according to some reports, anyway - on some Suite A algorithms.) So clearly the purpose of pushing ECC for this application is that they want the public key algorithm and its key size to have comparable security while both performing reasonably well. (Same for DH and DSA.) It looks as if they are betting that factoring and discrete logs over the integers aren't as hard as people had thought. And here we actually agree. Note that I didn't say there was any evidence that NSA was ahead of the public state of the art - even given the public state of the art and the rate that it's advancing, using Z/p as a field is rapidly fading as a realistic alternative. NSA, looking forward, would be making the recommendation to move to elliptic curves whether or not they could do better than the public at large. So we can't read much into that aspect of it. However, note (a) that if NSA does have a theoretical breakthrough, factoring is probably more likely than AES - we know they've hired many people in related fields over many years, and even in public the state of the art has been advancing; (b) most of the Internet is way behind recommendations that are now out there for everyone. Google recently switched to 2048 bit keys; hardly any other sites have done so, and some older software even has trouble talking to Google as a result. Not at all, and the rationale is public and seen above. I believe you're incorrectly claiming that we know much less than we
Re: [Cryptography] NSA and cryptanalysis
On Sun, Sep 1, 2013 at 10:35 PM, James A. Donald jam...@echeque.com wrote: On 2013-09-01 9:11 PM, Jerry Leichter wrote: Meanwhile, on the authentication side, Stuxnet provided evidence that the secret community *does* have capabilities (to conduct a collision attacks) beyond those known to the public - capabilities sufficient to produce fake Windows updates. Do we know they produced fake windows updates without assistance from Microsoft? Given the reaction from Microsoft, yes. The Microsoft public affairs people have been demonstrating real anger at the Flame attack in many forums. -- Website: http://hallambaker.com/ ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Mon, 2 Sep 2013 14:45:00 -0400 Phillip Hallam-Baker hal...@gmail.com wrote: Do we know they produced fake windows updates without assistance from Microsoft? Given the reaction from Microsoft, yes. The Microsoft public affairs people have been demonstrating real anger at the Flame attack in many forums. But of course, sufficiently paranoid people might contend that perhaps the Microsoft people who complained might not have been briefed by the ones who cooperated. The problem with all such exercises is that they involve too many layers of recursive paranoia, but do not pay off with useful information that tells me how to act going forward. In the current case, the fact that they *could* potentially suborn process inside a vendor is an interesting thing to consider when doing design, and whether they *have* is less interesting to me. Clearly, as things like bad vendor drivers updates have been sent out using stolen keys in the past, and clearly vendors might simply make mistakes in the future. From there, I can consider whether the someone at vendor signs bad updates security model component is productive to defend against or not, and how one might defend against it. (In the current case, I'd say only typed assembly language offers an interesting defense against bad binaries that get executed in kernel mode, regardless of why they are bad. Using typed assembly language effectively of course requires that the code be written in a high level language with strong typing to be preserved in the delivered machine code in the first place.) I leave speculation to pundits, and prefer to write code and design protocols. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
You know, if there was a completely ironclad legal opinion that made use of ECC possible without the risk of a lawsuit costing over $2 million from Certicom then I would be happy to endorse a switch to ECC like the NSA is pushing for as well. I would not therefore draw the conclusion that NSA advice to move to ECC is motivated by knowledge of a crack of RSA, if anything that would argue against moving from ECC. It is merely a consequence of the US government having a license which we don't have. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
Do we know they produced fake windows updates without assistance from Microsoft? Given the reaction from Microsoft, yes. The Microsoft public affairs people have been demonstrating real anger at the Flame attack in many forums. But of course, sufficiently paranoid people might contend that perhaps the Microsoft people who complained might not have been briefed by the ones who cooperated. I would be very surprised if they had gotten any assistance from Microsoft. It goes against the grain. Microsoft engineers are really indoctrinated with the trustworthy computing agenda, with mandatory security training every year, specialized design reviews, code reviews, tests and all that. Not saying there are no bugs or oversights in Microsoft's code, but a deliberate action like that is very unlikely. Also, It would be very difficult to keep something like that secret for long, and the leak would have dire effects on the company's reputation. -- Christian Huitema ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Mon, 2 Sep 2013 13:14:00 -0700 Christian Huitema huit...@huitema.net wrote: Do we know they produced fake windows updates without assistance from Microsoft? Given the reaction from Microsoft, yes. The Microsoft public affairs people have been demonstrating real anger at the Flame attack in many forums. But of course, sufficiently paranoid people might contend that perhaps the Microsoft people who complained might not have been briefed by the ones who cooperated. I would be very surprised if they had gotten any assistance from Microsoft. As would I. Not my wider point. My wider point is that the speculation is not helpful, and one probably wants to think about how to make things trustworthy even in the presence of bugs, adversaries who look like bugs for most viewpoints, etc. Paranoid speculation is useless, concrete discussion of threat models and how to address them is useful. (Thus why I mentioned things like typed assembly language as being a more productive topic than infinitely recursive paranoia. One can speculate endlessly on who is collaborating with whom without ever terminating, but robust threat models with technical solutions are something you can actually do something about.) Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Mon, 2 Sep 2013 17:44:57 -0400 Jerry Leichter leich...@lrw.com wrote: ...Clearly, as things like bad vendor drivers updates have been sent out using stolen keys in the past, and clearly vendors might simply make mistakes in the future Except that that's not what happened in this case. Someone took an old, valid Microsoft license - which should never Yes, certainly, but the end effect was that an untrustworthy piece of code was then executing on the victim's machine. That can be happen by many means, however, both intentional and accidental -- trojan horses, vendor mistakes, bugs, rogue employees at a vendor, a vendor's credentials being stolen, cryptographic breaks like this, etc. Now, I do indeed find it interesting and exotic that someone involved knows how to create MD5 collisions by a different method than we know of in the open literature, and that tickles my fancy as a person who loves cryptography, and probably tells us something about who wrote that particular exploit. What it does not do, however, is tell me much about how to make systems robust against the wide variety of reasons why untrustworthy software might appear on a machine. As a security person, it is this latter problem that is vital to me, since doubtless that will show up again in the future. Even ignoring malice, bugs often happen in device drivers and other code running in security critical environments like kernels. I will again mumble things like: typed assembly language, proof carrying code, microkernels, hardware assists, formal verification... in the hopes that the mumbling might set some minds thinking. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
Do we know they produced fake windows updates without assistance from Microsoft? Given the reaction from Microsoft, yes. The Microsoft public affairs people have been demonstrating real anger at the Flame attack in many forums. ...Clearly, as things like bad vendor drivers updates have been sent out using stolen keys in the past, and clearly vendors might simply make mistakes in the future Except that that's not what happened in this case. Someone took an old, valid Microsoft license - which should never have been issued, and which was blocked on Vista and Windows 7. They worked around the block using a technique that required the ability to produce MD5 collisions, which allowed them to spoof Windows Update. All the details are at http://trailofbits.files.wordpress.com/2012/06/flame-md5.pdf. A cryptographic approach for producing chosen-prefix collisions in MD5 was presented at CCC in 2008, with a cost estimate of about $20K on a 2008 Amazon EC2 cluster - the authors showed a POC using a cluster of PS3's. Open source code to implement the attack was published in 2009. However, the form of the collision apparently didn't match the published code, nor, more fundamentally, the theoretical work that made it possible. Someone has a *different*, so far nowhere-published attack. The comment that this required world-class cryptanalysis came from the developer of the published chosen-prefix attack, Marc Stevens. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Mon, Sep 02, 2013 at 03:09:31PM -0400, Jerry Leichter wrote: a) The very reference you give says that to be equivalent to 128 bits symmetric, you'd need a 3072 bit RSA key - but they require a 2048 bit key. And the same reference says that to be equivalent to 256 bits symmetric, you need a 521 bit ECC key - and yet they recommend 384 bits. So, no, even by that page, they are not recommending equivalent key sizes - and in fact the page says just that. Suite B is specified for 128 and 192 bit security levels, with the 192 bit level using ECC-384, SHA-384, and AES-256. So it seems like if there is a hint to be drawn from the Suite B params, it's about AES-192. (b) most of the Internet is way behind recommendations that are now out there for everyone. Google recently switched to 2048 bit keys; hardly any other sites have done so, and some older software even has trouble talking to Google as a result. Not to mention that our entire PKI system (as well as TLS 1.2, ie the versions actually supported in browsers) rely on the security of SHA-1, an algorithm which has a public 2**68 (IIRC) collision attack and which was phased out by NIST years ago. Fortunately now TLS 1.2 is finally being forced into most browsers thanks to BEAST, Lucky13, RC4 breaks, etc but still we're bound to see some major problems on the PKI side when a practical chosen prefix SHA-1 collision is found, as I expect at least a few widely used CAs have still not adopted randomized serial numbers and will have the MD5 experience all over again. On the symmetric side, I've already agreed that NSA's approval indicated that the considered AES secure 10 years ago, but if they've since learned otherwise but think they are and will remain the only ones with a viable attack for a while, they would be unlikely to admit it by changing their recommendation now. Worth noting that NIST has announced plans to create AEAD modes based on Keccak. It will be interesting to see how quickly AES-GCM is phased out of Suite B once that occurs. Jack ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sep 2, 2013, at 3:06 PM, Jack Lloyd ll...@randombit.net wrote: On Mon, Sep 02, 2013 at 03:09:31PM -0400, Jerry Leichter wrote: a) The very reference you give says that to be equivalent to 128 bits symmetric, you'd need a 3072 bit RSA key - but they require a 2048 bit key. And the same reference says that to be equivalent to 256 bits symmetric, you need a 521 bit ECC key - and yet they recommend 384 bits. So, no, even by that page, they are not recommending equivalent key sizes - and in fact the page says just that. Suite B is specified for 128 and 192 bit security levels, with the 192 bit level using ECC-384, SHA-384, and AES-256. So it seems like if there is a hint to be drawn from the Suite B params, it's about AES-192. The real issue is that the P-521 curve has IP against it, so if you want to use freely usable curves, you're stuck with P-256 and P-384 until some more patents expire. That's more of it than 192 bit security. We can hold our noses and use P-384 and AES-256 for a while. Jon -BEGIN PGP SIGNATURE- Version: PGP Universal 3.2.0 (Build 1672) Charset: us-ascii wj8DBQFSJWpasTedWZOD3gYRAjMtAKD/W9IPWtI8qwpP7w0v1aX9BgrwHACeMsRl 594r4LFPCTsIA9+xBUk4/5Q= =RGYR -END PGP SIGNATURE- ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sat, 31 Aug 2013 17:00:01 -0400 John Kelsey crypto@gmail.com wrote: If I had to bet, I'd bet on bad rngs as the most likely source of a breakthrough in decrypting lots of encrypted traffic from different sources. This seems by far the most probable conclusion. Note, for example, Heninger et al's recent work on the Taiwanese national smartcards. A discovery that some commonly used randomness sources are dramatically less random than supposed could dramatically lower the work factor on an otherwise brute force attack. That said, we simply can't know, and I think excessive speculation on the basis of no actual concrete information isn't that productive. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sep 1, 2013, at 2:36 AM, Peter Gutmann wrote: John Kelsey crypto@gmail.com writes: If I had to bet, I'd bet on bad rngs as the most likely source of a breakthrough in decrypting lots of encrypted traffic from different sources. If I had to bet, I'd bet on anything but the crypto. Why attack when you can bypass [1]. Well, sure. But ... I find it hard to be quite so confident. In practical terms, the vast majority of encrypted data in the world, whether in motion or at rest, is protected by one of two algorithms: RSA and AES. In some cases, RSA is used to encrypt AES keys, so an RSA break amounts to a bypass of AES. If you want to consider signatures and authentication, you come back to RSA again, and add SHA-1. This is not to say there aren't other techniques out there, or that new ones aren't being developed. But to NSA it's clearly a game of numbers - and any kind of wedge into either of just two algorithms would expose huge amounts of traffic to interception. Meanwhile, on the authentication side, Stuxnet provided evidence that the secret community *does* have capabilities (to conduct a collision attacks) beyond those known to the public - capabilities sufficient to produce fake Windows updates. And recent evidence elsewhere (e.g., using a bug in the version of Firefox in the Tor Browser Bundle) has shown an interest and ability to actively attack systems. (Of course, being able to decrypt information without an active attack is always the ideal, as it leaves no traces.) I keep seeing statements that modern cryptographic algorithms are secure, don't worry - but if you step back a bit, it's really hard to justify such statements. We *know*, in a sense, that RSA is *not* secure: Advances in factoring have come faster than expected, so recommended key sizes have also been increasing faster than expected. Most of the world's sites will always be well behind the recommended sizes. Yes, we have alternatives like ECC, but they don't help the large number of sites that don't use them. Meanwhile, just what evidence do we really have that AES is secure? It's survived all known attacks. Good to know - but consider that until the publication of differential cryptanalysis, the public state of knowledge contained essentially *no* generic attacks newer than the WW II era attacks on Enigma. DC, and to a lesser degree linear cryptanalysis not long after, rendered every existing block cipher (other than DES, which was designed with secret knowledge of DC) obsolete in one stroke. There's been incremental progress since, but no breakthrough of a similar magnitude - in public. Is there really anything we know about AES that precludes the possibility of such a breakthrough? There's a fundamental question one should ask in designing a system: Do you want to protect against targeted attacks, or do you want to protect against broad fishing attacks? If the former, the general view is that if an organization with the resources of the NSA wants to get in, they will - generally by various kinds of bypass mechanisms. Of the latter, the cryptographic monoculture *that the best practices insist on* - use standard protocols, algorithms and codes; don't try to invent or even implement your own crypto; design according to Kirchoff's principle that only the key is secret - are exactly the *wrong* advice: You're allowing the attacker to amortize his attacks on you with attacks on everyone else. If I were really concerned about my conversations with a small group of others being intercepted as part of dragnet operations, I'd design my own small variations on existing protocols. Mix pre-shared secrets into a DH exchange to pick keys. Use simple steganography to hide a signal in anything being signed - if something shows up signed without that signal, I'll know (a) it's not valid; (b) someone has broken in. Modify AES in some way - e.g., insert an XOR with a separate key between two rounds. A directed attack would eventually break all this, but generic attacks would fail. (You could argue that the failure of generic attacks would cause my connections to stand out and thus draw attention. This is, perhaps, true - it depends on the success rate of the generic attacks, and on how many others are playing the same games I am. There's no free lunch.) It's interesting that what what little evidence we have about NSA procedures - from the design of Clipper to Suite B - hints that they deploy multiple cryptosystems tuned to particular needs. They don't seem to believe in a monoculture - at least for themselves. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
What I think we are worried about here are very widespread automated attacks,
and they're passive (data is collected and then attacks are run offline). All
that constrains what attacks make sense in this context. You need attacks that
you can run in a reasonable time, with minimal requirements on the amount of
plaintext or the specific values of plaintext. The perfect example of an
attack that works well here is a keysearch on DES; another example is the
attack on WEP.
All the attacks we know of on reduced-round AES and AES-like ciphers require a
lot of chosen plaintexts, or related key queries, or both. There is no way to
completely rule out some amazing new break of AES that makes the cipher fall
open and drop your plaintext in the attacker's lap, but I don't see anything at
all in the literature that supports that fear, and there are a *lot* of smart
people trying to find new ways to attack or use AES-like designs. So I put
this at the bottom of my list of likely problems.
Some attacks on public key systems also require huge numbers of encryptions or
specially formed ciphertexts that get sent to the target for decryption--we can
ignore those for this discussion. So we're looking at trying to factor an RSA
modulus or to examine a lot of RSA encryptions to a particular public key (and
maybe some signatures from that key) and try to get somewhere from that. I
don't know enough about the state of the art in factoring or attacking RSA to
have a strong intuition about how likely this is. I'm pretty skeptical,
though--the people. know who are experts in this stuff don't seem especially
worried. However, a huge breakthrough in factoring would make for workable
passive attacks of this kind, though it would have to be cheap enough to use to
break each user's public key separately.
Finally, we have the randomness sources used to generate RSA and AES keys.
This, like symmetric cryptanalysis, is an area I know really well. And my
intuition (backed by plenty of examples) is that this is probably the place
that is most likely to yield a practical offline attack of this kind. When
someone screws up the implementation of RSA or AES, they may at least notice
some interoperability problems. They will never notice this when they screw up
their implementation so that RNG only gets 32 bits of entropy before generating
the user's RSA keypair. And if I know that your RSA key is likely to have one
of these 2^{32} factors, I can make a passive attack work really well.
Comments?
--John
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sun, 1 Sep 2013 07:11:06 -0400 Jerry Leichter leich...@lrw.com wrote: Meanwhile, just what evidence do we really have that AES is secure? The fact that the USG likes using it, too. That's also evidence for eliptic curve techniques btw. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sep 1, 2013, at 2:11 PM, Perry E. Metzger wrote: On Sun, 1 Sep 2013 07:11:06 -0400 Jerry Leichter leich...@lrw.com wrote: Meanwhile, just what evidence do we really have that AES is secure? The fact that the USG likes using it, too. We know they *say in public* that it's acceptable. But do we know what they *actually use*? That's also evidence for eliptic curve techniques btw. Same problem. -- Jerry Perry -- Perry E. Metzger pe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Sun, 1 Sep 2013 16:33:56 -0400 Jerry Leichter leich...@lrw.com wrote: On Sep 1, 2013, at 2:11 PM, Perry E. Metzger wrote: On Sun, 1 Sep 2013 07:11:06 -0400 Jerry Leichter leich...@lrw.com wrote: Meanwhile, just what evidence do we really have that AES is secure? The fact that the USG likes using it, too. We know they *say in public* that it's acceptable. But do we know what they *actually use*? We know what they spec for use by the rest of the US government in Suite B. http://www.nsa.gov/ia/programs/suiteb_cryptography/ AES with 128-bit keys provides adequate protection for classified information up to the SECRET level. Similarly, ECDH and ECDSA using the 256-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-256 provide adequate protection for classified information up to the SECRET level. Until the conclusion of the transition period defined in CNSSP-15, DH, DSA and RSA can be used with a 2048-bit modulus to protect classified information up to the SECRET level. AES with 256-bit keys, Elliptic Curve Public Key Cryptography using the 384-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-384 are required to protect classified information at the TOP SECRET level. Since some products approved to protect classified information up to the TOP SECRET level will only contain algorithms with these parameters, algorithm interoperability between various products can only be guaranteed by having these parameters as options. We clearly cannot be absolutely sure of what they actually use, but we know what they procure commercially. If you feel this is all a big disinformation campaign, please feel free to give evidence for that. I certainly won't exclude the possibility, but I find it unlikely. Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Aug 30, 2013, at 1:17 PM, Jerry Leichter leich...@lrw.com wrote: So the latest Snowden data contains hints that the NSA (a) spends a great deal of money on cracking encrypted Internet traffic; (b) recently made some kind of a cryptanalytic breakthrough. What are we to make of this? (Obviously, this will all be wild speculation unless Snowden leaks more specific information - which wouldn't fit his style, at least as demonstrated so far.) I read that WP report too. IMHO this can only be related to RSA (factorization, side-channel attacks). 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] NSA and cryptanalysis
On Fri, Aug 30, 2013 at 07:17:08AM -0400, Jerry Leichter wrote: So the latest Snowden data contains hints that the NSA (a) spends a great deal of money on cracking encrypted Internet traffic; (b) recently made some kind of a cryptanalytic breakthrough. What are we to make of this? (Obviously, this will all be wild speculation unless Snowden leaks more specific information - which wouldn't fit his style, at least as demonstrated so far.) I wonder how much of the editing of the recent Snowden data is in any way related to Snowden himself (who is presumably very completely controlled and monitored by the Russians at the moment) ? The story as I understand it (from afar), is that he expropriated some roughly 20,000 complete NSA documents... and has turned some of them - mostly complete and unedited - over to his journalist collaborators who have in turn turned some of those over to their larger news organizations - where the editors have figured out what parts of them to publish under great pressure from various spooks and high officials NOT to publish certain information. What we have seen so far rather looks like it was heavily bowdlerized under very great government pressure from various governments, and it seems very likely MOST if not all of this pressure was aimed at the editorial and management level of news organizations, not Snowden himself (who is beyond their reach obviously, but also not in a position to control much about what is published). In the end it is pretty likely nobody in senior management of the media organizations involved really wants to take responsibility for leaking something that actually destroys a major US intelligence edge... and what was left out to protect legitimate US intelligence secrets or technical methods is anyone's guess at the moment. Surely, however, inevitably eventually *some* of this will leak out of the media organizations to the extent that it has passed outside of a very very small circle of people there. What is not clear, is how many of those folks at the media organizations know enough about the technological implications of what they are reading to understand what its long term significance is. A cryptanalytic breakthrough might be huge and fundamental and invalidate a lot of currently deployed cryptography, or just a new and very effective attack on some aspect of a commonly used security protocol that can be easily patched once it is known. -- Jerry -- Dave Emery N1PRE/AE, d...@dieconsulting.com DIE Consulting, Weston, Mass 02493 An empty zombie mind with a forlorn barely readable weatherbeaten 'For Rent' sign still vainly flapping outside on the weed encrusted pole - in celebration of what could have been, but wasn't and is not to be now either. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On 08/30/2013 08:10 PM, Aaron Zauner wrote: I read that WP report too. IMHO this can only be related to RSA (factorization, side-channel attacks). I have been hearing rumors lately that factoring may not in fact be as hard as we have heretofore supposed. Algorithmic advances keep eating into RSA keys, as fast as hardware advances do. A breakthrough allowing most RSA keys to be factored could be just one or two more jumps of algorithmic leverage away (from academics; possibly not from the NSA). It could also be the case that special-purpose ASICs that accelerate the process substantially may have been designed and built. We know about Shor's algorithm for factoring in NlogN time. It requires a quantum computer to run though. We have heard rumors of quantum computers being built, and I recall a group of academics who actually built one nearly eight years ago. That seems to be the sort of thing that would attract attention from a lot of three-letter agencies, and efforts to scale it up would be intensely supported with all the resources and brainpower that such an organization could bring to bear. How far have they come in eight years? It is both interesting and peculiar that so little news of quantum computing has been published since. Bear ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On 31/08/13 06:10 AM, Aaron Zauner wrote: On Aug 30, 2013, at 1:17 PM, Jerry Leichter leich...@lrw.com wrote: So the latest Snowden data contains hints that the NSA (a) spends a great deal of money on cracking encrypted Internet traffic; (b) recently made some kind of a cryptanalytic breakthrough. What are we to make of this? (Obviously, this will all be wild speculation unless Snowden leaks more specific information - which wouldn't fit his style, at least as demonstrated so far.) I read that WP report too. IMHO this can only be related to RSA (factorization, side-channel attacks). It's all speculation of course, but that is what it feels like to me. An interesting clue from the earlier report is that they aren't there yet, they're building towards a capability. They've figured out some way to crack in theoretically, and with a big investment they'll get there. Which suggests a combination of massive crunch power, keys on the margin *and* cribs from side-channel attacks. The bright shiny new 3rd division of the NSA is responsible for the side-channel attack. And it was very expensive... Coincidence? Or, it could all be fluff, designed to suck money from cow in w.DC. Many a conman has made rich by claiming some secret invention; the investors are the muggins for putting their money in without doing the due diligence. iang ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
If I had to bet, I'd bet on bad rngs as the most likely source of a breakthrough in decrypting lots of encrypted traffic from different sources. --John ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On 2013-09-01 4:02 AM, Ray Dillinger wrote: On 08/30/2013 08:10 PM, Aaron Zauner wrote: I read that WP report too. IMHO this can only be related to RSA (factorization, side-channel attacks). I have been hearing rumors lately that factoring may not in fact be as hard as we have heretofore supposed. Algorithmic advances keep eating into RSA keys, as fast as hardware advances do. So far, not much affect on elliptic keys. Except that all elliptic keys of the extremely useful gap-diffie-hellman group are potentially subject to techniques analogous to those that are attacking RSA. ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] NSA and cryptanalysis
On Aug 31, 2013, at 2:02 PM, Ray Dillinger wrote: ... It is both interesting and peculiar that so little news of quantum computing has been published since. I don't understand this claim. Shor's work opened up a really hot new area that both CS people and physicists (and others as well) have rapidly jumped into. There's been a huge amount of publication on quantum computing and, more generally, the field of quantum information. No one - at least publicly - claims to know how to build a non-toy quantum computer here (the D-wave machine, if it's really doing quantum computation, is a special kind of machine and couldn't run Shor's algorithm, for example). But there are many reported advances on the physics. Simultaneously, there's quite a bit of published work on the algorithmic/complexity side as well. A look at http://en.wikipedia.org/wiki/Quantum_computer will readily confirm this. If you want to dig deeper, there's Scott Aaronson's blog at http://www.scottaaronson.com/blog/ -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] NSA and cryptanalysis
So the latest Snowden data contains hints that the NSA (a) spends a great deal of money on cracking encrypted Internet traffic; (b) recently made some kind of a cryptanalytic breakthrough. What are we to make of this? (Obviously, this will all be wild speculation unless Snowden leaks more specific information - which wouldn't fit his style, at least as demonstrated so far.) -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
