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

From: Andrew Ayer <[email-masked]>
Date: Tue, 11 Aug 2015 08:52:05 -0700

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

---

From: Jacob Hoffman-Andrews <[email-masked]>
Date: Tue, 11 Aug 2015 22:50:27 -0700

This is an excellent find, thanks for spotting it and writing it up.

On 08/11/2015 08:52 AM, Andrew Ayer wrote:
> 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).
This seems like a good approach, though I think it's not compatible with
the new domain validation requirements being worked on at the CA/B
Forum: https://cabforum.org/pipermail/validation/2015-July/000080.html,
which require a random token. We could propose an addition to those
requirements, once we have concrete spec language in place.

The nice thing about publishing account keys is that they can remain
constant over time, which would in theory allow for significant changes
to the protocol. For instance, DVSNI, SimpleHTTP, and DNS challenges
could be specified as re-validateable on demand, and in practice a CA
could revalidate the relevant challenges immediately before issuance,
not just at authorization time.

That, in turn, would resolve some thorny problems people have raised
(https://github.com/letsencrypt/boulder/issues/572) about transferring
authorizations between account keys, and removing authorizations from
account keys. For instance, if we specify that
/.well-known/certificate/acme-account-keys.json on any given host should
contain a list of JWKs authorized to issue certificates, then
authorizing a new hosting provider to issue certificates would be as
simple as adding their account key to that file. The hosting provider
could even check for themselves that it's present before beginning an
interaction with the ACME server. Similarly, someone who leaves a
hosting provider would be able to remove that provider's key from the
relevant file to deauthorize them from issuing future certificates.

A similar system could apply with key hashes for DVSNI and DNS.

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Aug 2015 22:52:05 -0700

Hey Andrew,

Thanks for the really thoughtful analysis here.

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.

Smallest diff change from the current document would be simply to
explicitly require validation value bound to account key that created
it -- not the one the signs the response.  Since the attack requires
that the attacker change keys (using recovery) after receiving the
token, the attack only works if the validation is done against the new
public key.  This option introduces non-trivial implementation
complexity, though, since the server now has to remember what key
signed the new-authorization request that caused the challenges to be
issued.

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.

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

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.

--Richard

On Tue, Aug 11, 2015 at 8:52 AM, Andrew Ayer <[email-masked]> wrote:
> _______________________________________________
> Acme mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/acme

---

From: yan <[email-masked]>
Date: Wed, 12 Aug 2015 13:55:52 -0700

> signed the new-authorization request that caused the challenges to be

Doesn't it already have to remember this? The current instructions for 
verifying a DNS challenge says: "1. Verify the validation JWS using the 
account key for which this challenge was issued."

Since the challenge was issued before the attacker initiated account 
recovery to do the key change, the wording implies that the server 
remembers the original key at validation time.

---

From: Richard Barnes <[email-masked]>
Date: Wed, 12 Aug 2015 15:54:17 -0700

On Wed, Aug 12, 2015 at 1:55 PM, yan <[email-masked]> wrote:
> recovery to do the key change, the wording implies that the server remembers
> the original key at validation time.

Yeah, good point.  I still think that it would be better to simplify
things in the way Andrew suggested.

--Richard

---

From: Andrew Ayer <[email-masked]>
Date: Wed, 12 Aug 2015 16:04:05 -0700

On Tue, 11 Aug 2015 22:52:05 -0700

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

> shown with a signature, but with its being provisioned in a particular

Exactly.

> with (to prevent replay for different domains, or in different

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.

> and the "put it here" challenges can provision a digest of the

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

---

From: Andrew Ayer <[email-masked]>
Date: Wed, 12 Aug 2015 16:16:17 -0700

On Wed, 12 Aug 2015 13:55:52 -0700
yan <[email-masked]> wrote:

> > explicitly require validation value bound to account key that
> > created it -- not the one the signs the response.  Since the attack
> > requires that the attacker change keys (using recovery) after
> > receiving the token, the attack only works if the validation is
> > done against the new public key.  This option introduces
> > non-trivial implementation complexity, though, since the server now
> > has to remember what key signed the new-authorization request that
> > caused the challenges to be issued.
> 
> Doesn't it already have to remember this? The current instructions
> for verifying a DNS challenge says: "1. Verify the validation JWS
> using the account key for which this challenge was issued."
> 

That wording is bound to trip up implementers - in fact, a quick look
at the Boulder source indicates it validates against the current account
key, not the account key at the time the challenge was issued[1] :-)

I think this would be a pretty fragile way to work around what is
fundamentally a crypto problem.

Also, only DVSNI and DNS currently use this language - the wording for
the Simple HTTP challenge is "Verify that the body of the response is
[...] signed with the client's account key".  The wording should
probably be clarified and made consistent among the challenges.

Regards,
Andrew

[1]
https://github.com/letsencrypt/boulder/blob/7eae93873d394c359c371621c4e9064c9e780f19/va/validation-authority.go#L381,
which is ultimately called from
https://github.com/letsencrypt/boulder/blob/7eae93873d394c359c371621c4e9064c9e780f19/ra/registration-authority.go#L380,
where the account key comes from the registration object.

---

From: yan <[email-masked]>
Date: Wed, 12 Aug 2015 18:58:05 -0700

On 8/12/15 4:16 PM, Andrew Ayer wrote:
> key, not the account key at the time the challenge was issued[1]

Consider us tripped. :)

> fundamentally a crypto problem.

Agree, I like Barnes' proposal above.

> probably be clarified and made consistent among the challenges.

I see James is already fixing this: 
https://github.com/letsencrypt/acme-spec/pull/217/files.

Thanks,
Yan

---

From: Richard Barnes <[email-masked]>
Date: Wed, 12 Aug 2015 22:21:25 -0700

> commonly-used curves (P-256, P-384, and so on) specify a fixed base

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

---

From: Eric Mill <[email-masked]>
Date: Thu, 13 Aug 2015 01:30:22 -0400

> hand, Jacob's /.well-known/certificate/acme-account-keys.json idea is

This is only tangentially on-topic, but since the idea's been reinforced,
just a note that some deployment setups will find it challenging to deploy
and maintain special content at HTTP URIs that aren't part of the app's
business logic. I'm thinking of platform-as-a-service hosts like Heroku or
Cloud Foundry, which map hostnames entirely to "apps" (often with a code
repository as the sole content source for URIs).

Right now, /.well-known is only used for the Simple HTTP validation
mechanism, where the ability to put special metadata at HTTP URIs within
the validated hostname is already a prerequisite. Making that ability a
requirement for the overall ACME protocol would add friction for a class of
users.

-- Eric

-- 
konklone.com | @konklone <https://twitter.com/konklone>

---

From: Richard Barnes <[email-masked]>
Date: Wed, 12 Aug 2015 22:42:15 -0700

On Wed, Aug 12, 2015 at 10:30 PM, Eric Mill <[email-masked]> wrote:
> mechanism, where the ability to put special metadata at HTTP URIs within the
> validated hostname is already a prerequisite. Making that ability a

Different environments are going to be able to do different
challenges.  That's why it's important to have multiple of them.

Just to pick two examples off the top of my head, Cloudflare typically
controls DNS, so DNS-based challenges will be easy for them.  Akamai
typically doesn't, so they might want to do an HTTP-based challenge.

> konklone.com | @konklone

---

From: Eric Mill <[email-masked]>
Date: Thu, 13 Aug 2015 02:06:17 -0400

On Thu, Aug 13, 2015 at 1:42 AM, Richard Barnes <[email-masked]> wrote:

> the

Yep, I get that. I might be misreading it, but it looked like the
suggestion of a /.well-known URI for account keys would impact all ACME
users, not just those using Simple HTTP validation.

-- Eric

---

From: Rob Stradling <[email-masked]>
Date: Thu, 13 Aug 2015 10:40:51 +0100

On 13/08/15 02:58, yan wrote:
<snip>
> https://github.com/letsencrypt/acme-spec/pull/217/files.

Shouldn't that work be happening at...

https://github.com/ietf-wg-acme/acme

...now?

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 13 Aug 2015 11:05:32 +0100

> be prevented by checks on account public keys.

I know you're not suggesting we do, but depending on special values
or patterns for keys would be risky. I think it has often turned out
that application developers are unaware of the details of what their
crypto libraries do or do not support at that level. So it could be
quite easy to recommend something that'd fall between the cracks.

Cheers,
S.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 13 Aug 2015 10:27:09 -0400

+1

I would much rather block the entire class of attacks rather than spend any
time working out if there is a way to do this with ECC based keys.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 13 Aug 2015 17:51:55 +0300

> time working out if there is a way to do this with ECC based keys.

FYI, one of the five proposals for CFRG signatures:
- One is definitely vulernable (and key-checking won't help).
- Two are definitely not vulernable.
- Two I don't know.

So good idea to just block the attack.

-Ilari

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 13 Aug 2015 11:00:31 -0400

> So good idea to just block the attack.

I hadn't actually thought of using this as a discrimination function on the
CFRG algorithms. It is as good as anything else.

---

From: Richard Barnes <[email-masked]>
Date: Thu, 13 Aug 2015 08:01:07 -0700

> https://github.com/ietf-wg-acme/acme

Yes, thanks for pointing that out.  I have closed that PR.

To be clear: The "letsencrypt/acme-spec" repo is still open for the
moment, but at this point, the only changes being accepted are minor
clarifications or critical fixes.  (Once Let's Encrypt gets stable, I
expect that repo to close down and any deltas against -04 to be
proposed against the IETF document.)  Since there's an
implementation-side fix for this issue (using the proper account key),
this is not a critical fix.

Anything novel needs to be discussed on this list and done in the IETF
repo, as you note.

--Richard

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 13 Aug 2015 17:41:41 +0200

> CFRG algorithms. It is as good as anything else.

This is not a good discriminator of the CFRG options -- this problem is
a weakness in this protocol, and should be addressed here.

/Simon

---

From: Jacob Hoffman-Andrews <[email-masked]>
Date: Thu, 13 Aug 2015 10:24:58 -0700

> suggestion of a /.well-known URI for account keys would impact all
> ACME users, not just those using Simple HTTP validation.
I didn't fully expand the idea, but my assumption was that similar
continuous publication techniques could apply to other challenge types.
For instance, DVSNI could involve answering for a
<identifier>.acme.invalid at any time with a test certificate embedding
a list of account keys or account key hashes in some format. Similarly,
one could publish a list of account key hashes in DNS.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 13 Aug 2015 12:17:11 -0700

> a weakness in this protocol, and should be addressed here.

I'd agree, this is a conceptual misuse of digital signatures. While
creating a signature algorithm resistant to this is a "neat trick" much
like nonce reuse resistant AEAD schemes, you shouldn't design protocols
that rely on that resistance in either case.

-- 
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 13 Aug 2015 18:11:29 -0400

> that rely on that resistance in either case.

Old style crypto was to choose between a belt and braces.

New style is to take the belt and the braces and sew the pants to the
bottom of the shirt.

People need to change their attitudes. We are designing building blocks
that are going to be used by pin heads as well as geniuses. And on occasion
the genius is going to build something on a bad day. The harder it is to
screw up, the better.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 13 Aug 2015 15:17:08 -0700

On Thu, Aug 13, 2015 at 3:11 PM, Phillip Hallam-Baker <[email-masked]

>> that rely on that resistance in either case.
[...] People need to change their attitudes. We are designing building
> blocks that are going to be used by pin heads as well as geniuses. And on
> occasion the genius is going to build something on a bad day. The harder it
> is to screw up, the better.
>

In case I was unclear, I support the creation of schemes that take the
sharp edges off, hence the hat tip to nonce reuse-resistant AEAD. In fact I
have participated in the development of and tried to popularize libraries
that try to remove as many sharp edges as possible, such as libsodium.

The caveat I gave was that protocol designers shouldn't assume those sharp
edges aren't present. I think you'll find most digital signature algorithms
break under the assumption that two keys can't produce the same digital
signature.

-- 
Tony Arcieri

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 14 Aug 2015 00:42:06 +0200

> The caveat I gave was that protocol designers shouldn't assume those
> sharp edges aren't present. I think you'll find most digital
> signature algorithms break under the assumption that two keys can't
> produce the same digital signature.

Exactly -- there is no cryptographic requirement on a public-key
signature system that the above property holds.  Protocol designers
using crypto primitives should only require the properties that are
actually promised.  Further, before using any non-standard property,
you should demand that there is a security proof reducing that property
into a common computational problem that people believe is difficult to
solve.

/Simon

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 13 Aug 2015 19:18:59 -0400

> into a common computational problem that people believe is difficult to

Yep, I certainly don't advise anyone relying on the signature scheme not
resisting this sort of thing. If has to be belt and braces.