Note that they have decomposed the GOST S-box into several non-linear 4-bit functions. While this is certainly great for hardware optimization, the cipher is still not fully understood: the authors have not determined why these particular functions were chosen. Non-linear functions are given in the paper as magic constants.
The choice of the numbers used for S-boxes can be very mysterious unless the designers explain it. So reverse engineering the S-box design might reveal something interesting (something good or something evil).
For years people thought that the S-boxes in the Data Encryption Standard (DES) hid a back door since the NSA had helped design it. It surprisingly turned out years later that the NSA had actually strengthened the S-boxes against an attack called differential cryptanalysis that was not known to the public crypto community at the time[1]. But neither were they entirely benevolent: The NSA also weakened DES by shortening the key length so they could brute force it, and in the heyday of DES, the NSA was probably the only organization in the world that had the computing power to do so.
> ...in the heyday of DES, the NSA was probably the only organization in the world that had the computing power to do so.
Less an issue of the computing power, more an issue of the knowledge. As you noted, civilian cryptographers hadn't even discovered differential analysis yet, so hardening the cipher against it wasn't even a consideration.
> Less an issue of the computing power, more an issue of the knowledge.
I think you're mixing up two issues:
(a) Strengthening DES against differential cryptanalysis is a knowledge issue. The NSA knew about that attack, and maybe the Soviets knew too, but the public didn't.
(b) The key length for DES however is entirely a computing power issue; it is not a knowledge issue. It would be obvious to everyone even in 1977 that a 64-bit key as originally proposed would have been better than the 56 bits they ended up using[1]. Furthermore, everyone understood how to do a brute force attack, but it just wasn't feasible for the public. Only the NSA would have had the budget and inclination to develop special-purpose computing hardware to actually do it in the 1980's DES era.
[1]I have to mention one nitpick here, otherwise someone else will point it out. The 56-bit key length was supposedly ideal because DES would have been more easily cracked using differential cryptanalysis than brute force with any key longer than 56 bits. Thus the NSA can claim, "no we didn't weaken DES by shortening the key, we optimized it because 64 bits doesn't buy you extra security over 56 bits". But that argument is bogus. They could have improved DES in such a way that it used 64-bit keys and wasn't vulnerable to differential cryptanalysis. But they did the latter and not the former, because it keeps DES secure against the Soviets (assuming they knew about differential cryptanalysis) and against the public (who can't mount a brute force attack) but does allow the NSA to be able crack it.
They're just raising questions about the S-Box's internal structure and making it easier for other parties to study it in greater detail in the future to see if there is an issue.
I'd suggest not jumping to conclusions. This could be like the DES situation all over again where the NSA strengthened the S-Boxes against differential cryptanalysis in secret and then got accused of weakening DES for its efforts (because cryptanalysis was unknown/secret at the time).
But regardless this might be one of these "watch this space" things where interesting insights could come up later.
