Re: [cryptography] Duplicate primes in lots of RSA moduli
Michael Nelson nelson_mi...@yahoo.com writes: Paper by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter finds that two of every one thousand RSA moduli that they collected from the web offer no security. An astonishing number of generated pairs of primes have a prime in common. The title of the paper Ron was wrong, Whit is right I think is rather misleading, since virtually all the DSA keys were PGP-generated and there was only one ECDSA key, while there were vast numbers of RSA keys from all manner of software. So what it should really say is PGP got DSA keygen right, the sample size for ECDSA is too small to make any meaingful comment, and some RSA implementations aren't so good. Peter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
Hi, Paper by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter finds that two of every one thousand RSA moduli that they collected from the web offer no security. An astonishing number of generated pairs of primes have a prime in common. The title of the paper Ron was wrong, Whit is right I think is rather misleading, since virtually all the DSA keys were PGP-generated and there was only one ECDSA key, while there were vast numbers of RSA keys from all manner of software. So what it should really say is PGP got DSA keygen right, the sample size for ECDSA is too small to make any meaingful comment, and some RSA implementations aren't so good. Their survey seems to be very nice work. But they reach this conclusion in the abstract that RSA is significantly riskier than ElGamal/DSA. In the body of the paper, they indicate (although they are much more defensive already) that this is due to the fact that you need two factors and more randomness to go into the key creation. The larger number of weak RSA keys is then taken as an indication that this is inherently a problem of RSA. It's a leap. If you need more input, more can go wrong; but it does not seem conclusive evidence here. It would be conclusive if they compared keys created with the help of the same source of randomness and primality testers. Interestingly, in their own conclusions section they do not reiterate the above statement. Ralph -- Ralph Holz Network Architectures and Services Technische Universität München http://www.net.in.tum.de/de/mitarbeiter/holz/ PGP: A805 D19C E23E 6BBB E0C4 86DC 520E 0C83 69B0 03EF signature.asc Description: OpenPGP digital signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Feb 14, 2012, at 10:02 PM, Jon Callas wrote: On 14 Feb, 2012, at 5:58 PM, Steven Bellovin wrote: The practical import is unclear, since there's (as far as is known) no way to predict or control who has a bad key. To me, the interesting question is how to distribute the results. That is, how can you safely tell people you have a bad key, without letting bad guys probe your oracle. I suspect that the right way to do it is to require someone to sign a hash of a random challenge, thereby proving ownership of the private key, before you'll tell them if the corresponding public key is in your database. Yeah, but if you're a bad guy, you can download the EFF's SSL Observatory and just construct your own oracle. It's a lot like rainbow tables in that once you learn the utility of the trick, you just replicate the results. If you implement something like the Certificate Transparency, you have an authenticated database of authoritative data to replicate the oracle with. Waving my hand and making software magically appear, I'd combine Certificate Transparency and such an oracle be combined, and compute the status of the key as part of the certificate logs and proofs. Note that they very carefully didn't say how they did it. I have my own ideas -- but they're just that, ideas; I haven't analyzed them carefully, let alone coded them. --Steve Bellovin, https://www.cs.columbia.edu/~smb ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] On the duplicate RSA keys issue
Hi, the following blog post, which documents similar efforts, sheds some light, I think: https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs Ralph -- Ralph Holz Network Architectures and Services Technische Universität München http://www.net.in.tum.de/de/mitarbeiter/holz/ PGP: A805 D19C E23E 6BBB E0C4 86DC 520E 0C83 69B0 03EF signature.asc Description: OpenPGP digital signature ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Wed, 15 Feb 2012, Ralph Holz wrote: But they reach this conclusion in the abstract that RSA is significantly riskier than ElGamal/DSA. In the body of the paper, they indicate (although they are much more defensive already) that this is due to the fact that you need two factors and more randomness to go into the key creation. While the RSA may be easier to break if the entropy during the key *generation* is low, the DSA is easier to break if the entropy during the key *use* is low. Obviously, if you have access only to the public keys, the first issue is more spectacular, but usually a key is used more often than generated. -- Regards, ASK ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Wed, Feb 15, 2012 at 4:56 PM, Ben Laurie b...@links.org wrote: On Wed, Feb 15, 2012 at 4:13 PM, Steven Bellovin s...@cs.columbia.edu wrote: On Feb 14, 2012, at 10:02 PM, Jon Callas wrote: On 14 Feb, 2012, at 5:58 PM, Steven Bellovin wrote: The practical import is unclear, since there's (as far as is known) no way to predict or control who has a bad key. To me, the interesting question is how to distribute the results. That is, how can you safely tell people you have a bad key, without letting bad guys probe your oracle. I suspect that the right way to do it is to require someone to sign a hash of a random challenge, thereby proving ownership of the private key, before you'll tell them if the corresponding public key is in your database. Yeah, but if you're a bad guy, you can download the EFF's SSL Observatory and just construct your own oracle. It's a lot like rainbow tables in that once you learn the utility of the trick, you just replicate the results. If you implement something like the Certificate Transparency, you have an authenticated database of authoritative data to replicate the oracle with. Waving my hand and making software magically appear, I'd combine Certificate Transparency and such an oracle be combined, and compute the status of the key as part of the certificate logs and proofs. Note that they very carefully didn't say how they did it. I have my own ideas -- but they're just that, ideas; I haven't analyzed them carefully, let alone coded them. I did this years ago for PGP keys. Easy: take all the keys, do pairwise GCD. Took 24 hours on my laptop for all the PGP keys on keyservers at the time. I'm trying to remember when this was, but I did it during PETS at Toronto, so that should narrow it down. With Matthias XXX (I've forgotten his surname!). Now wish I'd repeated the experiment for SSL :-) BTW, we wrote the code and ran the keys during PETS, so not exactly rocket science. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Wed, 15 Feb 2012, Steven Bellovin wrote: Note that they very carefully didn't say how they did it. I have my own ideas -- but they're just that, ideas; I haven't analyzed them carefully, let alone coded them. If one limits the same-factor search to the keys of the same model of each device, one can even do the trivial pair-wise search among few thousand keys, but the general technique is also not a secret: https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs -- Regards, ASK ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On 15 February 2012 11:56, Ben Laurie b...@links.org wrote: I did this years ago for PGP keys. Easy: take all the keys, do pairwise GCD. Took 24 hours on my laptop for all the PGP keys on keyservers at the time. I'm trying to remember when this was, but I did it during PETS at Toronto, so that should narrow it down. With Matthias XXX (I've forgotten his surname!). I mentioned this a few months ago, you had said you did it at PETS 2004. [0,1] Something I found strange in their paper was this quote: PGP keys have no expiration dates or hashes. All public keys were further analysed as described below. (bottom of page 4) PGP keys *may* have no expiration date, but they may, and anecdotally most I've seen do. Likewise, nearly all keys have a self-signed UID associated with them, and that signature uses a hash algorithm. -tom [0] Original Thread: http://lists.randombit.net/pipermail/cryptography/2011-September/001301.html [0] Your Reply: http://lists.randombit.net/pipermail/cryptography/2011-September/001305.html ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] This paper was presented in August?
Crypto shocker: four of every 1,000 public keys provide no security (updated) By Dan Goodin | Published February 15, 2012 6:00 AM Crypto shocker: four of every 1,000 public keys provide no security (updated) Keys that share one prime factor are vulnerable to cracking by anyone. Keys that share both prime factors can be broken by the other holder. An astonishing four out of every 1,000 public keys protecting webmail, online banking, and other sensitive online services provide no cryptographic security, a team of mathematicians has found. The research is the latest to reveal limitations in the tech used by more than a million Internet sites to prevent eavesdropping. The finding, reported in a paper (PDF) submitted to a cryptography conference in August, is based on the analysis of some 7.1 million 1024-bit RSA keys published online. By subjecting what's known as the modulus of each public key to an algorithm first postulated more than 2,000 years ago by the Greek mathematician Euclid, the researchers looked for underlying factors that were used more than once. Almost 27,000 of the keys they examined were cryptographically worthless because one of the factors used to generate them was used by at least one other key. ... http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars?utm_source=feedburnerutm_medium=feedutm_campaign=Feed%3A+arstechnica%2Findex+%28Ars+Technica+-+Featured+Content%29 ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] This paper was presented in August?
This coming August. --Paul Hoffman ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] how many MITM-enabling sub-roots chain up to public-facing CAs ?
From: James A. Donald jam...@echeque.com Not only is their lower class law abiding, their bankers and bureaucrats, unlike ours are also law abiding. From which it is evident that the death penalty *does* deter, both for institutions and individuals. Sub-Saharan Africa is in general hotter than Canada. The best runners in the world are African, not Canadian. From which it is evident that higher average temperatures causes faster runners. Unless there's some other explanation? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
Alexander Klimov alser...@inbox.ru writes: While the RSA may be easier to break if the entropy during the key *generation* is low, the DSA is easier to break if the entropy during the key *use* is low. Obviously, if you have access only to the public keys, the first issue is more spectacular, but usually a key is used more often than generated. My thoughts exactly, I've always stayed away from DLP-based PKCs (except DH) because they're extraordinarily brittle, with RSA you have to get entropy use right just once, with DLP PKCs you have to get it right every single time you use them. For embedded systems in particular that's just too risky. Peter. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Wed, Feb 15, 2012 at 5:57 PM, Peter Gutmann pgut...@cs.auckland.ac.nz wrote: Alexander Klimov alser...@inbox.ru writes: While the RSA may be easier to break if the entropy during the key *generation* is low, the DSA is easier to break if the entropy during the key *use* is low. Obviously, if you have access only to the public keys, the first issue is more spectacular, but usually a key is used more often than generated. My thoughts exactly, I've always stayed away from DLP-based PKCs (except DH) because they're extraordinarily brittle, with RSA you have to get entropy use right just once, with DLP PKCs you have to get it right every single time you use them. For embedded systems in particular that's just too risky. Of course, if you're doing RSA key transport and the client selects the key and has little or no entropy then the client still has a problem (and the server may not know). Most cryptographic protocols call for random keys, nonces, confounders, IVs, and so on somewhere. Typically the security of the system depends to a large degree, if not entirely, on those random items. What can you do with RSA keys if you can't generate good entropy? You can sign. What else? You can encrypt messages small enough that there's no need to generate a symmetric key for encrypting the message (or you can chunk the message and encrypt each chunk). Oh, there is one thing one can do with RSA keys but without good enough entropy: one can *ask* a remote system for entropy (the remote system encrypts some entropy in the client's RSA public key, then signs this in the server's public key) -- much better than having no good entropy at all. Nico -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Duplicate primes in lots of RSA moduli
On Wed, 15 Feb 2012, Steven Bellovin wrote: On Feb 15, 2012, at 11:56 45AM, Ben Laurie wrote: I did this years ago for PGP keys. Easy: take all the keys, do pairwise GCD. Took 24 hours on my laptop for all the PGP keys on keyservers at the time. I'm trying to remember when this was, but I did it during PETS at Toronto, so that should narrow it down. With Matthias XXX (I've forgotten his surname!). How many keys? They had 11M keys, meaning there are 121e12 pairs. That's a lot of GCD operations... The blog post here: https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs Explains how it can be done in linear time. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] trustwave admits issuing corporate mitm certs
On Wed, Feb 15, 2012 at 12:49 AM, Jeffrey Walton noloa...@gmail.com wrote: On Sun, Feb 12, 2012 at 8:17 PM, Steven Bellovin s...@cs.columbia.edu wrote: On Feb 12, 2012, at 6:31 AM, Harald Hanche-Olsen wrote: [Jeffrey Walton noloa...@gmail.com (2012-02-12 10:57:02 UTC)] (1) How can a company actively attack a secure channel and tamper with communications if there are federal laws prohibiting it? IANAL, as they say, but I guess they are acting under the presumption that any communication originating in the company's own is the company's own communication, and so they can do anything they please with it. It could be argued that the notion of tampering with your own communications doesn't make sense, and so there is no breach of federal law. I am not defending the above interpretation, nor am I saying for sure that it holds water. But I think it is a reasonable guess, at least that that the company's lawyers will use arguments along those lines (abeit argued in more legalese terms) if they had to defend this practice. Although I'm not a lawyer, I've worked with a number of lawyers on the wiretap act, and have been studying it for close to 20 years. I do not see any criminal violation. Nor do I. If anything, I think this would be a civil matter. 18 USC 2512 (http://www.law.cornell.edu/uscode/text/18/2512) bars devices if design of such device renders it primarily useful for the purpose of the surreptitious interception of wire, oral, or electronic communications. Is a private key or certificate a device? Not as I read 18 USC 2510(5) (http://www.law.cornell.edu/uscode/text/18/2510). Paragraph (12) of that section would seem to say that intra-company wires aren't covered. But a better explanation of that can be found in Ruel Torres Hernandez, ECPA and online computer privacy, Federal Communications Law Journal, 41(1):17–41, November 1988. He not only concluded that the ECPA did not bar a company from monitoring his own devices, he quoted a participant in the law's drafting process as saying that that was by intent. California law bars employers from monitoring employee phone calls, but in 1991 a court there explicitly ruled that monitoring email was permissible -- or rather, that it wasn't barred by a statute that only spoke of phone calls. I looked at the cited cases. As a layman, I'm not contesting the fact that an employer has a right to monitor its employees, and I understand why some of the plaintiff positions were undefensible in civil court. I'm talking about violation of US Code and criminal cases. Remember, a lot of these corporations wanted harsh regulations for folks breaking into their [insecure] networks. Obviously, they don't want to eat their own dog food. But some of this stuff is sufficiently broad so that their actions are criminal despite their intentions or desires. I'd agree that their actions are immoral / unethical, but that doesn't make their actions criminal, especially if their users consent to monitoring of all company computer and network usage. And, the AUPs that I've seen at all the companies that I've worked for as both employee and contractor all make you sign those...otherwise, you won't be collecting a pay check. If the company did not inform the employees that they were being monitored, then _perhaps_ a criminal case might be made based on illegal wire tap statutes, but I do not not have enough knowledge to judge that. As they say, IANAL. Whether they like or or not (or agree or disagree), they were only authorized to transmit traffic. Perhaps, if you are talking about someone who is merely acting in the role of provider / carrier of services, but I thought this discussion was about employee / employer relationships. Maybe I'm misunderstanding something that you are trying to communicate. Here, I speak of the communications between two parties - A and B. When they peeled away SSL/TLS, they exceeded their authorization. Even if party A agreed to be monitored, I doubt party B also agreed 'a priori,' especially if party B did not reside on the same corporate network. Hence a criminal violation of federal code. In some states, both parties do not need to be informed that they are being monitored...only one of the parties needs to be aware. However, regardless of that, I don't see how this is any different in principle if a company decided to install a keystroke logger on your company PC and take a constant video of your screen? Is that illegal? Probably not if the employees consent to it. How about if I monitor your network traffic by decrypting your SSL connection at your PC's endpoint by some SSL DLL that would leak the SSL master key and record that and the SSL keystream to some central server? Again, I think that would only be illegal if employees did not consent to monitoring. That said, I do think that companies may be in trial from a civil suit perspective, especially if it had been widely known that
