Since the Edward Snowden revelations a year ago, I have been writing quite a lot about encryption although I don’t know much about it. I came across this introduction to the PGP (Pretty Good Privacy) system, a common form of what is known as public key cryptography, that was fairly clear about how it worked in converting the plain text message into the encrypted form called the ciphertext.
I know that many readers here are way more expert in this area and am putting the link out there for their critical comments as well as to serve as a general introduction to novices like me.
Public key cryptography is an asymmetric scheme that uses a pair of keys for encryption: a public key, which encrypts data, and a corresponding private, or secret key for decryption. You publish your public key to the world while keeping your private key secret. Anyone with a copy of your public key can then encrypt information that only you can read. Even people you have never met.
It is computationally infeasible to deduce the private key from the public key. Anyone who has a public key can encrypt information but cannot decrypt it. Only the person who has the corresponding private key can decrypt the information.
The primary benefit of public key cryptography is that it allows people who have no preexisting security arrangement to exchange messages securely. The need for sender and receiver to share secret keys via some secure channel is eliminated; all communications involve only public keys, and no private key is ever transmitted or shared.
The article goes into some detail about how it works.
PGP then creates a session key, which is a one-time-only secret key. This key is a random number generated from the random movements of your mouse and the keystrokes you type. This session key works with a very secure, fast conventional encryption algorithm to encrypt the plaintext; the result is ciphertext. Once the data is encrypted, the session key is then encrypted to the recipient’s public key. This public key-encrypted session key is transmitted along with the ciphertext to the recipient.
Decryption works in the reverse. The recipient’s copy of PGP uses his or her private key to recover the temporary session key, which PGP then uses to decrypt the conventionally-encrypted ciphertext.
…While the public and private keys are mathematically related, it’s very difficult to derive the private key given only the public key; however, deriving the private key is always possible given enough time and computing power. This makes it very important to pick keys of the right size; large enough to be secure, but small enough to be applied fairly quickly.
As the article states, the recipients public and private keys are somehow related, as they must be if the recipient is to be able to decrypt with the private key something that has been encrypted with just the public key. I am assuming that the algorithm that relates the recipient’s public and private keys has some functionality that is unique to the recipient that prevents third parties from deducing the private key by knowing the public key.
One thing I learned from this article that I was not aware of before was the importance of verifying the identity of the recipient. It is no good having the best encryption system in the world if you are sending the message to the wrong person using the wrong’s person’s public key to encrypt it.
One issue with public key cryptosystems is that users must be constantly vigilant to ensure that they are encrypting to the correct person’s key. In an environment where it is safe to freely exchange keys via public servers, man-in-the-middle attacks are a potential threat. In this type of attack, someone posts a phony key with the name and user ID of the user’s intended recipient. Data encrypted to — and intercepted by — the true owner of this bogus key is now in the wrong hands.
In a public key environment, it is vital that you are assured that the public key to which you are encrypting data is in fact the public key of the intended recipient and not a forgery. You could simply encrypt only to those keys which have been physically handed to you. But suppose you need to exchange information with people you have never met; how can you tell that you have the correct key?
It does this using what are called Digital Certificates that is the equivalent of something like your driver’s license or passport that proves your identity and is included along with your public key. This turns out to be pretty complicated.
The whole thing is quite fascinating. It is likely that I will only really understand how it works when I actually implement it.
I haven’t implemented it, but I have seen the math behind it. All it boils down to prime numbers, factorization, exponentiation and “clock” or modulus math. Wikipedia has the nuts and bolts; it’s simple stuff, the real challenge is doing quick math with large numbers.
Right, you can simulate the way the private-key public-key exchange works with small prime numbers to get an idea how it works. The actual system works with prime numbers in multiple hundreds of digits, and there is no shortcut for dealing with those numbers (if there was, the system would be useless). Hence the convoluted approach with session keys.
This perhaps a bit hyperbolic. There must be an unbroken chain of people you trust between you and the recipient. The trust for each link must be commensurate with the secrecy intended in the communication.
It should be noted that it is suspected that factoring large numbers is amenable to a quantum computing approach. Governments do have quantum computers, but it is not known that they are large enough (in terms of q-bits) to factor the size of numbers we are talking about.
Also, consider the intended life of the message you are sending. Is it ok if they message is decrypted in twenty years? Fifty years? Ever? One should assume that every message one sends over public lines will be saved forever.
I found this video very helpful in understanding the basic principles behind encryption: https://www.youtube.com/watch?v=3QnD2c4Xovk
I always found the mathematical explanation way more clear than the actual implementation. The proof that the RSA algorithm works is actually quite simple and is basically an application of Fermat’s little theorem. Probably every computer science student has to do this proof at some point during his studies.
This is actually the problematic part that has not been solved satisfactory yet. The current solution is a 3rd party that both participants in the conversation have to trust. This 3rd party will check the identity of the participants and then sign their keys public keys with its private key which means that the 3rd parties public key can be used to verify the integrity of the keys. And in the past those certification authorities have been part of the problem. A decentralized approach such as WOT is probably the way to go but that is also not without its problems.
Not to mention that these approaches are way too complicated for the average user who just wants to send messages.
I very much like the approach that Threema (a relatively new instant messaging service for mobile phones) has to this subject. All communication is encrypted and they also provide the public key infrastructure for the key exchange. If you happen to meet your communication partner in person you can validate the key just by scanning a QR code on their phone.
There is a guide that was put out recently to help people running Windows, MacOS X or Linux (aka GNU/Linux) get emai encryption going fairly quickly and easily. The guide is by the Free Software Foundation. Here’s a link to the Windows version as that’s what most people will have a use for. Walkthroughs for the other operating systems are a click away on the page.
https://emailselfdefense.fsf.org/en/windows.html
Note: The walkthrough uses the cross-platform Thunderbird email client and a plugin to enable it to use PGP. This won’t work with webmail or another email client.
James Mickens makes some useful points concerning the usefulness of encryption against state actors in this hilarious presentation, from time index 16:15 onwards (for about 5 minutes). His basic point is that encryption is essentially futile as long as you can’t trust the rest of your software or hardware, that the capabilities of state actors are such that relying on cryptography to protect yourself from government spying is roughly equivalent to relying on black powder muskets to protect yourself from Tomahawk cruise missiles, and that they’re not going to even bother trying to break your encryption when then can own your hardware, your software, and all of the network infrastructure: “How can we defend against the government when the only things we can trust are some rocks, a pencil, and this big dry leaf I found in my driveway?”
(The rest of the presentation is also well worth watching. They don’t call him “the funniest man in Microsoft Research” for nothing.)
@6: Makes one wonder how people did cryptography before computers…
There are very secure cryptographic systems that don’t require computers. If one is concerned about Mossad, one should be using them.
Makes one wonder how people did cryptography before computers…
Much better. 🙂 The playfair cipher and book ciphers were pretty much unbreakable. Rotor machines like the Enigma and Hagelin actually ushered in the computer age. But prior to them, you had simple rotor machines like the ones the US used in the civil war, which were more or less unbreakable until “The index of co-incidence” was published, linking statistics to cryptanalysis.
A way I like to think about PGP and public key systems is that they transfer one problem (exchanging a key) into another one (determining if the key is trustworthy, and keeping it safe) — what’s interesting, in my opinion, is that the latter two problems are harder. In other words, public key is a step backwards. Now you have a 2048-bit pseudoprime diffie-hellman key pair and it’s stored on your hard drive, managed by a shitty operating system that supports USB keyboards(*) which cannot adequately protect the memory of its virtual machines and in which the key resides -- exposed to anyone with a debugger. … Oh, that’s great. And, of course, you assume that the key signing key was not compromised because -- (here, picture me waving jazzhands!) -- Verisign signed it. Never mind that Verisign is literally down the street from CIA HQ and was founded by a bunch of security industry people that have been historically very very friendly with the police state… Then, there’s the problem that PGP brilliantly includes message headers and checksums, one of which screams “HEY NSA THIS IS A PGP MESSAGE OMG OMG!” and the other of which will tell them automatically if they have decrypted the message correctly, greatly simplifying attacks against it.
The challenge that PGP solves is a difficult one: me meeting up with my co-conspirator someplace dark and gloomy and exchanging a piece of paper with a passphrase that’s long enough and complicated enough that with enough rounds of bulk encryption on the data, it will not be broken. Period.
In security, we often say “complexity is the enemy of security.” And we also say “ease of use is the enemy of security.” It is a truism that if you have an encryption system that automates a lot of the process, that automation is a gilt-edged invitation for your enemy, reading “<<—- ATTACK HERE" PGP has a lot of automation.
NSA used to pretend to hate PGP but they stopped back in the 90s. Some think it's because the NSA could/can break PGP(**) and others think it's because very very few people actually use it. My thinking is that it's an ideal situation for NSA: enough people use PGP that they can be pretty sure that people who use PGP are waving a big red flag that says "NEEENER NEENER I HAVE A SEEEECRET!"
(* it's as if that interface was designed by a villain as a mechanism to make it easy to steal cryptokeys!)
(** I wouldn’t be surprised, but it’s equally plausible that the checksums in the messages provide enough certainty that a parallelized search brute force is possible. What I expect, and some of the leakers’ revelations appear to bear out, is that people who use PGP are more likely to attract complete message capture and a malware drop onto their computer, rendering the encryption bypassable)
Here’s a hint: if you wish to engage in secure communication, obtain an iPad (for example) and use it only for the purpose of encrypting and decrypting messages. Do this only on battery power, store it in a safe when not in use, and ideally only use it in the basement of your house, bomb shelter, or handy Faraday cage. Never hook it to any network but the very small one you use to transfer the encrypted messages to/from the internet. Never open any documents on it at all except the encrypted messages. If you’re going to do this, your best bet is to pre-exhange iPads containing 32GB of random noise, and use that sequentially as a one-time pad.
Otherwise, you may as well post your stuff on facebook.
The current solution is a 3rd party that both participants in the conversation have to trust.
I used to like to ask people “how many 3rd parties would you trust to decide whether or not you live or die?” Because whatever number that is, is the number you can trust to authenticate your public key exchange, if you’re really being naughty.
Marcus Ranum @10:
Hmmm, I’d prefer to use an Android smart phone with a removable battery and micro SD, imaged with a hardened, non-rooted OS just before each boot. And 32GB is overkill, you’d have a tough time exhausting 1GB. Just make sure it’s ACTUAL random noise, taken from a cryptographically secure source.