5

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?

2
  • Aside: I've been self-conscious lately after reading some strong opinions on HN that no respectable programmer doesn't know how SSH works and how to use it. I only have ~4 years of industry experience working on windows-based 'helper' tools and simulation software and it never really came up. I have a undergrad with a couple security courses that touched on this, but I'm sure the particulars didn't make or break the exams. Am I really so incompetent without experience in this area?
    – Alain
    May 22, 2012 at 16:34
  • Well, I wouldn't say you need to know how it works at the protocol layer. The Hacker News discussion is a complaint that an account there requires a GitHub account, and that requires you to generate a ssh certificate. Many developers will have done this before, since it is a convenient way to get secure remote access to a UNIX system, but you can be a good Windows dev and never have this come up. Never fear though, it's easy. E.G. see jaybyjayfresh.com/2009/02/04/… May 23, 2012 at 8:50

3 Answers 3

6

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.

3
  • 3
    I think I understand now, thanks. This method on its own only protects against passive observers of the exchange, not active interceptors.
    – Alain
    May 22, 2012 at 17:26
  • Awesome answer, I love the analogy! +1
    – Cyril N.
    May 22, 2012 at 20:50
  • Not mine, cx42net, alas: it's from the quoted Wikipedia article. May 23, 2012 at 8:43
5

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.

1

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 !

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .