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

[Richard Barnes <[e-mail]>]

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 <[e-mail]> wrote:
> 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
>
> _______________________________________________
> Acme mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/acme