Brute Force Attack

Brute Force Attack, aka Exhaustive Key Search, is a #Cryptanalysis technique that attempts to obtain an intelligible plaintext by trying every possible key on a piece of ciphertext. On average, \(\frac{N}{2}\) number of keys must be tried before a success, where \(N\) annotates the total number of possible keys. Therefore, we know that the time used by Brute Force Attack is proportional to the key size: the larger the key size, the longer the time taken to crack the algorithm.

For example, suppose the key size used is 32 bits. The total number of possible keys should be \(2^{32}\), and it requires \(\frac{2^{32}}{2} = 2^{32 - 1} = 2^{31}\) attempts on average. Assume that the speed to decrypt is 1 decryption per µs, it will be \(2^{31}\) µs \(= 2^{31} \times 10^{-6}\) s \(= 2^{31} \times 10^{-6} \div 60\) min, which is \(35.79\) minutes. If the speed to decrypt increased to \(10^6\) decryption per µs, it will be \(\frac{2^{31}}{10^6}\) µs \(= 2^{31} \times 10^{-6 - 6}\) s \(= 2^{31} \times 10^{-12}\) s \(= 2.147 \times 10^{-3}\) s or \(2.147\) ms.

If a #Cryptanalysis could crack an encryption scheme with an attempts less than of the Brute Force Attack, then it is considered to be a Cryptanalytic Attack on the scheme.

Links to this page

Vigenère Cipher

However, Vigenère Cipher not entirely secure as the key could be repeated thus make it vulnerable to Frequency Analysis if there is too many repetitions. Another way to attack it is by guessing the number of alphabets being used, and then attack by brute force. If the key is too short, then it is easy to break with Kasiski Method#.
TAC3121 Chapter 1: Introduction

Brute Force Attack
Shift Cipher

Since there is only 25 possible ciphers (English alphabets), it is vulnerable to Brute Force Attack#.
Rivest-Shamir-Adleman (RSA)

The security of RSA is guarantee by its Trapdoor One-Way Function# nature as primes \(p\) and \(q\) are only known to the key owner. It is impossible to do a Brute Force Attack on RSA due to the large key size. Other Cryptanalytic Attack such as mathematical attack based on difficulty of computing \(\phi(n)\), by factoring modulus \(n\) (can be overcome by having a larger \(n\)), timing attacks# on decryption algorithm, and chosen ciphertext attacks (CCA) can be done on RSA.
Permutation/Transposition Cryptography

A Cryptanalytic Attack done on Permutation/Transposition Cryptographic algorithm is by first guessing period, try all possible permutation on the period (Brute Force Attack), search for common patterns and then use lists of common diagrams and trigrams (Frequency Analysis#).
Message Authentication Code (MAC)

Note: To crack the key, see Brute Force Attack.
Data Encryption Standard (DES)

DES encrypts 64-bit of data using 56-bit key, which has been criticised of having poor security due to the small key size, making it vulnerable to possible Brute Force Attack. Analytic Attacks are possible to crack DES. Other than that, smart-card implementation of DES is susceptible to Timing Attack.
Cryptanalysis

Brute Force Attack#
Analytic Attacks

Analytic Attacks is a #Cryptanalytic Attack utilising the encryption information gathered before carrying out attack to recover some or all subkey bits and if necessary involving Brute Force Attack#. They are generally categorised as statistical attacks.

#security