Stream cipher attacks: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
← Previous edit
VisualWikitext
imported>BossyPirate
→Chosen-IV attack: Expanded the "Chosen-IV attack" section with technical details, examples, and references from reliable academic sources (Springer, IET, ECRYPT).
imported>Expert700
polished it for encyclopedic tone, readability, and consistency
 
Line 5: Line 5:
}}
}}


[[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.{{citation needed|date=July 2019}} However, they are vulnerable to attacks if certain precautions are not followed:
[[Stream cipher]]s, where [[plaintext]] bits are combined with a cipher bit stream by an exclusive-or operation ([[xor]]), can be secure if used properly.{{citation needed|date=July 2019}} However, they are vulnerable to attacks if certain precautions are not followed:


*keys must never be used twice
* Keys must never be reused.
*valid decryption should never be relied on to indicate authenticity
* Valid decryption should never be relied on to indicate authenticity.


==Reused key attack==
==Reused key attack==
[[Stream cipher]]s are vulnerable to attack if the same key is used twice (depth of two) or more.
[[Stream cipher]]s are vulnerable to attack if the same key is used more than once (a depth of two or greater).


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:
Suppose messages ''A'' and ''B'' of the same length are both encrypted using the same key, ''K''. The stream cipher produces a string of bits ''C(K)'' of the same length as the messages. The encrypted versions of the messages are:


:''E(A) = A xor C''
:''E(A) = A xor C''
:''E(B) = B xor C''
:''E(B) = B xor C''


where ''xor'' is performed bit by bit.
where ''xor'' is performed bit by bit.


Say an adversary has intercepted ''E(A)'' and ''E(B)''.  They can easily compute:
If an adversary intercepts ''E(A)'' and ''E(B)'', they can compute:


:''E(A) xor E(B)''
:''E(A) xor E(B)''


However, ''xor'' is [[commutative]] and has the property that ''X xor X = 0'' (self-inverse) so:
Because ''xor'' is [[commutative]] and has the property that ''X xor X = 0'' (self-inverse):
 
:''E(A) xor E(B) = (A xor C) xor (B xor C) = A xor B xor C xor C = A xor B''
:''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 their 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. During [[World War II]], British cryptanalyst [[John Tiltman]] accomplished this with the [[Lorenz cipher]] (dubbed "Tunny"). 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.
If one message is longer than the other, the adversary can truncate the longer message to the size of the shorter one, revealing only that portion. In other words, if two messages are encrypted with the same key, an attacker can recover ''A xor B'', which is a form of [[running key cipher]]. Even if neither message is known, as long as both are in a natural language, such a cipher can often be broken by hand methods. During [[World War II]], British cryptanalyst [[John Tiltman]] accomplished this with the [[Lorenz cipher]] (dubbed "Tunny"). With an average [[personal computer]], such ciphers can usually be broken in 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 code|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 from 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.<ref>[https://www.nsa.gov/about/_files/cryptologic_heritage/publications/misc/tsec_kw26.pdf Securing Record Communications: The TSEC/KW-26] {{Webarchive|url=https://web.archive.org/web/20121010011445/https://www.nsa.gov/about/_files/cryptologic_heritage/publications/misc/tsec_kw26.pdf |date=2012-10-10 }}, Melville Klein, NSA history series</ref>{{rp|p. 6}}
Another situation where recovery is trivial is when [[traffic-flow security]] measures require each station to send a continuous stream of cipher bits, with null characters (e.g. ''LTRS'' in [[Baudot code|Baudot]]) transmitted when there is no real traffic. This is common in military communications. In that case, if the transmission channel is not fully loaded, there is a high likelihood that one of the ciphertext streams will consist only of nulls. The [[NSA]] has taken extensive measures to prevent keys from being reused. In the 1960s, encryption systems often included a [[punched card]] reader for loading keys. The mechanism would automatically cut the card in half when it was removed, preventing reuse.<ref>[https://www.nsa.gov/about/_files/cryptologic_heritage/publications/misc/tsec_kw26.pdf Securing Record Communications: The TSEC/KW-26] {{Webarchive|url=https://web.archive.org/web/20121010011445/https://www.nsa.gov/about/_files/cryptologic_heritage/publications/misc/tsec_kw26.pdf |date=2012-10-10 }}, Melville Klein, NSA history series</ref>{{rp|p. 6}}


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.
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 systems that use the popular stream cipher [[RC4]], including [[Wired Equivalent Privacy]] (WEP), [[Wi-Fi Protected Access]] (WPA), and [[Ciphersaber]]. One of the problems with WEP was that its IV was too short (24 bits). This meant there was a high likelihood that the same IV would be reused if more than a few thousand packets were sent with the same master key (see [[birthday attack]]), subjecting those packets to the key reuse attack. This problem was addressed in WPA by changing the "master" key frequently.


==Bit-flipping attack==<!-- This section is linked from [[Man-in-the-middle attack]] -->
==Bit-flipping attack==<!-- This section is linked from [[Man-in-the-middle attack]] -->
{{main|Bit-flipping attack}}
{{main|Bit-flipping attack}}
{{see also|Malleability (cryptography)}}
{{see also|Malleability (cryptography)}}
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 attack]], they can alter the content of the message without knowing the key, ''K''. Say, for example, they know a portion of the message, say an electronics fund transfer, contains the [[ASCII]] string ''"$1000.00"''. They can change that to ''"$9500.00"'' by XORing 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:
Suppose an adversary knows the exact content of all or part of a message. As part of a [[man in the middle attack]] or [[replay attack]], they can alter the content without knowing the key, ''K''. For example, if they know a portion of the message contains the [[ASCII]] string ''"$1000.00"'', they can change it to ''"$9500.00"'' by XORing that portion of the ciphertext with the string: ''"$1000.00" xor "$9500.00"''.   
 
:''(C(K) 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 [[Exclusive or|XORed]] with itself produces all zeros and that a string of zeros XORed 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.
The ciphertext being sent is ''C(K) xor "$1000.00"''. The adversary creates a new message:


Bit-flipping attacks can be prevented by including [[message authentication code]] to increase the likelihood that tampering will be detected.
:''(C(K) 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"''


== Chosen‑IV attack ==
Since a string [[Exclusive or|XORed]] with itself produces all zeros, and a string of zeros XORed with another string leaves that string unchanged, the result ''C(K) xor "$9500.00"'' is what the ciphertext would have been if $9500 were the original amount.
In a '''chosen‑IV attack''', an attacker is allowed to select or influence the initialization vectors (IVs) used in multiple sessions with the same secret key. By carefully choosing IVs and analyzing the resulting keystreams, the attacker may identify biases or algebraic relations that leak information about the key. This can effectively reduce the cipher’s security through distinguishing or key‑recovery attacks using statistical differentials or Boolean function analysis.<ref name="Rathgeb2018"/>


=== General form ===
Bit-flipping attacks can be prevented by including a [[message authentication code]], which increases the likelihood that tampering will be detected.
Stream ciphers are often viewed as a black‑box function taking key, IV, and counter to produce keystream bits. In chosen‑IV setups, the key remains fixed while IVs are varied—a scenario exploited in many attacks on [[eSTREAM]] ciphers. Statistical tests, including analysis of Algebraic Normal Form (ANF), can reveal non‑random structure in the output for particular IV patterns.<ref name="Rathgeb2018"/>


=== Examples ===
==Chosen-IV attack==
* '''WG cipher''': Wu & Preneel (2005) demonstrated a differential-style attack on the hardware‑oriented WG cipher. By querying ≈2^31.3 specially‑chosen IV pairs, one can recover ≈48 bits of an 80‑bit key; similar attacks apply to larger key/IV sizes.<ref name="Wu2005">{{cite conference |last=Wu |first=B. |last2=Preneel |first2=B. |title=Chosen-IV Attack against the Stream Cipher WG |conference=Fast Software Encryption |year=2005 |pages=216–228}}</ref>
{{Expand section|date=December 2017}}
* '''eSTREAM ciphers (Grain, Trivium)''': Englund et al. (2007) presented a general statistical distinguishing framework which, when applied to reduced‑round versions of Grain‑128 and Trivium, recovers a few key bits by selecting IVs and observing keystream biases.<ref name="Englund2007">{{cite conference |last=Englund |first=H. |last2=Johansson |first2=T. |last3=Maximov |first3=A. |title=A framework for chosen IV statistical analysis of stream ciphers |book-title=Selected Areas in Cryptography (SAC 2007) |year=2007 |pages=268–285}}</ref>
* '''Grain‑128a''' (related‑key variant): A chosen‑IV plus related‑key attack broke Grain‑128 and Grain‑v1 due to symmetric padding. Grain‑128a was later attacked using ≈2^64 IVs and ≈2^32 related keys, recovering 32 key bits by solving nonlinear equations.<ref name="Massey2010">{{cite web |last=Massey |first=J. |title=New Attacks on Grain Family Using Related Keys and IVs |website=Cryptology ePrint Archive |year=2010 |url=https://eprint.iacr.org/2010/000 |access-date=27 June 2025}}</ref>
* '''Turing cipher''': Joux & Muller (2006) showed that with fewer than 2^16 chosen IVs, their attack leaks partial key information for the new Turing cipher due to flaws in its key‑scheduling algorithm.<ref name="Joux2006">{{cite conference |last=Joux |first=A. |last2=Muller |first2=F. |title=Chosen-IV Attacks against the Turing Stream Cipher |book-title=Fast Software Encryption (FSE 2006) |pages=162–176 |year=2006}}</ref>


=== Mitigation ===
Stream ciphers combine a secret key with an agreed initialization vector (IV) to produce a pseudo-random sequence that is periodically re-synchronized.<ref>{{cite book |last1=Englund |first1=Hakan |last2=Johansson |first2=Thomas |last3=Sonmez Turan |first3=Meltem |title=Progress in Cryptology – INDOCRYPT 2007 |chapter=A Framework for Chosen IV Statistical Analysis of Stream Ciphers |series=Lecture Notes in Computer Science |date=2007 |volume=4859 |publisher=Springer |pages=268–281 |doi=10.1007/978-3-540-77026-8_20 |isbn=978-3-540-77025-1 |s2cid=18097959 |edition=INDOCRYPT / volume 4859 of LNCS |url=https://pdfs.semanticscholar.org/cdaf/30e07673a11eb95f62793858951da2feba32.pdf |archive-url=https://web.archive.org/web/20181001182527/https://pdfs.semanticscholar.org/cdaf/30e07673a11eb95f62793858951da2feba32.pdf |url-status=dead |archive-date=2018-10-01 |accessdate=1 October 2018}}</ref>
Secure stream ciphers should thoroughly mix the key and IV during initialization—through sufficiently many rounds, robust nonlinearity, and absence of algebraic shortcuts—making the mapping from IV to keystream indistinguishable from random for any fixed key. Designers must also ensure IV space is large, unpredictable, and free from exploitable structures.<ref name="Rathgeb2018"/>


=== Comparison with related attacks ===
A "chosen IV" attack relies on finding particular IVs which, taken together, may reveal information about the secret key. Typically, multiple pairs of IVs are chosen and differences in the generated key streams are then analyzed statistically for a linear [[Correlation attack|correlation]] and/or an algebraic Boolean relation (see also [[Differential cryptanalysis]]). If choosing particular values of the initialization vector exposes a non-random pattern in the generated sequence, the attack can recover some bits and shorten the effective key length. A symptom of such an attack would be frequent re-synchronization. Modern stream ciphers include steps to adequately mix the secret key with the initialization vector, usually by performing many initial rounds.
Chosen‑IV attacks differ from '''related‑key''' attacks (which vary the key) and '''known‑IV''' scenarios (where IVs are not attacker‑controlled). They are also distinct from simple reuse attacks: here, the threat stems from statistical weaknesses triggered by adversarial IVs rather than accidental IV collisions.<ref name="Rathgeb2018">{{cite journal |last=Rathgeb |first=C. |title=Statistical and algebraic properties of stream ciphers under chosen-IV settings |journal=Journal of Cryptographic Engineering |volume=8 |issue=3 |year=2018 |pages=231–245 |doi=10.1007/s13389-018-0178-6}}</ref>


==References==
==References==
Line 67: Line 59:
==External links==
==External links==
* [http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html Security of the WEP algorithm]
* [http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html Security of the WEP algorithm]
* [https://eprint.iacr.org/2014/677.pdf "Attacks in Stream Ciphers: A Survey"] – a brief 2014 overview of different stream cipher attacks
* [https://eprint.iacr.org/2014/677.pdf "Attacks in Stream Ciphers: A Survey"] – a 2014 overview of different stream cipher attacks
* [http://www.isical.ac.in/~palash/talks/ASK11-talk.pdf "Attacks on Stream Ciphers: A Perspective"] – talk slides from 2011
* [http://www.isical.ac.in/~palash/talks/ASK11-talk.pdf "Attacks on Stream Ciphers: A Perspective"] – talk slides from 2011


Latest revision as of 18:28, 21 October 2025

Template:Short description Script error: No such module "Unsubst".

Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be secure if used properly.Script error: No such module "Unsubst". However, they are vulnerable to attacks if certain precautions are not followed:

  • Keys must never be reused.
  • Valid decryption should never be relied on to indicate authenticity.

Reused key attack

Stream ciphers are vulnerable to attack if the same key is used more than once (a depth of two or greater).

Suppose messages A and B of the same length are both encrypted using the same key, K. The stream cipher produces a string of bits C(K) of the same length as the messages. The encrypted versions of the messages are:

E(A) = A xor C
E(B) = B xor C

where xor is performed bit by bit.

If an adversary intercepts E(A) and E(B), they can compute:

E(A) xor E(B)

Because xor is commutative and has the property that X xor X = 0 (self-inverse):

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, the adversary can truncate the longer message to the size of the shorter one, revealing only that portion. In other words, if two messages are encrypted with the same key, an attacker can recover A xor B, which is a form of running key cipher. Even if neither message is known, as long as both are in a natural language, such a cipher can often be broken by hand methods. During World War II, British cryptanalyst John Tiltman accomplished this with the Lorenz cipher (dubbed "Tunny"). With an average personal computer, such ciphers can usually be broken in minutes. If one message is known, the solution is trivial.

Another situation where recovery is trivial is when traffic-flow security measures require each station to send a continuous stream of cipher bits, with null characters (e.g. LTRS in Baudot) transmitted when there is no real traffic. This is common in military communications. In that case, if the transmission channel is not fully loaded, there is a high likelihood that one of the ciphertext streams will consist only of nulls. The NSA has taken extensive measures to prevent keys from being reused. In the 1960s, encryption systems often included a punched card reader for loading keys. The mechanism would automatically cut the card in half when it was removed, preventing reuse.[1]Template:Rp

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 systems that use the popular stream cipher RC4, including Wired Equivalent Privacy (WEP), Wi-Fi Protected Access (WPA), and Ciphersaber. One of the problems with WEP was that its IV was too short (24 bits). This meant there was a high likelihood that the same IV would be reused if more than a few thousand packets were sent with the same master key (see birthday attack), subjecting those packets to the key reuse attack. This problem was addressed in WPA by changing the "master" key frequently.

Bit-flipping attack

Script error: No such module "Labelled list hatnote". Script error: No such module "Labelled list hatnote". Suppose an adversary knows the exact content of all or part of a message. As part of a man in the middle attack or replay attack, they can alter the content without knowing the key, K. For example, if they know a portion of the message contains the ASCII string "$1000.00", they can change it to "$9500.00" by XORing that portion of the ciphertext with the string: "$1000.00" xor "$9500.00".

The ciphertext being sent is C(K) xor "$1000.00". The adversary creates a new message:

(C(K) 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"

Since a string XORed with itself produces all zeros, and a string of zeros XORed with another string leaves that string unchanged, the result C(K) xor "$9500.00" is what the ciphertext would have been if $9500 were the original amount.

Bit-flipping attacks can be prevented by including a message authentication code, which increases the likelihood that tampering will be detected.

Chosen-IV attack

Script error: No such module "Unsubst".

Stream ciphers combine a secret key with an agreed initialization vector (IV) to produce a pseudo-random sequence that is periodically re-synchronized.[2]

A "chosen IV" attack relies on finding particular IVs which, taken together, may reveal information about the secret key. Typically, multiple pairs of IVs are chosen and differences in the generated key streams are then analyzed statistically for a linear correlation and/or an algebraic Boolean relation (see also Differential cryptanalysis). If choosing particular values of the initialization vector exposes a non-random pattern in the generated sequence, the attack can recover some bits and shorten the effective key length. A symptom of such an attack would be frequent re-synchronization. Modern stream ciphers include steps to adequately mix the secret key with the initialization vector, usually by performing many initial rounds.

References

<templatestyles src="Reflist/styles.css" />

  1. ↑ Securing Record Communications: The TSEC/KW-26 Template:Webarchive, Melville Klein, NSA history series
  2. ↑ Script error: No such module "citation/CS1".

Script error: No such module "Check for unknown parameters".

External links

Script error: No such module "Navbox".

Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Stream_cipher_attacks&oldid=5512044"