MATH 470 Lecture 19

« previous | Thursday, March 28, 2013 | next »

Tests will be graded by tomorrow, and are viewable during office hours on Monday 11:00 – 12:30

From Yesterday

The secret was 23:

Three pairs for group were:

• (12,96)
• (38,25)
• (2,17)

Randomness and Collisions: The Birthday Paradox

What are the chances that among 25 people, there exist at least 2 people with the same birthday?

Very likely: $1-Pr[\text{no common birthdays}]$, and the probability that there are no common birthdays is

$1\cdot \frac{364}{365}\cdot \frac{363}{365}\dots =\prod _{j=1}^{24}(1-\frac{j}{365})$

With a little work, we can get an estimate:

$\prod _{j=1}^{24}(1-\frac{j}{365})\ge 1-{\mathrm{e}}^{-\frac{25(25-1)}{2(365)}}$

Similarly, when picking $r$ numbered balls (with replacement) out of an urn with $n$, the probability of getting a collision is at least

$1-{\mathrm{e}}^{-\frac{r(r-1)}{2n}}$

Back to Signatures: Priority

This is an example of "Blind" Signatures

Suppose Pfizer and Roche are developing a cure for cancer. They are entering trials with patients, but want to later claim priority.

They want to prevent espionage by the other company.

If they want the CDC to believe their claim of priority, all parties can do the following:

Reveal that you know something without telling anyone what it is.

• CDC generates 2 RSA instances: $(p_1,q_1,n_1,e_1,d_1)$ and $(p_1,q_1,n_1,e_1,d_1)$.
• CDC sends set 1 $(n_1,e_1)$ to Pfizer and set 2 $(n_2,e_2)$ to Roche
• Pfizer picks a random $k_1\in {(\mathbb{\mathbb{Z}}/n_1\mathbb{\mathbb{Z}})}^{*}$ and sends $t_1=k_1^{e_1}{m}_1(\mathrm{mod}{n}_1)$ to the CDC.
• The CDC signs $t_1$ by computing $s_1=t_1^{d_1}(\mathrm{mod}{n}_1)$ and sends it back to Pfizer
• Pfizer keeps $s_1/k_1$
• Roche does the same with subscript 2

Each message $m_i$ is the formula for the cancer drugs.

Assuming these dialogues happened today (28 Mar. 2013), when trials are done, Pfizer (or Roche) can say: "I was first!" and prove it:

Proof. Pfizer observes

$\frac{s_1}{k_1}=\frac{t_1^{d_1}}{k_1}=\frac{{\left(k_1^{e_1}{m}_1\right)}^{d_1}}{k_1}=m_1^{d_1}$

CRC evaluates ${\left(m_1{d}_1\right)}^{e_1}=m_1$

Now in order for this to work, the CDC must be honest

Hash Functions

For digital signatures to be practical, we need to sign digests of messages instead of messages because RSA and El Gamal run in cubic time, not linear time (i.e. slow).

How do we get a digest?

Simple idea: use first few hundred bits

However, this can lead to collisions if two messages start with the same thing.

Mathematically, we want a function

$H:{\{0,1\}}^N\to {\{0,1\}}^n$

(maps bit strings of length $N$ to bit strings of length $n$)

such that

1. $H$ can be computed relatively quickly ($On)$)
2. $H$ is pre-image resistant, i.e. given $y$, finding $m^{\prime }$ with $H(m^{\prime })=y$ is very hard.
3. $H$ is strongly collision-free: it is very hard to find $m_1$ and $m_2$ with $H(m_1)=H(m_2)$

Note: For $N>n$ with $H$ having no collisions, this is impossible!

Note: requirements 2 and 3 are for cryptographic hash functions. For computing programming hashes for use in hash tables, requirements 2 and 3 may be discarded

Example Hash Functions

1. $H(m)=m(\mathrm{mod}n)$
   • (1 passes) easy to compute
   • (2 fails) given $y$, it's easy to find $m^{\prime }$ with $H(m^{\prime })=y$, namely $m^{\prime }=y$.
   • (3 fails) take $H(m_1)=H(m_1+n)$
2. $H(x)={\alpha }^x(\mathrm{mod}p)$
   • (1 passes) easy
   • (2 passes) discrete log is hard
   • (3 passes) only if $\alpha$ is a generator for $p$
   • BUT range is still considerably big: $H(13081)\equiv 5^{13081}\equiv 103103(\mathrm{mod}104729)$

Digression: Transmitting Keys via RSA

Suppose you want to transmit a 56-bit (< 10¹⁷) DES key using RSA with $n$ having 200 bits (> 10⁶⁰).

You would like your adversary to be forced to search through all possibilities if she tries to read your message.

However, using RSA naïvely enables Eve to find the 56-bit key after searching just 2E9 possibilities!

1. Compute $y^{-e}(\mathrm{mod}n)$ for $y\in \{1,\dots ,10^9\}$
2. Upon seeing your message $c=m^e$, she computes $c{x}^e$ for $x\in \{1,\dots ,10^9\}$
3. Now Eve looks for collisions $y^{-e}=cx$ by checking $(\genfrac{}{}{0ex}{}{10^9}{2})\le 10^{18}$ possibilities in total, BUT
4. Thanks to the birthday paradox, Eve will find a collision with probability 2E9 checks!

The collisions work because $y^{-e}=c{x}^e⟺c=(xy{)}^{-e}=((xy{)}^{-1}{)}^e$, and so $m=(xy{)}^{-1}$

Eve just found an encrypted key with relatively little work

What to do!?

Padding

Concatenate 72 random bits to the front and back of the key.

This still is not quite secure: Eve could figure out how the padding scheme works

OAEP-Padding Scheme

1994: Bellaire and Rogaway

Based on hash functions, but performs the inverse $\{0,1{\}}^n\to \{0,1{\}}^N$ mapping.