id: Гость   вход   регистрация
текущее время 13:59 29/03/2024
Автор темы: Гость, тема открыта 02/02/2007 18:57 Печать
http://www.pgpru.com/Форум/Криптография/ПовышениеКриптостойкостиRc4
создать
просмотр
ссылки

повышение криптостойкости rc4


Как известно, криптоалгоритм rc4 содержит слабость в алгоритме развертывания ключа к 256 байтную матрицу ГПСЧ.
Эта уязвимость мешает применению алгоритма, хотя rc4 обладает одним немаловажным достоинством – высокой производительностью.
Нет ни одного криптоалгоритма, который бы даже близко приблизился по производительности к rc4, а поэтому он хорошо подходит для шифрования трафика в высокоскоростных сетях, тобишь для VPN решений.
Поэтому для повышения криптостойкости при сохранении высокой производительности я предлагаю переписать развертку ключа нижеописаным способом:


Матрица из 256 байт заполняется порядковыми номерами эти байт. Береться sha512 хеш от ключа шифрования, в результате мы получаем 64 байта хешированых данных. Пусть каждые два байта описывают пару элементов матрицы, которые нужно поменять местами, таким образом на один хеш мы имеем 32 перестановки. Для того чтобы любой елемент матрицы мог быть переставлен, нам нужно провести минимум 128 перестановок, что эквивалентно четырем sha512 хешам. Второй хеш береться от ключа шифрования и первого хеша, третий от ключа и второго, и.т.д., пока мы не получим нужные нам 256 байт, после чего выполняем описываемые ими 128 перестановок.


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


 
Комментарии
— unknown (03/02/2007 02:23)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Этот алгоритм развертки ключа опирается на стойкость хеш функции sha512, тобишь такой самопал не должен содержать уязвимостей.

Если как то-так, то это префикс-метод:




Если так, то это суффикс-метод:



А ещё можно использовать XOR. Как доказать, что выбранный метод безопасный? Для всех конкретных случаев есть методы анализа. И от всех этих методов при создании PRNG в своё время отказались.

См. например здесь и здесь. Здесь больше про HMAC для аутентификации, но и про свойства PRF тоже.

Заменили хэш на HMAC из двух хэшей (MD5 и SHA-1), и используют PRNG на его основе до сих пор в SSL и других протоколах.

Вот более современный результат, использующий последние достижения в анализе хэш-функций fileдля взлома HMAC, что ещё год-два назад многими считалось невозможным.

Для чего такие сложности, когда нужно стремиться к простому решению?

Дело в том что хэш-функции разрабатывались для контроля целостности файлов, для получения свёртки в цифровой подписи.
А вот в известной книге HAC в главе 9.2.6 утверждается, что для дополнительного применения (генераторы псевдослучайных чисел, получение ключей из основного ключа) хэш функции не конструировались и хотя они пригодны для этого, требуется тщательный анализ и(или) специальная конструкция (обычно HMAC).

Реально ли провести такой анализ?
Подробных сведений нигде нет, но вдруг совместно используя неидеальность самого RC-4, хэш функций, ускоренный методы поиска коллизий и дифференциальные различители, описанные в работе по взлому HMAC, можно придумать какую-то хотя бы чисто теоретическую атаку? Например, зная часть внутреннего состояния матрицы, быстрее найти ключ.

В общем, можно посоветовать по крайней мере использовать HMAC-PRNG вместо непроверенной конструкции из хэшей. Это хотя бы более стандартный способ генерации дополнительных ключей.
— Гость (03/02/2007 03:06)   <#>

Простым решением бы было взять готовый стойкий криптоалгоритм, да к сожалению ничего подходящего просто не существует. К примеру blowfish довольно быстр, но до rc4 ему всеравно очень далеко.


В общем, как вариант можно просто использовать ключ размером 256 байт, вырабатываемый в процессе аутентификации по асимметрике.. При условии случайности такого ключа, его можно непосредственно использовать для перестановок, и не трогать хеши вобще.
Какие еще уязвимости могут быть в rc4, в случае действительно случайного размешивания его prng матрицы?
— Гость (03/02/2007 19:23)   <#>
А как насчёт xTEA?
— unknown (03/02/2007 21:43)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Например в этой работе авторы предложили улучшить RC4, используя исходную матрицу уже заполненную статичными случайными эдементами и заодно сделать шифр 32-битным.
Его смогли тривиально взломать. Были и другие попытки улучшить ключевое расписание. Возможно и Ваша идея тоже кому-то приходила в голову, но её не стали публиковать по причине бесперспективности.

Для RC4 найдено большое число различителей. Он проваливает даже статистические тесты при объеме шифртекста 2 Gb. Есть отклонения в распределении биграмм и т.д. Это не означает практического взлома, но означает дефектность алгоритма.

Все опубликованные работы основаны на оригинальном или ослабленном RC4. Мне неизвестно работ по RC4 с успешно усиленным ключевым расписанием. А делать самому какие-то выводы я бы не решился. В России этим в частности занималась М. А. Пудовкина из МФТИ. Попробуйте узнать мнение оттуда.

Насчёт XTEA: даёт ли он выигрыш в скорости или только в объёме памяти?

Наконец самое общее соображение: идёт конкурс eSTREAM, а никаких убедительных результатов получено не было, может повториться тоже, что было на CryptoNESSIE – финалиста назвать не решатся, по причине непроработанности теории потоковых шифров.


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


Совершенно верно. Ничего подходящего пока и несуществует. Не изобрели ещё.
Или приходиться использовать блочный шифр или если хотите скорость, то надёжность потокового шифра просто никто не может реально гарантировать.
— Гость (04/02/2007 05:43)   <#>

Производительность TEA и XTEA находиться на ужасающем уровне, а разы медленее того же AES, и даже медленее таких ресурсоемких алгоритмов, как IDEA (недостаток которого в использовании операций умножения).
Для сравнения, полученые мной скорости шифрования (в мегабитах в секунду) для процессора core duo 2 2000

rc4 – 350
blowfish – 122
twofish – 80
aes – 55
IDEA – 16
TEA – 12

Вопрос производительности стоит настолько остро, что видимо придется пожертвовать теоретической стойкостью (главное чтобы практических атак не было).
— unknown (04/02/2007 15:00, исправлен 04/02/2007 15:35)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Вам виднее по вашей задаче. Обычно, если нужно повысить скорость и есть много памяти, используют AES, у которого заранее просчитаны комбинации SubBytes и MixColumn в виде готовых таблиц. Т.е. скорость существенно (до x2) зависит от вида оптимизации.

Но до RC4 он конечно всё равно не дотянет.


В OpenSSH используется ARC4-drop.
Теория хорошо рассмотрена fileв этой работе. Несмотря на большое количество атак, хэширование ключа с вектором инициализации (даже без изменения ключевого расписания) и отбрасывание 2n битов потока на выходе перед гаммированием, делают RC4 практически безопасным на сегодняшний момент.
— domov0y (22/05/2007 16:57)   <#>
у меня вопросы по теме

1. а почему не использовать вот такой вариант:
обозначим за keyx случайный байт выработаный генератором rc4 и зашифруем байт следующим образом
(keyx^3*keyx+ keyx^2*keyx+keyx*keyx+keyx) mod 256 xor byte
2. дайте инфу по взлому rc4 или общую инфу по раскрытию информации зашифрованой поточным алгоритмом
— SATtva (22/05/2007 17:12)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
fileО корреляциях между ключом и потоком гаммы RC4.
— unknown (22/05/2007 18:00, исправлен 23/05/2007 08:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Уж сколько было попыток улучшить RC4: Ciphersaber, VMPC
Вот хотя бы почитайте fileVMPC

И вот ещё оттуда же: fileOn the InSecurity of Stream Ciphers Based on Arrays and Modular Addition

ИМХО перспектив нет.
— unknown (23/05/2007 09:48, исправлен 23/05/2007 09:49)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Сам себя процитирую:

Мне неизвестно работ по RC4 с успешно усиленным ключевым расписанием.

В последней работе рассматриваются атаки на RC4-подобные шифры как раз с идеальным ключевым расписанием. Как если бы внутреннее состояние шифра вообще было истинно случайным. Что, как доказывают авторы тоже не спасает.
— domov0y (26/05/2007 14:19)   <#>
т.е. 256 байт и любые ухищрения не помогут поточному шифру удержать безопасность...
а какое количество символов необходимо дляя взлома?
могут ли исправить ситуацию блуждающие ключи (сменяющихся на вырабатываемые случайно, через каждые x символов) при использовании шифра в качестве средства шифрования передачи
?
— unknown (26/05/2007 15:54, исправлен 26/05/2007 15:58)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

а какое количество символов необходимо дляя взлома


Пока что никакое. Практических атак нет. Обычно в них и нет заинтересованности, если удаётся доказать, что алгоритм слишком отличается от идеальной модели.

Блуждающие ключи? Возможно это затруднит анализ, но не повысит стойкость. По крайней мере это непрактично.

Если кого интересуют потоковые шифры, следите за конкурсом eStream

Если лучшие криптографы мира до сих пор не могут изобрести ни одного потокового шифра, для которого была бы такая же уверенность в стойкости, как для блочного шифра, то наверное это не просто так.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3