Question

Introduction to Cryptographic Methods - 61314

COURSE PROJECT

CHOICES AND TECHNOLOGY INTRODUCTION

Encryption—Symmetric Techniques

1. Substitution Ciphers
2. Transposition Ciphers
3. Classical Ciphers: Usefulness and Security
4. The Data Encryption Standard (DES)
5. The Advanced Encryption Standard (AES)
6. Confidentiality Modes of Operation
7. Key Channel Establishment for Symmetric Cryptosystems

Answer 1

1.Encryption - Symmetric Techniques

Symmetric ciphers use symmetric algorithms to encrypt and decrypt data. These ciphers are used in symmetric key cryptography. A symmetric algorithm uses the same key to encrypt data as it does to decrypt data. For example, a symmetric algorithm will use key kk to encrypt some plaintext information like a password into a ciphertext. Then, it uses kk again to take that ciphertext and turn it back into the password.

Symmetric ciphers are the opposite of asymmetric ciphers, like those used in public-key cryptography. These ciphers use asymmetric algorithms which use one key to encrypt data and a different key to decrypt ciphers. Typically, those two keys are called public and private keys, as is the case with RSA encryption. The public key is used to encrypt data, and the private key is used to decrypt data.

Symmetric ciphers have many important advantages, like speed. But they lack in other areas like security and key management. Due to these pros, however, there are a number of important symmetric ciphers in production today. The most popular of these is Advanced Encryption Standard (AES). Because of its security concerns, however, it is often used on a single machine for encryption and decryption. This eliminates the need to share the secret key. Symmetric ciphers are a good place to get started when learning cryptography as they were the first widespread systems used in modern computing.

Like all forms of cryptography, the general process of symmetric key cryptography is to first encrypt a message. This encryption algorithm will turn any plaintext data into ciphertext, an unreadable code. Then, that ciphertext is transmitted to another party who decrypts it to find the original message.

This process uses some sort of key in the encryption and decryption algorithms. Typically this key is only a series of bits, representing some number. What the key is exactly depends on the encryption being used. For symmetric ciphers, the same key is used in both the encryption and decryption algorithm.

Simple Symmetric Ciphers

Caeser Cipher

Simple symmetric are the oldest forms of cryptography, dating back to the Caesar cipher, a cipher used by Julius Caesar to communicate in secret. This cipher, a type of substitution cipher, took any message that Caesar might write to someone, and shifted each character in that message by a certain amount. For example, the message "hello" shifted by a value of 5 would result in "mjqqt". This cipher is symmetric because the same key, in this case 5, is used to encrypt and decrypt the message.

Caesar's cipher is especially prone to attacks like frequency analysis. Words and characters in lanaguage are not random. If an attacker intercepts enough messages, they might learn that they letter j shows up a lot in the cipher text codes. Now the attacker has a clue that j is Caesar cipher code for a common letter, probably an s or an a. Definitely not a z. Repeating this process enough can break this code.

One-time pad

The one-time pad is another famous symmetric cipher. It's famous for its reported use by KGB and American spies during the Cold War. Let's say one spy wanted to get another spy a message, and for simplicity that message is in binary format. The two spies have already met up beforehand and decided on a key of 10110 for this one message. This key is usually decided at random to heighten security. The first spy, Alice, wants to send the message 01101 to Bob, the second spy. To encrypt Alice's message, she creates a new cipher text that has a 0 if the corresponding bit is the same between the original message and the key. Otherwise, it has a 1. This is also called an XOR in boolean logic.

There is a problem with the one-time pad (apart from other general problems with symmetric ciphers). The key needs to be exactly as long as the message itself. Alice and Bob can get around this issue by simply looping around to the beginning of the key when they reach the end. However, this will make the code much easier to break by opposing spies using brute force or statistical analysis. However, one-time pads are perfectly secret in theory. This means that an attacker cannot know anything about a particular cipher text if they intercept it. In practice, however, it's insecure to distribute and exchange keys.

Transposition Ciphers

Transposition Ciphers are a bit different to Substitution Ciphers. Whereas Substitution ciphers replace each letter with a different letter or symbol to produce the ciphertext, in a Transposition cipher, the letters are just moved around.

The letters or words of the plaintext are reordered in some way, fixed by a given rule (the key).

One example of a transposition cipher, is to reverse the order of the letters in a plaintext. So "a simple example" becomes "ELPMAXE ELPMIS A". Another, similar, way to encrypt a message would be to reverse the letters of each word, but not the order in which the words are written. In this case "a simple example" becomes "A ELPMIS ELPMAXE". Both of these are available in the activity at the bottom of the page.

Substitution Ciphers

Substitution ciphers are probably the most common form of cipher. They work by replacing each letter of the plaintext (and sometimes puntuation marks and spaces) with another letter (or possibly even a random symbol).

A monoalphabetic substitution cipher, also known as a simple substitution cipher, relies on a fixed replacement structure. That is, the substitution is fixed for each letter of the alphabet. Thus, if "a" is encrypted to "R", then every time we see the letter "a" in the plaintext, we replace it with the letter "R" in the ciphertext.

A simple example is where each letter is encrypted as the next letter in the alphabet: "a simple message" becomes "B TJNQMF NFTTBHF". In general, when performing a simple substitution manually, it is easiest to generate the ciphertext alphabet first, and encrypt by comparing this to the plaintext alphabet. The table below shows how one might choose to, and we will, lay them out for this example.

The ciphertext alphabet for the cipher where you replace each letter by the next letter in the alphabet

There are many different monoalphabetic substitution ciphers, in fact infinitely many, as each letter can be encrypted to any symbol, not just another letter.

The history of simple substitution ciphers can be traced back to the very earliest civisilisations, and for a long time they were more than adequate for the purposes for which they were needed. By today's standards they are very weak, and incredibly easy to break, but they were a very important step in developing cryptography.

Classical Ciphers -

Classical ciphers have been used since ancient Egypt to exchange classified
messages between authorized persons. Since then, different methods and techniques are used in order to increase security level of such information. Most of these methods and techniques are based on the idea that each natural language has its own distribution characteristics.

The encryption process aims to uniformly flatten the statistical characteristics of the language and obscure any correlation and dependencies between plaintext and ciphertext by diffusion and confusion. In the other hand, cryptanalysis tries to make use of remaining information (such as structured properties, redundancy, correlation, and dependencies) to recover the plaintext or the used key during encryption process.

Cryptographic systems have been classified into different types in many cryptography literatures. However, most of these literatures classify them into two main categories; symmetric (one-key) cryptosystems, and asymmetric (two-key) systems.In symmetric or one-key systems, the enciphering and deciphering key are the same. In asymmetric cryptosystems enciphering and deciphering keys are different in such a way the at least one key is computationally infeasible to determine from the other.

From the ancient ages till the last few decades, all cryptosystems were one-key   systems, thus one-key systems referred to as conventional or (classical) systems.There are four basic types of classical cryptosystems based on substitution. They are ; ( simple substitution , homophonic substitution , polyalphabetic substitution , and polygram substitution systems ), and one cipher system based on transposition (permutation).

Data Encryption Standard(DES)

DES is a symmetric system that was once a predominant standard in the 1970s but has since fallen our of favor due to its low security. Its introduction sparked heated debate about the role of standards in cryptography and led to much research and innovation in the field. However, DES is the archetype of block cipher systems, many systems today are based on its design.

DES uses block ciphers. The block ciphers in DES consist of 56 random bits, and 8 more bits are used for error detection. These error detecting bits make DES unmalleable - attackers can't change the cipher on its way to its destination because they might accidentally delete a bit used for error detection, and then receivers would know the data had been attacked. However, the relatively small key size was an issue of debate even in the 1970s. By 1999, DES could be broken in under a day. This was later solved by sequencing multiple DES systems together, called 3DES.

The data is first sent into the system and then cut into two 32-bit halves. Those two halves are sent through the entire system, criss-crossing using what's known as the Feistel system. There are 16 layers in DES, and at each layer, one half of the data goes through the Fiestel function. Once it's finished, it is XORd with the other half of the data. Each layer has its own subkey. The subkey is derived from the main, 56-bit key using a key scheduler.

The Fiestel function, which occurs in every block labeled FF in the diagram to the right, has 3 steps:

1. Expansion: The incoming 32-bit block has half of its bits duplicated, making it a 48-bit block.
2. Mixing: The new, 48-bit input block is put through an XOR gate with this round's unique subkey.
3. Substitution: The mixed, 48-bit block is divided into 8 6-bit pieces. Each of these 8 pieces is put through an S-block which will output only 4-bits using a non-linear-transformation. *
4. Permutation: The 32 output bits are then arranged in a specific permutation that ensures that they will be distributed among different S-blocks in the next round.

*This is most important part of security in DES, it helps to avoid simple, algebra-based attacks.

The key scheduler:

1. The 56-bit primary key is split into two 28-bit keys. These halves are hereafter treated separately.
2. In each round, each half is rotated left or right by either one or two bits (depending on the round).
3. 24 bits from the left half are chosen, and 24 from the right are chosen to make a 48-bit subkey.

Because we rotate on each round, each bit is only used in approximately 14 out of the 16 rounds. The key scheduler for encryption and decryption are the exact same except that the subkeys are in reverse order for decryption.

DES was vulnerable to brute force attacks as early as the 1970s, but there were other ways it was weak as well. Differential cryptanalysis, or the study of how changes in inputs can affect output, are very effective at breaking block ciphers and DES in particular. Linear cryptanalysis, which apply affine transformations to a cipher were also widely used.

Advanced Encryption Standard(AES)

AES is similar to DES in that it is symmetric and uses block ciphers. However, it is much more secure than DES and has become the international standard. It is at least 6 times faster than 3DES. Instead of Fiestel functions, AES uses a substitution-permutation network. This network is a series of operations than either replaces input with output bits (substitution) or shuffles the bits (permutation).

It uses 128-bit input plaintext, but it operates on bytes rather than bits. So, the input is represented as 16 bytes (because 128 bits = 16 bytes), arranged in a 4 x 4 matrix. This matrix, called the state, will be modified as the algorithm progresses. AES also operates in rounds, but the number of rounds is variable and is based on the length of the key used. A 128-bit key will run AES for 10 rounds, a 192-bit key for 12 rounds, and a 256-bit key will run for 14 rounds. Similar to DES, each round uses a different key. These subkeys are 128-bits in length and are calculated from the original key.

AES proceeds as follows:

1. Round 1

   a. AddRoundKey

2. Rounds 2 through (n-1)

   a. SubBytes

   b. ShiftRows

   c. MixColumns

   d. AddRoundKey

3. Round n

   a. SubBytes

   b. ShiftRows

   c. AddRoundKey

The first function, AddRoundKey, takes the current state (a 16-byte matrix) and XORs it with the key for this particular round. The result is the new state.

SubBytes is one of the substitution functions of AES. The 16 byte state matrix is substituted using a S-box from the design of the specific AES implementation. This step is very similar to the substitution step in DES in that it uses non-linearity and an affine transformation to provide security to the system.

ShiftRows shifts the bytes in each row with respect to each other. Typically, the top row of the state will remain unchanged, the second row will shift left one, the third row will shift left two and the fourth row will shift left 3. This step is done to ensure the columns are not linearly independent, which would turn AES into 4, independent block ciphers.

MixColumns multiplies each column of the state by an invertible function, a fixed polynomial.

Decryption in AES is the same algorithm as encryption, but in a reverse manner. Decryption, unlike in Fiestel's structure, needs to be implemented separately because the functions are in reverse order, but they are very similar.

Confidentiality Modes of Operation

Block ciphers can operate in one of several modes; the following are the most important:

• Electronic Codebook (ECB) mode is the simplest, most obvious application: the secret key is used to encrypt the plaintext block to form a ciphertext block. Two identical plaintext blocks, then, will always generate the same ciphertext block. ECB is susceptible to a variety of brute-force attacks (because of the fact that the same plaintext block will always encrypt to the same ciphertext), as well as deletion and insertion attacks. In addition, a single bit error in the transmission of the ciphertext results in an error in the entire block of decrypted plaintext.
• Cipher Block Chaining (CBC) mode adds a feedback mechanism to the encryption scheme; the plaintext is exclusively-ORed (XORed) with the previous ciphertext block prior to encryption so that two identical plaintext blocks will encrypt differently. While CBC protects against many brute-force, deletion, and insertion attacks, a single bit error in the ciphertext yields an entire block error in the decrypted plaintext block and a bit error in the next decrypted plaintext block.
• Cipher Feedback (CFB) mode is a block cipher implementation as a self-synchronizing stream cipher. CFB mode allows data to be encrypted in units smaller than the block size, which might be useful in some applications such as encrypting interactive terminal input. If we were using one-byte CFB mode, for example, each incoming character is placed into a shift register the same size as the block, encrypted, and the block transmitted. At the receiving side, the ciphertext is decrypted and the extra bits in the block (i.e., everything above and beyond the one byte) are discarded. CFB mode generates a keystream based upon the previous ciphertext (the initial key comes from an Initialization Vector [IV]). In this mode, a single bit error in the ciphertext affects both this block and the following one.
• Output Feedback (OFB) mode is a block cipher implementation conceptually similar to a synchronous stream cipher. OFB prevents the same plaintext block from generating the same ciphertext block by using an internal feedback mechanism that generates the keystream independently of both the plaintext and ciphertext bitstreams. In OFB, a single bit error in ciphertext yields a single bit error in the decrypted plaintext.
• Counter (CTR) mode is a relatively modern addition to block ciphers. Like CFB and OFB, CTR mode operates on the blocks as in a stream cipher; like ECB, CTR mode operates on the blocks independently. Unlike ECB, however, CTR uses different key inputs to different blocks so that two identical blocks of plaintext will not result in the same ciphertext. Finally, each block of ciphertext has specific location within the encrypted message. CTR mode, then, allows blocks to be processed in parallel — thus offering performance advantages when parallel processing and multiple processors are available — but is not susceptible to ECB's brute-force, deletion, and insertion attacks