Encryption, NSA, and terrorism

This is actually a question about a technology I use daily, and I still find it pretty cool. You can read about it here.

https://en.wikipedia.org/wiki/Public-key_cryptography

In a nutshell you can generate a pair of keys, one public and one private. These keys have the property that they can be mathematically generated together fairly easily, but one is computationally difficult (to the point of being unfeasible) to derive from the other.

I can give you my public key. My private key I keep secret.

You can use my public key to encrypt a message that only I can read. It is a one way operation. Someone else with my public key can't decrypt the message, only the private key can do that.

That way, we can exchange public keys... even post them on internet sites. And these keys can be used to send secure private messages.

The mathematics behind this are well known. Even so, with a reasonably sized key, it is computationally expensive (even prohibitively so) to crack even for the NSA.

Making sure that the public key you have for me is really my key (and some imposter pretending to be Max didn't give you a bogus key that she has the private key to read) is also interesting. There is key signing technology.

This can protect against the infamous "man in the middle attack".

If you are interested in any more detail of this stuff, let me know.

With public key cryptography you don't need to exchange a secret key, the secret is in mathematical problems that are for practical purposes only solvable one way (calculating it in reverse is not possible for practical purposes). This is because the calculation would take an army of computers a long time to finish (measurable in the years etc).

So you can exchange secrets using a public key, and for messaging systems like you describe the public key cryptography is often used to exchange a secret key for a symmetric-key algorithm to use to decode messages going forward.

I will say one more thing.

We are pretty sure that the mathematics behind the most common form of public key encryption is secure (i.e. that while encrypting is easy, decrypting is very expensive), but no one (as far as I know yet) has been able to mathematically prove that this is the case.

There is a very small, probably insignificant, chance that someone will come up with a way to decrypt that is easy (it involves finding certain prime numbers of large integers).... we are obviously confident enough that this won't happen that we base all of our encryption on.

But if anyone ever figures out how to do this, all of our encryption (used for internet security, encoded messages of all types, and even keeping bank accounts secure) will be come instantly useful and all of the protected information will become public.

My thanks to Max and Robert. I may have follow-up questions shortly. Meanwhile, I need to correct an error: the 109 encrypted messages were in connection with the Mohammed cartoon contest attack in Garland, Texas, not the San Bernardino shooters.

Public key elliptic curve is well on it way to replacing primes public keys as they seem more secure and need a great deal smaller key

Public key elliptic curve is well on it way to replacing primes public keys as they seem more secure and need a great deal smaller key

Robert Gentel wrote:

"...for messaging systems like you describe the public key cryptography is often used to exchange a secret key for a symmetric-key algorithm to use to decode messages going forward."

I presume that in these hybrid systems, a different secret key is used to encrypt each message, even though when sending multiple messages to a single receiver, a single public key is used to encrypt these different secret keys? Or is that incorrect?

Question: Do public key cryptography algorithms encrypt a secret key bit by bit, where each plaintext bit of the secret key is encrypted independently of the other bits; or does the encrypted value of a bit depend on the plaintext values of other bits?

A separate question: if a particular encryption app uses a known algorithm in applying a public key to encrypt a secret key, and both the algorithm and the public key are known, and the encrypted form of the secret key is known and of limited length, why would the following brute force technique fail:

(1) In advance, create a table for each possible public key. For a public key of length N, the elements of this table consist of every possible encrypted string (i.e., every possible secret key encipherment) generatable from that key using the known key encryption algorithm, regarded as binary numbers and arranged in binary order.

(2) Use the known public key to identify the applicable table.

(3) Reading the encrypted secret key as a binary number, look up the corresponding plaintext secret key in the applicable table.

(4) Use the decrypted secret key to decrypt the message text using the known app algorithm.

Typically you would not use a different secret key for each message as you'd have to use the alternate method to deliver each. For security's sake you really only need to deliver it one time and it's up to you on when you want your trust to expire, so to speak.



Not quite sure what you are asking, and I'm not too intimately familiar with how they work on that level.




This approach is called a rainbow table and has been used with some degree of success with passwords. If you have an unlimited amount of characters there is essentially an unlimited amount of variations, thusly making it impossible to have them all. Even then, with short passwords this really relies on common passwords to work effectively.

With much longer strings being encrypted the amount of variations is itself a mathematical problem of scale that renders this impossible (for practical purposes) barring breakthroughs in computing or mathematics as alluded to earlier in the thread.

Actually, there are several ways to do this. It is a balance between speed (time it takes to encrypt and decrypt) and security. There are tricks to get more speed that use public key encryption to send a random number that is then used to encrypt the message with a more efficient algorithm. Generally this is done behind the scenes. A programmer might choose the underlying algorithm, or they might just pick the default.



There is an easy answer to this. The longer the public key and the longer the private key, the more possible combinations you have to try.

When we talk about the security, we talk about the number of possible answers. Then if you know how many answers the fastest computers currently available can try each second, you can calculate how long such a brute force attack will take.

Most people think an 128 bit key which lead to 3.4 x 10^38 (that's 34 followed by 37 zeros) possibilities a computer needs to try is plenty good enough. I have used 1024 bit keys professionally.

Of course people are always looking for shortcuts so they don't have to try every combination, and there are some cute hacks that have been used on encryption schemes.

First of all the public part of a public keys cipher is only used to transmit a non-public symmetric key that the two parties agree on between them.

It take too must resources even today to encode a whole message using public keys alone and no current cipher does so.

To try to made it clearer there are not one but two ciphers being used in public keys ciphers the first one used one of the systems known public key to transmit the non-public/private working key that will be used to encrypted and decrypted the message.

maxdancona wrote: "When we talk about the security, we talk about the number of possible answers. Then if you know how many answers the fastest computers currently available can try each second, you can calculate how long such a brute force attack will take."

I think this is exactly right, though we can also ask how many fast computers will be used in parallel, since this is a problem whose range can be split between multiple processors. Once the tables are compiled for a particular encryption app the tough work is finished and decryption can take place almost in real time for each new message.

maxdancona wrote: "Most people think an 128 bit key which lead to 3.4 x 10^38 (that's 34 followed by 37 zeros) possibilities a computer needs to try is plenty good enough. I have used 1024 bit keys professionally."

That's 2 to the 128th power alright, but I'm not sure there are that many possible keys in practice. For example, would a short random string followed by a bunch of zeroes be used if this is technically equivalent to the same string without the zeroes? What I mean is, if a key is 128 bits, wouldn't that have to include only binary strings of 128 bits, rather than all the much shorter numbers that can be expressed in 128 bits (but also with fewer than 128 bits)? I mean, 0, 1, 2, etc., are counted among those 3.4 times ten to the 38 possibilities, but (I assume) many or most partial string equivalents would be excluded for security reasons, by design, as potential keys. If we only have to consider keys that cannot be expressed in fewer than 128 bits, how many possibilities does that leave?

James Bamford's book Body of Secrets was written 15 years ago. In Chapter 14 he writes about then extant processor in memory (PIM) chips manufactured by the NSA's Special Processing Lab capable of performing a quadrillion (10 to the 15th) operations per second. He writes that "by 2005 the SRC (NSA's Supercomputer Research Center), with years of secret, highly specialized development accumulated, will likely be working with computers operating at exaflop speeds -- a quintillion operations a second -- and pushing for zettaflop and even yottaflop machines, capable of a septillion (10 to the 24th) operations a second."

Even with multiple supercomputers that fast, 2 to the 128 is still a lot of possibilities, though. If you had 100 yottaflop machines working simultaneously, it would still take more than 100,000 years to perform that many calculations, if I did the math correctly.

But as you point out, there can be short cuts. And I still need to know if in practice a 128 bit key actually implies 2 to the 128th power possibilities (per above).

Question: if your cellphone knows the unencrypted key, and it's connected to the Internet or some other data stream capable of being manipulated, wouldn't it be easier to upload something that scanned your phone's memory for the decrypted key?

No key will be excluded as that lesson was learn during WW2 when the Enigma machine would not allowed the output letter to be the same as the input letter resulting in a must must smaller search area then otherwise.

Next go to https://www.grc.com/haystack.htm and find out how long even the fastest computers that can be dream of will take with very long keys.

Hint it billions of times the current age of this universe.

BillRM wrote: "No key will be excluded as that lesson was learn during WW2 when the Enigma machine would not allowed the output letter to be the same as the input letter resulting in a must must smaller search area then otherwise."

Does everyone agree with BillRM about this -- that in (say) PGP every possible combination of 128 bits (in versions using a 128 bit key) is allowed? Would for example a symmetric shared secret key used to encrypt and decrypt the message, be set at all zeroes, or other highly redundant or reducible values, despite the simplified cryptanalysis this would permit for those attempting to decrypt the text of multiple messages encrypted with that key during a single session? And what about the choice of the 128 bit public key used to encrypt the secret key? Is it possible (or desirable) to generate a key pair with the required mathematical relationship, with one of the key pair set to zero?

You need and must have a good pseudo or even better a good random generator for your key selection so it could be anything in the key space allowed and checking for all zeros or whatever would be pointless as it is no more or no less likely then any other number in the key space and cause no weakness.

All you do for checking and not allowing keys with any given number of pattern is that you are reducing the key space with no gain by doing so.

Now if you are selecting primes keys not just keys then there are such things as bad/weak primes that need to be check for but once more that is another subject.

If you are talking about a prime public/private key pair a zero would not be allowed as it is not a prime less alone a large prime but for a symmetric key it is as good as any.

What exactly are you worried about PuzzledPerson?

If the NSA, with its hundred billion dollar budget, wants your secrets bad enough, they can put a bug in your home, or a hardware keyboard logger, or just pick you up secretly and take you to Guantanamo.

PGP is theoretically secure... but that only works if you do everything around it correctly. There are all sorts of ways for the NSA to attack PGP if you have done the slightest thing wrong in setting it up or using it. Bill has already talked about the random number problem. And if you make one little mistake that you don't even know you made, all your secrets are out (read about the Heartbleed bug if you want to know more about that).

The NSA types are whining about encryption because messages are being sent over the internet and covert teams to scrape information off of harddrives and video cards are expensive.

But if the NSA wants your information, they probably have some way of getting it.

I feel like we need to have more understanding and clear then I and others had been able to be at least to this point.

In public keys ciphers if I wish to send you a message I would encode not the message itself but first using your known public key but a random symmetric key that I had used to encode the message.

So when you received the message your software would first decode the part that contain the symmetric key using public key software and using that key it would then decode the complete message.

In other word it is a two parts process first using public key software to send the working key that in turn is used to decode the message.

Well yes and no as if NSA decided that as all cost they need your communications yes they are likely to be able to do so one way of another.

The problem is a fair number an and ever growing number of people are encrypting their internet traffic and there is no way that even NSA have the resource to go all out on all that traffic.