INFORMATION SECURITY

UNIT II

INTRODUCTION
1 Symmetric encryption , also referred to as or conventional / private-key / single-key encryption 2 sender and recipient share a common key

Block vs. Stream Ciphers Block ciphers process messages in blocks, each of which is then en/decrypted like a substitution on very big characters 64-bits or more Stream ciphers process messages a bit or byte at a time when en/decrypting many current ciphers are block ciphers

CONVENTIONAL ENCRYPTION PRINCIPLES

An encryption scheme has five ingredients: Plain text: is the original message or data that is fed into algorithm as input. Encryption algorithm: performs various substitutions and transformations on the

plain text. Secret Key: is a value independent of the plain text and of the algorithm. Cipher text: coded message Decryption algorithm: takes the cipher text and the secret key and produces the

original text message. Security depends on the secrecy of the key, not the secrecy of the algorithm. The message source is the plain text X, and the secret key K as input and cipher text Y then, Y= E(K,X) ____________ ( 1 ) Using equation ( 1 ) Y is to be produced by using encryption algorithm E as a function of the plain text X. The intended receiver in possession of the key is able to do invert transformation X = D (K. Y)

INFORMATION SECURITY

cryptanalysis (code breaking) - study of principles/ methods of deciphering cipher text without knowing key Brute force attack: the attacker tries every possible key on a piece of cipher text until an intelligible translation into plain text is obtained. The various type of cryptanalytic attacks based on the amount of information known to cryptanalyst.

FEISTEL CIPHER STRUCTURE

Virtually all conventional block encryption algorithms, including DES have a structure first described by Horst Feistel of IBM in 1973.

INFORMATION SECURITY

The below figure shows classical Feistel cipher structure plain text block of length 2W bits and a key K are the input to the encryption algorithm. The plain text block is divided into two halves L0 and R0 . The two halves of the data pass through n rounds .of processing and then combine to produce the cipher text block. Each round I has an inputs derived from overall k.
Li-1

and Ri-1 derived from the previous round, as well as sub key Ki

The realization of a Feistel Network depends on the choice of the following parameters and design features: Block size: larger block sizes mean greater security Key Size: larger key size means greater security Number of rounds: multiple rounds offer increasing security Sub key generation algorithm: greater complexity will lead to greater difficulty of cryptanalysis. Round functions: again, greater complexity generally means greater resistance to cryptanalysis.

INFORMATION SECURITY

Fast software encryption/decryption: the speed of execution of the algorithm becomes a concern. Ease of analysis: although we would like to make our algorithm as difficult as possible to crypt analyze, there is a great benefit in making the algorithm easy to analyze.

CONVENTIONAL ENCRYPTION ALGORITHMS

DES: DATA ENCRYPTION STANDARD The most widely used encryption scheme The algorithm is referred to the Data Encryption Algorithm (DEA) DES is a block cipher The plaintext is processed in 64-bit blocks The key is 56-bits in length

The basic process for enciphering a 64-bit data blocks which consists of: - an initial permutation (IP) which shuffles the 64-bit input block

INFORMATION SECURITY

- 16 rounds of a complex key dependent round function involving substitutions & permutations - a final permutation, being the inverse of IP The handling of the 56-bit key and consists of: - an initial permutation of the key (PC1) which selects 56-bits out of the 64-bits input, in two 28-bit halves - 16 stages to generate the 48-bit sub keys using a left circular shift and a permutation of the two 28-bit halves Initial Permutation IP The input to a table consists of 64 bits numbered left to right from 1 to 64. The 64 entries in the permutation table contain a permutation of the numbers from 1 to 64. Each entry in the permutation table indicates the position of a numbered input bit in the output, which also consists of 64 bits. DES Round Structure: uses two 32-bit L & R halves Li = R i1 Ri = L
i1

F(R i1, Ki)

1 F takes 32-bit R half and 48-bit sub key: expands R to 48-bits using perm E adds to sub key using XOR passes through 8 S-boxes to get 32-bit result finally permutes using 32-bit perm P The internal structure of the DES round function F, which takes R half & sub key, and processes them through E, add sub key, S & P.

INFORMATION SECURITY

Substitution Boxes S 1 have eight S-boxes which map 6 to 4 bits 2 each S-box is actually 4 little 4 bit boxes Outer bits 1 & 6 (row bits) select one row of 4 Inner bits 2-5 (col bits) are substituted Result is 8 lots of 4 bits, or 32 bits 3 row selection depends on both data & key Feature known as autoclaving (auto keying) The substitution consists of a set of eight S-boxes, each of which accepts 6 bits as input and produces 4 bits as output. These transformations are defined in table below, which is interpreted as follows: The first and last bits of the input to box Si form a 2-bit binary number to select one of four substitutions defined by the four rows in the table for Si. The middle four bits select one of the sixteen columns. The decimal value in the cell selected by the row and column is then converted to its 4-bit representation to produce the output.

INFORMATION SECURITY

DES Key Schedule 1 forms sub keys used in each round initial permutation of the key (PC1) which selects 56-bits in two 28-bit halves 16 stages consisting of: rotating each half separately either 1 or 2 places depending on the key rotation schedule K selecting 24-bits from each half & permuting them by PC2 for use in round function F DES Decryption 1 decrypt must unwind steps of data computation 2 with Feistel design, do encryption steps again using sub keys in reverse order (SK16 SK1) IP undoes final FP step of encryption 1st round with SK16 undoes 16th encrypt round 16th round with SK1 undoes 1st encrypt round then final FP undoes initial encryption IP Thus recovering original data value As with any Feistel cipher, DES decryption uses the same algorithm as encryption except that the sub keys are used in reverse order SK16. SK1.

INFORMATION SECURITY

If you trace through the DES overview diagram can see how each decryption step top to bottom with reversed sub keys, undoes the equivalent encryption step moving from bottom to top. Strength of DES Key Size 56-bit keys have 256 = 7.2 x 1016 values brute force search looks hard recent advances have shown is possible in 1997 on Internet in a few months in 1998 on dedicated h/w (EFF) in a few days in 1999 above combined in 22hrs!

still must be able to recognize plaintext must now consider alternatives to DES

INFORMATION SECURITY

Triple DEA 1 Use three keys and three executions of the DES algorithm (encrypt-decryptencrypt) C = cipher text P = Plaintext EK[X] = encryption of X using key K DK[Y] = decryption of Y using key K 2 Effective key length of 168 bits

Other Symmetric Block Ciphers

1 International Data Encryption Algorithm (IDEA)

INFORMATION SECURITY

10

IDEA operates on 64-bit blocks using a 128-bit key, and consists of a series of eight identical transformations (a round, see the illustration) and an output transformation (the half-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from different groups modular addition and multiplication, and bitwise eXclusive OR (XOR) : After the eight rounds comes a final "half round", the output transformation illustrated below:

Key schedule Each round uses six 16-bit sub-keys, while the half-round uses four, a total of 52 for 8.5 rounds. The first eight sub-keys are extracted directly from the key, with K1 from the first round being the lower sixteen bits; further groups of eight keys are created by rotating the main key left 25 bits between each group of eight. This means that it is rotated less than once per round, on average, for a total of six rotations.

INFORMATION SECURITY

11

2 Blowfish 3 RC5 Designed by Ronald Rivest Suitable for hardware and software Fast, simple Adaptable to processors of different word lengths Variable number of rounds Variable-length key Low memory requirement High security Data-dependent rotations Easy to implement High execution speed Run in less than 5K of memory

4 Cast-128 Key size from 40 to 128 bits The round function differs from round to round

CIPHER BLOCK MODES OF OPERATION

Electronic Codebook Book (ECB) 1 message is broken into independent blocks which are encrypted 2 each block is a value which is substituted, like a codebook, hence name 3 each block is encoded independently of the other blocks 4 uses: secure transmission of single values The simplest mode is the electronic codebook (ECB) mode, in which plaintext is handled one block at a time and each block of plaintext is encrypted using the same key. ECB is the

INFORMATION SECURITY

12

simplest of the modes, and is used when only a single block of info needs to be sent (eg. a session key encrypted using a master key). Advantages and Limitations of ECB 1 message repetitions may show in cipher text if aligned with message block Particularly with data such graphics or with messages that change very little, which become a code-book analysis problem Weakness is due to the encrypted message blocks being independent use is sending a few blocks of data main

Cipher Block Chaining Mode (CBC) To overcome the problems of repetitions and order independence in ECB, want some way of making the cipher text dependent on all blocks before it. This is what CBC gives us, by combining the previous cipher text block with the current message block before encrypting. To start the process, use an Initial Value (IV), which is usually well known (often all 0's), or otherwise is sent, ECB encrypted, just before starting CBC use. CBC mode is applicable whenever large amounts of data need to be sent securely, provided that all data is available in advance (eg email, FTP, web etc).

INFORMATION SECURITY

13

The input to the encryption algorithm is the XOR of the current plaintext block and the preceding cipher text block. Repeating pattern of 64-bits are not exposed

message is broken into blocks

and linked together in encryption operation

each

previous cipher blocks is chained with current plaintext block, hence name use Initial Vector (IV) to start process Ci = E K (Pi XOR Ci-1) uses: bulk data encryption, authentication

Cipher feedback mode: 1 Data is encrypted in units that are smaller than a defined block size. 2 It is possible to convert the DES into stream cipher using cipher feedback mode. 3 More than one message can be encrypted with the same key, provided that a different initialization vector is used.

INFORMATION SECURITY

14

LOCATION OF ENCRYPTION DEVICES

If encryption is to be used to counter attacks on confidentiality, need to decide what to encrypt and where the encryption function should be located. Now examine potential locations of security attacks and then look at the two major approaches to encryption placement: link and end to end. Have many locations where attacks can occur in a typical scenario such as : 1 workstations on LANs access other workstations & servers on LAN 2 LANs interconnected using switches/routers 3 with external lines or radio/satellite links

INFORMATION SECURITY

15

Consider attacks and placement in this scenario: 1 snooping from another workstation 2 use dial-in to LAN or server to snoop 3 physically tap line in wiring closet 4 use external router link to enter & snoop 5 monitor and/or modify traffic one external links Placement of encryption function decides where the encryption function should be located. 1 Link encryption: A lot of encryption devices High level of security Decrypt each packet at every switch

2 End-to-end encryption The source encrypt and the receiver decrypts Payload encrypted Header in the clear

INFORMATION SECURITY

16

KEY DISTRIBUTION
For symmetric encryption to work, the two parties to an exchange must share the same key, and that key must be protected from access by others. This is one of the most critical areas in security systems - on many occasions systems have been broken, not because of a poor encryption algorithm, but because of poor key selection or management. 164 Symmetric schemes require both parties to share a common secret key 165 issue is how to securely distribute this key 166 often secure system failure due to a break in the key distribution scheme given parties A and B have various key distribution alternatives: A can select key and physically deliver to B third party can select & deliver key to A & B if A & B have communicated previously can use previous key to encrypt a new key if A & B have secure communications with a third party C, C can relay key between A & B

INFORMATION SECURITY

17

The strength of any cryptographic system thus depends on the key distribution technique. For two parties A and B, key distribution can be achieved in a number of ways: Physical delivery (1 & 2) is simplest - but only applicable when there is personal contact between recipient and key issuer. This is fine for link encryption where devices & keys occur in pairs, but does not scale as number of parties who wish to communicate grows. 3 is mostly based on 1 or 2 occurring first. A third party, whom all parties trust, can be used as a trusted intermediary to mediate the establishment of secure communications between them (4). Must trust intermediary not to abuse the knowledge of all session keys. As numbers of parties grow, some variant of 4 is only practical solution to the huge growth in number of keys potentially needed. Key Hierarchy 1 session key Temporary key used for encryption of data between users for one logical session then discarded 2 master key used to encrypt session keys shared by user & key distribution center 3 Permanent key: Used between entities for the purpose of distributing session keys Key Distribution Issues 1 hierarchies of KDCs required for large networks, but must trust each other 2 session key lifetimes should be limited for greater security 3 use of automatic key distribution on behalf of users, but must trust system 4 use of decentralized key distribution 5 controlling key usage

INFORMATION SECURITY

18

Some of the major issues associated with the use of Key Distribution Centers (KDCs). For very large networks, a hierarchy of KDCs can be established. For communication among entities within the same local domain, the local KDC is responsible for key distribution. If two entities in different domains desire a shared key, then the corresponding local KDCs can communicate through a (hierarchy of) global KDC(s) To balance security & effort, a new session key should be used for each new connectionoriented session. For a connectionless protocol, a new session key is used for a certain fixed period only or for a certain number of transactions. An automated key distribution approach provides the flexibility and dynamic characteristics needed to allow a number of terminal users to access a number of hosts and for the hosts to exchange data with each other, provided they trust the system to act on their behalf. The use of a key distribution center imposes the requirement that the KDC be trusted and be protected from subversion. This requirement can be avoided if key distribution is fully decentralized. In addition to separating master keys from session keys, may wish to define different types of session keys on the basis of use.

INFORMATION SECURITY

19

APPROACHES OF MESSAGE AUTHENTICATION

Message authentication is concerned with protecting the integrity of a message, validating identity of originator, non-repudiation of origin (dispute resolution) and will consider the security requirements Requirements - must be able to verify that: 1. Message came from apparent source or author, 2. Contents have not been altered, 3. Sometimes, it was sent at a certain time or sequence.

Protection against active attack (falsification of data and transactions) Security Requirements disclosure traffic analysis masquerade content modification

INFORMATION SECURITY

20

sequence modification timing modification source repudiation destination repudiation

Three alternative functions used: message encryption message authentication code (MAC) hash function

Message Encryption message encryption by itself also provides a measure of authentication if symmetric encryption is used then: receiver know sender must have created it since only sender and receiver now key used know content cannot of been altered if message has suitable structure, redundancy or a checksum to detect any changes if public-key encryption is used: encryption provides no confidence of sender since anyone potentially knows public-key however if sender signs message using their private-key then encrypts with recipients public key have both secrecy and authentication again need to recognize corrupted messages but at cost of two public-key uses on message

INFORMATION SECURITY

21

INFORMATION SECURITY

22

Message Authentication Code (MAC) generated by an algorithm that creates a small fixed-sized block depending on both message and some key like encryption though need not be reversible appended to message as a signature receiver performs same computation on message and checks it matches the MAC provides assurance that message is unaltered and comes from sender

as shown the MAC provides authentication can also use encryption for secrecy generally use separate keys for each can compute MAC either before or after encryption is generally regarded as better done before why use a MAC? sometimes only authentication is needed sometimes need authentication to persist longer than the encryption (eg. archival use) note that a MAC is not a digital signature a MAC is a cryptographic checksum

INFORMATION SECURITY

23

MAC = CK(M) condenses a variable-length message M using a secret key K to a fixed-sized authenticator is a many-to-one function potentially many messages have same MAC but finding these needs to be very difficult taking into account the types of attacks need the MAC to satisfy the following: knowing a message and MAC, is infeasible to find another message with same MAC MACs should be uniformly distributed MAC should depend equally on all bits of the message can use any block cipher chaining mode and use final block as a MAC Data Authentication Algorithm (DAA) is a widely used MAC based on DES-CBC using IV=0 and zero-pad of final block encrypt message using DES in CBC mode and send just the final block as the MAC or the leftmost M bits (16M64) of final block but final MAC is now too small for security Hash Functions condenses arbitrary message to fixed size h = H(M) usually assume that the hash function is public and not keyed cf. MAC which is keyed hash used to detect changes to message can use in various ways with message most often to create a digital signature Hash Functions & Digital Signatures

INFORMATION SECURITY

24

HASH AND MAC ALGORITHMS

Hash Functions condense arbitrary size message to fixed size by processing message in blocks through some compression function either custom or block cipher based Message Authentication Code (MAC) fixed sized authenticator for some message to provide authentication for message by using block cipher mode or hash function MAC based on DES

Secure Hash Algorithm

INFORMATION SECURITY

25

The Secure Hash Algorithm was developed by the National Institute of Standards and Technology (NIST) and published as a federal information processing standard in 1993, A revised version was issued as FIPS 180-1 in 1995 and is generally referred to as SHA-1.

The actual standards document is entitled Secure Hash Standard. SHA is based on the hash function MD4 and its design closely models MD4. SHA-1 produces a hash value of 160 bits. In 2005, a research team described an attack in which two separate messages could be found that deliver the same SHA-1 hash using 2^69 operations, far fewer than the 2^80 operations previously thought needed to find a collision with an SHA-1 hash . This result should hasten the transition to newer, longer versions of SHA.

Now examine the structure of SHA-512, noting that the other versions are quite similar. SHA-512 follows the structure depicted in figure. The processing consists of the following steps: Step 1: Append padding bits Step 2: Append length Step 3: Initialize hash buffer Step 4: Process the message in 1024-bit (128-word) blocks, which forms the heart of the algorithm Step 5: Output the final state value as the resulting hash

INFORMATION SECURITY

26

The SHA-512 Compression Function is the heart of the algorithm. In this Step 4, it processes the message in 1024-bit (128-word) blocks, using a module that consists of 80 rounds, labeled Figure .

Each round takes as input the 512-bit buffer value, and updates the contents of the buffer. Each round t makes use of a 64-bit value Wt derived using a message schedule from the current 1024-bit block being processed.

Each round also makes use of an additive constant Kt, based on the fractional parts of the cube roots of the first eighty prime numbers. The output of the eightieth round is added to the input to the first round to produce the final hash value for this message block, which forms the input to the next iteration of this compression function, as shown on the previous slide.

INFORMATION SECURITY

27

The structure of each of the 80 rounds is shown in fig. Each 64-bit word shuffled along one place, and in some cases manipulated using a series of simple logical functions. Register values : a- 67452301 b- EFCDAB89 c- 98BADCFE d- 10325476 e- C3D2E1F0

HASHED MESSAGE AUTHENTICATION CODE

H Embedded hash function IV Initial value input

INFORMATION SECURITY

28

M Message L No. of blocks b- No. of bits n Length of hash code K Secret key K+ - k padded with 0 bits to get length of b bits ( 36) ipad - > 00110110 repeated b/8 times (5C) opad - > 01011100 repeated b/8 times Then HMAC can be expressed as follows : HMAC (K,M) = H [ (k+ opad) || H[ (K+ ipad) || M ] Algorithm: 1. Append zeros to the left end of k to create a b bit string K+ 2. XOR K+ with ipad to produce the b bit block Si 3. Append M to Si 4. Apply H to stream generated in step 3 5. XOR K+ with opad to produce the b bit block S0 6. Append the hash result from step 4 to S0. 7. Apply H to the stream generated in step 6 and output the result.

INFORMATION SECURITY

29