Hello, thank you very much for the info, I see that a signing algo like RSA is indeed helpful in MITM-prevention. The problem for me to understand is: how to securely exchange the public keys if these are used in an ephemeral fashion, ie. on the fly generated to be used just in this one session. I have described the problem in detail in my reply to Justin King-Lacroix.
Martin Dehnel-Wild wrote on 12/05/2015 09:36 AM:
(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
I think it should be on-topic, because I intend to use the MITM-secure solution also in a messaging application like an IM or in secure mailing.
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
