# Diffie-Hellman with colors

**Spoiler:** *To explain the Diffie-Hellman key
exchange protocol, many articles and videos use a metaphor with colors
that should be mixed. I propose here to push this comparison to the end…
what if we really used it? There is a catch because after mixing colors,
even if it is difficult to do in real life, the computer can quite
easily find the original colors.*

When trying to establish a shared secret between two correspondents, the Diffie-Hellman Key Exchange Protocol is a must. It is “simple to implement” and secures communications sessions by ensuring forward secrecy.

Like all modern cryptography, the definition of this protocol uses mathematical theories. In our case, the groups, the notion of generator, exponentiation and calculation of discrete logarithm. When you understand these concepts, the protocol is relatively easy to understand.

To facilitate its understanding, most authors use a metaphor where the participants exchange paint colors. Without the math layer, the protocol is even easier to understand.

So let’s see how it works with paint and how far it works…

# The color metaphor

To communicate, Alice and Bob will therefore have to establish a shared secret and, as you can imagine, it will be a color. This particular shade, let’s call it ■ taupe for now, will only be known to them.

Taupe grey :as everyone knows, by dint of mixing colors, you always get a kind of very ugly and nondescript ■ brown that any child calls ■ poo but which interior designers decided to call■ taupe.

Alice and Bob start by using a common first paint. Since everything
is done publicly, anyone can see that color, *i.e.* Eve who
wishes she could know their secrets. Let’s take some ■ glaucous (also called *creepy* but
I need a name beginning with *g* in French and English).

Glaucous:Sort of ■ green a little ■ greyish pulling towards the ■ teal. Nobody really agrees on the exact shade of color. We can assume that, for safety, Alice sent a sample to Bob.

Alice and Bob will now each choose another secret color. After much hesitation, Alice settled on ■ amaranth. Bob already chose ■ blue a long time ago.

Amaranth:Shade of ■ purple that evokes the flower of amaranth. Bob calls it ■ pink or ■ burgundy in his heyday but we needed a color starting byA.

Blue:Alice would have said■ azurebut it’s not really the same color and, more importantly, it doesn’t start withB.

Each on their side, they will mix, in equal volumes, a little of
their color with the color in common and send each other half of their
result. This color, sent publicly, is their *public key*. Alice
sends some sort of ■ russett and Bob
returns a shade of ■ Boston Blue.

They will then mix the received color with their secret color to obtain the same mixture of the three colors in equal proportions. Here, we get a ■ kashmir blue.

Kashmir Blue:sort of■ Steel Blue. We feel the kinship with ■ taupe gray but as Bob would say,all that seems blue.

Security is based on the fact that it is difficult for Eve to find
the exact shade of *taupe grey* by having observed only the
common color and the two intermediate mixtures. This is called an
*“Attack on Diffie Hellman”*. To achieve this, Eve would have to
be able to remove a portion of the common color (taupe) color from the
mix.

Metaphorically, *“the attack on the discrete logarithm”* would
be to find the private colors from the public colors. Intuitively, we
feel that it is about the same difficulty.

And as everyone knows: once you start mixing brushes, you never find the original colors.

# The real metaphor

Among the possible color modeling we
have chosen the triplet of primary colors
$(r, g, b)$
to which we add a fourth member for the quantity . The following code is
an example with `C++`

implementation.

```
class Color
{
public:
float r ;
float g ;
float b ;
float w ;
public:
(float r, float g, float b, float w = 1.0)
Color: r(r), g(g), b(b), w(w)
{ }
(std::string const & hex)
Color{
unsigned int r, g, b ;
(hex.c_str(), "#%02x%02x%02x", &r, &g, &b) ;
sscanf
this->r = r / 256.0 ;
this->g = g / 256.0 ;
this->b = b / 256.0 ;
this->w = 1.0 ;
}
} ;
```

The triplet
$(r, g, b)$
can be assimilated to a *quantity of pigments* in the sample, to
know the shade, it is therefore necessary to *canonize* these
values by dividing by the quantity; principle similar to homogeneous
coordinates. You can use this operation to write the color to an
output stream:

```
template <typename Stream>
& operator<<(Stream & stream, Color const & c)
Stream {
char buf[8] ;
(buf, sizeof(buf), "#%02x%02x%02x",
snprintf(unsigned int) (256.0 * c.r / c.w),
(unsigned int) (256.0 * c.g / c.w),
(unsigned int) (256.0 * c.b / c.w)
) ;
<< buf;
stream return stream ;
}
```

With this convention, computation of mixtures are much simpler, adding two colors is simply adding the pigments and the quantities. You can also define an operator to multiply a color by a coefficient.

```
operator+(Color const & lhs, Color const & rhs)
Color {
return Color(
.r + rhs.r,
lhs.g + rhs.g,
lhs.b + rhs.b,
lhs.w + rhs.w
lhs) ;
}
operator*(float f, Color const & rhs)
Color {
return Color(
* rhs.r,
f * rhs.g,
f * rhs.b,
f * rhs.w
f ) ;
}
```

The set of possible quadruplets forms a group in $(R^4, +)$. Our modeling based on floating-point numbers is a subset which, apart from a few measurement inaccuracies, would also form a group.

On the other hand, the set of colors that have a physical and real meaning forms a Quasigroup. As for values to describe a color, all numbers must be positive and no pigment can be greater than the quantity.

In a quasigroup, this mixing operation therefore loses the notion of an inverse: no color can cancel out another. The key exchange protocol is then perfectly safe since it is impossible for Eve to find the original colors.

But just because Alice and Bob have a convention (staying in the quasigroup world) doesn’t mean Eve is bound to follow it.

For her attack, Eve can completely consider *irrational*
colors (negative pigments or pigments greater than the weight) and thus
make her computations in
$(R^4, +)$,
where inverting a color is possible (and even very simple to do):

```
operator-(Color const & rhs)
Color {
return -1.0 * rhs ;
}
```

Eve can therefore very easily find the common color of Alice and Bob. By mixing the public colors, she obtains a mixture consisting of one part of Alice’s secret color, one part of Bob’s and two parts of the initial color. By removing a part of public color, she will get an equal mix of all three colors.

```
(
Color getCommonSecretconst & base,
Color const & pubA,
Color const & pubB
Color )
{
return pubA + pubB - base ;
}
```

This is a direct attack on the *Diffie-Hellman problem*. Eve
computes the shared secret directly from the public information,
bypassing the secret keys.

The computation of these secret keys, *ie* the metaphorical
equivalent of the *discrete logarithm* is also very easy to
perform. Here is an implementation:

```
(
Color logconst & base,
Color const & pub,
Color )
{
return pub - base ;
}
```

It could hardly be simpler as an attack.

# And after ?

This metaphor is well suited to illustrate the idea that, if we have an operation that is difficult to reverse, such as mixing paint buckets, we can define a protocol to establish a shared secret. Our experience has taught us that you cannot physically undo color mixing, so we intuitively understand and accept the security of the protocol.

But just because something is *physically impossible* doesn’t
mean you can’t model it, build a mathematical model and, *in
fine*, make useful calculations on it.

Complex numbers are an example. We all know that the area of a figure cannot be negative! But we can still imagine a side length $i$ whose area of the square is -1. We can then use it to build a coherent set and discover the most beautiful formula and draw the most beautiful set.

And this brings us to a deeper philosophical principle, in computer
security but not only, doubt.
Just because a protocol or algorithm *seems intuitively secure to
us* doesn’t necessarily mean it is:

If we implemented the algorithm with colors, we would think of a perfectly safe algorithm while it would be easy to break. Fortunately, it is implemented instead with modular exponentiation of integers and more recently with elliptic curves, both of which are way much safer than paint buckets.