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 valuesin the examples to make sure you
understand them. For example, the factors of %%n=%%
are {}.
ElGamal
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.
Background Theory: Modulo, Subgroups, and Cycles
Before we can explore ElGamal, we need to understand some of the principles that are involved.
Modulo: What and Why?
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.
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: {
}.
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:
ElGamal: How Does it Work?
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}%%.
Meet in the Middle: Attacking Alice Inc.
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.
Mathematical Theory
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
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.
...
...
The Attack in Practice
With the theory out of the way, we can finally help Eve with her attack:
Running the 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 = %%
.
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