How easy it is to break into crypto systems
Begin forwarded message:
From: Jon Callas
Date: July 9, 2006 5:56:15 PM EDT
To: dave@farber.net
Cc: Jon Callas
Subject: Re: [IP] more on FBI plans new Net-tapping push
Brian Randell said:
Just because the government *claims* it can't break a given code ... :-)
I realize that there was a smiley face at the end of this, and I might be showing humorlessness about this, but this concerns my profession in general, and my software in particular. Consequently, I have no choice but to comment on this remark.
Modern cryptographic systems are essentially unbreakable, particularly if an adversary is restricted to intercepts. We have argued for, designed, and built systems with 128 bits of security precisely because they are essentially unbreakable. It is very easy to underestimate the power of exponentials. 2^128 is a very big number. Burt Kaliski first came up with this characterization, and if he had a nickel for every time I tell it, he could buy a latte or three.
Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years.
If you want to brute-force a key, it literally takes a planet-ful of computers. And of course, there are always 256-bit keys, if you worry about the possibility that government has a spare planet that they want to devote to key-cracking.
Now of course, there are other ways to break the system.
They could know something we don't. They could know some fundamental truth about mathematics (like how to factor really fast), some effective form of symmetric cryptanalysis, or something else. They could know about quantum computers, DNA computers, systems based upon non-Einsteinian physics, and so on. Yes, it's possible. But this quickly gets into true paranoid thought. There isn't a lot of difference between the *presumption* that they have such things and the presumption that they have aliens in a vault in Nevada. It isn't falsifiable. It gets irrational quickly. The evidence that we have about this suggests quite the opposite, but more on that later.
They could have something we don't. For example, they could know about software flaws in my or other people's computer systems. Yes, that's possible, too. At PGP Corporation, we guard against this by making our software available to people for their examination. Approximately 2,000 people per month do that. If you want to be one of them, go to.
They could be hacking people's systems. This is a much more reasonable worry. If I were going to be doing this, it's what I would do. The state of computer operational security is such that it makes much more sense to invest time, money, and effort into rootkits than into cryptanalysis.
However, there are things that we know that they *are* doing. One of them is relevant to this particular case. That is work on cracking the passphrases that people use to protect their keys. The cryptography we're using is itself uncrackable, but about 2/3 of the people in the world use a password (not even a passphrase) that directly relates to a pet or loved one. The order of frequency seems to be pets (living or dead), then children, then ex-loves. We know that at least one government has a password cracker that is based upon building a psychometric model of person who owns the key and constructing passphrases on that model. If you're a Hollywood private eye and they seize your computer and find on it that you're a basketball fan from your browser cache, then "Lak3rz 4 Teh w1n!" is actually a very bad passphrase. Don't blame me when they find it in about two minutes.
It isn't just government that does this, either. Companies such as Access Data and Elcomsoft have distributed password crackers. These things aren't hacking the crypto, they're hacking the mind using the crypto. My old friend and colleague, Drew Gross, who is a forensics expert, has said, "I love crypto; it tells me what part of the system not to bother attacking."
The last bit of evidence we have that suggests that they can't break the crypto is that they are apparently devoting a lot of effort to traffic analysis. Look at what we've learned in the last few months. Listening for keywords is so twentieth century. They're looking at call patterns, message flow, and so on. I could go on about this for a long time, but it's a tangent from this. If you're interested in more, I am going to be leading a panel at Defcon this August on traffic analysis. Come liven up the discussion.
Jon
--
Jon Callas
CTO, CSO
PGP Corporation Tel: +1 (650) 319-9016
3460 West Bayshore Fax: +1 (650) 319-9001
Palo Alto, CA 94303 PGP: ed15 5bdf cd41 adfc 00f3
USA 28b6 52bf 5a46 bc98 e63d
From: Jon Callas
Date: July 9, 2006 5:56:15 PM EDT
To: dave@farber.net
Cc: Jon Callas
Subject: Re: [IP] more on FBI plans new Net-tapping push
Brian Randell said:
Just because the government *claims* it can't break a given code ... :-)
I realize that there was a smiley face at the end of this, and I might be showing humorlessness about this, but this concerns my profession in general, and my software in particular. Consequently, I have no choice but to comment on this remark.
Modern cryptographic systems are essentially unbreakable, particularly if an adversary is restricted to intercepts. We have argued for, designed, and built systems with 128 bits of security precisely because they are essentially unbreakable. It is very easy to underestimate the power of exponentials. 2^128 is a very big number. Burt Kaliski first came up with this characterization, and if he had a nickel for every time I tell it, he could buy a latte or three.
Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years.
If you want to brute-force a key, it literally takes a planet-ful of computers. And of course, there are always 256-bit keys, if you worry about the possibility that government has a spare planet that they want to devote to key-cracking.
Now of course, there are other ways to break the system.
They could know something we don't. They could know some fundamental truth about mathematics (like how to factor really fast), some effective form of symmetric cryptanalysis, or something else. They could know about quantum computers, DNA computers, systems based upon non-Einsteinian physics, and so on. Yes, it's possible. But this quickly gets into true paranoid thought. There isn't a lot of difference between the *presumption* that they have such things and the presumption that they have aliens in a vault in Nevada. It isn't falsifiable. It gets irrational quickly. The evidence that we have about this suggests quite the opposite, but more on that later.
They could have something we don't. For example, they could know about software flaws in my or other people's computer systems. Yes, that's possible, too. At PGP Corporation, we guard against this by making our software available to people for their examination. Approximately 2,000 people per month do that. If you want to be one of them, go to
They could be hacking people's systems. This is a much more reasonable worry. If I were going to be doing this, it's what I would do. The state of computer operational security is such that it makes much more sense to invest time, money, and effort into rootkits than into cryptanalysis.
However, there are things that we know that they *are* doing. One of them is relevant to this particular case. That is work on cracking the passphrases that people use to protect their keys. The cryptography we're using is itself uncrackable, but about 2/3 of the people in the world use a password (not even a passphrase) that directly relates to a pet or loved one. The order of frequency seems to be pets (living or dead), then children, then ex-loves. We know that at least one government has a password cracker that is based upon building a psychometric model of person who owns the key and constructing passphrases on that model. If you're a Hollywood private eye and they seize your computer and find on it that you're a basketball fan from your browser cache, then "Lak3rz 4 Teh w1n!" is actually a very bad passphrase. Don't blame me when they find it in about two minutes.
It isn't just government that does this, either. Companies such as Access Data and Elcomsoft have distributed password crackers. These things aren't hacking the crypto, they're hacking the mind using the crypto. My old friend and colleague, Drew Gross, who is a forensics expert, has said, "I love crypto; it tells me what part of the system not to bother attacking."
The last bit of evidence we have that suggests that they can't break the crypto is that they are apparently devoting a lot of effort to traffic analysis. Look at what we've learned in the last few months. Listening for keywords is so twentieth century. They're looking at call patterns, message flow, and so on. I could go on about this for a long time, but it's a tangent from this. If you're interested in more, I am going to be leading a panel at Defcon this August on traffic analysis. Come liven up the discussion.
Jon
--
Jon Callas
CTO, CSO
PGP Corporation Tel: +1 (650) 319-9016
3460 West Bayshore Fax: +1 (650) 319-9001
Palo Alto, CA 94303 PGP: ed15 5bdf cd41 adfc 00f3
USA 28b6 52bf 5a46 bc98 e63d
posted by Nick Maslowski at 7/10/2006 09:11:00 AM
0 Comments:
Post a Comment
<< Home