TenMinuteTutor

Programming tutorials

Attacks on symmetric ciphers

There are many techniques which can be used to try to attack symmetric encryption. Here we divide them into several main classes. Before that, it is worth considering what the attacker might be trying to achieve, and what level of access he might have to the cryptography system.

The purpose of an attack

If an attacker can find a way of examining a message, and somehow working out what key was used to encrypt it (key recovery) then he has totally broken the algorithm - he can decrypt any message you send, and can also encrypt any message of his own using your key. However, sometimes attacks which only partially break the encryption are still potentially useful to an attacker. In order of severity:

  • Recognising a message (or part of a message) which has been seen before. This can leak some useful information as the attacker might notice that a particular message is always sent before a particular event occurs. Using [[data formats:cryptography:Cryptographic modes|CBC mode]] often solves this problem.
  • Decoding some parts of some messages. This leaks some information, and the attacker might be able to guess the blanks and decrypt the entire message. See dictionary attacks, below
  • Decrypting a particular message, either by good fortune or a lot of effort, but without discovering anything which makes it easier to decrypt other messages.
  • Finding a method to decode all messages easily, but without discovering their key.
  • Key recovery.

Levels of Access

In some cases, the attacker might only have access to the encrypted message (ciphertext), and has nothing else to go on. Breaking encryption under such circumstances is as difficult as it can be. In other cases, a system might make more information available to an attacker.

It is sometimes possible for the attacker to have access to an encrypted messages and the corresponding unencrypted message (the plaintext). Having both parts of the message might help him gain information which can be used to help crack subsequent messages encrypted with the same key.

It would be even better for the attacker if he can choose the plaintext and get to see the encrypted result, or better still if he could do this over and over, each time choosing a new plaintext based on the previous result. He could then hone in on any weaknesses of the algorithm.

Brute Force Attacks

Brute force is an attempt to crack an encrypted message by trying every possible key until you find one which works, ie the encrypted data makes sense after decryption. Any encryption method can be broken in this way, given a powerful enough computer. This attack only requires a relatively short piece of cipertext, and can result in key recovery if successful. That is, this algorithm requires the minimum amount of information to produce the most devatasting reult.

However, things are not as bad as they seem. The basic defence against a brute force is to use a long key, so that the number of possible keys becomes far too large to be able to check them all. Most modern algorithms use 128 bit keys (or longer), and there is little chance of cracking this by brute force with any computer which will be available in the forseeable future.

If there was a computer powerful enough to mount a brute force attack, then the would-be attacker needs to find a way of checking the plaintext produced by each candidate key, to detect which one looks like a proper message. Given the vast number of keys, the check needs to be automatic. If the type of data is known, for example it is known to be a text message, then it is reasonably easy to look for characteristics of the data. If the type of data is unknown, then it is necessary to perfrom a statistical test on the message - meaningful messages tend to have less entropy (ie they are less random, and more ordered). A message decoded with the wrong key is almost certain to be highly random in nature.

It is also possible to examine the start of the message to see if it resembles the data header of any known data format. This is useful if the data is possibly compressed, as compressed data is very random in nature.

In any case, as things currently stand, technology is so far away from any possibility of mounting a brute force attack that there is little point in worrying about exactly how to do it.

Dictionary Attacks##

A dictionary attack tries to crack the encryption by building up a dictionary, matching encrypted blocks with their plaintext counterparts. This can be a difficult attack to mount because the attacker needs to be able to obtain large amounts of matching plaintext and ciphertext in order to build up the dictionary. He also needs a vast amount of storage to hold the dictionary.

This can still be a powerful attack, because a partially complete dictionary can be used to partially decode messages. In a situation where the data is fairly repetitive, then it might be that relatively few unique data blocks are used in most messages, and an attacker could glean valuable information from a fairly sparse dictionary.

One defence against this attack is to use a large enough block size, so that it becomes infeasible to create a large enough dictionary. Interestingly, the key length is insignificant to this type of attack. In theory you could build up the encryption but still not even know the key. This defence does not always work in a situation where you are encrypting very repetitive, structured data.

A better defence is [[data formats:cryptography:Cryptographic modes|CBC]] mode encryption. Typically a modern algorithm has a large block size and uses CBC as well.

Cryptanalysis

Cryptanalysis can be used to try to crack strong encryption by finding weaknesses in specific algorithms. An attacker might be lucky enough to find some clever shortcut which renders the algorithm completely useless overnight (such things have happened). However this is quite unlikely to happen with any well respected modern algorithm, because so many experts have tried and failed to crack these algorithms.

Cryptanalysis may throw up more subtle flaws. For example, by analysing a number of matching plaintext/ciphertext blocks, an attacker might be able to derive some information about the key. This in turn might make a brute force attack easier.

The best defence against this type of attack is to use a tried and tested algorithm (at the moment, Rijndael is the best choice for most applications).

You might think it would be safer to invent your own algorithm, and then keep the algorithm secret, in order to make cryptanalysis more difficult. Unfortunately it is almost impossible to keep an algorithm secret once it has been deployed. Any determined attacker will be able to reverse engineer software or hardware, or somehow obtain information on how it works. It is difficult enough to keep a 128 bit key secret, let alone an ecryption algorithm. As soon as your algorithm becomes known, you have to ask whether you algorithm (which has only ever been analysed by your small trusted team) is actually as good as Rijndael (which has been analysed by every cryptographer on the planet).

The Human Factor

The final class of attacks exploits the human factor. This is by far the major weakness in many systems, and often allows attackers to obtain keys directly. In the human domain, we tend to think of passowrds rather than keys, but they amount to the same thing. Attacks include:

  • Password guessing. Naive users often choose easily guessable passwords, or write down their passwords where they can be found by others.
  • Spying on a legitimate user as he enters his password. This is sometimes done using keystroke logging software which has been surreptitiously installed on the system. A less sophisticated method is simply looking over someone’s shoulder as they type.
  • Spoofing or “phishing”. Here the attacker attempts to convince the user that he has a legitimate need to know their password. This might be done by a spoofed phone call, email or a website made to appear genuine and requesting the password.
  • Bribery. Staff may also deliberately hand over a password for a bribe, or because they have a grievance with their employer, or due to some ideological affiliation.
  • Force and intimidation. In the most extreme cases, the attacker might resort to threat, blackmail, kidnap or torture to obtain a password.