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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le r \le n-1} relatively prime to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} (i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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$: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g}

1. Each party secretly picks a random number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_a} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_b}
2. each party computes public key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_a = g^{S_a}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_b = g^{S_b}} and shares with each other
3. Each party raises key to the (random number) power to get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_1} , and Trudy/Bob</math> have different key Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_a} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_b} for each other to retrieve and generate keys at any time.
3. Each key generation must use same Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} , and random number.

Picking Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} :

• Advantageous to change periodically.
• Choose large, difficult to factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p}
• Choose non quadratic residue Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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