Re: [Acme] Signature misuse vulnerability in draft-barnes-acme-04

Richard Barnes <rlb@ipv.sx> Thu, 13 August 2015 05:21 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: acme@ietfa.amsl.com
Delivered-To: acme@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 769C91B2A7B for <acme@ietfa.amsl.com>; Wed, 12 Aug 2015 22:21:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.978
X-Spam-Level:
X-Spam-Status: No, score=-1.978 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
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 RAhxlFJnXCXy for <acme@ietfa.amsl.com>; Wed, 12 Aug 2015 22:21:27 -0700 (PDT)
Received: from mail-vk0-f42.google.com (mail-vk0-f42.google.com [209.85.213.42]) (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 8E8591B2A78 for <acme@ietf.org>; Wed, 12 Aug 2015 22:21:26 -0700 (PDT)
Received: by vkhl6 with SMTP id l6so13751159vkh.1 for <acme@ietf.org>; Wed, 12 Aug 2015 22:21:25 -0700 (PDT)
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:date :message-id:subject:from:to:cc:content-type; bh=hpsmWXlG2G0f5oKumduStHlKS8/eziGyHmQ5fq4YXVA=; b=CC3wTpxAXr2AoGXKY5EwI1uJziO2R7gl6aPN3wR34zGQxST3WE9ynlLqW5GnAs98Kh fLMe31kBFsjNvPYw7Z7PiKwmBDcbzX09vEbaGt0n6qBZvLxm/ZqBJCNRoEqE3gF+TZ83 OkX+rjI9tmLa6BKi7HkgRLA+IIQv42k8c7zuL+leKoT7AhVqeDhVSRSVE7mukC9M1/kr nzV+9rTNWs5dQYo5/L2sTUBDpNUfr9Ur+xkDqN6BmuvmyJQgz8ee3ONI6sLibZwQ91TG WStrWRqxghCrQv5/3m7UmjuxYbd2aDHyfwS9u0ekaX4Rz6w7w9e3xlD3uHc1iCWfGaM8 yDVQ==
X-Gm-Message-State: ALoCoQlQctxTRa7QOkXl+kJdblo4Lydj4uhOUR5/DbAYb4dqyqq8Ht7epF0UovSOVZ4w5BjZEsSP
MIME-Version: 1.0
X-Received: by 10.53.6.38 with SMTP id cr6mr46414244vdd.54.1439443285694; Wed, 12 Aug 2015 22:21:25 -0700 (PDT)
Received: by 10.31.164.207 with HTTP; Wed, 12 Aug 2015 22:21:25 -0700 (PDT)
In-Reply-To: <20150812160405.b824b673ad9b139a4fd9446f@andrewayer.name>
References: <20150811085205.bbcd37b3b0bb0482f6522b1a@andrewayer.name> <CAL02cgRf2M0Gkqymif-=rmNG0v9hhaMC2SBiXf-n5aYiRKBnmQ@mail.gmail.com> <20150812160405.b824b673ad9b139a4fd9446f@andrewayer.name>
Date: Wed, 12 Aug 2015 22:21:25 -0700
Message-ID: <CAL02cgReCTMZ+ECiZVtv2=sNDng3mvEmGv4w6V_REbZ6xf75dw@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
To: Andrew Ayer <agwa@andrewayer.name>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/acme/ZLF76nhWEIirHaRrIxJVSGhhEhU>
Cc: "acme@ietf.org" <acme@ietf.org>
Subject: Re: [Acme] Signature misuse vulnerability in draft-barnes-acme-04
X-BeenThere: acme@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Automated Certificate Management Environment <acme.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/acme>, <mailto:acme-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/acme/>
List-Post: <mailto:acme@ietf.org>
List-Help: <mailto:acme-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/acme>, <mailto:acme-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 13 Aug 2015 05:21:29 -0000

On Wed, Aug 12, 2015 at 4:04 PM, Andrew Ayer <agwa@andrewayer.name>; wrote:
> On Tue, 11 Aug 2015 22:52:05 -0700
> Richard Barnes <rlb@ipv.sx>; wrote:
>
>> I'm not 100% sure I agree that there are non-trivial cases where RSA
>> allows one to find a key that will verify a given (message, signature)
>> pair.  (I would note, however, that you don't even need to find the
>> modular inverse d of e -- you just need n and e such that s^e == m mod
>> n.)  It's even less clear for ECDSA.  I'm not sure we even need to get
>> a clear answer to that question, though.  There are protocol ways to
>> hack around it, as you suggest.
>
> Thanks to Trevor Perrin, I now know that this attack is called
> "duplicate-signature key selection," and found a paper which presents
> a general way to construct a non-trivial RSA key (pages 4-5):
>
> http://eprint.iacr.org/2011/343
>
> It also presents an attack with ECDSA, though it depends on the
> attacker picking their own base point, and I believe that the
> commonly-used curves (P-256, P-384, and so on) specify a fixed base
> point.

Nice find!  (Thanks, Trevor!)

I would note, though that in practice, e=65537 pretty much always, and
the attack would almost never produce that value.  So this could still
be prevented by checks on account public keys.

Still doesn't change the conclusion, though :)

--Richard


>
>> I think you're on the right track that we really should just not use
>> signatures here.  I had added those in response to concerns about a
>> CDNs in front of the ACME server, but in retrospect, they're solving
>> the wrong problem.  The risk posed by a CDN is that it swaps the keys
>> out, much like this situation.  So it's enough for the statement by
>> the domain owner (i.e., the validation object) to include an
>> indication of which account key he intends to authorize.
>>
>> This actually adds some symmetry to the challenges.  I had thought
>> that proofOfPossession seemed like the odd one out, since the account
>> key was being signed instead of doing the signing.  Your observation
>> that the domain holder needs to assert the key basically says that the
>> other challenges should follow the proofOfPossession model and have
>> the domian owner make a statement about the account key.  It's just
>> that in the other cases, the authenticity of the statement won't be
>> shown with a signature, but with its being provisioned in a particular
>> place.
>
> Exactly.
>
>> We will probably want to bind some more stuff into the validation
>> object besides the public key, though, in order to bound replay
>> opportunities.  At the very least, there needs to be a token that the
>> CA can use to associate the validation object with things like which
>> identifier is being authorized, and what type of challenge it goes
>> with (to prevent replay for different domains, or in different
>> channels).
>
> I may be overlooking something, but I'm skeptical of the value of
> including extra information.  If an attacker can replay a validation
> object for another domain or in the context of a different challenge,
> that means the attacker effectively controls that domain/validation
> channel, and can just contact the ACME server, start a new challenge,
> and complete it "normally" without any need for replays.
>
>> In light of the above, ISTM that the right tactical move is probably
>> to define a standard validation object that many challenges can use.
>> Then the proofOfPossession challenge can sign the validation object,
>> and the "put it here" challenges can provision a digest of the
>> validation object.
>
> That seems like a great way to simplify the protocol.  On the other
> hand, Jacob's /.well-known/certificate/acme-account-keys.json idea is
> also quite nice.
>
> Regards,
> Andrew