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.

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)