MIS risk and security project
Abdulellah1997
6-Cryptography.pptxCryptography
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; }
