I have 2-factor authentication enabled on my gmail account, which means I have a little app on my cell phone that produces a new number every 30 seconds, and if Google gets suspicious of my login, they ask for the number currently displayed by that app.
If I understand it correctly, it works because Google and I have a shared secret number, and from that number, and the number of 30 second periods that have elapsed, we can both determine the next number in the sequence. The sequence is designed so that observing the created numbers does not give enough information to easily infer the shared secret.
I was wondering if there was a way to do this kind of authentication without requiring a shared secret at all, in a public-key-authentication style. I would produce a the same sequence for all entities that I was authenticating with, using some random seed, but instead of sharing that random seed with Google, I would give them some other seed, with which they could create another sequence. At any time they could verify some well known mathematical relationship between my number and theirs, which would serve to authenticate myself, but I’d never be giving them enough information to create my sequence themselves. And it would also preserve the property that observing the numbers themselves wouldn’t enable you to infer either seed.
Is there a sequence-generating method that makes that viable?
So, you’d like to do a public/private key pairing with the current time (however that’s expressed) factored in with a one-way function (function input can never be determined from function output, even if the exact function is known)?
The problem with one-way functions is that they can only determine if an unencrypted input will match against stored, encrypted value, after the input is encrypted (you could store the password in the clear, but that’s VERY unsafe). Since public/private key pairs do NOT match, there’s really no way to encrypt one and determine if it matches.
You can’t use the same mathematical operation on the encrypted values because encrypting the result of x+y yields a completely different result than encrypting x, encrypting y and adding those them together. This is partly an innate function of the encryption functions, and partly a desirable trait in encryption schemes (any uniformity in encrypted output can be used to eventually break the encryption).
One cryptographer has written a paper about a formula he’s come up with that allows mathematical operations on encrypted values to produce the same result as the encrypted result of that same operation. But that’s still an abstract theory and not likely to see implementation for several years yet.
You have a secret and public key pair. Google knows your public key. They use it to encrypt a random message, that only you can decrypt (with your secret key). You then send back their random message, thus confirming it’s you.
To add another layer, Google could keep their own key pair, that they use only with you. Instead of sending the random message back unencrypted, you could send it back encrypted so that only Google could decrypt it.
I’ve been thinking about this overnight, and think I can express it clearer:
Basically the current Google authenticator uses three functions:
[ul]
[li]GenerateOtherSecret(secret):number – Given your secret value, generate the other guy’s secret value.[/li][li]CreateIterate(secret, time):number – creates the number for a given time.[/li][li]Corresponds(number1, number2):Boolean – tells if a number provided for authentication corresponds to the local number.[/li][/ul]
The process is that I create a random secret, call GenerateOtherSecret on it, and send the result to Google. At any time, Google and I can both call CreateIterate() with our corresponding secrets and the current time, swap the outputs, and we can each verify that Corresponds returns true when passed both our numbers. I.e.
Corresponds(CreateIterate(GenerateOtherSecret(x), t), CreateIterate(x, t)) == True for all x, t.
In the current implementation, GenerateOtherSecret is an identity function, and Corresponds is just an equality test (while GenerateIterate is hard to invert). I’m wondering if they could be replaced with “hard to invert” functions in some scheme.
That way if someone steals Google’s data, they can pretend to be Google just fine, but can’t pretend to be me.
I guess implicitly I would like the system to work like the current authenticator does, with one way authentication being possible with only one message passed. Of course there are better ways to do authentication if we permit two-way communication at authentication time.
Hmm. There’s probably a way to do a one-way authentication using digital signatures, but I’m not familiar enough with how they work to know for sure. For example, one could sign a standard message with a time-date stamp, which could be used to verify that it’s you who’s trying to do something at particular time.
