Abstract The Pilsung cipher is part of the North Korean Red Star operating system, which was leaked to the West in 2014. Initial analysis by Kryptos Logic reported a possibility of a class of weak keys due to the use of pseudo-random diffusion. Following this lead, we analyzed the cipher and identified a small class of such weak keys. We developed techniques for searching for a key that belongs to the class. After spending thousands of CPU hours, we found a supposedly weak key for a slightly weaker version of Pilsung, but the key did not behave as we expected. On further investigation we found out a crucial misunderstanding in a critical part of the cipher and that no such class of weak keys exists in Pilsung. Thus, this paper makes two main contributions to the art of cryptanalysis. First, it identifies and shows how to investigate a potential weakness in randomizing diffusion, which although does not exist in Pilsung, may affect future designs. Second, it highlights the need for early verification of results in order to identify errors before expending significant resources.

Abstract At IEEE GLOBECOM 2008, a lightweight cipher based on a Multiple Recursive Generator (MRG) was proposed for use in resource limited environment such as sensor nodes and RFID tags. This paper proposes two efficient attacks on this MRG cipher. A distinguishing attack is firstly introduced to identify the use of an MRG cipher that has a modulus suggested by its designers. It requires 218 words of ciphertext and the most significant bit of each corresponding plaintext word. Then an efficient known plaintext attack is proposed to construct the cipher's current state and generate subkeys used for all subsequent encryption. The known plaintext attack, when targeted at the MRG ciphers optimized for efficiency, only requires 2k words of known plaintext and trivial computation where k is the MRG order. Even the ciphers based on complicated and inefficient MRGs can be attacked with low complexity, e.g. in the magnitude of 212 words of known plaintext for all MRG ciphers with order 47, regardless of which MRG modulus is used. These two attacks indicate that the examined MRG cipher structure is seriously flawed. Copyright © 2010 John Wiley & Sons, Ltd.