Subject: [Cfrg] Fun with Alice and Bob

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Feb 2014 09:50:24 -0800

Bob calls Alice.
Alice calls Bob at the same time.
Bob sets up a date, and Alice repeats back the time.

The next day Alice is a no show.

Alice and Bob used dragonfly. Dragonfly is symmetric: too symmetric.
Echoing one side of the exchange back leads to a succesful negotiation.

Don't be like Bob. Use real PAKEs.
Sincerely,
Watson Ladd

---

From: Alexandre Anzala-Yamajako <[email-masked]>
Date: Tue, 4 Feb 2014 18:58:20 +0100

This very notion of security was formalized as Aliveness by Lowe in 1997
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.3385&rep=rep1&type=pdf.

It feels ill advised to make an rfc of a protocol failing to achieve that
weak of a property in 2014

Sincerely

-- 
Alexandre Anzala-Yamajako

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 4 Feb 2014 10:51:46 -0800 (PST)

> weak of a property in 2014

  Yes such a thing would be ill advised, good thing the protocol does not
fail to achieve this property. Please read the I-D.

  Dan.

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Feb 2014 11:13:11 -0800

> > This very notion of security was formalized as Aliveness by Lowe in 1997
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.3385&rep=rep1&type=pdf
.
> fail to achieve this property. Please read the I-D.

Unless I'm badly mistaken a simple reflection attack does work. I went back
and double checked on receiving your email, and it looks like the key
exchange is symmetric.

You avoided this by specifying a reflection attack protection, but such
protection doesn't work if we interchange 2 exchanges, which I specified in
my story above.

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 4 Feb 2014 11:51:58 -0800 (PST)

> protection doesn't work if we interchange 2 exchanges, which I specified

  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.

  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).

  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.

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Feb 2014 13:37:55 -0800

On Feb 4, 2014 1:03 PM, "Dan Harkins" <[email-masked]> wrote:
>
>
> On Tue, February 4, 2014 12:03 pm, Watson Ladd wrote:
> > On Feb 4, 2014 11:51 AM, "Dan Harkins" <[email-masked]> wrote:
> > 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.

Balanced also doesn't mean symmetric.
> > Hidden in the above is the assumption that only one instance of the
> > dragonfly state machine runs between Alice and Bob.
> >
> >>
> > 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.

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?

Did the EAP draft discuss this issue?
Was this discovered in 802.11s?
It wasn't noticed in the TLS debate. I didn't notice it until this morning.

Dragonfly should be secure. It looks at first glance to be secure. But we
don't know if it is secure. It has surprising properties that aren't
documented in the draft.

How certain are you of its security, and when you insist that it is secure,
what do you mean?

Sincereley,
Watson Ladd

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 4 Feb 2014 16:45:54 -0800 (PST)

> 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.

> 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).

> 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.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Feb 2014 17:20:12 -0800

> 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.

> (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.

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