Алгоритм FROG

был создан в 1998 г. тремя специалистами компании Tecnologia Apropriada (ТесАрго) из небольшого латиноамериканского государства Коста-Рика (неизвестного ранее своими разработками в области криптографии): Дианелосом Георгоудисом (Dianelos Georgoudis), Дамианом Jlepy (Damian Leroux) и Билли Симоном Чавесом (Billy Simon Chaves) [160].

Основные характеристики и структура алгоритма

Как известно, конкурс AES (см. разд. 2.1) устанавливал для алгоритмов — участников конкурса обязательность поддержки 128-битного размера блока шифруемых данных, а также 128-, 192- и 256-битных ключей шифрования. Однако, разработчики алгоритма FROG предложили несравнимо более широкий набор значений этих параметров:

? допустимо использовать ключи размером от 5 до 125 байтов (т. е. от 40 до 1000 битов);

? размер блока может варьироваться от 8 до 128 байтов, т. е. от 64 до 1024 битов (однако в авторском описании алгоритма в соответствии с требованиями AES фигурирует 16-байтный размер блока).

Рис. 3.82. Структура раунда алгоритма FROG

Независимо от размера ключа и блока, шифрование выполняется в 8 раундов.

В каждом раунде над каждым байтом шифруемого блока (для определенности также будем считать, что блоки имеют размер 16 байтов) производятся

следующие действия (рис. 3.82):

1.    Значение текущего (/-го) байта складывается по модулю 2 со значением того же байта 1-й части ключа раунда (процедура расширения ключа описана далее).

2.    Вторая часть ключа раунда представляет собой таблицу перестановок. Из данной таблицы выбирается байт, порядковый номер которого равен значению, вычисленному на первом шаге. Значение выбранного байта замещает значение текущего байта шифруемого блока данных.

3.    Значение следующего байта (/ +1 -перекладывается по модулю 2 со значением, выбранным на шаге 2. Полученный результат замещает старое значение / +1 -го байта шифруемого блока данных.

4.    Третья часть ключа раунда представляет собой таблицу индексов. Значение /-го байта таблицы индексов определяет еще один модифицируемый байт шифруемого блока данных, который изменяется полностью аналогично i + 1 -му байту (т. е. складывается по модулю 2 со значением, полученным на шаге 2).

Процедура расширения ключа

Эта процедура должна получить из ключа шифрования 8 ключей раундов — по одному на каждый раунд алгоритма. Как видно из описания алгоритма, ключ раунда состоит из трех подключей:

?        16-байтная 1-я часть;

?       256-байтная таблица перестановок;

?        16-байтная таблица индексов.

Рис. 3.83. Процедура расширения ключа

Таким образом, для работы алгоритма необходимо выработать 2304 байтов ключевой информации. Вот как это происходит (рис. 3.83):

1. Путем «размножения» ключа шифрования (т. е. значение ключа шифрования повторяется необходимое количество раз, а ключ шифрования этого

алгоритма, как было сказано выше, имеет размер от 5 до 125 байтов) вырабатывается первый 2304-байтный временный массив данных. Байты последней из «размноженных» копий ключа, выходящие за границу требуемого 2304-байтного массива (например, последний 71 байт 125-байтного ключа — ключа максимального размера), отбрасываются.

2. Аналогичным «размножением» 251-байтного фрагмента мастер-ключа формируется второй 2304-байтный временный массив данных. Мастер- ключ представляет собой специально подобранную константу размером 251 байт. Побайтное значение мастер-ключа (начиная с младшего байта) приведено в табл. 3.25.

Таблица 3.25

113

21

232

18

113

92

63

157

124

193

166

197

126

56

229

229

156

162

54

17

230

89

189

87

169

0

81

204

8

70

203

225

160

59

167

189

100

157

84

11

7

130

29

51

32

45

135

237

139

33

17

221

24

50

89

74

21

205

191

242

84

53

3

230

231

118

15

15

107

4

21

34

3

156

57

66

93

255

191

3

85

135

205

200

185

204

52

37

35

24

68

185

201

10

224

234

7

120

201

115

216

103

57

255

93

110

42

249

68

14

29

55

128

84

37

152

221

137

39

11

252

50

144

35

178

190

43

162

103

249

109

8

235

33

158

111

252

205

169

54

10

20

221

201

178

224

89

184

182

65

201

10

60

6

191

174

79

98

26

160

252

51

63

79

6

102

123

173

49

3

110

233

90

158

228

210

209

237

30

95

28

179

204

220

72

163

77

166

192

98

165

25

145

162

91

212

41

230

110

6

107

187

127

38

82

98

30

67

225

80

208

134

60

250

153

87

148

60

66

165

72

29

165

82

211

207

0

177

206

13

6

14

92

248

60

201

132

95

35

215

118

177

121

180

27

83

131

26

39

46

12

 

 

 

 

 

3.     Путем применения операции сложения по модулю 2 к соответствующим битам двух массивов, выработанных на шагах 1 и 2, получается временный расширенный ключ.

4.     Форматирование ключа, полученного на шаге 3 (т. е. его разбиение на 8 отрезков— по числу раундов— размером 16 + 256 + 16 байтов, а также дополнительная обработка, которая будет описана далее), дает предварительный расширенный ключ алгоритма.

5.      Предварительный расширенный ключ используется для зашифровывания 2304-байтного массива, заполненного нулями. Шифрование выполняется в режиме сцепления блоков шифра (см. разд. 1.4), где в качестве вектора инициализации (IV) используются первые 16 байтов исходного ключа шифрования, самый первый из которых еще и складывается по модулю 2 с числом, равным размеру ключа шифрования в байтах (это необходимо для получения различных IV для ключей разного размера, но с совпадающими первыми 16 байтами). Результат операции— расширенный ключ, заполненный псевдослучайной информацией.

6.     Аналогично шагу 4, выполняется форматирование расширенного ключа для получения восьми ключей раундов с необходимой структурой.

Форматирование ключа

Шаги 4 и 6 алгоритма расширения ключа представляют собой форматирование 2304-байтной псевдослучайной последовательности с целью получения 8 ключей раундов. Если 1-я часть ключа раунда, используемая для сложения по модулю 2, может иметь абсолютно случайную структуру, то корректная таблица перестановок должна состоять из 256 неповторяющихся значений от 0 до 255, а к 16-байтной таблице индексов, кроме того, предъявляются дополнительные требования.

Таким образом, при форматировании производятся следующие действия:

1.     Разбиение 2304-байтного массива на 8 фрагментов по 16 + 256 + 16 байтов.

2.     Первые 16 байтов фрагмента становятся первой частью ключа раунда без изменений.

3.     Следующие 256 байтов (обозначим этот фрагмент А) обрабатываются специальной процедурой с целью получения корректной таблицы перестановок. Данная процедура выглядит так:

•                 создается 256-байтный массив t/, содержащий последовательно расположенные значения от 0 до 255;

•                 в цикле от 0 до 255 /-й байт таблицы перестановок Т определяется по формуле:

где:

О index[i-l] — номер элемента массива t/, использованного на предыдущем шаге (для нулевого шага принимается равным 0), a L — текущий размер массива U\

О использованный байт массива U выбрасывается, а расположенные после него элементы массива U сдвигаются на 1 байт к началу массива; таким образом, значение L в каждом проходе данного цикла уменьшается на 1;

• если таблица перестановок создается для операции расшифровывания, то выполняется ее инвертирование.

4.     Аналогично шагу 3 создается 16-байтная таблица индексов /.

5.     Выполняется анализ цепочек ссылок таблицы индексов; если таблица состоит из нескольких цепочек, производится изменение таблицы с целью получения одной цепочки ссылок, длина которой будет равна размеру таблицы.

6.     Таблица снова анализируется с целью поиска индексов, удовлетворяющих следующему условию:

если такие элементы таблицы существуют, их значение меняется на

Шаги 3-5 процедуры форматирования стоит рассмотреть на примере. Предположим, создается 6-байтная таблица индексов из следующего 6-байтного фрагмента Л псевдослучайной последовательности:

21,247,199,108,66,239.

В цикле от 0 до 5 (шаг 4) /-й байт таблицы индексов I определяется по формуле:

что на примере приведенной выше последовательности выглядит так, как показано в табл. 3.26. ‘

 

 

Таблица 3.26

и

index[i –1] + A[i] mod L

I

0, 1,2, 3, 4,5

0 + 21 mod 6 = 3

3

0, 1,2, 4,5

3 + 247 mod 5 = 0

3,0

1,2, 4,5

0 + 199 mod 4 = 3

3,0,5

1,2,4

3 + 108 mod 3 = 0

3, 0, 5, 1

2,4

0 + 66 mod 2 = 0

3,0,5, 1,2

4

 

3,0,5, 1,2,4

Результат — таблица индексов:

Анализ таблицы (шаг 5) позволяет выяснить, что данная таблица состоит из двух цепочек ссылок:

Однако для достижения максимальной криптостойкости алгоритма таблица индексов должна содержать одну цепочку максимального размера. Алгоритм, выполняемый на шаге 5, позволяет объединить несколько цепочек в одну. В данном примере это достигается путем перемены местами значений 0 и 2, т. е. получается следующая таблица индексов:

которая формирует одну цепочку:

Достоинства и недостатки алгоритма

Несомненно, FROG является одним из самых оригинальных из современных алгоритмов шифрования. Как и многие другие алгоритмы, например AES (Rijndael) или SAFER+ (см. разд. 3.3 и 3.45 соответственно), FROG является байт-ориентированным. Однако, в отличие от объяснимых и объясненных авторами Rijndael и SAFER+ преобразований, примененных в этих алгоритмах, авторы алгоритма FROG ограничились пояснением, что такая необычная структура раунда выбрана с целью обеспечить максимально быстрое рассеивание входных данных (т. е. обеспечение влияния каждого бита шифруемых данных на каждый бит шифртекста в пределах блока).

К сожалению, алгоритм FROG был признан одним из наиболее слабых участников конкурса AES; в нем было найдено множество недостатков, в частности [284, 387]:

?      довольно большая часть множества возможных ключей алгоритма оказалась слабой (благодаря очень сложной процедуре расширения ключа) к различным видам атак;

?      алгоритм оказался весьма медленным, причем даже по сравнению с алгоритмами, известными до конкурса AES, например, Blowfish (см. разд. 3.8) и RC5 (см. разд. 3.42)\

?      алгоритм FROG оказался очень требовательным к оперативной памяти — ему необходимо около 2500 байтов в случае, если ключи раундов сформированы заранее, а для работы полнофункционального алгоритма, включающего процедуру расширения ключа, необходимо около 5000 байтов; эти требования очень велики (особенно в сравнении с другими алгоритмами — участниками конкурса AES) для реализации данного алгоритма в смарт-картах.

Таким образом, алгоритм FROG не вышел в финал конкурса AES.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100