In the Diffie-Hellman key exchange, how is the shared base key 'p' known and how are A and B, protected from Eve?

Question

I'm trying to wrap my head around Hellman, Diffie, and Merkle's key exchange design, but after reading the Wiki article about it, I can't figure out how the commonly known factor ('p', I think) comes to be?

In the initial laymen description, they first describe it with: "Note that the yellow paint is already agreed by Alice and Bob". Yet the original description of the exchange is: "The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key."

Where does the shared base 'paint' (which I understand to be a commonly known prime number) come from? Is it built into the algorithm itself? Presuming anyone could know it, why isn't that a problem in preventing man-in-the-middle attacks from hijacking both connections with their own key and providing a 'translation' service between two encryption keys based on the attacker's private key?

Answer 1

The trick is that Alice and Bob can share non-secret information freely; they can agree that yellow will be their base color and it doesn't help Eve at all if she finds this out.

When Eve intercepts the green paint Alice has sent to Bob, she knows it was made with yellow and some other color, but figuring out the other color is too hard to do even with this much information.

And yes, man-in-the-middle is a problem; man-in-the-middle is specifically an attack on the key exchange part of a communication. Diffie-Hellman doesn't help with that.

Answer 2

Where does the shared base 'paint' (which I understand to be a commonly known prime number) come from? Is it built into the algorithm itself?

Can be sent in plain-text

Presuming anyone could know it, why isn't that a problem in preventing man-in-the-middle attacks from hijacking both connections with their own key and providing a 'translation' service between two encryption keys based on the attacker's private key?

That's an authentication problem and not one solved by D-H key exchange. E.g., you need to combine D-H with a cryptographic chain-of-trust (e.g., from past communication, checking several trusted public key-server, or using certificate authority).

From wikipedia:

In the original description, the Diffie–Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack. A person in the middle may establish two distinct Diffie–Hellman key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing the attacker to decrypt (and read or store) then re-encrypt the messages passed between them. A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. Variants of Diffie-Hellman, such as STS, may be used instead to avoid these types of attacks.

Answer 3

Raw Diffie-Hellman is for allowing communication between two people who are in the same subway station, but on opposite sides of the tracks. They can see each other, they can shout things at each other, but everybody in the station can also see them and hear them. They know when what they hear is indeed what the other said; the messages they send to each other cannot be altered without their noticing it (the communication can be jammed, e.g. when a train passes or when an violin-wielding thug comes by, but that's the extent of the adversary's powers).

Under these conditions, secure communication is feasible, beginning with a Diffie-Hellman key exchange. One of the involved parties shouts the modulus p and generator g; or, equivalently, the definition of the elliptic curve they will use. They can rely on "well-known" group parameters, because it is no problem if the same group is used ever and again by everybody.

And there is an app for that !