Encryption Flashcards
What are the components of symmetric encryption?
Plaintext input Encryption algorithm Transmitted Ciphertext Decryption algorithm Plaintext output
What are two ways to attack symmetric encryption?
Brute-force
Cryptographic analysis
What is AES?
Advanced Encryption Standard, which is a symmetric encryption algorithm
Plaintext block size of 128
Ciphertext block size 128
Key size 128, 192, 256
Number of alternative keys:
2^128
2^192
2^256
should have a security strength equal to or better than 3DES and significantly improved efficiency
NIST specified that AES must be a symmetric block cipher with a block length of 128 bits and support for key lengths of 128, 192, and 256 bits.
AES is now widely available in commercial products
What are other ways to attack encryption?
Cryptoanalysis
Brute force attacks
Implementation attacks
Social engineering attacks
What are the requirements for a hash function?
Hash functions should satisfy the following:
Easy to compute
Completely infeasible to find the original message - one-way hash function
Given the message m1, it is computationally infeasible to find m2 from m1 such that they have the very same hash value h(m1) = h(m2). IT MUST BE WEAK COLLISION-RESISTANT
Strong collision-resistant
How does AES work?
Plain text block is represented as a square matrix
First, XOR happens with Add Round Key (also represented as square matrix)
Then commences multiple rounds (xNr - 1) of encryption For each round, there are several operations that represent substitution and permutation Encryption round Sub bytes (using s-box) Shift rows - simple permutation row by row Mix columns - substitution per column Add round key (XOR with this key) - Last Round - sub bytes (see above) - shift rows (see above) - add round key (see above) - Cipher text output
The above steps must be reversible:
XOR operation is reversible
Substitution, shifts, and mixes can be reversed using an inverse function
AES each round:
Data is represented as state array
Results of each operation stored in state array
Each round involves substitution and permutation and use of encryption key
What is the forward substitute byte transformation in AES?
The forward substitute byte transformation, called SubBytes, is a simple table lookup. AES defines a matrix of byte values, called an S-box (see Table 20.2a), that contains a permutation of all possible 256 8-bit values. Each individual byte of State is mapped into a new byte in the following way: The leftmost 4 bits of the byte are used as a row value, and the rightmost 4 bits are used as a column value. These row and column values serve as indexes into the S-box to select a unique 8-bit output value.
What is the forward shift row transformation?
For the forward shift row transformation, called ShiftRows, the first row of State is not altered. For the second row, a 1-byte circular left shift is performed. For the third row, a 2-byte circular left shift is performed. For the third row, a 3-byte circular left shift is performed
What is the forward mix column tranformation?
operates on each column individually. Each byte of a column is mapped into a new value that is a function of all 4 bytes in the column. The mapping makes use of equations over finite fields.
What is the forward add round key transformation?
he 128 bits of State are bitwise XORed with the 128 bits of the round key. The operation is viewed as a column-wise operation between the four bytes of a State column and one word of the round key; it can also be viewed as a byte-level operation
What is RC4?
one of the most popular symmetric stream cipher (which processes the input elements continuously producing one element at a time)
It is a variable-key-size stream cipher with byte-oriented operations
based on the use of a random permutation
the cipher can be expected to run very quickly in software
used in the SSL/TLS (Secure Sockets Layer/Transport Layer Security) standards that have been defined for communication between Web browsers and servers
How it works:
A variable-length key of from 1 to 256 bytes (8 to 2048 bits) is used to initialize a 256-byte state vector S, with elements S[0], S[1], …, S[255]
S contains a permutation of all 8-bit numbers from 0 through 255. For encryption and decryption, a byte k (see Figure 2.3b) is generated from S by selecting one of the 255 entries in a systematic fashion
As each value of k is generated, the entries in S are once again permuted.
for a key of length keylen bytes, the first keylen elements of T are copied from K and then K is repeated as many times as necessary to fill out T.
Next we use T to produce the initial permutation of S. This involves starting with S[0] and going through to S[255], and, for each S[i], swapping S[i] with another byte in S according to a scheme dictated by T[I]
Once the S vector is initialized, the input key is no longer used. Stream generation involves cycling through all the elements of S[i], and, for each S[i], swapping S[i] with another byte in S according to a scheme dictated by the current configuration of S. After S[255] is reached, the process continues, starting over again at S[0]
Strength of RC4:
the problem is not with RC4 itself but, the way in which keys are generated for use as input to RC4
can be remedied in WEP by changing the way in which keys are generated
What is RSA?
a public-key encryption scheme/algorithm
Supports both public-key encryption and digital signatures
block cipher in which the plaintext and ciphertext are integers between 0 and for some n.
Theoretical basis: factoring a very large number is hard
Characteristics:
- variable key length
- variable plaintext block size
- ciphertext block is the same as the keylength
- plaintext treated as an integer and must be smaller than the key
How does it work?
- The public key is e and n
The private key is d and n
- Select p,q prime numbers
- The public key e and the private key d are multiplicative inverses of each other
- To encrypt a message: Raise m (message) to the power of e (public key) mod n ; all equal to c
To decrypt a message:
- m = c ^ d mod n = to get original message - same as (m ^ e*d) mod n
ex) Plaintext represented as 88 p=17, q=11 ; p * q = 187 = n totient(187) = 16 * 10 = 160 We select 7 which is relatively prime to totient(n) = 160
The private key d is the multiplicative inverse e mod totient(n)
The multiplicative inverse of 7 mod 160 is 23 ; therefore the private key is 23
Public keys => 7, 187
Private keys => 23, 187
Cipher text is 11 from plaintext 88
Why it works/secure:
- factoring large numbers is hard (with at least 512 bits)
Issues with RSA:
- for the same key, the plaintext is always mapped to a specific ciphertext
- special case plaintexts produce the same exact ciphertexts no matter what keytexts
- Transforming a ciphertext into another leads to predictable transformation to plaintext
Elliptic Curve Cryptography
This is a public key encryption algorithm
Equal security for smaller bit sizes compared to RSA
Not as high of a confidence level compared to RSA
Based on a mathematical concept known as the elliptic curve
Diffie-Hellman Key Exchange
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.
depends for its effectiveness on the difficulty of computing discrete logarithms
ex) two prime numbers
q = 353
pi = 3 (less than q and must be primitive root)
compute public keys
A -> YA = 3^97 mod 353 = 40
B -> YB = 3^233 mod 353 = 248
Public keys = 40, 248
Exchange and compute secret key:
For A: K = YB^XA mod 353 = 248^97 mod 353 = 160
For B: K = YA^XB mod 353 = 40^233 mod 353 = 160
Share the secret key in common -> 160
Limitations:
- expensive exponential operation
- scheme itself can’t be used to encrypt anything
- no authentication, so you can’t sign anything
RSA example: given p=3 q=11
n = ?
totient(n) =
Assume e=7
What is d? d=?
What is the public key? e, n
What is the private key? d, n
Message m = 2
What is the encryption of m?
What is the formula used to decrypt m?
n = 33
totient n = 20
d = 3
because totient n = 20 thus
7 * 3 = 21 = (1X 20) + 1 ( de mod 20 = 1)
public key => 7, 33
private key => 33, 3
Encryption of m:
2^7 mod 33 = 29
Decryption of m:
29^3 mod 33 = 2
Euclid’s algorithm:
multiplicative inverse of 3 mod 17
6
Totient function example:
if n = 21, what is totient n?
totient n = 12
Digital Signature Standard
makes use of SHA-1 and the Digital Signature Algorithm
Proposed in 1991 and revised in 1993
Cannot be used for encryption or key exchange
Uses an algorithm designed only for digital signature function
List the requirements for a block cipher scheme
Use substitution to achieve confusion
Use permutation to achieve diffusion
Use a few rounds of both with combo of substitution and permutation
Data Encryption Standard
Published in 1977 and standardized in 1979
64 bit M and 64 bit Cypher
56 bit key
Every 8th bit is a parity bit
High-level overview:
Initial permutation at the beginning
Final permutation at the end
16 rounds of operations
16 subkeys are generated, one for each round
Use the Ciphertext as input to DES
Then the subkeys are used in reverse order
Use K16 for the first round of decryption
Use K15 for the second round of decryption
And so on
DES is achieved through bit permutation (changing the position of the bits)
Each DES round:
Each DES round has the same operations
Uses a different round key (subkey)
Each DES round takes an input of a cipher text from the previous round
Each DES round outputs cipher text for the next round
The input is divided into the left half and the right half
The output right half is just the left half of the input
The right half of the output is the result of XORing the left half of the input
The Mangler function -
Takes 32 bit input right half
Expands it to 48 bit
XOR it with 48 bit per round key
Then uses s-boxes to substitute the 48 bit value into a 32 bit value
Security and Effectiveness:
Key space is too small 2^56
S-box design criteria has been kept secret
Highly resistent to crypto-analysis
What is the Mangler function?
performs both substitution and permutation for DES
Performs processing for each round of encryption
Takes the right half of the input and expands the 32 bit data into 48 bit data
Then XOR with per round key
48 bit value is substituted to a 32 bit value
The result is then permutated
What is the S-box?
Substitute and Shrink
S-box substitutes 6-bit value with 4-bit value from a pre-defined table
Middle 4 bits index into the columns of the table
Outer 2 bits are used to index into the rows of the table
The value in a table entry is the output of the 4 bit value
The tables are pre-defined and there are 8 such tables in DES
Triple DES vs DES
Standard to overcome this shortcoming is to run DES 3 times, which is called Triple DES
results in 112 bit keyspace
Effective lengths could be 56, 112, 168
The encryption process uses keys K1 - K3 in that order
Encrypts - decrypts - and encrypts again
The decryption process uses keys in the reverse order K3 -> K1
Decryption - encryption - decryption again
What is the electronic code book (ECB)?
Mechanism for breaking down large messages (larger than 256 bits)
Large message broken down into fixed sized 64 bit blocks
It also pads the last block so that it’s also 64 bit
Each block is encrypted using the same key
There is a corresponding cipher text block for each original block
What are the problems with ECB?
If two message blocks are the same, there corresponding cipher blocks are also the same due to encryption with the same key
Lacks basic protection against integrity attacks on the ciphertext on the message level
- blocks could be subbed out or rearranged
What is CipherBlock Chaining?
Mechanism for sending long messages that solves the problems of ECB
CBC more secure than ECB
The input to the encryption algorithm is the result of XORing the previous block from the previous step
To encrypt the first block, an IV (initialization vector) is used and we XOR IV with the plain text block to produce the first cipher text block
This solves the problem for identical plain text blocks because the cipher text blocks are unlikely to be the same
IV must be known to both sender and receiver
CBC needs to separated keys for confidentiality and integrity
