Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by 244.8 multiple key-IV pairs or 260.8 keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the 21400 step algorithm of Ankele et al. at Latincrypt 2015. Finally we propose a simple fix that removes the bias in the first two keystream bytes. The countermeasure requires only one additional memory access and hence does not diminish software performance substantially, and in fact the loss in software speed is only around 1.5%.
Subhadeep BANIK
Nanyang Technological University
Takanori ISOBE
University of Hyogo
Masakatu MORII
Kobe University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Subhadeep BANIK, Takanori ISOBE, Masakatu MORII, "Analysis and Improvements of the Full Spritz Stream Cipher" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 6, pp. 1296-1305, June 2017, doi: 10.1587/transfun.E100.A.1296.
Abstract: Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by 244.8 multiple key-IV pairs or 260.8 keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the 21400 step algorithm of Ankele et al. at Latincrypt 2015. Finally we propose a simple fix that removes the bias in the first two keystream bytes. The countermeasure requires only one additional memory access and hence does not diminish software performance substantially, and in fact the loss in software speed is only around 1.5%.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1296/_p
Copy
@ARTICLE{e100-a_6_1296,
author={Subhadeep BANIK, Takanori ISOBE, Masakatu MORII, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Analysis and Improvements of the Full Spritz Stream Cipher},
year={2017},
volume={E100-A},
number={6},
pages={1296-1305},
abstract={Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by 244.8 multiple key-IV pairs or 260.8 keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the 21400 step algorithm of Ankele et al. at Latincrypt 2015. Finally we propose a simple fix that removes the bias in the first two keystream bytes. The countermeasure requires only one additional memory access and hence does not diminish software performance substantially, and in fact the loss in software speed is only around 1.5%.},
keywords={},
doi={10.1587/transfun.E100.A.1296},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Analysis and Improvements of the Full Spritz Stream Cipher
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1296
EP - 1305
AU - Subhadeep BANIK
AU - Takanori ISOBE
AU - Masakatu MORII
PY - 2017
DO - 10.1587/transfun.E100.A.1296
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2017
AB - Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by 244.8 multiple key-IV pairs or 260.8 keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the 21400 step algorithm of Ankele et al. at Latincrypt 2015. Finally we propose a simple fix that removes the bias in the first two keystream bytes. The countermeasure requires only one additional memory access and hence does not diminish software performance substantially, and in fact the loss in software speed is only around 1.5%.
ER -