Rotational cryptanalysis of GOST with identical S-boxes

Abstract

Rotational cryptanalysis was introduced by Khovratovich and Ni-
kolic as a tool to analyse ARX-type cipher designs. GOST 28147-89 is a former
Soviet Union cipher standard based on a Feistel construction with 32 rounds.
Its round function adds the round key modulo 232, transforms the result with
4-to-4 bit S-boxes, and rotates the output. We apply the rotational cryptanalysis
to GOST version that uses eight identical S-boxes, such as GOST-PS. We show
the existence of (practical) rotational distinguisher in related key model for full
GOST. Furthermore, there is a set of weak keys (rotationally symmetric keys)
that enables rotational attacks in single-key model as well. Finally, we show a
simple attack on last round that uses the rotational distinguisher to reduce the
complexity of the full GOST (in average) to 208 bits.