36

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?

  • 20
    Are you talking about a private key in asymmetric cryptography, like RSA, or are you talking about symmetric keys, like AES (which I kind of guess based on using 256 bits as the example size and talking about sharing the key itself)? The answer differs significantly based on which of those you are talking about. – forest Dec 12 '17 at 14:41
  • 12
    It seems people have been giving incorrect answers due to the popularity this question got. You have people talking about how a 4096 bit key has a 2^4096 keyspace, people who are claiming that factoring a large RSA is harder than brute forcing it, and people who don't even understand the basic structure of such a key, thinking it's all homogenous. You should probably go to Crypto.SE if you want actual answers. – forest Dec 13 '17 at 2:02
  • Comments are not for extended discussion; this conversation has been moved to chat. – Rory Alsop Dec 15 '17 at 8:14
81

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.

  • 15
    Private keys do not provide security by having a large keyspace, they provide security through the difficulty of factoring huge semiprimes. Leaking part of a private key doesn't leak an equivalent amount of information. – forest Dec 12 '17 at 14:30
  • 23
    All information in a private key is not equal, so there is no "equivalent factor". Leak the modulus or public exponent and nothing happened (versus sharing the public key). Leak "50%" of the prime numbers and you're 100% boned. – Nick T Dec 12 '17 at 15:33
  • Comments are not for extended discussion; this conversation has been moved to chat. – Rory Alsop Dec 14 '17 at 19:53
54

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.

  • 8
    +1 for explaining what is so wrong about the other answers (re. assuming a symmetric cipher). Depending on what type of system the OP is asking about, this whole thread is either dangerously incorrect or rather decent. – forest Dec 14 '17 at 5:23
23

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.

  • In case of a binary textual representation where 1 character = (0 or 1) = 1 bit : 8 characters means a reduction factor of 2^8 = 256.
  • In case of an hexadecimal representation where 1 character = 4 bits : 8 characters means a reduction factor of 2^32 = 4294967296.
  • In case of a base64 representation where 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.

8

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

  • 1
    A clever zero-knowledge proof ! – entrop-x Dec 14 '17 at 6:18
6

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.

  • 3
    While this is a neat and clever solution to a problem, I don't think that this answer the question as stated in the title. – Anders Dec 13 '17 at 16:04
  • @Anders: It depends on what one understands in the original question by "check they have the same key", and whether this is simply a check by mutually trusting parties over an insecure link, or whether the counterparty is not to be trusted either. – entrop-x Dec 14 '17 at 6:14
4

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.

  • For public key cryptography, each bit in a key is not equivalent, and you can't use simple keyspace arguments to calculate how much it would be weakened. For a symmetric key it would be a valid argument, but your assumption that a 256 bit keyspace can be searched in 13.8 billion years is incorrect. 8 characters is 64 bits. A 256 bit key reduced by 64 bits still has a 2^192 keyspace, which can absolutely not be searched in 0.023 seconds. You would need to guess a quattuorsexagintillion keys per second for this answer to be correct even within an order of magnitude. – forest Dec 17 '17 at 3:29
  • I never said that it could be calculated at that speed. My point was the proportion of the reduction. human beings have a hard time comparing 2^256 to 2^192, or even "it takes 1/(2^64) times as long", whereas people have some idea that the age of the universe -> 23ms, is quite a big reduction. With no reference to the specific algorithm, nothing can be said about how long it takes to crack a key. – AMADANON Inc. Dec 17 '17 at 18:48
  • Then this seems like an explanation of how big numbers are hard to understand, not an answer to the question. Are you describing asymmetric cryptography (which I imagine because you mention public/private keypairs)? If so, then the speedup isn't going to be linear either, as other comments and answers have pointed out. – forest Dec 18 '17 at 0:58
  • I think giving an understandable comparison is highly relevant to this conversation. My answer (for the most part) is irrespective of asymmetric of symmetric, but does assume a linear speedup (e.g. brute force). This assumption may not be correct. Is there something inherent in asymmetric cryptography that necessarily stops it being linear? I understand that some (e.g. the most commonly used RSA, EC) have better attacks, does this mean that all (must) do? – AMADANON Inc. Dec 27 '17 at 1:43
  • As far as I am aware, all public key cryptosystems are based on "hardness problems" such as the discrete log problem, factoring huge semiprimes, shortest vector problem, etc. This necessarily means that they are not cracked with brute force, but by using the best available algorithm for solving the problem (e.g. GNFS for integer factorization). Symmetric crypto, on the other hand, uses completely different techniques. Rather than using hardness problems, they introduce "confusion and diffusion" with things like feistel networks, substitution-permutation networks, add-rotate-xor, etc. – forest Dec 27 '17 at 3:28
2

If Alice and Bob suspect they share the same private key, then why not:

  1. Alice generates nonce X.
  2. Alice encrypts X to herself - Y.
  3. Alice sends X, Y to Bob.
  4. If Alice and Bob really have the same private key, then when Bob decrypts Y, he will get X. Now Bob knows that Alice shares his private key.
  5. Bob does the same in reverse. Now Alice knows Bob shares his private key.

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.

  • This is a good answer. I was about to write the same! And I'd just have added that 2 persons (/servers/etc) shouldn't have the same private keys! – Olivier Dulac Dec 14 '17 at 14:50
  • 1
    @OlivierDulac you are correct that it is a non-problem – emory Dec 14 '17 at 16:40
  • It wasn't said in the question whether the private key was the private key in asymmetric crypto. If it is a symmetric private key, it makes sense. And if it is part of an asymmetric key pair, there's no point: you compare the public keys ! We could be talking about "checking the same password". – entrop-x Dec 16 '17 at 5:33
  • If two people share the same private key (using the same algorithm, e.g. RSA), then they MUST share the same public key. So Alice can search for her public key in a public key directory like keyserver.pgp.com . This lets her check millions of keys in one go. – AMADANON Inc. Dec 17 '17 at 18:46
  • @AMADANONInc. I do not believe that is strictly speaking true. Can you prove it? – emory Dec 18 '17 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.