BRAND: Asymmetric Encryption
Learning Outcomes
After completing these activities you should be able to:
- Define asymmetric encryption and be able to discuss what it is used for.
- Describe how asymmetric encryption is used in the context of the Cyber Pillars discussed earlier in this course.
- Be able to understand, describe, and execute a real-world example of asymmetric encryption, namely public key cryptography, and be able to use and explain the command-line tool OpenSSL.
Behold: The World's First Digitally Signed International Agreement
The Atlantic
In this lesson we will learn about Asymmetric Encryption (also called Public-Key Encryption). Asymmetric/Public-Key Encryption allows us to establish secure communications even when we have no opportunity to agree on a secret key ahead of time or via another communication channel. This is crucial for secure transactions over the Internet. Who would want to travel to a phyiscal Amazon location to get an encryption key in order to be able to shop securely!!! Additionally, we will discover that asymmetric/public-key encryption will provide us with a mechanism to digitally "sign" files, which gives us the ability to sign documents from anywhere.
Limitations of Symmetric (Secret Key) Encryption
The Problem. The fundamental limitation of symmetric (secret key) encryption is ... how do two parties, who haven't previously communicated, agree on and share an encryption key? Let's call the two parties 'Alice' and 'Bob'. There is a third party, an eavesdropper, who we'll call 'Eve' (generally representing anyone who can intercept traffic). In order for Alice and Bob to communicate securely they need to agree on a secret key. In order to agree on a secret key, they need to be able to communicate securely. In terms of the Pillars of Cyber Security, To provide Confidentiality, a secret key must first be shared. But to initially share the key, you must already have Confidentiality. It's a chicken-and-egg problem.
This problem is especially common in the digital age. We constantly end up at websites with whom we decide we want to communicate securely (like online auction sites) but with whom there is not really an option to communicate "offline" to agree on some kind of secret key. In fact, it's usually all done automatically browser-to-server, and for the browser and server there's not even a concept of "offline" — they only exist online. We need to be able to establish secure communications over an insecure channel. Symmetric (secret key) encryption can't do this for us. So what is the solution? ...
Asymmetric Encryption (Public-Key Cryptography)
Asymmetric encryption is a big topic. It gets used in lots of interesting ways — often in combination with
hashing and
secret key encryption, as we'll see. You might like to check out this
arstechnica.com overview of asymmetric encryption/public-key cryptography and how it's
commonly used.
In asymmetric encryption, both communicating parties (i.e. both Alice and Bob) have two keys of their own — just to be clear, that's four keys total. Each party has their own public key, which they share with the world, and their own private key which they ... well, which they keep private, of course, but more than that, which they keep as a closely guarded secret.
The magic of public key cryptography derives from three important points:
- A message may be encrypted with a public key and then decrypted with the corresponding (paired) private key. It is also possible, but not recommended, to encrypt a message with a private key and then have decrypt it with your public key. It is mathematically possible for either key to be used for encryption or decryption (Some public-key cryptography algorithms, including the RSA algorithm that we'll cover in some depth, have the special property of being commutative, which means that the roles of private key and public key are interchangeable), but they only work in pairs:
- A message encrypted with a certain public key can ONLY be correctly decrypted with the corresponding private key, and vice versa.
- Because only the private key needs to be protected, public keys can be shared openly (even to Eve), and therefore the limitation of symmetric encryption is alleviated.
Encrypted Communications. In this scenario, Alice encrypts her message with Bob's public key, and Bob decrypts the message with his private key. Alice can rest assured that only Bob can decrypt the message she sends, because she has encrypted it with his public key. Only Bob's private key can correctly decrypt the message.
Note, however, that while this provides a solution to Alice's
confidentiality problem (she knows only Bob can read the message), Bob has an
authentication problem on his hands. Yes, he's received a message only he could read, and the message claims to have been sent by Alice, but he has no guarantees that it really did come from Alice. Anyone can send a message to Bob using Bob's public key, since it's freely available.
Note: We will discuss what Digital signatures are in another lesson. For the time being think of a public/private key pair and a public-verification/private-signing key pair as two different key pairs constructed in the same way, but being used for different purposes. One is used to encrypt things and the other is used to attempt to bind an identity to the object it encrypts.
Authenticated Communications. In this scenario, Alice will generate a new signing key pair (public-verification key, private-signing key) that acts in a similar manner to what we have already learned above. Alice then encrypts her message with her private-signing key and shares her public-verification key. Bob decrypts the message with Alice's public-verification key. If the message correctly decrypts with Alice's public-verification key, Bob knows that the message could only have been encrypted by someone possessing Alice's private-signing key. This establishes that the message must have been sent by Alice (assuming no one has stolen Alice's private-signing key).
Bob's
authentication problem is solved. However, Eve, or anyone else seeing the encrypted message, could decrypt it using Alice's public-verification key, which is freely available, so the message's
confidentiality is not guaranteed. Can we combine the first two techniques, and achieve both authentication and confidentiality? Sure!
Confidential and Authenticated Communications. In this scenario, the previous methods are combined. Alice encrypts the message first with her private-signing key, then Bob's public key. Bob decrypts the message, first with his private key, then with Alice's public-verification key. Now, both authentication and confidentiality are achieved!
Real World Implementation of Asymmetic/Public-Key Encryption: RSA (Rivest, Shamir & Adleman) Encryption
- General. The RSA encryption scheme provides commutative, asymmetric encryption.
- Math Description. The public key consists of two large integers (e,n) and the private key consists of two large integers (d,n). Note that the second number, n, is the same in both! The three numbers e,d,n are related in a special way, which requires a bit more mathematics to go into. The crucial point is that n is guaranteed to be the product of two prime numbers, i.e. n = pq for two primes p and q. If you know e and n, and you've found the factorization of n into pq, you can compute d easily. So the security of RSA requires that factoring a large integer is difficult. And when we say large, we're not kidding! Today, RSA implementations might use a 4096-bit number for n. Nobody currently knows how to factor numbers of that size quickly, which is to say before we and our planet are long dead, so RSA seems pretty secure. However, nobody has formally, mathematically proved that it's impossible to factor numbers quickly either, so RSA may be broken some day. <-- add correctness proof comment here-->
- Check out the SY110 RSA Demo Page, which is also linked off of SY110 Resources. Try to encrypt a message as if you were Alice and decrypt the message as if you were Bob. Note that this tool generates just a 128-bit key, which is nowhere near a length that is currently considered to be secure.
- To see a more in-depth walkthrough that shows you the mathematics behind Public Key Cryptography visit Brett Slakin's website.
The Security of RSA
- Finding the Prime Factors of the Modulus. We won't go into too much detail about how RSA works: block size, padding schemes, key-generation etc., even though getting these kinds of details right when implementing RSA is actually tricky. However, it is important to understand one fundamental fact: it is always possible to crack RSA by computing someone's private key from their public key. All it takes is being able to factor the modulus (the number n that's common to both the public and private key) into its two prime factors. However, if the modulus is big enough, even though it will be possible to do the factorization, it will not be feasible — meaning that the time/computing-power required to do it is simply too great. After all, if Eve dies of old age before her computer factors the modulus from Bob's public key, it doesn't do her a lot of good.
Your CAC knows crypto.
Your CAC supports a number of different cryptographic
algorithms, including:
Hashing: SHA-512
Symmetric encryption: AES-256
Asymmetric Encryption: RSA-2048
... and others.
Included on your CAC are public/private key pairs that you
can use to decrypt e-mails intended only for you, and to
digitally sign documents. For more information visit the following cac.mil website.
- Just Increase the Key Size. The power of RSA, and the reason that even though it has been in use since the 1970's, stems from the fact that as computers and algorithms get faster, it becomes feasible to factor bigger and bigger numbers, we can simply use bigger (and therefore harder to factor) numbers for the moduli in our RSA keys. Moreover, increasing the size of the modulus even a relatively small amount vastly increases the difficulty of factorization.
- "N-bit" RSA means n bits in the modulus size. Generally, when you read n-bit RSA it means that the modulus (the number n (n=p*q) that's shared by the public (n, e) and private (n, q) keys) is N-bits long. In 1990, 512-bit RSA keys were deemed pretty secure. In the intervening years, the computing power of a typical desktop computer has increased several thousandfold. Still, today 2048-bit RSA is deemed pretty secure. That means that we've only had to increase our RSA key size by a factor of four to make up for the more than 1,000-fold increase in the computing power of a typical desktop PC. If you are really worried about security, simply increase the bit-size of your RSA keys!
Student Asymmetric (Public-Key) Encryption Activity: RSA
RSA Asymmetric / Public-Key Encryption, which we've already covered, is a real-world tool. In fact, it is the most commonly used public-key encryption technique. With RSA you have to worry about key-size and block-size, as we've seen for symmetric (secret key) encryption in the digital world. However, RSA keys have to be much larger that AES keys in order to provide the same level of security. Recall that an RSA key-pair looks like (e,n),(d,n), where e, d, and n are numbers ... very large numbers. When we talk about key size with RSA, we're really referring to the number of bits in n. Today, RSA keys or 2048 or 4096 bits are usually considered secure, and anything less is suspect.
A real-world tool that provides RSA key-pair generation, encryption and decryption is provided as part of the openssl
library, which was included in your software install. Here is a summary of some commands for using
RSA encryption with openssl:
openssl genrsa -out keypair.pem 2048
| ← |
Generate 2048-bit RSA keypair and store in file keypair.pem. |
openssl rsa -text -in keypair.pem
| ← |
View (in text and hex) the RSA keypair in file keypair.pem.
|
openssl rsa -in keypair.pem -pubout -out pubkey.pem
| ← |
Extract the public key from keypair.pem and save in file pubkey.pem.
|
openssl rsautl -encrypt -pubin -inkey pubkey.pem -in plain -out cipher |
← |
Encrypt the file plain using the public key in file pubkey.pem, store the result in file cipher. |
openssl rsautl -decrypt -inkey keypair.pem -in cipher -out plain1 |
← |
Decrypt the file cipher using the private key in file keypair.pem, store the result in file plain1. |
Obviously, the
syntax of these openssl commands is a bit daunting. You are not expected to remember it. What you should keep in mind is that openssl provides the exact same functionality as our online RSA demo page, it just does it from the command-line, and with much bigger numbers (which means more security!).
Option Student Activity:
Want to save yourself some time? Accessing the
ssh.cyber.usna.edu
shell from your Windows laptop requires you to use a symmetric, username/password, combination to authenticate to the server. In this mini-lab, you'll generate asymmetric keys for use by ssh, replacing symmetric authentication and no longer having to type in your domain credentials to access the server.
- Open a local
cmd
shell and generate ssh key pair: ssh-keygen -t rsa -b 4096
- Use the default configuration when navigating through the wizard
- View the public key that was generated:
type .ssh\id_rsa.pub
- Copy the public key to the server's authorized_keys file:
type .ssh\id_rsa.pub |ssh midn.cyber.usna.edu "cat >> .ssh/authorized_keys"
- Enter your credentials to access the server and copy the public key to the authorized_keys file.
- Verify your asymmetric keys are working by logging into the server:
ssh ssh.cyber.usna.edu
References
Schneier, Bruce. 1996. "Applied Cryptography : Protocols, Algorithms, and Source Code in C". Wiley
Department of Defense. 2011. DoDI 8520.02: Public Key Infrastructure (PKI) and Public Key (PK) Enabling. Washington: May 24, 2011.
Department of the Navy Chief Information Officer. 2005. SECNAV M-5239.1: Department of the Navy Information Assurance Program. Washington: November 2005.
Rivest, Shamir, Adleman. 1978. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." ACM 21, no. 2 (February): 120-126.