Lecture 3 ~Modern Cryptography~
Assalamualaikum w.b.t..
Lam lecture 3 nie encek ajr kiteorg bab Modern Cryptography... Lecture nie mmg best tp kdg2 tue pening gakk.. tp aku suker.. hehhee.. kalu der yg kire2 lg syok!.. byk guner IQ daaaa...Aku nie mmg ske sgt berpkir... sejak azali lagi.. da mmg sesuai la aku yg fanatik green nie... org yg kuat berfikir.. uhukss... Topics lam lecture nie adalah :-
~Modern Cryptography Algorithm
~Block and Stream
~DES
~AES
~MAC
~Digital Signature, RSA
Modern Cryptography Algorithm
•Most modern ciphers use a sequence of binary digits (bits), that is, zeros and ones such as ASCII.
•This bit sequence representing the plaintext is then encrypted to give the ciphertext as a bit sequence.
•The encryption algorithm may act on a bit-string in a number of ways.
~stream ciphers where the sequence is encrypted bit-by-bit.
~block ciphers, where the sequence is divided into blocks of a predetermined size.
~ASCII requires 8 bits to represent one character, and so for a block cipher that
has 64-bit blocks, the encryption algorithm acts on eight characters at once.
•Since most modern algorithms operate on binary strings we need to be familiar with a method of combining two bits called Exclusive OR and often written as XOR or .
•Stream ciphers
~they convert one symbol of plaintext immediately into a symbol of ciphertext
~depends on symbol, key and control information of encipherment algorithm
•Block ciphers
~encrypt a group of plaintext symbols as one block
~examples are transposition ciphers
•e.g, in columnar transposition, the entire message is translated as one block,
block size need not have any particular relationship to the size of the character
Stream Ciphers
~The plaintext is enciphered bit by bit.
•The value of each bit is changed to the alternative value or leave unchanged.
•If a bit is changed twice, it returns to its original value.
~If an attacker knows that a stream cipher has been used, then their task is to try
to identify the position of those bits which have been changed and to change them
back to their original values.
•If there is any easily detectable pattern that identifies the changed bits then
the attacker task may be simple.
•The position of the changed bits must be unpredictable to the attacker but the
genuine receiver needs to be able to identify them easily.
~The encryption key is often called a keystream sequence.
•0 to mean ‘leave unchanged’, 1 to mean ‘change’.
•Plaintext, ciphertext and keystream are all binary sequences.
~Suppose that we have the plaintext 1100101 and the keystream is 1000110.
•By applying the rule gives 0100011 as the ciphertext.
~Changing a bit twice has the effect of returning it to its original value.
•This means that decryption process is identical to the encryption process, so the
keystream also determines decryption.
~If Pi, Ki and Ci are respectively the plaintext, keystream and ciphertext bits in position i, then the ciphertext bit Ci is given by Ci = Pi Ki.
•The decryption is defined by Pi = Ci Ki.
~A stream cipher takes a short key to generate a long keystream.
•This is achieved by using binary sequence generator.
~The keystream bit in position i, Ki = Pi Ci can be determined as the XOR of the plaintext and ciphertext in position i.
•This highlight the potential weakness for stream ciphers.
•Anyone who is able to launch a known plaintext attack, can deduce parts of the
keystream sequence from the corresponding plaintext and ciphertext bit pairs.
•Thus the keystream must be unpredictable in the sense that knowledge of some of
it should not enable an attacker to deduce the rest.
~If the keystream generator produces the same bit stream every time it is turned on,
the resulting cryptosystem will be trivial to break.
•Anyone who has two different ciphertexts encrypted with the same keystream, can
XOR them together and get two plaintext messages XORed with each other.
•When the interceptor gets a single plaintext/ciphertext pair, they can read
everything.
•That is why all stream ciphers have keys - the output of the keystream generator
is a function of the key.
Block Ciphers
~For a block cipher, the bit-string is divided into blocks of a given size and the
encryption algorithm acts on that block to produce a cryptogram block that, for
most symmetric ciphers, has the same size.
~Block ciphers have many applications.
•Can be used to provide confidentiality, integrity, or user authentication and can
even be used to provide the keystream generator for stream ciphers.
~A symmetric algorithm is said to be well designed if an exhaustive key search is
the simplest form of attack.
~Usual number of blocks are 64,128,256 and 512 bits
~There are a few obvious properties that a strong block cipher should possess.
•Diffusion properties - which a small change in the plaintext, may
be one or two positions, should produce an unpredictable change in the ciphertext.
•Confusion properties - if an attacker is conducting an exhaustive key search then there should be no indication that they are near to the correct key.
•To prevent divide-and-conquer attacks we require completeness - each bit of a
ciphertext must depend on every bit of the key.
•Statistical testing forms a fundamental component of the assessment of block
ciphers for these three listed properties and others.
Data Encryption Standards (DES)
~Widely used encryption scheme
~Adopted by The national Bureau of standard in 1977
~The plaintext is divided into 64 bit blocks with a key of 56 bits(with 8 bit
parity).
~DES structure is similar to Fiestel Network concept.
~Process through 16 round of Expansion, substitution, key mixing and permutation
process.
~Is it breakable?
~Yes, can try brute force attack using all the 2^56 possible key
~1998, Electronic Frontier Foundation (EFF) has created a USD220,000 machine to go
through the entire 56 bit DES key space in average of 4.5 days.
~Triple DES has been introduced to improve the standard.
Advanced Encryption Standard (AES)
•needed a better replacement for DES
•NIST called for proposals in 1997
•selected Rijndael in Nov 2001
•published as FIPS 197
•symmetric block cipher
•uses 128 bit data & 128/192/256 bit keys
•now widely available commercially
Message Authentication
•protects against active attacks
•verifies received message is authentic
~contents unaltered
~from authentic source
~timely and in correct sequence
•can use conventional encryption
~only sender & receiver have key needed
•or separate authentication mechanisms
~append authentication tag to cleartext message
Message Authentication Codes (MAC)
Hash Function
Hash Function Requirements
~applied to any size data
~H produces a fixed-length output.
~H(x) is relatively easy to compute for any given x
~one-way property
•computationally infeasible to find x such that H(x) = h
~weak collision resistance
•computationally infeasible to find y ? x such that H(y) = H(x)
~strong collision resistance
•computationally infeasible to find any pair (x, y) such thatH(x) = H(y)
Simple Hash Functions
•a one-way or secure hash function used in message authentication, digital
signatures
•all hash functions process input a block at a time in an iterative fashion
•one of simplest hash functions is the bit-by-bit exclusive-OR (XOR) of each block
– effective data integrity check on random data
– less effective on more predictable data
– virtually useless for data security
Hash Functions
~two attack approaches
•cryptanalysis
~exploit logical weakness in alg
•brute-force attack
~trial many inputs
~strength proportional to size of hash code (2n/2)
~SHA most widely used hash algorithm
•SHA-1 gives 160-bit hash
•more recent SHA-256, SHA-384, SHA-512 provide improved size and security
~There are 2 prominent algorithms in Hashing functions.
•First, the most popularly used technique is MD5.
•Second, the well accepted standard is secure hashing algorithm SHA-1.
~Nevertheless, SHA-256 is chosen in this class as it is considered to be the
primary next-generation algorithm.
~MD-5
•A hash function designed by Ron Rivest, one of the inventors of the RSA public-key
encryption scheme.
•The MD-5 algorithm produces a 128-bit output. Note that MD-5 is now known to have
some weaknesses and should be avoided if possible.
•SHA-1 is generally recommended.
~SHA-1 (Secure Hash Algorithm-1)
•SHA-1 is an MD-5-like algorithm that was designed to be used with the Digital
Signature Standard (DSS).
•NIST (National Institute of Standards and Technology) and NSA (National Security
Agency) are responsible for SHA-1.
•The SHA-1 algorithm produces a 160-bit MAC.
•This longer output is considered to be more secure than MD-5.
SHA Secure Hash Functions
•SHA originally developed by NIST/NSA in 1993
•was revised in 1995 as SHA-1
– US standard for use with DSA signature scheme
– standard is FIPS 180-1 1995, also Internet RFC3174
– produces 160-bit hash values
•NIST issued revised FIPS 180-2 in 2002
– adds 3 additional versions of SHA
– SHA-256, SHA-384, SHA-512
– with 256/384/512-bit hash values
– same basic structure as SHA-1 but greater security
•NIST intend to phase out SHA-1 use
•For SHA-1 and SHA-256, each message block has 512 bits, which are represented as a
sequence of sixteen 32-bit words.
•SHA-256 uses six logical functions, where each function operates on 32-bit words,
which are
•SHA-1 and SHA-256
•Suppose that the length of the message, M, is l bits. Append the bit “1” to the end
of the message.
•followed by k zero bits, where k is the smallest, non-negative solution to the
equation
•l +1+ k º 448mod 512 . Then append the 64-bit block that is equal to the number l
expressed
•using a binary representation. For example, the (8-bit ASCII) message “abc” has
length 8´3 = 24, so the message is padded with a one bit, then 448 - (24 +1) = 423
zero bits, and then the message length, to become the 512-bit padded message
•For SHA-1 and SHA-256, the padded message is parsed into N 512-bit blocks, M(1), M(2),…,M(N). Since the 512 bits of the input block may be expressed as sixteen 32-bit words, the first 32 bits of message block i are denoted M (i) 0, the next 32 bits are M (i) 1, and so on up to M (i) 15.
•For SHA-256, the initial hash value, H(0), shall consist of the following eight 32-bit words, in hex:
Initial value
SHA-512 Structure
SHA-512 Round
Digital Signatures
~It is the provision of a means of settling disputes between sender and receiver
that distinguishes the digital signature mechanism from the MACing process.
•Such dispute can only be settled if there is asymmetric between sender and
receiver.
~For a digital signature scheme based on RSA or El Gamal:
•Each user has a private key that only they can use and its use is accepted as
identifying them.
•There is a corresponding public key.
•Anyone who knows this public key, can check that the corresponding private key has
been used, but cannot determine the private key.
•This gives the receiver assurance of both the origin and content of the message.
Generating a Digital Signature
•Asymmetric cryptographic processing requires much computational processing.
•Thus a condensed version or hash of the message is produced by applying a hash
function to the message.
•The signature is produced from the hash (which represent the message) by using the
asymmetric algorithm with the private key.
•Thus only the owner of the private key can generate the signature.
Digital signature
Hash Function
How to Create a Digital Signature Using RSA
Verifying a Digital Signature
~The signature can be verified by anyone who knows the corresponding public key.
~To do this a value is produced from the signature using the asymmetric algorithm
with the public key.
~This value should be the hash of the message, which anyone can calculate.
~If this value and the hash agree, the signature is accepted as genuine.
How to Verify a Digital Signature Using RSA
Certification Authority (CA)
AIM:
•To guarantee the authenticity of public keys.
METHOD:
•The CA guarantees the authenticity by signing a certificate containing user’s
identity and public key with its secret key.
REQUIREMENT:
•All users must have an authentic copy of the Certification Authority’s public key.
Certification Process
How Does it Work?
~The certificate can accompany all sender’s messages.
~The recipient must directly or indirectly:
•Trust the CA
•Validate the certificate
Certification Authorities
~Problems / Questions
•Who generates users’ key?
•How is identity established?
•How can certificates be cancelled?
•Any others?
Attacks on Digital Signature
•Suppose digital signatures are being used as a means of identification.
•If user A wishes to impersonate user B, then there are two different forms of
attack:
>A attempts to obtain the use of B’s private key
>A tries to substitute their public key for B’s public key.
Public Key Infrastructure (PKI)
~The motivation of using PKI is to facilitate the use of public key cryptography.
~Three key players in PKI system:
•The certificate owner - who applies for the certificate.
•CA - which issues the certificate that binds the owner’s identity to the owner’s
public key value.
•The relying party - who uses on the certificate.
~Other players:
•Registration Authority (RA) - in some systems the identification verification is
performed by a separate authority.
•Validation Authority (VA) - end users ask the VA if a given certificate is still
valid and receive a yes or no answer.
Establishing a PKI
~When a PKI is established, the following processes need to take place:
•The key pairs for CAs must be generated.
•The key pairs for users must be generated.
•Users must request certificates
•Users’ identities must be verified.
•Users’ key pairs must be verified.
•Certificates must be produced.
•Certificates must be checked.
•Certificates must be removed/updated (when necessary).
•Certificates must be revoked (when necessary).
Key Management
~A typical requirement specification for a symmetric key system might include each
of the following:
•Keys must be generated using a random or pseudorandom process.
•Any key used by a communicating pair must be unique to them.
•A key must be used for only for a purpose, e.g. the same key should not be used
for both encryption and authentication.
•Each key must be replaced within the time deemed necessary to determine it by an
exhaustive search.
•A key must not be used if its compromise is either known or suspected.
•Compromise of a key which is shared between two parties must not compromise any
key used by a third party.
•Keys should only appear in clear form within a highly tamper resistant device.
Elsewhere all keys must be encrypted or in component form.
•Keys must be protected against misuse.
•Unauthorized modification, substitution or replay of any key must be prevented or
detected.
The Key Life Cycle
RSA
~by Rivest, Shamir & Adleman of MIT in 1977
~best known & widely used public-key scheme
~Ingredients of RSA:
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
•note ø(n)=(p-1)(q-1)
~selecting at random the encryption key e
•where 1
•e*d=1 mod ø(n) and 0≤d≤n
~publish their public encryption key: PU={e,n}
~keep secret private decryption key: PR={d,n}
RSA Use
~to encrypt a message M the sender:
•obtains public key of recipient PU={e,n}
•computes: C = Me mod n, where 0≤M
•uses their private key PR={d,n}
•computes: M = Cd mod n
~note that the message M must be smaller than the modulus n (block if needed)
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 (number 88<187)
•encryption:
C = Me mod n
C = 887 mod 187 = 11
•decryption:
M = Cd mod n
M = 1123 mod 187 = 88
Exponentiation
~can use the Square and Multiply Algorithm
~a fast, efficient algorithm for exponentiation
~concept is based on repeatedly squaring base
~and multiplying in the ones that are needed to compute the result
~look at binary representation of exponent
~only takes O(log2 n) multiples for number n
•eg. 75 = 74.71 = 3.7 = 10 mod 11
•eg. 3129 = 3128.31 = 5.3 = 4 mod 11
Exponentiation (Algorithm for Computing ab mod n)
c = 0; f = 1
for i = k downto 0
do c = 2 x c
f = (f x f) mod n
if bi == 1 then
c = c + 1
f = (f x a) mod n
return f
Efficient Encryption
~encryption uses exponentiation to power e
~hence if e small, this will be faster
*often choose e=65537 (216-1)
*also see choices of e=3 or e=17
~but if e too small (eg e=3) can attack
*using Chinese remainder theorem & 3 messages with different moduli
~if e fixed must ensure gcd(e,ø(n))=1
*i.e. reject any p or q not relatively prime to e
Efficient Decryption
•decryption uses exponentiation to power d
~this is likely large, insecure if not
•can use the Chinese Remainder Theorem (CRT) to compute mod p & q separately. then
combine to get desired answer
~approx 4 times faster than doing directly
•only owner of private key who knows values of p & q can use this technique
RSA Key Generation
•users of RSA must:
~determine two primes at random - p, q
~select either e or d and compute the other
•primes p,q must not be easily derived from modulus n=p*q
~means must be sufficiently large
~typically guess and use probabilistic test
•exponents e, d are inverses, so use Inverse algorithm to compute the other
RSA Security
~possible approaches to attacking RSA are:
•brute force key search (infeasible given size of numbers)
•mathematical attacks (based on difficulty of computing ø(n), by factoring modulus
n)
•timing attacks (on running of decryption)
•chosen ciphertext attacks (given properties of RSA)
Methods of Attack
~Four general attacks can be perform against encrypted information:
•Ciphertext-only attack guessing the plaintext or using frequency analysis
•Known Plaintext guess using known pliantext.
•Chosen-plaintext
•Chosen-ciphertext attack
~There are also specific attacks that can be launched against encryption systems.
•Brute-Force attack
*Exhaustive key search - trying every possible combination.
•Replay attacks
*Taking encrypted information and playing it back at a later point in time.
~Man-in-the-middle attacks
~Fault in Cryptosytem
yuhuuu... walaupun ia memeningkan... kepuasan n keseronokan itu penting!.. hehehehee...
alhamdulilllah...
