Generalize RSig (Auth) function

[claucece]

This section assumes that A1 is the public key, but the function must be generalized to work with any of the keys (while using constant-time conditional copies and other techniques to avoid side channel attacks). Ideally, the specification should show all three versions along with the side-channel-free generalized version to reduce the chance of implementation bugs.

See: https://github.com/otrv4/otrv4/blob/master/otrv4.md#ring-signature-authentication and "Improved Strongly Deniable Authenticated Key Exchanges for Secure Messaging", section 4.3.

[juniorz]

I don't understand the benefit of generalizing the RSig function, I would rather propose rewriting as RSig(A1, a1, {A2, A3}, m) since the caller must control (A1, a1) anyways.

I also can't see any potential side-channel attacks on the current description of Rsig (on the spec), and it seems to be a problem that will appear only if we generalize it.

Do you remember any additional information on this issue?

[claucece]

I guess that the benefit of generalizing it is that it provides:

1. anonymity against full key exposure: it is not possible to determine which secret key was used to produce the ring signature, even if all secret keys are revealed.

I think that the way we are handling this right now, is showing exactly which secret key is used. And the key used to produce the proof should not be able to be inferred, that is why "the order of elements passed to H and sent to the verifier must not depend on the secret known the prover (otherwise, the key used to produce the proof can be inferred in practice)".

Generalizing it, will mean – RSig(A, a,S, m, r): RSig produces an SoK, bound to the message m, that demonstrates knowledge of a private key corresponding to one of three public keys. S is the ring of public keys {A1,A2,A3} that could possibly have produced the proof. It is required that (A, a) is a Diffie-Hellman keypair in the appropriate group, and A > S. r controls the randomization of the output. The SoK is computed as described above, with r interpreted as r = t_i||c_j||c_k||r_j||r_k, where i is the index of A in S, and j and k are the values in {1, 2, 3} such that i, j, and k are distinct and j < k. If r is omitted, it is assumed that r<- {0, 1}^l is used.

This comment is referring to the Authentication: RSig(A1, a1, {A1, A2, A3}, m) section. And I guess as an appendix, it can be generalized. This means generalizing on the appendix and maybe showing the three ways of doing it on the DAKEZ or ZXDH overview plus the "side-channel" free one.

There is no potential side-channel attacks as it is right now, but it will probably be when it is generalized (that is why it says "the side-channel-free generalized version"). I think that can be achieved by: doing the three way RSig can show the time of doing with Ax and therefore be compared with the time of doing with other Ay. This might leak information. This is just an idea.

I would rather propose rewriting as RSig(A1, a1, {A2, A3}, m) since the caller must control (A1, a1) anyways.

I guess we are putting A1 twice to be consistent with the notation: RSig(A, a, S, m, r): A is any of the pub keys and S is the ring of the pub keys, defined as {A2, A, A3}, whichever A it is. The choice of three is sort of defined on "Efficient Ring Signatures without Random Oracles" by Hovav Shacham and Brent Waters, on "Our Ring Signature Construction" section. As it is defined there: "No key may appear twice in S, and S must include pk."

[juniorz]

Oh, I see. Now it is clearer that we may need to start by making sure this holds:

The order of elements passed to H and sent to the verifier must not depend on the secret known the prover (otherwise, the key used to produce the proof can be inferred in practice).

and, to me this is achieved by making sure:

The SoK is computed as described above, with r interpreted as r = t_i||c_j||c_k||r_j||r_k, where i is the index of A in S, and j and k are the values in {1, 2, 3} such that i, j, and k are distinct and j < k.

And it is free of side-channel effects.

In practice it seems to mean that the order that we concatenate elements should stay the same (A1 || A2 || A3 || T1 || T2 || T3) regardless of the position of A1 (pair of a1) in the "ring". Which is not true given our current implementation (and spec).

Thanks, I feel much more comfortable in explaining this to someone else now.

[juniorz]

This is very interesting, I will unassign this to me for now.

[claucece]

@juniorz check it, if you can :)

[juniorz]

I see the intent of be3a52bd557cdf6ca0604a64dcd09479209ecdb0, but I think its clarity can be improved.

What I had in mind initially was to have a single function description that is already written having both concerns in mind (constant positional order of T1, T2, and T3; constant-time and side-channel free implementation).

P = G * a1
eq1 = constant_time_eq(P, A1)
eq2 = constant_time_eq(P, A2)
eq3 = constant_time_eq(P, A3) 

serT1 = constant_time_select(eq1, SER(G * t1), SER(G * r1 + A1 * c1))
serT2 = constant_time_select(eq2, SER(G * t2), SER(G * r2 + A2 * c2))
serT3 = constant_time_select(eq3, SER(G * t3), SER(G * r3 + A3 * c3)).

Here we explicitly generate each Ti already serialized, rather than postponing serializing each Ti to the moment it is used to compose the value that will be hashed to a scalar.

The constant time functions are the traditional functions: constant_time_eq returns 1 if equals, 0 otherwise, and constant_time_selectreturns the second parameter if the value is 1, and the third otherwise.

Also note the choice to be explicit and use longer variable names (eq1 and serT1) to indicate something that is not either a point or a scalar. I think the lack of this boundary confused me in my previous messages).

I am assuming this is what you meant later with 7e7742f2a1b0f85f8be09716e081b520a752e9fa, is that correct?

[juniorz]

I updated the original comment for clarity. I am sorry. ;)

[claucece]

I updated the original comment for clarity. I am sorry. ;)

No problem. :)

Yeah, that looks very nice. I was actually thinking on only having the three specific ways of doing it, but this is clearer.

Also note the choice to be explicit and use longer variable names (eq1 and serT1) to indicate something that is not either a point or a scalar. I think the lack of this boundary confused me in my previous messages).

Well, eq1 is just a "bool". But serT* are encoded as points.

I was actually thinking on having a section (maybe in recommendations for implementers), which defines how to do point addition, subtraction and scalar multiplication. We can add constant time equality and selection as well. Just like some RFCs do it.

Commit 6d3fd8495788f4cee7f41a915df649c57f0dac37 now has the changes.. is that better?

Thanks!

[annacruz]

For me personally is much better now than was previously. The only thing that I missed (but I really don't know if is necessary) was what is A2 and A3.

[claucece]

@annacruz

Thanks for looking into this :)

A2 and A3, depend on how the function will be called. In the case of sigma = RSig(Pka, ska, {Pkb, Pka, Y}, t), they are: Pka, Y.

[juniorz]

I guess there's no need for the first A1. What about writing the function as RSig(a, {A1, A2, A3}, m) to both remove the duplicate A1 parameter and dissociate the private key with the first public key in the set?

On 03/12/2018 06:17 PM, Sofía Celi wrote:

@annacruz https://github.com/annacruz

Thanks for looking into this :)

|A2| and |A3|, depend on how the function will be called. In the case of |sigma = RSig(Pka, ska, {Pkb, Pka, Y}, t)|, they are: |Pka, Y|.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/otrv4/otrv4/issues/99#issuecomment-372465539, or mute the thread https://github.com/notifications/unsubscribe-auth/AAB4WZ5miX1tCVM-wMPTn4GXp6viXyVVks5tduXTgaJpZM4Raaqf.

[juniorz]

Compute c = HashToScalar(0x29 || G || q || A1 || A2 || A3 || T1 || T2 || T3 || m).

Also, step 3 mentions Ti instead of serTi.

On 03/12/2018 06:17 PM, Sofía Celi wrote:

@annacruz https://github.com/annacruz

Thanks for looking into this :)

|A2| and |A3|, depend on how the function will be called. In the case of |sigma = RSig(Pka, ska, {Pkb, Pka, Y}, t)|, they are: |Pka, Y|.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/otrv4/otrv4/issues/99#issuecomment-372465539, or mute the thread https://github.com/notifications/unsubscribe-auth/AAB4WZ5miX1tCVM-wMPTn4GXp6viXyVVks5tduXTgaJpZM4Raaqf.

[claucece]

I guess there's no need for the first A1. What about writing the function as RSig(a, {A1, A2, A3}, m) to both remove the duplicate A1 parameter and dissociate the private key with the first public key in the set?

This is more to be consistent with the notation, and what is used in the 'actual' function. The choice of three is sort of defined on "Efficient Ring Signatures without Random Oracles" by Hovav Shacham and Brent Waters, on "Our Ring Signature Construction" section. As it is defined there: "No key may appear twice in S, and S must include pk."

Also, step 3 mentions Ti instead of serTi.

Oh, I was going to call it Ti, because they are encoded points.

Thanks!