SNOW (шифр): различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
мНет описания правки |
Добавлены ссылки. Улучшено оформление и пояснены непонятные места |
||
Строка 1: | Строка 1: | ||
{{Другие значения|тип=слово|Snow|Snow (значения)}} |
{{Другие значения|тип=слово|Snow|Snow (значения)}} |
||
'''SNOW''' — словоориентированный синхронный [[поточный шифр]], разработанный |
'''SNOW''' — словоориентированный синхронный [[поточный шифр]], разработанный [[Лундский университет|Лундском университете]] (Швеция). На данный момент у него существует 3 модификации: SNOW 2.0, SNOW 3G, SNOW-V, последние две из которых используются для безопасной передачи мобильных данных. |
||
== История == |
== История == |
||
SNOW 1.0, первоначально просто SNOW |
SNOW 1.0, первоначально просто SNOW<ref name="snow1" />, был разработан в 2000 году. Шифр работает с 32-битными словами и поддерживает как 128-, так и 256-битные ключи. Шифр состоит из комбинации [[регистр сдвига с линейной обратной связью|регистра сдвига с линейной обратной связью]] (РСЛОС) и [[конечный автомат|конечного автомата]] (КА), где РСЛОС также передает функцию следующего состояния КА. |
||
В первой версии были обнаружены слабые места |
В первой версии были обнаружены слабые места<ref name = "snow2"> |
||
<ref name = "snow2"> |
|||
{{публикация|статья |
{{публикация|статья |
||
|автор= Patrik Ekdahl, Thomas Johansson |
|автор= Patrik Ekdahl, Thomas Johansson |
||
|заглавие= A |
|заглавие= A New Version of the Stream Cipher SNOW |
||
|язык= en |
|язык= en |
||
|издание= Springer |
|издание= Springer |
||
Строка 17: | Строка 16: | ||
|issn= 0302-9743 |
|issn= 0302-9743 |
||
|ссылка= https://link.springer.com/chapter/10.1007/3-540-36492-7_5 |
|ссылка= https://link.springer.com/chapter/10.1007/3-540-36492-7_5 |
||
}} </ref>, и в результате SNOW не был включен в набор алгоритмов NESSIE. |
}} </ref>, и в результате SNOW не был включен в набор алгоритмов [[NESSIE]]. В 2003 году авторы разработали новую версию шифра SNOW 2.0<ref>{{публикация|статья |
||
|автор = O. Billet, H. Gilbert |
|||
|заглавие= Resistance of SNOW 2.0 Against Algebraic Attacks |
|||
|язык= en |
|||
|издание= Springer |
|||
|год= 2005 |
|||
|volume= 3376 |
|||
|pages= 19-28 |
|||
|doi= 10.1007/978-3-540-30574-3_3 |
|||
|ссылка= https://link.springer.com/chapter/10.1007%2F978-3-540-30574-3_3 |
|||
}}</ref>, в которой устранили недостатки и улучшили производительность. Во время оценки ETSI SAGE<ref>{{cite web| url = https://www.etsi.org/technologies/security-algorithms| title = Security algorithms}}</ref>, которая предоставляет разработчикам стандартов криптографические алгоритмы и протоколы, предназначенные для предотвращения мошенничества, несанкционированного доступа к публичным и частным телекоммуникационным сетям и конфиденциальности данных пользователей, алгоритм шифрования был дополнительно изменён, чтобы повысить его устойчивость к алгебраическим атакам. Результатом таких улучшений в 2006 году стала модификация шифра SNOW 3G<ref> {{cite web| url = http://www.gsma.com/aboutus/wp-content/uploads/2014/12/uea2designevaluation.pdf| title = UEA2 Design and Evaluation Report| date = 2006-09-06| lang = eng}}</ref><ref name="snow3g"/>. |
|||
В 2019 году ''Ericsson Research'' совместно с Лундским университетом пересмотрели алгоритм SNOW 3G и обновили его до нового, более быстрого шифра под названием SNOW-V<ref name = snowv> |
|||
{{публикация|статья |
|||
|автор = P.Ekdahl, T.Johansson, A.Maximov, J.Yang |
|||
|заглавие= A new SNOW stream cipher called SNOW-V |
|||
|язык= en |
|||
|издание= ToSC |
|||
|год= 2019 |
|||
|volume= 2019 |
|||
|issue = 3 |
|||
|pages= 1-42 |
|||
|doi= 10.13154/tosc.v2019.i3.1-42 |
|||
|ссылка= https://tosc.iacr.org/index.php/ToSC/article/view/8356 |
|||
}} |
|||
</ref>, который может быть использован для безопасной передачи данных в новом поколении связи [[5G]]. |
|||
== Cхема работы SNOW == |
== Cхема работы SNOW == |
||
Строка 25: | Строка 47: | ||
=== Общая схема работы === |
=== Общая схема работы === |
||
[[Файл:Схема работы SNOW 1.0.jpg|thumb|Схема работы SNOW 1.0]] |
[[Файл:Схема работы SNOW 1.0.jpg|thumb|Схема работы SNOW 1.0]] |
||
Генератор состоит из регистра сдвига с линейной обратной связью длины 16 над полем <math>\mathbb{F}_{2^{32}}</math>. Выход регистра подается на вход конечного автомата. КА состоит из двух 32-битных регистров, называемых R1 и R2, а также некоторых операций для вычисления вывода и следующего состояния (следующего значения R1 и R2). Работа шифра выглядит следующим образом. Сначала выполняется инициализация ключа. Эта процедура обеспечивает начальные значения для РСЛОС, а также для регистров R1, R2 в конечном автомате. Затем первые 32 бита ключевого потока вычисляются путем поразрядного сложения выходных данных КА и последней записи РСЛОС. После этого весь шифр синхронизируется один раз, и следующие 32 бита ключевого потока вычисляются путем ещё одного побитового сложения выходных данных конечного автомата и последней записи РСЛОС. Мы снова синхронизируем и продолжаем в том же духе. |
Генератор состоит из регистра сдвига с линейной обратной связью длины 16 над полем <math>\mathbb{F}_{2^{32}}</math>. Выход регистра подается на вход конечного автомата. КА состоит из двух 32-битных регистров, называемых R1 и R2, а также некоторых операций для вычисления вывода и следующего состояния (следующего значения R1 и R2). Работа шифра выглядит следующим образом. Сначала выполняется инициализация ключа. Эта процедура обеспечивает начальные значения для РСЛОС, а также для регистров R1, R2 в конечном автомате. Затем первые 32 бита ключевого потока вычисляются путем поразрядного сложения выходных данных КА и последней записи РСЛОС. После этого весь шифр синхронизируется один раз, и следующие 32 бита ключевого потока вычисляются путем ещё одного побитового сложения выходных данных конечного автомата и последней записи РСЛОС. Мы снова синхронизируем и продолжаем в том же духе.<ref name="snow2"/> |
||
=== Детальная схема работы === |
=== Детальная схема работы === |
||
Строка 51: | Строка 73: | ||
: <math> R1=newR1 </math> |
: <math> R1=newR1 </math> |
||
Наконец, [[S-box|S-блок]], обозначаемый <math> S(x) </math>, состоит из четырёх идентичных 8-8 битных S-блоков и перестановки полученных битов. Входные данные разделены на 4 байта, каждый байт входит в нелинейное отображение от 8 бит до 8 бит. После этого отображения биты в результирующем слове переставляются, чтобы сформировать окончательный результат S-блока |
Наконец, [[S-box|S-блок]], обозначаемый <math> S(x) </math>, состоит из четырёх идентичных 8-8 битных S-блоков и перестановки полученных битов. Входные данные разделены на 4 байта, каждый байт входит в нелинейное отображение от 8 бит до 8 бит. После этого отображения биты в результирующем слове переставляются, чтобы сформировать окончательный результат S-блока<ref name = "snow1"> |
||
<ref name = "snow1"> |
|||
{{публикация|статья |
{{публикация|статья |
||
|автор= Patrik Ekdahl, Thomas Johansson |
|автор= Patrik Ekdahl, Thomas Johansson |
||
Строка 64: | Строка 85: | ||
|pages= 167-168 |
|pages= 167-168 |
||
|ссылка= https://www.semanticscholar.org/paper/SNOW-A-new-stream-cipher-Ekdahl-Johansson/900e081fa7ba0d0b45e36185e327e1081bf55d28?p2df |
|ссылка= https://www.semanticscholar.org/paper/SNOW-A-new-stream-cipher-Ekdahl-Johansson/900e081fa7ba0d0b45e36185e327e1081bf55d28?p2df |
||
}} |
}}</ref>. |
||
== Известные атаки == |
== Известные атаки == |
||
* В феврале 2002 года Филипп Хоукс и Грегори Роуз описали атаку методом предположений и определений на SNOW 1.0, в котором используются в основном два свойства, чтобы снизить сложность атаки ниже исчерпывающего поиска ключей. Во-первых, тот факт, что автомат имеет только один вход s(1). Это позволяет злоумышленнику инвертировать операции в конечном автомате и получать больше неизвестных только из нескольких предположений. Второе свойство — неудачный выбор полинома обратной связи в SNOW 1.0 |
* В феврале 2002 года Филипп Хоукс и Грегори Роуз описали атаку методом предположений и определений на SNOW 1.0, в котором используются в основном два свойства, чтобы снизить сложность атаки ниже исчерпывающего поиска ключей. Во-первых, тот факт, что автомат имеет только один вход s(1). Это позволяет злоумышленнику инвертировать операции в конечном автомате и получать больше неизвестных только из нескольких предположений. Второе свойство — неудачный выбор полинома обратной связи в SNOW 1.0<ref> |
||
{{публикация|статья |
{{публикация|статья |
||
|автор = Philip Hawkes, Gregory G. Rose |
|автор = Philip Hawkes, Gregory G. Rose |
||
Строка 78: | Строка 99: | ||
|ссылка= https://link.springer.com/chapter/10.1007/3-540-36492-7_4 |
|ссылка= https://link.springer.com/chapter/10.1007/3-540-36492-7_4 |
||
}} |
}} |
||
</ref> |
</ref>. |
||
* В августе 2003 года Даи Ватанабе, [[Бирюков, Алекс|Алекс Бирюков]] и Кристоф Де Канньер описали атаку на SNOW 2.0 методом линейной маскировки. Эта атака использует <math> 2^{230}</math> битов потока и <math> 2^{225}</math> шагов анализа, что быстрее, чем исчерпывающий поиск 256-битного ключа |
* В августе 2003 года Даи Ватанабе, [[Бирюков, Алекс|Алекс Бирюков]] и Кристоф Де Канньер описали атаку на SNOW 2.0 методом линейной маскировки. Эта атака использует <math> 2^{230}</math> битов потока и <math> 2^{225}</math> шагов анализа, что быстрее, чем исчерпывающий поиск 256-битного ключа<ref> |
||
{{публикация|статья |
{{публикация|статья |
||
|автор = Dai Watanabe, Alex Biryukov, Christophe De Cannière |
|автор = Dai Watanabe, Alex Biryukov, Christophe De Cannière |
||
Строка 90: | Строка 111: | ||
|ссылка= https://link.springer.com/chapter/10.1007/978-3-540-24654-1_16 |
|ссылка= https://link.springer.com/chapter/10.1007/978-3-540-24654-1_16 |
||
}} |
}} |
||
</ref> |
</ref>. |
||
== Применение == |
== Применение == |
||
SNOW 2.0 — это один из потоковых шифров, выбранных организацией [[International Organization for Standardization|ISO/IEC]] за [[Стандарты шифрования данных|стандарт]] ISO/IEC 18033-4<ref> |
SNOW 2.0 — это один из потоковых шифров, выбранных организацией [[International Organization for Standardization|ISO/IEC]] за [[Стандарты шифрования данных|стандарт]] ISO/IEC 18033-4<ref> |
||
Строка 104: | Строка 125: | ||
</ref>, который определяет функции вывода для объединения ключевого потока с открытым текстом, генераторы ключевого потока для создания ключевого потока и идентификаторы объектов, назначенные выделенным генераторам ключевого потока в соответствии с ISO/IEC 9834 для поточных шифров. |
</ref>, который определяет функции вывода для объединения ключевого потока с открытым текстом, генераторы ключевого потока для создания ключевого потока и идентификаторы объектов, назначенные выделенным генераторам ключевого потока в соответствии с ISO/IEC 9834 для поточных шифров. |
||
SNOW 3G |
SNOW 3G<ref name = snow3g> |
||
<ref> |
|||
{{публикация|статья |
{{публикация|статья |
||
|автор = J. Molina-Gil, Caballero-Gil, Caballero-Gil, Amparo Fúster-Sabater |
|автор = J. Molina-Gil, Caballero-Gil, Caballero-Gil, Amparo Fúster-Sabater |
||
Строка 118: | Строка 138: | ||
|ссылка= https://link.springer.com/chapter/10.1007/978-3-319-01854-6_51 |
|ссылка= https://link.springer.com/chapter/10.1007/978-3-319-01854-6_51 |
||
}} |
}} |
||
⚫ | |||
</ref> |
|||
⚫ | |||
== Примечания == |
== Примечания == |
||
Строка 127: | Строка 146: | ||
[[Категория:Потоковые шифры]] |
[[Категория:Потоковые шифры]] |
||
[[ВП:ПЕР]] |
|||
{{Кандидат в добротные статьи|11 ноября 2020}} |
{{Кандидат в добротные статьи|11 ноября 2020}} |
Версия от 21:37, 25 ноября 2020
SNOW — словоориентированный синхронный поточный шифр, разработанный Лундском университете (Швеция). На данный момент у него существует 3 модификации: SNOW 2.0, SNOW 3G, SNOW-V, последние две из которых используются для безопасной передачи мобильных данных.
История
SNOW 1.0, первоначально просто SNOW[1], был разработан в 2000 году. Шифр работает с 32-битными словами и поддерживает как 128-, так и 256-битные ключи. Шифр состоит из комбинации регистра сдвига с линейной обратной связью (РСЛОС) и конечного автомата (КА), где РСЛОС также передает функцию следующего состояния КА.
В первой версии были обнаружены слабые места[2], и в результате SNOW не был включен в набор алгоритмов NESSIE. В 2003 году авторы разработали новую версию шифра SNOW 2.0[3], в которой устранили недостатки и улучшили производительность. Во время оценки ETSI SAGE[4], которая предоставляет разработчикам стандартов криптографические алгоритмы и протоколы, предназначенные для предотвращения мошенничества, несанкционированного доступа к публичным и частным телекоммуникационным сетям и конфиденциальности данных пользователей, алгоритм шифрования был дополнительно изменён, чтобы повысить его устойчивость к алгебраическим атакам. Результатом таких улучшений в 2006 году стала модификация шифра SNOW 3G[5][6].
В 2019 году Ericsson Research совместно с Лундским университетом пересмотрели алгоритм SNOW 3G и обновили его до нового, более быстрого шифра под названием SNOW-V[7], который может быть использован для безопасной передачи данных в новом поколении связи 5G.
Cхема работы SNOW
Общая схема работы
Генератор состоит из регистра сдвига с линейной обратной связью длины 16 над полем . Выход регистра подается на вход конечного автомата. КА состоит из двух 32-битных регистров, называемых R1 и R2, а также некоторых операций для вычисления вывода и следующего состояния (следующего значения R1 и R2). Работа шифра выглядит следующим образом. Сначала выполняется инициализация ключа. Эта процедура обеспечивает начальные значения для РСЛОС, а также для регистров R1, R2 в конечном автомате. Затем первые 32 бита ключевого потока вычисляются путем поразрядного сложения выходных данных КА и последней записи РСЛОС. После этого весь шифр синхронизируется один раз, и следующие 32 бита ключевого потока вычисляются путем ещё одного побитового сложения выходных данных конечного автомата и последней записи РСЛОС. Мы снова синхронизируем и продолжаем в том же духе.[2]
Детальная схема работы
В начальный момент времени t = 0 происходит инициализация регистра сдвига 32-битными значениями .
Обратная связь регистра сдвига задается многочленом:
где порождается неприводимым многочленом
- ,
над и .
Выход КА назовем . Он рассчитывается по следующей формуле:
- ,
где — целочисленное сложение .
Выход конечного автомата сравнивается с по модулю 2 для формирования потокового ключа, то есть
- ,
где — сложение по mod2.
Для конечного формирования шифртекста потоковый ключ сравнивается с открытым текстом по модулю 2. Внутри конечного автомата новые значения для R1 и R2 присваиваются по следующим формулам:
- ,
где — циклический сдвиг влево
Наконец, S-блок, обозначаемый , состоит из четырёх идентичных 8-8 битных S-блоков и перестановки полученных битов. Входные данные разделены на 4 байта, каждый байт входит в нелинейное отображение от 8 бит до 8 бит. После этого отображения биты в результирующем слове переставляются, чтобы сформировать окончательный результат S-блока[1].
Известные атаки
- В феврале 2002 года Филипп Хоукс и Грегори Роуз описали атаку методом предположений и определений на SNOW 1.0, в котором используются в основном два свойства, чтобы снизить сложность атаки ниже исчерпывающего поиска ключей. Во-первых, тот факт, что автомат имеет только один вход s(1). Это позволяет злоумышленнику инвертировать операции в конечном автомате и получать больше неизвестных только из нескольких предположений. Второе свойство — неудачный выбор полинома обратной связи в SNOW 1.0[8].
- В августе 2003 года Даи Ватанабе, Алекс Бирюков и Кристоф Де Канньер описали атаку на SNOW 2.0 методом линейной маскировки. Эта атака использует битов потока и шагов анализа, что быстрее, чем исчерпывающий поиск 256-битного ключа[9].
Применение
SNOW 2.0 — это один из потоковых шифров, выбранных организацией ISO/IEC за стандарт ISO/IEC 18033-4[10], который определяет функции вывода для объединения ключевого потока с открытым текстом, генераторы ключевого потока для создания ключевого потока и идентификаторы объектов, назначенные выделенным генераторам ключевого потока в соответствии с ISO/IEC 9834 для поточных шифров.
SNOW 3G[6]выбран в качестве генератора потоковых ключей для алгоритмов шифрования 3GPP UEA2 и UIA2[11].
Примечания
- ↑ 1 2 Patrik Ekdahl, Thomas Johansson. SNOW-a new stream cipher : [англ.] // Proceedings of first open NESSIE workshop, KU-Leuven. — 2000. — 13 November. — P. 167-168.
- ↑ 1 2 Patrik Ekdahl, Thomas Johansson. A New Version of the Stream Cipher SNOW : [англ.] // Springer. — 2003. — Vol. 2595. — P. 47-61. — ISSN 0302-9743.
- ↑ O. Billet, H. Gilbert. Resistance of SNOW 2.0 Against Algebraic Attacks : [англ.] // Springer. — 2005. — Vol. 3376. — P. 19-28. — doi:10.1007/978-3-540-30574-3_3.
- ↑ Security algorithms .
- ↑ UEA2 Design and Evaluation Report (англ.) (6 сентября 2006).
- ↑ 1 2 J. Molina-Gil, Caballero-Gil, Caballero-Gil, Amparo Fúster-Sabater. Analysis and Implementation of the SNOW 3G Generator Used in 4G/LTE Systems : [англ.] // Springer. — 2013. — Vol. 239. — P. 499-508. — ISBN 978-3-319-01854-6. — doi:10.1007/978-3-319-01854-6_51.
- ↑ P.Ekdahl, T.Johansson, A.Maximov, J.Yang. A new SNOW stream cipher called SNOW-V : [англ.] // ToSC. — 2019. — Vol. 2019, no. 3. — P. 1-42. — doi:10.13154/tosc.v2019.i3.1-42.
- ↑ Philip Hawkes, Gregory G. Rose. Guess-and-determine attacks on SNOW : [англ.] // Springer. — 2002. — Vol. 2595. — P. 37–46. — doi:10.1007/3-540-36492-7\_4.
- ↑ Dai Watanabe, Alex Biryukov, Christophe De Cannière. A Distinguishing Attack of SNOW 2.0 with Linear Masking Method : [англ.] // Springer. — 2003. — Vol. 3006. — P. 222-233.
- ↑ ISO/IEC 18033-4:2011 : Information technology — Security techniques — Encryption algorithms — Part 4: Stream ciphers : [англ.]. — 2. — International Organization for Standardization (ISO), 2011. — 92 p.
- ↑ UEA2 & UIA2 Specification (англ.) (16 марта 2009).
Статья является кандидатом в добротные статьи с 11 ноября 2020. |