[messaging] Messaging Digest, Vol 357, Issue 1

[U.Mutlu]

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.