Stream cipher attack
Encyclopedia
Stream cipher
s, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be very secure if used properly. However they are vulnerable to attack if certain precautions are not followed:
s are vulnerable to attack if the same key is used twice (depth of two) or more.
Say we send messages A and B of the same length, both encrypted using same key, K. The stream cipher produces a string of bits C(K) the same length as the messages. The encrypted versions of the messages then are:
where xor is performed bit by bit.
Say an adversary has intercepted E(A) and E(B). He can easily compute:
However xor is commutative and has the property that X xor X = 0 (self-inverse) so:
If one message is longer than the other our adversary just truncates the longer message to the size of the shorter and his attack will only reveal that portion of the longer message. In other words, if anyone intercepts two messages encrypted with the same key, they can recover A xor B, which is a form of running key cipher
. Even if neither message is known, as long as both messages are in a natural language, such a cipher can often be broken by paper-and-pencil methods. John Tiltman accomplished this with the Lorenz cipher
(TUNNY) in World War II
. With an average personal computer
, such ciphers can usually be broken in a matter of minutes. If one message is known, the solution is trivial.
Another situation where recovery is trivial is if traffic-flow security measures have each station sending a continuous stream of cipher bits, with null characters (e.g. LTRS in Baudot
) being sent when there is no real traffic. This is common in military communications. In that case, and if the transmission channel is not fully loaded, there is a good likelihood that one of the ciphertext streams will be just nulls. The NSA goes to great lengths to prevent keys being used twice. 1960s-era encryption systems often included a punched card
reader for loading keys. The mechanism would automatically cut the card in half when the card was removed, preventing its reuse.
One way to avoid this problem is to use an initialization vector
(IV), sent in the clear, that is combined with a secret master key to create a one-time key for the stream cipher. This is done in several common systems that use the popular stream cipher RC4
, including Wired Equivalent Privacy
(WEP), Wi-Fi Protected Access
(WPA) and Ciphersaber
. One of the many problems with WEP was that its IV was too short, 24 bits. This meant that there was a high likelihood that the same IV would be used twice if more than a few thousand packets were sent with the same master key (see birthday attack
), subjecting the packets with duplicated IV to the key reuse attack. This problem was fixed in WPA by changing the "master" key frequently.
, he can alter the content of the message without knowing the key, K. Say, for example, he knows a portion of the message, say an electronics fund transfer, contains the ASCII
string "$1000.00". He can change that to "$9500.00" by xor'ing that portion of the ciphertext with the string: "$1000.00" xor "$9500.00". To see how this works, consider that the cipher text we send is just C(K) xor "$1000.00". The new message the adversary is creating is:
xor "$1000.00") xor ("$1000.00" xor "$9500.00") = C(K) xor "$1000.00" xor "$1000.00" xor "$9500.00" = C(K) xor "$9500.00"
Recall that a string xor'ed with itself produces all zeros and that a string of zeros xor'ed with another string leaves that string intact. The result, C(K) xor "$9500.00", is what our ciphertext would have been if $9500 were the correct amount. See also: malleability (cryptography)
.
Bit-flipping attacks can be prevented by including message authentication code
to increase the likelihood that tampering will be detected.
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...
s, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be very secure if used properly. However they are vulnerable to attack if certain precautions are not followed:
- keys must never be used twice
- valid encryption should never be relied on to indicate authenticity
Reused key attack
Stream cipherStream 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...
s are vulnerable to attack if the same key is used twice (depth of two) or more.
Say we send messages A and B of the same length, both encrypted using same key, K. The stream cipher produces a string of bits C(K) the same length as the messages. The encrypted versions of the messages then are:
- E(A) = A xor C
- E(B) = B xor C
where xor is performed bit by bit.
Say an adversary has intercepted E(A) and E(B). He can easily compute:
- E(A) xor E(B)
However xor is commutative and has the property that X xor X = 0 (self-inverse) so:
- E(A) xor E(B) = (A xor C) xor (B xor C) = A xor B xor C xor C = A xor B
If one message is longer than the other our adversary just truncates the longer message to the size of the shorter and his attack will only reveal that portion of the longer message. In other words, if anyone intercepts two messages encrypted with the same key, they can recover A xor B, which is a form of running key cipher
Running key cipher
In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream...
. Even if neither message is known, as long as both messages are in a natural language, such a cipher can often be broken by paper-and-pencil methods. John Tiltman accomplished this with the Lorenz cipher
Lorenz cipher
The Lorenz SZ40, SZ42A and SZ42B were German rotor cipher machines used by the German Army during World War II. They were developed by C. Lorenz AG in Berlin. They implemented a Vernam stream cipher...
(TUNNY) in World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
. With an average personal computer
Personal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
, such ciphers can usually be broken in a matter of minutes. If one message is known, the solution is trivial.
Another situation where recovery is trivial is if traffic-flow security measures have each station sending a continuous stream of cipher bits, with null characters (e.g. LTRS in Baudot
Baudot code
The Baudot code, invented by Émile Baudot, is a character set predating EBCDIC and ASCII. It was the predecessor to the International Telegraph Alphabet No 2 , the teleprinter code in use until the advent of ASCII. Each character in the alphabet is represented by a series of bits, sent over a...
) being sent when there is no real traffic. This is common in military communications. In that case, and if the transmission channel is not fully loaded, there is a good likelihood that one of the ciphertext streams will be just nulls. The NSA goes to great lengths to prevent keys being used twice. 1960s-era encryption systems often included a punched card
Punched card
A punched card, punch card, IBM card, or Hollerith card is a piece of stiff paper that contains digital information represented by the presence or absence of holes in predefined positions...
reader for loading keys. The mechanism would automatically cut the card in half when the card was removed, preventing its reuse.
One way to avoid this problem is to use an initialization vector
Initialization vector
In cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...
(IV), sent in the clear, that is combined with a secret master key to create a one-time key for the stream cipher. This is done in several common systems that use the popular stream cipher 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...
, including Wired Equivalent Privacy
Wired Equivalent Privacy
Wired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
(WEP), Wi-Fi Protected Access
Wi-Fi Protected Access
Wi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
(WPA) and Ciphersaber
CipherSaber
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...
. One of the many problems with WEP was that its IV was too short, 24 bits. This meant that there was a high likelihood that the same IV would be used twice if more than a few thousand packets were sent with the same master key (see birthday attack
Birthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
), subjecting the packets with duplicated IV to the key reuse attack. This problem was fixed in WPA by changing the "master" key frequently.
Bit-flipping attack
Suppose an adversary knows the exact content of all or part of one of our messages. As a part of a man in the middle attack or replay attackReplay attack
A replay attack is a form of network attack in which a valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary who intercepts the data and retransmits it, possibly as part of a masquerade attack by IP packet...
, he can alter the content of the message without knowing the key, K. Say, for example, he knows a portion of the message, say an electronics fund transfer, contains the ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
string "$1000.00". He can change that to "$9500.00" by xor'ing that portion of the ciphertext with the string: "$1000.00" xor "$9500.00". To see how this works, consider that the cipher text we send is just C(K) xor "$1000.00". The new message the adversary is creating is:
xor "$1000.00") xor ("$1000.00" xor "$9500.00") = C(K) xor "$1000.00" xor "$1000.00" xor "$9500.00" = C(K) xor "$9500.00"
Recall that a string xor'ed with itself produces all zeros and that a string of zeros xor'ed with another string leaves that string intact. The result, C(K) xor "$9500.00", is what our ciphertext would have been if $9500 were the correct amount. See also: malleability (cryptography)
Malleability (cryptography)
Malleability is a property of some cryptographic algorithms. An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext...
.
Bit-flipping attacks can be prevented by including message authentication code
Message authentication code
In cryptography, a message authentication code is a short piece of information used to authenticate a message.A MAC algorithm, sometimes called a keyed hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC...
to increase the likelihood that tampering will be detected.