# Advantage (cryptography) - Examples - Example 2: Brute Force Search

Example 2: Brute Force Search

This adversary (call it A1) will attempt to cryptanalyze its input by brute force. It has its own DES implementation. It gives a single query to its oracle, asking for the 64-bit string of all zeroes to be encrypted. Call the resulting ciphertext E0. It then runs an exhaustive key search. The algorithm looks like this:

E0 = oracle_query(0) for k in 0,1,...,256-1: if DESk(0) == E0: return 1 return 0

This searches the entire 56-bit DES keyspace and returns "1" if it probably finds a matching key. In practice, several plaintexts are required to confirm the key, as two different keys can result in one or more matching plaintext-ciphertext pairs. If no key is found, it returns 0.

If the input oracle is DES, this exhaustive search is certain to find the key, so Pr = 1. If the input oracle is a random permutation, there are 264 possible values of E0, and at most 256 of them will get examined in the DES keysearch. So the probability of A1 returning 1 is at most 2-8. That is:

Pr <= 2-8, so

Adv(A1) = |Pr - Pr| >= 1 - 2-8

so the advantage is at least about 0.996. This is a near-certain distinguisher, but it's not a security failure because it's no faster than brute force search, after all, it is the brute force search.