Distinguishing attack

Last updated

In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. [1] Modern symmetric-key ciphers are specifically designed to be immune to such an attack. [2] In other words, modern encryption schemes are pseudorandom permutations and are designed to have ciphertext indistinguishability. If an algorithm is found that can distinguish the output from random faster than a brute force search, then that is considered a break of the cipher.

Contents

A similar concept is the known-key distinguishing attack, whereby an attacker knows the key and can find a structural property in the cipher, where the transformation from plaintext to ciphertext is not random. [3]

Overview

To prove that a cryptographic function is safe, it is often compared to a random oracle. If a function were 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. Two parties use one encryption system to encrypt a message M of length n as the bitwise XOR of M and the next n bits of T or S respectively. The output of the encryption using T is truly random. Now, if the sequence S cannot 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.

Examples

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. [4] 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. [5]

See also

Related Research Articles

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

<span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

Articles related to cryptography include:

<span class="mw-page-title-main">Substitution–permutation network</span> Cipher design construction

In cryptography, an SP-network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Square.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, a cipher key made by random number generation is very unlikely to give rise to a security problem. Nevertheless, it is considered desirable for a cipher to have no weak keys. A cipher with no weak keys is said to have a flat, or linear, key space.

CipherSaber is a simple symmetric encryption protocol based on the RC4 stream cipher. Its goals are both technical and political: it gives reasonably strong protection of message confidentiality, yet it's designed to be simple enough that even novice programmers can memorize the algorithm and implement it from scratch. According to the designer, a CipherSaber version in the QBASIC programming language takes just sixteen lines of code. Its political aspect is that because it's so simple, it can be reimplemented anywhere at any time, and so it provides a way for users to communicate privately even if government or other controls make distribution of normal cryptographic software completely impossible.

In cryptography, MUGI is a pseudorandom number generator (PRNG) designed for use as a stream cipher. It was among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003, however, has been dropped to "candidate" by CRYPTREC revision in 2013.

Bart Preneel is a Flemish cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group.

In cryptanalysis, attack models or attack types are a classification of cryptographic attacks specifying the kind of access a cryptanalyst has to a system under attack when attempting to "break" an encrypted message generated by the system. The greater the access the cryptanalyst has to the system, the more useful information they can get to utilize for breaking the cypher.

<span class="mw-page-title-main">One-way compression function</span> Cryptographic primitive

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.

In cryptography, the Fluhrer, Mantin and Shamir attack is a stream cipher attack on the widely used RC4 stream cipher. The attack allows an attacker to recover the key in an RC4 encrypted stream from a large number of messages in that stream.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

VMPC for cryptography is a stream cipher similar to the well known and popular cipher RC4 designed by Ron Rivest. It was designed by Bartosz Żółtak, presented in 2004 at the Fast Software Encryption conference. VMPC is a modification of the RC4 cipher.

<span class="mw-page-title-main">Xor–encrypt–xor</span>

The xor–encrypt–xor (XEX) is a (tweakable) mode of operation of a block cipher. In tweaked-codebook mode with ciphertext stealing, it is one of the more popular modes of operation for whole-disk encryption. XEX is also a common form of key whitening, and part of some smart card proposals.

References

  1. ↑ Meier, Willi; Kunzli, Simon (2005). "Distinguishing Attack on MAG" (PDF). ENCRYPT Stream Cipher Project. eSTREAM. Retrieved 8 February 2013.
  2. ↑ Leonid Reyzin (2004). "Symmetric Cryptography" (PDF). Lecture Notes for Boston University CAS CS 538: Fundamentals of Cryptography.
  3. ↑ Elena Andreeva; Andrey Bogdanov; Bart Mennink (8 July 2014). Towards Understanding the Known-Key Security of Block Ciphers. FSE 2014.
  4. ↑ Itsik Mantin and Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152 – 164 (PS) Archived June 12, 2011, at the Wayback Machine .
  5. ↑ Souradyuti Paul and Bart Preneel, Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT 2003, pp52 – 67 (PDF).
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.