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

Andrew Ayer <agwa@andrewayer.name> Tue, 11 August 2015 15:54 UTC

Return-Path: <agwa@andrewayer.name>
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 9785B1A89FA for <acme@ietfa.amsl.com>; Tue, 11 Aug 2015 08:54:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.002
X-Spam-Level:
X-Spam-Status: No, score=-2.002 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] 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 nj9wZGseqzC1 for <acme@ietfa.amsl.com>; Tue, 11 Aug 2015 08:54:48 -0700 (PDT)
Received: from alcazar.beanwood.com (alcazar.beanwood.com [IPv6:2600:3c00:e000:6c::1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C75C61A877E for <acme@ietf.org>; Tue, 11 Aug 2015 08:54:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=andrewayer.name; s=alcazar2; t=1439308487; bh=RuHyjywPPS/gPMDItl+E9Q92DHPMR3FpqU9pZvAJrbY=; h=Date:From:To:Subject; b=adJgVvkU04vvbYAjMWwQyjojrK0XoS7/t7tTcy4jqHOW/oJYS5FQIJ1BpM+cxrIl6 L7WW5tlKCq3EEZYx9D5ndfsSqrI6hCpK033p2+76wMtDqAlQSzCKGMmfrJLAVqk6ex V8q9UvyAI2dZ1bK5fDghU9+uOeeEslefwsxoHKKq4HUrAAbvuA0Ge9wgcC0jf2oV8i iAd7vXdPahigP+ZTiABg8NGEdREQkDh+50KII0kZjiUbLA4hXahXqpiiSVnjw9IRHY AJqfe8zJfK12SrFbX2sBQgWd11ev4g/yMmnc+T3AdiKdtBZhjoLJo2b6LqKeRo3NjV cTpdc+7ezryBA==
Date: Tue, 11 Aug 2015 08:52:05 -0700
From: Andrew Ayer <agwa@andrewayer.name>
To: acme@ietf.org
Message-Id: <20150811085205.bbcd37b3b0bb0482f6522b1a@andrewayer.name>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Archived-At: <http://mailarchive.ietf.org/arch/msg/acme/F71iz6qq1o_QPVhJCV4dqWf-4Yc>
Subject: [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: Tue, 11 Aug 2015 15:54:50 -0000

I recently reviewed draft-barnes-acme-04 and found vulnerabilities in
the DNS, DVSNI, and Simple HTTP challenges that would allow an attacker
to fraudulently complete these challenges.

I shall describe the DNS challenge vulnerability first, since it is the
most serious as it requires no MitM or other network-layer subversion.
The assumptions are:

1. The victim, example.com, has recently completed its own DNS
challenge, and the _acme-challenge.example.com. TXT record is still
provisioned in the DNS.

2. The victim uses an RSA account key.

3. The attacker has an account with an ACME server (not necessarily the
same server as the victim).

4. The attacker's account has a recovery key.

The attack is as follows:

1. The attacker creates an authorization object for example.com.
The server replies with a DNS challenge.

2. The attacker constructs an ordinary validation object in response to
the DNS challenge, but does not yet sign it or send it to the server.
Let m be the PKCS#1 v1.5 padded hash of this validation object (i.e. the
raw value which is signed by RSA).

3. The attacker queries the _acme-challenge.example.com. TXT record
to get the victim's signature.  Let s be this signature.

4. The attacker crafts an RSA key pair such that s is a valid signature
from this key for m.  The easiest way to do this is to set e = 1, d = 1,
and n = s - m.  This requires m < s, but since the first byte of PKCS#1
v1.5 padding is always zero, m < s will be true with very high
probability.

5. The attacker uses the account recovery process to replace its current
account key on the server with its new, specially-crafted key.

6. The attacker now sends its validation object, with s as its
signature, to the server.

7. The server validates the DNS challenge by following the 5 steps
specified in section 7.4.  In step 1, it verifies the signature on the
validation object using the attacker's account key.  RSA
signatures are verified by checking that:

	s^e mod n == m

Since e = 1, and n = s - m:

	s^1 mod (s - m) == m
	s mod (s - m) == m
	m == m

Step 1 passes.  Steps 2 and 3 pass because there's nothing out of the
ordinary about the validation object itself.  In steps 4 and 5, the
server queries the _acme-challenge.example.com. TXT record and compares
it against the validation object's signature, s.  Since they're the
same, the check passes and the validation is successful.

The attack against DVSNI is similar, except that the attacker can't simply
query a TXT record to get the signature; instead it must connect to a
TLS server and request a server name which it wouldn't know.  However,
an application-layer MitM on the victim's ACME channel (which is part
of ACME's threat model) would know the signature and be able to complete
the attack.

The attack against Simple HTTP is trickier, since instead of retrieving
just the signature over the validation channel, the entire validation
object is retrieved.  But the attacker can still craft an RSA key that
can fool the server into thinking that the victim's validation object
is signed by the attacker's key.  This works as long as the server
doesn't check that the public key in the validation object's JWS header
matches the account's public key.  The draft doesn't explicitly say to
check this.

Note that the attack I described above depends on the server's RSA
implementation not being too strict with keys and signatures.  The
attack fails if the RSA implementation checks for e = 1, or s > n.
However, there's no reason why an RSA implementation needs to do these
checks, since it really doesn't matter in normal RSA use.  For example,
Go's RSA implementation does not (see [1] for a proof-of-concept in
Go). Also, I only demonstrated the simplest way to craft an RSA key.
More generally, the attacker needs to find d, e, and n, such that m =
s^e mod n and d = e^-1 mod n.  That seems like a lot of leeway for the
attacker to pick a more convincing-looking RSA key, although I don't
have the number theory background to know for sure.  Also, I haven't
looked at ECDSA-specific attacks, or algorithm confusion attacks (where
the victim uses one type of key, and the attacker uses another).

The real problem is that ACME makes false assumptions about signatures.
It assumes that a signature uniquely identifies a (public key, message)
tuple, which RSA does not guarantee.  To fix this, I propose simply
publishing the authorized account public key (or a hash of it) in the
TXT record (for DNS challenges), in the TLS certificate (for DVSNI), or
in the file (for Simple HTTP).  Checking that the account public key is
present in a place that only the domain administrator controls should
be sufficient to establish that the domain authorizes that account
public key to issue DV certificates for it.  There is no need for
signatures, nor do I see any need for tokens.

Regards,
Andrew

[1] https://gist.github.com/AGWA/683a11e0b1c9ea20a62b