Here's another attack scenario to think about.

Consider the original protocol: server sends a t-bit nonce N, client signs it.

Suppose that Eve can passively observe Alice's authentications to Bob's server, but she can't actively MitM the connection. Her best generic attack is a birthday attack:

1. Eve observes 2^b authentications and remembers each (N, S(N)) pair.

2. Eve attempts to authenticate as Alice. If Bob sends an N she has seen before, she's in. If he sends a fresh N, she aborts and tries again.

Eve will succeed in step 2 after roughly 2^(t-b) attempts.

Now consider the amended protocol. In each authentication, Eve observes two signatures: S(R) and S(R^N). Each is a signature over what is essentially a random t-bit number. This allows Eve to improve her attack:

1. Eve observes 2^b authentications. She stores two (X, S(X)) pairs per authentication: one for X = R and one for X = R^N. The size of the set is 2^(b+1).

2. Eve attempts to authenticate as Alice. Bob sends N. For each X in her set of observations, Eve calculates X' = X^N. If X' is also in the set, Eve wins. If not, she aborts and tries again.

Notice that Eve is now colliding N with the set of (X, X') pairs. Since this set grows with the square of Alice's authentication attempts, Eve will succeed after roughly 2^(t-2(b+1)) attempts.

This attack is plausible for sufficiently small t (say, 64) and sufficiently large b (say, 16-20). While b will be very small in web login scenarios, large b may be plausible in automated authentication scenarios.

This can obviously be defeated by choosing a sufficiently large t.

EDIT: (I'm not 100% certain about all the math. Corrections are welcome.)

That's a very cool attack. However, the client can sign R and R^N together, which I think defeats it. I didn't describe it as such because I was afraid "S(R+R^N)" may cause some confusion, and I ran some numbers and found the security level acceptable for 128-bit nonces and a few billion logins.

The scheme you outline still allows trivial impersonation attacks.

Care to provide an example?

And keep in mind this is not a complete authentication protocol. I'm just proposing a small change to fix the signing-not-random-nonce problem, so I assume the rest of the protocol context is kept.

Barring stupid mistakes from my part, if this is vulnerable to impersonation so is the article's.

Alice is an end user. Eve and Bob each host legitimate servers. Alice authenticates to Eve, and Eve impersonates Alice to Bob like so:

    A        E        B
     -hello->
              -hello->
              <-nonce-
     <-nonce-

     -random->
     -S(rand)>
     -S(n^r)->
              -random->
              -S(rand)>
              -S(n^r)->

If Alice doesn't validate the identity of the server, that's absolutely a legitimate attack. But building a secure channel is out of scope and assumed solved here. The problem is how can Alice authenticate to Bob without exposing herself to signing arbitrary documents.

(nice diagram, by the way)

To be clear, Alice is intentionally authenticating to Eve in this scenario. So a secure channel does not impede the attack. For example, suppose Eve is Facebook and Bob is Google. Alice logs into Facebook, but what she doesn't know is that Facebook is passing her signatures directly through to Google. Now Mark Zuckerberg can like YouTube videos on Alice's behalf.

To prevent this, Alice must also sign the domain she's authenticating to. The article mentioned this, and maybe you had meant it to be implicit in your protocol, in which case: my bad.

I totally overlooked that, thank you for pointing out. Thankfully the fix is simple. I've updated the original post.

Well, yeah, but as BoppreH said, that's still present in the original article's design. What BoppreH's solution doesn't allow (which is the problem the article raises) is the tricking of Alice into signing arbitrary data.

Imagine that the "check" protocol has a similar requirement: that the client xor the check with their own random value. Now we have the same problem again, as your signed message looks just like a valid check. You can make the attack increasingly unlikely by mutating your protocol in ways that you don't expect any other protocol also does, but this seems like security by obscurity unless done as part of an agreed standard which other protocol authors follow.

If the "check" protocol works like this, yes, we have a problem. But I think there are two very distinct types of "signatures" here: binding statements and proofs of possession. Because the client nonce was explicitly added so we don't sign intelligible data during proof of possession, I don't see why the "check" protocol, which is a binding statement, would have a similar requirement.

I think that if your safety is based on "I don't think someone else would design a protocol like that", it seems pretty weak.

I agree completely. But it's an improvement, which shows how bad the current state is, and strictly better than relying on just standardization or caution.

(By the way, if you still think it's broken, I'm ball to improve it. "Wrestling with pig"...)

Sure, as I said, any change to the protocol that "seems unlikely" to collide with any other protocol makes an attack less likely. But I think an easier way to accomplish that, compared to your proposal, would be to add a context string prefix. E.g. require the signed message starts with "RFC 123456 authentication protocol\0" or something. The article has a link to Adam Langley suggesting this for some uses of signatures in TLS. In comparison, the client-chosen XOR introduces a construct that seems like it could have subtle cryptographic implications, so seems riskier.

Of course, the context string is also vulnerable to, say, a colliding protocol that happens to ignore leading strings (which is not unheard of). So ideally you specify that "this key shall only sign messages that begin with a context string", and then you're pretty solid. This is effectively saying "the type of things signed by this key are arbitrarily-typed messages prefixed with a NUL-terminated human-readable string identifying their type", which satisfies my "only sign unambiguously-typed data" rule. :)

(If you're referring to my edit earlier: I had previously thought I saw an attack that wasn't there, and had noticed other people claiming brokenness, so I assumed they were pointing it out. But then I realized the problem I imagined wasn't there. Sorry about that.)

To make it a little more fixed-size and built of known primitives, what about just signing a mutated hash of the content a la HMAC?

Like this?

    Server: server_nonce
    Client: random_key + sign(hmac(server_nonce, random_key))

That's a nice alternative. Though generating random data and XOR'ing is as known and as primitive as you can get, and none of it is ever reused, so I have no preferences of one over the other.

(if you are thinking "why not just sign the hash of the nonce without bothering with a key?", that's exactly how we sign documents, because they are long. You could sign the hash of the hash to avoid this conflict, but that's a hack)