Re: [Cfrg] Fun with Alice and Bob

[Watson Ladd <[e-mail]>]

On Tue, Feb 4, 2014 at 4:45 PM, Dan Harkins <[e-mail]> wrote:
>
> On Tue, February 4, 2014 1:37 pm, Watson Ladd wrote:
>> On Feb 4, 2014 1:03 PM, "Dan Harkins" <[e-mail]> wrote:
>>>
>>> On Tue, February 4, 2014 12:03 pm, Watson Ladd wrote:
>>> > On Feb 4, 2014 11:51 AM, "Dan Harkins" <[e-mail]> wrote:
>>> >>   The symmetry of dragonfly is a feature since the world is not
>>> > client-server
>>> >> and it most certainly is not HTTP. For ad hoc, mesh and peer to peer
>>> >> networking either side can initiate and both sides can initiate
>>> >> simultaneously (while one of the messages will cross the ether before
>>> >> the
>>> >> other, both parties send the initial message and they view themselves
>> as
>>> >> "initiator" in the protocol). To allow for password authentication in
>>> >> such
>>> >> an environment a symmetric PAKE like dragonfly is necessary.
>>> >
>>> > Or one can decide to go first.
>>>
>>>   Yes, one can decide to go first. But if the other side decides to go
>>> first too then you need a protocol to settle who goes first. So let's
>>> say you have this protocol to go first that runs before your augmented
>>> PAKE. That will require each side to possess the password and the
>>> verifier since the protocol to go first could pick one or the other. So
>>> your losing this valuable (to you) feature in your augmented PAKE,
>>> reducing it to a balanced PAKE, and adding unnecessary complication
>>> in the form of the protocol to go first. That is a losing proposition.
>>
>> Maybe, maybe not. Remember dragonfly assumes ordered IDs. Higher ID goes
>> first doesn't add rounds.
>
>   Not sure where you got that assumption. But if the ID is conveyed in the
> protocol you have a serious chicken-and-egg issue since someone has to
> "go first" to find out who goes first. For a protocol like IKE this would not
> work either because IKE is initiated because some IP packet got a hit in
> the SPD and there's no SA to process it. If that happened on an IKE peer
> that had a "lower ID" then all packets would be dropped. Not good.

Other than the draft using min and max on IDs? We need to distinguish
the password elements
of different pairs of nodes to avoid A and B negotiating a key with
each other instead of with C
as they both think.

Lower ID could initiate: the idea would be that the higher ID node
would, once it starts initiating,
not respond to a lower ID invitation.

>
>> Balanced also doesn't mean symmetric.
>>>
>>> >>   Dragonfly handles the situation of simultaneous initiation very
>>> well
>>> >> as evidenced by its use in the 802.11 (and the open11s project which
>>> >> uses a mesh daemon implementing dragonfly to authenticate other
>>> >> mesh peers). The state machine is quite elegant, if I may say so
>> myself,
>>> >> and is robust-- it got quite a bit of testing for the open11s
>>> project.
>>> >>
>>> >>   Now, this draft in the CFRG is a generic description of the
>>> exchange.
>>> >> Instantiations of dragonfly for some particular protocol could add
>>> >> the sender's identity-- MAC address, NAI, whatever-- to the Confirm
>>> >> message to prevent a reflection attack. But as a general description
>>> of
>>> >> the protocol that information is not available since no medium is
>>> used.
>>> >> The Confirm message is symmetric and the prevention of the attack is
>>> >> somewhat clunky (make sure what you received differs from what you
>>> >> sent).
>>> >
>>> > Hidden in the above is the assumption that only one instance of the
>>> > dragonfly state machine runs between Alice and Bob.
>>> >
>>> >>
>>> >>   All that said, I don't see the attack you mention. It looks like
>>> one
>>> >> of the exchanges will fail because it's a reflection attack and the
>>> >> other will either time out because it was just used to echo back
>>> >> initial data to the other exchange or it will also fail due to the
>>> > reflection
>>> >> attack check.
>>> >
>>> > Alice to Eve: g^x.
>>> > Eve causes Alice to instantiate a different dragonfly instance,
>>> leading
>>> > with g^x.
>>> > Alice responds with g^y, which Eve relays over to the other
>>> connection.
>>> >
>>> > Keeping a consistent global anti replay list solves this, but is a
>>> real
>>> > pain point for implementations.
>>>
>>>   Yes, the assumption in the draft was that if you're doing a strict
>>> client-server instantiation then one side is always the client and one
>>> side is always the server. And if you're not doing client-server then
>>> you have a single state machine to handle both the initiation role
>>> and the responder role. That assumption is not explicit in the draft.
>>
>> It should be. It also isn't sufficient: a client that makes two
>> simultaneous connections to a server also falls to this attack.
>
>   You bring up a good point so I should probably be more explicit but
> something tells me you don't really care. You're just throwing bombs.
> (And I say that as an experienced bomb thrower).

If you fix those problems, then dragonfly has a security reduction in
the ROM to something somewhat
reasonable. I only discovered this a few minutes ago.

In the ROM we have independent PE's p_{ij} between each pair of nodes
a_i and a_j. Therefore, we can focus on
a given pair A and B with generator g.

Both nodes will strictly alternate between sending g^x for random x
and the confirmation key for the exchange they
just underwent.

The attacker wins if they can learn anything about the key, or cause A
to think that it confirmed with B and B doesn't think so.

The problem of course is the independence assumption is completely
false in the standard model, and the restrictions
on usage really nasty for most protocols. The problem I reduced it to
isn't yet computational, and so we still have work to do.
It also isn't clear how strong it is. Let me write it up and see if it
actually is correct.

Anyway, given this reduction being correct, and some text explaining
the protocol restrictions, I think I don't have any objections to the
protocol.

>
>> How many more assumptions like this are there? How many real
>> instantiations
>> will violate these assumptions? Absent a reduction why should I think we
>> found them all? And why can't you use something more robust?
>
>   As I stated, this is a generic definition. The actual instantiations of
> dragonfly are not susceptible to this kind of attack because they
> produce a different password element with each run of the protocol
> and because they follow the assumptions that I have poorly stated
> in this generic definition (since I wrote all the actual instantiations).
>
>   I will address this in a next version of the I-D so that if someone
> were to take this generic protocol statement and instantiate it for the
> Foo protocol it will be done correctly. Thank you for helping me
> to further refine and improve the language in this document. It will
> be more clear because of your help.
>
>   Dan.
>
>
>
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin