Опасность использования «учебных» криптопротоколов

Написать данную статью меня побудил не столько сам пост от пользователя EugeneSukhov, сколько первый комментарий от @AstralMan.

Действительно, зачастую увидев описание или даже готовую реализацию (соответствующую описанию) криптографического протокола высокого уровня, некоторые люди пытаются её тут же внедрить в собственный проект и объявить об этом широкой общественности (просьба не воспринимать это как камень в огород AstralMan). А ведь такое решение далеко не самое удачное! Описание криптопротокола, как правило, не содержит различных необходимых проверок на стороне участников и уточнений, имеющих критическую важность при реальном использовании. История знает множество примеров, когда протокол, основанный на стойких и прошедших испытание временем алгоритмах шифрования, хеширования и т.д. оказывался взломанным именно из-за самой логики построения, и из-за таких «мелочей» как проверки и уточнения. Описание криптопротокола, демонстрирующее саму его идею, будем называть учебным.

Сразу замечу, что протокол аутентификации из статьи EugeneSukhov является учебным. Это значит, что при некоторых условиях вполне реально провести на него атаку, что и будет продемонстрировано в дальнейшем. Однако это не значит, что протокол плохой, а его автор – не профессионал. Это значит лишь то, что автор хотел донести до читателей высокоуровневую концепцию протокола, а точную дотошную спецификацию протокола, которая передана разработчикам для дальнейшей «боевой» реализации, опустил по причинам неуместности.

Возьмем для примера хоть RSA и допустим, что мы решили передать только один байт при помощи данной криптосистемы. Использование учебной RSA естественно закончится провалом! Перехватив шифртекст, злоумышленник моментально восстановит открытый текст (тот самый байт) методом полного перебора чисел от нуля до 255. «Боевая» RSA такого произвола не должна допускать, что и происходит при грамотной реализации.

В дальнейшем будем считать, что злоумышленнику (или нарушителю) доступен полный арсенал разномастных гадких действий, таких как «прослушка» канала общения, сохранение всех перехваченных сообщений, подмен сообщений, отправка ранее перехваченных сообщений и т.д. Будем также предполагать, что нарушитель может украсть базу данных с сервера. Уточню, что все эти предположения не расходятся с предположениями автора анализируемого учебного криптопротокола.

Перейдем собственно к тому виду протокола, каким представил его автор.

image

Обратим внимание на самую последнюю пересылку от клиента к серверу M=hash(RND). Казалось бы, зачем хеширование? Можно просто переслать RND и на этом закончить. Но не все так просто. Для начала рассмотрим ослабленную версию протокола аутентификации, без использования хеширования на последней пересылке и укажем на его недостатки. Схема протокола будет выглядеть так:

image

Первый недостаток состоит в том, что в ослабленной версии протокола клиент играет роль так называемого «Оракула расшифровки». Действительно, сервер высылает клиенту сообщение (в нашем случае RND) зашифрованное на открытом ключе клиента. Клиент дешифрует сообщение при помощи своего закрытого ключа и отправляет сообщение в открытом виде обратно серверу. Такие стратегии построения протоколов являются «нестандартными», несут потенциальную уязвимость и, в некотором смысле, говорят о дилетантстве автора протокола.

Второй недостаток более серьезный и кроется в том, что протокол взламывается при некоторых оговорках практически мгновенно. Опишем атаку. Предположим, что нарушитель узнал число N – модуль криптосистемы RSA. Сделал ли он это, перехватив данные на этапе регистрации, или украл базу с сервера сейчас не важно. Главное, что N ему известно. Также предположим, что для шифрования сообщения {d||N} на симметричном ключе K выбран режим счетчика (вполне реальная ситуация). Это значит, что нарушитель сможет легко сформировать сообщение {d||p}_K при помощи модификации сообщения {d||N}_K, где p – специально выбранное им простое число, и отправить сообщение клиенту. Справедливость этого утверждения я хотел бы возложить на плечи читателя. Далее. Злоумышленник выбирает число p таким образом, что p-1 имеет «хорошее» (в криптографическом смысле) разложение на множители, а также превосходит d (закрытый ключ клиента). Затем вместо {RND}_e нарушитель высылает g — образующий группы Z_p^*. Ничего не подозревающий клиент в полном соответствии с протоколом на последней пересылке высылает злоумышленнику g^d (mod p). Используя алгоритм Полига-Хеллмана нарушитель вычисляет закрытый ключ клиента d за полиномиальное время. После этого, нарушитель сможет всегда выдать себя за клиента.

А теперь вернемся к рассмотрению протокола «в оригинале», так, как представил его автор (с хешированием на последней пересылке). Я утверждаю, что если k – длина закрытого ключа клиента d в битах, то реально вычислить закрытый ключ менее чем за k попыток клиента аутентифицироваться на сервере. Математических выкладок, доказывающих представленное утверждение в самой статье я приводить не буду, поскольку они достаточно объемны и не рассчитаны на широкий круг читателей. Тем не менее, чтобы не быть голословным, опишу, как можно вычислить несколько младших бит ключа d за единственную попытку аутентификации клиента на сервере. Очевидно, что возможность такового вычисления говорит об уязвимости учебного протокола. Ещё раз заострю внимание читателя, что уязвимость учебного протокола – «штатная» ситуация, которая может ровным счетом ничего не говорить о стойкости «боевого» протокола. Ранее сделанные предположения о том, что злоумышленнику известно число N и что для симметричного шифрования используется режим счетчика, остаются по-прежнему в силе.

Возьмем для нашего скромного примера простое число p = 65537 = 2^16 + 1. В Z_p^* выберем элемент g, генерирующий Z_p^*. Вычислим значения hash(g), hash(g^2), hash(g^3),…, hash(g^{p-1}) и сохраним их у себя на компьютере в виде таблицы. Времени и памяти на эту операцию у нас уйдет крайне мало. Перехватим данные от сервера к клиенту и, как ранее было описано подменим N на p, RND на g. В результате получим от клиента хэш от неизвестного элемента – hash(g^i), найдем его у себя на компьютере в таблице и восстановим i. Таким образом, мы приходим к уравнению
g^d=g^i mod p

Из него следует, что d = i + a(p-1), где а – некоторое неизвестное нам число. Получим, что d = i + 2^16*a. Если мы представим число i как битовую строку длины 16, то она и будет представлять собой последние 16 бит закрытого ключа клиента.

Примечание. Если кому-то не сразу очевиден данный факт, тогда рассмотрим десятичную систему счисления. Например, пусть A = B + 10^3*C. Тогда B – это остаток от деления числа A на 10^3 = 1000. А поскольку 1000 представляет собой степень 10 (мы же работаем в десятичной системе счисления), то B – последние три цифры числа А. Если А = 12345, то А = 345 + 12*1000 и такое разложение единственно для неотрицательного B <= 1000.

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

Послесловие: Данной статьей я хотел подчеркнуть, что те «готовые» решения, алгоритмы и протоколы в области криптографии, которые можно найти в открытом доступе в литературе или Интернете вовсе не «готовые», они — учебные. Если вы хотите, чтобы в вашем проекте были заложены действительно надежные защитные механизмы, позаботьтесь о наличии в вашей команде человека с профильным образованием и опытом в области защиты информации. Эта область крайне обширна, сложна и многообразна, чтобы в ней разобраться с наскока, уверяю вас. Всем успехов и спасибо за внимание!

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 19

    +2
    Не могу не согласится, путь от концепции до рабочий версии обычно долог и не прост. И это касается любых разработок.
      –7
      Невероятен эффект от «наведённого контекста», только с 5 раза прочитал в заголовке статьи, что это не слово «криптопроктолог».
        0
        Да хватит, минусовать, я честное слово несколько раз прочитал в названии статьи «учебных криптопроктологов»
        не тролю же
      • UFO just landed and posted this here
        • UFO just landed and posted this here
            0
            Угу. Из других подобных азов: если в асинхронном зашифрованном сообщении вы не указываете, например, уникальное время, то злоумышленник сможет перехватить это сообщение и отреплеить.
            А если вы проверяете уникальность времени, но при приёмке не проверяете это время, то есть шанс, что злоумышленник сможет заджамить оригинальное сообщение, а вам проиграть копию.
              0
              Что Вы подразумеваете под уникальным временем? Как можно проверить время на уникальность? 18 июля 2011 года 1 час ночи, 11 минут, 36 секунд — уникальное время? И что вы имеете ввиду под асинхронным зашифрованным сообщением? Не уверен, что до конца Вас понял.
                0
                Уникальное — для стороны, принимающей сообщение. Если не хватает времени, используют дополнительную последовательность уникальных значений (собственно, так и надо, просто иногда для простоты пользуются временем).

                Асинхронное — имеется в виду, что сообщение не привязано иным способом (например, хотя бы, tcp-сессией) к контексту, по которому можно идентифицировать это сообщение (или отсеять идентичные сообщения от злоумышленников).
                  0
                  То есть предполагается, что сторона, принимающая сообщение не может получить два сообщения от разных адресатов в одно и то же время? Сообщение №1 получено во время Х, это время уникально, окей. И если вдруг пришло сообщение №2 от другого адресата во время Х, то оно отклоняется? Х то уже не уникально! Или я снова неправильно вас понял?
                  Есть такой механизм, как метки времени. Слово «уникальность» в нем отсутствует. У многих криптоаналитиков возникают серьезные сомнения по поводу эффективности использования меток времени. Я разделяю их точку зрения целиком и полностью. Если Вас или кого-либо заинтересует почему именно, с удовольствием расскажу в отдельном комментарии.
                  То, как Вы ввели понятие асинхронности не соответствует что ли «чистой криптографии». В ней нет tcp сессий и прочих благ современности. Есть канал общения, Алиса, Боб, посередине злой Трент. Поэтому я, признаться, теряюсь в догадках, к какой области относятся подобные приведенному Вами азы. К криптографии вряд ли.
                    0
                    Я максимально упростил схему (и опустил некоторые вещи, понятные из контекста, типа того, что речь идёт об ассиметричной криптографии). И я не на 100% владею терминологией, да, — только некоторыми азбучными прикладными технологиями, нарушения которых встречаю регулярно (и с этими нарушениями приходится бороться).

                    Если пришло сообщение №2, идентичное первому — то вполне логично его либо отклонить, либо поднять тревогу (либо ещё что-то, в зависимости от приложения).

                    «Метки времени» у меня ассоциируются с деятельностью timestamping authority и об этом речи не велось.

                    Речь шла (1) об обеспечении уникальности корректных сообщений, используемых в протоколе (например, в простейшем случае, с использованием указания времени в сообщении), что бы Трент не мог вбросить 100500 таких сообщений и получить от Боба по ним кучу ништяков и (2) о необходимости проверки этого времени (и, соответственно, проверки соответствия хода часов Алисы и Боба), если вероятна атака с помощью перехвата и дальнейшего вбрасывания Трентом перехваченного сообщения, при условии того, что проверить то, что источник коммуникации/транзакции, ассоциированной с сообщением, — на самом деле Алиса, а не Трент, — затруднительно.

                    И, естественно, речь идёт о практических аспектах криптографии для обеспечения распределённых транзакций. Напомню, что математически задача двух генералов принципиально нерешаемая, поэтому кроме криптографии для понижения вероятности атаки приходится применять кучу разных мер, связанных с «обнюхиванием конвертов» (в т.ч. и tcp-сессий/датаграмм, если это важно). И указанные мной моменты — азы, которые, тем не менее, в отрасли невероятно часто нарушаются и из-за этого в реальном мире угоняются машины, теряются бабки и т.п.
              0
              К сожалению не «копался» в QtCrypto, поэтому не могу ничего Вам сказать о его безопасности. Достаточно говорящими в некоторых случаях бывают фамилии авторов ПО. Если они признанные «классики», то с большой вероятностью им можно довериться.
              О самой RSA. Очевидно, что в том примере что я привел атакующий перебирает всевозможные открытые тексты (априори ему известно, что длина текста 8 бит = 1 байт). Учебная RSA тут же ломается. В учебной RSA для противодействия этой атаке не хватает так называемого паддинга, или дополнения сообщения (открытого текста) длиной 8 бит до «нужной» длины, на которую атаку построить не удастся. Паддинг не есть постоянная величина, т.е. он уникален для каждого передаваемого сообщения. Тогда передавая 1 байт Вы передаете на самом деле, допустим, 64 байта (открытый текст + паддинг). А перебрать 2^512 вариантов атакующему крайне трудно…
              RSA очень непростая вещь в плане безопасной реализации, есть ещё дополнительно 1001 подводный камень, будьте внимательны!
            0
            у john_smith даже логин зашифрованный )
              +1
              > Если вы хотите, чтобы в вашем проекте были заложены действительно надежные защитные механизмы, позаботьтесь о наличии в вашей команде человека с профильным образованием и опытом в области защиты информации.

              О, я как раз хотел проконсультироваться с таким человеком. У меня есть opensource проект RC5Simple (криптографическая библиотека).

              В самом начале его разработки за основу взял исходники RSA, вот из этого документа (там есть код в конце).

              Я тогда не понимал, что они по большей части учебные. Так вот, в этих исходниках вроде как правильно написана шифрация/дешифрация одного блока. Но режим шифрования набора блоков в этих исходниках очень странный (если он вообще там есть). Там в цикле постоянно происходит пересчет ключа на основе предыдущего результата шифрования:

              /* Initialize pt1 and key pseudorandomly based on previous ct */
              pt1[0]=ct[0];
              pt1[1]=ct[1];
              for (j=0;j<b;j++)
              key[j] = ct[0]%(255-j);


              Но когда я стал разбираться с режимами шифрования:

              ru.wikipedia.org/wiki/Режим_шифрования

              то не обнаружил там ни одного режима, в котором бы был пересчет ключа. Поэтому, я реализовал обычный Cipher Block Chaining (CBC) режим для связывания блоков шифротекста.

              Вопрос: правильно ли я поступил? И не могли бы вы посмотреть опытным взглядом на исходники, они небольшие (20 Кб), там половина — переработанный копипаст из реализации RSA reference implementation of RC5-32/12/16.
                +1
                  0
                  Давайте я Вам для начала задам такой вопрос: Зачем Вы занялись реализацией криптографической библиотеки, не имея в этом должного опыта? Просто для собственного развития или Вы планируете продвигать библиотеку в массы?
                    0
                    Ответ ниже.
                  0
                  > Давайте я Вам для начала задам такой вопрос: Зачем Вы занялись реализацией криптографической библиотеки, не имея в этом должного опыта? Просто для собственного развития или Вы планируете продвигать библиотеку в массы?

                  Потому что других реализаций на чистом C или C++ я не нашел. Думал, что легко найду. Ничего подобного. Только сложно портируемые монстры типа libcrypt совершенно без документации как встраивать их вовнутрь кроссплатформенного приложения — то есть не тупо использовать через заголовок, а встроить вовнутрь. Чтобы проект без плясок с бубном собирался в Linux, Windows, MacOsX, MeeGo. Плюс стояла задача — программа должна быть Qt-only. То есть, ничего левого подключать для сборки нельзя. Оказалось, что прощще написать своё, чем ковырять чужие поделия.

                  То есть, мне нужна была встраиваемая библиотека шифрования. Таких библиотек не обнаружил в природе.

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

                  webhamster.ru/site/page/index/main/news/167

                  Можете взламывать, исходники открыты.

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

                  ЗЫЖ Возможно, мне и помогла бы libcrypt, и я бы ее расковырял и сделал встраиваемой, но более-менее внятное описание на русском появилось позже, чем я сделал свою библиотеку:

                  habrahabr.ru/blogs/programming/120639/

                    0
                    Возможно вы и правы, насчет отсутствия нужных библиотек в природе. Оставим это без комментариев. Просто постарайтесь представить, что у вас получится в итоге. Возможно, выйдет хорошая годная вещь. Но вероятность этого крайне мала.
                    Приведу гипотетический пример. Я не считаю себя глупым человеком, и хочу спроектировать жилой многоэтажный дом. Уверен, что крупных огрехов аля в однокомнатных квартирах кухня 6 кв.м., а в трехкомнатных — 5 кв.м. я не допущу. Приступаю к работе и в результате получаю полный отрыг. А все потому, что я не разбираюсь в тонкостях. Я могу пользоваться только «бытовой логикой», не зная всех особенностей. Конечно есть вероятность, что удастся выдать стоящий проект дома…
                    Криптография — область далеко не простая. Консультируясь в форумах вы не добьетесь даже малой части нужной вам информации, необходим человек, постоянно направляющий движение в нужное русло.
                    Не хочу сбавлять в вас энтузиазм, честное слово. Просто хочу донести свою точку зрения и призываю задуматься.
                      0
                      Так вы, как профессионал, не могли бы провести аудит кода? Там всего 20Кб вместе с заголовками, комментариями и дебаговыми выводами. Развивать дальше там особо-то и нечего, разве что мелкие баги править да поддержку экзотических платформ добавлять.

                  Only users with full accounts can post comments. Log in, please.