A "good enough" digital signature, with short key

Question

In my application, I want to hide debug feature behind a password. I don't want the password to be easily known by issuing strings executable, so I want to rely on digital signature.

We want Debbie to be able to debug the program.

The main scheme is:

1. Give the private RSA key to Debbie, put public RSA key in the program.
2. Give a random number sig to Debbie and put it in the program.
3. Debbie will "encrypt" sig with the private key, and access the debug features through the url /debug/<base64_encoded_encrypted_sig>
4. The software will verify that "decrypting" the number Debbie wrote in the URL, gives sig, and then allow access to debug features.

Why do I use plain RSA and not a known signature standard (such as PGP etc)?

The reason is, a typical signature is too long. Even 256 bits is long, and looks like that:

RS69BdGmd7330TNZU0Wk46VbTHvGLE46hIiy2ecHFX4T

So my question is, is my scheme secure enough?

update: even 256 bits keys are trivial to factor, so the answer is probably, this is not the way to go.

Answer 1

No scheme like this one will prevent a determined attacker from activating the "debug feature", by the simple expedient of reverse engineering the code to locate the part which, in the software code, will look like:

if (is_good_password(password)) {
    activate_debug();
}

and turn it into:

if (true) {
    activate_debug();
}

which is usually only a matter of turning a conditional jump into an unconditional jump, or an unconditional non-jump (i.e. a nop opcode). It is not even hard to do, even in big pieces of software (e.g. I did it once for Windows 2000, to allow for testing a custom CSP -- CSP must be signed, and the Microsoft-provided solution for deactivating the signature verification on development platforms was good only up to Win2k SP2, or WinXP, while I had a Win2k SP4; so I had to hack into the advapi32.dll, which took me 3 hours).

That being said, if you just want to verify a password, the easy way is to store in your software a password-verification token, i.e. a hash value computed over the password. No need to bring the whole paraphernalia of digital signatures ! Just a simple hash, and this can accommodate passwords of any length. The software embeds the hash value; when the "debug" URL is entered, it hashes the part after the "debug/" and sees if it matches the recorded hash value. Thus, the password does not appear in the software code itself (neither in cleartext, or merely "scrambled"), and you can use a "password" short enough to be typed.

Digital signatures are any good here only if you have an unbounded number of "Debbies", and you want to be able to give a "debug password" to each Debbie, so that each Debbie has her own password distinct from the passwords given to the other Debbies, and you want to make it impossible for an evil Debbie, regardless of how much reverse engineering she does, to recompute the other passwords from the one she already has (if you have only, say, 20 Debbies, you can just include 20 hash values in your code; by "unbounded" I mean "potentially millions"). This is a pretty specific scenario. An example is "product keys" -- digital signatures could theoretically thwart product-key-generators. Nevertheless, the strongest digital signature will do no better than a password hash against an attacker who does a few hours of reverse engineering on the code to locate the right conditional jump opcode. The signature would not protect against illicit access to the debug code; it protects only against extending an illicit access to an industrial scale, giving it to many other customers without requiring a local modification of the code -- a so-called "hack".

---

For the hash function, if in doubt, use SHA-256 -- if (and only if) the "password" is long and random enough (say 128 random bits). If the Debbie is allowed to choose a "meaningful" password (one that a human being will be able to remember, as opposed to have it written down on a piece of paper), then you should use a hash function which resists dictionary attacks, e.g. PBKDF2 or bcrypt.

Do not use the "encrypt with the private key" way of describing a signature; it is a terrible explanation, which does not work for all signature algorithms. It is just an historical way with which RSA was first presented, but even for RSA it is wrong: it does not take padding into account, and padding is essential for security (see PKCS#1). Just forget it. There is nothing wrong in "using the private key to sign some data" and "using the public key to verify some data".

Answer 2

Factoring a 74 bit rsa key can be done with wolfram alpha, 256 bits usually takes about an hour or so including complining the code, hence you're going to be doing rapid key changing a whole helluva lot.

What I'd suggest doing is using a much different signature system, either ECDSA or ideally BLS. ECDSA you still 4t hash length. However key length changes signature length. Your other huge issue is unless you use RSA-PSS you have a whole nother set of headaches to deal with, on how to properly pad your messages.

However, there is something a bit different that is actually really kinda cool called BLS, it's a pairing based signature scheme. If you don't have to worry about annoying legacy systems it's probably your best bet, http://crypto.stanford.edu/pbc/ is a library that has bls all implemented as an example and makes life fairly easy.

It would also allow for you to not need to change keys since as long as you make around a 384 bit key you're going to have a very strong private key, since it's based on a different problem. RSA is integer factorization in here your on a curve it's different strength metrics.

ECDSA will give you a much greater security margin, since it's randomized and the keys are a lot harder to find. It is a bit more complex but your current key size predictions just are far to small.

Your best bet if you want to do something like this is use a short signature scheme like BLS, their rare and a bit hard to figure out at first but are the way crypto is moving.

Answer 3

If you want compact signatures you should look at ECDSA. RSA is pretty much horrible if key & signature size is important. I have no idea what key strength a 256 bit RSA key would have but even 1,024 bit key is only has 80 bit strength and it takes a 15,360 bit key to achieve 256 bit strength.

The raw ECDSA signatures are 2x the key length as r & s are equal to length of the private key. A key length of 2x the bit strength is required. So for 80 bit security you are looking at a 320 bit signature.

To avoid a replay attack the message signed should not be a static number but rather an random nonce. If you are doing it by urls it could be a simple as accessing /debug will have the software return a unique message for Debbie to sign.

If smaller signature size is really needed you could trade bits for verification time but it won't save you much as ECDSA signature verifications are already slow (you can get something on the order of 2^16 sig verifications per second per core on modern cpu).

Answer 4

You can use a long (e.g. 256 bit) signature, but only have the human enter a short (e.g. 128 bit) signature!

Simply generate the N (e.g. 256) bit signature as normal, then show the human the first M (e.g. 128) bits. Then the checking program can cycle through all combinations of (N-M) bit tails appended onto the M bits that the human entered. Of course, it will take longer for the checking program to check, but that's OK (maybe even good).