Ciphertext is the scrambled and unreadable output of encryption

Cryptography

What Is Cryptography?

Cryptography (from Greek words meaning hidden writing) is the practice of transforming information so that it is secure and cannot be accessed by unauthorized

parties.

This is accomplished through scrambling the information in such a way that only approved recipients can access it

steganography hides the existence of the data, usually some type of message, embedded within the image

Encryption

the process of changing the original text into a scrambled message

The reverse process is decryption: changing the message back to its original form

Plaintext. Unencrypted data that is input for encryption or is the output of decryption.

Ciphertext. is the scrambled and unreadable output of encryption.

Cleartext. Readable (unencrypted) data that is transmitted or stored in “the clear” and is not intended to be encrypted

cryptography - study of encryption principles/methods

cryptanalysis (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing key

cryptology - the field of both cryptography and cryptanalysis

Cipher algorithm consists of procedures based on a mathematical formula to encrypt and decrypt the data.

A key is a mathematical value entered into the algorithm to produce the ciphertext.

When the ciphertext is to be returned to plaintext, the reverse process occurs with a decryption algorithm and key.

Classification of Cryptography

Number of keys used

Hash functions: no key

Secret key cryptography: one key

Public key cryptography: two keys - public, private

Type of encryption operations used

substitution / transposition / product

Way in which plaintext is processed

block / stream

7

Unconditional vs. Computational Security

Unconditional security

No matter how much computer power is available, the cipher cannot be broken

The ciphertext provides insufficient information to uniquely determine the corresponding plaintext

Computational security

The cost of breaking the cipher exceeds the value of the encrypted info

The time required to break the cipher exceeds the useful lifetime of the info

8

8

Unconditional security would be nice, but the only known such cipher is the one-time pad (later). For all reasonable encryption algorithms, have to assume computational security where it either takes too long, or is too expensive, to bother breaking the cipher.

Brute Force Search

Always possible to simply try every key

Most basic attack, proportional to key size

Assume either know / recognise plaintext

9

Key Size (bits) Number of Alternative Keys Time required at 1 decryption/µs Time required at 106 decryptions/µs

32 232 = 4.3  109 231 µs = 35.8 minutes 2.15 milliseconds

56 256 = 7.2  1016 255 µs = 1142 years 10.01 hours

128 2128 = 3.4  1038 2127 µs = 5.4  1024 years 5.4  1018 years

168 2168 = 3.7  1050 2167 µs = 5.9  1036 years 5.9  1030 years

26 characters (permutation) 26! = 4  1026 2  1026 µs = 6.4  1012 years 6.4  106 years

9

A brute-force attack involves trying every possible key until an intelligible translation of the ciphertext into plaintext is obtained. On average, half of all possible keys must be tried to achieve success. Stallings Table 2.2 shows how much time is required to conduct a brute-force attack, for various common key sizes (DES is 56, AES is 128, Triple-DES is 168, plus general mono-alphabetic cipher), where either a single system or a million parallel systems, are used.

Block vs Stream Ciphers

Block ciphers process messages in into blocks, each of which is then en/decrypted

Stream ciphers process messages a bit or byte at a time when en/decrypting

Many current ciphers are block ciphers, one of the most widely used types of cryptographic algorithms

Most symmetric block ciphers are based on a Feistel Cipher Structure

1- Classical Substitution Ciphers

Letters of plaintext are replaced by other letters or by numbers or symbols

Plaintext is viewed as a sequence of bits, then substitution replaces plaintext bit patterns with ciphertext bit patterns

Caesar Cipher

Earliest known substitution cipher

Replaces each letter by 3rd letter on

Example:

meet me after the toga party

PHHW PH DIWHU WKH WRJD SDUWB

Caesar Cipher

Define transformation as:

a b c d e f g h i j k l m n o p q r s t u v w x y z

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Mathematically give each letter a number

a b c d e f g h i j k l m

0 1 2 3 4 5 6 7 8 9 10 11 12

n o p q r s t u v w x y Z

13 14 15 16 17 18 19 20 21 22 23 24 25

Then have Caesar cipher as:

C = E(p) = (p + k) mod (26)

p = D(C) = (C – k) mod (26)

Cryptanalysis of Caesar Cipher

Only have 25 possible ciphers

A maps to B,..Z

Given ciphertext, just try all shifts of letters

Do need to recognize when have plaintext

Monoalphabetic Cipher

Rather than just shifting the alphabet

Could shuffle (jumble) the letters arbitrarily

Each plaintext letter maps to a different random ciphertext letter

Key is 26 letters long

Plain: abcdefghijklmnopqrstuvwxyz

Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters

Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

Monoalphabetic Cipher Security

Now have a total of 26! = 4 x 1026 keys

Is that secure?

Problem is language characteristics

Human languages are redundant

Letters are not equally commonly used

English Letter Frequencies

Example Cryptanalysis

Given ciphertext:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

Count relative letter frequencies (see text)

Guess P & Z are e and t

Guess ZW is th and hence ZWP is the

Proceeding with trial and error finally get:

it was disclosed yesterday that several informal but

direct contacts have been made with political

representatives of the viet cong in moscow

2- Transposition Ciphers

These hide the message by rearranging the letter order, without altering the actual letters used

3- Product Ciphers

Ciphers using substitutions or transpositions are not secure because of language characteristics

Hence consider using several ciphers in succession to make harder, but:

Two substitutions make another substitution

Two transpositions make a more complex transposition

But a substitution followed by a transposition makes a new much harder cipher

This is bridge from classical to modern ciphers

Strengths of cryptography

Keys are random numbers:

The primary property of a truly random number is that the probability of it being selected is the same as any other number being selected, so that it is not possible to predict a future number based on a previous number

Diffusion means that if a single character of plaintext is changed then it should result in multiple characters of the ciphertext changing.

Eliminating a one-to one correspondence between the plaintext and the ciphertext makes it more difficult for a threat actor to perform cryptoanalysis

Confusion: means that the key does not relate in a simple way to the ciphertext.

Each character of the ciphertext should depend upon several different parts of the key.

This forces the threat actor to create the entire key simultaneously, a difficult task, rather than trying to recreate the key piece by piece

Cryptography and Security

Cryptography can support the following basic protections:

Confidentiality: by ensuring that only authorized parties can view it

Integrity: it ensures that the information is correct and no unauthorized person or malicious software has altered that data.

Because ciphertext requires that a key must be used to open the data before it can be changed, cryptography can ensure its integrity.

Categories of cryptography

Hash algorithms

Symmetric cryptographic algorithms

Asymmetric cryptographic algorithms.

Hash Functions

Condenses arbitrary message to fixed size

h = H(M)

Usually assume that the hash function is public and not keyed

Hash used to detect changes to message

Can use in various ways with message

Most often to create a digital signature

Hash algorithm

Creates a unique “digital fingerprint” of a set of data.

Uses computational functions that take a variable-length input of data and produce a fixed length result that can be used as a fingerprint to represent the original data.

This process is called hashing, and the resulting fingerprint is a digest (a message digest or hash) that represents the contents.

Hashing is used primarily for comparison purposes

Although hashing is a cryptographic algorithm, its purpose is not to create ciphertext that can later be decrypted.

Requirements for Hash Functions

Can be applied to any sized message M

Produces fixed-length output h

Is easy to compute h=H(M) for any message M

Pre-Image Resistance

It should be computationally hard to reverse a hash function.

If a hash function h produced a hash value z, then it should be a difficult process to find any input value x that hashes to z.

5- Second Pre-Image Resistance

Given an input and its hash, it should be hard to find a different input with the same hash.

If a hash function h for an input x produces hash value h(x), then it should be difficult to find any other input value y such that h(y) = h(x).

6- Collision Resistance

It should be hard to find two different inputs of any length that result in the same hash (collision free hash function)

Examples:

Same length:

A digest of the single letter a is 86be7afa339d0fc7cfc785e72f578d33

A digest of 1 million occurrences of the letter a is 4a7f5723f954eba1216c9d8f6320431f

Weak collision resistance:

Digest of Sunday is 0d716e73a2a7910bd4ae63407056d79b

Digest of sunday (lowercase s) is 3464eb71bd7a4377967a30da798a1b54

http://onlinemd5.com/

How are hashes used?

1- Verifying file integrity of the original contents that it has not been changed:

For example, digests are often calculated and then posted on websites for files that can be downloaded.

After downloading the file a user can create her own digest on the file and then compare it with the digest value posted on the website.

A match indicates that there has been no change to the original file

2- Hashing passwords: storing hash of the password, rather than the plain password.

Because hashes are not reversible, there is no way to find out the original password.

Storing a hash instead of a password

Testing a proposed password against the stored hash

3- Digitally Signed Documents: the sender signs (encrypts with private key) the hash of the document, the result of which is a digital signature.

The most common hash algorithms are

Message Digest 5

Secure Hash Algorithm

RACE Integrity Primitives Evaluation Message Digest

Hashed Message Authentication Code

Message Digest (MD)

Four different versions of MD hashes were introduced over almost 20 years: MD2 (1989), MD4 (1990), MD5 (1992), and MD6 (2008).

The most well known of these algorithms is Message Digest 5 (MD5).

Weakness: its not collision free (having the same output for two distinct inputs)

SHA-1 verses MD5

Brute force attack is harder (160 vs 128 bits for MD5)

A little slower than MD5 (80 vs 64 steps)

Both work well on a 32-bit architecture

Both designed as simple and compact for implementation

Cryptanalytic attacks

MD4/5: vulnerability discovered since its design

SHA-1: no until recent 2005 results raised concerns on its use in future applications

Secure Hash Algorithm (SHA)

SHA-0: Dropped

SHA-1: similar to MD, not collusion free

SHA-2: comprised of six variations named SHA3-224, SHA3-256, SHA3-384, and SHA3-512; in each case, the suffix after the dash indicates the fixed length of the digest

SHA-3: compact, suitable for some low-power devices

Symmetric cryptographic algorithms

Uses the same single key to encrypt and decrypt a document.

Encryption key must kept private (confidential), because if an attacker obtained the key he could read all the encrypted documents.

For this reason, symmetric encryption is also called private key cryptography.

Common symmetric cryptographic algorithms:

Data Encryption Standard

Triple Data Encryption Standard

Advanced Encryption Standard

Data Encryption Standard (DES)

Is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST).

DES is an implementation of a Feistel Cipher.

It uses 16 round Feistel structure.

The block size is 64-bit.

Key length is 64-bit

Vulnerable against exhaustive key search attack

Triple DES

The speed of exhaustive key searches against DES after 1990 began to cause discomfort amongst users of DES.

However, users did not want to replace DES as it takes an enormous amount of time and money to change encryption algorithms that are widely adopted and embedded in large security architectures.

The pragmatic approach was not to abandon the DES completely, but to change the manner in which DES is used.

This led to the modified schemes of Triple DES

There are two variants of Triple DES known as 3-key Triple DES (3TDES) and 2-key Triple DES (2TDES).

Before using 3TDES, user first generate and distribute a 3TDES key K, which consists of three different DES keys K1, K2 and K3.

This means that the actual 3TDES key has length 3×56 = 168 bits.

The encryption-decryption process :

Encrypt the plaintext blocks using single DES with key K1.

Decrypt the output of step 1 using single DES with key K2.

Encrypt the output of step 2 using single DES with key K3.

The output of step 3 is the ciphertext.

Decryption of a ciphertext is a reverse process. User first decrypt using K3, then encrypt with K2, and finally decrypt with K1.

Second variant of Triple DES (2TDES) is identical to 3TDES except that K3is replaced by K1.

The user encrypt plaintext blocks with key K1, then decrypt with key K2, and finally encrypt with K1 again.

Therefore, 2TDES has a key length of 112 bits.

Triple DES systems are significantly more secure than single DES, but these are clearly a much slower process than encryption using single DES.

Advanced Encryption Standard (AES)

A replacement for DES as its key size was too small

128-bit data, 128/192/256-bit keys

Stronger and faster than Triple-DES

Provide full specification and design details

Software implementable in C and Java

Based on ‘substitution–permutation network’.

Comprises of a series of linked operations, some of which involve replacing inputs by specific outputs (substitutions) and others involve shuffling bits around (permutations).

AES performs all its computations on bytes rather than bits.

AES treats the 128 bits of a plaintext block as 16 bytes. These 16 bytes are arranged in four columns and four rows for processing as a matrix

Unlike DES, the number of rounds in AES is variable and depends on the length of the key. AES uses 10 rounds for 128-bit keys, 12 rounds for 192-bit keys and 14 rounds for 256-bit keys.

AES algorithm

Each round comprise of four sub-processes:

1- Byte Substitution (SubBytes)

The 16 input bytes are substituted by looking up a fixed table (S-box) given in design. The result is in a matrix of four rows and four columns.

2- Shiftrows

Each of the four rows of the matrix is shifted to the left. Any entries that ‘fall off’ are re-inserted on the right side of row. Shift is carried out as follows −

First row is not shifted.

Second row is shifted one (byte) position to the left.

Third row is shifted two positions to the left.

Fourth row is shifted three positions to the left.

The result is a new matrix consisting of the same 16 bytes but shifted with respect to each other.

3- MixColumns

Each column of four bytes is now transformed using a special mathematical function. This function takes as input the four bytes of one column and outputs four completely new bytes, which replace the original column.

The result is another new matrix consisting of 16 new bytes.

This step is not performed in the last round.

4- Addroundkey

The 16 bytes of the matrix are now considered as 128 bits and are XORed to the 128 bits of the round key.

If this is the last round then the output is the ciphertext.

Otherwise, the resulting 128 bits are interpreted as 16 bytes and we begin another similar round.

Decryption Process

The process of decryption of an AES ciphertext is similar to the encryption process in the reverse order.

Each round consists of the four processes conducted in the reverse order:

Add round key

Mix columns

Shift rows

Byte substitution

Asymmetric Cryptographic Algorithms

The primary weakness of symmetric encryption algorithms: distributing and maintaining a secure single key among multiple users, who are often scattered geographically

Asymmetric encryption uses two keys instead of only one.

These keys are mathematically related and are called the public key and the private key.

The public key is known to everyone and can be freely distributed, while the private key is known only to the individual to whom it belongs.

Common asymmetric cryptographic algorithms:

RSA

Elliptic Curve Cryptography

Digital Signature Algorithm

Important properties of public key encryption scheme:

Different keys are used for encryption and decryption.

Each receiver possesses a unique decryption key (private key).

Receiver needs to publish an encryption key (public key).

Some assurance of the authenticity of a public key is needed in this scheme to avoid spoofing by adversary as the receiver.

This type of cryptosystem involves trusted third party which certifies that a particular public key belongs to a specific person or entity only.

Encryption algorithm is complex enough to prohibit attacker from realizing the plaintext from the ciphertext and the encryption (public) key.

Though private and public keys are related mathematically, it is not feasible to calculate the private key from the public key.

RSA Algorithm

Rivest, Shamir & Adleman who first publicly described it in 1977.

It is an algorithm for public-key cryptography

RSA algorithm involves three steps

Key Generation

Encryption

Decryption

Keys generation algorithm:

Generate the RSA modulus (n)

Select two large primes, p and q.

Calculate n=p*q. For strong unbreakable encryption, let n be a large number, typically a minimum of 512 bits.

Find Derived Number (e)

Number e must be greater than 1 and less than (p − 1)(q − 1).

There must be no common factor for e and (p − 1)(q − 1) except for 1. In other words two numbers e and (p – 1)(q – 1) are coprime.

Form the public key

The pair of numbers (n, e) form the RSA public key and is made public.

Interestingly, though n is part of the public key, difficulty in factorizing a large prime number ensures that attacker cannot find in finite time the two primes (p & q) used to obtain n. This is strength of RSA.

Generate the private key

Private Key d is calculated from p, q, and e. For given n and e, there is unique number d.

Number d is the inverse of e modulo (p - 1)(q – 1). This means that d is the number less than (p - 1)(q - 1) such that when multiplied by e, it is equal to 1 modulo (p - 1)(q - 1).

This relationship is written mathematically as follows −

ed = 1 mod (p − 1)(q − 1)

The Extended Euclidean Algorithm takes p, q, and e as input and gives d as output.

Example

Let two primes be p = 7 and q = 13. Thus, modulus n = pq = 7 x 13 = 91.

Select e = 5, which is a valid choice since there is no number that is common factor of 5 and (p − 1)(q − 1) = 6 × 12 = 72, except for 1.

The pair of numbers (n, e) = (91, 5) forms the public key and can be made available to anyone whom we wish to be able to send us encrypted messages.

Input p = 7, q = 13, and e = 5 to the Extended Euclidean Algorithm. The output will be d = 29.

Check that the d calculated is correct by computing −

de = 29 × 5 = 145 = 1 mod 72

Hence, public key is (91, 5) and private keys is (91, 29).

Encryption

C = Pe mod n

the ciphertext C is equal to the plaintext P multiplied by itself e times and then reduced modulo n. This means that C is also a number less than n.

Returning to our Key Generation example with plaintext P = 10, we get ciphertext C = 105 mod 91

Decryption

Plaintext = Cd mod n

RSA Example

1. Select primes: p=17 & q=11

2. Compute n = pq =17×11=187

3. Compute ø(n)=(p–1)(q-1)=16×10=160

4. Select e : gcd(e,160)=1; (e,160)=1; choose e=7

5. Determine d: de=1 mod 160 and d < 160

Value is d=23 since 23×7=161= 10×160+1

6. Publish public key PU={7,187}

7. Keep secret private key PR={23,187}

RSA encryption/decryption

message M = 88 (88<187)

Encryption

C = 887 mod 187 = 11

Decryption

M = 1123 mod 187 = 88

RSA Analysis

The security of RSA depends on the strengths of two separate functions. The RSA cryptosystem is most popular public-key cryptosystem strength of which is based on the practical difficulty of factoring the very large numbers.

Encryption Function − It is considered as a one-way function of converting plaintext into ciphertext and it can be reversed only with the knowledge of private key d.

Key Generation − The difficulty of determining a private key from an RSA public key is equivalent to factoring the modulus n. An attacker thus cannot use knowledge of an RSA public key to determine an RSA private key unless he can factor n. It is also a one way function, going from p & q values to modulus n is easy but reverse is not possible.

Public key infrastructure (PKI)

Public keys are in open domain and seen as public pieces of data.

By default there are no assurances of whether a public key is correct, with whom it can be associated, or what it can be used for.

Thus key management of public keys needs to focus on assurance of purpose of public keys.

PKI provides assurance of public key.

It provides the identification of public keys and their distribution.

PKI has the following components:

Public Key Certificate, commonly referred to as ‘digital certificate’.

Private Key tokens.

Certification Authority.

Registration Authority.

Certificate Management System.

symmetric vs. Asymmetric encryption

Symmetric encryption

Faster

Require less computational power

Main weakness is key distribution. Because the same key is used to encrypt and decrypt information, that key must be distributed to anyone who would need to access the data

When these keys are shared over an unsecured connection, they are vulnerable to being intercepted by malicious third parties

Asymmetric encryption

solves the problem of key distribution by using public keys for encryption and private keys for decryption.

The key used for encryption can be shared securely over any connection

weakness: very slow by comparison to symmetric systems and require much more computing power as a result of their massively longer key lengths

.MsftOfcThm_Accent1_Fill { fill:#E48312; } .MsftOfcThm_Accent1_Stroke { stroke:#E48312; }

.MsftOfcThm_Accent1_Fill { fill:#99CB38; } .MsftOfcThm_Accent1_Stroke { stroke:#99CB38; }