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 > > >
- [Cfrg] A problem with the security proof of AugPA… Stanislav V. Smyshlyaev
- Re: [Cfrg] A problem with the security proof of A… 辛星漢
- Re: [Cfrg] A problem with the security proof of A… Stanislav V. Smyshlyaev
- Re: [Cfrg] A problem with the security proof of A… Mike Hamburg