Figure out which DAKE to use about otrv4

[tcz001]

Cool, so we agree on using Spawn?

[chelseakomlo]

Hey All,

The outcome from the debate is:

• We recommend using RSDAKE/QuickSpawn
  The reason for this is because this introduces fewer new concepts. As Spawn introduces both the DRE and Auth, whereas RSDAKE/QuickSpawn only introduce Auth. As the properties for performance and security are similar between RSDAKE/QuickSpawn and Spawn, we wanted to choose the option that had less risk for implementation.
• We recommend splitting the spec, so that an implementer could implement the protocol only online with RSDAKE, or could do both online/offline.
  The reason for this is because if someone wants to upgrade to v4 but doesn't have the ability to implement a central server, they could still get the benefit of deniability from RSDAKE.
  We can talk further about how to do this exactly.

Cheers!

[tcz001]

Signed by survivors in quito

[tcz001]

Spawn:

• Computational: a bit slower, less than one second
• Performance on high latency: 1 transmissions faster when interactive
• Complexity: Needs DRE no enough assessment
• Security: Introduce two new cryptosystem DRE and Auth at the same time can be a potential risk

[tcz001]

RSDAKE&QuickSpawn:

• Computational: faster with fewer Group operations
• Performance on high latency: 1 transmissions slower for RSDAKE
• Complexity: Needs two types of keys, two types of AKE
• Security: Needs a KDF function using PK_I

[chelseakomlo]

@olabini There is a line in thoughts.md that says "Quickspawn for noninteractive and RSDAKE for interactive, if we can make it work."

Do you mind giving more context on this? It seems that this was discussed offline so understanding why that was written (specifically the implied preference for RSDAKE/QuickSpawn) would be useful.

[chelseakomlo]

Here are how an initiator and responder would use RSDAKE/QuickSpawn:

Initiator:

• If online, respond to all messages using RSDAKE
• Once every period (maybe 1 week?) use QuickSpawn to generate a batch of prekeys to send to the central server
• If an initiator comes online & receives messages sent while offline, they would verify it and then create a root key (but would need to know that the message was received while offline, as the root key is derived from their public key as well as both I and R's ephemeral keys)

Responder:

• If the contact is offline (information provided by XMPP) perform the AKE with QuickSpawn
• Otherwise perform the AKE with RSDAKE

[chelseakomlo]

How likely is it that existing elliptic curve implementations expose the functions needed for Cramer Shoup? I see that @olabini had to submit a pull request to a GoLang ed25519 for this.

agl/ed25519#19

[chelseakomlo]

Also, after our meeting yesterday, we are assuming that if we decide to use Spawn, we will only use one key for both interactive/non-interactive.

[tcz001]

How likely is it that existing elliptic curve implementations expose the functions needed for Cramer Shoup?

Both Auth (for computing T_2 T_3) and DRE (for Cramer-Shoup) needs point addition, so once we decide to use ECC we need the same function exposed.

As I tested, the point addition on edward curve won't be dramatically increasing the computing time, compared with scalar multiplication on point. Because of this, both ed25519 and ed448 just need a constant time point addition exposed for Cramer Shoup and Auth

[chelseakomlo]

Fan and I are writing the AKE section of the protocol specification this afternoon!

[claucece]

Good! :) thanks!

[iapazmino]

Issue #15 is open for the AKE description.

[olabini]

Chelsea, the comment about QS/RSDAKE was just a reminder to think about it - the thing about whether it's possible to make it work was from the perspective of complexity of two AKEs, fallback etc. Not a specific endorsement of that combination of primitives.

[olabini]

Chelsea, the comment about Initiator, Responder is super confusing. I have absolutely no idea what any of it means.

[olabini]

Chelsea, about your comment on elliptic curve primitives. It doesn't matter - we will still need them for the rest of the AKE as well. It's not just Cramer-Shoup.

[olabini]

If we use Spawn, yes, we should be able to use the same long lived keys for both interactive and non-interactive cases.

[olabini]

I completely disagree with the recommendation - I need better reasoning than that - especially around the extreme increase in implementation complexity having two different DAKE's, fallbacks, corner cases and so on.

[olabini]

So, please don't start writing something. This issue is by no degrees solved to my happiness.

[tcz001]

Ok, around the complexity,

First DRE is very complecated and hard to be convincing according to current situation, no working implementation yet, no enough assessment either. You need to persuade me how and why you chose those two generators at least.

Second, by saying extremly increase of complexity, I don't understand what does it exactly mean, DRE also increase complexity. To what we discussed, the complexity will be most likely come from a state machine we need to maintain for both sides online and offline, it's not extremly decreasing the cases even when we choose Spawn-only, offline DAKE is still something providing lower security properties, that needs an extra care,
for example, When receiving offline message and want to reply, should we always restart AKE for online repudiation? When to send those preshared init message to central server? You will see they're corner cases for both sides.

The other concern will be management of two types of keys, this is turely increasing complexity, but from a implementor's perspective, we doubt if it's more difficult than having one more totally new cryptosystem.

BTW, Should we ask for some advise from otr community if they are happy to introduce DRE?

[olabini]

I actually do not think introducing DRE by itself is that big of a deal in terms of complexity. It's not a new crypto system at all - It's based on composing two well understood primitives - Cramer-Shoup and a NIZKP. Both of them have been seriously analyzed in the academia. (And the NIZKP construction is also used in Auth, so it will still be there).

I don't need to convince you of anything about how the generators were created. The code is in the repo for generating them - most of that code is a copy of the ed25519 python reference implementation.

You are right that the online vs offline introduces complexity by itself, but I would argue that having two completely different AKEs is a combinatorial increase in complexity ON TOP of the complexity of offline vs online.

[olabini]

About asking people, did you do what I said in one of my email and hang out on #otr and talk to the people I mentioned?

[chelseakomlo]

RSDAKE and QuickSpawn are not completely different, right? The primary difference between the two is how the session key is created.

[chelseakomlo]

If implementors only wanted to do an online version of v4, they could do it with just RSDAKE. I think it would be worth considering the barrier to upgrading for current projects. We should probably ask them this directly.

[olabini]

I have no idea what these two comments mean.
And no, I don't think we should consider the barrier to upgrading. This protocol will be completely new implementations no matter what.

[chelseakomlo]

It's not the barrier to upgrading for the protocol, it is the barrier to entry for the additional infrastructure needed for an offline AKE, as the implementor will need to set up a central server.

That is something we should definitely consider, whether this would prevent current implementations from upgrading.

For example, Coy would have to stand up a central server to upgrade. Is this something that is possible? Would other current implementations be also willing to do this?

[chelseakomlo]

I'm going to write up all of this, and send it to the otr mailing list for comment! Will first send to our team for review.

[chelseakomlo]

I completely disagree with the recommendation - I need better reasoning than that - especially around the extreme increase in implementation complexity having two different DAKE's, fallbacks, corner cases and so on.

Hey @olabini, can you expand on this? We are writing out all of the cases we have in mind, but if you have specific cases, fallbacks, or complexity, please let us know.

[chelseakomlo]

Here are the general cases we can think of for initiating a conversation (not specific to a protocol but in general).

Both online:

1. Both parties exchange ephemeral keys and authenticate to each other. This is similar to OTRv3

One online, the other offline:

1. I periodically uploads prekeys to a central server
2. R wants to initiate a message with I. They check their status & see they are offline
3. R fetches I's prekey from a central server
4. R sends I their ephemeral key, auth
5. When I comes online, I checks for AKE messages received while offline from a central server
6. I will validate and complete the handshake for each AKE message received while offline

Edge cases:

a. No available prekeys

1. R wants to initiate a message with I. They check their status & see they are offline
2. R tries to fetch I's prekey from a central server, but there are none available.

What further cases should we consider (protocol agnostic, the next message will be how each of these cases would be achieved between our two options)

[olabini]

Well, for one, what happens if you have done an RSDAKE start, waited for a while and then done a QS start, but at that point the other side continues the RSDAKE? How much context do you keep track of? Etc etc etc. I'm just saying, you will find that there are a bunch of these complexities.

[olabini]

And why in anything holy would Coy need to set up a central server? Of course not!

[olabini]

That would be super bad and not relevant at all to having a prekey system.

[olabini]

So, once again - I don't want you to continue writing out the AKE until you have actually come with better arguments than the above.
And no, sending it to the list is not a good idea.

[chelseakomlo]

And why in anything holy would Coy need to set up a central server? Of course not!

@olabini How would prekeys be managed for an offline AKE?

[tcz001]

this case is same for SPAWN, if you have a online SPAWN established, then
you receive a offline SPAWN AKE message and a encrypted message, which
session k should you use? You will need to keep track of all the
online/offline conversations to reveal session keys later, because anything
can happen.

2016年9月8日 下午2:36，"Ola Bini" [email protected]写道：

Well, for one, what happens if you have done an RSDAKE start, waited for a
while and then done a QS start, but at that point the other side continues
the RSDAKE? How much context do you keep track of? Etc etc etc. I'm just
saying, you will find that there are a bunch of these complexities.

—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
#4 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ABn5xN70QrCzbOpb36K-fw_oY5QveRSeks5qoGOsgaJpZM4J2NEI
.

[tcz001]

One important thing we haven't describe clearly is when should prekeys be
sent and avalible for others to use, and should those prekeys ask
authentation for fetcher? because even when you are online, there's
posibility to receive offline AKE/Data message in the queue, and It's easy
to do a DOS by withdraw all the keys out.

2016年9月8日 下午4:48，"蒋颿" [email protected]写道：

this case is same for SPAWN, if you have a online SPAWN established, then
you receive a offline SPAWN AKE message and a encrypted message, which
session k should you use? You will need to keep track of all the
online/offline conversations to reveal session keys later, because anything
can happen.

2016年9月8日 下午2:36，"Ola Bini" [email protected]写道：

Well, for one, what happens if you have done an RSDAKE start, waited for
a while and then done a QS start, but at that point the other side
continues the RSDAKE? How much context do you keep track of? Etc etc etc.
I'm just saying, you will find that there are a bunch of these complexities.

—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
#4 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ABn5xN70QrCzbOpb36K-fw_oY5QveRSeks5qoGOsgaJpZM4J2NEI
.

[olabini]

I don't think it is the same for SPAWN.
Whatever, you make the decision you want.

[olabini]

@chelseakomlo - absolutely not by having Coy have its own centralized infrastructure. That's where the other proposal comes in - as I said in one of my email, that would probably need to have specific things for specific technologies, so for XMPP we should use one of the storage mechanisms that XMPP allows, in order to save prekeys. PEP or something like that.

[juniorz]

We need to make a decision regarding the AKE.

I advocate for SPAWN because:

1. Same DAKE protocol stack for both interactive and non-interactive (less complexity to OTRv4 implementers - no need to maintain multiple DAKE stacks).
2. Same long-term keys for both interactive and non-interactive (less complexity to OTRv4 users - no need to verify two long-term keys independently).
3. Performance does not seem to be a problem (although the paper mentions a big difference in terms of group operations it don't seem to reflect in a big difference in terms of time).
4. Introducing DRE is less complex than maintaining two DAKE stacks.

[rosatolen]

Also, using RSDAKE/QuickSpawn does not provide better deniability than Spawn in either interactive or non-interactive cases.

[claucece]

This is what quantum resistance Spawn looks like in an interactive scenario (providing transitional security):

(This should be moved to another section)
TODO: review this part.

• G: group to be used for all key exchanges.
• q: the (prime) order of the group.
• p: a safe prime generated with a Sophie Germain prime q.
• g1 and g2: the distinct Cramer-Shoup generators for the group, suitable for Diffie-Hellman key exchanges and the Cramer-Shoup cryptosystem.

Alice long-term Cramer-Shoup key-pair is SKa = (x1A, x2A, y1A, y2A, zA) and PKa = (cA, dA, hA).
Bob long-term Cramer-Shoup key-pair is SKb = (x1B, x2B, y1B, y2B, zB) and PKb = (cB, dB, hB).

Alice:

1. Selects an ephemeral secret i from Zq uniformly at random.
2. Chooses an ephemeral SIDH key pair SIPKa SISKa
3. Sends ψ1 = ("I", g1^i, SIPKa) to Bob.

Bob:

1. Selects an ephemeral secret r from Zq uniformly at random.
2. Chooses an ephemeral SIDH key pair SIPKb SISKb
3. Computes γ = DREnc(PKb, PKa, “I” ∥ “R” ∥ g1^i ∥ g1^r ∥ SIPKb ∥ SIPKa).
4. Computes σ = Auth(hA, zA, {hB , hA, g1^i }, “I” ∥ “R” ∥ g1^i ∥ SIPKa ∥ γ).
5. Sends ψ2 = (“R”, γ, σ) to Alice.
6. Computes k = KDF((g1^i ) * r ∥ SIDH(SIPKa ∥ SIPKb)) and securely erases r and SISKb.
   Note: Bob can attach an initial message m by encrypting with key k.

Alice:

1. Verifies the proof σ.
2. Decrypts γ using SKa.
3. Verifies the following properties of the decrypted message:
   • The message is of the correct form (e.g., the fields are of the expected length);
   • Alice's identifier is the first one listed;
   • Bob's identifier is the second one listed, and it matches the identifier transmitted outside of the ciphertext; and
   • g1^i, SIPKa is a pre-key that Alice previously sent and remains unused.
4. Computes k = KDF((g1^r ) * i ∥ SIDH(SIPKb ∥ SIPKa))and securely erases i and SISKa. If an initial message was attached, Alice can decrypt the message using k.

Notes:

• SIDH has a reputation for being relatively inefficient.
• Possible replacement for SIDH: "New Hope" key transport scheme, but it will give a non-contributory exchange.