[messaging] Messaging Digest, Vol 357, Issue 1

Sat Dec 5 00:36:52 PST 2015

(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 <mpdehnel at gmail.com>
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, <messaging-request at moderncrypto.org>
> wrote:
>
>> Send Messaging mailing list submissions to
>>         messaging at moderncrypto.org
>>
>> 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
>>         messaging-request at moderncrypto.org
>>
>> You can reach the person managing the list at
>>         messaging-owner at moderncrypto.org
>>
>> 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" <for-gmane at mutluit.com>
>> To: messaging at moderncrypto.org
>> Subject: [messaging] Can a pre-shared public key prevent MITM-attacks?
>> Message-ID: <n3qs9g$9p4$1 at ger.gmane.org>
>> 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
>> Messaging at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/messaging
>>
>>
>> ------------------------------
>>
>> End of Messaging Digest, Vol 357, Issue 1
>> *****************************************
>>
>
>
>
> --
> Martin
>

-- 
Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20151205/d1222c00/attachment.html>