16-02-2011, 09:33 AM
[attachment=8680]
Introduction to Symmetric Block Cipher
Cryptography
• Encryption algorithm also called a cipher
• Cryptography has evolved so that modern encryption and decryption use secret keys
• Cryptographic algorithms can be openly published
• Only have to protect the keys
Symmetric-Key Cryptography
• Both sender and receiver keys are the same: KA=KB
• The keys must be kept secret and securely distributed
• Thus, also called “Secret Key Cryptography”
• Data Encryption Standard (DES)
Cryptanalysis
• Brute force: try every key
• Ciphertext-only attack:
• Attacker knows ciphertext of several messages encrypted with same key (but doesn’t know plaintext).
• Possible to recover plaintext (also possible to deduce key) by looking at frequency of ciphertext letters
• Known-plaintext attack:
• Attackers observes pairs of plaintext/ciphertext encrypted with same key.
• Possible to deduce key and/or devise algorithm to decrypt ciphertext.
Cryptanalysis (2)
• Chosen-plaintext attack:
• Attacker can choose the plaintext and look at the paired ciphertext
• Attacker has more control than known-plaintext attack and may be able to gain more info about key
• Adaptive Chosen-Plaintext attack:
• Attacker chooses a series of plaintexts, basing the next plaintext on the result of previous encryption
• Examples
• Differential cryptanalysis – DES is resistant it
• Linear cryptanalysis
• Cryptanalysis attacks often exploit the redundancy of natural language
• Lossless compression before encryption removes redundancy
Examples
• Simple and non-secure ciphers
– Shift Cipher – Caesar Cipher
– Affine Cipher
– Vigenere Cipher
– Hill Cipher
• Information-secure cipher
– One-Time Pad
Confusion and Diffusion
• Terms courtesy of Claude Shannon, father of Information Theory
• “Confusion” = Substitution
• a -> b
• Caesar cipher
• “Diffusion” = Transposition or Permutation
• abcd -> dacb
• DES
Confusion and Diffusion (2)
Confusion” : a classical Substitution Cipher
• Modern substitution ciphers take in N bits and substitute N bits using lookup table: called S-Boxes
Confusion and Diffusion (3)
Diffusion” : a classical Transposition cipher
• modern Transposition ciphers take in N bits and permute using lookup table : called P-Boxes
Block Cipher
• Divide input bit stream into n-bit sections, encrypt only that section, no dependency/history between sections
In a good block cipher, each output bit is a function of all n input bits and all k key bits
Example: DES
• Data Encryption Standard (DES)
• Encodes plaintext in 64-bit chunks using a 64-bit key (56 bits + 8 bits parity)
• Uses a combination of diffusion and confusion to achieve security
• Was cracked in 1997
• Parallel attack – exhaustively search key space
• Decryption in DES – it’s symmetric! Use KA again as input and then the same keys except in reverse order
Example: DES (2)
• DES
• 64-bit input is permuted
• 16 stages of identical operation
• differ in the 48-bit key extracted from 56-bit key - complex
• R2= R1 is encrypted with K1 and XOR’d with L1
• L2=R1, …
• Final inverse permutation stage
Beyond DES
• Triple-DES: put the output of DES back as input into DES again with a different key, loop again: 3*56 = 168 bit key
• Advanced Encryption Standard (AES)
– Requirements:
• shall be designed so that the key length may be increased as needed.
• block size n = 128 bits, key size k = 128, 192, 256 bits
– Candidates: MARS, twofish, RC6, Serpent, Rijndael
– successor (Rijndael)
Encryption Mode (ECB)
• Electronic Code Book (ECB) mode for block ciphers of a long digital sequence
• Vulnerable to replay attacks: if an attacker thinks block C2 corresponds to $ amount, then substitute another Ck
• Attacker can also build a codebook of <Ck, guessed Pk> pairs
Encryption Mode (CBC)
• Cipher Block Chaining (CBC) mode for block ciphers
• Inhibits replay attacks and codebook building: identical input plaintext Pi =Pk won’t result in same output code due to memory-based chaining
• IV = Initialization Vector – use only once
Stream Cipher
• Stream ciphers
• Rather than divide bit stream into discrete blocks, as block ciphers do, XOR each bit of your plaintext continuous stream with a bit from a pseudo-random sequence
• At receiver, use same symmetric key, XOR again to extract plaintext
Encryption Mode (OFB)