An Introduction to Cryptography
Applied cryptography has existed as an integral element of military operations for millennia, but only recently has it seen a wider integration in society. Such integration has required significant developments in the tools and mechanisms, cryptosystems, needed to support society’s reliance. It has developed to become an incredibly interesting, but extensive, area to learn. The topics covered below bring a brief introduction to the intricacies of modern cryptography, but will provide important context and a foundation for future learnings.
Contents:
FAQ
Cryptosystems
Symmetric Key Cryptography
Public Key Cryptography
Hash Functions
Digital Signatures and Digital Certificates
FAQ
How does symmetric and asymmetric cryptography differ?
Symmetric key cryptography refers to a cryptosystem that uses the same key for both encryption and decryption. The security lies in only the individuals that are communicating having access to the key. One common type of symmetric key cryptography is a block cipher. Well known examples include DES, 3DES, and AES. Asymmetric key cryptography - also known as public key cryptography - refers to a cryptosystem where all participants have a pair of keys, one private and one public. Generally speaking, a message that is encrypted with someone’s public key can be decrypted with that person’s private key and vice versa. The security lies in a private key being kept secret, whereas the public key remain easily accessible to any potential recipient. Well known examples include RSA and ECDSA (elliptic curves).
What is a hash?
A hash is a string of seemingly meaningless bits, and is the output of a hash function. Hash functions are sometimes referred to as one-way cryptography, as the utility of a hash is that (ideally) there is no computationally feasible manner to find the original message given only the hash. Hashes can be used to compress messages of any size to a fixed output, or for message authentication.
How do cryptography and steganography differ?
Differences arise from how the message is kept secret. Cryptography intends for a message to be encrypted in such a manner that though anyone can observe the encrypted version of the message, only the intended recipient can feasibly decrypt it and read the original message. Steganography intends for a message to be concealed within another medium that only the intended recipient can feasibly uncover. Another way to think of it is that in cryptography it is intended that an attacker cannot understand the message, whereas in steganography it is intended that an attacker cannot observe the message though if they could they would be able to understand it. Steganography as such contradicts Kerckhoff’s Principle that stipulates an attacker should not be capable of understanding any message they do uncover.
How does Kerckhoff’s Principle apply to cryptography?
Many principles (six) were laid out by Kerckhoff in his principle publication on the necessities of a secure cryptosystem, but one in particular remains the most significant. Kerckhoff’s Principle maintains that a cryptosystem is only secure if it is computationally infeasible for an attacker to break given knowledge of the entire system except for the key. Importantly it can be derived from this principle that security through obscurity (steganography) cannot be considered cryptographically secure (hence the differentiation between steganography and cryptography).
What is the CIA triad?
In cybersecurity the CIA triad describes the three core properties of confidentiality, integrity, and availability. While availability is not the purview of cryptography, confidentiality and integrity are. Confidentiality describes the concept of a given message only being capable of understanding by the intended recipients. Integrity asks for a message to be able to assure a recipient that it originated from the claimed sender; and doubles to ensure a sender cannot later deny sending the message.
What are digital signatures?
Symmetric and asymmetric cryptography are able to implement confidentiality through ensuring computationally infeasibility to understand a message if one is not the intended recipient, but on their own they cannot guarantee integrity. Digital signatures are the most common type of mechanism of assuring a recipient that the message they have received is from the claimed sender. In the typical asymmetric cryptosystem a sender would would encrypt a message with the recipient’s public key, and then concatenate this result with the hash of the encrypted message that is then encrypted separately with the sender’s private key. The recipient would then be able to decrypt the encrypted message with their private key, and decrypt the encrypted hash with the sender’s public key before hashing the message to compare it with the hash. If the two values are equal only the claimed sender could have feasibly sent the message.
Cryptosystems
A cryptosystem describes the particular method through which a sender can send a message to the receiver across an unsecured network, without the message being intercepted. To begin this article the components of a cryptosystem will be defined.
Visualisation of the following common definitions associated with cryptosystems.
Definitions
Plaintext
The message to be sent to the receiver, that is intended to be kept hidden from all other parties.
Ciphertext
The encrypted version of the plaintext. This string of characters will typically have no resolvable relation to the plaintext, and as such can be observed by other parties safely.
Encryption Key
This key is a value that the sender has (and in a symmetric system is equal to the decryption key). If this key is known by other parties, the cryptosystem is not secure.
Encryption Algorithm
This algorithm takes the plaintext and encrypts it into ciphertext using the encryption key. It is a series of operations and functions.
Decryption Key
This key is a value that the receiver has (and in a symmetric system is equal to the encryption key). If this key is known by other parties, the cryptosystem is not secure.
Decryption Algorithm
This algorithm takes the ciphertext and decrypts it to obtain the plaintext using the decryption key. It is a series of operations and functions.
Typical Implementation
In a typical cryptosystem (where Alice is sending a message to Bob) the following will occur. Alice takes her plaintext and inputs it into the encryption algorithm along with the encryption key. This produces some cipher text which Alice sends to Bob. If other parties intercept the ciphertext they will be unable to resolve a relation to the original plaintext to decrypt it. When Bob receives the ciphertext he inputs it into the decryption algorithm along with the decryption key to produce Alice’s original plaintext.
The final thing to note about cryptosystems - which will help clarify exactly where the security lies - is Kerckhoff’s Principle. His principle states that a cryptosystem should be designed such that it is secure even if every component of the cryptosystem - except for the key(s) - is known to an attacker. Simply put, if the keys are secret the cryptosystem is safe.
Kerckhoff actually had six design principles for a cryptosystem, but this one is so important and well known that it is simply referred to as Kerckhoff’s Principle.
Types of Attacks
Each unique cryptosystem may be subject to various attacks. The differences in vulnerabilities are due to differing encryption methods, and level of security assumptions. It is also important to note that having known vulnerabilities doesn’t necessarily render a cryptosystem useless or broken. This is because many known vulnerabilities are theoretical, found by academics, but not actually practical to implement due to limited computational capabilities. However, it is more accurate to say that it would be ‘computationally infeasible’ to break a cryptosystem, rather than it being impossible.
Variations of Vulnerabilities
Aside from specific vulnerabilities here are a number of general attacks that are kept in mind when creating a new encryption standard.
Ciphertext Only
A ciphertext only attack is when an attacker has a set ciphertexts and uses them to try to figure out one of their corresponding plaintexts. It is not feasible to execute this attack against modern encryption standards.
Known Plaintext & Chosen Plaintext
A known plaintext attack is when an attacker has any plaintext and its corresponding ciphertext, and using this pair they attempt to ‘break’ the encryption algorithm and find the plaintext for another piece of ciphertext.
For further research, see linear cryptanalysis, used against block ciphers.
A chosen plaintext attack is the same in principle, but the attacker gets to choose what plaintext they would like to use.
For further research, see differential cryptanalysis, used against block ciphers and hash functions.
Dictionary
This attack - generally - involves an attacker keeping a catalogue of known plaintexts and their corresponding ciphertexts. The attacker then intercepts encrypted messages and then looks up the ciphertext in their dictionary to see if they have it and the corresponding plaintext recorded. There are, however, many variations of this attack.
Brute Force
A brute force attack is simply checking every possible key or plaintext, until the desired key or ciphertext is found. Typically the larger the key size the more possible ciphertexts there are that can be generated and the more possibilities there are for the attacker to check through, meaning larger key sizes are more resistant to brute force attacks.
Typical Aftermath
After an attacker has broken a cryptosystem - in part or in full - they can choose to act maliciously in a passive or an active manner. A passive attack would be when the attacker has broken the cryptosystem, and just observes the communications that are occurring without the sender or receiver knowing that they are eavesdropping.
Information theft differs from physical theft, as when a physical item is stolen the theft is noticed because an item is missing. However, when information is stolen, the theft usually goes unnoticed because the intended receiver will also receive the information.
Illustration of the primary differences between a passive and an active attack; note that the passive attack (unlike in the case of physical theft) would not be detectable.
In the case of an active attack, the attacker would either prevent communication from happening, or make changes to the messages that are sent, unbeknownst to the receiver (and potentially the sender).
For further research, see: timing analysis attacks, power analysis attacks, error analysis attacks.
Symmetric Key Cryptography
Simply put, symmetric key cryptography refers to a cryptosystem that uses the same key for both the encryption of plaintext and the decryption of the ciphertext. This key is a shared secret, known only to the sender and receiver. In a symmetric key cryptosystem, the sender inputs the plaintext and shared key into the encryption algorithm, which produces the ciphertext. This ciphertext is then sent to the receiver, who inputs it and the shared key into the decryption algorithm, which produces the plaintext. The encryption and decryption algorithms differ depending on what the encryption standard is.
The most common type of symmetric key encryption is called a block cipher. This is because it encrypts blocks of plaintext into blocks of ciphertext. The block size is fixed, and it is typically a multiple of 8. If the plaintext being encrypted is larger than the block size, the plaintext will be broken up into multiple blocks. Most of the time, the length of the plaintext isn’t an exact multiple of the block size, meaning the last block would not be filled by plaintext alone. In these instances, the remaining space in the block is filled with padding (non-plaintext bits that have no meaning, but are used to fill in empty space). The size of the block and the method of choosing the padding bits differ from one encryption standard to another.
As an example, a particular block cipher may have a block size of 256 bits, and the method of padding is to append a 1 followed by enough 0s to fill up the block. If the plaintext to be encrypted was 544 bits long, this message would be broken into three blocks (256 + 256 + 32). The first two blocks would encrypted as is, but the last block would be the remaining 32 bits of plaintext with 224 bits of padding appended to it (32 bits of plaintext + 1 bit equal to 1 + 223 bits equal to 0). The block can take upon just about any size, with a tendency to avoid extreme sizes (either too small or too large). Smaller block sizes mean that there are fewer unique ciphertext outputs that are possible, allowing for a greater feasibility of dictionary or brute force attacks. Larger block sizes are often inefficient, requiring extra padding and encryption/decryption on average for a given plaintext. Something important to note is that the security of the block cipher is not directly linked to the block size. It is also the length of the key that determines how computationally infeasible it is to attack the cryptosystem.
Further information can be found here https://nvlpubs.nist.gov/nistpubs/sp958-lide/250-253.pdf
There are a few attacks that are unique to symmetric key encryption, due to the key being a shared secret. These typically relate to key mismanagement by one of the participants. For example, the sender or receiver could either accidentally or intentionally share the key with an outside party. This would allow the outside party to observe all communications, whilst the receiver or sender is unaware that the cryptosystem is no longer secure.
For further research, see stream ciphers (as opposed to block ciphers)
Depiction of a typical symmetric cryptographic system.
Public Key Cryptography
In short, public key cryptography, or asymmetric key cryptography, refers to a cryptosystem where each participant has two keys: one that is a secret, and one that is publicly known. The two keys are mathematically linked, but in such a way such that one cannot feasibly derive the private key from the public key. Asymmetric key cryptography involves the sender using the receiver’s public key to encrypt the plaintext and the receiver using their private key to decrypt the following ciphertext. This pattern lends itself to the concept of creating key pairings that can be visualised as a shared key. Due to the way that the private and public keys are linked, the sender and receiver can create a shared key independently of each other. Combining the sender’s private key and receiver’s public key will create a key with the same properties as combining the sender’s public key and the receiver’s private key.
There are, however, weaknesses in this system. This is because all public keys are kept in a public repository, with some level of trust involved. When a sender wants to encrypt a message, they need to request the receiver’s public key from the repository. If an attacker was to gain some level of control over this repository, when a sender requests the receiver’s public key, the attacker could send their own public key instead. The sender would then believe that they are creating a shared key with the receiver, but actually be creating a shared key with an attacker. The attacker would do the same with the receiver, allowing communication to occur between the innocent sender and receiver. This attack is a form of Man-in-the-Middle attacks, and is not an uncommon attack - especially over insecure networks like public Wi-Fi. This style of attack can be both a passive and an active attack. This is because the attacker cannot only listen in on the conversation undetected (passive), but they can also send false messages to either party as an imposter (active). While combatting this possibility of attack relies on appropriate forms of governance and regulation for public repositories, there are other similar forms of Man-in-the-Middle attacks.
Without appropriate cryptosystems in addition to asymmetric or symmetric systems, it is possible for an attacker to intercept messages from the sender and swap it with their own message that will be sent onto the receiver. Since the receiver’s public key is known by the attacker they can create a message that can still be decrypted by the receiver’s private key, and as such appears to be genuine. This attack would be active, but would be capable of avoiding detection by the receiver (though the sender can setup mechanisms to detect these attacks). Other examples of public key cryptography mitigate this attack vector by utilising digital signatures and digital certificates, which allows a receiver to authenticate that the message came from the sender that they are expecting. Digital signatures and digital certificates will be discussed later in this article.
Depiction of a typical asymmetric cryptographic system.
Hash Functions
Also referred to as one-way cryptography, hash functions derive utility from the fact that the hash of a message cannot be decrypted to find the original message. Essentially, a hashing algorithm takes some input and performs operations on it (permutations, expansions, contractions, bit shifts, XORs etc.) which produces some output that has no resolvable relation to the original input (in a similar manner to encryption, but more efficiently and with less security assumptions required).
Properties
There are many different families of hash functions that can have slight to extreme variations, but the following properties are very common.
Collision Resistance
For each input, there is an output that appears to be unique. It should be infeasible to ever find two inputs that are not identical that happen to have an equal hash. Two inputs that produce an identical hash are called a collision, and a hash function is considered broken if it is computationally feasible to find such a collision.
Fixed Length
Every input produces an output of a fixed length, which has been predetermined. For example the SHA256 algorithm will always produce an output with a length of 256 bits, regardless of how long the input is.
Pre-Image Resistance
If one has the hash of a message, it is computationally infeasible to find what the original message was.
Second Pre-Image Resistance
Even if one has a message and its hash, there will be no information gained that would allow the finding of a different message with the same hash. This property is also called ‘weak collision resistance’ due to its similarity and that a hash output needs to be only half the size required of the property of ‘collision resistance’ to be satisfied.
Illustration of the properties of a hash function.
Some other properties include:
- The same input is guaranteed to generate the same output.
- Two slightly different input will have two very different outputs.
- Creating a hash is a very fast process, but finding a hash collision is computationally infeasible.
Variations Between Families of Hash Functions
Possibly the most well known hash algorithms would be the SHA (Secure Hash Algorithm) family. The family of algorithms are published by the National Institute of Standards and Technology (NIST), and consist of SHA-0, SHA-1, SHA-2, SHA-3. However within each of these algorithms there are further variations which differ in internal characteristics, most notably the output size.
SHA-0 was briefly a standard, as is was withdrawn soon after it was published due to a significant flaw which was not disclosed.
SHA-1 was created by the NSA and had a 160 bit output size. Theoretical vulnerabilities were discovered in 2005, and the algorithm was banned from U.S. Federal Agencies in 2010. In 2015, a group of researchers devised a method to find a practical hash collision and began working with Google and their computing infrastructure. After ~9 quintillion computations, they were able to create two different pdf documents which had the same SHA-1 hash.
SHA-2 was again created by the NSA in 2001 as the successor of SHA-1. There are multiple variations of SHA-2 differing in output length, the most commonly known being SHA256 with an output of 256 bits. The algorithm includes 64 rounds of encryption functions. The best (publicly known) attacks on SHA256 can break the algorithm for 52 out of the 64 rounds with respect to preimage resistance, and can break the algorithm for 46 out of the 64 rounds with respect to collision resistance.
SHA-3 is the most recent addition to the SHA family, published by NIST in 2015. The internal workings of SHA-3 differ from those of SHA-1 and SHA-2, and was not created by the NSA, but chosen from a public competition spanning several years. There are currently no plans to remove SHA-2 as a standard, but SHA-3 can be substituted into system if it is ever required.
Digital Signatures and Digital Certificates
Digital signatures and digital certificates are two different authentication processes that work hand in hand to allow the receiver to verify who sent them a message. At a high level, a digital signature is a cryptographic function that authenticates that a message has come from the sender, and that it hasn’t been tampered with by a third party. Digital certificates instead are issued by a trusted third party and attach an identity to the sender. To create a digital signature, the sender first finds the hash of the message being sent.
Note: the ‘message’ is not the plaintext, the message being sent is already encrypted using some encryption algorithm. The reason that the hash of the message is used is because it is necessary that all messages to be signed are the same length, and not all encryption methods will compress a message to a certain size.
The digital signature is then created by encrypting the message with the sender’s private key.
Note: the public/private key pairings used in the encryption process and the signing process are typically not the same. This is usually due to differing key sizes for the encryption algorithm and digital signature algorithm.
The sender now sends the (pre-hashed) message and the digital signature to the receiver. The receiver then computes the hash of the message for themselves, to be used again in a moment. The receiver also takes the digital signature (which is the hash of the message, that is encrypted with the sender’s private key) and decrypts it with the sender’s public key, to find the message hash.
If the message hash obtained by decrypting the signature with the sender’s public key is the same as the message hash that the receiver computed themselves, then the receiver can be confident that the the message came form the sender that they are expecting, and the message has not been tampered with.
A digital certificate is issued by a Certificate Authority. The certificate authenticates that a particular public key is attached to a particular identity. The certificate contains information such as a name, expiration date, and serial number - and has the Certificate Authority’s digital signature. The digital certificate accompanies the digital signature and message when they are sent to the receiver.
