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