Scribd Logo
Upload

Welcome to Scribd!

  • 57 views

    Chapter 3 - Block Ciphers and The Data Encryption Standard

    Uploaded by

    durvasikiran
    This document discusses block ciphers and the Data Encryption Standard (DES). It begins by introducing modern block ciphers and DES, which was adopted as a standard in 1977. It then explains the differences between block and stream ciphers. The majority of the document describes the design and operation of DES, including the Feistel cipher structure, key schedule, substitution boxes, encryption/decryption process, strength against brute force attacks, and differential and linear cryptanalysis techniques. It concludes by discussing block cipher design principles and modes of operation.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Chapter 3 - Block Ciphers and The Data Encryption Standard

    Uploaded by

    durvasikiran
    57 views47 pages
    This document discusses block ciphers and the Data Encryption Standard (DES). It begins by introducing modern block ciphers and DES, which was adopted as a standard in 1977. It then explains the differences between block and stream ciphers. The majority of the document describes the design and operation of DES, including the Feistel cipher structure, key schedule, substitution boxes, encryption/decryption process, strength against brute force attacks, and differential and linear cryptanalysis techniques. It concludes by discussing block cipher design principles and modes of operation.

    Original Description:

    Explains DES algorithm.

    Original Title

    DES

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses block ciphers and the Data Encryption Standard (DES). It begins by introducing modern block ciphers and DES, which was adopted as a standard in 1977. It then explains the differences between block and stream ciphers. The majority of the document describes the design and operation of DES, including the Feistel cipher structure, key schedule, substitution boxes, encryption/decryption process, strength against brute force attacks, and differential and linear cryptanalysis techniques. It concludes by discussing block cipher design principles and modes of operation.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    57 views47 pages

    Chapter 3 - Block Ciphers and The Data Encryption Standard

    Uploaded by

    durvasikiran
    This document discusses block ciphers and the Data Encryption Standard (DES). It begins by introducing modern block ciphers and DES, which was adopted as a standard in 1977. It then explains the differences between block and stream ciphers. The majority of the document describes the design and operation of DES, including the Feistel cipher structure, key schedule, substitution boxes, encryption/decryption process, strength against brute force attacks, and differential and linear cryptanalysis techniques. It concludes by discussing block cipher design principles and modes of operation.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 47

    Chapter 3 Block Ciphers and the

    Data Encryption Standard

    Modern Block Ciphers


    will now look at modern block ciphers
    one of the most widely used types of
    cryptographic algorithms
    provide secrecy and/or authentication
    services
    in particular will introduce DES (Data
    Encryption Standard)
    We will look at AES (Advanced Encryption
    Standard) adopted in 2001 later
    1

    Block vs Stream Ciphers


    block ciphers process messages in into
    blocks, each of which is then en/decrypted
    like a substitution on very big characters
    64-bits or more

    stream ciphers process messages a bit or


    byte at a time when en/decrypting
    many current ciphers are block ciphers
    1

    Block Cipher Principles


    most symmetric block ciphers are based on a
    Feistel Cipher Structure
    needed since must be able to decrypt ciphertext
    to recover messages efficiently
    block ciphers look like an extremely large
    substitution
    would need table of 264 entries for a 64-bit block
    instead create from smaller building blocks
    using idea of a product cipher
    1

    Claude Shannon and SubstitutionPermutation Ciphers


    in 1949 Claude Shannon introduced idea of
    substitution-permutation (S-P) networks
    modern substitution-transposition product cipher

    these form the basis of modern block ciphers


    S-P networks are based on the two primitive
    cryptographic operations we have seen before:
    substitution (S-box)
    permutation (P-box)

    provide confusion and diffusion of message


    1

    Confusion and Diffusion


    cipher needs to completely obscure
    statistical properties of original message
    a one-time pad does this
    more practically Shannon suggested
    combining elements to obtain:
    diffusion dissipates statistical structure
    of plaintext over bulk of ciphertext
    confusion makes relationship between
    ciphertext and key as complex as possible
    1

    Feistel Cipher Structure


    Horst Feistel devised the feistel cipher
    based on concept of invertible product cipher

    partitions input block into two halves


    process through multiple rounds which
    perform a substitution on left data half
    based on round function of right half & subkey
    then have permutation swapping halves

    implements Shannons substitutionpermutation network concept


    1

    Feistel Cipher Structure

    Feistel Cipher Design Principles


    block size
    increasing size improves security, but slows cipher

    key size
    increasing size improves security, makes exhaustive key
    searching harder, but may slow cipher

    number of rounds
    increasing number improves security, but slows cipher

    subkey generation
    greater complexity can make analysis harder, but slows cipher

    round function
    greater complexity can make analysis harder, but slows cipher

    fast software en/decryption & ease of analysis


    are more recent concerns for practical use and testing
    1

    Feistel Cipher Decryption

    Data Encryption Standard (DES)


    most widely used block cipher in world for
    a long time; will change soon
    adopted in 1977 by NBS (now NIST)
    as FIPS PUB 46

    encrypts 64-bit data using 56-bit key


    has widespread use
    has been considerable controversy over
    its security
    1

    DES History
    IBM developed Lucifer cipher
    by team led by Feistel
    used 64-bit data blocks with 128-bit key

    then redeveloped as a commercial cipher


    with input from NSA and others
    in 1973 NBS issued request for proposals
    for a national cipher standard
    IBM submitted their revised Lucifer which
    was eventually accepted as the DES
    1

    DES Design Controversy


    although DES standard is public
    was considerable controversy over design
    in choice of 56-bit key (vs Lucifer 128-bit)
    and because design criteria were classified

    subsequent events and public analysis


    show in fact design was appropriate
    DES has become widely used, esp in
    financial applications
    1

    DES Encryption

    Initial Permutation IP

    first step of the data computation


    IP reorders the input data bits
    even bits to LH half, odd bits to RH half
    quite regular in structure (easy in h/w)
    example:
    IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)

    DES Round Structure


    uses two 32-bit L & R halves
    as for any Feistel cipher can describe as:
    Li = Ri1
    Ri = Li1 xor F(Ri1, Ki)

    takes 32-bit R half and 48-bit subkey and:


    expands R to 48-bits using perm E
    adds to subkey
    passes through 8 S-boxes to get 32-bit result
    finally permutes this using 32-bit perm P
    1

    DES Round Structure

    Substitution Boxes S
    have eight S-boxes which map 6 to 4 bits
    each S-box is actually 4 little 4 bit boxes
    outer bits 1 & 6 (row bits) select one rows
    inner bits 2-5 (col bits) are substituted
    result is 8 lots of 4 bits, or 32 bits

    row selection depends on both data & key


    feature known as autoclaving (autokeying)

    example:
    S(18 09 12 3d 11 17 38 39) = 5fd25e03
    1

    DES Key Schedule


    forms subkeys used in each round
    consists of:
    initial permutation of the key (PC1) which
    selects 56-bits in two 28-bit halves
    16 stages consisting of:
    selecting 24-bits from each half
    permuting them by PC2 for use in function f,
    rotating each half separately either 1 or 2 places
    depending on the key rotation schedule K
    1

    DES Decryption

    decrypt must unwind steps of data computation


    with Feistel design, do encryption steps again
    using subkeys in reverse order (SK16 SK1)
    note that IP undoes final FP step of encryption
    1st round with SK16 undoes 16th encrypt round
    .
    16th round with SK1 undoes 1st encrypt round
    then final FP undoes initial encryption IP
    thus recovering original data value
    1

    Avalanche Effect
    key desirable property of encryption alg
    where a change of one input or key bit
    results in changing approx half output bits
    making attempts to home-in by guessing
    keys impossible
    DES exhibits strong avalanche

    Strength of DES Key Size


    56-bit keys have 256 = 7.2 x 1016 values
    brute force search looks hard
    recent advances have shown is possible
    in 1997 on Internet in a few months
    in 1998 on dedicated h/w (EFF) in a few days
    in 1999 above combined in 22hrs!

    still must be able to recognize plaintext


    alternative to DES adopted in May 2001
    1

    Strength of DES Timing Attacks


    attacks actual implementation of cipher
    use knowledge of consequences of
    implementation to derive knowledge of
    some/all subkey bits
    specifically use fact that calculations can
    take varying times depending on the value
    of the inputs to it
    particularly problematic on smartcards
    1

    Strength of DES Analytic Attacks


    now have several analytic attacks on DES
    these utilise some deep structure of the cipher
    by gathering information about encryptions
    can eventually recover some/all of the sub-key bits
    if necessary then exhaustively search for the rest

    generally these are statistical attacks


    include
    differential cryptanalysis
    linear cryptanalysis
    related key attacks
    1

    Differential Cryptanalysis
    one of the most significant recent (public)
    advances in cryptanalysis
    known by NSA in 70's cf DES design
    Murphy, Biham & Shamir published 1990
    powerful method to analyse block ciphers
    used to analyse most current block
    ciphers with varying degrees of success
    DES reasonably resistant to it
    1

    Differential Cryptanalysis
    a statistical attack against Feistel ciphers
    uses cipher structure not previously used
    design of S-P networks has output of
    function f influenced by both input & key
    hence cannot trace values back through
    cipher without knowing values of the key
    Differential Cryptanalysis compares two
    related pairs of encryptions
    1

    Differential Cryptanalysis
    Compares Pairs of Encryptions
    with a known difference in the input
    searching for a known difference in output
    when same subkeys are used

    Differential Cryptanalysis
    have some input difference giving some
    output difference with probability p
    if find instances of some higher probability
    input / output difference pairs occurring
    can infer subkey that was used in round
    then must iterate process over many
    rounds (with decreasing probabilities)
    1

    Differential Cryptanalysis

    Differential Cryptanalysis
    perform attack by repeatedly encrypting plaintext pairs
    with known input XOR until obtain desired output XOR
    when found
    if intermediate rounds match required XOR have a right pair
    if not then have a wrong pair, relative ratio is S/N for attack

    can then deduce keys values for the rounds


    right pairs suggest same key bits
    wrong pairs give random values

    for large numbers of rounds, probability is so low that


    more pairs are required than exist with 64-bit inputs
    Biham and Shamir have shown how a 13-round iterated
    characteristic can break the full 16-round DES
    1

    Linear Cryptanalysis
    another recent development
    also a statistical method
    must be iterated over rounds, with
    decreasing probabilities
    developed by Matsui et al in early 90's
    based on finding linear approximations
    can attack DES with 247 known plaintexts,
    still in practise infeasible
    1

    Linear Cryptanalysis
    Find linear approximations with prob p !=

    P[i1,i2,...,ia](+)C[j1,j2,...,jb] =
    K[k1,k2,...,kc]
    where ia,jb,kc are bit locations in P,C,K

    gives linear equation for key bits


    get one key bit using max likelihood alg
    using a large number of trial encryptions
    effectiveness given by: |p|
    1

    Block Cipher Design Principles


    basic principles still like Feistel in 1970s
    number of rounds
    more is better, exhaustive search best attack

    function f:
    provides confusion, is nonlinear, avalanche

    key schedule
    complex subkey creation, key avalanche
    1

    Modes of Operation
    block ciphers encrypt fixed size blocks
    eg. DES encrypts 64-bit blocks, with 56-bit key
    need way to use in practise, given usually have
    arbitrary amount of information to encrypt
    four were defined for DES in ANSI standard
    ANSI X3.106-1983 Modes of Use
    have block and stream modes

    Electronic Codebook Book (ECB)


    message is broken into independent
    blocks which are encrypted
    each block is a value which is substituted,
    like a codebook, hence name
    each block is encoded independently of
    the other blocks
    Ci = DESK1 (Pi)

    uses: secure transmission of single values


    1

    Electronic Codebook Book (ECB)

    Advantages and Limitations of ECB


    repetitions in message may show in
    ciphertext
    if aligned with message block
    particularly with data such graphics
    or with messages that change very little,
    which become a code-book analysis problem

    weakness due to encrypted message


    blocks being independent
    main use is sending a few blocks of data
    1

    Cipher Block Chaining (CBC)


    message is broken into blocks
    but these are linked together in the
    encryption operation
    each previous cipher blocks is chained
    with current plaintext block, hence name
    use Initial Vector (IV) to start process
    Ci = DESK1(Pi XOR Ci-1)
    C-1 = IV

    uses: bulk data encryption, authentication


    1

    Cipher Block Chaining (CBC)

    Advantages and Limitations of CBC


    each ciphertext block depends on all message blocks
    thus a change in the message affects all ciphertext
    blocks after the change as well as the original block
    need Initial Value (IV) known to sender & receiver
    however if IV is sent in the clear, an attacker can change bits of
    the first block, and change IV to compensate
    hence either IV must be a fixed value (as in EFTPOS) or it must
    be sent encrypted in ECB mode before rest of message

    at end of message, handle possible last short block


    by padding either with known non-data value (eg nulls)
    or pad last block with count of pad size
    eg. [ b1 b2 b3 0 0 0 0 5] <- 3 data bytes, then 5 bytes pad+count
    1

    Cipher FeedBack (CFB)

    message is treated as a stream of bits


    added to the output of the block cipher
    result is feed back for next stage (hence name)
    standard allows any number of bit (1,8 or 64 or
    whatever) to be feed back
    denoted CFB-1, CFB-8, CFB-64 etc

    is most efficient to use all 64 bits (CFB-64)


    Ci = Pi XOR DESK1(Ci-1)
    C-1 = IV

    uses: stream data encryption, authentication


    1

    Cipher FeedBack (CFB)

    Advantages and Limitations of CFB


    appropriate when data arrives in bits/bytes
    most common stream mode
    limitation is need to stall while do block
    encryption after every n-bits
    note that the block cipher is used in
    encryption mode at both ends
    errors propogate for several blocks after
    the error
    1

    Output FeedBack (OFB)

    message is treated as a stream of bits


    output of cipher is added to message
    output is then feed back (hence name)
    feedback is independent of message
    can be computed in advance
    Ci = Pi XOR Oi
    Oi = DESK1(Oi-1)
    O-1 = IV

    uses: stream encryption over noisy channels


    1

    Output FeedBack (OFB)

    Advantages and Limitations of OFB


    used when error feedback a problem or where need to
    encryptions before message is available
    superficially similar to CFB
    but feedback is from the output of cipher and is
    independent of message
    a variation of a Vernam cipher
    hence must never reuse the same sequence (key+IV)

    sender and receiver must remain in sync, and some


    recovery method is needed to ensure this occurs
    originally specified with m-bit feedback in the standards
    subsequent research has shown that only OFB-64
    should ever be used
    1

    Summary
    have considered:
    block cipher design principles
    DES
    details
    strength

    Differential & Linear Cryptanalysis


    Modes of Operation
    ECB, CBC, CFB, OFB
    1

    You might also like