Protocol failures

Types:
------
  - exploit properties of crytography algorithm
  - exploit implementation of cryptography algorithm
  - weakness in protocol itself
  - system level failures


Protocol failure:
-----------------
Instance where the protocol fails to the advertised level of security or
authentification


RSA Algorithm:
--------------
primes p, q   n = p*q
e*d = 1 mod phi (n)
(n, e) is public
d, p, and q are private

To sign M, S = M^d mod n, S^e = M mod n


Security requirement:
---------------------
No party that does not know d, p, q should be able to produce a
valid signature on any message


Notary Protocol
Goal off attacks:
-----------------
Obtain a signature for P without the notary actually signing P,
P^d mod n is signature

Attacker:
---------
Choose x arbitrarily and compute X^(-1) mod n
Compute Y = X^e mod n

Note:  Y^d = X mod n

Now, compute M = Y * P
Ask notary to sign M, produce  S = M^d mod n

	M^d
	X^(-1) * M^d = X^(-1) * (Y * P)^d 
		         = X^(-1) * Y^d * P^d mod n = P^d mod n

For all X, M, d, n     (X * M)^d = X^d * M^d mod n

To defeat this attack, must destroy ability to exploit multiplicative structure.

General design principle:
-------------------------
Only sign documents that have a predetermined structure


Common modulus protocols:
-------------------------
Take RSA with modulus  m = p * q
and  generate {e _i, d_i} for each participant i

 	Y = X^e_i mod m
	S = X^d_i mod m

Say a message X is encrypted with 2 public keys whose e_i's are relative
prime

insider knows one of d_i

outsider attack:
----------------
Y_i = X^e_i mod m
Y_j = X^e_j mod m

Assume Y_i and Y_j are relative prime
Since e_i & e_j are relative prime, can find r and s such that
	r*e_i + s*e_j = 1

	r*5 + s*17 = 1, r = 7, s = 2
	Either r or s must be negative.

Say r is negative
Compute Y^(-1) mod m which equals X^(-e_i)
	(Y_i^(-1))^(-r) * Y_j^s = (X^(-e_i))^(-r) * (X^e_j)^s

	X^(e_i * r + e_j * s) = X

Insider attack:
---------------
If can factor m, you know all secret keys

First, find nontrivial square root m
   i.e.  b^2 =1 mod m
         b != -1 or 1 

Let e_1, d_1 be a user's exponents 
e_1 * d_1 = 1 mod phi (m)

So, e_1 * d_1- 1 = c * phi (m) for some c
e_1 * d_1 - 1 = 2^k * x where x is odd for some k


Probabilistic Algorithm -- for finding nontrivial square root
-----------------------
1.  pick at random a gcd (a, m) = 1, 1 < a < m - 1
2.  find smallest positive integer j which satisfies 
	a^(2^j * x) = 1mod m
     This exists because 2^k * x is a multiple of phi (m)

3.  Let b = a^(2^(j-1) * x)
     If b != -1 mod m, it is a nontrivial square root.

4.  If b = -1 mod m go to 1.

Algorithm fails 50% of the time.
Expected # of trials <= 2

Given b, b^2 = 1 mod m so b^2 - 1 = 0 mod m
	(b + 1) * (b - 1) = s*m = s*p*q for some integers s

Since 1 < b < m, 0 < b - 1< b + 1 < m = p*q
Obviously both p & q cannot divide b - 1 or b + 1

Since (b + 1)*(b - 1) = s*p*q and p & q don't both divide b + 1 or b - 1,
the gcd (b + 1, m) must be p or q.

So apply Euclidean algorithm to b + 1 and m to find p & q, this gives
factorization   phi (m) = (p - 1)*(q - 1).

Moral:  Can't have a common modulus in RSA system


Low exponent failure:
---------------------
  --  low exponent can be used to speed up one operation
	d, e small ( < 1000 bits )
	e*d = 1 mod phi (m)
	M^d mod m  -- fast
	C^e mod m  -- slow


Chinese Remainder Theorem:
--------------------------
Y_1 = X mod n_1 
Y_2 = X mod n_2
Y_3 = X mod n_3

n_i's are relatively prime

can compute Y = X mod (n_1 * n_2 * n_3) 

Take RSA system where each user picks his own p & q such that p*q = n.
Each user computes e_i and d_i and publishes e_i.

Problem if all users have e_i = 3 and message is sent to e_i users.

Take e_i = 3.  Encrypt a message for users 2, 3, 4.

C_2 = M^3 mod n_2
C_3 = M^3 mod n_3
C_4 = M^3 mod n_4

If n_2, n_3 and n_4 are not relatively prime, then it reduces to common
modulus attack.

Y = M^3 mod (n_2 * n_3 * n_4)

but M^3 < n_2 * n_3 * n_4 so no wrap-around occurs.

M - Y^(1/3)

To fix:  Add a timestamp to every message.  Then M is different.
But:  Halstad breaks this.

Moral:  Don't pick e to be too small.
Designer principle:  Pick large random e.


Low Entropy in public key systems:
----------------------------------
  --  if plaintext has low entropy
      --  pre-encrypt all possible plaintexts
      --  look for a match
      --  telephone 

Moral:  When creating a cryptosystem, add entropy to plaintext if chosen
        attacks are possible.


Timing attacks:
---------------
Modular exponent    R = Y^x mod n
S_0 = 1

For k = 0 to w - 1, if (bit k of x) is 1 then 
	               R_k = (S_k - y) mod n
                    else
                       R_k = S_k

                    S_(k+1) = (R_k)^2 mod n

		    Return R

w is the # of bits in x

Attack allows someone who knows 0..b-1 to find bit b
	R_b = (S_b - y) mod n
is computed if b is 1, skipped if b is 0.

Use timing info to guess b and verify by computing b - 1 iterations
of the loop.

T_1, T_2,..., T_n  -- sample timings
Known key bits b_1,..., b_i-1

Candidate b_i & compute i - 1 iterations of the algorithm
Subtract from T_j's 

	T_1,..., T_n
      - S_1,..., S_n

  --  if guess wrong, then thing go way off
  --  if not, then things are close

This is not feasible because of requirement that we have T_j's.