# Symmetric cryptography

Symmetric cryptography

## Principles of symmetric cryptography

• Same key used for encryption and decryption
• $E_{k}(M)=C$ ; M = plaintext (Message) , k = key, C = cipher text
• $D_{k}(C)=M$
• Fast and Efficient compared to asymmetric systems
• Fairly small key size
• Have long history (weakness are likely to be found).
• Key management is problematic
• Can be divided into two groups Block and Stream ciphers

• Unbreakable cryptosystem (in theory)
• No practical use
• Message is XOR:ed with random key
• $C=M\oplus k$
• $M=C\oplus k$
• Cannot be broken without knowing key
• Key has to be same size as Message
• Key has to be totally random
• Otherwise attacker attacks against key generation.
• Key cannot be reused
• How to store the key or do the key exchange
• securing the key is similar problem as securing the message

## Stream ciphers

• Pseudorandom number generator (PRNG) that is initialized with key.
• Initialization vector (IV) is usually used along with the key.
• Encryption is done by XOR:ing plain-text and bit-stream from PRNG $C=PRNG(k)\oplus M$
• The amount of bits handled at a time depends on the implementation.
• One byte is quite common.
• the amount of bits handled at a time affects on speed and hardware requirements.
• The change is dependant on plain character and the value coming from PRNG
• Security depends on the PRNG algorithm and key
• Output should resemble real randomness
• next output bit from algorithm should not be predictable without knowing used key
• Repeating bit patterns should be long
• The longer the sequence the harder it is to attack against
• output should pass randomness tests
• In long run all possible values should be equally represented
• Some algorithms: RC4/ARCFOUR,SEAL, A5

## LFSR sequences

• Linear feedback shift register
• simple way to generate pseudorandom bit stream
• fast but not very secure
• short LFSR example $x_{m+3}=x_{m+1}+x_{m}\:mod(2)$
• initial bitstream has to be 3 bits
• sequences repeat quite fast

## Stream cipher - RC4 /ARCFOUR/ARC4

• RC4 is pseudo random number generator.
• Generator is initialised with the key
• the result of PRNG is XORed with the plaintext
• 8-byte RC4 consists of 8*8 S-box, where is 256 elements that contains values 0-255 and which content changes during encryption
• Initialisation
• Initialisation of S-box: $S_{0}=0,S_{1}=1\ldots S_{255}=255$
• Initialisation of 256 bits vector K with key: $K_{0},K_{1}\ldots K_{255}$
• if key is less than 256 bits it can be repeated in order to get 256 bits j
• Run algorithm:
for i = 0 to 255;
$j=(j+ +)$
$j=(j+S_{i}+K_{i})\,mod\,256$
$swap(S_{i},S_{j})$
• Encryption
• Generating random byte with following algorithm. i and j are initially 0
$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}$
• In encryption the generated byte and plaintext byte are XOR:ed
• Original WLAN WEP uses RC4 with 40 bit key.

## Block ciphers

• Plaintext is divided in blocks and the blocks are encrypted one after another.
• All bits in the block affect to the encryption result (i.e. if one bit changes the encryption result is totally different)
• Different methods for combining the blocks to each other
• Can be used as a primitive for different kind of security systems
• e.g. hash value generation.
• Corner stones for block cipher are high diffusion and confusion (terms introduced by Shannon 1949)
• Diffusion: hides the relation between plaintext and ciphertext
• statistical structure of plain text is hidden inside the cipher text
• One bit in plaintext affect on several bits in cipher text
• Confusion: hides the relation between key and cipher text
• Achieved by complex substitution algorithm
• Basic operations: Subsitution and transposition
• Some algorithms: DES,3DES,Rijndael (AES) ,Blowfish

## Block cipher: DES

• Was accepted as a standard in USA November 23 1976
• AES replaced DES 2001 after open competition.
• DES serves as good example of block cipher functionality
• Uses both substitution and transposition techniques.
• Both techniques are used several times in 16 cycles of operation.
• It is hard to follow one bit change through all the 16 cycles.
• Key length is 64-bits
• In practise any 56-bit value fits as a key
• Is no longer secure against brute-force attacks, but the algorithm functionality is interesting.
• DES in action
• The data is divided in 64 bit blocks which all are encrypted one after another
• Initial permutation
• The bits in plaintext are changing their location
• No effect on security of algorithm
• Done for helping hardware implementation

## DES - key generation for cycles

• The encryption key is shortened by dropping out every 8th bit from the key by using following permutation
• This means that when creating key, 56-bit key can be created and after every 8 bits one bit is added as a parity bit. (MSB is bit number one)
• 56-bit key is divided in half
• Depending on the cycle, the bits of key are shifted to left either one or two bits
• After shifting the key halves are concatenated together again.
• The key is now run through compression permutation in order to get 48-bit key for the round.
• bits 9,18,22,25,35,38,43,54 are left out from key
• Expansion permutation (E-box)
• The 64-bit block is divided in two 32-bit halves
• Right half of block is expanded to 48 bits
• Goals of expansion
• Expand the block to same size as key
• Bigger result that can be compressed later in substitution box.
• The output relies more on single bits
• The output of E-box is XORed with 48-bit key
• Substitution ( S-Box)
• There are 8 different s-boxes which all contain 4 rows and 16 columns
• The result of E-box XORed with 48-bit key is divided in 8 6-bit subblocks a.
• Each sub-block are fed in their owwn S-box
• The first and sixth bit of sub-block tell which row is used
• The middle 4 bits show from which column the substitution value is taken
• Thus 4-bits are the output of S-box and 8*4-bits = 32 bits is the output of whole substitution process
• Permutation (P-Box)
• The output of S-box is run through simple permutation
• The result of P-box is XOR:ed with the 32-bit left half of block and becomes the new right half.
• New left half is the previous right half.
• After 16 rounds final permutation is done to concatenated left and right half
• All blocks are handled similarly

## DES decryption

• Same algortihm is used for decryption.
• Only difference is by generating the keys for cycles
• In decryption the geenrated keys are used in reverse order (i.e. key for cycle 16 is used first and so on)

## Security of DES

• Weak keys
• Produce only 1 key instead of 16T
• Rather weak keys
• Produce only two different keys .
• key pair provides same result no matter which of the keys is used.
• Possibly weak keys
• Produce only 4 different keys
• total of $4+12+48=64$ risky keys out of $72\,057\,594\,037\,927\,936$ possible keys.

## Combining block cipher blocks

• Block cipher returns a fixed size block of encrypted data. These blocks has to be combined somehow.
• The different block combining methods are called modes of operation.
• Modes are independent from the block cipher algorithms
• Modes affect significantly on the security and speed of encrypting.

## Electronic Code Book (ECB)

• Encrypted blocks are just concatenated one after another.
• Pros
• Simple and fast.
• Easy to parallerize.
• Blocks can be decrypted in any order
• One corrupted block does not mess other message
• Cons
• Input to cipher is not randomized
• Repeating structures in text are not hidden
• Codebook attacks
• The order of blocks can be switched
• Blocks can be added or removed without notice
• Too small block requires padding

## Cipher Block Chaining (CBC)

• Blocks are chained to each other
• The result of previous block encryption is combined with current block, before current block is encrypted
• XOR function is used for combination.
• On decryption, the result of decrypted block is XOR:ed with the current encrypted block
• $C_{i}=E_{k}(P_{i}\oplus C_{i-1})$
• Initialization vector (IV) is used for XOR:ing the first block
• IV is same size as the block of a cipher
• IV can be for example random data or timestamp
• IV will hide regularities in the beginning of the message.
• recurring headers of a document for example
• Pros
• Repeating patterns in plain text are covered
• With the use of IV encryption of same text with same key does not look same
• more than one message can be encrypted with same key.
• It is hard to change the places of blocks that have been encrypted
• Cons
• Slower than ECB (Due the extra XOR)
• Requires IV
• Cipher text is longer by the size of IV
• Parallerization of algorithm is not possible
• No possibility to do precalculation
• Too short blocks require padding
• Previous blocks has to be decrypted before current block
• It is possible to add blocks at the end of message.
• One bit error in block messes the current block and causes one bit error in the next block at the location of faulty bit (self healing)
• Adding or removing one bit messes the whole encryption

## Cipher-Feedback Mode (CFB)

• Making block-cipher to stream cipher with feedback from cipher stream.
• Encryption can be done in smaller blocks: $n\leq cipher\, block\, size$ (n-bit CFB)
• Functionality:
• Queue (shoft register) is filled first with IV
• Queue is encrypted and n-bits from left are XOR:ed with plaintext
• The result of XOR is sent forward as well as added at the end of queue
• The first n-bits of queu are removed and the queue is encrypted again
• Decryption is done in reverse order.
• Pros
• Repeating patterns in plain text are covered
• More messages can be encrypted with same key
• Message can be encrypted in smaller blocks.
• Good avalanche effect
• Only encryption algorithm has to be implemented.
• On some block ciphers decryption differs significantly from encryption
• cons
• Encryption cannot be parallerized
• Errors spread widely i.e. affect on the rest of message
• Other weaknesses that affect on stream ciphers.

## Output-Feedback mode (OFB)

• Making block cipher to streamcipher with feedback from encryption function
• IV is used in initialization
• Feedback is not dependant from plain/ciphertext
• $C_{i}=P_{i}\oplus S_{i}\:;\: S_{i}=E_{k}(S_{i-1})$
• For security reasons the feedback should be same size as the block used in cipher (in case of DES 64 bits)
• Pros
• Repeating patterns in plain text are covered
• Randomisation due the IV
• more messages can be encrypted with same key
• Key stream can be calculated beforehand (encryption is done with plain XOR)
• No need for padding message
• Only encryption algorithm has to be implemented.
• Cons
• Changes in the plaintext show directly in cipher text (not problem with proper IV)
• No avalanche effect
• Size of final encrypted text is P+IV
• Other common stream cipher problems

## Counter Mode (CTR)

• Making Block cipher to work like Stream cipher, with encrypting increasing counter value
• Counter is same size as cipher block
• Block cipher is used to encrypt a counter value with key. The result is XOR:ed with plaintext
• $C_{i}=P_{i}\oplus E_{k}(Counter_{i})$
• IV can be used to hide regularities in plaintext
• IV can be XORed, added or concatenated with the counter (the result should be same size as the block)
• Pros
• Repeating patterns in plain text are covered
• Randomisation due the IV
• Only encryption algorithm has to be implemented.
• Can be parallelized
• Supports random access.
• Key can be preprocesses, because there is no link to plaintext
• No need for padding message
• Cons
• Changes in the plaintext show directly in cipher text (not problem with proper IV)
• No avalanche effect
• Size of final encrypted text is P+IV
• Other common stream cipher problems

• Block cipher needs fixed size input and thus too small block has to be padded
• Some hash functions also require padding
• For short messages in RSA padding is also suggested to make cryptoanalysis harder