<div dir="ltr"><div style="font-size:12.8px">(Sorry for the mucked up subject line; I get digests. I tried sending this as a new email last night with the subject of the discussion thread, but it hasn't come through...)</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">So the basic point of a key-exchange protocol is to allow two actors to agree upon a common, shared key, that they can then use to communicate using symmetric crypto.</div><div style="font-size:12.8px">You don't actually need to encrypt anything symmetrically or asymmetrically until you've done the key-establishment phase.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Diffie-Hellman is the classic example of this: (This is a v simplified description for explanatory purposes; some details have been deliberately left out, so don't jump on me for that...<a href="https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange" target="_blank">https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange</a> for more info)</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">How it works:</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div>1: Alice and Bob agree on a public (generator) number g. Everyone including the attacker knows and agrees upon this number. (details about how to choose g deliberately omitted: don't worry about it for now)</div><div>2: Alice picks a (big) random integer x, and sends g^x to Bob, that is "g to the power of x". We say that g^x is Alice's public key, and x is Alice's private key.</div><div>3: Bob picks a (big) random integer y, and sends g^y to Alice. Similarly, g^y is Bob's public key, and y is Bob's private key.</div><div>4: Alice computes (g^y)^x, which is g^(y*x)</div><div>5: Bob computes (g^x)^y, which is g^(x*y). </div><div>Due to maths, the final number that Alice and Bob independently calculate are the same number: this number, g^(x*y) is then their agreed, shared key, and they use this as the key for symmetric encryption.</div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">You're now thinking: well, if the adversary saw all that stuff get transmitted, can't he calculate it too?</div><div style="font-size:12.8px">Enter the Discrete Logarithm Problem (<a href="https://en.wikipedia.org/wiki/Discrete_logarithm" target="_blank">https://en.wikipedia.org/wiki/Discrete_logarithm</a>). In a nutshell, this says "if you know g^x and g, it's still _really_ hard to work out what x is". </div><div style="font-size:12.8px">So the attacker knows what g^x and g^y are, but can't calculate the final agreed key g^(x*y) without also knowing either of x or y on their own (not in the form g^x or g^y), and these were never transmitted at any point.</div><div style="font-size:12.8px">The attacker can calculate (g^x)*(g^y), but this is equal to g^(x+y), not g^(x*y) as required: wrong key.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">So at no point has the final agreed key been transmitted over the network (in plaintext or even encrypted form), and Alice and Bob now have a key they agree upon that the adversary doesn't know.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">So we've agreed that public-keys are pre-shared: that was the whole reason for your question. </div><div style="font-size:12.8px">If Alice knows Bob's genuine public key (g^y) and Bob knows Alice's genuine public key (g^x), the adversary can't prevent Alice and Bob from calculating g^(x*y) (because they already have all the information they need, i.e. their partner's public key and their own private key), and the adversary can't learn anything useful about the final derived key.</div><div style="font-size:12.8px">Now they can encrypt messages symmetrically (e.g. using AES) to communicate.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">You'll note that at no point did either one of them encrypt anything using their individual public key: these were just used for the key-agreement stage.</div><div style="font-size:12.8px">More modern protocols like HMQV and NAXOS give extra guarantees, such as if they attacker compromises your long term private key, the adversary still can't learn the key.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">You can do key-exchange with other, non-DH-based protocols such as Needham-Schroeder-Lowe, but this perhaps isn't its intended purpose.</div><div style="font-size:12.8px">How NSL (public key variant) works: </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">0: Alice and Bob know each other's public keys (these could be RSA public keys as we're going to do some encryption with them)</div><div style="font-size:12.8px">1: Alice generates a fresh random number (a nonce) 'x'. </div><div style="font-size:12.8px">2: She encrypts x and her name (i.e. x,Alice) with Bob's public key pk(Bob), and sends it to Bob: Enc(pk(Bob),(x,Alice))</div><div style="font-size:12.8px">3: Bob decrypts this with his private key.</div><div style="font-size:12.8px">4: Bob generates a fresh random number 'y'.</div><div style="font-size:12.8px">5: He takes the number x sent to him by Alice, and his random number y, and his name 'Bob' and encrypts that with Alice's public key: Enc(pk(Alice),(x,y,Bob))</div><div style="font-size:12.8px">6: Alice decrypts this, and checks that the 'x' Bob transmitted is the same as the 'x' she sent (obviously the attacker can't do this, as he doesn't know Bob's private key). If it's not the same, she stops.</div><div style="font-size:12.8px">7: Finally, Alice then encrypts 'y' with Bob's public key, to prove she can decrypt it: Enc(pk(Bob),y).</div><div style="font-size:12.8px">8: Bob decrypts this with his private key, and checks that the y he received is the same as the y he sent. If it is the same: congrats! </div><div style="font-size:12.8px">We've now established that Alice and Bob are genuinely talking to each other, and it's not the adversary.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">They can now do something like XORing x and y together to use as a symmetric key, but as I say, NSL isn't really a key-exchange protocol, its purpose is to authenticate Alice and Bob to each other; however it is an example of how by using public key encryption and pre-shared public keys you can establish a shared key that the adversary doesn't know.</div><div style="font-size:12.8px">The reason for including the names in the encrypted messages is to prevent a subtle man-in-the-middle attack that went unnoticed for many years: read Gavin's paper on it for more information.<a href="http://www.cs.cornell.edu/~shmat/courses/cs6431/lowe.pdf" target="_blank">http://www.cs.cornell.edu/~shmat/courses/cs6431/lowe.pdf</a></div><div style="font-size:12.8px">The Tamarin prover (that I talked about before) is a way of being certain that these types of subtle MITM attacks aren't possible for the verified protocols.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Finally, as Natanael says, perhaps the simplest way is for Alice to encrypt and sign a message: </div><div style="font-size:12.8px">Alice encrypts the desired key (that she chooses randomly), x with Bob's public key, then signs the resulting cipher-text with her private signing key.</div><div style="font-size:12.8px">Bob verifies the signature, and then, if and only if this verifies correctly (and therefore must genuinely have been sent by Alice), does he decrypt the cipher-text to learn the new key. </div><div style="font-size:12.8px">One disadvantage of this is that Alice chooses the key entirely by herself: the key isn't the result of input from both parties.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Hope this makes sense to you, but this is perhaps not directly the intended topic of discussion for this mailing list :-)</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Martin</div><div><br></div><div><br></div><div><br></div><div><blockquote style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex" class="gmail_quote">Natanael wrote on 12/05/2015 12:50 AM:<br>><i> Den 4 dec 2015 23:49 skrev "U.Mutlu" <<a href="https://moderncrypto.org/mailman/listinfo/messaging">for-gmane at mutluit.com</a>>:
</i>>><br>>><i> Martin Dehnel-Wild wrote on 12/04/2015 09:58 PM:
</i>>>><br>>>><i> Yes. Having a pre-shared public key definitely allows you to prevent MITM
</i>>>><i> attacks. (Where by 'attack' I assume  you mean 'the adversary learns the
</i>>>><i> agreed key')
</i>>><br>>><br>>><i> Yes, indeed that's what I'm meaning by attacks.
</i>>><i> But I have a hard time to see how the use of a public key can help here,
</i>>><i> because the public key is by definition known to everybody, so also to
</i>>><i> the MITM, but then he can easily replace the encrypted message by his
</i>>><i> own message encrypted with the same public key --> bingo!
</i>>><br>>><i> Or, where is my lack of understanding here?
</i>>><br>>><i> Thanks for the info and links below, I'm going to study them.
</i>><br>><i> This is where you tell them to reply encrypted to your public key, inside
</i>><i> the encrypted message, and sign it. So they got a message from somebody
</i>><i> else? If they know you already, they'll see the signature failed. If they
</i>><i> don't, you'll be the one who notices the total lack of response, and you'll
</i>><i> try again until you get one (which is signed).
</i>
This introduces signing, but in the wikipedia article I had quoted<br>in the OP signing is not mentioned:<br><a href="https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange#Public_key">https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Public_key</a>
If I might summarize:<br>  Using DH protocol and adding to it the use of say RSA certificates<br>  (for signing, enc, dec) will make the DH session MITM-secure,<br>  for example for subsequently sending a new password (for something else)<br>  over to the other side.
Is that conclusion right?
That would be what I need, ie. a safe way to send the other side a<br>new/initial password (for a different purpose), but without any human<br>interaction as the participants are devices or apps but which already<br>have their own certificates.</blockquote></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 4, 2015 at 8:58 PM, Martin Dehnel-Wild <span dir="ltr"><<a href="mailto:mpdehnel@gmail.com" target="_blank">mpdehnel@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Yes. Having a pre-shared public key definitely allows you to prevent MITM attacks. (Where by 'attack' I assume  you mean 'the adversary learns the agreed key')<div><br></div><div>See e.g. MQV (<a href="https://en.wikipedia.org/wiki/MQV" target="_blank">https://en.wikipedia.org/wiki/MQV</a>), HMQV, NAXOS for examples of modern(-ish) protocols that are not vulnerable to MITM attacks.</div><div>Even Needham-Schroeder-Lowe protocol (<a href="https://en.wikipedia.org/wiki/Needham%E2%80%93Schroeder_protocol#Fixing_the_man-in-the-middle_attack" target="_blank">https://en.wikipedia.org/wiki/Needham%E2%80%93Schroeder_protocol#Fixing_the_man-in-the-middle_attack</a>, <a href="http://www.cs.cornell.edu/~shmat/courses/cs6431/lowe.pdf" target="_blank">http://www.cs.cornell.edu/~shmat/courses/cs6431/lowe.pdf</a>, 1996, not DH-based) is not vulnerable to MITM when you have pre-shared public keys.</div><div><br></div><div>If you'd like machine-based proofs of the fact that they're not vulnerable to MITM attacks, run them through the Tamarin-prover (a security protocol verification tool that supports both falsification and unbounded verification of security protocols): download <a href="https://github.com/tamarin-prover/tamarin-prover/" target="_blank">https://github.com/tamarin-prover/tamarin-prover/</a> and then look in examples/ake/dh/ and examples/classic/ for each of the above mentioned protocols.</div><div><br></div><div>This is just one way of demonstrating their invulnerability (in this case in the symbolic world), but you can also find proofs for (I believe) most of the above in the computational setting as well, which are generally stronger 'proofs', but mostly human constructed and verified.</div><div><br></div><div>Martin</div></div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Fri, Dec 4, 2015 at 8:00 PM,  <span dir="ltr"><<a href="mailto:messaging-request@moderncrypto.org" target="_blank">messaging-request@moderncrypto.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Send Messaging mailing list submissions to<br>
        <a href="mailto:messaging@moderncrypto.org" target="_blank">messaging@moderncrypto.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
        <a href="https://moderncrypto.org/mailman/listinfo/messaging" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
or, via email, send a message with subject or body 'help' to<br>
        <a href="mailto:messaging-request@moderncrypto.org" target="_blank">messaging-request@moderncrypto.org</a><br>
<br>
You can reach the person managing the list at<br>
        <a href="mailto:messaging-owner@moderncrypto.org" target="_blank">messaging-owner@moderncrypto.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of Messaging digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
   1. Can a pre-shared public key prevent MITM-attacks? (U.Mutlu)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Fri, 4 Dec 2015 03:03:27 +0100<br>
From: "U.Mutlu" <<a href="mailto:for-gmane@mutluit.com" target="_blank">for-gmane@mutluit.com</a>><br>
To: <a href="mailto:messaging@moderncrypto.org" target="_blank">messaging@moderncrypto.org</a><br>
Subject: [messaging] Can a pre-shared public key prevent MITM-attacks?<br>
Message-ID: <n3qs9g$9p4$<a href="mailto:1@ger.gmane.org" target="_blank">1@ger.gmane.org</a>><br>
Content-Type: text/plain; charset=UTF-8; format=flowed<br>
<br>
On the following wiki page it's boldly claimed that "A pre-shared public key<br>
also prevents man-in-the-middle attacks"<br>
<a href="https://en.wikipedia.org/wiki/Diffie?Hellman_key_exchange#Public_key" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Diffie?Hellman_key_exchange#Public_key</a> :<br>
   "It is also possible to use Diffie?Hellman as part of a public key<br>
infrastructure, allowing Bob to encrypt a message so that only Alice will be<br>
able to decrypt it, with no prior communication between them other than Bob<br>
having trusted knowledge of Alice's public key. Alice's public key is<br>
(g^a mod p, g, p). To send her a message, Bob chooses a random b and then<br>
sends Alice g^b mod p (un-encrypted) together with the message encrypted<br>
with symmetric key (g^a)^b mod p. Only Alice can determine the symmetric key<br>
and hence decrypt the message because only she has a (the private key).<br>
A pre-shared public key also prevents man-in-the-middle attacks."<br>
<br>
I have my doubts.<br>
What do others think of 'MITM prevention by using public key encryption'?<br>
<br>
<br>
<br>
<br>
<br>
------------------------------<br>
<br>
Subject: Digest Footer<br>
<br>
_______________________________________________<br>
Messaging mailing list<br>
<a href="mailto:Messaging@moderncrypto.org" target="_blank">Messaging@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/messaging" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
<br>
<br>
------------------------------<br>
<br>
End of Messaging Digest, Vol 357, Issue 1<br>
*****************************************<br>
</blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br><div>Martin <br></div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">Martin <br></div>
</div>