Advantage (cryptography)


Advantage (cryptography)

In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person. A cryptographic algorithm is considered secure if no adversary has a non-negligible advantage, subject to specified bounds on the adversary's computational resources (see concrete security). "Negligible" usually means "within O(2-p)" where p is a security parameter associated with the algorithm. For example, p might be the number of bits in a block cipher's key.

Description of concept

(to be expanded)

Let F be an oracle for the function being studied, and let G be an oracle for an idealized function of that type. The adversary A is a probabilistic algorithm given F or G as input and which outputs 1 or 0. A's job is to distinguish F from G based on making queries to the oracle that it's given. We say:Adv(A) = |Pr [A(F)=1] - Pr [A(G)=1] |

Examples

Let F be a random instance of the DES block cipher. This cipher has 64-bit blocks and a 56-bit key. The key therefore selects one of a family of 256 permutations on the 264 possible 64-bit blocks. A "random DES instance" means our oracle F computes DES using some key K (which is unknown to the adversary) where K is selected from the 256 possible keys with equal probability.

We want to compare the DES instance with an idealized 64-bit block cipher, meaning a permutation selected at random from the (264)! possible permutations on 64-bit blocks. Call this randomly selected permutation G. Note from Stirling's approximation that (264)! is around 10^{3.47 imes 10^{20, so even specifying which permutation is selected requires writing down a number too large to represent exactly in any real computer. Viewed another way, G is an instance of a "cipher" whose "key length" is about 1021 bits, which again is too large to fit in a computer. (We can, however, implement G with storage space proportional to the number of queries, using a random oracle).

Note that because the oracles we're given encrypt plaintext of our choosing, we're modelling a chosen-plaintext attack or CPA, and the advantage we're calculating can be called the CPA-advantage of a given adversary. If we also had decryption oracles available, we'd be doing a chosen-ciphertext attack or CCA and finding the CCA-advantage of the adversary.

We'll look at several different adversaries and see how they perform.

Example 1: guess at random

We'll call this adversary A0. It simply flips a coin and returns 1 or 0 with equal probability and without making any oracle calls. Thus, Pr [A0(F)=1] and Pr [A0(G)=1] are both 0.5. The difference between these probabilities is zero, so Adv(A0) is zero. The same thing applies if we always return 0, or always return 1: the probability is the same for both F and G, so the advantage is zero. This adversary can't tell F and G apart. If we're cipher designers, our desire (maybe not achievable) is to make it so that it's computationally infeasible for "any" adversary to do significantly better than this. We will have succeeded if we can make a cipher for which there's no distinguisher faster than 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 [A1(F)=1] = 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 [A1(G)=1] <= 2-8, so

Adv(A1) = |Pr [A1(F)=1] - Pr [A1(G)=1] | >= 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--because it "is" brute force search.

Example 3: RC4 Stream Cipher (Fluhrer-McGrew attack)

TBD

References

Phillip Rogaway and Mihir Bellare, [http://www-cse.ucsd.edu/~mihir/cse207/classnotes.html Introduction to Modern Cryptography]

Oded Goldreich, [http://theory.lcs.mit.edu/~oded/frag.html Foundations of Cryptography (Fragments of a Book)]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Cryptography in Japan — There is not much cryptological history in Japan prior to the twentieth century, only a few simple codes were used and there seems to have been no practice of cryptanalysis at all.There seems to be almost no cryptology in Japan before the Warring …   Wikipedia

  • Quantum cryptography — Quantum cryptography, or quantum key distribution (QKD), uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random bit string known only to them, which can be used as a key to encrypt and decrypt… …   Wikipedia

  • Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… …   Wikipedia

  • Public-key cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key …   Wikipedia

  • Neural cryptography — is a branch of cryptography dedicated to analyzing the application of stochastic algorithms, especially neural network algorithms, for use in encryption and cryptanalysis. Contents 1 Definition 2 Applications 3 Neural key e …   Wikipedia

  • Magic (cryptography) — Magic was an Allied cryptanalysis project during World War II. It involved the United States Army s Signals Intelligence Section (SIS) and the United States Navy s Communication Special Unit. [1] Contents 1 Codebreaking 1.1 RED …   Wikipedia

  • Adversary (cryptography) — In cryptography, an adversary (rarely opponent, enemy) is a malicious entity whose aim is to prevent the users of the cryptosystem from achieving their goal (primarily privacy, integrity and availability of data). An adversary s efforts might… …   Wikipedia

  • Trace Zero Cryptography — In the year 1998 Gerhard Frey firstly purposed using trace zero varieties for cryptographic purpose. These varieties are subgroups of the divisor class group on a low genus hyperelliptic curve defined over a finite field. These groups can be used …   Wikipedia

  • Network Security & Cryptography — is a concept to protect our network and data transmission over wireless network. Data Security is the main aspect of secure data transmission over unreliable network. Data Security is a challenging issue of data communications today that touches… …   Wikipedia

  • asymmetric cryptography — noun cryptography in which the key used in decryption is different from that used for encryption. One advantage of asymmetric cryptography is that you can exchange data without sharing the ability to read it …   Wiktionary