Modern Cryptograpy

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
Stream ciphers

• 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

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 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.
• DES is brakeable by using brute force of 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.

DES Process Diagram






































Advanced Encryption Standard (AES)

• created to be 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

Message Authentication
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

• weak collision resistance

• strong collision resistance
  

> computationally infeasible to find any pair (x, y) such thatH(x) = H(y)

Simple Hash Function

• 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 algorithm,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 Function
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 8x3 =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

SHA-512 Structures
SHA-512 Round

Digital Signatures
t 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.
• 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.

Public Key Infrastructure (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.