Encryption Systems

Shared Secret Key

Public Key

 

Threats to Communications in Computer Systems

•      Disclosure

–   wire tapping attack

–   controlled when communications are encrypted with keys known only to authorized entities

•      Loss of integrity

–   masquerading attack

–   corruption attack

–   controlled by authentication and encryption when only authorized entities have keys

 

Secret Key Systems

•      Many also known as symmetric systems

•      Shared Secret Keys

–     A message, M, encrypted with a key K is denoted as [M]K

–   The encrypted message is then decrypted with the same key K denoted as [[M]K]K = M

•      What are the advantages and disadvantages of these systems?

 

Public Key Systems

•      Also known as asymmetric systems

•      A message, M, from A to B is encrypted with B’s  public key and decrypted with B’s private key

–   This encrypted message is denoted as [M]KBpub

–   The encrypted message is then decrypted with B’s private key denoted as [[M]KBpub]KBpriv  = M

•      What are the advantages and disadvantages of these systems?

 

Public Key System for Authentication

•      Reverse use of the private and public keys can authenticate a message

–   A message encrypted with an entity’s private key can only be decrypted with the same entity’s public key, [[M]KApriv]KApub  = M

–     For additional confidentiality an encrypted message from A to B would be [[M]KApriv]KBpub

–   Where  [[[[M]KApriv]KBpub ] KBpriv]KApub = M

 

RSA Algorithm for Public Key Encryption

•      Rivest, Shamir, and Adleman of MIT in 1977 devised this famous implementation

•      Involves multiplication of large prime numbers to produce keys

•      Relies in part on the time factor

–   large numbers are extremely difficult to factor

–   Will this always be true?

 

RSA Implementation -- Preliminary steps

        1. Select two large prime numbers p and q that are each more than 100 digits long

        2. Compute n = pq and ψ = (p - 1)(q - 1)

        3. Choose an integer E between 3 and ψ which has no common factors with ψ

        4. Select an integer D, such that D*E differs from 1 by a multiple of ψ

        5. Make E and n public, but keep p, q, D, and ψ private

 

Problems of Secret Key Systems

•      Compromised keys can be used for masquerading and disclosure attacks

•      Key distribution can be complex

•      Not scalable in large systems

•      Many secret (symmetric) key systems are weak compared to PKI approaches

 

DES Overview

•      Purpose is to be efficient and unbreakable

•      Basic functionality

–   initial permutation of input cleartext

–   sixteen rounds of substitutions and permutations

–   final inverse permutation resulting in output ciphertext

•      The same algorithm is used to encode and decode

 

Some Details of DES

•      Algorithm operates on 64-bit blocks of input cleartext

•      Uses a 56-bit key for encryption

•      During each round the key is transposed resulting in a new 48-bit key

•      Successive rounds involve alternating substitutions and transpositions of different portions (left and right halves)

 

S-Boxes

•      Substitutions are performed by eight S-boxes

•      The 48-bit input is divided into eight 6-bit blocks

•      By substitution the 6-bit blocks are reduced to 4-bit blocks

•      The 4-bit blocks are concatenated for a 32-bit output

 

To Release or Not To Release

•      Should details of algorithms be kept secret?

•      Pro -- Designers of algorithms need to demonstrate that their algorithms are unbreakable

–   This involves releasing details of the algorithm

•      Con -- Explainable routines increase the vulnerability of many algorithms

 

Weaknesses in DES

•      Key length

•      Weak keys

•      Semi-Weak keys

•      Unknown design weaknesses

•      Key clustering

•      Linear and differential analysis

DES-X

•      DES-X is a strengthened variant of DES

–   supported by RSA Data Security’s toolkit

•      Difference between DES and DES-X

–   input plaintext and output from DES are both bitwise XORed with an additional 64-bit keys

•      Main motivation -- to provide improved protection from exhaustive key searches

 

Triple DES

•      Uses two keys in a special way to improve protection

•      Two keys are used K1 and K2

–   sender encrypts with K1, then decrypts with K2, and then encrypts again with K1

–   receiver decrypts with K1, then encrypts with K2, and then decrypts with K1

 

Simple DES Application

•      In DES 64-bit blocks of data are encrypted at a time

•      If A, B, C, … are 64-bit bocks of data then the encrypted form looks like E(A)E(B)E(C)…

•      If the blocks of plaintext are ABBA then the ciphertext is E(A)E(B)E(B)E(A)

•      What is the problem here?

Cipher Block Chaining

•      Uses added diffusion on the blocks of data

•      The encryption of each block of data is not only based on the data in the block, but on the previously encrypted blocks also

•      So, if the blocks of data are ABA, the ciphertext is

•      E(A)E(B, E(A))E(A, E(B, E(A)))

 

The AES Encryption System

The AES Contest Requirements

 

–   Unclassified

–   Publicly disclosed

–   Available for worldwide use, royalty-free

–   Symmetric 128 bit block cipher algorithms

–   Key sizes of 128, 192, and 256 bits

 

 

Overview of Rijndael

–   Fast and easily implemented

–   Uses repeat cycles (rounds)

–   Different number of cycles for the different size keys

–   Steps of each cycle

•    Byte substitution

•    Shift row

•    Mix columns

•    Add subkey

 

Comparison of DES and AES

–   Key length

•   DES remains fixed at 56 bits

•   AES can be 128, 192, 256 or more if needed

 

–   Number of Cycles

•   DES remains fixed at 16

•   AES is more flexible: number can be increased

 

–   DES has been proven in the field