Re: [Cfrg] Wack-A-Mole and PKEX 3.0 -> Re: Fwd: New Version Notification for draft-harkins-pkex-00.txt

[Dan Harkins <[e-mail]>]

On 9/13/16 12:57 PM, Andy Lutomirski wrote:
> On Tue, Sep 13, 2016 at 12:24 PM, Dan Harkins <[e-mail]> wrote:
>> On 9/13/16 9:51 AM, Andy Lutomirski wrote:
>>> On Tue, Sep 13, 2016 at 7:36 AM, Paul Lambert <[e-mail]> wrote:
>>>> With enough tries … PKEX 3.0 or PKEX n.0 could be deemed secure.
>>>> Including
>>>> the validated exchange of public keys in a PAKE exchange is a very
>>>> interesting mechanism. Usage constraints of such a protocol still may
>>>> make
>>>> it inappropriate for particular applications.
>>> Can we take a step back and ponder *why* a protocol that exchanges
>>> public keys and proves possession of the corresponding private keys is
>>> useful?
>>>
>>> Here's roughly what PKEX tries to achieve (I think):  Alice and Bob
>>> each know a password, and Alice and Bob are assumed to be the only
>>> parties that know that password.  Alice can run PKEX and, if the
>>> protocol succeeds, she knows that (1) a public key B, (2) that Bob
>>> claims that the holder of the private key b is Bob and (3) that Bob
>>> actually has the ability to perform private key operations using b.
>>> Bob learns the same things about Alice and her keys.  There are whole
>>> bunch of properties about offline attack that the protocol ought to
>>> have.
>>
>>    Yes, that's a good list and let me add that Alice also knows that
>> b is the private analog to the public key B. Also an important feature.
> What does that mean?  Alice doesn't know b.  She knows that there
> exists a number b such that B = b*G, but that's not interesting.  She
> does not, and cannot, know that Bob actually knows b unless Bob tells
> it to her (which would be a terrible idea) because b might reside on
> an HSM.

   I didn't say she knows b. She knows that Bob knows b. That knowledge
is what PKEX provides.

>>    If there are any other "properties about offline attacks that the protocol
>> ought to have" that are not already listed in PKEX I'd like to hear about
>> them. Thank you in advance.
> A strong concept of what various parties (Alice, Bob, and any
> potential MITM) can and cannot do to attack a weak password, online
> and offline, even if Alice and Bob go and leak the entire output of
> the protocol along with a and b afterwards.  The literature on PAKEs
> should contain something usable here.

   Perhaps I was too soon in offering thanks. In any event, the offer 
stands.
If you can think of any properties that PKEX ought to have that it doesn't
I'd like to hear of them.

>>> For the purpose of pairing two devices that intend to communicate
>>> using public-key crypto, property (1) is obviously critical.  In my
>>> mind, property (2) should be sufficient.  I'm asking why property (3)
>>> is useful.
>>
>>    PKEX is, as the intro states, intended to provide trust to public keys
>> so they can be used in a different exchange that uses "raw" public keys
>> like TLS and IKEv2.
> This doesn't mean anything to me.  I don't trust public keys.  I trust
> certain things about the people who are able to use those keys in the
> future.

   Are you just being contrarian as a protective defense? I can't tell. You
may not trust public keys but if you obtained one via PKEX you could have
a certain amount of trust in one that you did not have before. A part of
this trust will be a binding to a person "who [is] able to use [that] key
in the future." So PKEX is offering you exactly what you want. Not that you
will admit it.
>>    Now both TLS and IKEv2 offer security guarantees about the authenticated
>> state of a successful run of the protocol and these are based, in part, on
>> the assurances placed in the public keys used in authentication. For
>> instance,
>> that the certificate was not issued to someone who could not prove ownership
>> of
>> the public key.
> Please elaborate.  What exactly breaks in TLS if I somehow obtain an
> apparently valid certificate for andy.lutomirski.com that lists
> Google's private key?  I certainly can't get any browser to identify
> me as andy.lutomirski.com using such a certificate because I have no
> ability to perform private key operations.  I sure hope that none of
> the TLS variants are subject to identity misbinding attacks.

   You're thinking about it backwards. What if I got a valid certificate
for google.com that lists Dan Harkins' public key? Maybe I'm blackmailing
some poor schlep at google. Maybe I gave him my signature on my public
key and threatened him to run Andy Lutomirski's insecure enrollment 
protocol,
or else. It would be better if the poor schlep would be able to say, 
"there's
nothing I can do, the protocol is secure, we're not running the Andy 
Lutomirski
protocol!"
>>> Here's an example of a bad protocol where you need property (3).
>>> Suppose that Bob writes a message that says "Please send me $100" and
>>> signs it using b.  Alice receives that message with appropriate
>>> assurances from someone she trusts that she should pay $100.  She
>>> further learns via an *unauthenticated* channel that the money should
>>> go to Bob.  She looks up Bob's public key B, checks the signature,
>>> decides that only Bob could have sent the message, and sends Bob $100.
>>>
>>> This protocol requires property (3).  But it's insecure in general
>>> anyway because digital signatures don't provide the guarantee that
>>> Alice is relying on: in many digital signature protocols, Charlie can
>>> take a signed message and generate a brand new key pair that appears
>>> to have also signed that message.
>>>
>>> But this protocol is just silly and shouldn't need property (3) at
>>> all.  Bob should sign the message "Pay me, Bob, $100 to this account"
>>> and Alice should look up the key that Bob says is safe to use to
>>> identify him (property (2)) and check the signature.  Problem solved
>>> (and it's now using digital signatures correctly, too).
>>
>>    Instead of addressing this ridiculous straw man of a protocol let me
>> refer you to the seminal work of Hugo Krawczyk: "SIGMA: The SIGn-and-MAc
>> Approach to Authenticated Diffie-Hellman and its Use in the IKE
>> Protocols." I strongly suggest you read the whole thing very closely but
>> pay special attention to the "identity mis-binding" attack he describes
>> against STS "when parties can register public keys without proving knowledge
>> of the corresponding signature key."
> Do you mean this bit, quoted directly from the paper?
>
>> Thus, for the STS to be secure one must assume that a secure external mechanism for proof of possession of signature keys is enforced. As we will see both the ISO protocol discussed in Section 4 and the SIGMA protocols presented here do not require such a mechanism.
> A large part of that paper is about developing a protocol that does
> *not* require property (3).

   Indeed it is. Designing protocols that are resistant to an identity
mis-binding attack is a goal. It is not an excuse to create identities
that can be mis-bound.

   Given the hygienic problem your suggested protocols have had I think it
is imperative every assurance that can be made of a key be made in case it
is used in one of your wacky protocols.

>>> So what is DPP doing that makes property (3) useful in pairing?
>>
>>    Who cares? The property is not only useful it's critical!
> It's only critical if DPP is poorly designed.  See above.

   Well then you should focus your attention on DPP then. This is
not DPP.
> There's a good reason not to provide property (3), though: unless you
> provide a genuine zero-knowledge proof of knowledge of the private
> key, you are now at risk from cross-protocol attacks and the overall
> protocol that uses your primitive needs to be checked for
> cross-protocol attacks.  For example, here's a proof of possession of
> a private key that is exceedingly dangerous:
>
> Alice -> Bob (encrypted, authenticated, etc): N_a
> Bob -> Alice (encrypted, authenticated, etc.): b * N_a
>
> Bob has just proved knowledge of b very convincingly to Alice.  But
> Alice can use this protocol as an oracle to sign arbitrary messages
> from Bob.

   Once again, your ability to create a ridiculously insecure straw man
protocol says nothing about PKEX. But it does quite strongly demonstrate
the need for true and strong proof-of-possession of any protocol that
creates trust in a public key.
> Another problem with proving knowledge of the private key as a
> built-in part of the protocol is that it ties the protocol to the
> public-key cryptosystem.  If Bob is merely transmitting a bit string B
> (with property (2) -- Alice trusts that Bob intended to send that bit
> string), then B could be an encryption-only key, it could be on any
> group, it could be a key of different underlying type entirely (e.g. a
> hash-based signature key or a lattice key), etc.  If you prove
> possession of b, then your protocol depends on the cryptosystem.  It
> also may rule out restrictive HSMs -- suppose that Bob stores b on an
> HSM that can *only* do ECDSA.  (This is probably a good idea in many
> cases.)  Bob can't run your protocol.

   Once again you have looked at the PKEX draft (in this case section 3),
noticed a statement and constructed some issue out of it. It's like you're
telling a car company, "You might've said I had to change the oil but I
never did, and now the engine seized. So the entire problem is with your
design of the car."

   It's odd for someone to argue for less integrity in a key but then,
here you are. You shouldn't be surprised that your campaign for less
integrity in public keys is not a popular one.

   Dan.