Distinguishing attack
Encyclopedia
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 . 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a distinguishing attack is any form of cryptanalysis
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
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
Key space
In cryptography, an algorithm's key space refers to the set of all possible keys that can be used to initialize it. For example, if an algorithm works using a key that is a string of 10 bits, then its key space is the set of all binary strings of length 10. i.e...
.
To prove that a cryptographic function is safe, it is often compared to a random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
. 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
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
. 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
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
such as RC4
RC4
In cryptography, RC4 is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer and WEP...
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
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
who showed that the 2nd output byte of RC4 was heavily biased toward zero . In another example, Souradyuti Paul
Souradyuti Paul
Souradyuti Paul is an Indian cryptologist . Formerly a member of COSIC, he is currently working as a Guest Researcher for the National Institute of Standards and Technology in the United States...
and Bart Preneel
Bart Preneel
Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group, president of the International Association for Cryptologic Research, and project manager of ECRYPT....
of COSIC
COSIC
The Computer Security and Industrial Cryptography research group, commonly called COSIC, is a research group at the Department of Electrical Engineering of the Katholieke Universiteit Leuven, which is headed by Professor Bart Preneel, Vincent Rijmen, and Professor Ingrid Verbauwhede.The goal of...
have shown that the XOR value of the 1st and 2nd outputs of RC4
RC4
In cryptography, RC4 is the most widely used software stream cipher and is used in popular protocols such as Secure Sockets Layer and WEP...
is also non-uniform. Significantly, both the above theoretical biases can be demonstrable through computer simulation.
External links
- Source
- [ftp://ftp.inf.ethz.ch/pub/crypto/publications/MaReHo04.pdf Indifferentiability]