View page as slide show

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
  • Advantages:
    • 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
    • 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+ +)
  • Encryption
    • Generating random byte with following algorithm. i and j are initially 0
      i=(i+1)\: mod\:256
      j=(j+S_{i})\: mod\:256
      t=(S_{i}+S_{j})\: mod\:256
    • 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.
  • Error spreading
    • 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)
    • 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
    • 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

Padding block

  • 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
  • Bit padding
    • Single 1 bit is added at the end of message and after that as many 0 bits as required.
    • RFC 1321
  • Byte padding
    • Padding is done with whole bytes.
    • The padding bytes content is the amount of padded bytes required
    • RFC 3852
  • Padding with random bits or regular bit pattern
    • Last byte informs the amount of used bits for padding
    • All messages have to be padded
Last modified: 2013/07/01 14:42