(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...)
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. You don't actually need to encrypt anything symmetrically or asymmetrically until you've done the key-establishment phase. 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... https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange for more info) How it works: 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) 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. 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. 4: Alice computes (g^y)^x, which is g^(y*x) 5: Bob computes (g^x)^y, which is g^(x*y). 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. You're now thinking: well, if the adversary saw all that stuff get transmitted, can't he calculate it too? Enter the Discrete Logarithm Problem ( https://en.wikipedia.org/wiki/Discrete_logarithm). In a nutshell, this says "if you know g^x and g, it's still _really_ hard to work out what x is". 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. The attacker can calculate (g^x)*(g^y), but this is equal to g^(x+y), not g^(x*y) as required: wrong key. 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. So we've agreed that public-keys are pre-shared: that was the whole reason for your question. 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. Now they can encrypt messages symmetrically (e.g. using AES) to communicate. 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. 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. You can do key-exchange with other, non-DH-based protocols such as Needham-Schroeder-Lowe, but this perhaps isn't its intended purpose. How NSL (public key variant) works: 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) 1: Alice generates a fresh random number (a nonce) 'x'. 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)) 3: Bob decrypts this with his private key. 4: Bob generates a fresh random number 'y'. 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)) 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. 7: Finally, Alice then encrypts 'y' with Bob's public key, to prove she can decrypt it: Enc(pk(Bob),y). 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! We've now established that Alice and Bob are genuinely talking to each other, and it's not the adversary. 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. 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. http://www.cs.cornell.edu/~shmat/courses/cs6431/lowe.pdf 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. Finally, as Natanael says, perhaps the simplest way is for Alice to encrypt and sign a message: 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. 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. One disadvantage of this is that Alice chooses the key entirely by herself: the key isn't the result of input from both parties. Hope this makes sense to you, but this is perhaps not directly the intended topic of discussion for this mailing list :-) Martin Natanael wrote on 12/05/2015 12:50 AM: > >* Den 4 dec 2015 23:49 skrev "U.Mutlu" <for-gmane at mutluit.com > <https://moderncrypto.org/mailman/listinfo/messaging>>: *>> > >>* Martin Dehnel-Wild wrote on 12/04/2015 09:58 PM: *>>> > >>>* 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') *>> > >> > >>* Yes, indeed that's what I'm meaning by attacks. *>>* But I have a > hard time to see how the use of a public key can help here, *>>* because > the public key is by definition known to everybody, so also to *>>* the > MITM, but then he can easily replace the encrypted message by his *>>* > own message encrypted with the same public key --> bingo! *>> > >>* Or, where is my lack of understanding here? *>> > >>* Thanks for the info and links below, I'm going to study them. *> > >* This is where you tell them to reply encrypted to your public key, > inside *>* the encrypted message, and sign it. So they got a message from > somebody *>* else? If they know you already, they'll see the signature > failed. If they *>* don't, you'll be the one who notices the total lack > of response, and you'll *>* try again until you get one (which is > signed). * This introduces signing, but in the wikipedia article I had > quoted > in the OP signing is not mentioned: > https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Public_key If I > might summarize: > Using DH protocol and adding to it the use of say RSA certificates > (for signing, enc, dec) will make the DH session MITM-secure, > for example for subsequently sending a new password (for something else) > 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 > new/initial password (for a different purpose), but without any human > interaction as the participants are devices or apps but which already > have their own certificates. On Fri, Dec 4, 2015 at 8:58 PM, Martin Dehnel-Wild <[email protected]> wrote: > 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') > > See e.g. MQV (https://en.wikipedia.org/wiki/MQV), HMQV, NAXOS for > examples of modern(-ish) protocols that are not vulnerable to MITM attacks. > Even Needham-Schroeder-Lowe protocol ( > https://en.wikipedia.org/wiki/Needham%E2%80%93Schroeder_protocol#Fixing_the_man-in-the-middle_attack, > http://www.cs.cornell.edu/~shmat/courses/cs6431/lowe.pdf, 1996, not > DH-based) is not vulnerable to MITM when you have pre-shared public keys. > > 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 > https://github.com/tamarin-prover/tamarin-prover/ and then look in > examples/ake/dh/ and examples/classic/ for each of the above mentioned > protocols. > > 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. > > Martin > > On Fri, Dec 4, 2015 at 8:00 PM, <[email protected]> > wrote: > >> Send Messaging mailing list submissions to >> [email protected] >> >> To subscribe or unsubscribe via the World Wide Web, visit >> https://moderncrypto.org/mailman/listinfo/messaging >> or, via email, send a message with subject or body 'help' to >> [email protected] >> >> You can reach the person managing the list at >> [email protected] >> >> When replying, please edit your Subject line so it is more specific >> than "Re: Contents of Messaging digest..." >> >> >> Today's Topics: >> >> 1. Can a pre-shared public key prevent MITM-attacks? (U.Mutlu) >> >> >> ---------------------------------------------------------------------- >> >> Message: 1 >> Date: Fri, 4 Dec 2015 03:03:27 +0100 >> From: "U.Mutlu" <[email protected]> >> To: [email protected] >> Subject: [messaging] Can a pre-shared public key prevent MITM-attacks? >> Message-ID: <[email protected]> >> Content-Type: text/plain; charset=UTF-8; format=flowed >> >> On the following wiki page it's boldly claimed that "A pre-shared public >> key >> also prevents man-in-the-middle attacks" >> https://en.wikipedia.org/wiki/Diffie?Hellman_key_exchange#Public_key : >> "It is also possible to use Diffie?Hellman as part of a public key >> infrastructure, allowing Bob to encrypt a message so that only Alice will >> be >> able to decrypt it, with no prior communication between them other than >> Bob >> having trusted knowledge of Alice's public key. Alice's public key is >> (g^a mod p, g, p). To send her a message, Bob chooses a random b and then >> sends Alice g^b mod p (un-encrypted) together with the message encrypted >> with symmetric key (g^a)^b mod p. Only Alice can determine the symmetric >> key >> and hence decrypt the message because only she has a (the private key). >> A pre-shared public key also prevents man-in-the-middle attacks." >> >> I have my doubts. >> What do others think of 'MITM prevention by using public key encryption'? >> >> >> >> >> >> ------------------------------ >> >> Subject: Digest Footer >> >> _______________________________________________ >> Messaging mailing list >> [email protected] >> https://moderncrypto.org/mailman/listinfo/messaging >> >> >> ------------------------------ >> >> End of Messaging Digest, Vol 357, Issue 1 >> ***************************************** >> > > > > -- > Martin > -- Martin
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
