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.
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 (17961865)
“Union may be strength, but it is mere blind brute strength unless wisely directed.”
—Samuel Butler (18351902)
“When a person doesnt understand something, he feels internal discord: however he doesnt search for that discord in himself, as he should, but searches outside of himself. Thence a war develops with that which he doesnt understand.”
—Anton Pavlovich Chekhov (18601904)