tmacuk

A Quick Intro

Hello everyone, my name is Matthew and as you might have guessed I’m here to provide a guest series on cryptography. If any of you should feel the strange desire to check me out, you might want to start at my technical blog here.

I’m afraid I must also make a short disclaimer. Although I like to think I know plenty about it, I’m not an expert in cryptography (or at least not yet). But I do know more than Tmacuk does, so that’s alright I guess.

The Current State of Cryptography

In the next few posts I’m going to be introducing you to a particular set of cryptographic software, namely GnuPG/PGP. I’ve chosen to show you this software, partly because I use it and it’s very useful, but also because it makes use of many of the most modern algorithms, so it’s a good chance for you all to see the state of cryptography in the present day.

Historically there has been a long ongoing battle between cryptographers trying to send secure messages, and cryptanalysists trying to read them. At various points through history the balance of power has shifted between one and the other, but at the moment the boot is firmly on the foot of the cryptographer. If you use the systems I describe here, then (excepting some caveats) it is thought (by some people) that cracking one of your encrypted messages would take longer than the age of the known universe. Not that I’m being at all sensationalist of course.

PGP, OpenPGP and GnuPG

The standard of encryption we are going to be using is called OpenPGP, and it is an open standard implemented by many pieces of free and non-free software. It’s based on (and very similar to) the original PGP file format (PGP was the first cryptography software for ordinary desktop users), and allows many different applications to interoperate so people using different software can easily send each other encrypted messages.

GnuPG (shortened to GPG) is the Gnu Privacy Guard, GNU’s open source implementation of the OpenPGP standard. As well as the required elements it supports many extra ciphers and algorithms for extra security, most of which are supported by most other implementations anyway. This is the software I will be using for this guide, as it is the easiest to use for most GNU/Linux users (myself included). It should be noted that, while we will be configuring it to allow you to send messages to people using other software, you may not be able to export your key and import it into other software because we will be using some extra protections for it. However, we shan’t be generating a key until next post folks.

How GPG works

GPG combines two different encryption technologies to provide an easy way to securely send a message to another. The first of these is asymmetric encryption, also known as `public key’ encryption. This form of encryption allows a message to be sent without having to exchange any secret information prior to sending. Each GPG user generates their own private key, which they keep secret. However, in doing so, they also generate a public key, and this should be distributed as widely as possible. If somebody wishes to send a message, they first look up the recipients public key.

Usually this is done using a keyserver which stores public keys that are uploaded to it – there exists a large network of these servers, and they all share keys with each other so that the keys are as widely available as possible. Once you have the recipients public key, this can be used to encrypt a message to them. Anyone can encrypt a message using the public key, but these messages can only be decrypted using the private key, which only the recipient has a copy of.

However, asymmetric ciphers are notoriously slow, and if you were to encrypt an entire message with them it could take several minutes. So to provide speed, a symmetric cipher is used to encrypt the message body. Symmetric ciphers use the same key for encryption and decryption, so a new key is generate for each message, and this key is then encrypted using the public key of the recipient, and sent with the message (in a header).

This method provides speed and easy security. Anybody can easily send a message to the recipient using their public key, and only the recipient can use their private key to decrypt the key for the message body, and in turn decrypt and read the message. It is also possible to use the asymmetric cipher in reverse, to create data that only the owner of the private key can encode, and anyone else can decode. GPG also can do this, known as digitally signing, and this can be used by the recipient to verify that a message was sent by the owner of a particular public key (and has not been modified by anyone during transmission).

Cracking GPG

While GPG is relatively secure, it is of course not impossible to break it. There are two main cases for an attack on GPG, and fortunately both of them should be unreasonably difficult to crack, as will be discussed
below.

The first case is if an attacker were to intercept an encrypted message. There are currently no known shortcut attacks for either AES (the symmetric cipher we will choose to use), or RSA (the asymmetric cipher). This means that the attacker has three choices of how to proceed. Firstly, the attacker can try to brute force the AES encryption. Because the AES key is not generated from a password, this must be done directly and possibly weak passwords cannot be used as a shortcut. Assuming we use AES256 (a 256 bit key) this means the attacker must (according to probability) try 50% of the 2^256 possibilities (2^255 different keys) in order to find the correct one. To put this in perspective, the universe is estimated to be 13.7 billion years old, which is equivalent to a bit under 2^88.5 nanoseconds. So if we assume an attacker can check one possible key every nanosecond (which means they can check one billion keys per second) it would take them thousands of times longer than the universe has existed for. For this reason, 256 bit AES is generally considered to be too secure to effectively crack.

The second and third possible attacks are concerned with cracking the RSA key. The first of these possibilities is to simply try all the possible private keys, but as the RSA key is even longer than the AES key (4096 bits compared to 256 bits) this is generally considered to be impossible. The other possibility is to try and work out what the private key is from from the public key.

Fortunately this is also difficult. The private key consists of two very large prime numbers, which when multiplied together give us the public key, a number 4096 bits long (very very big). This means it is very easy to calculate the public key from a private key, but as much as it seems it would be easy to factorise the public key to find the private key, this is actually very hard to do. There are several known optimisations to factoring, but even with these optimisations the attacker still has to try almost every possible pair of factors in order to find the correct one, so this attack should still take a long time, and RSA is considered secure for the time being (see Quantum Attacks below).

The second case for an attack on GPG offers one other possible, much easier, method of attack. If an attacker has a copy of the file in which a user’s private key is stored (for example by having hacked into their computer) this allows an attack based on weak passwords. The private key is stored by GPG in a file which is symmetrically encrypted, but unlike the symmetric encryption in a message, this encryption is done using a key generated from the user’s passphrase. This means an attacker can try possibilities of the passphrase, in the hope that the user will have picked an easy to guess password. GPG employs several techniques to make this harder, including using a salt to prevent precomputed dictionary attacks (also known as rainbow tables) and using password strengthening in order to slow down a brute force attack. However, despite these measures, it is generally considered that if an attacker gets a copy of the file containing your private key, the security measures are there to buy you enough time to have your private key revoked, so that future messages will still be secure. However, providing you keep your computer secure (and in my case I keep my key on an encrypted partition as well) hopefully this should never be an issue.

Quantum Attacks

As mentioned earlier, the balance of power is currently firmly with the cryptographers rather than cryptanalysists. However, depending on how quickly quantum computing is developed this may change things. There is one particular algorithm for factorisation, which would only be possible to
implement on some very specialised quantum computers, and so is yet impossible to use. However, if it was to be implemented, it would make RSA useless, as it would allow public keys to be factorised (and thus RSA keys cracked) in the same amount of time it takes to use them. Fortunately however, it is unlikely that this will be possible for a long time, and so RSA is still considered secure for the time being.

Next Time

That concludes this lengthy articles on the methods behind, and the security of GPG. In my next article I plan to show you how to generate your own GPG key, and I will then attempt to demonstrate its use in the following articles. I hope you found this interesting, stay tuned for next time.

DO out.