The not so cryptic explanation of encryption: symmetric keys, asymmetric keys, hashing and PKI

This month 80 years ago the first digital computer was taken into operation at Bletchley Park Estate, 6 days before the D-Day landings on the beaches of Normandy started. The computer named Colossus was used to break the Lorenz cypher, a cryptographic system used by the higher echelons of the German military and not, as you sometimes read, for breaking the Enigma code.

Okay, must admit, it was the Colossus MK 2 as the first iteration of the machine was already available in December of 1943. Even though that first machine was a couple of months earlier, the introduction of the MK 2 and its 80 year anniversary is enough reason for me to use this addition of this newsletter to dive deeper into the complexities of cryptography and/or encryption.

Always wanted to know a little more? then by all means please read on. But I must warn you, this addition is a little longer and a little more complex then any of the previous additions in this newsletter, so bare with me.

Definitions

Before you can read on, there are a couple of terms I need to clarify. This is because they are usually used either interchangeably or wrongly. I want to make sure we are on the same page before explaining more. For this section I will use the definitions provided in the ISACA Interactive Glossary . Any definitions not discussed here but which are relevant, will be included later on in this addition.

What is cryptography

The definition given is:

"The study of mathematical techniques related to aspects of information security, such as confidentiality, data integrity, entity authentication and data origin authentication"

Basically this is the study to create, evaluate and validate cryptographic algorithms or as the correct term is encryption algorithms which is defined as:

"A mathematically based function or calculation that encrypts/decrypts data, including block or stream ciphers"

What is encryption

The definition given is: "The process of taking an unencrypted message (plaintext), applying a mathematical function to it (encryption algorithm with a key) and producing an encrypted message (ciphertext)"

Basically everything I will discuss in this addition has to do with encryption, encryption algorithms and keys. How these were ever designed, cryptography, is mostly left out.

Cypher vs. cleartext

If you can read it, it's cleartext and if you can't because encryption was used its called cyphertext.

This is important to understand as it will explain in basic how encryption works.

Encryption and decryption

Now we know what cypher- and cleartext is, this is the final bit I need to discuss with you.

When encrypting something an encryption algorithm and a key is used to change something in cleartext to cyphertext.

When decrypting something the exact opposite is done so using that same algorithm and key to go from cyphertext to cleartext.

A brief history of cryptography

its almost impossible to discuss the entire history of anything related to encryption and their historical perspective. So I decided to pick out a couple of the more interesting elements that also underline the usefulness of encryption and its weaknesses as well.

There is lots more to discover regarding historical encryption methods and the use of encryption.

The Scytale cypher

If you read this and ever had a training course from me with explanation of using a rod or circular disk to wrap a piece of parchment around it, write on it and send it off without the rod or disk and I called it a Caesar cypher then I must apologise as that was incorrect, see the next subsection for the correct description.

The method is actually called the Scytale or Skytale method and uses 2 rods or discs with equal width, one stays with one sender or recipient and the other party takes away the second rod.

When a text is written on the parchment wound around the rod, the text takes on a particular shape on the parchment. Unwind it and that shape is distorted, making the message unreadable. When you received a message you would take your scytale and rewind the parchment around it to restore the spacing between the text written on it to be abel to read it properly.

The encryption key here is the width of the or rod or disc used. Do note we are talking about the time of the old Greek and Spartans when this system was allegedly in use.

The Caesar cypher

A bit more modern system was invented by Julius Caesar , who used a system which rotated the letters clockwise or counter clockwise in the roman alphabet to encrypt his private communication. This system works by shifting the letter that is written down either left or right by N number of places in the alphabet.

So if we use a left shift of 3, then a D becomes an A, and M becomes a J and an A becomes an X.

More modern encryption algorithms still use this shift method, but not just by itself anymore.

A more recent usage of this system was the ROT 13 or rotate 13 method, which was widely used to obfuscate plot spoiler texts when publishing a joke online or as part of reviews of new episodes of popular TV series to hide the plot from people who had not watched it yet. As the method was well known, even published in the post that it was used, it didn't serve to encrypt anymore. But then again that wasn't the intention either.

The enigma cypher machine

Although the Enigma has gained most if not all of its notoriety because of its extensive usage by the German military, it was actually an invention that was already 20 years old when the WWII started and was used a lot in the private sector for securing company communication during the 1920s and 1930s the world over.

This time had also seen the massive growth of radio communication, in morse code, so a method to secure these messages was a welcome addition.

The system uses a variation on the Caesar cypher in that it doesn't simply shift a number of characters to the left or right but it substitutes them in a given order. Each disc used in the Enigma machine had a different substitution pattern and combining different discs together gave a unique pattern, this combined with the starting position of the of the discs gave even more unique combinations. The more discs, the more complex the substitutions could become.

Some machines also included a switch board on the front wich could even change more electrical connections and paths between the typing keyboard and the lamps on the machine. Type in one letter and the corresponding lamp with light up after all substiutions were completed in an electrical circuit.

The system was already broken by Polish mathematicians in 1932 who subsequently trained French and British staff in 1939 to achieve similar results, even providing the hardware to assist them in the endeavour.

Although the Germans tried to make the system more complicated by creating extra discs which could be used to variate the setup of the machine, they also made mistakes by e.g. not changing the plug board too often or not at all which decreased the number of permutations possible.

British code breakers broke the new improvements February 1941. They obviously were helped by code books, dialy setup instructions for the Enigma machines, and the machines themselves which were obtained during military operations.

The Lorenz cypher and Colossus

The Lorenz cypher , actually it uses the Vernam cypher as Lorenz designed the machine and not the encryption method, was used during the war by Germanys high command for communication across europe.

The Vernam cypher uses the XOR function where 2 bits are compared and if they are the same you get a 0 and if they are different you get a 1. So 0 XOR 0 is 0 and 0 XOR 1 is 1.

This method is still widely used in encryption algorithms today.

Two tapes would run together, one with the message and one with the key being used for that message. At the receiving end a similar setup would run the cyphertext received message with the similar key strip and thus be able to generate the original cleartext message.

Code breaking

The system is as good as its operators. One of the mistakes made was a station sending a message, the receiving station didn't receive it completely so ask for a re-transmition, which was done with a similar message being a bit shorter because of some small alterations. Two mistakes were made: first of all the same encryption key was used to re-transmit and secondly the request to do so actually was transmitted unencrypted so the British knew what was going on.

Colossus

The best way to find not only the setting of the Lorenz machine, 12 discs with each their own setting per message, and then decrypting the actual message by hand or by machines that didn't work very reliable, was a tidious process. Made more difficult by the Germans actually also improving the Lorenz machines over time too.

In December 1943 the first version of Colossus (MK1 ) was build and shown to be more reliable and faster. Instead of 2 tapes it used only one tape, so no tape synchronisation issues, and used valves (tubes if you will) to electro mechanically calculate what the correct key would be to be able to decypher the message that was received.

This month 80 years ago the MK 2 version of the Colossus machine was taken into production, twice as fast as the mark I it greatly helped in the war effort. In the end 6 of them were build and its design formed the basis for later commercial versions in the late 1940s and and 1950s.

What is quantum cryptography

In quantum computing so-called Q-bits are used to make very fast calculations. The trouble is, if or when this is ever possible in significant computing power, that most of our current encryption algorithms would become useless.

The problem, if you will, is that if you want to break any of the current widely used algorithms, you would have to brute-force them by calculating every key possible and then trying them all in turn to see which one fits and can decrypt the wanted message. With most algorithms this will take thousands of years to achieve, quantum computes are allegedly able to do this in a much shorter timeframe, some say seconds to hours but all will depend on how much computing power the machine actually has.

This means we need to act now to replace vulnerable algorithms with those that can withstand such an attack. The fact of the matter is though, this isn't easy as Microsoft along with multiple universities, Amazon, Infosec Global and Texas Instruments showed a couple of years ago with a contender in a NIST quantum encryption algorithm competition (National Institute of Standards) being broken in under an hour by a machine with one CPU core being over a decade old. Something even a basic quantum computer probably would do in mere seconds or even faster.

Encryption basics

A couple of years back, when teaching a CISA certification course (Certified Information Systems Auditor) I had to describe the concepts in this section to 4 students. One of them had an information security background but the other three were accountants with almost no background in the field. Trying to explain computer hardware, the 7 layer OSI model (network design which is still taught but hardly used anymore) and indeed encryption basics as well was somewhat challenging.

Unless the people from that course contradict me in the comments, I reasonably succeeded. The method used then will be the basis of the explanation in this section.

As is usual in any encryption textbook we will use Alice and Bob who want to communicate securely yet Eve trying to make that impossible (evil Eve if you will).

What are symmetric algorithms?

Encryption algorithms are available in 2 variants, symmetric and asymmetric, this has mostly to do with the key or keys being used for encryption and decryption. Lets deal with the symmetric variant first.

If Alice wants to communicate with Bob, they need a secret key to do so. That key is the same for both encryption and decryption, hence the symmetric nature of the system.

If Eve is able to obtain that secret key, she can both read the messages Alice and Bob exchange but she can also change them and therefore screw with their communication.

Let's see it another way: the key to lock and unlock your front door is a form of secret key, its both used to lock and unlock your door similarly to encrypting and decrypting the messages Alice and Bob exchange.

And similarly to the symmetric system, if somebody has the key then they can enter and leave your house at will as well.

The biggest challenge is: how do Alice and Bob make sure they both have the same secret key without Eve being able to eavesdrop that key exchange? I will come back to that in a bit.

What are asymmetric algorithms?

But lets discuss the other variant, the asymmetric system first.

If Alice wants to communicate with Bob then she needs the public key from Bob and the other way round as well. In an asymmetric system both Alice and Bob have a key pair with a public and a private key that are mathematically linked together.

Lets see it another way and look at the front door example used above which was symmetric, right? Now if we had 2 locks on that door with two related keys, one key would be used to lock it and then only the other key would be able to unlock it again. This works both ways.

Another analogy: think of a small box, the box has two locks on it, if you put a message in and then lock the box with key 1 in lock 1 then only key 2 with lock 2 can unlock the box again and retrieve the message that was put in. And yes vice versa too.

The reason why I named them key 1 and key 2 here is to not confuse you with the public and private key as they are designated in the asymmetric system. But lets tackle that too.

The key names are really what it says on the tin, the public key is indeed public and meant to be public. The private key is required to be kept private as that key is the only key that can unlock any message encrypted with the public key.

And the other way round? Indeed, but that's not used to keep messages secret as anybody can have that public key, correct? When what is it used for? Digital signatures.

With the asymmetric system Alice and Bob have no issues exchanging keys as they exchange their public keys and so if evil eve intercepts them she still can't read their messages. Evil Eve could screw up the key exchange though and play man-in-the-middle attack (MitN) or WitM if you will because their is no way for Alice nor Bob to verify the key they received is from the other person.

What is hashing?

Hashing algorithms are a different kettle of fish, its not really encryption but its important to grasp the concept if you want to understand how public key infrastructure works and when public and private keys are used for digital signatures as noted above.

The biggest advantages of a hashing algorithm are:

• From the outcome of the hash function, the original input can never be retrieved;
• If you put in exactly the same value over and over again, the same result is calculated every time.

We can't speak of encryption as there is no way to decrypt the output again. Its cryptography though but lets leave that for now.

A hash value is always the same for the same input, change a couple of bits and the hash value will change as well.

Okay, not entirely, it really depends on the length of the hash value. The shorter it is, the bigger the chance is you could calculate a collision value, a different input that leads to the same hash value output.

The birthday problem

Put X number of people in a room and depending on the size of the group, the chance is that two persons have the same birthdate, without the birth year that is.

Interestingly enough, the group needs to contain only 23 persons for the chance to be 50%. And yes, this is indeed true.

This problem can be turned into an attack where there is a probability to calculate a collision hash value, this is called the birthday attack . The larger the hash value, the more difficult this attack becomes. This is one of the reasons why hashing algorithms like MD5 and SHA 1 are no longer used, this amongst other security issues.

Some usage scenarios

Hashing is used for a variety of scenarios, here are a couple common once:

• Digital signatures (e.g. for certificates)
• Securely storing and comparing passwords;
• Make sure downloaded files, usually software, are not changed;
• Detecting known CSAM (child sexual abuse material) automatically;
• Used for the integrity within blockchain systems and crypto currencies.

Hashing therefore has a very important role to play in the digital economy, specially when the European Union ends up implementing the Digital Euro but also as part of the underlying digital identity systems currently in development under the eIDAS 2.0 regulation.

The key distribution problem

As already hinted at, both symmetric and asymmetric encryption have a key distribution problem.

In the symmetric system evil Eve can read and screw up the communication if Alice and Bob exchange the secret or shared key in a way that Eve can intercept it.

With the asymmetric system evil Eve can only screw up the exchange of the public keys, she needs to be able to intercept both public keys from Alice and Bob and replace both with her own public key. As long as she stays in the loop of all communications between Alice and Bob, she can again read and screw with their communications and both Alice and Bob will be none the wiser.

Several protocols have been designed to mitigate these risks. Besides that, it seems the easiest to make sure that Alice and Bob exchange the keys via another communication channel or possibly offline. It will greatly depend on the circumstances if this is possible, even more difficult if Alice and Bob actually don't know each other yet.

What is public key infrastructure (PKI)?

The name is actually a bit misleading as its the private keys in an asymmetric key pair that are the real backbone of the system.

So what is it? PKI is a method to obtain digital certificates from a trusted third party or TTP. The certificate is signed by the TTP with which they effectively tell you they have confirmed who the owner is of a specific private key, the certificate will hold some identity information of the owner of that private key as well as the corresponding public key. Other information that is included are the signature of the TTP of course, the date the certificate becomes valid and the expiry date as well plus some information on the allowed usage, algorithms used and who the party is who signed the certificate.

A public key infrastructure setup typically contains the following elements:

• Registration authority (RA);
• Certificate Authority (CA);
• Archiving Service;
• CRL provider (Certificate Revocation List) or
• OCSP service (Online Certificate Status Protocol).

Certificate issuance

The basic procedure works as follows:

1. you request a certificate with the RA by providing a Certificate Signing request (CRS) which proves you own the private key, the corresponding public key and requested identity information;
2. The RA will verify the CRS, verify your identity and when all steps are completed hand if off to the CA;
3. The CA will format the certificate and sign the certificate with its own public key;
4. When done, the CA will issue the certificate back to you.

The last step can also be executed by the RA, this depends on how the system is setup but has no effect on the overal operation.

Key distribution

When Alice and Bob now exchange public keys, they can either directly provide the certificate as well or either of them can request the certificate from the PKI service as they keep them in the archive service. Now evil Eve can try as hard as she can but there is no way she can pull off the trickery as discussed before because Alice can verify the key belongs to Bob and vice versa, all because that trusted third party as verified and signed off on the fact that the specific key belongs to the other party. If Eve exchanges the key and certificate, unless she was able to spoof the system, the certificate will show her identity information and not that of Alice or Bob so they know the game is up for Eve.

CRL and OCSP

The entire system is based on two things: trust in that third verifying party and the private key actually staying private or under sole control of Alice or Bob respectively.

But we all know security isn't 100% fool prove so that private key can be compromised. When that happens either Alice or Bob needs to notify the TTP immediately. The TTP will then revoke the certificate and publish the fact that they have done so in either a certificate revocation list or via the OCSP protocol, both can be queried to see if a certificate is still valid or not. Not doing so can lead to security issues btw.

How does encrypted email work?

Lets bring it all together in a practical example, the usage of e-mail encryption.

Why e-mail encryption? Because it uses asymmetric, symmetric and hashing algorithms to accomplish secure communications and certificates to aid in the key exchange, as discussed above. Here is the step-by-step scenario:

1. A secret (symmetric) key is generated when the message needs to be send, called the message key;
2. The message is encrypted with the message key;
3. The encrypted message is now hashed so the receiving party can check it hasn't been tampered with;
4. The public key (asymmetric) of the recipient is obtained and the certificate is checked for validity and correctness (not expired or revoked and the name and e-mail address matching the recipient);
5. Now the public key of the receiving party is used to encrypt both the secret key and the hash value;
6. The encrypted message and encrypted key + hash value are combined and send to the recipient.

Lets asume Alice sends a message to Bob in this fashion, then Bob has to go through part of this procedure in reverse to obtain Alice her message:

1. Get the key and hash value from the message;
2. Decrypt them using his private key;
3. Validate the hash value by calculating the hash on the encrypted message and comparing both values;
4. Decrypt the message using the message key.

Why doesn't the system encrypt the entire message with the asymmetric (public) key of Bob? There is a good reason for this. Whilst asymmetric algorithms are good for helping with key exchanges, they are particularly bad and slow with actually encrypting and decrypting large volumes of data. Using them to encrypt and decrypt a secret key and a hash value is fast enough, but the entire message?

This is the reason that for the message a symmetric message key is generated and used. The combination of both systems properly secures the entire transaction.

Whilst this is explained here for e-mail, many other communication protocols work in a similar manner.

Some cryptographic implementations

This section will explain a couple of extremely impossible implementations. So keep this in mind whilst reading the subsections below.

They are based on quotes and ideas by people I have seen over the last decades in discussions on encryption and/or used by politicians or people from the law enforcement or intelligence communities.

Using certificates to encrypt connections

"I have a certificate and its used to encrypt my connection" or "the certificate encrypts" or a variation on this theme, something I have heard and read over and over and over again during my career in information security.

It simply is not true and in all fairness its not even technically possible.

If you have read through the explanations above, you may now understand why this is the case.

A certificate is a signed document by a trusted third party that tells you they checked and verified the displayed identity and the fact that they have control over the private key that is mathematically linked to the public key in the certificate.

So please do me and any other professional out there a favour, never claim this again. It's the underlying keys, usually both asymmetric and symmetric, that actually encrypt their respective parts of your communication, not the certificate. The certificate only proves you are talking with the right party or server on the other end of the line, nothing more and nothing less.

Building backdoors in encryption algorithms

Encryption algorithms can be weak, this usually isn't done on purpose but it happens and examples of this are widely available from the WPA protocol used to "secure" wireless networks to SSLv3 (Secure Socket Layer) and the protocols to "encrypt" the Tetra communication protocol used e.g. for the emergency services and police services in the Netherlands (C2000).

So yes it is definitely possible to build backdoors into encryption algorithms and yes it can be done on purpose too.

In the past it has been done by lowering the length of the encryption key so the American government could decrypt all network traffic. Whilst the keys were 56 bits in length, by design, they managed to lower them to 40 bits to make this possible.

Breaking encryption for law enforcement only

Whilst it is possible to break encryption, even do it on purpose instead of as a failure of the mathematical design, the problem is that if you do it this holds for all implementations of the specific encryption algorithm.

Encryption either works or it doesn't work as intended, there is no middle route and certainly no way to implement it such that the weakness can be used by only a few parties who know its there and keep that a secret too.

Whilst you could deliberately build in a backdoor, keeping that a secret for everyone else is a mere impossibility. Doing it simply breaks the encryption algorithm and therefore the security of the communication. As most widely used encryption algorithms are openly available, anybody who has enough knowledge and time can find out the weakness and either exploit it or publish it so everybody knows its there. This holds for closed, proprietary, algorithms too, the Tetra encryption algorithms are a good example of such a situation, they were made public because of them being cryptographically broken a couple of months ago.

This is one of the reasons why some governments actually ban the use of encryption or mandate you hand over your private key to them before you are allowed to use it.

it remains troubling that both politicians as well as people from the law enforcement and intelligence communities keep pushing this narrative hoping that people will beleive them its possible, it is not.

Conclusion

There is a lot more to teach about encryption, how the research of trying to break encryption works (cryptoanalyses) and which algorithms are available. There is also a lot more to discuss on the security aspects, the correct implementation of encryption and hashing algorithms and their correct usage, including encryption key management.

But as this addition is already pretty long, I will leave that for future addition or maybe an e-learning course. The latter which was once requested by a student on a privacy course a couple of years ago specially crafted for privacy professionals, who knos.

I at least hope you now have a basic understanding of encryption, its complexities and its proper usage, even if its only in discussions with others. It remains an interesting topic, besides the fact that encryption plays a very essential role in your every day digital lifes. Breaking it breaks our digital society, it really does.

Next addition

What will be the topic for the next addition? Help me out and suggest one in the comments or send me a private message which is possible even if you are not linked to me on this platform.

Who is Drs. Andor Demarteau

I am a Chief Information Security Officer with 15+ years’ experience. A trusted advisor to Business, Banking, Healthcare, Aviation, Broadcasting, Education and Government, bridging the gap between Business and IT. Delivering high quality, transparent and ethical expertise in Information Security, Data Protection, Privacy, and IT Risk Management Strategy. Public speaker, article author, visionary.

This newsletter is sponsored by Shamrock Information Security