Operating Systems Lecture Notes

2014 December 9 • Cryptographic Security

---

Outline

• Cryptography
  • One-Time Pad
  • Symmetric-Key Cryptography
  • Asymmetric-Key Cryptography
• Breaking Cryptography
• Passwords

Cryptography

• Cryptography is a fundamental data transformation in security.
• A cryptographic algorithm (a cypher) obscures (encrypts) data relative to a secret (a key).
• The algorithm (or a related one) also unobscures (decrypts) the obscure data relative to the secret (or a related one).
• Encrypting or decrypting data without the secret should be impossible.

Cypher Example

• The Ceasar cypher shifts letters in an alphabet A by integer k.
  • Encryption: C_i → C_{(i + k) mod |A|}.
  • Decryption: C_i → C_{(i - k) mod |A|}.
  • Key: k
• Example:
  • if k = 5, cow encrypts to htb.
  • if k = 4, htb decrypts to dpx.

Another Example

$ od -t x1z pt
0000000 68 65 6c 6c 6f 0a                                >hello.<

$ aescrypt2 0 pt ct key

$ od -t x1z ct
0000000 c6 25 e6 54 8c cf 34 df ab 51 c9 ba 88 04 d4 f6  >.%.T..4..Q......<
0000020 ab c9 d7 c7 5e 4d 9b 1d bf aa 9a 42 d4 98 7f 9a  >....^M.....B....<
0000040 61 3a 37 cb fe 26 ce 68 e1 79 d1 1c 4f 5b 31 6a  >a:7..&.h.y..O[1j<
0000060 d1 fc fc 50 be d8 15 7a ae 21 f8 d4 db 40 53 03  >...P...z.!...@S.<

$ aescrypt2 1 ct pt2 key

$ od -t x1z pt2
0000000 68 65 6c 6c 6f 0a                                >hello.<

$ 

Cryptographic Security

• A secure cypher is impossible to decrypt without the key.
  • There’s one mathematically proven secure cypher: the one-time pad cypher.
• All other cyphers may be secure.
  • Security comes from the computational complexity of decrypting without a key.
  • This is fragile, technology-dependent security.
    • R.I.P. DES.

One-Time Pad

• The Vernam cypher: If the plain text is n bits long, generate a string of n random bits.
  • The one-time pad key.
• Bit i of the cypertext is
  • c_i = p_i ⊕ k_i
• The cyphertext recipient recovers bit i of the plain text with
  • p_i = c_i ⊕ k_i
• Sender and receiver throw away the key.

One-Time Pad Security

• If the key is truly random, the cypher text is equally likely to decode to any message.

  Meet me at one
  Meet me at six
  Kill the queen

• Losing randomness lets patterns creep into the cyphertext.
  • Reusing keys loses lots of randomness.

Symmetric-Key Cryptography

• A symmetric-key cypher uses the same key for encryption and decryption.

  

  E:Encryption algorithm
  D:Decryption algorithm
  K:Key
  P:Plaintext (data)
  C:Cyphertext
  

Symmetric Techniques

• Cryptographic algorithms combine character substitution and transposition techniques.
• Substitution: plaintext characters are mapped to other plaintext characters.
  • The Caesar cypher.
• Transposition: permute a plaintext character sequence.

  Most modern cyphers: DES, AES, …

Example Symmetric Cypher

• 

Example Use

• Alice and Bob know algorithms E and D and agree on secret key k.
• Alice computes E(M, k) = M_k.
• Alice sends M_k to Bob.
• Bob computes D(M_k, k) = M (he hopes).
• In theory, M_k cannot be understood, nor undetectably tampered with.

Asymmetric-Key Cryptography

• An asymmetric-key cypher uses different but related keys for encryption and decryption.

  

  E:Encryption algorithm
  D:Decryption algorithm
  K_BP:Bob’s public key
  K_BS:Bob’s secret key
  P:Plaintext (data)
  C:Cyphertext
  

Breaking Cryptography

• A cryptographic algorithm is broken when cyphertext can be decrypted without a key.
  • Or the key can be recovered from the cypertext (WiFi security).
• Practically, quasi-security comes from the difficulty of breaking cyphers.
  • A message with a useful life of X years should be protected by a cypher that takes at least X years to break.
  • A common, but dangerous, interpretation.

Problem Solved?

• Are we done? Does good cryptography provide security?
• Unfortunately, no.
  • Generating good keys is hard.
  • Good keys are inconvenient to handle.
  • Distributing keys is hard and expensive.
• Cryptography is ineffective for other common attack points.
  • Physical security, social engineering, …

Passwords

• An artificial secret a person can know.
• A plaintext password hashed into an encrypted form.
  • But never decrypted.
• Hashed passwords stored, not plaintext ones.
• Hash a candidate password and find result to the list.
  • A match is taken as an authentication.

Attacking Passwords

• The hashing algorithm is known.
  • Steal the hashed password list.
• The dictionary attack:
  • A dictionary of well-known passwords.
  • Feed candidates into the program.
• Rainbow-table attack: a dictionary attack using hash tables.
  • Pre-hash the passwords into a hash table (the rainbow table).

Defending Passwords

• Force people to constantly create “good” passwords.
  • Which they write on a PostIt stuck to their terminal.
• Salt is a random number added to a password.
  • Hash password_x + salt_x for person X.
  • Keep a separate list of (X, salt_x) pairs.
• Two-factor authentication.
  • Passwords + something else.

One-Time Passwords

• Continuously create new passwords.
  • Ideally, each password is used at most once.
• Synchronization between challenger and challenged.
  • Encrypt time + salt.
  • Iteratively encrypt a base password.

Summary

• Cryptography is the bases of many information protection strategies.
• Don't be an amateur cryptographer.
• Authentication assigns an identity to an agent.

References

• Communication Theory of Secrecy Systems by Claude Shannon in Bell System Technical Journal (USA: AT&T Corporation), October 1949.

Credits

• enigma machine by David Perry under a Creative Commons BY NC SA license.

---

This page last modified on 2011 October 9.