Cryptography, Encryption, Hashes Cont. Flashcards
Symmetric Encryption Ingredients
Plaintext message
Encryption algorithm
Secret Key
Ciphertext (scrambled message)
Decryption algorithm
Requirements for secure use of symmetric encryption
Strong encruption algorithm
Sender and receive have obtained copies of secret key in secure fashion and keep key secure
Encryption/Decryption services
Integrity checking:
–no tampering
Authenticity:
–verified authorship
Authentication:
–not an imposter
Attacks on Encryption
Break a cipher:
Uncovering plaintext p from ciphertext c, or, alternatively, discovering the key
Brute-force attack
E.g., try all possible keys
Cryptanalysis
Analysis of the algorithm and data characteristics
Implementation attacks
E.g., side channel analysis
Social-engineering attacks
Block ciphers
Most common symmetric encryption algorithms
Processes plaintext input in fixed size blocks and produces a block of ciphertext of equal size for each plaintext block
Most common:
- -Data Encryption Standard (DES)
- -Triple DES
- -Advanced Encryption Standard (AES)
Asymmetric Encryption
Plaintext
Encryption algorithm
Public and private key
Ciphertext
Decryption key
Digital Encryption Standard
Adopted 1977, most widely used until recently
Plaintext block of 64 bits, key of 56 bits, produces ciphertext block of 64 bits
Algorithm hasn’t been exploited
Key length is too short, so can be guessed
Triple DES (3DES)
repeats DES three times
Advantages:
- -168 bit key length, so more secure, overcomes vulnerability of brute force attack
- -Underlying encryption is same as DES, so already subjected to scrutiny
Drawbacks:
- -sluggish due to three times as many calculations
- -64 bit block size, need larger for efficiency and security
Advanced Encryption Standard
128 bit block, key lengths of 128, 192, 256
Stream ciphers
Processes input elements continuously, producing output one element at a time
Output called keystream
Authentication using symmetric encryption
symmetric encryption alone not sufficient for authentication even though only sender/receive share the key because the message may be reordered
Message Authentication Method
(Note: these don’t encrypt messages so confidentiality isn’t guaranteed)
Message Authentication Code: generated with secret key
Secure Hash Functions aka one way hash
Hash Function Requirements
Compute message digest of data of any size
Fixed length output: 128-512 bits
Easy to compute H(m)
Given H(m), no easy way to find m --One-way function
Given m1, it is computationally infeasible to find m2≠m1 s.t. H(m2) = H(m1)
–Weak collision resistant
Computationally infeasible to find m1≠m2 s.t. H(m1) = H(m2)
–Strong collision resistant
Public key cryptography:
Asymmetric: two keys
- -Public for encryption, private for decryption
- -Private for signing and public for verification
Not necessarily more secure than symmetric encryption
Has not made symmetric encryption obsolete
—-due to overhead from public key encryption
Protocol to distribute public key still required and is no simpler than handshaking required for symmetric encryption key distribution
Security of encryption scheme depends on 2 factors
Length of the key
–not the number of keys
Computational work involved in breaking cipher
Public Key encryption ingredients
Plaintext: Readable message or datathat is fed into the algorithm
Encryption algorithm: Performs transformations on the plaintext
Public and private key: Pair of keys, one for encryption, one for decryption
Ciphertext: Scrambled message produced as output
Decryption key: Produces the original plaintext
Steps of public key encryption
Each user generates a pair of keys
Each user places one of the keys in a public register (public key) and keeps other key private
To send message, user encrypts with other user’s public key
When other user receives message, decrypts using private key
Asymmetric Encryption Algorithms
RSA
Diffie-Hellman Key Agreement
Digital Signature Standard
Elliptic Curve Cyrptography
Digital Signature
Encrypts hash code for authentication
Public key certificates
Solves problem of impersonators sending out public announcement of public key
Certificate consists of public key plus user ID of key owner, whole block signed by trusted third pary
Methods in which public key encryption is used to protect a message
Digital Signature
Public key certificates
Symmetric key exchange using public-key encryption
Digital Envelopes
- -Protects a message without needing to first arrange for sender and receiver to have the same secret key
- -Equates to the same thing as a sealed envelope containing an unsigned letter
Cryptanalysis
Analysis of the algorithm and data characteristics to discover the plaintext or key
Cryptographic systems classified along three independent dimensions
Type of operations used for transforming plaintext to ciphertext
The number of keys used
The way in which plaintext is processed
Feistel Cipher Structure
Structure for symmetric block encryption.
Half the data block is used to modify the other half and then halves are swapped.
Following parameters/design features:
- -Block size: larger means greater security
- -Key size: larger key size means greater security
- -Number of rounds: single round inadequate security
- -Subkey generation algorithm: greater complexity in algorithm leads to greater difficulty in cryptanalysis
- -Round function: greater complexity greater resistence to cryptanalysis
DES
The process of decryption with DES is essentially the same as the encryption
process. The rule is as follows: Use the ciphertext as input to the DES
algorithm, but use the subkeys K i in reverse order. That is, use K 16 on the first
iteration, K 15 on the second iteration, and so on until K 1 is used on the sixteenth
and last iteration.
AES
Not Feistel because processes entire data block in parallel using substitution and permutation
Key provided a input is expanded into an array of 44 32-bit words.
4 stages:
- -substitute bytes
- -shift rows (permutation)
- -mix columns
- -add round key
Structure:
- -cipher begins with Add Round Key stage (only time key is used)
- -9 rou ds that each include all four stages
- -10th round of three stages
AES generally
In 1997, the U.S. National Institute for Standards and Technology (NIST) put out a public call for a replacement to DES
It narrowed down the list of submissions to five finalists, and ultimately chose an algorithm (Rijndael) that is now known as the Advanced Encryption Standard (AES)
New (Nov. 2001) symmetric-key NIST standard, replacing DES
Processes data in 128 bit blocks
Key length can be 128, 192, or 256 bits
Forward substitute byte transformation
SubBytes
simple table lookup
Each individual byte of state is mapped to a new byte.
The leftmost 4 bits of the byte are used as row value and the rightmost 4 bits are used as a column value
Inverse substitute byte transformation
InvSubBytes
uses S box
Designed to be resistant simple mathematical function of the input
Forward Shift Row Transformation
ShiftRows
First row of State is not altered
Second row, 1 byte circular left shift performed
Third row, 2 byte ciruclar left shift performed
Third roww, 3 byte circular left shift is performed
Principle Elements of AES
Forward substitute byte transformation
Inverse substitute byte transformation
Forward Shift Row Transformation
Inverse row transformation
Forward Mix column transformation
Forward add round key transformation
Add round key transformation
AES key expansion
Inverse row transformation
InvShiftRows
Circular shifts in opposite direction for each of last three rows, with 1 byte circular right shift for second row
Forward Mix column transformation
MixColumns
Forward add round key transformation
AddRoundKey
128 bits of State are bitwise XORed with 128 bits of round key
Add round key transformation
Identical to forward add round key transformation
AES key expansion
input 4 word key and produces linear array of 44 words
Stream Cipher Structure
encrypts plaintext 1 byte at a time
key input into psuedorandom bit generator that produces a stream of 8 bit numbers that are random
Output of the generator is called a keystream
RC4 algorithm
Stream cipher designed in 1987 by Ron Rivest for RSA Security
USed in Secure Socket Layer/Transport Layer Security
Variable length key from 1 to 256 bytes is used to initialize 256 byte vector S.
S contains a permutation of all 8 bit number from 0 through 255
For encryption and decryption, a byte k is generated from S by selecting one of the 255 entries
Cipher Block 5 Modes of Operation
Electronic Code book ECB
Cipher Block Chaining
Cipher Feedback
Output Feedback
Counter
Block Cipher Primitives
Confusion:
- -An encryption operationwhere the relationship between the key and ciphertext is obscured
- -Achieved with substitution
Diffusion:
- -An encryption operation where the influence of one plaintext bit is spread over many ciphertext bits with the goal of hiding statistical properties of the plaintext
- -Achieved with permutation
Electronic Code book ECB
Each block of 64 plaintext bits is encoded independently using the same key
Used for secure transmission of single values
Cipher Block Chaining
The input to the encryption algoritm is the XOR of the next 64 bits of plaintext and the preceding 64 bits of ciphertext
Used for
- -general purpose block oriented transmission
- -authentication
Cipher Feedback
Input processed s bits at a time. Preceding ciphertet is used as input to the encryption algorithm to produce psuedorandom output whih is XORed with plaintext to produce next unit ciphertext
Used for
- -General purpose stream oriented transmission
- -Authentication
Output Feedback
Similar to CFB, except that the input to the encryption algorithm is the preceding DES output
Used for
–stream oriented transmission over noise channel (satellite communication)
Counter
Each block of plaintext is XORed with an encrypted counter. The counter is incremented for each subsequent block.
Used for
- -General purpose block oriented transmission
- -Useful for high speed requirements
Advantages
- -hardware efficiency
- -software efficiency
- -preprocessing
- -random access
- -provable security
- -simplicity
End to end encryption
Two keys:
- -Session key: all user data encrypted with one time session key for the duration of logical connection
- -Permanent key: used between entities for the purpose of distributing session keys
Configuration:
- -key distribution center: determines which systems allowed to communicate with each other
- -security service module: performs end to end encryption and obtains session keys on behalf of users
Modular Arithmetic
Public key algorithms are based on modular arithmetic
Modular addition
- -Addition modulo (MOD) M
- -E.g., M=10, for k=2, its inverse is k-1=8 because 2+8 MOD 10 = 0
Modular multiplication
- -Multiplication modulo M
- -E.g., M=10, 3 and 7 are inverse of each other because 3×7 MOD 10 = 1
- -But 2, 5, 6, 8 do not have inverse when M=10
- -Use Euclid’s algorithm to find inverse. Given x, n, it finds y such that x×y mod n = 1
Modular exponentiation
- -x^y mod n = x^(y mod ø(n)) mod n
- -if y = 1 mod ø(n) then x^y mod n = x mod n
Simple Hash Function
Input viewed as sequence of n-bit blocks
Input processed one block at a time in iterative fashion to produce n-bit hash function
SHA-1
Developed by NIST in 1993
Produces hash value of 160 bits
SHA-2
Produced in 2002
Produces hash value lengths of 256, 384, 512 bits
For SH-512:
- -1 Append padding bits to get length congruent to 896 modulo 1024
- -2 Append length (block of 129 bits)
- -3 Initialize Hash Buffer (512 bit buffer to hold intermediate and final results)
- -4 Process message in 1023 bit (128 word) blocks
- -5 Output
SHA-3
Competition to develop announced in 2007
Must be possible to replace SHA-2 with SHA-3 in any application by drop in substitution. Hash value lengths 224, 256, 384, 512
Must preserve online nature of SHA-2
HMAC
Hash code approach to message authentication
Design objectives:
- -Use, without modification, available hash functions
- -Allow for easy replaceability of embedded hash function
- -Preserver original performance of hash functions
- -Use and handle keys in a simple way
- -Have a well-understood cryptographic analysis of the strength of the authentication mechanism based on reasonable assumptions on the embedded ash function
RSA
Widely used, and one of the first (1977)
Support both public key encryption and digital signature
Assumption/theoretical basis:
–Factoring a very large integer is hard
RSA Characteristics
Variable key length
Variable plaintext block size
- -Plaintext treated as an integer, and must be “smaller” than the key
- -Ciphertext block size is the same as the key length
RSA Algorithm
This summarizes the RSA algorithm.
Begin by selecting two prime numbers, p and q and calculating their product n, which is the modulus for encryption and decryption.
Next, we need the quantity totient n, which is (p-1)*(q-1)
Then select an integer e that is relatively prime to φ(n) [i.e., the greatest common divisor of e and φ(n) is 1].
Finally, calculate as the multiplicative inverse of e, modulo φ(n).
The public key is (e,n), and the private key is (d,n)
For encryption, suppose Alice has published its public key and Bob wishes to send the message M to Alice. Then B calculates C = Me (mod n) and transmits C.
For decryption, on receipt of this ciphertext, Alice decrypts by calculating M = Cd (mod n). The property of RSA guarantees that only Alice can decrypt the message she has the private key that is paired with the public key used to encrypt the message.
RSA Example generating keys
- Select two prime numbers, p = 17 and q = 11.
- Calculate n = pq = 17 × 11 = 187.
- Calculate φ(n) = (p – 1)(q – 1) = 16 × 10 = 160.
- Select e s.t. e is relatively prime to φ(n) = 160 and less than φ(n); we choose e = 7.
- Determine d such that de mod 160 = 1 and d < 160. The correct value is d = 23, because 23 × 7 = 161 = (1 × 160) + 1.
The resulting keys are public key PU = {7, 187} and private key PR = {23, 187}. The example shows the use of these keys for a plaintext input of M = 88. For encryption, we need to calculate C = 887 mod 187
4 Approaches to attacking RSA
Brute force: trying all possible private keys
Mathematical attacks: factoring the product of two primes
- -factor n into its two prime factors
- -determine φ(n) directly without p and q
- -determine d directly without φ(n)
Timing attacks: depend on running time of algorithm
–countermeasures include constant exponentiation time, random delay, blinding
Chosen ciphertext attacks:
Diffie and Hellman Key Exchange
First published public-key algorithm
The purpose of the algorithm is to enable two users to exchange a secret key securely that can then be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of the keys.
The security of the Diffie-Hellman key exchange lies in the fact that, while it is relatively easy to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms. For large primes, the latter task is considered infeasible.
By Diffie and Hellman in 1976 along with the exposition of public key concepts
Used in a number of commercial products
Practical method to exchange a secret key securely that can then be used for subsequent encryption of messages
Security relies on difficulty of computing discrete logarithms
Diffie-Hellman Limitations
Expensive exponential operation
–DoS possible
The scheme itself cannot be used to encrypt anything – it is for secret key establishment
No authentication, so you cannot sign anything
–man-in-the-middle attack possible
Digital Signature Standard:
Makes use of SHA-1 and the Digital Signature Algorithm (DSA)
Originally proposed in 1991, revised in 1993 due to security concerns, and another minor revision in 1996
Cannot be used for encryption or key exchange
Uses an algorithm that is designed to provide only the digital signature function
Elliptic-Curve Cryptography (ECC)
Equal security for smaller bit size than RSA
Seen in standards such as IEEE P1363
Confidence level in ECC is not yet as high as that in RSA
Based on a mathematical construct known as the elliptic curve
Hash Function Properties
Compute message digest of data of any size
Fixed length output: 128-512 bits
Easy to compute H(m)
Given H(m), no easy way to find m --One-way function
Given m1, it is computationally infeasible to find m2≠m1 s.t. H(m2) = H(m1)
–Weak collision resistant
Computationally infeasible to find m1≠m2 s.t. H(m1) = H(m2)
–Strong collision resistant
Note:
a hash function that is strong collision resistant is automatically weak collision resistant.
