In cryptography, the goal of the attacker is to break the secrecy of the encryption and learn the secret message and, even better, the secret key. There are dozens of different types of attacks that have been developed against different types of cryptosystems with varying levels of effectiveness. Some are easily understandable while others may require an advanced degree in mathematics to comprehend. In this post, we'll be discussing some of the more common attacks and why they may or may not work against different types of ciphers.
The simplest attack on a cipher is the brute force attack. In this attack, an attacker simply tries to decrypt the message with each possible secret key and checks the result of the decryption to see if it makes sense. Given enough time and computational resources, this attack is guaranteed to work since the true secret key has to be within the set of possible secret keys and the attacker will eventually try it and (hopefully) realize that the resulting plaintext is the correct one.
Modern ciphers protect themselves against brute force attacks by using a secret key that is long enough to make guessing all of the possibilities impossible. For example, the longest available key length of the AES cipher (described in another post) is 256 bits, which means there are 2256 possible AES keys. By contrast, there are an estimated 2266 atoms in the observable universe. Needless to say, no existing computer can search that size of a keyspace in a reasonable amount of time.
The Man-in-the-Middle (MitM) attack assumes that an attacker, Eve, can insert herself in the communication channel between Alice and Bob, who are trying to talk to one another. When Alice sends a message to Bob, Eve intercepts it before it reaches him. In a successful MitM attack, Eve can decrypt the intercepted message, read and possibly modify it, and then pass it on to Bob.
To pull off a Man-in-the-Middle attack, Eve typically needs to be able to convince Alice that Eve is Bob and Bob that Eve is Alice. Eve will then independently establish a separate secret key with each party and, when a message is moving from Alice to Bob, decrypts using her key for Alice and reencrypt using her key for Bob. As long as Eve controls the only communication channel between Alice and Bob, the MitM attack is undetectable.
A replay attack is when an attacker replays a valid session between a legitimate user and some form of server. In this attack, Eve captures every piece of traffic between the user, Alice, and the server, Bob, during normal operation. Later, the attacker resends the first piece of traffic and waits for Bob's response before sending the next piece, and so on. If Bob does not implement some protection against replay attacks, Eve may be able to achieve a valid session with Bob while masquerading as Alice.
For example, assume that Alice is buying something from Bob's online store. The entire transaction process is encrypted, but Eve is able to make a copy of each stage of the communication between Alice and Bob. At the end of Alice's transaction, she has successfully purchased one bicycle. Now, Eve can begin to replay Alice's session with Bob. From Bob's perspective, Eve is actually Alice purchasing another bicycle from his store. Eve does not need to decrypt any of the traffic to perform a replay attack or even know what is going on, but she does have the ability to cause issues for Alice by draining her bank account or credit card and causing a large number of bicycles to arrive at her residence.
To protect against replay attacks, many people who use ciphers in daily life (like Bob's store) will generate a random number to be included in each session. This way, if Bob sends the number to Alice and Alice sends it back, Bob can check that it is the expected number for the given session. When Eve attempts to replay Alice's session, she will provide the random number from Alice's session rather than the number for her replayed session and Bob will reject the transaction.
Side-channel attacks are attacks that use unintended side effects of cryptographic operations to glean information about the plaintext and/or secret key being processed. In the two types of attacks described here, the electrical power used by a computer while performing encryption/decryption and the time it takes to perform these operations are used to help determine the secret key.
Computers need power to run. The amount of power used and how long the power is used for can vary based upon the operations performed. When a cryptographic algorithm is being run on a computer, this may reveal information about the data being processed by the algorithm.
An example of a power analysis attack on a cryptographic algorithm is Simple Power Analysis (SPA) of the RSA algorithm. In the RSA algorithm, the secret key is used as the power in an exponentiation operation. A simple way of performing this step is using the square-and-multiply algorithm. In square-and-multiply, the exponent (secret key) is represented in binary and walked through from most significant bit to least significant bit. If a bit is a zero, the current value is squared. If a bit is a one, the current value is squared and then multiplied by the base.
The difference between the operations performed for a zero bit and a one bit in the secret key makes a side-channel attack on this version of RSA possible. The Figure above shows a power trace of a computer running an RSA operation. The rise on the left indicates a squaring operation (a bit value of zero) while the rise on the right indicates a square and multiple operation (a bit value of one) since it is longer than the left one. Given the power trace of an RSA implementation using square-and-multiply and no protections, it is possible to read the value of the secret key off of the image.
A timing attack on a cryptographic algorithm exploits the fact that the algorithm may take different amounts of time to run with different plaintexts or secret keys.
An example of a timing attack is the checking of a password during login to a secure system. Unprotected systems will incrementally check each character of the password for a match against the stored password and return failure immediately upon discovering mismatched characters. An attacker can try passwords starting with each of the possibilities for the first character of the password and select the option with the longest execution time (since it is the only case where the second character was also checked). By repeating this process one character at a time, the complete password can be built by the attacker.