Some Results on Related Key-IV Pairs of Grain

摘要

In this paper we explain how one can obtain Key-IV pairs for Grain family of stream ciphers that can generate output key-streams which are either (i) almost similar in the initial part or (ii) exact shifts of each other throughout the generation of the stream. Let l_P be the size of the pad used during the key loading of Grain. For the first case, we show that in expected 2~(l_P) many invocations of the Key Scheduling Algorithm and its reverse routine, one can obtain two related Key-IV pairs that can produce same output bits in 75 (respectively 112 and 115) selected positions among the initial 96 (respectively ICO and 160) bits for Ghain v1 (respectively Grain-128 and Grain-128a). Similar idea works for the second case in showing that given any Key-IV, one can obtain another related Key-IV in expected 2~(l_P) many trials such that the related Key-IV pairs produce shifted key-streams. We also provide an efficient strategy to obtain related Key-IV pairs that produce exactly i-bit shifted key-streams for small i. Our technique pre-computes certain equations that help in obtaining such related Key-IV pairs in 2~i many expected trials.