3
   

Encryption, NSA, and terrorism

 
 
Reply Wed 9 Dec, 2015 04:51 pm
Just saw the FBI director complaining that one of the San Bernardino shooters had used a cellphone 109 times to exchange messages with someone overseas, but that they don't know what was said because the messages were encrypted. Maybe I'm behind the times as regards encryption software, but it seems surprising that the NSA, with supercomputers capable of petaflop speeds and massive parallel processing, can be thwarted by a simple cellphone app.

Anyway, this started me thinking about how encryption is only as strong as the weakest link in the communication chain. My question is this:

If two cellphones are using a common messaging encryption app, the receiving app needs some way to know what the encryption key for that particular message is so that it can decrypt the message. With an app I would expect the key to be a long pseudo-random string and for the process of key choice to be completely automated.

If the key is determined by the sending device, how is the receiving device informed of the key value (or of a hash code which allows it to determine the key value)? If instead the key is provided to both devices by a common cloud server, then how is the key provided?

If the encryption app is either commercial or open source, why wouldn't it be possible for someone with the resources of the NSA to compile a table of hash codes (or whatever) so that when the envelope metadata (or whatever) telling the receiving device which key to use is sent to that device, it can use the same algorithm as the receiving app to decrypt the message?

I guess what I'm asking is: if the algorithm used by the receiver is known, and the key for a particular message (or a code allowing that key to be reconstructed by an algorithm that is also known) must be sent to the receiver via a communications stream that is already under surveillance (else neither the fact of encrypted messages nor their encrypted content would be known), then why couldn't a third party decrypt the message?

Put another way: both the sending and receiving apps must somehow be synchronized, cryptographically speaking. That requires a synch signal, either sent by one device to the other, or sent to both devices by an outside device in communication with both. If that synch signal is intercepted by a third party like the NSA, why couldn't it, combined with knowledge of the app software code or encryption algorithm, allow decryption?

Ciphers like Enigma were comparatively secure only because the keys or key change procedures were established manually (i.e. outside the communication channel). I don't see that being the case with fully automated cellphone encryption apps.
 
maxdancona
 
  3  
Reply Wed 9 Dec, 2015 05:15 pm
@puzzledperson,
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.
maxdancona
 
  2  
Reply Wed 9 Dec, 2015 05:19 pm
@maxdancona,
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.

Robert Gentel
 
  1  
Reply Wed 9 Dec, 2015 05:20 pm
@puzzledperson,
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.
maxdancona
 
  2  
Reply Wed 9 Dec, 2015 05:24 pm
@maxdancona,
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.
puzzledperson
 
  1  
Reply Wed 9 Dec, 2015 05:31 pm
@puzzledperson,
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.
0 Replies
 
BillRM
 
  1  
Reply Wed 9 Dec, 2015 05:35 pm
@maxdancona,
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
0 Replies
 
BillRM
 
  1  
Reply Wed 9 Dec, 2015 05:35 pm
@maxdancona,
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
0 Replies
 
puzzledperson
 
  1  
Reply Wed 9 Dec, 2015 07:32 pm
@Robert Gentel,
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.

Robert Gentel
 
  1  
Reply Wed 9 Dec, 2015 07:42 pm
@puzzledperson,
puzzledperson wrote:
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?


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.

Quote:
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?


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


Quote:
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.


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.
0 Replies
 
maxdancona
 
  1  
Reply Wed 9 Dec, 2015 08:03 pm
@puzzledperson,
Quote:
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?


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.

Quote:
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:


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.

BillRM
 
  1  
Reply Wed 9 Dec, 2015 08:24 pm
@puzzledperson,
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.


0 Replies
 
puzzledperson
 
  1  
Reply Thu 10 Dec, 2015 01:17 am
@maxdancona,
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?
BillRM
 
  1  
Reply Thu 10 Dec, 2015 01:39 am
@puzzledperson,
Quote:
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?


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.
puzzledperson
 
  1  
Reply Thu 10 Dec, 2015 04:53 am
@BillRM,
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?

BillRM
 
  1  
Reply Thu 10 Dec, 2015 05:05 am
@puzzledperson,
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.
BillRM
 
  1  
Reply Thu 10 Dec, 2015 07:22 am
@puzzledperson,
Quote:
Is it possible (or desirable) to generate a key pair with the required mathematical relationship, with one of the key pair set to zero?


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.
maxdancona
 
  1  
Reply Thu 10 Dec, 2015 07:44 am
@puzzledperson,
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.

BillRM
 
  1  
Reply Thu 10 Dec, 2015 07:48 am
@BillRM,
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.
0 Replies
 
BillRM
 
  1  
Reply Thu 10 Dec, 2015 07:54 am
@maxdancona,
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.
0 Replies
 
 

Related Topics

Clone of Micosoft Office - Question by Advocate
Do You Turn Off Your Computer at Night? - Discussion by Phoenix32890
The "Death" of the Computer Mouse - Discussion by Phoenix32890
Windows 10... - Discussion by Region Philbis
Surface Pro 3: What do you think? - Question by neologist
Windows 8 tips thread - Discussion by Wilso
GOOGLE CHROME - Question by Setanta
.Net and Firefox... - Discussion by gungasnake
Hacking a computer and remote access - Discussion by trying2learn
 
  1. Forums
  2. » Encryption, NSA, and terrorism
Copyright © 2019 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 0.04 seconds on 12/07/2019 at 11:50:26