[curves] Mutual-auth Ace (was Re: MQV)
Trevor Perrin
trevp at trevp.net
Thu May 15 11:33:19 PDT 2014
On Thu, May 15, 2014 at 2:53 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
>>> you
>>> could use CDH(P, A, Y_1) + CDH(P, X_1, B) + CDH(P, Y_1, Y_2) as the
>
> Er. The last term should be CDH(P, X_2, Y_2).
I'll be explicit, for those following along:
Alice has:
identity public key A
ephemeral public keys A1, A2
Bob has:
identity public key B
ephemeral public keys B1, B2
ecdh_result = ECDH(A, B1) + ECDH(B, A1) + ECDH(A2, B2)
session_key = Hash(ecdh_result || A || A1 || A2 || B || B1 || B2)
ECDH(pub1, pub2) = (priv1 * priv2) * basepoint
+ is addition of EC points
|| is concatenation of byte sequences
Calculating ecdh_result as a sum of 3 points means the sum can be
computed using Shamir's simultaneous exponentiation (aka
"multi-exponentiation"). So this perhaps could be faster than a naive
"TripleDH" that hashes 3 ECDHs directly.
Anyone see a problem?
>>> secret input to the KDF.
>>
>> That's cool!, if it's secure it seems like a better extension of Ace
>> to mutual-auth. It's similar to TripleDH but each party has 2
>> ephemerals instead of 1, and the 3 ECDHs are added together before
>> being hashed into a session key.
>
> It does need a systematic security analysis. (It also needs a name --
> “Mace”? “Deuce”? Insert random winged insect name here?)
I think that's up to you, deuce isn't bad..
>> (Also similar to MTI/A0 with an
>> ephemeral-ephemeral op added.)
>
> I thought Ace was similar to MTI/C0, not MTI/A0.
MTI/AO exchanges ephemerals A1, B1, and calculates:
ecdh_result = ECDH(A, B1) + ECDH(B, A1)
MTI/C0 exchanges ECDH(A, B1) and ECDH(B, A1), and calculates:
ecdh_result = ECDH(A1, B1)
I.e. it assumes Alice and Bob know each other's identity public keys,
and uses those to mask the ephemerals.
> Remember that the MTI protocol didn't specify to include the public
> keys in the KDF input. Ace is only secure if you hash all of the
> public keys along with the secret group element.
Right.
>> But it could be faster than TripleDH because you could use Shamir's
>> trick to compute the sum of the 3 ECDHs.
>>
>> Assuming MQV is ~2x faster than TripleDH:
>> - 1.5 variable-base ops, 1 fixed-base (MQV) vs
>> - 3 variable-base ops, 1 fixed-base (TripleDH)
>>
>> I wonder how close to MQV speed this could get?:
>> - 1 variable-base triple-op, 2 fixed-base
>
> Again, remember that in TripleDH and the Ace variants, the fixed-base
> exponentiations (to generate ephemeral keypairs) can be reused across
> multiple protocol runs *if* the parties which reuse their keys each
> contribute a nonce to the shared key. (This does make the protocol
> runs linkable, but that's often acceptable.) I suspect that that's
> not safe in MQV.
Ephemeral reuse also reduces your KCI-resistance and forward-secrecy
during that window.
Are there formal models of security for ephemeral reuse (e.g. is there
a way to tweak something like eCK to account for it?)
(And do you have a reference for MQV being insecure with ephemeral reuse?)
Anyways, I'd still be curious how the apples-to-apples performance
comparison looks (above vs MQV).
To be concrete: what's the efficiency difference between 1.5
variable-base curve25519 and one fixed-base (MQV), versus a triple
Ed25519 multi-op, with 2 fixed base (mutual-Ace).
Trevor
More information about the Curves
mailing list