Does a public key absolutely need to be used to initiate an encrypted session?

Question

I am a software developer working on an application with the .NET platform. This application needs to provide a secure connection and encrypt all data between the client and the server. It is a standaone app that does not use a web browser and will be using a symmetrical key for the vast majority of the messages for best perfomance. Sessions can be expected to last between a few minutes to more than 24 hours. I am somewhat of a beginner when it comes to cryptography, but I have done some research.

From the research I have done, it appears that the current thinking is to use a public/private pair of keys to initiate the session. The first message sent by the client is encrypted with the public key, which is then decrypted by the server with a private key. In the first message to the server, a random symmetric session key is also transmitted which is then used for the rest of the session and then discarded after use. All this seems to be quite reasonable, but I do have some questions and concerns:

1. If public/private keys are to be used for the initial message, then should the same public client / server private key be used for all clients? Or, should each user have a separate public / private key? The application client would not need to maintain a private key for decrypting public key messages from the server since all further messages would be using symmetric encryption. My concern is that if only one key pair is used and someone does somehow manage to figure out that private 2048-bit key, then all the users of the application would be vulnerable...

2. From research I have done, it looks like some are recommending that nothing less than 2048 bit RSA keys should be used. If this application takes off, it could easily have 500,000 users within 5 years or so. Generating public/private 2048 bit key pairs takes some time (if you know how much time it takes - please let me know along with the hardware) and with 500,000 users, could cause some serious time delays in the future. Imagine a scenario where all of the 500,000 key pairs need to be regenerated. How long woutd that take? So, I'm wondering if there is another way of initiating the session that is just as good and circumvents the need to use public / private key pairs to initiate the session...

3. The application will have a website assocatiated with it that will allow users to register with a user id and password. What I am thinking about doing is to apply the password to generate the initial symmetric key that would be used to encrypt the first message to the server. The random session key would still be transmitted and used after the first message. To identify the user, a unique user token would be supplied to the client installation upon registration that would be appended to the first encrypted message and the user token would not be encrypted. Once the server receives the first message, it looks up the token and obtains the password. The symmetric key for that password is then generated on the server exactly the same way as was done on the client. The .NET platform provides a way to generate keys from a password with the PasswordDeriveBytes class. So, this approach seems like it will work, but I am not an expert on this topic and would appreciate hearing from others who are more experienced and are in a position to point out anything that I might be missing...

4. I have also researched symmetric ciphers. Since performance is an issue as well as security, I am thinking of going with CAST-128 instead of Rijndael which is now being used by just about everyone as the AES. The reason for this is because according to some benchmarks, CAST-128 is faster on Windows systems. Also, from a security point of view, I would much prefer to use a much less popular cipher than one that is being used by the US, other governments, and most companies. There is much more interest in breaking Rijndael than CAST-128 which is only being used by the Canadian govt and PGP.

Answer 1

I'm going to address your last sub-question, about CAST-128.

We used it in PGP because that was one of the better choices in 1997. It is no longer 1997. There is nothing wrong with it, but you can do a lot better these days.

CAST was even at the time a bit controversial, but we liked it. It was actually designed from a framework, and was one of the first attempts to develop a cipher framework. But at that time there were relatively few other choices. 3DES was (and is) slow, and there was lots of residual ire about DES. IDEA was patented and had inconsistent licensing. Blowfish was perceived to be slow, as well, but as it turns out, Blowfish is damned fast if you're using it on anything of size (i.e. when the slow key schedule is amortized).

These days, you should use AES, unless there's a good reason for some other reason. The reason you state (the US Government) is actually the wrong reason. Don't make crypto decisions based on politics. AES should be faster than CAST, on any decent implementation.

But more importantly, AES has a 16-byte block. All of the ciphers of the era when they had 8-byte blocks should be avoided because they have birthday attacks that matter at data lengths of relatively few gigabytes. (It's a ~50% chance at $2^{32}$ cipher blocks, and that's 32 GB.)

I hear you say, "but I'm not going to encrypt anything that large." You will, trust me. And even if you won't, that's again the wrong reason not to use AES. You want the 128-bit block.

If you really don't want to use AES, you should use Twofish or Serpent. They are IP-free finalists for AES and completely reasonable functions. If you still want to use something that's not AES, I recommend Threefish. It runs at twice the speed as software AES and has the advantage of a very large block size. You can find implementations of it via the Skein / Threefish web site. I'm using Werner Dittmann's implementation myself.

Answer 2

First recommendation: Don't invent your own protocol, but use an existing one. Use SSL/TLS, in the newest version possible if you don't have to provide downwards compatibility to existing clients. This will take care of most problems here, you simply put in a pair of plaintext data streams, and get a pair of encrypted streams. There are TLS implementations for most programming languages available, I'm quite sure that .NET has one, too.

TLS is quite flexible about the key exchange, authentication and encryption algorithms (bundled together as "cipher suite"). You'll have a public key for the server (usually with a certificate, whose subscribing key can already be embedded in the client application), and then use (for example) Diffie-Hellman key exchange with public-key authentication. There are also password-based key exchange algorithms, then you even don't need a public key (but client and server need some other way to first get the common password).

To your questions:

1. SSL/TLS works fine with a constant public key, not a different one per-client. Of course, if the private key gets leaked, all future connections are broken. If you did use the simple "encrypt session key by public key" model (RSA key exchange), also all past connections can be decrypted. Diffie-Hellman provides forward-secrecy, as the key is generated from random input of both sides, and the public key is only used for authentication.

   If you create a new key pair per-client, you'll need some way of the client to tell its name (or key ID or similar) before the actual connection.

2. I have no data about how long key generation nowadays takes, sorry. You also have to take care of having enough entropy for your keys. But as said before, there is no need to generate new keys regularly.

3. Instead of doing this yourself, have a look on the secure remote password protocol for generating a shared session key authenticated by a password. This is also available (standardized) as a key exchange method for TLS, though I'm not sure if it is supported by .NET's implementation.

4. You can use whatever cipher you want, but as said by others, AES is actually more likely to be secure than other ciphers. Also, modern processors have actually AES-instructions build in, which could make the performance difference quite small or even negative (i.e. AES-128 could be faster than CAST-128), if you use a library which actually can make use of these.

Answer 3

Also, from a security point of view, I would much prefer to use a much less popular cipher than one that is being used by the US, other governments, and most companies. There is much more interest in breaking Rijndael than CAST-128 which is only being used by the Canadian govt and PGP.

Since there is much more interest in breaking Rijndael, any flaws in it are much more likely to have already been discovered. In addition, any new breakthroughs are likely to be publicly disclosed with their relevant to Rijndael mentioned first. Thus you can have more confidence that Rijndael doesn't have hidden flaws than CAST-128 right now. And you can have more confidence that if cryptographic breakthroughs comprise the algorithm, you're more likely to find out the good way (by reading academic papers) than the bad way (by your application being compromised).

Also, say Rijndael is compromised. You followed the industry recommendation, and everyone's stuff will break. Customers will understand it's not your issue alone. If you pick CAST-128, the opposite situation is likely.

Also, if some bad person does compromise Rijndael, you're very unlikely to be the first thing they go after. With CAST-128, your odds of being the first target are much higher.

That said, CAST-128 is not a bad choice. There's nothing wrong with it, and it's sufficiently popular that any significant cryptographic breakthroughs would be published. Just understand that if you choose it, you will have to monitor the literature. It won't be front page news the way an AES issue would be.

Answer 4

Regard your sub question 4: Your argument is unfortunately flawed. A broken cipher algorithm becomes a security issue if both of the following conditions are true:

1. Your adversary knows how to break the algorithm,
2. You don't known that your adversary knows how to break the algorithm.

Suppose you are choosing between the two algorithms A and B. Both algorithms have the same alleged security strength, but not necessarily the same actual security strength (i.e. security strength after all known and unknown attacks have been accounted for). You don't know the actual security strength of either algorithm. However, algorithm A is more popular than algorithm B and receives more attention from researchers.

Does the relative popularity of algorithm A compare to algorithm B mean that the probability of 1 & 2 is higher for algorithm A?

The common sense opinion is that it is actually the other way around. The probability that 1 will be true without 2 being false is lower for a popular algorithm.

Answer 5

1) If your private key is compromised you are screwed, but this is pretty much always the case. I'd suggest one long term public key and securing that box to the highest degree.

However, if you're worried, the key to clients will be interesting. You could do TLS, and create a certificate authority that's stored on a usb key(I have a similiar setup it's a live encrypted os on the key, boot it and i can be fairly sure it's clean). Each time you need a new key, stIf you have belief that you've been compromised, set a revocation for the current certificate, and then sign a new certificate. This is arduous, but it means that someone needs to compromise the usb key in order to get the certificate.

Otherwise, I suggest doing short Term keys with the aforementioned solution if you don't want full TLS. I'm going to give the standard, please don't roll your own cryptographic protocol, but it appears to be too late. Have some signing authority sign a key and have them only be valid for a month or two at a time, each month boot up your usb key and then get anew signed certificate. This minimizes compromise damage, but does not come even close to negating it.

1A) On individual keys- This is dependent on your security model. Do you want to mutual authentication, maybe a PKI system? If so probably want each client to have their own certificate you give them during registration. If you just want to make sure the servers the server, then you only need for the server to have a public key.

2)
2048 Bit keys are most definitely necessary.
However, RSA is not, but some form of key agreement is. Based on my completely unscientific tests of running rsagen on my computer, it seems to take around a second or so, and we'll use this number for our calculations. You most likely do not need to calculate 500k keys, just one and have them connect to you. If you want to have ach key be calculated, what'd you do is have the client calculate the key, and submit it to the server for signing.

Secondly, if you use DH this number becomes a lot smaller, since a DH key is choose a number between 1 and 1 million, unlike RSA where the numbers must be prime, so there are only the numbers that work, on top of that you must run primality tests each time. Hence, diffie key generation is faster. All you probably really need is key exchange.

3) This is a horrible idea. Please abandon it, it's going to go wrong in ways you haven't even thought about yet, and are going to be to subtle for us to notice.

If your server is ever compromised, the person can now imitate clients forever, since they can derive the first request, have the authentication for it, and then pretty much are able to login forever. You're essentially storing your encryption keys as passwords in plaintext. Just have the server use a private key, hardcode a CA inside your application, or some public key and use that to set up an authenticated chat.

Most likely there's also some way that can manipulate it to be a MITM attack because you're doing something you didn't realize. Or maybe, just flipping a few bits and causing the encrypted message to be a new one that I already have the key for, or maybe replay between client and server or ...

4) Use AES

David schwartz sums it really well, and I'd say the same thing.

5) Though you didn't ask anything about this i'm going to say it anyway. MAC Everything. Have the key you setup create two subkeys, one to encrypt one to MAC, since most likely a bit flip to you is a really bad thing. Don't repeat IV's. Use cbc or ctr mode. I suggest the encrypt then mac model. If your set on doing this please atleast read this

Answer 6

To answer your question:

Does a public key absolutely need to be used to initiate an encrypted session?

No. It is sufficient that the client and the server have "a shared secret".

The server can encrypt a random (rotating session) key with the shared secret, and send it to the client. The client can then decrypt the key and send encrypted data to the server.

You used a shared secret as an alternative to a public key.

Answer 7

1.
This of course depends on how many logins you're getting. If logins are rare, it might even be no
slower to generate a new public key for each session. (It would certainly be better. Also see *)

2.
http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange,
although here too I would recommend using at least a 2048-bit prime. (also see *)

3.
No, no, no. That idea is only for if the server cannot send and cannot have sent anything to the client. Since the server will have previously been able to make an authenticated communication to the
client (preferably when providing the application, otherwise right before it receives the password)
and will be able to interact with the client, the server signs the transcript of the initiation
phase once that phase is otherwise complete, which the client verifies before proceeding.
(In particular, the client's verification occurs before anything that depends on the password.)

4.
(I have no clue here.)

*
The server needs to sign as described in my answer to 3.

Your number 3 also leaves me worried that, if nothing else, you are planning on using PasswordDeriveBytes. The server should store an scrypt value from the password, and not the password itself, a PasswordDeriveBytes value from the password, or anything else derived from the password.

Answer 8

Thanks to everyone for their suggestions.

I am convinced that going with CAST is not a good idea and will use AES-128 for time-limited (typically < 1 day and where the info has no value after disconnection) transactions where performance is more important and use AES-256 for financial transactions where longer term security is more important.

In order to see how fast a public/private key pair can be created (twice - one for the server and one for the client), the public key exported and then imported into the client, the data encrypted with the public key and then decrypted with the private key, I have written a little benchmark test program in C# to see how quickly this will take for both 1024 bit and 2048 bit keys:

  static void Main()
  {
     // This is a console project.
     try
     {
        //Create a UnicodeEncoder to convert between byte array and string.
        UnicodeEncoding ByteConverter = new UnicodeEncoding();

        DateTime StartTime, EndTime;
        TimeSpan DeltaTime;
        StartTime = DateTime.Now;
        //
        RSASpeedTest(100, 1024);
        EndTime = DateTime.Now;
        DeltaTime = EndTime - StartTime;
        //Display the time it took to run the test. 
        Console.WriteLine("  Time for 1024 bit key = " + DeltaTime.ToString());
        Console.ReadKey();
        //
        StartTime = DateTime.Now;
        RSASpeedTest(100, 2048);
        EndTime = DateTime.Now;
        DeltaTime = EndTime - StartTime;
        //Display the time it took to run the test. 
        Console.WriteLine("  Time for 2048 bit key = " + DeltaTime.ToString());
        Console.ReadKey();
     }
     catch (Exception E)
     {
        // If an excpetion occurred, then display it to the user.
        Console.WriteLine("Main - exception thrown.  Msg = " + E.Message);
        Console.ReadKey();
     }
  }

  static public void RSASpeedTest(int TestCount, int KeySize)
  {
     // This method tests how quickly the following can be done:
     // 1. Create a public / private key pair for the client and server.
     // 2. Export and import a public key.
     // 3. Encrypt the data using the public key.
     // 4. Decrypt the data using the private key.
     // The above steps are tested TestCount number of times.
     int Loop;
     try
     {
        UnicodeEncoding ByteConverter = new UnicodeEncoding();
        byte[] dataToEncrypt = ByteConverter.GetBytes("Data to Encrypt");
        byte[] encryptedData;
        byte[] decryptedData;

        for (Loop = 0; Loop < TestCount; Loop++)
        {
           RSACryptoServiceProvider RSA = new RSACryptoServiceProvider(KeySize);
           RSACryptoServiceProvider RSA2 = new RSACryptoServiceProvider(KeySize);
           // The next line of code shows how to export a public key from the public/private key pair.
           byte[] CspBlob = RSA.ExportCspBlob(false);
           // The next line of code shows how to import the public key into the object.
           RSA2.ImportCspBlob(CspBlob);
           // The next line of code shows how to move the public and private keys into a string.
           // String S = RSA.ToXmlString(true);
           // The next line of code shows how to move just the public key into a string.
           // String S1 = RSA2.ToXmlString(false);
           // The next line of code shows a different way of getting the public key data.
           // RSAParameters RSAParams = RSA.ExportParameters(false);
           // The next line of code encrypts the data with the public key.
           encryptedData = RSA2.Encrypt(dataToEncrypt, false);
           // The next line of code decrypts the data with the private key.
           decryptedData = RSA.Decrypt(encryptedData, false);
        }
     }
     catch (Exception E)
     {
        // If an excpetion occurred, then display it to the user.
        Console.WriteLine("RSASpeedTest - exception thrown.  Msg = " + E.Message);
        Console.ReadKey();
     }
  }

On my computer, which uses a Pentium I7 950 running at around 3.5 ghz with Win 7 and 2000 ghz memory, the 1024 bit key test took just over 10 seconds. So, since the test is run 100 times it takes roughly 1/10 of a second on average for it to complete just once. The 2048 bit test is just over 2.6 times slower. The test makes use of the .NET Framework 3.5 and is single threaded.

So, what I am thinking of doing is not storing any keys at all. Instead, all keys will be generated on the fly since the tests show that creating the keys can be done fairly quickly. For 99%+ of most transactions for my application, a 1024 bit key can be used since there is no value to the data after the user terminates the connection. The connection will not usually last more than 24 hours and certainly not more than 72 hours. For financial transactions, then a 2048 bit key will be used to deliver the 256 bit AES symmetric key.