Keys required for cryptography

Question

I am reading an article on cryptography at following location:

http://www.entrust.com/resources/pdf/cryptointro.pdf

Historically, encryption systems used what is known as symmetric cryptography. Symmetric cryptography uses the same key for both encryption and decryption. Using symmetric cryptography, it is safe to send encrypted messages without fear of interception (because an interceptor is unlikely to be able to decipher the message); however, there always remains the difficult problem of how to securely transfer the key to the recipients of a message so that they can decrypt the message.

With symmetric cryptography, as the number of users increases on a network, the number of keys required to provide secure communications among those users increases rapidly. For example, a network of 100 users would require almost 5000 keys if it used only symmetric cryptography. Doubling such a network to 200 users increases the number of keys to almost 20,000. Thus, when only using symmetric cryptography, key management quickly becomes unwieldy even for relatively small-scale networks.

How did the author conclude 5000 keys for 100 users and 20,000 keys for 200 users?

Answer 1

The system can be viewed as a complete graph, in which each vertex is a user and each edge represents a different symmetric key.

Thus for 100 users (vertices), you need (100*99)/2 keys (edges). This is roughly 5,000.

To help visualise, consider the image below from Wikipedia. It demonstrates a complete graph with seven users. Hence 21 seperate keys would be required.

Answer 2

See Duncan's answer for the reasoning the original author used. The problem isn't so much the total number of keys, but the problem of exchanging them securely; that is, if you share a key with someone else, you need to ensure somehow that who that someone else is who you think they are, and that no one else knows what that key is. This is certainly doable (say, by meeting them in private), but is not trivial.

Now, the problem with the argument that a complete graph is needed is that it isn't, strictly speaking, correct. There are ways to reduce the total number of keys in a complete graph using trusted intermediaries.

Here's a simple case of how this can work: suppose Alice, Bob and 998 of their closest friends all want to communicate securely. Instead of each one exchanging 999 different secret keys with all their friends, what they can do is find a person they trust (Trent), and each one exchange a secret key with Trent. Trent, of course, needs to store all 1000 keys, along with who each key belongs to.

So, when Alice wants to have a secure communication with Bob, what she does is pick a random key, and sends an encrypted message to Trent that says "I'm Alice, please send the K to Bob". Trent decrypts the message with his key with Alice, checks that it's reasonable (e.g. that it says that it's from Alice and not someone else), and then encrypts the message with his key with Bob, and sends it to Bob. Bob decrypts the message, and now Alice and Bob share a key that they can use to communicate securely. No one else knows what that key is (other than Trent, but we trust Trent). Alice and Bob can use their shared key for traffic between them, and discard it when they're done.

So, this procedure reduced the number of times we need to exchange keys securely from 499,500 (for the simple complete graph) to 1,000 (each person exchanges a key securely with Trent). Another way of looking at it; if Carol then joins the group, in the complete graph, she'd need to exchange keys with 1,000 other people, in the Trent scenario, she'd need to do it only once (with Trent himself).

So, the obvious question is: if this works so well, why do we use asymmetric cryptography. Well, because asymmetric cryptography does have some advantages:

• In the above procedure, Trent had to be involved with the start of every secure communication. With PKI, the trusted party (Certificate Authority or CA) needs to be involved with giving out certificates initially, but does not need to be involved with establishing secure communications between two parties.

• In the above procedure, Trent had to have all the keys, and also be able to handle active communications. This means that Trent is a very attractive target to hackers; they'd have valuable keying information, and a large potential attack surface. With PKI, CAs can be much more isolated.

• Trent had to be trusted; if he wanted to, he could listen into every communication. CAs are also trusted, but to a lesser extent; they can impersonate other people, and they can act as an active Man-in-the-Middle between two people establishing a communication, but they cannot passively eavesdrop.

• With PKI, not everyone needs to be registered with the Trusted Third party, if no one really cares who they are. That is, if Alice wants to make sure she's talking to Bob, but Bob doesn't really care who's he talking with, Alice doesn't need a certificate. This is a more common scenario than you'd expect; when you give your credit card information to Amazon, you really care that you are, in fact, giving it to an Amazon server; Amazon doesn't really care which PC you're using.