- Greetings and felicitations!
*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*

- Quote for the Day
- Simple substitution ciphers
- Go through rotor systems (Enigma)
- Go through one-time pads

- Polygram substitution cipher: Playfair
- Key is 5 by 5 grid
- If
*m*_{1},*m*_{2}in same row,*c*_{1},*c*_{2}are to immediate right of*m*_{1},*m*_{2}respectively - If
*m*_{1},*m*_{2}in same column,*c*_{1},*c*_{2}are below*m*_{1},*m*_{2} - If
*m*_{1}=*m*_{2}, insert null in text - if
*m*_{1},*m*_{2}in different rows and columns,*c*_{1},*c*_{2}form rectangle with*c*_{1}in*m*_{1}'s row and*c*_{2}in*m*_{2}'s row - if odd number of characters in message, append null.

- History
- IBM did Lucifer, submitted it in response to NIST CFP
- NIST (really, NSA) suggested some minor changes; major one was to make key 56 bits, not 112.

- Show the cipher
- Product cipher with 64 bits in, 64 bits out, and 16 48-bit round keys generated from 56 bit key
- Note S-boxes are real heart of algorithm

- Known attacks and weaknesses
- Complementation property:
DES
*k*(*m*) = (DES*k*'(*m*'))' where*x*' is the bitwise complement of*x*; - Weak, semiweak keys
- If it's a group, multiple encipherment worthless (as group is closed under composition)
- 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
^{47}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 - Linear cryptanalysis drops required chosen plaintext/ciphertext pairs to
2
^{42}not known to designers of DES.

- Complementation property:
DES
- DES Modes
- ECB
- CBC
- note that OFB and CFB exist, essentially use DES as a pseudorandom bitstream generator; OFB feeds back before xor, CFB after
- Triple DES and EDE mode

- Public Key Ciphers
- 2 keys, public
*k*and private*p*; public key published, private key kept secret - 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* - Show confidentiality, authenticity; emphasize integrity is by-product of authenticity, except that one needs to keep the order of blocks correct
- Some ciphers do confidentiality and authenticity, others do only one

- 2 keys, public
- Do RSA
- Exponentiation cipher:
*C*=*M*mod^{e}*n*,*M*=*C*mod^{d}*n*;*d*is private key, (*e*,*n*) is public key; must choose*d*first, then*e*so that*ed*mod [[phi]](*n*) = 1. - Why? as
*ed*mod [[phi]](*n*) = 1,*ed*=*t[[phi]]*(*n*) + 1 for some integer*t*. Then

*C*mod^{d}*n*= (*M*mod^{e}*n*)mod^{d}*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 - 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^{11}mod 35 = 28,*etc*. so encipherment is 28 09 16 16 14 08 14 33 16 12.

- Exponentiation cipher:
- ACM and primitive operations
- Go over subjects, objects (includes subjects), and state (
*S*,*O*,*A*) where*A*is ACM - Transitions modify ACM entries; primitive operations follow
**enter***r***into***A*[*s*,*o*]**delete***r***from***A*[*s*,*o*]**create subject***s'*(note*A*[*s'*,*x*] =*A*[*x*,*s'*] = ø for all*x*)**create object***o'*(note*A*[*x*,*o'*] = ø for all*x*)**destroy subject***s'***destroy object***o'*

- Go over subjects, objects (includes subjects), and state (
- commands
**command***c*(*s*1, ...,*s*k,*o*1, ...,*o*k)**if***r*1**in***A*[*s*1,*o*1]**and**

*r*2**in***A*[*s*2,*o*2]**and**...

*r*m**in***A*[*s*m,*o*m]**then**

*op*1;

*op*2;

...;

*op*n;**end.**- 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.** - 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.**

- What is the safety question?
- 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. - Question: in a given arbitrary protection system, is safety decidable?

- An unauthorized state is one in which a generic right
- Mono-operational protection systems: decidable
- Theorem: there is an algorithm that decides whether a given mono-operational system and initial state is safe for a given generic right.
- 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.**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).

You can get this document in ASCII text, Framemaker+SGML version 5.5, PDF (for Acrobat 3.0 or later), or Postscript.

Send email to cs253@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562