**Example 2: Brute Force Search**

This adversary (call it A_{1}) 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 E_{0}. It then runs an exhaustive key search. The algorithm looks like this:

_{0}= oracle_query(0) for k in 0,1,...,256-1: if DES

_{k}(0) == E

_{0}: 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 E_{0}, and at most 256 of them will get examined in the DES keysearch. So the probability of A_{1} returning 1 is at most 2-8. That is:

Pr <= 2-8, so

Adv(A_{1}) = |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.

Read more about this topic: Advantage (cryptography), Examples

### Famous quotes containing the words force, brute and/or search:

“... what is especially insufferable in a woman is a restless, bold, domineering manner, for this manner goes against nature.... [ellipsis in source] No matter what her worth, no matter that she never forgets that she could be a man by virtue of her superiority of mind and the *force* of her will, on the outside she must be a woman! She must present herself as that creature made to please, to love to seek support, that being who is inferior to man and who approaches the angels.”

—Elisabeth-Felicite Bayle-Mouillard (1796–1865)

“Union may be strength, but it is mere blind *brute* strength unless wisely directed.”

—Samuel Butler (1835–1902)

“When a person doesn’t understand something, he feels internal discord: however he doesn’t *search* for that discord in himself, as he should, but searches outside of himself. Thence a war develops with that which he doesn’t understand.”

—Anton Pavlovich Chekhov (1860–1904)