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

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> 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 <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
> https://www.irtf.org/mailman/listinfo/cfrg