Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Советский/российский национальный стандартный блочный шифр
Soviet/Russian national standard block cipher
Блочный шифр ГОСТ (Magma), определённый в стандарте ГОСТ 28147-89 (RFC 5830), является советским и российским государственным стандартом симметричного шифрования с размером блока 64 бита. Исходный стандарт, опубликованный в 1989 году, не присваивал шифру какого-либо названия, но последняя редакция стандарта, ГОСТ Р 34.12-2015 (RFC 7801, RFC 8891), указывает, что его можно называть Magma. Таким образом, они очень похожи по структуре.
The GOST block cipher (Magma), defined in the standard GOST 28147 89 (RFC 5830), is a Soviet and Russian government standard symmetric key block cipher with a block size of 64 bits. The original standard, published in 1989, did not give the cipher any name, but the most recent revision of the standard, GOST R 34.12 2015 (RFC 7801, RFC 8891), specifies that it may be referred to as Magma. Thus, the two are very similar in structure.
Криптоанализ ГОСТ
Последний криптоанализ ГОСТ показывает, что он безопасен в теоретическом плане. На практике вычислительная и памятью сложность лучших опубликованных атак достигла практически реализуемого уровня, в то время как временная сложность даже лучшей атаки всё ещё составляет 2<sup>192</sup> при наличии 2<sup>64</sup> данных. С 2007 года было разработано несколько атак против GOST с уменьшенным количеством раундов и/или слабых ключей. В 2011 году несколько авторов обнаружили более серьёзные недостатки в GOST, впервые получив возможность атаковать полный 32-раундовый GOST с использованием произвольных ключей. Николя Куртуа даже назвал его «глубоко дефектным шифром». Первоначальные атаки позволили снизить временную сложность с 2<sup>256</sup> до 2<sup>228</sup> за счёт огромных требований к памяти, а вскоре они были улучшены до временной сложности 2<sup>178</sup> (за счёт 2<sup>70</sup> памяти и 2<sup>64</sup> данных). В декабре 2012 года Куртуа, Гавинецки и Сонг улучшили атаки на GOST, вычислив всего 2<sup>101</sup> раундов GOST. Isobe уже опубликовал атаку на полный шифр GOST с использованием одного ключа, которую Динур, Дункельман и Шамир улучшили, достигнув временной сложности 2<sup>224</sup> для 2<sup>32</sup> данных и 2<sup>36</sup> памяти, и 2<sup>192</sup> временной сложности для 2<sup>64</sup> данных. Поскольку атаки снижают ожидаемую прочность с 2<sup>256</sup> (длина ключа) примерно до 2<sup>178</sup>, шифр можно считать взломанным. Однако эта атака нереализуема на практике, поскольку количество необходимых тестов 2<sup>178</sup> недостижимо. Следует отметить, что для любого блочного шифра с размером блока n бит максимальный объём открытого текста, который можно зашифровать до смены ключа, составляет 2<sup>n/2</sup> блоков из-за парадокса дней рождения, и ни одна из вышеупомянутых атак не требует менее 2<sup>32</sup> данных.
The latest cryptanalysis of GOST shows that it is secure in a theoretical sense. In practice, the data and memory complexity of the best published attacks has reached the level of practical, while the time complexity of even the best attack is still 2192 when 264 data is available. Since 2007, several attacks have been developed against reduced round GOST implementations and/or weak keys. In 2011 several authors discovered more significant flaws in GOST, being able to attack the full 32 round GOST with arbitrary keys for the first time. It has even been called "a deeply flawed cipher" by Nicolas Courtois. Initial attacks were able to reduce time complexity from 2256 to 2228 at the cost of huge memory requirements, and soon they were improved up to 2178 time complexity (at the cost of 270 memory and 264 data). In December 2012, Courtois, Gawinecki, and Song improved attacks on GOST by computing only 2101 GOST rounds. Isobe had already published a single key attack on the full GOST cipher, which Dinur, Dunkelman, and Shamir improved upon, reaching 2224 time complexity for 232 data and 236 memory, and 2192 time complexity for 264 data. Since the attacks reduce the expected strength from 2256 (key length) to around 2178, the cipher can be considered broken. However, this attack is not feasible in practice, as the number of tests to be performed 2178 is out of reach. Note that for any block cipher with block size of n bits, the maximum amount of plaintext that can be encrypted before rekeying must take place is 2n/2 blocks, due to the birthday paradox, and none of the aforementioned attacks require less than 232 data.