Notes for January 10, 1997

1. Hello
   1. Remember, no section meeting this week
2. Puzzle of the day
   1. Key point: people problem; no amount of code fixing will solve this.
3. Can we determine if something is secure or not?
   1. Need to represent system in some way
   2. Need to represent changes to protections in some way
4. Background
   1. Protection State: (S, O, A)
   2. A Access Control Matrix (Graham/Denning); give examples
   3. Primitives: enter r into A[s, o]; delete r from A[s, o]; create subject s; create object o; destroy subject s; destroy object o
   4. Commands: if (r₁ in A[x_s1, x_o1]) and ... and (r_n in A[x_sn, x_on]) then prim₁; ... prim_m
   5. Unauthorized state Q: one in which a generic right could be leaked; in other words, a command c would execute a primitive operation entering r into some cell of A not previously containing r (if not possible, initial state Q?₀ is safe or secure)
5. Basic results:
   1. There is an algorithm that decides whether a given mono-operational system and initial state is safe for a given generic right r. It is however NP-complete.
   2. It is undecidable whether a given state of a given protection system is safe (secure) for a given generic right. Reduce the halting problem to it.
   3. Implications: key word is generic; cannot get general algorithm, but if you focus on a specific system, you often can.
6. Cryptography
   1. Basic components of ciphers: substitution, transposition
   2. Classical v. public-key
   3. Attacks: ciphertext only, known plaintext, chosen plaintext, chosen ciphertext
   4. Best ciphers withstand all of these
7. Classical
   1. monoalphabetic (simple substitution): f(a) = a + k mod n
   2. example: Caesar with k = 3, RENAISSANCE -> UHQDLVVDQFH