Subject: [Cfrg] A problem with the security proof of AugPAKE?

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 11 Jul 2016 16:06:06 +0300

Dear SeongHan and colleagues!

It seems to me and my colleagues that there may be a major problem with a
security proof of AugPAKE, and I'll be thankful if you comment on this
issue.

If we look on the most significant part of the upper bound of adversary
advantage (Theorem 1 in https://eprint.iacr.org/2010/334.pdf), we'll have
the following:
\Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} + 2N^2\cdot
q_{hashH} \cdot Succ^{1sdh}_{g,\mathbb{G}}(t + \tau_e).

The problem we see is that the estimation depends on N (the volume of
dictionary) quadratically, and in the first part N occurs in the divisor
only linearly - so when the dictionary grows, the bound becomes weaker.

It wouldn't be a problem, if the effect were not present for ordinary
values of N (and would occur only for extremely large values of N) - but it
is.

[The rest part of the message contains rough estimations that illustrate
what I'm saying.]

If we estimate Succ^{1sdh}_{g,\mathbb{G}}(t)  as \frac{t^2}{|\mathbb{G}|}
(Pollard's rho-algorithm) and t \approx q_{hashH} the estimation will be
the following:
\Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} +
\frac{2N^2\cdot q^3_{hashH}}{|\mathbb{G}|} .
Let |\mathbb{G}| = 2^{256}$, $q_{hashH} = 2^{50}.
Then for N \geqslant
\sqrt[3]{\frac{6(q_{sendC}+q_{sendS})|\mathbb{G}|}{q^3_{hashH}}} \approx
2^{30} the estimation will be weaker for greater $N$.

And N=2^{30} is the dictionary for 6 symbols of (0-9, a-z, A-Z) -
absolutely reasonable value, that is definitely not extremely large.

Thank you in advance for your comments!

Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,
CryptoPro LLC

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 11 Jul 2016 11:53:29 -0700

Hi Stanislav,

That AugPAKE proof doesn’t work anyway, as I’ve pointed out here before.  Specifically, Lemma 1 doesn’t hold even with the quadratic bound.  A legitimate server will compute:

y random
y~ = H~(y)
K = g^y~

The proof of Lemma 1 assumes that an adversary will also do this, and that (because of some random-oracle assumption on H~) that the challenger will therefore know y~.  Of course this isn’t true, because the adversary might have computed K as something other than g^y~.  For example, it might have used X in the calculation, where in the relevant game X is an unknown power of g.  This is where the q_hashH~ term comes from in Lemma 1.

The N^2 term in that lemma comes from the same wrong idea about how a challenger and adversary work.

I asked the authors of the paper (both 辛星漢 and 古原和邦) about this last March.  They said they wanted some time to think about my comments, but they didn’t get back to me.

Cheers,
— Mike

> On Jul 11, 2016, at 6:06 AM, Stanislav V. Smyshlyaev <[email-masked]> wrote:
> 
> It seems to me and my colleagues that there may be a major problem with a security proof of AugPAKE, and I'll be thankful if you comment on this issue.
> 
> If we look on the most significant part of the upper bound of adversary advantage (Theorem 1 in https://eprint.iacr.org/2010/334.pdf <https://eprint.iacr.org/2010/334.pdf>), we'll have the following: 
> \Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} + 2N^2\cdot q_{hashH} \cdot Succ^{1sdh}_{g,\mathbb{G}}(t + \tau_e).
> 
> The problem we see is that the estimation depends on N (the volume of dictionary) quadratically, and in the first part N occurs in the divisor only linearly - so when the dictionary grows, the bound becomes weaker.
> 
> It wouldn't be a problem, if the effect were not present for ordinary values of N (and would occur only for extremely large values of N) - but it is.
> 
> [The rest part of the message contains rough estimations that illustrate what I'm saying.]
> 
> If we estimate Succ^{1sdh}_{g,\mathbb{G}}(t)  as \frac{t^2}{|\mathbb{G}|} (Pollard's rho-algorithm) and t \approx q_{hashH} the estimation will be the following:
> 	
> \Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} + \frac{2N^2\cdot q^3_{hashH}}{|\mathbb{G}|} .
> 	
> Then for N \geqslant \sqrt[3]{\frac{6(q_{sendC}+q_{sendS})|\mathbb{G}|}{q^3_{hashH}}} \approx 2^{30} the estimation will be weaker for greater $N$.
> 
> And N=2^{30} is the dictionary for 6 symbols of (0-9, a-z, A-Z) - absolutely reasonable value, that is definitely not extremely large.
> 
> Best regards, <>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 12 Jul 2016 07:28:08 +0300

Good morning, Mike!

Thank you very much for your comment - you're absolutely right, these are
tightly connected problems.

Maybe we'll be able to have some understanding in Berlin - I hope that
SeongHan and Kazukuni will participate in the discussion on PAKEs after my
talk on SESPAKE.

Kindest regards,
Stanislav

2016-07-11 21:53 GMT+03:00 Mike Hamburg <[email-masked]>:

> Hi Stanislav,
>
> That AugPAKE proof doesn’t work anyway, as I’ve pointed out here before.
> Specifically, Lemma 1 doesn’t hold even with the quadratic bound.  A
> legitimate server will compute:
>
> y random
> y~ = H~(y)
> K = g^y~
>
> The proof of Lemma 1 assumes that an adversary will also do this, and that
> (because of some random-oracle assumption on H~) that the challenger will
> therefore know y~.  Of course this isn’t true, because the adversary might
> have computed K as something other than g^y~.  For example, it might have
> used X in the calculation, where in the relevant game X is an unknown power
> of g.  This is where the q_hashH~ term comes from in Lemma 1.
>
> I asked the authors of the paper (both 辛星漢 and 古原和邦) about this last March
> .  They said they wanted some time to think about my comments, but they
> didn’t get back to me.
>
> Cheers,
> — Mike
>
> 2N^2\cdot q_{hashH} \cdot Succ^{1sdh}_{g,\mathbb{G}}(t + \tau_e).
>

---

From: 辛星漢 <[email-masked]>
Date: Tue, 12 Jul 2016 09:57:28 +0000

Dear Stanislav and Mike,

Thank you for your comments.

>They said they wanted some time to think about my comments, but they didn’t get back to me.

I'm so sorry and there is no excuse about this.

Regarding these comments, I hope to get back to you by mid September.

Sorry again and thank you in advance for your understanding.

Best regards,

Shin

________________________________
差出人: Stanislav V. Smyshlyaev <[email-masked]>
送信日時: 2016年7月12日 13:28
宛先: Mike Hamburg
CC: 辛星漢; [email-masked]; [email-masked]
件名: Re: [Cfrg] A problem with the security proof of AugPAKE?

Good morning, Mike!

Thank you very much for your comment - you're absolutely right, these are tightly connected problems.

Maybe we'll be able to have some understanding in Berlin - I hope that SeongHan and Kazukuni will participate in the discussion on PAKEs after my talk on SESPAKE.

Kindest regards,
Stanislav

2016-07-11 21:53 GMT+03:00 Mike Hamburg <[email-masked]<mailto:[email-masked]>>:
Hi Stanislav,

y random
y~ = H~(y)
K = g^y~

Cheers,
- Mike

On Jul 11, 2016, at 6:06 AM, Stanislav V. Smyshlyaev <[email-masked]<mailto:[email-masked]>> wrote:

If we look on the most significant part of the upper bound of adversary advantage (Theorem 1 in https://eprint.iacr.org/2010/334.pdf), we'll have the following:
\Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} + 2N^2\cdot q_{hashH} \cdot Succ^{1sdh}_{g,\mathbb{G}}(t + \tau_e).

Best regards,

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