# Digital signature for an expiring password

I would like to create a publicly available tool that is used to generate a password that gives a limited time access to a resource.

My idea is to digitally sign the current date with a private key entered by the user, generating a message that is sent to the resource that verifies it with the public key. If valid, the access is granted if the date matches the current date. The only secret element is the private key.

My constraints are:

• as the private key has to be memorized and typed, it should remain short (10 characters)
• the generated message should be as short as possible, to be manually typed

What is the best security level that can be reached with these constraints? What algorithm can be used?

-
There are no secure public-key schemes with a private key typical humans can memorize. Could you use a shared-key scheme, i.e. where the resource knows the same "password"? –  Paŭlo Ebermann Apr 30 '12 at 23:24
@diskograf: Can you clarify if the (server doing access control for the) resource can be assumed to maintain confidentiality of access control data that it holds during (a) user enrollment (b) access control? –  fgrieu May 1 '12 at 8:59
@PaŭloEbermann: I see no curse making it harder to have a short private key in a public-key cryptosystem than it is to have a short key in a secret-key cryptosystem. E.g. expand 10-characters private key using Scrypt (salt = user ID, 10 second computation) to get the 256-bit seed of a CSPRNG, used to deterministically generate a big RSA key pair; store the public key as usual, reconstruct the RSA private key when needed, from the short private key. If that has 40 bits of entropy, this scheme is solid (hundreds thousands CPU.years to attack). –  fgrieu May 1 '12 at 9:12
@PaŭloEbermann: the resource is also distributed and someone could find that symmetric key and use it to sign. I think it also answers the question of fgrieu. –  diskograf May 1 '12 at 13:47
@fgrieu: I'm not strong enough to understand your comment. If I look at the problem naively, a humanely memorable password (like 10 characters) is enough for granting a temporary access. It is not different than the password I use for my web mail. The only difference is that with that password I'm generating a different token each time I use it, so if it is seen or intercepted, it will be useless in a short time. –  diskograf May 1 '12 at 13:57
show 1 more comment

So, let's see if we can build something from the ideas in the question and the ones collected in the comments.

While the plain keys for asymmetric signature schemes need to be quite long (longer than normal humans can memorize), creating an asymmetric key pair from a password is doable [as pointed out by fgrieu in a comment]. Here is what Alice (or some program in her control) would do when first signing up:

• Alice feeds the password and some other data, like her user ID (what Alice uses to login), system ID (an identifier for the server/system/...), system parameters, maybe some random salt from the user database, etc. as input to a key derivation function like PBKDF-2, bcrypt or scrypt, with suitable work factor so this takes as long as Alice is normally ready to wait whenever giving out a new authorization (this might be 10 seconds, for example), and obtain a 256-bit number $s$.

• Alice uses this number $s$ as the seed to some (deterministic) cryptographically secure random number generator.

• Alice uses the generator to generate a key pair. The exact procedure will depend on the algorithm in use - for RSA, Alice would generate two numbers $p$ and $q$, and check them for primeness (using more random numbers from the same generator) - if one of them turns out not to be prime, repeat. Then Alice creates their key pair from these in the normal way. (There are known standards for this, this is just a sketch.) For (EC)DSA or ElGamal, she just takes some random number $x$ from the generator, and calculates the public key $y = g^x$ in the group in use - nothing more to do.

• She now gives the public key from this key pair to Bob (Bob is the "resource administrator" here.)

The private key will not be stored anywhere - whenever Alice needs it (e.g. to create a token), she will do this whole procedure again.

As all inputs are fixed and everything is deterministic, the key pair will only depend on the password (and Alice's user ID, so other users will have other key pairs).

How to create the token:

To generate a token, Alice takes all the necessary data together:

• Alice's user ID
• the ID $X$ of the resource which is to be accessed
• Some form of the validity time (could be the current date in the simplest form)

Hash these together, and sign it with the private key (recreated from the password as above).

Now encode enough of the information mentioned before (the user ID could be enough) together with the signature in a token, and hand this token to Charles.

Charles takes the token, and shows it to Bob to access some resource $X$.

How to check the token:

Bob gets the token (and the resource ID $X$), extracts the user ID, and looks up the Alice's public key (and checks if she is actually permitted to access the resource, and to authorize such access to others).

Then Bob hashes together the user ID, the resource ID $X$ and the current date. Then he checks (with Alice's public key) if the signature is a valid signature for this message, and only then allows Charles access to $X$.

This scheme is extensible to other validity time spans - either encode the validity date into the token, too, or let Bob check the last some days as input.

-
Great response, every step makes sense and I would accept it immediately if I was able to fully understand it. I will work on it and come back to you. The creation of the asymmetric key pair seems the most complex part. I have to end up with a concrete implementation, reusing as much standard tools as possible. –  diskograf May 1 '12 at 22:51