id: Гость   вход   регистрация
текущее время 11:49 29/03/2024
Автор темы: Вий, тема открыта 15/04/2013 20:47 Печать
Категории: криптоанализ, атаки, полный перебор
https://www.pgpru.com/Форум/Криптография/SAThome-РаспределенныеВычисления
создать
просмотр
ссылки

SAT@home – распределенные вычисления


Присоединился к российскому проекту SAT@home, осуществляемому под эгидой РАН с использованием системы распределенных вычислений на основе BOINC.


Научная цель проекта описывается здесь.

........
........
Крайне привлекательным классом задач, для решения которых можно использовать SAT-подход, являются задачи криптоанализа. Сразу оговоримся, что мы не решаем задачи дешифровки реальных конфиденциальных данных. Все рассматриваемые нами тесты сгенерированы случайным образом. В этом плане наша работа направлена на исследование стойкости современных систем шифрования и подразумевает реальную помощь в создании новых систем шифрования. Наиболее сильным достигнутым нами практическим результатом является успешный логический криптоанализ (то есть в форме SAT-задачи) генератора ключевого потока широко известного шифра A5/1. Данный результат был получен в 2009 году с использованием системы BNB-Grid (статья в Трудах ИСА РАН, статья на Arxiv, статья в Lecture Notes in Computer Science). В 2010-2011 годах появились исследования (см., например, эту работу), в которых также был осуществлен реальный криптоанализ A5/1, но с использованием совершенно других методов (по сути, использовалась продвинутая техника rainbow таблиц). Однако даже самые хорошие rainbow-таблицы не покрывают все ключевое пространство на 100%. Поэтому в ближайшей перспективе в рамках SAT@home предполагается решение задач поиска инициализирующих последовательностей для A5/1, не покрываемых лучшими известными rainbow таблицами.

В дальнейшем предполагается использовать SAT@home для исследования других криптографических функций, для решения некоторых «крайне трудных» задач дискретной оптимизации, в частности, квадратичной задачи о назначениях (QAP), а также для решения задач из области биоинформатики (исследование поведения дискретных моделей генных сетей).



На мой взгляд довольно интересно и, надеюсь, полезно.


Если позволите – прикладной вопрос. Использую Linux, ядро 3.5.0-17-generic. Видеокарта Nvidia Geforce 630. Драйвер для карты установлен, но при вычислениях не используется GPU, хотя в настройках клиента BOINC настройка "Использовать ГП" выставлена. На странице статистики 2-й идет машина с Linux и использованием для вычислений GPU, т.е. в принципе в данном проекте использовать GPU можно.



 
Комментарии
— Гость (16/04/2013 00:56)   <#>
SETI-2005, SETI-2009, SETI-2011, SETI-2012.

Вий, я ждал этого. Я уже терял надежду, но продолжал верить. И МММ-2013 SETI-2013 таки появился! Спасибо Вам! Надеюсь, что вы не погорели при участии в МММ-2012 SETI-2012.
— Вий (16/04/2013 05:35)   профиль/связь   <#>
комментариев: 510   документов: 110   редакций: 75
Почему SETI? SETI это SETI, ну я понял, Вы образно.
Мне то же понравилось, что наконец-то появился российский проект. Можно смело считать и ни в чем не сомневаться, заодно помочь своей академии наук.
— Гость (16/04/2013 23:09)   <#>
Почему SETI?
Потому, что BOINC летает и там и тут. Это тоже образно.

практическим результатом является успешный логический криптоанализ (то есть в форме SAT-задачи) генератора ключевого потока широко известного шифра A5/1
SAT-задача — это вот это? A5/1 уже давно не жилец. По ссылке видно, что ещё в 2010ом году сломали (причём практический взлом) A5/3, а эти нам вещают про взлома A5/1? Они действительно отстают, или только кажется?
— Гость (17/04/2013 08:26)   <#>
мы не решаем задачи дешифровки реальных конфиденциальных данных
Как в этом можно быть уверенным?
— unknown (17/04/2013 09:57, исправлен 17/04/2013 10:04)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
мы не решаем задачи дешифровки реальных конфиденциальных данных

Как в этом можно быть уверенным?

Они просто могут досчитывать и оптимизировать rainbow-таблицы, например, чтобы расшифровывать налету. Такие таблицы и не являются взломом какого-то конкретного шифртекста — это массив данных для ускорения криптоанализа любого шифртекста. Они хотя бы обещают его опубликовать? Или будут использовать коллективные наработки в своих целях?


Кое-что по теме вот по этой ссылке ещё:


Незадолго до написания данной статьи был реализован набор таблиц, названный "Берлинским набором", совместно с утилитой поиска Kraken. Таблицы были распространены через битторент в специальном транспортном формате. Они составили на этот момент 1,5 Тбайта данных. Транспортный формат может быть перекодирован в актуальный формат чтения, занимающий всего 1,7 Тбайт дискового пространства. На тот момент таблицы покрывали 22% ключевого пространства. Если ключ содержится в таблице, то Kraken обычно находит его за несколько минут (в среднем от 1 до 4 минут) на машине с процессором Intel Core2 Quad 2.33 GHz с таблицами, разделёнными на несколько дисков. Использование твёрдотельных накопителей вместо обычных жёстких дисков значительно увеличивает скорость поиска, но повышает затраты.

Это было по состоянию дел на 2011 год.


По ссылке видно, что ещё в 2010ом году сломали (причём практический взлом) A5/3

Как бы да, но:


Поскольку новая атака использует одновременно как связанные ключи, так и подобранные сообщения, то не может быть применена на практике против того специфического способа, которым алгоритм KASUMI используется в качестве стандарта шифрования A5/3 в телефонных сетях GSM третьего поколения.

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

— Гость (05/05/2013 23:05)   <#>
Лучше бы тоже инопланетян поискали...
— Slon (10/07/2013 13:27)   <#>
В этой программе как я понял просчитываются разные проекты, одни заканчиваются, другие начинаются, т.е. не только те, что касаются криптоанализа. Думаю можно для своих посчитать.
— Slon (30/07/2013 10:06)   <#>
Еще 2 российских проекта распределенных вычислений: OPTIMA@HOME.RU и Gerasim@home, второй правда имеет задания только для windows.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3