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

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Tue, 12 July 2016 04:28 UTC

Return-Path: <smyshsv@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2B4FE12B046 for <cfrg@ietfa.amsl.com>; Mon, 11 Jul 2016 21:28:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 0Ac96mDExRv2 for <cfrg@ietfa.amsl.com>; Mon, 11 Jul 2016 21:28:09 -0700 (PDT)
Received: from mail-qk0-x22e.google.com (mail-qk0-x22e.google.com [IPv6:2607:f8b0:400d:c09::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 96809128E19 for <cfrg@irtf.org>; Mon, 11 Jul 2016 21:28:09 -0700 (PDT)
Received: by mail-qk0-x22e.google.com with SMTP id 82so3822661qko.3 for <cfrg@irtf.org>; Mon, 11 Jul 2016 21:28:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=7+7iv1oa4fuAHOii8a8Y0GYzQXBEFihUX4hM4dppx34=; b=sRVWf4UX9uEosxQAkL0pSf1Nr49YRQ96bRiwC/O+5tnzDdlM3piQkyA9X3QHTzQOtQ G/QzMEZ3aNgi8xsyeivusv4uttAKbzFJgy7a2RYo1BX5wMUk6L7LbyQt77KvnRLCAx85 02tH0E9mT6yzgcZ5cQ1qyYRdqDn4CglefYOgp097WBFKWhzlAzM38/G7hUnzRsL/SftL AWghEdC4NCOvWAxzNfwMCok30dShbVg5lK1zTdp3dnS6VNm1TfFi2CfhHDGbxy54ZYu9 mgTXyt1hS9GZOSIBjySFFW6fJvMbEx5CjiDKv0YCtr/pluwA984ESUbaZVxduICDr2/H rdbg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=7+7iv1oa4fuAHOii8a8Y0GYzQXBEFihUX4hM4dppx34=; b=arG2kttlo88lRoYNJDQKXz8rDDjdBQVgoxIF6NeMRnTMCYEXTHPFJ+4DMrfj+9Aaeb ftfB6LT5/zujseOKUSv7+2bt1ofxF+RBlWl00KLl9w0Ohant3P+i2gsr+mmIQ1vf0xVF ntPXFTAUK7LwPrgHa4H3vb+CevCqn9jJSv0do80jM2BhBU8z/nyWuqIVJOeQ6jp6YeeB eznwLu6TN+jfOuJPSZqewF7Ww7U5/U/uJwyTLaQeBUX/BEkG0scSXvyqBwHs87nlbShu +ThZTu+Xjai98L6Oi/II/u/cHcS+zFlNO3dn5vKS4X4TppX+7ZnCPKvp5D/i72cDW70k ARiQ==
X-Gm-Message-State: ALyK8tIHg9wHPzQ3daJ7eRepwj3HiO0lOuArk8ZZjrObhpZZ3iUwym8UWNBycfX+66uUcpYfJ4fbCSweie3ctA==
X-Received: by 10.55.3.143 with SMTP id 137mr248287qkd.154.1468297688712; Mon, 11 Jul 2016 21:28:08 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.200.50.86 with HTTP; Mon, 11 Jul 2016 21:28:08 -0700 (PDT)
In-Reply-To: <AE3E19B2-AF26-4289-902F-FB13D62412C9@shiftleft.org>
References: <CAMr0u6nZKKiikeD3r5zSVbqEac2DeNqs6CKjtkbMXTsSYR3Cnw@mail.gmail.com> <AE3E19B2-AF26-4289-902F-FB13D62412C9@shiftleft.org>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Tue, 12 Jul 2016 07:28:08 +0300
Message-ID: <CAMr0u6nTY0M92seecvs4Sks84ou89GE03fzKsJkyeBaceHd6AQ@mail.gmail.com>
To: Mike Hamburg <mike@shiftleft.org>
Content-Type: multipart/alternative; boundary="001a114c753c292a95053768b249"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/DuyAjRvjjfnameZMyfPFoofIbAg>
Resent-From: alias-bounces@ietf.org
Resent-To: <>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] A problem with the security proof of AugPAKE?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 12 Jul 2016 04:28:11 -0000

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>:

> 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), 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
>
>
>