Editing GOST (block cipher) (section)

==The algorithm==

GOST has a 64-bit [[block size (cryptography)|block size]] and a [[key length]] of 256 bits. Its [[S-box]]es can be secret, and they contain about 354 (log<sub>2</sub>(16!<sup>8</sup>)) bits of secret information, so the effective key size can be increased to 610 bits; however, a chosen-key attack can recover the contents of the S-boxes in approximately 2<sup>32</sup> encryptions.<ref>{{
cite journal
 |last=Saarinen
 |first=Markku-Juhani
 |title=A chosen key attack against the secret S-boxes of GOST
 |year=1998
 |url=http://citeseer.ist.psu.edu/rd/96002585%2C277448%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/compress/0/papers/cs/13215/http:zSzzSzwww.jyu.fizSz~mjoszSzgost_cka.ps.gz/saarinen98chosen.ps
 |quote=We show that a simple "black box" chosen-key attack against GOST can recover secret S-boxes with approximately 2^32 encryptions}}
</ref>

GOST is a [[Feistel network]] of 32 rounds. Its round function is very simple: add a 32-bit subkey [[modular arithmetic|modulo]] 2<sup>32</sup>, put the result through a layer of S-boxes, and rotate that result left by 11 bits. The result of that is the output of the round function. In the adjacent diagram, one line represents 32 bits.

The subkeys are chosen in a pre-specified order. The key schedule is very simple: break the 256-bit key into eight 32-bit subkeys, and each subkey is used four times in the algorithm; the first 24 rounds use the key words in order, the last 8 rounds use them in reverse order.

The S-boxes accept a four-bit input and produce a four-bit output. The S-box substitution in the round function consists of eight 4 × 4 S-boxes. The S-boxes are implementation-dependent, thus parties that want to secure their communications using GOST must be using the same S-boxes. For extra security, the S-boxes can be kept secret. In the original standard where GOST was specified, no S-boxes were given, but they were to be supplied somehow. This led to speculation that organizations the government wished to spy on were given weak S-boxes. One GOST chip manufacturer reported that he generated S-boxes himself using a [[pseudorandom number generator]].<ref name=schneier1996>
{{cite book
 |last=Schneier
 |first=Bruce
 |title=Applied cryptography : protocols, algorithms, and source code in C
 |url=https://archive.org/details/Applied_Cryptography_2nd_ed._B._Schneier
 |year=1996
 |publisher=Wiley
 |location=New York [u.a.]
 |isbn=978-0-471-11709-4
 |edition=2. ed., [Nachdr.]}}</ref>

For example, the [[Central Bank of Russia|Central Bank of Russian Federation]] used the following S-boxes: <!--http://www.intuit.ru/department/security/networksec/3/4.html-->

{|class="wikitable"
 !#
 !S-box
 |-
 !1
 |4 A 9 2 D 8 0 E 6 B 1 C 7 F 5 3
 |-
 !2
 |E B 4 C 6 D F A 2 3 8 1 0 7 5 9
 |-
 !3
 |5 8 1 D A 3 4 2 E F C 7 6 0 9 B
 |-
 !4
 |7 D A 1 0 8 9 F E 4 6 C B 2 5 3
 |-
 !5
 |6 C 7 1 5 F D 8 4 A 9 E 0 3 B 2
 |-
 !6
 |4 B A 0 7 2 1 D 3 6 8 5 9 C F E
 |-
 !7
 |D B 4 1 3 F 5 9 0 A E 7 6 8 2 C
 |-
 !8
 |1 F D 0 5 7 A 4 9 2 3 E 6 B 8 C
 |}

However, the most recent revision of the standard, '''GOST R 34.12-2015''', adds the missing S-box specification and defines it as follows.<ref name="std2015">{{Cite web |url=http://tc26.ru/standard/gost/GOST_R_3412-2015.pdf |title=GOST R 34.12-2015 (Russian only)  |access-date=2015-08-28 |archive-url=https://web.archive.org/web/20150924113434/http://tc26.ru/standard/gost/GOST_R_3412-2015.pdf |archive-date=2015-09-24 |url-status=dead }}</ref>

{| class="wikitable"
 !#
 !GOST R 34.12-2015 S-box
 |-
 !1
 |C 4 6 2 A 5 B 9 E 8 D 7 0 3 F 1
 |-
 !2
 |6 8 2 3 9 A 5 C 1 E 4 7 B D 0 F
 |-
 !3
 |B 3 5 8 2 F A D E 1 7 4 C 9 6 0
 |-
 !4
 |C 8 2 1 D 4 F 6 7 0 A 5 3 E 9 B
 |-
 !5
 |7 F 5 A 8 1 6 D 0 9 3 E B 4 2 C
 |-
 !6
 |5 D F 6 9 2 C A B 7 8 1 4 3 E 0
 |-
 !7
 |8 E 2 5 6 9 1 C F 4 B 0 D A 3 7
 |-
 !8
 |1 7 E D 0 5 8 3 4 F A 6 9 C B 2
 |}