Cryptography, Encryption, Hashes Cont.

Question 1

Symmetric Encryption Ingredients

Answer 1

Plaintext message

Encryption algorithm

Secret Key

Ciphertext (scrambled message)

Decryption algorithm

Question 2

Requirements for secure use of symmetric encryption

Answer 2

Strong encruption algorithm

Sender and receive have obtained copies of secret key in secure fashion and keep key secure

Question 3

Encryption/Decryption services

Answer 3

Integrity checking:
–no tampering

Authenticity:
–verified authorship

Authentication:
–not an imposter

Question 4

Attacks on Encryption

Answer 4

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

Question 5

Block ciphers

Answer 5

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)

Question 6

Asymmetric Encryption

Answer 6

Plaintext

Encryption algorithm

Public and private key

Ciphertext

Decryption key

Question 7

Digital Encryption Standard

Answer 7

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

Question 8

Triple DES (3DES)

Answer 8

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

Question 9

Advanced Encryption Standard

Answer 9

128 bit block, key lengths of 128, 192, 256

Question 10

Stream ciphers

Answer 10

Processes input elements continuously, producing output one element at a time

Output called keystream

Question 11

Authentication using symmetric encryption

Answer 11

symmetric encryption alone not sufficient for authentication even though only sender/receive share the key because the message may be reordered

Question 12

Message Authentication Method

Answer 12

(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

Question 13

Hash Function Requirements

Answer 13

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

Question 14

Public key cryptography:

Answer 14

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

Question 15

Security of encryption scheme depends on 2 factors

Answer 15

Length of the key
–not the number of keys

Computational work involved in breaking cipher

Question 16

Public Key encryption ingredients

Answer 16

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

Question 17

Steps of public key encryption

Answer 17

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

Question 18

Asymmetric Encryption Algorithms

Answer 18

RSA

Diffie-Hellman Key Agreement

Digital Signature Standard

Elliptic Curve Cyrptography

Question 19

Digital Signature

Answer 19

Encrypts hash code for authentication

Question 20

Public key certificates

Answer 20

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

Question 21

Methods in which public key encryption is used to protect a message

Answer 21

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

Question 22

Cryptanalysis

Answer 22

Analysis of the algorithm and data characteristics to discover the plaintext or key

Question 23

Cryptographic systems classified along three independent dimensions

Answer 23

Type of operations used for transforming plaintext to ciphertext

The number of keys used

The way in which plaintext is processed

Question 24

Feistel Cipher Structure

Answer 24

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

Question 25

DES

Answer 25

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.

Question 26

AES

Answer 26

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

Question 27

AES generally

Answer 27

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

Question 28

Forward substitute byte transformation

Answer 28

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

Question 29

Inverse substitute byte transformation

Answer 29

InvSubBytes uses S box Designed to be resistant simple mathematical function of the input

Question 30

Forward Shift Row Transformation

Answer 30

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

Question 31

Principle Elements of AES

Answer 31

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

Question 32

Inverse row transformation

Answer 32

InvShiftRows Circular shifts in opposite direction for each of last three rows, with 1 byte circular right shift for second row

Question 33

Forward Mix column transformation

Answer 33

MixColumns

Question 34

Forward add round key transformation

Answer 34

AddRoundKey 128 bits of State are bitwise XORed with 128 bits of round key

Question 35

Add round key transformation

Answer 35

Identical to forward add round key transformation

Question 36

AES key expansion

Answer 36

input 4 word key and produces linear array of 44 words

Question 37

Stream Cipher Structure

Answer 37

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

Question 38

RC4 algorithm

Answer 38

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

Question 39

Cipher Block 5 Modes of Operation

Answer 39

Electronic Code book ECB Cipher Block Chaining Cipher Feedback Output Feedback Counter

Question 40

Block Cipher Primitives

Answer 40

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

Question 41

Electronic Code book ECB

Answer 41

Each block of 64 plaintext bits is encoded independently using the same key Used for secure transmission of single values

Question 42

Cipher Block Chaining

Answer 42

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

Question 43

Cipher Feedback

Answer 43

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

Question 44

Output Feedback

Answer 44

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)

Question 45

Counter

Answer 45

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

Question 46

End to end encryption

Answer 46

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

Question 47

Modular Arithmetic

Answer 47

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

Question 48

Simple Hash Function

Answer 48

Input viewed as sequence of n-bit blocks Input processed one block at a time in iterative fashion to produce n-bit hash function

Question 49

SHA-1

Answer 49

Developed by NIST in 1993 Produces hash value of 160 bits

Question 50

SHA-2

Answer 50

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

Question 51

SHA-3

Answer 51

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

Question 52

HMAC

Answer 52

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

Question 53

RSA

Answer 53

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

Question 54

RSA Characteristics

Answer 54

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

Question 55

RSA Algorithm

Answer 55

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.

Question 56

RSA Example generating keys

Answer 56

1. Select two prime numbers, p = 17 and q = 11. 2. Calculate n = pq = 17 × 11 = 187. 3. Calculate φ(n) = (p – 1)(q – 1) = 16 × 10 = 160. 4. Select e s.t. e is relatively prime to φ(n) = 160 and less than φ(n); we choose e = 7. 5. 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

Question 57

4 Approaches to attacking RSA

Answer 57

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:

Question 58

Diffie and Hellman Key Exchange

Answer 58

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

Question 59

Diffie-Hellman Limitations

Answer 59

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

Question 60

Digital Signature Standard:

Answer 60

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

Question 61

Elliptic-Curve Cryptography (ECC)

Answer 61

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

Question 62

Hash Function Properties

Answer 62

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.