Distinguishing attack

Distinguishing attack

In cryptography, a distinguishing attack is any form of cryptanalysis where the attacker can extract some information from encrypted data sufficient to distinguish it from random data. This information might then reveal the encryption method used, some information about the encrypted message, or refine the potential key space.

To prove that a cryptographic function is safe, it is often compared to a random oracle. If a function would be a random oracle, then an attacker is not able to predict any of the output of the function. If a function is distinguishable from a random oracle, it has non-random properties. That is, there exists a relation between different outputs, or between input and output, which can be used by an attacker for example to find (a part of) the input.

Example Let T be a sequence of random bits, generated by a random oracle and S be a sequence generated by a pseudo-random bit generator. If two parties use an encryption system, which encrypts a message M of length n as the bitwise XOR of M and the next n bits of T or S. So the output of the encryption using T is truly random. Now if the sequence S can not be distinguished from T, the output of the encryption with S will appear random as well. If the sequence S is distinguishable, then the encryption of M with S may reveal information of M.

Two systems S and T are said to be indistinguishable if there exists no algorithm D, connected to either S or T, able to decide whether it is connected to S or T.

A distinguishing attack is given by such an algorithm D. It is broadly an attack in which the attacker is given a black box containing either an instance of the system under attack with an unknown key, or a random object in the domain that the system aims to emulate, then if the algorithm is able to tell whether the system or the random object is in the black box, one has an attack. For example, a distinguishing attack on a stream cipher such as RC4 might be one that determines whether a given stream of bytes is random or generated by RC4 with an unknown key. Classic examples of distinguishing attack on a popular stream cipher was by Itsik Mantin and Adi Shamir who showed that the 2nd output byte of RC4 was heavily biased toward zero [1]. In another example, Souradyuti Paul and Bart Preneel of COSIC have shown that the XOR value of the 1st and 2nd outputs of RC4 is also non-uniform. Significantly, both the above theoretical biases can be demonstrable through computer simulation[2].

See also

  • Randomness test

References

  1. ^ Itsik Mantin and Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152 – 164 (PS).
  2. ^ Souradyuti Paul and Bart Preneel, Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT 2003, pp52 – 67 (PDF).

External links



Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Attack — This unusual and interesting surname is of Anglo Saxon origin, and is from a topographical name for someone who lived near an oak tree or in an oak wood, derived from the Middle English (1200 1500) oke , oak, from the Olde English pre 7th Century …   Surnames reference

  • Collision attack — In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision. In contrast to a preimage attack, neither the hash value nor one of the inputs is… …   Wikipedia

  • Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

  • Brute force attack — In cryptanalysis, a brute force attack is a method of defeating a cryptographic scheme by trying a large number of possibilities; for example, possible keys in order to decrypt a message. In most schemes, the theoretical possibility of a brute… …   Wikipedia

  • Brute-force attack — The EFF s US$250,000 DES cracking machine contained over 1,800 custom chips and could brute force a DES key in a matter of days. The photograph shows a DES Cracker circuit board fitted with 32 Deep Crack chips and some control chips. In… …   Wikipedia

  • Py (cipher) — * Py is a stream cipher submitted to eSTREAM by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms. It has a structure a little like RC4, but adds an array of 260 32 bit… …   Wikipedia

  • Phelix — is a high speed stream cipher with a built in single pass message authentication code (MAC) functionality, submitted in 2004 to the eSTREAM contest by Doug Whiting, Bruce Schneier, Stefan Lucks, and Frédéric Muller. The cipher uses only the… …   Wikipedia

  • DFC — Шифрование Расшифрование Эта статья включает описание термина «DFC»; о значении Dfc см. Субарктический климат. DFC (Decorrelated Fast Cipher)  блочный симметричный криптоалгоритм, созданный в 1998 году совместно криптографами …   Википедия

  • Tiger (cryptography) — Tiger General Designers Ross Anderson and Eli Biham First published 1996 Detail Digest sizes 192, 128, 160 Rounds 24 In cryptography, Tiger is a …   Wikipedia

  • Variably Modified Permutation Composition — VMPC ( Variably Modified Permutation Composition ) is encryption technology designed by Bartosz Zoltak, publicly presented in 2004 at an international cryptography conference Fast Software Encryption in Delhi, India.The core of the technology is… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”