User generates a public and private keypair. The public key is given to the remote site (such as LoL or Linkedin), but the public key is not secret -- it is public. You can post it on your blog, whatever. You can use it for multiple accounts without concern.
The public key allows one to encrypt some data, but the public key cannot decrypt the data.
The private key can decrypt the data.
When the user wishes to log in the remote site, using the public key, encrypts a random string and sends it to the user. If the user manages to successfully decrypt this random string and send it back then the remote site can infer that the user holds the private key -- because only the private key can perform the decryption.
The private key is never sent to a remote party. Only meaningless random strings are communicated over the wire.
The (significant) drawback to this method is that the user will have to have the private key with them in order to perform the authentication. But perhaps mobile devices will solve that problem for us.
The biggest problem is it is so user unfriendly.
Mozillas new BrowserID scheme is pretty similar to this too.
A decentralized key system as ssh provides is much more appropriate for end users.
In fact, I can't think of any VPN I've ever connected to that didn't require a machine certificate. Cisco VPNs I've used require it, as does my own personal VPN.
Apparently it's quite tricky to implement properly though.
(I don't see how there's any possible protocol that behaves otherwise: if Alice is capable of proving she possesses a secret to Bob through a protocol, then Bob can always discover Alice's secret by playing that protocol with himself, enumerating every possible secret until the protocol succeeds. And so can anyone who knows everything that Bob knows about Alice's secret.)
The SRP paper doesn't say much about this except that brute-force dictionary attacks are "expensive". I don't think they make specific claims about computational hardness like scrypt. The paper was written in 1997.
"An attacker who captures the host's password file cannot directly compromise user-to-host authentication and gain access to the host without an expensive dictionary search."
Maybe some day there will be "Security as a Service" where someone helps you do this properly.
The first can be done if people would bother to learn and completely understand what they're doing (this thread and the corrections I've had to make seems to prove that people think they know what they're doing when they don't).
The second, have fun with.
The third is already solved. oAuth, OpenID, Facebook Connect, Twitter, BrowserID, etc.
The reason they're uncrackable is because when using bcrypt it takes a second or more to generate a hash for a password (compared to 0.000001 seconds for md5) meaning if they want to try and brute force the password or build a rainbow table it'll take them years instead of seconds to crack each password.
There's no need to remote password storage, they just need to learn more about password security.
It'd be nice if everyone who runs a non-trivial website stayed was a security expert, but we're also busy with other aspects of the site.