Public Key Cryptography for Boy Scouts

Let’s imagine that someone (let’s call her Sophie – actually, we can use any desired name, but I would be pleased to use a name of my favorite actress – hope, she would be too :)) is willing to send you something quite sensitive – let it be an old map of the treasure island where captain Flint has hidden his chest full of golden coins. As a true woman, Sophie wishes to ask you – her brave knight – to sail to that island, fight the dragon and bring the treasure to her (I am not sure if there actually was a dragon, but the girls do like that sort of things, so we imagine that the monster is there :)).

However, there’s one problem: a river stands between you and Sophie. The only way for her to send you a map is to use the services of a boat driven by an old one-legged guy with a parrot on his shoulder, and this guy appears not to be that honest. The boat is quite small for two, so neither she nor you can accompany the map in its transfer across the river.

As you are a smart guy, a real knight, you quickly find a solution. Sophie should take a box with a lock, put a map there, close the lock and send the box to you via the boat. Once the box is here, you’ll open the lock and get the map. A great idea, isn’t it? Well, let’s try. Sophie finds the appropriate box, locks it with a key and calls the boat. But… wait a minute. You need the key to open the lock. But the key is on Sophie’s side, and obviously she cannot use the boat to transfer it to you.

You are sitting on the shore and thinking. You understand that Sophie should be able to close the lock and you should be able to open it, but the key should never be transferred across the river. And suddenly you get it! The solution is really simple. You will take a box with a self-closing lock, similar to the one shown on the picture at the left, and send the box to Sophie with an open lock, leaving the key in your pocket. Once Sophie receives the box, she puts the map there and pushes down the shackle. Now she can freely send the box with that strange guy, as she knows that he can’t open the lock without having a key.

An attentive reader may propose the following solution: let Sophie lock the box with a key and send the box with a boat. When the box arrives to the other side, let she call the boat once again and ask the guy to transfer the key. Well, yes, this solution will work (actually, it even suits one of the core principles of cryptography – never store a key along with encrypted data). However, you will not be able to use the same box or lock again, and who knows how many old maps Sophie is going to find? Besides, this solution is not applicable in the digital world, where an old one-legged guy can always do a copy of whatever he transfers and unlock the box once he gets the key.

The above story describes a method that cryptographers call public key (or asymmetric) encryption. In every public key cryptosystem a key consists of two halves called public key and private key. Public key is publicly available, while a private one should be kept in a safe place by its owner. Everyone can encrypt data with a public key, but only the one who possesses the private key will be able to decrypt it. In our case, the open lock is a public key, and the key in the pocket is a private key.

Let’s consider another situation. You and Sophie wish to send letters to each other across the river, and, as you are really a romantic couple, the number of letters is expected to be quite big. Of course, you can use the above scheme with a box with a self-closing lock. However, there will appear two disadvantages of such a scheme applied to our romantic task. First, you will need two boxes (a first one to transfer letters from Sophie to you and a second one – from you to Sophie). Second, a boat will have to do twice more trips across the river than the actual number of letters transferred (there is an extra “dummy” transfer of an empty open box for each letter). This is not critical if the transfers are free of charge, but I am pretty sure that the guy’s parrot eats plenty of corn and that’s why the transfers are performed on a paid basis.

Now that you are not a greenhorn in public key encryption, a reasonable idea comes to your mind quite fast. You will take a box with a lock that can be both opened and closed with the same key (see the picture at the left), and two identical keys that fit it. Then you will ask Sophie to send you an empty box with an open self-closing lock, exactly the same as you used to transfer the map. Once the box is here, you will put one of the two keys inside, close the lock and send it back to your girlfriend. She will open the box using her key and get the key that you’ve put inside. Now – voila - you have a box with a lock and two keys that fit that lock, one on your side and another on Sophie’s side, and you can start exchanging the letters using this box. A box with a self-closing lock is not needed anymore, so Sophie can put it aside.

The second case is a classic key exchange example. A general key exchange method allows two (or more) parties to set up a shared key by communicating over insecure data channel. A lot of key exchange methods are based on public key cryptosystems. The above case is based on public key encryption scheme; however, underlying encryption algorithm is not a requirement though. In modern cryptography key exchange algorithms serve a very important task of sharing a symmetric cipher key between peers using extraordinary strength provided by the asymmetric algorithms.

To be continued...

Don't hide your keys in the flower pot

“Encryption” word sounds like a spell for many people. “If my data is encrypted, no one can read it”. Thinking that way is a fatal flaw. No one can read it if the key is in safe place.

Many people believe that encryption itself guarantees the complete protection of the data. They say: “the data that is used by our application is encrypted with industry-standard AES algorithm with 256 bit key. Recent research show that in order to decrypt such data a hacker needs to spend a transcendental amount of time, and that’s why our customers should not worry about their secrets”.

It is not completely so.

Modern cryptosystems are designed in the way that the security of the system is delegated to the secret key being used. Although the internals of the underlying cryptographic algorithms are well known, the algorithms guarantee that it is impossible for an eavesdropper to decrypt the encrypted data unless he knows the secret key (to be exact, it is possible for him to decrypt the data, but only by trying all the possible keys one by one; such a big number of keys to try leads to the “transcendental amount of time” referenced by the people from the paragraph above).

So what's the obvious consequence? A hacker will do his best to avoid checking all the keys. In particular, he will try to get the key or some information about the key by other means. That’s why a lack of care about preserving the secrecy of the secret key can lead to a compromise of the entire system. And neither bit of 256 of AES key will help you.

We often face with situations where a secret key is simply hard-coded into the application’s source code. Naturally, such an approach is not suitable. Leaving aside the fact that different data are encrypted with the same key in this case, the key itself is easily accessible to the hacker. He just has to browse the application’s binary code and to extract all the constant values from it. An intermediate hacker will spent no more than five minutes to get the key.

Avoid hard-coding the secret key into the application. If your application needs to encrypt user-specific data, ask user to provide a password and then use this password to generate a strong secret key. To decrypt the data, ask user for a password and use the same procedure to obtain the decryption key. The secret key in this case is nowhere stored in explicit form (except the user’s head), and this fact seriously complicates retrieving it by a hacker.

If due to the certain reasons it is not possible to use password-based secret key generation approach, secret key protection should be implemented in the other ways. In particular, a task of key protection can be delegated to built-in functionality of an operating system. Windows provides several ways for secure storing secret data, such as DPAPI (Data Protection API), LSA, protected registry sections. Use these functions if you need to store a secret key inside an operating system. They have been built by gurus in the field of information security and provide much greater protection than the one you will be able to implement yourself. Besides, they are ready-to-use – and aren’t yours?

Even if OS functionality is not available for you (such cases are rare, but nevertheless possible), never store a secret key in plain form. Instead, generate it on the fly using complex and incomprehensible functions. Of course, this will not stop an inquisitive hacker (he will just use other instruments, such as debugger, in this case), but will prevent the secret key from being disclosed by script kiddies and beginner hackers.

The conclusion. The strongest cryptographic algorithm is useless if you do not care about the proper protection of the secret key. Don't hide your keys in the flower pot.