Notes for January 10, 1997
Remember, no section meeting this week
Puzzle of the day
Key point: people problem; no amount of code fixing will solve this.
Can we determine if something is secure or not?
Need to represent system in some way
Need to represent changes to protections in some way
Protection State: (S, O, A)
A Access Control Matrix (Graham/Denning); give examples
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
Commands: if (r1 in
and ... and (rn in
then prim1; ... primm
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?0 is
safe or secure)
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.
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.
Implications: key word is generic; cannot get general algorithm,
but if you focus on a specific system, you often can.
Basic components of ciphers: substitution, transposition
Classical v. public-key
Attacks: ciphertext only, known plaintext, chosen plaintext, chosen ciphertext
Best ciphers withstand all of these
monoalphabetic (simple substitution):
f(a) = a + k mod n
example: Caesar with k = 3, RENAISSANCE -> UHQDLVVDQFH
You can also see this document as a
Binhex Framemaker version 5 document,
plain ASCII text document.
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 1/23/97