4

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.

Elazar Leibovich
  • 519
  • 2
  • 7
  • 14

4 Answers4

5

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

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • Thanks! (of course, if you patch the binary you can use the debug features, but you cannot use them remotely, unless you patch the binary.) Excellent points, I'm feeling such an idiot that a simple thing such as hash function escaped me. BTW you can protect code (a la product key), if you encrypt the actual code, and given the correct product key you decrypt it and run it on the fly. Maybe this scheme was burned into my memory so hard that simpler solution escaped me. – Elazar Leibovich Jan 15 '12 at 17:55
  • BTW2, I've seen PKCS#1, and my understanding is, it's benefit is mostly saving you from choosing bad signature values by smartly padding even small numbers. If you choose randomly a high enough number to sign, you can avoid this hazard, am I correct with my observation? – Elazar Leibovich Jan 15 '12 at 17:56
  • @ElazarLeibovich: it is more complex than that. The hash function invocation (you sign a hash value over the data, not the data itself) is important for unforgeability. The padding bytes are important to avoid using value which are numerically "too low" because there are possible attacks in that case (the involved mathematics are quite involved). Also, note that there is no proof that PKCS#1 (old version) is secure, only that it sustained two decades of analysis. Changing even a single bit of that padding nullifies the benefits of these two decades. – Thomas Pornin Jan 15 '12 at 18:00
  • Thanks again! Can you please explain (or refer me to explanation), of why does invoking hash is "better" than generating a random value in the hash functions result's range. After all hash function result is supposed to look like a random function. – Elazar Leibovich Jan 15 '12 at 19:57
  • 1
    One other element to consider - your solution and a SHA256 of a shared secret have no replay protection. URLs have a habit of not staying secret (they're Referrer headers, cached resources, bookmarks stored locally and in cloud services, etc...). Consider using a different scheme where Debbie's secret access code must change on a periodic basis. – Tails Jan 16 '12 at 05:58
  • @Tails Thanks. The canonical answer for this is a challenge response (which indeed must be based on private key I think), but I'm not sure how to do that in user friendly-enough way (maybe an internal JS static page which implements the crypto? I'm not sure it'll be able to cross domain boundaries though). The only improvement I can think of is putting the secret in `POST` which is a bit less problematic, but less convenient. – Elazar Leibovich Jan 16 '12 at 06:51
0

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.

user1392
  • 119
  • 2
  • Even with elliptic curves going below 40 byte signatures becomes insecure. – CodesInChaos Aug 16 '12 at 09:50
  • 1
    I also disagree that the randomization in ECDSA increases security. The randomization in common ECDSA implementations is an unnecessary risk, and I strongly prefer deterministic variants. – CodesInChaos Aug 16 '12 at 09:53
0

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

Gerald Davis
  • 2,250
  • 16
  • 17
-3

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

  • 2
    1) I know no scheme with 256 bit signatures 2) Cycling through 2^128 potential signatures is far too expensive. This technique can be used to save some bits, but only 30 or so. – CodesInChaos Aug 16 '12 at 10:01