lOMoARcPSD|38071713
Computer security Module 2
Information Systems Security (Mahatma Gandhi University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Module 2
Advanced Encryption Standard (AES)
Symmetric block cipher published by National Institute of Standards and Technology (NIST) in December
2001.
Intended to replace DES and 3DES
NIST Evaluation Criteria
Security: The effort to crypt analyze an algorithm.
Cost: The algorithm should be practical in a wide range of applications.
Algorithm and Implementation Characteristics: Flexibility, simplicity etc.
Final evaluation criteria
1. General Security
2. Software Implementations
3. Hardware Implementations
4. Restricted-Space Environments
5. Attacks on Implementations
6. Encryption vs. Decryption
7. Key Agility
8. Potential for Instruction-Level Parallelism
9. Other versatility and Flexibility
AES Cipher
an iterative rather than Feistel cipher
processes data as block of 4 columns of 4 bytes
operates on entire data block in every round
designed to have:
resistance against known attacks
speed and code compactness on many CPUs
design simplicity
AES Structure
processes data as state array
Encryption/Decryption consists of 10 rounds of processing for 128-bit keys, 12 rounds for 192-bit keys, and
14 rounds for 256-bit keys.
Except for the last round, all other rounds are identical.
Each round of processing includes
1. Byte substitution (1 S-box; byte to byte substitution)
2. Shift rows (permutation of bytes)
3. Mix columns (substitution using matrix multiply of groups)
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
4. Add Round Key (XOR state with a portion of expanded K)
The order in which these four steps are executed is different for encryption and decryption
The input is a single 128 bit block both for decryption and encryption and is known as the in matrix.
This block is copied into a state array which is modified at each stage of the algorithm and then copied to an
output matrix.
The key is expanded into an array of 44/52/60 words of 32 bits each (the w matrix).
Input key is expanded into an array of 4 different words serve as a key for each round
AddRoundKey
Adds a key word with each state column matrix.
Each column in the state matrix is XORed with a different word.
Proceeds one column at a time.
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Byte Substitution
a simple substitution of each byte
uses S-box to perform a byte-by-byte substitution of State
uses one table of 16x16 bytes containing a permutation of all 256 8-bit values
each byte of state is replaced by byte indexed by row (left 4-bits) & column (right 4-bits)
eg. byte {95} is replaced by byte in row 9 column 5.
Shift Rows
a circular byte shift in each row
1st row is unchanged
2nd row does 1 byte circular shift to left
3rd row does 2 byte circular shift to left
4th row does 3 byte circular shift to left
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Mix Columns
operates at the column level;
It transforms each column of the state to a new column.
AES Key Expansion
create round keys for each round,
takes key and expands into array of 44/52/60 32-bit words
start by copying key into first 4 words
AES Decryption
AES decryption is not identical to encryption since steps done in reverse.
Decryption algorithm uses the expanded key in reverse order.
All functions are easily reversible and their inverse form is used in decryption
Analysis of AES
The AES is secure against all known attacks.
Various aspects of its design incorporate specific features that help provide security against specific attacks.
There are apparently no known attacks on AES.
Multiple Encryption & DES
Double-DES
could use 2 DES encrypts on each block
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
C = EK2(EK1(P))
P = D(K1, D(K2, C))
Encryption sequence: E-E
Decryption sequence: D-D
Triple-DES with Two-Keys
hence must use 3 encryptions and decryptions
Encryption sequence: E-D-E
Decryption sequence: D-E-D
but can use 2 keys with E-D-E sequence
C = EK1(DK2(EK1(P)))
P = D(K1, E(K2, D(K1, C)))
no current known practical attacks
Triple-DES with Three-Keys
although are no practical attacks on two-key Triple-DES have some indications
can use Triple-DES with Three-Keys to avoid even these
C = EK3(DK2(EK1(P)))
P=DK1 (EK2 (EK3 (C)))
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Modes of Operation
block ciphers encrypt fixed size blocks
eg. DES encrypts 64-bit blocks with 56-bit key
NIST defines 5 possible modes to cover a wide variety of applications
1. Electronic CodeBook Mode (ECB)
2. Cipher Block Chaining Mode (CBC)
3. Cipher FeedBack Mode (CFB)
4. Output FeedBack Mode (OFB)
5. CounTeR Mode(CTR)
can be used with any block cipher
have block and stream modes
Electronic Code Book (ECB)
message is broken into independent blocks which are encrypted
each block is a value which is substituted, like a codebook,
each block is encoded independently of the other blocks
Ci = EK1(Pi)
uses: secure transmission of single values
Advantages and Limitations of ECB
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
message repetitions may show in cipher text
main use is sending a few blocks of data
Cipher Block Chaining (CBC)
message is broken into blocks
linked together in encryption operation
each previous cipher blocks is chained with current plaintext block,
use Initial Vector (IV) to start process
Ci = EK1(Pi XOR Ci-1)
Ci-1 = IV
uses: bulk data encryption, authentication
Advantages and Limitations of CBC
a cipher text block depends on all blocks before it
any change to a block affects all following cipher text blocks
need Initialization Vector (IV)
which must be known to sender & receiver
hence IV must either be a fixed value
or must be sent encrypted in ECB mode before rest of message
Stream Modes of Operation
block modes encrypt entire block
may need to operate on smaller units
real time data
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
convert block cipher into stream cipher
cipher feedback (CFB) mode
output feedback (OFB) mode
counter (CTR) mode
use block cipher as some form of pseudo-random number generator
Cipher Feed Back (CFB)
message is treated as a stream of bits
added to the output of the block cipher
result is feedback for next stage
standard allows any number of bit (1,8, 64 or 128 etc) to be feed back
denoted CFB-1, CFB-8, CFB-64, CFB-128 etc
Ci = Pi XOR EK1(Ci-1)
C-1 = IV
Advantages and Limitations of CFB
appropriate when data arrives in bits/bytes
most common stream mode
encryption mode used at both ends
Output Feed Back (OFB)
output of cipher is added to message
output is then feed back
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
feedback is independent of message
So feedback can be computed in advance
Ci = Pi XOR Oi
Oi = EK1(Oi-1)
Oi-1 = IV
Advantages and Limitations of OFB
Encryption and decryption of blocks can be done in parallel
Counter (CTR)
must have a different key & counter value for every plaintext block (never reused)
uses: high-speed network encryptions
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Advantages and Limitations of CTR
efficiency
can do parallel encryptions in h/w or s/w
can preprocess in advance of need
random access to encrypted data blocks
provable security (good as other modes)
But must ensure never reuse key/counter values, otherwise could break.
STREAM CIPHERS
Start with a secret key
process message bit by bit (as a stream)
have a pseudo random keystream
Combine the key stream with the plaintext to produce the cipher text (typically by XOR)
Ci = Mi XOR StreamKeyi
but must never reuse stream key
otherwise can recover messages
Stream Cipher Properties
some design considerations are:
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
long period with no repetitions
statistically random
depends on large enough key
properly designed, can be as secure as a block cipher
simpler & faster
RC4
A symmetric key encryption algorithm invented by Ron Rivest
Variable key size(1-256 bytes), byte-oriented stream cipher
Normally uses 64 bit and 128 bit key sizes.
Cryptographically very strong and easy to implement
Used in
SSL/TLS (Secure Socket Layer, transport layer security) between web browsers and servers, IEEE
802.11 wirelss LAN stds etc.
Consists of 2 parts:
Key Scheduling Algorithm (KSA)
Pseudo-Random Generation Algorithm (PRGA):
The KSA
Generate State array
Use the secret key to initialize and permutation of state array S, done in two steps
A variable-length key from 1 to 256 bytes is used to initialize a 256-byte state array S, with elements S [0],S[1],
… ,S[255].
At all times, S contains a permutation of all 8-bit numbers from 0 through 255.
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
The PRGA
Generate key stream, XOR key stream with the data to generate encrypted stream
Decryption using RC4
Use the same secret key as during the encryption phase.
Generate keystream by running the KSA and PRGA.
XOR keystream with the encrypted text to generate the plain text.
RC4 Security
claimed secure against known attacks
since RC4 is a stream cipher, must never reuse a key
Confidentiality using Symmetric Encryption
Traditionally symmetric encryption is used to provide message confidentiality.
Placement of Encryption
have two major placement alternatives
link encryption
encryption occurs independently on every link
requires many devices
end-to-end encryption
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
encryption occurs between original source and final destination
need devices at each end with shared keys
Encryption function of the front-end processor (FEP)
A front end processor (FEP), is a small-sized computer which interfaces the host computer to a number of
networks or a number of peripheral devices.
On the host side, the FEP accepts packets. The user data portion of the packet is encrypted, while the packet
header bypasses the encryption process. The resulting packet is delivered to the network.
In the opposite direction, for packets arriving from the network, the user data portion is decrypted and the
entire packet is delivered to the host.
when using end-to-end encryption must leave headers in clear
so network can correctly route information
hence although contents protected, traffic pattern flows are not
ideally want both at once
end-to-end encryption protects data contents over entire path and provides authentication
link encryption protects traffic flows from monitoring
can place encryption function at various layers in OSI Reference Model
link encryption occurs at layers 1 or 2
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
end-to-end can occur at layers 3, 4, 6, 7
Traffic Confidentiality
Is related to the monitoring of communications flows between parties
link encryption approach
Network-layer headers (e.g., frame or cell header) are encrypted, reducing the opportunity for traffic analysis.
traffic padding
An effective countermeasure to traffic analysis
Traffic padding produces cipher text output continuously, even in the absence of plaintext.
A continuous random data stream is generated. When plaintext is available, it is encrypted and transmitted.
When input plaintext is not present, random data are encrypted and transmitted.
Key Distribution
symmetric schemes require both parties to share a common secret key
issue is how to securely distribute this key
system failure due to a break in the key distribution scheme
given parties A and B have various key distribution alternatives:
1. A can select key and physically deliver to B
2. third party can select & deliver key to A & B
3. if A & B have communicated previously can use previous key to encrypt a new key
4. if A & B have secure communications with a third party C, C can deliver key between A & B
Key Hierarchy
typically have a hierarchy of keys
session key
temporary key
used for encryption of data between users
for one logical session then discarded
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
master key
used to encrypt session keys
shared by user & key distribution center
Key Distribution Scenario
1. A issues a request to the KDC for a session key to protect a logical connection to B. The message includes the
identity of A and B and a unique identifier, N1, for this transaction.
2. The KDC responds with a message encrypted using Ka Thus, A is the only one who can successfully read the
message. The message includes two items intended for A,
A one-time session key(Ks) to be used for the session
The original request message.
The message includes two items intended for B;
The one-time session key, Ks to be used for the session
An identifier of A (e.g., its network address), IDA
These two items are encrypted with Kb (the master key that the KDC shares with B). They are to be sent to B to
establish the connection and prove A's identity.
3. A stores the session key for use in the upcoming session and forwards to B the information that originated at
the KDC for B, namely, E(Kb, [Ks || IDA]).
4. Using the newly minted session key for encryption, B sends a identifier N2, to A.
5. Also using Ks, A responds with f (N2), where f is a function that performs some transformation on N2 (e.g.,
adding one).
Key Distribution Issues
hierarchies of KDC’s required for large networks, but must trust each other
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
session key lifetimes should be limited for greater security
use of automatic key distribution on behalf of users,
use of decentralized key distribution
controlling key usage
Automatic Key Distribution
1. A issues a request (ID of A and a unique identifier N1) to B for a session key
2. B responds with a message that is encrypted using the shared master key (MKm).The response includes the session
key selected by B, an identifier of B, the value f(N1), and another identifier, N2.
3. Using the new session key, A returns f(N2) to B.
Controlling Key Usage
Different types of session keys e.g.,
Data encrypting key: for general communication across network
PIN-encrypting key: for PIN used in electronic funds
File encrypting key: for encrypting files stored on a publicly accessible location
Random Numbers
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
many uses of random numbers in cryptography
nonces in authentication protocols to prevent replay
session keys
public key generation
keystream for a one-time pad
in all cases its critical that these values be
statistically random
with uniform distribution, independent
Pseudorandom Number Generators (PRNGs)
algorithmic technique to create “random numbers”
although not truly random
can pass many tests of “randomness”
Using Block Ciphers as Stream Ciphers
can use block cipher to generate numbers
Blum Blum Shub Generator
based on public key algorithms
use least significant bit from iterative equation
Introduction to Number Theory
Prime Numbers
prime numbers only have divisors of 1 and self
Prime Factorisation
to factor a number n is to write it as a product of other numbers: n=a x b x c .
the prime factorisation of a number n is written as a product of primes
e.g. 91=71x131, 300=22x31x52
Relatively Prime Numbers
two numbers a, b are relatively prime if have no common divisors apart from 1
eg. 8 & 15 are relatively prime since factors of 8 are 1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only
common factor
GCD
can determine the greatest common divisor of any numbers by Multiplying the common prime factors with
least power
eg. 300=22x31x52 18=21x32 hence
GCD (18,300) =21x31=6
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Fermat's Theorem
ap-1 mod p = 1
where p is prime and gcd (a,p)=1
also known as Fermat’s Little Theorem
useful in public key and primality testing
Example:
ap-1 ≡ 1 (mod p)
Euler Totient Function ø(n)
when doing arithmetic modulo n
complete set of residues is: 0..n-1
reduced set of residues is those numbers which are relatively prime to n
for example n=10, when doing arithmetic modulo n
complete set of residues is(0….n-1)= {0,1,2,3,4,5,6,7,8,9}
reduced set of residues is numbers which are relatively prime to n= {1,3,7,9}
number of elements in reduced set of residues is called the Euler Totient Function ø(n)
to compute ø(n) need to count number of elements to be excluded
in general need prime factorization, but
for p (prime) ø(p) = p-1
for p.q (p,q prime) ø(p.q) = (p-1)(q-1)
eg.
ø(37) = 36
ø(21) = (3–1)×(7–1) = 2×6 = 12
Euler's Theorem
states that for every a and n that are relatively prime:
aø(n) ≡ 1 (mod n)
eg.
a=3;n=10; ø(10)=4;
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Hence 34 = 81 = 1 mod 10
a=2;n=11; ø(11)=10;
hence 210 = 1024 = 1 mod 11
Primality Testing
any positive odd integer n ≥ 3 can be expressed as
n - 1 = 2kq with k > 0, q odd
Miller-Rabin Algorithm
a test based on Fermat’s Theorem
The procedure TEST takes a candidate integer as input and returns the result composite if it is definitely not
a prime, and the result inconclusive if may or may not be a prime.
Example 1: n=29
Then (n - 1) = 28 = 22(7) = 2kq.
First, let us try a=10 .compute 107 mod 29 = 17, so we continue the test.
The next calculation finds that (107)2 mod 29 = 28, and the test returns inconclusive (i.e., 29 may be prime).
Let’s try again with a=2 .We have the following calculations: 27 mod 29 = 12; 214 mod 29 = 28; and the test
again returns inconclusive.
If we perform the test for all integers in the range 1 through 28, we get the same inconclusive result.
Example 2: n = 13 * 17 = 221.
Then n-1 =220 = = 22(55) = 2kq.
Let us try a=5. Then we have 555 mod 221 = 112, which is neither 1 nor 220
(555)2 mod 221 = 168 .the test returns composite, indicating that 221 is definitely a composite number.
Suppose we had selected a=21. Then we have 2155 mod 221 = 200;
(2155)2 mod 221 = 220; and the test returns inconclusive, indicating that 221 may be prime.
In fact, of the 218 integers from 2 through 219, four of these will return an inconclusive result, namely 21, 47,
174, and 200.
Chinese Remainder Theorem
used to speed up modulo computations
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
if working modulo a product of numbers
– eg. mod M = m1m2..mk
• Chinese Remainder theorem work in each modulus mi separately
• Since computational cost is proportional to size, this is faster than working in the full modulus M.
can implement CRT in several ways
to compute A (mod M)
– First compute all ai = A mod mi separately
– determine constants ci below, where Mi = M/mi
– Then combine results to get answer using:
Public Key Cryptography and RSA
Public Key Cryptography
asymmetric
uses two keys – a public & a private key
developed to address two key issues:
key distribution – how to have secure communications in general without having to trust a KDC with
your key
digital signatures – how to verify a message comes intact from the claimed sender
public-key/two-key/asymmetric cryptography involves the use of two keys:
a public-key, which may be known by anybody, and can be used to encrypt messages, and verify
signatures
a private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures.
1. Each user generates a pair of keys to be used for the encryption and decryption of messages.
2. Each user places one of the two keys in a public register or other accessible file. This is the public key. The
companion key is kept private. Each user maintains a collection of public keys obtained from others.
Public-Key Cryptosystems
Encrypting a message, using the sender’s private key. This provides the digital signature.
Encrypt again, using the receiver’s public key.
Final cipher text can be decrypted only by the intended receiver, who alone has the matching private key.
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
Public-Key Characteristics
Public-Key algorithms rely on two keys where:
it is computationally infeasible to find decryption key knowing only algorithm & encryption key
it is computationally easy to en/decrypt messages when the relevant (en/decrypt) key is known
either of the two related keys can be used for encryption, with the other used for decryption (for some
algorithms)
RSA
by Rivest, Shamir & Adleman of MIT in 1977
best known & widely used public-key scheme
Is a block cipher in which the plaintext and cipher text are integers between 0 and n - 1 for some n.
Uses large integers (e.g. 512, 1024 bits).
RSA makes use of an expression with exponentials.
RSA Key Setup
Each user generates a public/private key pair by:
selecting two large primes at random p, q
Computing their system modulus n= p. q
selecting the random encryption key e
where 1<e<ø(n), gcd (e, ø(n))=1
note ø(n)=(p-1)(q-1)
solve following equation to find decryption key d
e.d=1 mod ø(n) and 0≤d≤n
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
publish their public encryption key: PU={e,n}
keep secret private decryption key: PR={d,n}
RSA En/decryption
to encrypt a message M the sender:
obtains public key of recipient PU={e,n}
computes: C = Me mod n, where 0≤M<n
to decrypt the ciphertext C the owner:
uses their private key PR={d,n}
computes: M = Cd mod n
RSA Example - Key Setup
1. Select primes: p=17 & q=11
2. Compute n = pq =17 x 11=187
3. Compute ø(n)=(p–1)(q-1)=16 x 10=160
4. Select e: gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160 Value is d=23
6. Publish public key PU={7,187}
7. Keep secret private key PR={23,187}
RSA Example - En/Decryption
sample RSA encryption/decryption is:
given message M = 88
encryption:
C = 887 mod 187 = 11
decryption:
M = 1123 mod 187 = 88
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
lOMoARcPSD|38071713
RSA Security
possible approaches to attacking RSA are:
brute force key search (infeasible given size of numbers)
Mathematical attacks.
timing attacks (on running of decryption)
chosen cipher text attacks
Mathematical attack
mathematical approach takes 3 forms:
factor n=p.q, hence compute ø(n) and then d
determine ø(n) directly and compute d
find d directly
Chosen Ciphertext Attacks
RSA is vulnerable to a Chosen Ciphertext Attack (CCA)
attackers chooses ciphertexts & gets decrypted plaintext back
Downloaded by Anakha Abhinav (anakhaabhinav24@gmail.com)
