 Symmetric cryptography

Symmetric cryptography

Principles of symmetric cryptography

• Same key used for encryption and decryption
• ; M = plaintext (Message) , k = key, C = cipher text
• 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

One time pad (OTP)

• Unbreakable cryptosystem (in theory)
• No practical use
• Message is XOR:ed with random key
• 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
• 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
• 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:
• Initialisation of 256 bits vector K with key:
• 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;

• Encryption
• Generating random byte with following algorithm. i and j are initially 0

• 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 - key generation for cycles

• 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

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

• Produce only 1 key instead of 16T
• 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 risky keys out of 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
• 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-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
• 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)
• Errors are not spreading
• 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
• 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 