CSCE 465 Lecture 11

From Notes
Jump to navigation Jump to search

« previous | Tuesday, February 19, 2013 | next »


Lecture Slides


test next week


Secret Key Cryptography

  • Intro
  • Feistel Cipher
  • DES
  • AES

Same key used for both encryption and decryption

Applications

Confidentiality

  • Transmission over insecure channel
  • Secure storage on insecure volumes

Integrity

  • Message Integrity Codes (MIC)

Authentication

  • Challenge-Response protocol: ask Alice to encrypt a known string of text, check that encrypted text is original


Block Encryption

Converts one input plaintext block of fixed size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} bits to an output ciphertext bolck of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} bits.

  • Large Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} : faster encryption, but harder data recovery
  • Small Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} : easier data recovery, but slower encryption

Key Sizes

  • 40 bits were adequate in 70s
  • 56 used by DES adequate in 80s
  • 128 adequate for now

If computers increase in power by 40% per year, need roughly 5 more bits per decade to stay "sufficiently" hard to break.


Notation

Notation Meaning
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \oplus Y} Exclusive Or
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \mid Y} Concatenation
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K\{m\}} Application of Encryption Alogrithm


Principles of Cipher design:

  1. confusion: make output as complex (non-linear) as possible
  2. diffusion: spread influence of each input bit across many output bits

Use multiple, alternating permutations (diffusion) and substitutions (confusion): S → P → S → P → ...


Basic Form of modern block ciphers

Plaintext Block Key
Preprocessing subkey generation
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} rounds of encryption subkey 1 … Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n}
Postprocessing
Ciphertext block

Feistel Cipher

Very influential template for designing a block cipher

Major benefit: can do encryption and decryption with the same hardware (same function)

Examples: DES, RC5

One Round of Feistel

To encrypt:

  1. Break input block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} into left and right halves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i}
  2. Copy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i} to create output half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}}
  3. Half block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i} and key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} are "scrambled" by function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
  4. XOR result with input half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i} to create output half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_{i+1}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} L_{i+1} &= R_i \\ R_{i+1} &= f(R_i, k_i) \oplus L_i \end{align}}

— OR —

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \text{input} &= L_i ~\mid~ R_i \\ \text{output} &= R_i ~\mid~ (f(R_i, k_i) \oplus L_i) \end{align}}

To decrypt, reverse the steps (by reversing the order of the keys)

  1. Break input block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} into left and right halves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_{i+1}}
  2. Copy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}} back into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_i}
  3. Use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{i+1}} and key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} as input to function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
  4. XOR result with input half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_{i+1}} to create output half-block Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i}

Post-processing: swap outputs

Parameters:

  • Block size
  • Key Size
  • number of rounds
  • subkey generation algorithm
  • scrambling function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}


DES

Standardized in 1976 by NBS

  • Proposed by IBM
  • A Feistel cipher

Criteria (official)

  • Provide high security
  • security in key, not algorithm
  • not pantented
  • exportable

Unofficial:

  • slow to compute on software, but fast on hardware
  • breakable by the NSA


64-bit block size 16 rounds of encryption 64 bit key length (actually 56, since every 8th bit is a parity checksum bit


  1. Initial permutation based on table (does not improve security, but makes this a feistel cipher)
  2. Throw out 8 parity bits of key
  3. Perform a circular left-shift of each part of 56-bit key, permute and discard to get 48 bit subkey
  4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} -function is an expansion of 32-bit half-block to 48 bits, XOR with subkey, substitution (shrink to 32 bits), and permutation
  5. Final permutation reverse of table (does not improve security, but makes this a feistel cipher)

Substitution is a lookup table: for 6-bit chunk b of 48-bit expanded part, b[0] | b[5] denote row, b[1] | b[2] | b[3] | b[4] denote column. output is table value o[0] | o[1] | o[2] | o[3]


Analysis

  • Were the particular details well-chosen?
  • Tables built by flipping coins?
  • Built-in exploits by the designer?

Don't know

Number of rounds should be large enough to make advanced attacks as expensive as exhaustive search for key.

S-Box (substitution) is only non-linear part of DES

  • Each row should have unique permutation of four bits

Avalanche Effect:

  • Small change in either plaintext or key should produce big change in ciphertext
  • Output bit should be inverted with probability 0.5 if any input bit is changed
  • DES Example: 0x000000000000000 and 0x800000000000000 differ by 1 bit. key: 0x16B24621C181C32; Differ by 34 bits out of 64
  • There are 4 weak keys such that K{K{m}} = m: /(0{28}|1{28})(0{28}|1{28})/ (RegExp)
  • Semiweak keys such that K1{K2{m}} = m

Cryptanalysis

Differential cryptanalysis: Exploits differences between two different plaintext blocks; provides insight into possible key values Linear cryptanalysis: exploits similarities between two different plaintext blocks;


AES

Selected from an open competition by NSA (won by Rijndael /rhine-dall/)

Similarities to DES:

  • rounds
  • round keys
  • alternate permutation+substitution

Differences:

  • not a Feistel cipher
  • Block-size = 128 bits
  • Key sizes may be 128, 192, or 256 bits
  • Secure, well-justified, fast
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_465_Lecture_11&oldid=2641"