Skip to Content
CSE4303Introduction to Computer Security (Lecture 7)

CSE4303 Introduction to Computer Security (Lecture 7)

Cryptography in Symmetric Systems

Symmetric systems

Symmetric (shared-key) encryption

  • Classical techniques
  • Computer-aided techniques
  • Formal reasoning
  • Realizations:
    • Stream ciphers
    • Block ciphers

Stream ciphers

  1. Operate on PT one bit at a time (usually), as a bit “stream”
  2. Generate arbitrarily long keystream on demand

Keystream

Keystream G(k)G(k) generated from key kk.

Encryption:

E(k,m)=m⊕G(k)E(k,m) = m \oplus G(k)

Decryption:

D(k,c)=c⊕G(k)D(k,c) = c \oplus G(k)

Security abstraction

  1. XOR transfers randomness of keystream to randomness of CT regardless of PT’s content
  2. Security depends on GG being “practically” indistinguishable from random string and “practically” unpredictable
  3. Idea: shouldn’t be able to predict next bit of generator given all bits seen so far

Keystream G(k)G(k)

  • Idea: shouldn’t be able to predict next bit of generator given all bits seen so far
  • Strategies and challenges: many!

Idea that doesn’t quite work: Linear Feedback Shift Register (LFSR)

  • Choice of feedback: by algebra
  • Pro: fast, statistically close to random
  • Problem: susceptible to cryptanalysis (because linear)

LFSR-based modifications

  • Use non-linear combo of multiple LFSRs
  • Use controlled clocking (e.g. only cycle the LFSR when another LFSR outputs a 1)
  • Etc.

Others

  • Modular arithmetic-based constructions
  • Other algebraic constructions

Hazards

  1. Weak PRG
  2. Key re-use
  3. Predictable effect of modifying CT on decrypted PT

Weak PRG

  • Makes semantic security impossible

Key re-use

Suppose:

c1=m1⊕G(k)c_1 = m_1 \oplus G(k)

and

c2=m2⊕G(k)c_2 = m_2 \oplus G(k)

Then:

c1⊕c2=m1⊕m2c_1 \oplus c_2 = m_1 \oplus m_2

This may be enough to recover m1m_1 or m2m_2 using natural language properties.

IV (Initialization Vector)

Used to avoid key re-use:

  • IV incremented per frame
  • But repeats after 2242^{24} frames
  • Sometimes resets to 0
  • Enough to recover key within minutes

Note:

  • Happens if keystream period is too short
  • Real-world example: WEP attack (802.11b)

Predictable modification of ciphertext

If attacker modifies ciphertext by XORing pp:

Ciphertext becomes:

(m⊕k)⊕p(m \oplus k) \oplus p

Decryption yields:

m⊕pm \oplus p
  • Affects integrity
  • Not CCA-secure for integrity

Summary: Stream ciphers

Pros

  • Fast
  • Memory-efficient
  • No minimum PT size

Cons

  • Require good PRG
  • Can never re-use key
  • No integrity mechanism

Note

  • Integrity mechanisms exist for other symmetric ciphers (block ciphers)
  • “Authenticated encryption”

Examples / Uses

  • RC4: legacy stream cipher (e.g. WEP)
  • ChaCha / Salsa: Android cell phone encryption (Adiantum)
Last updated on
Introduction to Computer Security (Lecture 6)Introduction to Computer Security (Lecture 8)