Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
If two people want to check they have the same (say 256 bit) private key, how great is the risk in sharing the first say 8 chars over a potentially public channel?
Can an attacker recover any more information than just those characters, and/or how much faster could an attacker crack the key given those 8 chars?
Providing any part of the private key makes it less secure, at least marginally, simply because it provides an attacker with a smaller potential key space to explore.
I fail to understand what you want to achieve. The only thing two people need to do to check if they hold the same information is exchange a hash.
If you are designing a protocol and are worried about replay attacks, you can protect against it by performing a challenge response using a HMAC.
Edit:
As suggested the comments and explained in D.W.'s insightful answer, I need to emphasis that the impact on the security of your private key will depends a LOT of exactly what algorithm you are using. In the worse case scenario, revealing only a small part of the private key will completely break the security of that key.
Revealing part of the private key can be catastrophic, for some asymmetric (public-key) cryptosystems. The exact level of risk depends on exactly which cryptosystem you are using. Some examples:
If you are using RSA with e=3 for the public key, then revealing 1/4th of the private key (the low 1/4 bits of d) is enough to let an attacker reconstruct the entire private key. For instance, if you're using 2048-bit RSA and you reveal the 512 least significant bits of the private key, then an attacker can recover the rest of your private key. This result is due to Boneh, Durfee, and Frankel. There are other results like it in the literature (e.g., about the most significant bits, a random subset of bits, etc.).
With DSA, if a few bits are leaked from the nonce used in each signature (for a variety of signatures), this is enough to recover the private key. For instance, if you can observe 5 bits of the secret nonce that was used in each of 4000 signatures, that's enough to recover a 384-bit ECDSA private key. This isn't exactly revealing the private key (it's revealing some other secret value generated during signing), but it's similar.
I realize other answers are saying it's no problem. Those answers might be assuming you are using a symmetric-key cryptosystem. For most symmetric-key cryptosystems, if you reveal part of the key, but enough of the key remains unrevealed, they'll likely still be secure. When it comes to asymmetric cryptosystems, things are different. Other answers appear to be assuming that brute force (exhaustively trying all possible private keys) is the best attack possible against the cryptosystem. For many asymmetric cryptosystems, this assumption is not accurate.
How much faster could an attacker crack the key given those 8 chars?
It's hard to answer without knowing what kind of key we are talking about and what algorithm it's used with.
In the case of symmetric encryption where the key is entirely random (understand each bit takes equal part in the global uncertainty of the key), then it mainly depends on what "1 char" represents in terms of binary data.
In general, by revealing n bits, you are effectively reducing the number of possible keys by a factor of at least 2^n.
1 character = (0 or 1) = 1 bit : 8 characters means a reduction factor of 2^8 = 256.1 character = 4 bits : 8 characters means a reduction factor of 2^32 = 4294967296.1 character = 6 bits : 8 characters means a reduction factor of 2^48 = 281474976710656.Which - depending on the amount of the revealed information - may (or may not) be used as a leverage to break your key depending of the possible (current or futur) weaknesses of your encryption algorithm.
Also note that in the case of asymmetric encryption where the key is not completely random (e.g. prime factor modulus and exponent in RSA), revealing n bits may actually reveal much more useful information and may lead to catastrophic loss of security.
But the real question is :
Why would anyone ever need to do that ?
Not only this method poses a potential security flaw, it doesn't seem to reliability fit your purpose, what about the remaining 248 bits ?
The method you describe is just a very trivial hash function that is completely continuous (very bad for integrity check) and partially reversible (very bad for security purpose).
If you really need to do this, use a secure and widely-available cryptographic hash function such as SHA-256 which will generate a hash that is much more secure (practically irreversible and computationally intensive) and much more collision-resistant than "the first 8 chars".
If you are using asymmetric encryption, you should never need too share any part (even a hash) of the private key, use the public key instead.
I'd say it ranges from "not critical, but kinda stupid" to "disastrous", depending on what "8 chars" means and depending on what algorithms are used.
If one reads "8 chars" as what they literally are, 64 bits, then you reduce your key size by 64 bits (it's somewhat less drastic if one assumes "char" as base-64 encoded character, then it would only be 48 bits).
Assuming "private key" actually refers to a symmetric algorithm (unlikely?), that's probably tolerable since 192 bits are way beyond possible to brute-force. But then again, why use a 256-bit key in the first place?
Assuming "private key, 256 bits" means you use an elliptic curve crypto of sorts (for symmetric ciphers, "private" makes little sense as all keys are private, and for RSA et al. 256 bits is way too small to be useful), you lower your security level from slightly below 128 bits (which is, presently, unfeasible) to somewhat less than 96 bits. Which is... well, not precisely feasible, but almost. Considering that quantum computing is not quite there yet but on its way, "not quite, but almost" is kinda disastrous.
After all, what one plans for is the worst case, not the best case.
It's disastrous even more so as doing this is absolutely, 100% unnecessary.
If two parties share a secret key, one very obvious method of making sure it's the same key would be to encrypt a sufficiently long (longer than hash output) random bit pattern, let the other side decrypt the bit pattern, and send back a secure hash (say, SHA-256, SHA3, whatever) of the bit pattern.
Which the first party can trivially compare to the result of calculating the hash on the original random pattern.
At no time is the private key (or part of it) transmitted, or even a hash of said key (which could very very unlikely, but possibly, be reversed or provide a hint towards part of it), and since there are more random input bits than output bits, it is impossible to determine the original bit pattern that was hashed from the hash value, and use that to get an angle on the encryption.
The attacker only gets to see a random bit pattern for which he needs to know the (unknown) key to obtain the original, and the hash of another unknown bit pattern which could be one of many bit patterns (with no way of knowing which one).
Others have already answered by how much the information is leaked and hence how much the entropy is lowered for an attacker ; and the main point that one should compare (publicly) hashes has been noted also.
However, this is assuming that the two people wanting to compare keys trust one another. If they don't trust one another, the problem is that if A sends hash(K) to B, B can know that A has the same, or a different K than B, but he can cheat and send back the same hash, making A think erroneously that B is also in possession of the same key.
A solution to that problem is that A sends hash(K) to B, and expects B to send hash(not K) to A, where not K is the bitwise flipped value of K. B can only send this hash to A if it really possesses K.
NOTE The following assumes a linear speedup (such as would be gained in a brute-force attack) - the speedup may be EXPONENTIALLY MORE, depending on the algorithm.
It is very difficult to comprehend big numbers - even I was surprised when the answer came up. Here is a way of thinking about it:
If, without any information, it would take 13.8 billion years (the age of the universe so far) to crack a key, with the help of 8 binary characters, it would take only 0.023 seconds.
This is: 13.8 billion years / 2(bits_per_symbol*number_of_symbols).
You said the number of symbols is "8 characters", and I'm assuming binary, which has 8 bits per symbol. so: 13.8 billion years / 2(8*8)
If they are uuencoded, or base64, they will have 6 bits per symbol, so it would take them all of 25 minutes to work through the remaining combinations.
These proportions apply only to the number of bits you've revealed, and is irrespective of how long the key is (only that the key would take 13.8 billion years to crack).
The whole point of public key cryptography is that you NEVER EVER EVER need to share the private key. Each private key should exist only in one place, and never travel across a network. Sending keys goes against the very principle of public key cryptography. There is NEVER a need to send private keys, partially or otherwise.
If you want two (or more) different devices to be able to decode the same message, have each create their own private key, send you their public key (securely!!) then encrypt the message with both keys. Usually with PKC, long messages are encrypted using symmetric encryption with a random key, and the key is then encrypted with PKC, and sent with the message; you can easily encrypt the random key with multiple public keys, and send all of them with the same message.
If all you want to do is show you have the private key, you can do the following:
Ask the person you want to prove it to to provide a random value (a "nonce"). Add random value of your own, hash it, and sign the hash. Send the your random value, and the signature, back.
Your counterpart will then take the nonce they sent, plus your random value, hash it, and check the signature against your public key.
Including a random value from the sender, proves that you did not just select a value that has been signed by the real owner previously.
DO NOT UNDER ANY CIRCUMSTANCES accept something sent by someone else, and signing it, without any changes. They can send you the fingerprint of a document they wrote, and you will be effectively signing that document.
If Alice and Bob suspect they share the same private key, then why not:
I am not a cryptographic expert. Am I missing something?
I think the above will satisfy their question without exposing their secrets. Eve will not know the answer to the question either.
