Brute Force Attack
As the name suggests, “Brute Force Attack”, the process is based on testing all possible keys until find the correct key. Let’s consider that the attacker finds out the correct key after trials.
We have 4 keys such as, k_1-(00), k_2-(01), k_3-(10), k_4-(11) where information entropy of the system is 2 bits (1 of the 4 keys is the correct key).
https://cryptoquantus.com/2019/07/28/information-entropy/ Take a look at simplified information entropy article.
The attacker tries the first key and realizes that it is false. Now, system’s information entropy is log_2 (which is appr. 1.58). So, even if the attacker tries the wrong key, the probability of finding the right key is increasing. Moreover, information entropy of the system is decreasing whenever the attacker tries a key. Hence, the strength of the key is related to information entropy and the attacker’s effort.
As a result, with “n” bits long keys, there are 2^[n] possible keys to crack for the attacker. If the attacker succeeds in the first attack – it would be the best case – or last try – after 2^[n] tries. So, on average, there are 2^[n-1] possible keys for the attacker to try.
Basically, relies on studying and analyze the crypto-system in order to decipher the message without the key. The non-uniform key selection yields entropy reduction. Attacker may know which key(s) are more feasible than others.
In WW2, the nazis encrypted communication was provided with unbreakable enigma machine. Alan Turing and his crew noticed the most repeated word “heil hitler” and changed the history of the world. This might be the one of the most important events in the history of crypto-analysis.
In order to provide perfect crypto-system, ciphertext shouldn’t provide any information about the plaintext i.e. cryptanalytically unbreakable. One-time pad achieves perfect secrecy. The entropy is great as the message entropy, even as the message grows. There are two practical challenges such as, key and randomness generation and key distribution and agreement. Especially used during the Russian – American cold war.
Resources: https://www.scienceabc.com/innovation/cracking-the-uncrackable-how-did-alan-turing-and-his-team-crack-the-enigma-code.html — https://www.lri.fr/~fmartignon/documenti/systemesecurite/3-OneTimePad.pdf — https://d3c33hcgiwev3.cloudfront.net/_e4baa6d289359be9186e344fc5cbedcd_slides_brute_force_and_cryptanalysis.pdf?Expires=1565136000&Signature=ZneTnV3Tux14qRglguD-0X1858yQoZxv0IyAqGpg1qg3Wfml3sCtGJHmAJc5MXmFJ5ipLWYa~jsBHCKSg6nQ~E0MWZ4T6owST4GWljvU-0vT24JrZQKFF7mkqAt6RlZTIOddvupqaHNs1x0iWluAOIaHoO1T2nlnRPLsXN18B1Q_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A by Sang-Yoon Chang, Ph.D. —