Outline for January 14, 1999
- 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 m1, m2 in same row,
c1, c2 are to immediate
right of m1, m2 respectively
- If m1, m2 in same column,
c1, c2 are below
- If m1 = m2, insert null in text
- if m1, m2 in different rows and columns,
form rectangle with c1 in m1's
row and c2 in m2's row
- if odd number of characters in message, append null.
- 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:
DESk(m) = (DESk'(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
- 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
247 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
242 not known to designers of DES.
- DES Modes
- 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
- Do RSA
- Exponentiation cipher: C = Me mod n,
M = Cd mod 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
Cd mod n =
(Me mod n)d mod n
= Mt[[phi]](n) + 1 mod n
= M(Mt[[phi]](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 = 0711 mod 35 = 28, etc. so
encipherment is 28 09 16 16 14 08 14 33 16 12.
- 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'
- command c(s1, ..., sk, o1, ...,
if r1 in A[s1, o1]
r2 in A[s2, o2] and
rm in A[sm, om]
- Example 1: creating a file
create object f;
Own into A[p, f]
Read into A[p, f]
Write into A[p, f]
- Example 2:granting one process read rights to a file
grant_read(p, q, f)
if Own in A[p, f]
enter Read into A[q, f]
- 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?
- 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,
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 2gso.
"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
Framemaker+SGML version 5.5,
PDF (for Acrobat 3.0 or later),
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 1/20/99