Julian Ceipek, Mar 10, 2014

**ElGamal** is an *asymmetric encryption algorithm* used
to securely exchange messages over long distances. Unfortunately, if the
message being encrypted is short enough, the algorithm is susceptible to
a **Meet in the Middle attack**. In this reactive document,
we'll look at how **ElGamal** works and how to break it in order
to steal a fraction of the credit card numbers sent to a hypothetical web
store called *Alice Inc.*

Since this is a reactive document, make sure to experiment with the adjustable values in the examples to make sure you understand them. For example, the factors of %%n=%% are {}.

The objective of encryption algorithms is to help people share secret or sensitive information with one another by using the information equivalent of physical keys. To make the discussion easier to follow, we say that Bob wants to send Alice a message without Eve ever being able to see it. With a *symmetric encryption algorithm*, the key used to encrypt a message is the same as the key used to decrypt it. This is analogous to Bob putting his message in a box, locking it, and sending it to Alice to unlock. A big problem with this approach is that Alice needs a copy of the key that Bob used. This is a chicken and egg problem: in order to securely exchange information with one another in this way, Alice and Bob must already have exchanged secret information. If Bob ever sends a key to Alice, Eve can easily intercept it and use it to read his messages. In theory, Bob could give Alice a key in person, but that doesn't work well in practice. Imagine having to drive to Amazon's offices in order to give them your credit card number before you could buy something online. Inconceivable!

The solution can be found with *asymmetric encryption algorithms*, which don't use the same key for encryption and decryption. Continuing our analogy of boxes and physical keys, Alice sends an unlocked lock to everyone who wants to send messages to her. Bob puts his message in a box, locks it with Alice's lock, and sends it back to Alice. Since Alice is the only one with the key to the lock, only she can read the message once it is in the locked box. **ElGamal** is an example of an information algorithm that works on this principle.

Before we can explore ElGamal, we need to understand some of the principles that are involved.

The %%modulus%% operator is an integral part of many encryption systems. For positive numbers, %%a \bmod b%% computes the remainder after dividing %%a%% by %%b%%, which ensures that the result is between %%0%% and %%b-1%%. Try it out:

%% \bmod %% %% = %%

The aspect of modulo that makes it so useful for encryption algorithms is that the result of %%a \bmod b%% doesn't reveal any information about %%a%%.

The result could just as easily be %% \bmod %% as %% \bmod %% . We say and are congruent modulo :

%% \equiv %% (%% \bmod %% )

Conveniently for cryptography purposes (encryption algorithms deal with very large numbers), the operator distributes over multiplication, addition, and subtraction.

Read more about modular arithmetic on Wikipedia.

A *cyclic group* is a mathematical group generated by one of the
elements in the group, %%g%%. As far as **ElGamal** is concerned,
we are only interested in two types of groups:

- The group of integers from %%1%% to %%p-1%% under multiplication %%\pmod{p}%% for some prime number %%p%%, which is known as %%\mathbb{Z}_p^*%%
- The subgroups of %%\mathbb{Z}_p^*%% of prime order

If %%p=%% , the factors of %%p-1=%% are {}.

The integer is the smallest generator %%g%% for the full group of order %% n = p-1 = %% containing all the elements from 1 to .

We can produce the sequence { }
by raising to successive powers (%%
\bmod %% ). This is a *finite* cyclic
group because it wraps around such that %%g^{n} = g^0 = 1%%, %%g^{n+1}
= g^1 = g%% and so on.

One of the cyclic subgroups of %%\mathbb{Z}_p^*%% of prime order is { }, generated by .

All the elements of a subgroup can also act as generators. For example, generates the subgroup in a different order: { }.

Read more about cyclic groups on Wikipedia.

Alice wants to enable people to send secret messages to her, so she creates
a **public key** %%(p,g,y)%% that she shares with the world
and a **private key** %%x%% that she never rveals to anyone
else. Bob wants to send Alice a secret message, so he uses Alice's public
key and a one-time **ephemeral key** %%k%% to produce the encrypted **ciphertext** %%(u,v)%%.
Here's how it works:

Choose a prime number %%p%%.

Choose an integer %%g%% in %%\mathbb{Z}_p^*%% that generates a cyclic subgroup of %%\mathbb{Z}_p^*%% of order %%n%%.

Choose a private key %%x%% such that %%1 \leq x \leq n-1%%.

Find %%y = g^x \pmod{p}%%.

Publish the public key %%(p,g,y)%%.

Look at Alice's public key %%(p,g,y)%%.

Choose a random integer %%k%% such that %%1 \leq k \leq n-1%%. Note that this means that Bob needs to know %%n%% in order to send a message.

Determine %%m%% such that %%1 \leq m \leq p-1%%. If the full message is too long, split up the message into chunks in order to encrypt them separately.

Compute %%u = g^k \pmod{p}%%.

Compute %%v = m y^k \pmod{p}%%.

Publish the ciphertext %%(u,v)%%.

Look at Bob's ciphertext %%(u,v)%%.

Decrypt the message with %%m = u^{-x} v \pmod{p}%%.

While Alice and Bob have been exchanging secrets, Eve has been feeling
left out. In order to make her happy, lets explore one of the ways that
Eve can read Bob's messages to Alice: the *Meet in the Middle Attack*.
The *Meet in the Middle Attack* is very different from the *Man in the Middle Attack* which involves Eve
pretending to be Alice and Bob, reading messages that Bob encrypts with
her key instead of Alice's and sending the messages to Alice after encrypting
them with Alice's key.

If a number of conditions are met and the message %%m%% Bob sends Alice
is short enough, Eve can recover %%m%% if she can intercept %%v%% as Bob
sends his ciphertext to Alice. Specifically, the *Meet in the Middle Attack* only
works if

- %%m%% consists of at most %%b%% bits, Eve knows %%b%%, and %%b%% is small. This is not unreasonable if Eve knows that Bob is purchasing something from Alice Inc. and wants to send the company a %%54%% bit credit card number, for example.
- %%m%% can be factored into two parts such that %%m = (m_1)(m_2)%%. Let %%m_1%% consist of %%b_1%% bits and %%m_2%% consist of %%b_2%% bits.
- Eve knows %%n%%. Since Bob's ephemeral key %%k%% has the property %%1 \leq k \leq n-1%%, he also needs to determine %%n%% somehow. If he can, Eve can, too.
- %%m%% happens not to be an element of the subgroup generated by %%g%%. This seems quite unlikely. However, according to the thesis Implementing several attacks on plain ElGamal encryption, %%n%%, the order %%n%% of the subgroup generated by %%g%%, is frequently chosen to be small for efficiency reasons.
- The order %%n%% of the subgroup generated by %%g%% has the property that %% n \leq (p-1)2^{-b} %%. Again, it is possible that %%n%% is small for efficiency reasons.

If all the assumptions are met, Eve can proceed as follows:

She knows that

$$y = g^x \pmod{p}$$

and that

%%v = my^k \pmod{p}%%.

Raising both sides to %%n%%,

%%v^n = (m^n)(y^{kn}) \pmod{p}%%.

This is useless as part of an attack if %%m%% is an element of the subgroup generated by %%g%% because then %%m^n = 1%% (since all the elements of a subgroup generate that subgroup, albeit in a different order, and wrap around to %%1%% once they are raised to the order of the subgroup).

If that is not the case, however, remember that %%g^n = g^0 = 1%% because the subgroup generated by %%g%% is cyclic, so

$$ y^{kn} = g^{xkn} = (g^{n})^{xk} = 1^{xk} = 1 $$

which simplifies %%(m^n)(y^{kn})%% substantially:

%%v^n = m^n \pmod{p}%%.

Using the assumption that %%m = (m_1)(m_2)%%,

$$v^n = (m_1^n)(m_2^n) \pmod{p}$$

%%(v^n)(m_2^{-n}) = m_1^n \pmod{p}%%.

To implement the *Meet in the Middle Attack*, Eve will need to use *dictionaries* —
the computer science ones.

A traditional dictionary is organized so that it is very easy to look up a word to find its definition. The reverse — looking for a definition in order to match it to a word — is really time consuming, especially as the amount of entries in the dictionary grows.

Word | Definition |
---|---|

Dictionary | What this is. |

Eve | The coolest hacker on the planet. |

Meet in the Middle | Eve's favorite attack. |

... | ... |

A computer science dictionary is very similar, and it can even be used
for the same purpose. The only difference is that the element to look up
is called a *key* and the element stored under that key is called
a *value*.

Key | Value |
---|---|

Dictionary | What this is. |

Eve | The coolest hacker on the planet. |

Meet in the Middle | Eve's favorite attack. |

... | ... |

With the theory out of the way, we can finally help Eve with her attack:

Given that the prime %%p%% has bits,

The public key might be:

( %%p = %% ,

%%g = %% ,

%%y = g^x \pmod{p} = %% )

where the order of the subgroup generated by %%g%% is %%n=%% ,

and the private key might be: %%x = %%

Assuming that %%b = %% bits and that %%b_1 = %% bits meaning that %%b_2=%% bits,

%%m = %%

If the ephemeral key %%k%% is , the ciphertext is:

( %%u = %% ,

%%v = %% )

- For all %%m_1=1,...,2^{b_1}%%, create a dictionary mapping from %%m_1^n \pmod{p} \to m_1%%
- For all %%m_2=1,...,2^{b_2}%%, compute %%v^n m_2^{-n} \pmod{p}%% and look it up in the dictionary.
- If we find a match in the dictionary, we have found a solution %%(m_1,m_2)%% to %%(v^n)(m_2^{-n}) = m_1^n \pmod{p}%% and %%m%% is probably equal to %%(m_1)(m_2)%%.

Since the dictionary only depends on the public key %%(p,g,y)%% and the length of the message %%b%%, we can use it again. Notably, it doesn't depend on the ephemeral key %%k%% in any way.

Using the *Meet in the Middle Attack*, Eve guesses that %%m = %%
.

- Implementing several attacks on plain ElGamal encryption
- A Quick Tutorial on Pollard's Rho Algorithm
- Generate cyclic group of prime order and one of its generator
- CS 6260: Some number theory
- Wikipedia: Multiplicative order
- Wikipedia: Cyclic group
- Wikipedia: Group (mathematics)
- Wikipedia: Multiplicative group of integers modulo n
- Wikipedia: Pollard's rho algorithm