International Data Encryption Algorithm: 1 International Data Encryption Algorithm
Overview: 2 Overview DES algorithm has been a popular secret key encryption algorithm and is used in many commercial and financial applications. However, its key size is too small by current standards and its entire 56 bit key space can be searched in approximately 22 hours. IDEA is a block cipher designed by Xuejia Lai and James L. Massey in 1991.
Overview (cont’): 3 Overview (cont’) IDEA was originally called IPES ( Improved PES) and was developed to replace DES. It entirely avoids the use of any lookup tables or S-boxes. IDEA was used as the symmetric cipher in early versions of the Pretty Good Privacy cryptosystem
IDEA: 4 IDEA IDEA operates with 64-bit plaintext and cipher text blocks and is controlled by a 128-bit key. The algorithm structure has been chosen such that when different key sub-blocks are used, the encryption process is identical to the decryption process. IDEA consists of 8 rounds followed by a final transformation function.
Over all structure: Over all structure 5
Key generation: 6 Key generation Six 16-bit key are generated from the 128-bit key for each round. Since a further four 16-bit key-sub-blocks are required for the subsequent output transformation, a total of 52 (= 8 x 6 + 4) different 16-bit sub-blocks have to be generated from the 128-bit key. z1 z2z3z4z5z6z7z8 z15z16z9z10z11z12z14z15 --z22z23z24z17z18z19z20z21-- z28z29z30z31z32z25z26z27z28 z35z36z37z38z39z40z33z34— --z41z42z43z44z45z46z47z48 z49z50z51z52
Key generation process: 7 Key generation process First, the 128-bit key is partitioned into eight 16-bit sub-blocks which are then directly used as the first eight key sub-blocks. The 128-bit key is then cyclically shifted to the left by 25 positions, after which the resulting 128-bit block is again partitioned into eight 16-bit sub-blocks to be directly used as the next eight key sub-blocks. The cyclic shift procedure described above is repeated until all of the required 52 16-bit key sub-blocks have been generated
PowerPoint Presentation: 8 IDEA... Confusion: - Achieved by mixing three different operations. -Each operation takes two 16-bit inputs and produces a 16-bit output. Three Operations: 1. Bit-by-bit Exclusive-OR. 2. Addition of integers modulo 2^16 (=65536) inputs and output are treated as 16 bit unsinged integers. 3. Multiplication of integers modulo 2^16+1 (=65537). -inputs and output are treated as 16 bit unsinged integers.
IDEA…: 9 IDEA… A block of all zeros is treated as 2^16. Three operations are incompatible: >No two satisfy distributive law. >No two satisfy associate law. Three Operations “in combination provide a complex transformation making cryptanalysis very difficult.”
IDEA…: 10 IDEA… Diffusion: Provided by a multiplication/addition structure (MA). >Takes two inputs: (1) Two 16 bit values derived from plaintext. (2) Two 16 bit subkeys derived from the key. >Produces two 16 bit outputs. Each output bit depends on every input bit and on every bit of the subkeys. //lot of diffusion.// >This structure is repeated 8 times in the encryption algorithm.//very effective diffusion.
Encryption: 11 Encryption The 64-bit plaintext block is partitioned into four 16-bit sub-blocks(X1, X2, X3, X4). The first four 16-bit key sub-blocks are combined with two of the 16-bit plaintext blocks using addition modulo 2 16 , and with the other two plaintext blocks using multiplication modulo 2 16 + 1 . At the end of the first encryption round four 16-bit values are produced which are used as input to the second encryption round . The process is repeated in each of the subsequent 7 encryption rounds.
PowerPoint Presentation: The four 16-bit values produced at the end of the 8th encryption round are combined with the last four of the 52 key sub-blocks using addition modulo 2 16 and multiplication modulo 2 16 + 1 to form the resulting four 16-bit ciphertext blocks. 12
Encryption : Encryption 13 X1 X2 X3 X4 Y1 Y2 Y3 Y4
Decryption: 14 Decryption The computational process used for decryption of the ciphertext is essentially the same as that used for encryption. The only difference is that each of the 52 16-bit key sub-blocks used for decryption is the inverse of the key sub-block used during encryption. In addition, the key sub-blocks must be used in the reverse order during decryption in order to reverse the encryption process.
Blowfish: 15 Blowfish Easy to implement High execution speed. Run in less than 5K of memory. Variable security: key length is variable. (can be as long as 448 bits, range 32..448). > Allows a tradeoff between speed and security. -The key is used to generate 18 32-bit subkeys. -Encryption/decryption consist of 16 rounds.
Blowfish…: 16 Blowfish… Bruce Schneier (born January 15, 1963) Encryption: Uses two primitive operations: 1. Addition: performed modulo 2^32. 2. Bitwise Exclusive-OR. > These two operations do not commute. >Making cryptanalysis difficult.
Blowfish…: 17 Blowfish… Encryption Algorithm: -Plaintext is divided into two 32 bit halves. -Go through 16 rounds of transformation using subkeys. -Each rounds takes two 32 bit inputs and produces two 32 outputs. -Output of a round is fed into the next round. -The output of 16 th round is exclusive-ORed with 17 th and 18 th subkeys to produce the ciphertext. 32 bits 32 bits
Blowfish…: 18 Blowfish… Details of a Single Round: - Each round includes complex use of addition modulo 2^32, Ex-OR, and substitution using S-Boxes. - 32 bit input to the function F is divided into four bytes. -Each byte goes through a separate S-box and is expanded into 32 bits. -32 bit outputs go through complex transformation using addition modulo 2^32 and Ex-OR.
Single Round: Single Round 19 32 32 Li-1 Ri-1 Li Ri
CAST-128: CAST-128 64-bit iterated block cipher key: 40 bits -128 bits (increments of 8 bits) 12 up to 16 rounds The round function differs from round to round Feistel Network structure designed by C. Adams and S.Tavares (1996)
CAST-128: CAST-128 CAST-128 is part of the GnuPG suite of cryptographic algorithms (nicknamed CAST-5) CAST-128 uses fixed 8x32-bit S-boxes: for encryption and decryption (S 1 , S 2 , S 3 , S 4 ) and for the key schedule (S 5 , S 6 , S 7 , S 8 ) round operations: +, -, <<<, three round functions: f 1 , f 2 and f 3 An official algorithm for use with the Canadian Government:
CAST-128: CAST-128 f 1 f 2 f 3 Round functions
Single round: Single round 23
Stream Cipher: Stream Cipher A key is input to a pseudorandom bit generator that produces an apparently random keystream of bits. These bits are XOR’d with message to encrypt the data. 11001100 plaintext 01101100 key stream 10100000 ciphertext They are XOR’d again to decrypt it by the receiver. 24
Stream Cipher Structure: Stream Cipher Structure 25
Stream Cipher Properties: Stream Cipher Properties Some design considerations are: long period with no repetitions statistically random depends on large enough key large linear complexity Properly designed, can be as secure as a block cipher with same size key. Usually simpler & faster 26
RC4: RC4 A proprietary cipher owned by RSA Security A Ron Rivest design, simple but effective, based on random permutation Variable key size, byte-oriented stream cipher Widely used SSL/TLS web security protocol Wireless WEP/WPA LAN security protocols Key forms random permutation of all 8-bit values Uses that permutation to scramble input info processed a byte at a time Kept secret until anonymously posted on the Internet 27
RC4 Algorithm: RC4 Algorithm The RC4 algorithm is remarkably simple. It uses a variable-length key of from 1 to 256 bytes. The RC4 key schedule initializes the state S to the numbers 0..255 Then it walks through each entry in turn, using its current value plus the next byte of key to pick another entry in the array, and swaps their values over. 28
RC4 Algorithm: RC4 Algorithm Starts with an array S of numbers 0..255 Use key to shuffle array S forms internal state of the cipher for i = 0 to 255 do // Initialization S[i] = i T[i] = K[i mod keylen] j = 0 // Initial permutation of S for i = 0 to 255 do j = (j + S[i] + T[i]) (mod 256) swap (S[i], S[j]) Total number of possible states is 256! 29
RC4 Encryption: RC4 Encryption Encryption continues shuffling array values Sum of shuffled pair selects "stream key" value from permutation XOR S[t] with next byte of message to en/decrypt i = j = 0; //Stream Generation while (true) //for each message byte M i i = ( i + 1) (mod 256); j = (j + S[ i ]) (mod 256); swap(S[ i ], S[j]); t = (S[ i ] + S[j]) (mod 256); k= S[t]; C i = M i XOR S[t] or M i = C i XOR S[t]; (to Encrypt/ Decrypt) 30
RC4 Overview: RC4 Overview 31
RC4 Security: RC4 Security Claimed secure against known attacks have some analyses, none practical. Result is very non-linear Since RC4 is a stream cipher, must never reuse a key Concern with WEP, but due to key handling rather than RC4 itself Secure with key length of at least 128 bits 32
RC5: 33 RC5 RC5 – designed by Ron Rivest (1994) Block cipher Suitable for hardware and software Fast, simple Adaptable to processors of different word lengths Variable block size ( 32, 64, 128 bits) Variable number of rounds ( 0 to 255) Variable-length key ( 0 to 2040 bits) Low memory requirement, High security Data-dependent rotations Modulo additions and exclusive ORs (XOR) Feistel-like structure
RC5: RC5 34 Two half- rounds of RC5
Modes of Operation: Modes of Operation Modes of operation is a technique for enhancing the effect of a cryptographic alg/ adapting the alg for an app. NIST SP (FIPS 81) defines 5 modes: Electronic codebook (ECB) mode Cipher Block Chaining (CBC) mode Cipher Feedback (CFB) mode Output Feedback (OFB) mode Counter (CTR) mode 35
Modes of Operation: Modes of Operation Block ciphers encrypt fixed size blocks eg. DES encrypts 64-bit blocks with 56-bit key AES uses 128 bit blocks For larger sizes, break plain text into blocks Need some way to en/decrypt arbitrary amounts of data in practice have block and stream modes Cover a wide variety of applications can be used with any block cipher 36
1. Electronic Codebook Mode(EBC): 1. Electronic Codebook Mode(EBC) Message is broken into independent blocks which are encrypted Each block is a value which is substituted, like a codebook, hence name Each block B is encoded or decoded independently of the other blocks: C i = E K (P i ) B i = D K (C i ) Uses: secure transmission of single values like ‘DES key securely’. 37
PowerPoint Presentation: 38 P1 K1 C1 Encryption
PowerPoint Presentation: Codebook- for a given key there is a unique ciphertext for every b-bit block of plaintext. Advantages: Simplicity Tolerates block loss ( eg . over network) Used to send a few block of data Disadvantage: ECB mode may reveal pattern in text, i.e. blocks that are identical, will be encrypted in the same way. 39 1. Electronic Codebook Mode(EBC)
2. Cipher Block Chaining Mode of Operation: 2. Cipher Block Chaining Mode of Operation Message is broken into blocks. Linked together in encryption operation. Each previous cipher block is chained with current plaintext block, hence name Use Initial Vector (IV) to start process , single key for blocks Input to encryption algorithm bears no fixed relationship to the plaintext block Uses: bulk data encryption, authentication 40
Cipher Block Chaining Mode of Operation: 41 Cipher Block Chaining Mode of Operation Cipher Block Chaining Mode (CBC) The input to the encryption algorithm is the XOR of the current plaintext block and the preceding ciphertext block. Repeating pattern of 64-bits are not exposed
PowerPoint Presentation: 42
PowerPoint Presentation: To produce the first block of ciphertext , an IV is XOR with the first o/p of the decryption alg to recover the first block of plaintext. The IV must be known to both the sender and receiver but be unpredictable by the 3 rd party. For max security IV should protected against unauthorized changes. This could be done by sending the IV by ECB encryption. If an opponent is able to fool the receiver into using a d/f value for IV, then the opponent is able to invert selected bits in the first block of plaintext. 43
3. Cipher Feedback (CFB) Mode: 3. Cipher Feedback (CFB) Mode Message is treated as a stream of bits Added to the output of the block cipher Result is feed back for next stage (hence name) Standard allows any number of bits (1,8, 64 or 128 etc.) to be feed back denoted CFB-1, CFB-8, CFB-64, CFB-128 etc. Most efficient to use all bits in block (64 or 128) C i = P i XOR E K (C i-1 ) C -1 = IV Uses: stream data encryption, authentication 44
PowerPoint Presentation: 45 S-bit Cipher Feedback( CFB-s)
Advantages and Limitations of CFB: Advantages and Limitations of CFB Appropriate when data arrives in bits/bytes Most common stream mode Limitation -there is a need to stall while doing block encryption after every n-bits Note that the block cipher is used in encryption mode at both ends Errors propagate for several blocks after the error Not good for “noisy” links – requires reliable transport 46
4. Outback Feedback (OFB) Mode: 4. Outback Feedback (OFB) Mode A sequence of block is encrypted with a sequence of blocks generated with the block cipher. It begins with an initialization vector and generates a series of pad vectors. This mode can tolerate block losses It can be performed in parallel, both for encryption and decryption 47
5. Counter (CTR): 5. Counter (CTR) A “new” mode, though proposed earlier Similar to OFB but encrypts a counter value rather than any feedback value Must have a different key & counter value for every plaintext block (never reused) O i = E K (i) C i = P i XOR O i uses: high-speed network encryptions 48
Advantages and Limitations of CTR: Advantages and Limitations of CTR Efficiency can do parallel encryptions in h/w or s/w can preprocess in advance of need good for bursty high speed links Random access to encrypted data blocks Provable security (good as other modes) Must ensure never reuse key/counter values, otherwise could break, like OFB 49
Location of Encryption Device: Henric Johnson 50 Location of Encryption Device Link encryption: A lot of encryption devices High level of security Decrypt each packet at every switch End-to-end encryption The source encrypt and the receiver decrypts Payload encrypted Header in the clear High Security: Both link and end-to-end encryption are needed (see Figure 2.9)
PowerPoint Presentation: Henric Johnson 51
Key Distribution: 52 Key Distribution A key could be selected by A and physically delivered to B. A third party could select the key and physically deliver it to A and B. If A and B have previously used a key, one party could transmit the new key to the other, encrypted using the old key. If A and B each have an encrypted connection to a third party C, C could deliver a key on the encrypted links to A and B.
Key Distribution (See Figure 2.10) : 53 Key Distribution (See Figure 2.10) Session key: Data encrypted with a one-time session key.At the conclusion of the session the key is destroyed Permanent key: Used between entities for the purpose of distributing session keys
PowerPoint Presentation: 54 S App SSM S App SSM KDC KDC HOST HOST Network 1 2 3 4
PowerPoint Presentation: For remaining algoritms MAC to HASH Continued with following link ‘ NS_II_MAC_HASH.ppt ’ 55