Outline for January 14, 1999

1. Greetings and felicitations!
   1. lassen not reachable from 169.237 network; we're trying to figure it out. You can get to it from any 128.120 host, such as toadflax
2. Quote for the Day
3. Simple substitution ciphers
   1. Go through rotor systems (Enigma)
   2. Go through one-time pads
4. Polygram substitution cipher: Playfair
   1. Key is 5 by 5 grid
   2. If m₁, m₂ in same row, c₁, c₂ are to immediate right of m₁, m₂ respectively
   3. If m₁, m₂ in same column, c₁, c₂ are below m₁, m₂
   4. If m₁ = m₂, insert null in text
   5. if m₁, m₂ in different rows and columns, c₁, c₂ form rectangle with c₁ in m₁'s row and c₂ in m₂'s row
   6. if odd number of characters in message, append null.
5. History
   1. IBM did Lucifer, submitted it in response to NIST CFP
   2. NIST (really, NSA) suggested some minor changes; major one was to make key 56 bits, not 112.
6. Show the cipher
   1. Product cipher with 64 bits in, 64 bits out, and 16 48-bit round keys generated from 56 bit key
   2. Note S-boxes are real heart of algorithm
7. Known attacks and weaknesses
   1. Complementation property: DESk(m) = (DESk'(m'))' where x' is the bitwise complement of x;
   2. Weak, semiweak keys
   3. If it's a group, multiple encipherment worthless (as group is closed under composition)
   4. Differential cryptanalysis: first version unusable as at 16 rounds, more plaintext/ciphertext pairs needed than exhaustive key trial; but for 15 rounds, cuts this time. Later versions cut it to 2⁴⁷ tries. Works by comparing xors of results with xors of corresponding plaintext.. Designers of DES knew about this one, hence the design of the S-boxes
   5. Linear cryptanalysis drops required chosen plaintext/ciphertext pairs to 2⁴² not known to designers of DES.
8. DES Modes
   1. ECB
   2. CBC
   3. note that OFB and CFB exist, essentially use DES as a pseudorandom bitstream generator; OFB feeds back before xor, CFB after
   4. Triple DES and EDE mode
9. Public Key Ciphers
   1. 2 keys, public k and private p; public key published, private key kept secret
   2. Requires: (1) given k, computationally infeasible to compute p; (2) immune to chosen plaintext attack (as adversary can generate any amount of ciphertext); (3) given C and k, computationally infeasible to find M
   3. Show confidentiality, authenticity; emphasize integrity is by-product of authenticity, except that one needs to keep the order of blocks correct
   4. Some ciphers do confidentiality and authenticity, others do only one
10. Do RSA
    1. Exponentiation cipher: C = M^e mod n, M = C^d mod n; d is private key, (e, n) is public key; must choose d first, then e so that ed mod [[phi]](n) = 1.
    2. Why? as ed mod [[phi]](n) = 1, ed = t[[phi]](n) + 1 for some integer t. Then
       C^d mod n = (M^e mod n)^d mod n
       = M^{t[[phi]](n) + 1} mod n
       = M(M^t[[phi]](n) mod n) mod n
       = M(M^[[phi]](n) mod n)^t mod n
       = M(1)^t mod n
       = M mod n
       by Fermat's Little Theorem
    3. Example: p = 5, q = 7, n = 35, [[phi]](n) = 24; choose e = 11, then d = 11. HELLO WORLD is 07 04 11 11 14 22 14 17 11 03; enciphering is C = 07¹¹ mod 35 = 28, etc. so encipherment is 28 09 16 16 14 08 14 33 16 12.
11. ACM and primitive operations
    1. Go over subjects, objects (includes subjects), and state (S, O, A) where A is ACM
    2. Transitions modify ACM entries; primitive operations follow
    3. enter r into A[s,o]
    4. delete r from A[s,o]
    5. create subject s' (note A[s',x] = A[x,s'] = ø for all x)
    6. create object o' (note A[x,o'] = ø for all x)
    7. destroy subject s'
    8. destroy object o'
12. commands
    1. command c(s1, ..., sk, o1, ..., ok)
       if r1 in A[s1, o1] and
       r2 in A[s2, o2] and
       ...
       rm in A[sm, om]
       then
       op1;
       op2;
       ...;
       opn;
       end.
    2. Example 1: creating a file
       command create_file(p, f)
       create object f;
       enter Own into A[p, f]
       enter Read into A[p, f]
       enter Write into A[p, f]
       end.
    3. Example 2:granting one process read rights to a file
       command grant_read(p, q, f)
       if Own in A[p, f]
       then
       enter Read into A[q, f]
       end.
13. What is the safety question?
    1. An unauthorized state is one in which a generic right r could be leaked into an entry in the ACM that did not previously contain r. An initial state is safe for r if it cannot lead to a state in which r could be leaked.
    2. Question: in a given arbitrary protection system, is safety decidable?
14. Mono-operational protection systems: decidable
    1. Theorem: there is an algorithm that decides whether a given mono-operational system and initial state is safe for a given generic right.
    2. Proof: finite number of command sequences; can eliminate delete, destroy.
       Ignore more than one create as all others are conditioned on access rights in the matrix. (One exception: no subjects; then we need one create subject).
       Bound: s number of subjects (possibly one more than in original), o number of objects (same), g number of generic rights; number of command sequences to inspect is at most 2^gso.

Quote

"Without harmony in the state, no military expedition can be undertaken; without harmony in the army, no battle array can be formed."

-- Sun Tzu, The Art of War, (Translated by James Clavell), Dell Publishing, New York, NY 10036 (1983).