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

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 <smyshsv@gmail.com>
送信日時: 2016年7月12日 13:28
宛先: Mike Hamburg
CC: 辛星漢; cfrg@irtf.org; mike.scott@miracl.com
件名: 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 <mike@shiftleft.org<mailto:mike@shiftleft.org>>:
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 <smyshsv@gmail.com<mailto:smyshsv@gmail.com>> wrote:

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

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org<mailto:Cfrg@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg