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 by A.

Blue: Alice would have said ■ azure but it’s not really the same color and, more importantly, it doesn’t start with B.

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:

    Color(float r, float g, float b, float w = 1.0)
    : r(r), g(g), b(b), w(w)
    { }

    Color(std::string const & hex)
    {
        unsigned int r, g, b ;
        sscanf(hex.c_str(), "#%02x%02x%02x", &r, &g, &b) ;

        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>
Stream & operator<<(Stream & stream, Color const & c)
{
    char buf[8] ;
    snprintf(buf, sizeof(buf), "#%02x%02x%02x",
        (unsigned int) (256.0 * c.r / c.w),
        (unsigned int) (256.0 * c.g / c.w),
        (unsigned int) (256.0 * c.b / c.w)
    ) ;
        
    stream << buf;
    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.

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

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

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):

Color operator-(Color const & rhs)
{
    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 getCommonSecret(
    Color const & base,
    Color const & pubA,
    Color const & pubB
    )
{
    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 log(
    Color const & base,
    Color const & pub,
    )
{
    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.