CSCE 465 Lecture 22

« previous | Thursday, April 11, 2013 | next »

RSA (cont'd)

Timing Attack (cont'd)

Attacker figures out key bit-by-bit by timing how long each step takes to calculate.

countermeasures:

• slow down computation (already very slow)
• add random delay (still already slow)
• blinding: multiply ciphertext by random number before performing decryption.

Blinding

1. compute random number $0\leq r\leq n-1$ relatively prime to $n$ (i.e. $\mathrm {gcd} (r,n)=1$)
2. comptue $c'=c\,r^{e}{\pmod {n}}$
3. compute $m'=(c')^{d}{\pmod {n}}$
4. compute $m=m'\,r^{-1}{\pmod {n}}$

$m\equiv {\frac {m'}{r}}\equiv {\frac {(c')^{d}}{r}}\equiv {\frac {(c\,r^{e})^{d}}{r}}\equiv {\frac {c^{d}\,r}{r}}\equiv c^{d}{\pmod {n}}$

Other application in Decryption as a service: multiply ciphertext $c$ by random number $r$ before sending it to decryption service. Divide by $r$ when decrypted "plaintext" is received.

Performance penalty of less than 10% in decryption speed.

Diffie-Hellman Key Exchange

Used for negotiating shared secret key using only public communication. First development of public key cryptography, but not to be used for encryption.

Note: Does not provide authentication of communicating parties

Requirements (can be publicly known):

• Large prime (512 bits): $p$
• Primitive root (generator) of $p$: $g$

1. Each party secretly picks a random number $S_{a}$ and $S_{b}$
2. each party computes public key $T_{a}=g^{S_{a}}$ and $T_{b}=g^{S_{b}}$ and shares with each other
3. Each party raises key to the (random number) power to get $K=g^{S_{a}\,S_{b}}$ as the secret key.

This is secure since computing the discrete logarithm is computationally infeasible.

Limitations

• timing attacks (expensive exponentiation)
• Only useful for key negotiation
• Not used for anything else

Man-In-The-Middle Attack

Trudy impersonates Alice to Bob and chooses own S_"a" for negotiations with Bob.

This attack works if all traffic between Alice and Bob is transferred through Trudy (Alice/Trudy have key $K_{1}$, and Trudy/Bob</math> have different key $K_{2}$)

Authentication Requires already-known secret

Phone-Book Mode: Authenticating D-H Messages

1. Alice and Bob each choose a semi-permanent secret number
2. publish $T_{a}$ and $T_{b}$ for each other to retrieve and generate keys at any time.
3. Each key generation must use same $p$, $g$, and random number.

Picking $g$ and $p$:

• Advantageous to change periodically.
• Choose large, difficult to factor $p$
• Choose non quadratic residue $g$

Public Key and Certification Authorities (CA)

• A CA is a trusted node that maintains public keys for all nodes (Each node maintains its own private key).
• They also make a lot of money.
• certificate = signed message vouching that particular name goes with particular key:
  • [Alice's public key is 876234]_carol
  • [Carol's public key is 676554]_ted 7amp; [Alice's public key is 876234]_carol
• Knowing Certification Authority's key validates the alleged public key

PKI = Public Key Infrastructure: supports use of public key cryptography

CA is one of most important components of PKI