Аналог PGP с обеспечением отрицаемости и наперёд заданной секретности оффлайн?
Обсуждение в соседней теме натолкнуло на мысль: существует ли решение, аналогичное PGP и обеспечивающее для оффлайн-сообщений конфиденциальность и аутентификацию, но плюс отрицаемость и наперед заданную секретность (PFS), ну, и, желательно, тихое уведомление о прессинге. Нашел похожий вопрос на crypto.stackexchange: похоже, что готовых решений пока нет. Возможно, где-то на pgpru это уже обсуждалось, или что-то уже появилось?
комментариев: 393 документов: 4 редакций: 0
В то время как Menezes выясняет отношения с Krawczyk по поводу HMQV, Sarr представляет свой FHMQV, Ustaoglu – CMQV, aYao – OAKE, некто Moxie Marlinspike публикует на github протокол Axolotl (значительно улучшенный OTR с учетом всех замечаний Krawczyk и адаптированный для почты, и, кстати, уже реализованный в SMS-шифровании WhisperSystems-TextSecure и почтовом решении Pond на основе Tor). Вместо навороченной OTR-ровской SIGMA-R используется предельно простой и оригинальный IKE: Triple-DH.
Это DH-обмен ключами X и Y, аутентифицированный имеющимися долговременными ключами A и B. Идея в том, что общий секрет выводится хешированием результатов трех DH: (aY=Ay)|(Bx=bX)|(Xy=Yx) Я нашел только одно упоминание (вопрос) о таком обмене.
Возможно, кто-то сможет подсказать, встречались ли аналоги в публикациях? На сколько это видится надежным?
Дело в том, что в своем аналогичном решении я lege artis применил FHMQV в качестве IKE и далее на протяжении OTR для аутентификации вновь вводимых ключей на основе предыдущих (оригинальное решение против freshness-impersonation (раздел 3.2) при утечке единичного ефемерального секрета), а также COMQV для ключевого окна с PFS отправителя и добавление скаляра к точке кривой 25519 (вместо SMP при использовании общего секрета) (код уже работает, тестирую). Но решения в Axolotl на столько просты и очевидны (используют только обычный DH и хеширование), что теперь возникает сомнение в целесообразности таких математических наворотов.
комментариев: 9796 документов: 488 редакций: 5664
На всякий случай, по классическому DH может оказаться полезной Security Issues in the Diffie-Hellman Key Agreement Protocol.
В частности, там отмечается, что:
Но ведь это — очень древняя вещь, если бы всё можно было сделать легко на основе неё, почему раньше не сделали?
А где доказательство стойкости к атаке навязывания малых подгрупп? Большинство протоколов на (полу)статическом DH именно на этом и погорели. Вроде как DSA и изобрели не из вредности NSA, а от того, что полустатический DH (фактически, Эль-Гамаль) был уязвим к атакам ещё в большей степени.
Пока там все спорят, вот вам небольшие слайды про YAK ещё.
Скорее всего:
комментариев: 393 документов: 4 редакций: 0
Я уже устал их коллекционировать :) В ответ: LLK
Причем вырисовывается общая тенденция: каждый считает свой протокол если не идеалом, то по крайней мере на голову выше всех предыдущих. Именно на этом фоне меня заинтересовал тройной DH: всего пару упоминаний в поисковике! Или все так плохо, или же гениальное просто?
К сожалению, я не достаточно владею математическим аппаратом, чтобы оценить самостоятельно возможность и последствия SSA атаки, а также UKS-атаки. И впервые не могу найти абсолютно никаких работ по данному или похожим протоколам.
комментариев: 9796 документов: 488 редакций: 5664
хакерисследователь уязвимостей, в т.ч. в SSL. Идею тройного DH, как я понимаю, он позаимствовал ещё у какого-то шифрпанка. Никаких работ они не опубликовали. Даже на элементарном логическом уровне подробно не разобрали, что там будет, если человек-посредине будет отправлять сторонам старые значения, значения от предыдущих сеансов или какие-то хитро подобранные модули, пытаясь выудить степень секретного ключа. Ну да, стороны увидят, что хэш не сходится и не начнут сеанс, но не будет ли утечки статического ключа?Если всё так просто, чего же они не направили публикацию хотя бы в IACR? Идея настолько привлекательно проста, что сразу бы нашлись исследователи.
Тут или надо выждать, пока он не распиарит практическую реализацию своего протокола, что её кто-нибудь не ковырнёт и ждать, пока все обожгутся. Или скорее всего, исследователи были в курсе такой схемы, возможно ещё десятки лет назад, никому неинтересно публиковать работу с опровержением сравнительно неавторитетного источника, по фактам того, что и так негласно известно в сообществе.
В то, что это гениальное изобретение — верится в самую последнюю очередь. Сужу по собственным «изобретениям», когда пытаешься что-то упростить или открыть новое, чаще всего выясняется, что:
Сходу не скажу, но мне кажется, что тройной DH — ломается, по крайней мере нестоек к ряду существенных атак для того применения, для которого он задуман.
комментариев: 393 документов: 4 редакций: 0
Вобщем, я получил ответ от автора протокола 3DH Trevor, коллеги Moxie. Он подтвердил, что доказательств пока нет и дал ссылки на похожие протоколы.
Исходит все из ранней работы Menezes (стр.15, Протокол 4)
Позже Kudla привел формальные доказательства в своей же модели, немного модифицировав исходный протокол (глава 5.1)
A еще позже (2006) была показана UKS и предлжен вариант KEA+ (включены долговременные публичные ключи в хеш).
В варианте 3DH публичные ключи в хеш не включаются, но включается gxy
На фоне всей истории конечный вариант действительно выглядит как-то шатко. Все же COMQV хоть и сложнее (требует дополнительной математики на кривых), но кажется надежнее. Тем более, я уже успел прикрутить этот алгоритм к компактной библиотеке ED25519, так что на ней и остановлюсь.
В остальном Axolotl имеет преимущества перед OTR в плане совмещения хеширования ключей в окне (FS) и DH (PFS), что позволяет использовать его в том числе и для почты.
комментариев: 9796 документов: 488 редакций: 5664
Где честно осторожно пишут: "We speculate, that the following protocols meets…", "…at first glance, Protocol 4 may look almost identical…», "If indeed it can be shown that Protocol 4 is a secure AK protocol, then we imaginen be turned into a secure AKC protocol…".
Опять же, вступительная часть работы посвящена тому, что доказательства безопасности протоколов согласования ключей труднодостижимы, это общеизвестный факт, модели Беллейра-Рогвея и Каннети-Кравчика — недостаточны (или вообще надекватны). Причём, в первую очередь, плохо доказуемы именно сокращённые, немодулярные протоколы, где убраны лишние шаги и всевозможные включаемые в сообщения MAC и id.
А дальше:
Т.е. авторы вводят свою оригинальную и мало пока кому понятную систему доказательств т.н. немодулярных протоколов. Ну что ж, пусть продвигают свою модель. Принятие, как обычно в таких случаях, может растянуться на десятилетия. Пока что это представляет скорее теоретический интерес.
В третьей работе, авторы, опять же, предельно осторожно и честно предупреждают:
И после этого, они, якобы, на белом коне со своим AKE+ и новой системой доказательств. Опять же, это скорее теоретический вызов другим исследователям, не более. Спасибо им хоть за предупреждения и адекватную самооценку своей работы.
К тому же, во всех этих работах, включая SMQV (в отличие от ранее обсуждаемых работ Кравчика и др.), не декларируется явно сочетание для какого-то протокола всех требуемых качеств: PFS, отрицаемой аутентификации и готовой оптимизации под оффлайновый обмен.
комментариев: 393 документов: 4 редакций: 0
Нашел интересный проект по тестированию протоколов Tamarin
и их доклад на CSF12. Показана частичная wPFS-атака на KEA+ (получение долговременных ключей).
Подробнее – в файлах описателей протокола KEA (проект на github).
Интересно было бы смоделировать 3DH, но на первый взгляд описатели показались весьма сложными, что немного отбило охоту вникать. По уму это стоило бы сделать автору 3DH.
И на сколько такой автоматизированный символический анализ может быть эффективен без предварительного тщательного разбора?
SMQV (я неверно его обозвал в предущем посте) и FHMQV. Авторы те же, год разницы. Из серии: найти 5 отличий (а отличие в том, что в первом варианте на хеш умножается ефемеральный приватный ключ, а во втором – долговременный). Чего этим добились – так и не понял. А вот в плане отрицаемости, действительно, могут возникнуть непредсказуемые последствия.
комментариев: 9796 документов: 488 редакций: 5664
Были аналогичные попытки автоматизированных доказательств. Это инструмент, вспомогательное средство, что заложите, то и получите за вычетом неидеальности самого этого инструмента.
комментариев: 393 документов: 4 редакций: 0
Composability and On-Line Deniability of Authentication
Авторы формализуют понятие отрицаемости в строгой модели. В конце предлагается собственный протокол, по принципу похожий на
ECC-Based Non-Interactive Deniable Authentication with Designated Verifier
Первую ссылку взял из еще одной интересной работе немного не в тему, но не удержусь процитировать:
Improved Group Off-the-Record Messaging
Соответствует требованиям к проекту, озвученным в соседней теме: авторы предлагают протокол с формальными доказательствами и практическую реализацию в виде плагина для Pidgin (отрицаемого + PFS чата).
Работа свежая (ноябрь 2013), и на фоне такой реализации групповой чат в Cryptocat с его mpOTR без отрицаемости посто блекнет.
комментариев: 393 документов: 4 редакций: 0
Отдельное спасибо лично Вам за то, что направили меня все таки по академическому пути. Перечитываю начало темы и удивляюсь своей наивности.
Кстати, если будет возможность, взгляните на мой вопрос на crypto.stackexchange, так и оставшийся без ответа. Собственно, ответ я получить уже не надеюсь, но хотел услышать ваш совет: возможно, причина в форме подачи вопроса (я там впервые спрашиваю)?
Предыстория такова: email-шифровальщик оказался теретически куда более сложным делом, чем казалось вначале. На сегодня из существующих лучшим есть протокол Axolotl, я его и использовал. Но, не считая обсуждаемой выше 3DH, мне не особо нравится механизм передачи доверия к вводимым ключам: в отличие от OTR, новый паблик-ключ передается под маком, выведенным на основе этого же ключа. Для обеспечения доверия в выведении ключа участвует часть материала от предыдущего DH. Это противоречит теоретическим принципам отрицаемости и PFS (3-й абзац)
Моя идея заключалась в том, чтобы отделить аутентификацию сообщения от аутентификации ключа, используя для последней отрицаемый пруф с нулевым разглашением. Для этого идеально подошел один из китайских протоколов на базе трансформированной схемы Шнорра + ЭльГамаль (и в слайдах) В открытом доступе работу не нашел, поэтому выложил у себя на сайте. Этот протокол считается надежным в цитируемой ранее в теме свежей китайской работе (2013), с ним меряются по производительности (стр.16, табл.1, ссылка [10]).
Но уже после того, как я прикрутил все к Axolotl в виде рабочего и отлаженного С-кода, наткнулся на заброшенный архив форума, где один из участников утверждал, что протокол уязвим и предоставил схему атаки подмены. Наверное, в моей голове чего-то не хватает, т.к. до определенного момента я отслеживаю логику, но потом постоянно теряю ход его мысли, хотя математические выкладки верные. Возможно, я залез в слишком сложные теоретические дебри, но мне сейчас важнее на будущее убедиться в том, что вопрос на crypto.stackexchange корректен, и не моя вина в отсутствии ответа.
комментариев: 9796 документов: 488 редакций: 5664
Именно так. Я тоже считаю их слишком сложными. Это вопрос к топовым исследователям по "bleeding edge" протоколам, которые не обитают на форумах и рассылках, наподобие crypto.stackexchange и пр.
комментариев: 9796 документов: 488 редакций: 5664
X = g, p, ga mod p
Y = g, p, gb mod p
s = KDF ( ga )b mod p = KDF ( gb )a mod p
A → B: MDC_PKEB (idA, X)
B → A: MDC_PKEA (idB, Y, HMACs (idA, X, Y))
A → B: MDC_PKEB (idA, HMACs (idB, Y, X)); MDC_SEs (idA, Message)
комментариев: 393 документов: 4 редакций: 0
Вы перечитывали тему?? Да, давно это было...
Протокол видится надежным, но несколько избыточным. Идея вкладывать DH-ключи в PKE почему-то практически не используется, хотя выглядит весьма привлекательно. Но если мы уж используем общий секрет s для выведения MAC, то почему бы просто не обменяться половинками хеша этого секрета в качестве пруфов? Причем лучше даже вне PKE (в плане отрицаемости).
А вообще идеальным видится вариант включать в PKE-сообщения сразу по два ключа: секрет с одной пары использовать в качестве сессионного, а половинки хеша секрета со второй пары использовать в качестве пруфов. Похоже, так получаем полную отрицаемость как факта, так и содержимого сессии, и PFS (позже утечка обоих PGP-ключей безопасна как для содержимого, так и для доказательства факта сессии).
комментариев: 9796 документов: 488 редакций: 5664
Дело в том, что дискуссия закончилась в /comment78566 упоминанием протокола Axolot. По теории я ничего нового не нарыл, зато на GitHub нашёл любопытные реализации тематических проектов в виде набора питоновских скриптов rxcomm. Там же реализован эфемерный оффлайновый Диффи-Хеллман с PFS, но без отрицаемости, также готовый для оборачивания в PGP-сообщения.
Сначала я отнёсся к такой реализации скептически. Python плохо стыкуется с OpenSSL: сам OpenSSL — неудобный, да и питоновские модули с ним, по отзывам, часто глючат.
Но оказывается, всё делается на удивление проще, OpenSSL — не нужен. Питоновская функция pov обеспечивает возведение в степень по модулю для больших чисел вполне сносно по скорости. Если взять g и p из стандарта, то оффлайновый DH на питоне — это в пределе почти однострочник. Получается абсолютно прозрачный код, отсутствие закладок в котором может проверить кто-угодно.
Есть неплохо работающий модуль работы с GnuPG. Это значит не только, что можно делать готовые обёртки в виде OpenPGP сообщений со всеми нужными параметрами, но и отказаться от OpenSSL для симметричного высокоуровневого шифрования. Когда нужно до ответа от адресата сохранить на диск секретную половинку DH, то её можно зашифровать паролем. А уж GnuPG всё сделает правильно: PBKDF, вектор инициализации, правильный режим шифрования. Об этом всём уже не надо думать, ничего лишнего не нужно тащить в код, всё прозрачно для проверки и негде сделать ошибку. Минималистично, функционально и минимум затрат на разработку.
Наконец, модуль hmac в python тоже есть. Т.к. для почты не нужен bleeding edge, то не надо никакой эллиптики, преждевременного использования Keccak, использования сложного кода и подключения криптолиб. Используются только стандартные функции и модули самого Python и GnuPG, которым мы всё равно доверяем.
А если мой, вполне консервативный протокол зафейлится, то в худшем будет случае будет потеряна отрицаемость, PFS, но стойкость останется на уровне обычной переписки OpenPGP. Я стал ещё раз пересматривать слайды Кравчика и нашёл опечатку в своих формулах.
В принципе, ещё интересна питоновская возможность запаковать шифртекст и все параметры в base64-кодировке внутри JSON-формата. Тогда получатель при расшифровке будет наглядно видеть, что ему приходит. А если ему неинтересна эта отладка (хотя туда можно комментарии и удобные подсказки по связи помещать), то он может скормить JSON-сообщение в питоновский скрипт-обработчик.
Использование PKE с MDC привлекательно тем, что:
P.S. Небольшое уточнение. В референсной имплементации оффлайнового DH OpenSSL действительно не используется. Его подгружают только если не удаётся получить доступ к источнику системной энтропии, чтобы получать энтропию через него. Но для самого оффлайнового DH его не используют. Там и указано, что OpenSSL предназначен для онлайна, в нём много лишнего.
А вот в более практичном исполнении OpenSSL для работы с DH всё-таки используется, но только для подгрузки и парсинга DH-параметров из внешних файлов. Само же вычисление степени происходит без участия OpenSSL.
комментариев: 393 документов: 4 редакций: 0
Для получения максимальной прозрачности я выбрал противоположный путь – максимально низкоуровневую С реализацию, опять же без использования внешних библиотек. Но меня сильно шатнуло в сторону bleeding edge, от чего потом пришлось отказаться. Вот черновик описания протокола, изначально планируемого для проекта. Если не брать во внимание OTR-подобный механизм переписки, то суть IKE сводится к следующему:
A->B: MDC_PKEB ( idA, X )
B->A: MDC_PKEA ( Y, h(Xy) ) (используется вторая половина хеша)
A->B: Z, h(Yx || Zx)
Собственно, Z – это новый вводимый ключ, если его не брать во внимание, то можно переписать так:
A->B: h(Yx) (первая половина хеша)
Собственно, это Abadi, но вместо рандомных значений используются DH-ключи. В ответном сообщении Id не нужен, т.к. инициатор может определить отправителя по пруфу. Важно то, что публичные ключи X и Y по сути являются секретами: X шифруется для Боба, поэтому, получив пруф, выведенный с участием X, Алиса уверена, что автор – Боб. И, учитывая PGP MDC, уверена, что это его Y. Аналогично Боб.
Протокол также интересен своей полной отрицаемостью: после его выполнения и уничтожения приватных ключей x и y утечка даже обоих PGP-ключей безопасна как в плане получения общего секрета, так и в плане доказательства участия сторон в протоколе.
ПС: если у Вас будет время посмотреть, я отправлю черновик протокола OnionPhone. Он использует принцип, предложенный в теме шифрованного радио плюс несколько видов аутентификаций.