Написать данную статью меня побудил не столько сам пост от пользователя EugeneSukhov, сколько первый комментарий от @AstralMan.
Действительно, зачастую увидев описание или даже готовую реализацию (соответствующую описанию) криптографического протокола высокого уровня, некоторые люди пытаются её тут же внедрить в собственный проект и объявить об этом широкой общественности (просьба не воспринимать это как камень в огород AstralMan). А ведь такое решение далеко не самое удачное! Описание криптопротокола, как правило, не содержит различных необходимых проверок на стороне участников и уточнений, имеющих критическую важность при реальном использовании. История знает множество примеров, когда протокол, основанный на стойких и прошедших испытание временем алгоритмах шифрования, хеширования и т.д. оказывался взломанным именно из-за самой логики построения, и из-за таких «мелочей» как проверки и уточнения. Описание криптопротокола, демонстрирующее саму его идею, будем называть учебным.
Сразу замечу, что протокол аутентификации из статьи EugeneSukhov является учебным. Это значит, что при некоторых условиях вполне реально провести на него атаку, что и будет продемонстрировано в дальнейшем. Однако это не значит, что протокол плохой, а его автор – не профессионал. Это значит лишь то, что автор хотел донести до читателей высокоуровневую концепцию протокола, а точную дотошную спецификацию протокола, которая передана разработчикам для дальнейшей «боевой» реализации, опустил по причинам неуместности.
Возьмем для примера хоть RSA и допустим, что мы решили передать только один байт при помощи данной криптосистемы. Использование учебной RSA естественно закончится провалом! Перехватив шифртекст, злоумышленник моментально восстановит открытый текст (тот самый байт) методом полного перебора чисел от нуля до 255. «Боевая» RSA такого произвола не должна допускать, что и происходит при грамотной реализации.
В дальнейшем будем считать, что злоумышленнику (или нарушителю) доступен полный арсенал разномастных гадких действий, таких как «прослушка» канала общения, сохранение всех перехваченных сообщений, подмен сообщений, отправка ранее перехваченных сообщений и т.д. Будем также предполагать, что нарушитель может украсть базу данных с сервера. Уточню, что все эти предположения не расходятся с предположениями автора анализируемого учебного криптопротокола.
Перейдем собственно к тому виду протокола, каким представил его автор.
Обратим внимание на самую последнюю пересылку от клиента к серверу M=hash(RND). Казалось бы, зачем хеширование? Можно просто переслать RND и на этом закончить. Но не все так просто. Для начала рассмотрим ослабленную версию протокола аутентификации, без использования хеширования на последней пересылке и укажем на его недостатки. Схема протокола будет выглядеть так:
Первый недостаток состоит в том, что в ослабленной версии протокола клиент играет роль так называемого «Оракула расшифровки». Действительно, сервер высылает клиенту сообщение (в нашем случае 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.
Естественно, в ходе атаки мы могли бы вычислить и большее количество младших бит закрытого ключа. Отметим, что это количество напрямую зависит от доступной памяти на нашем компьютере, в которой мы можем хранить таблицу хэшей, и производительности ПК.
Послесловие: Данной статьей я хотел подчеркнуть, что те «готовые» решения, алгоритмы и протоколы в области криптографии, которые можно найти в открытом доступе в литературе или Интернете вовсе не «готовые», они — учебные. Если вы хотите, чтобы в вашем проекте были заложены действительно надежные защитные механизмы, позаботьтесь о наличии в вашей команде человека с профильным образованием и опытом в области защиты информации. Эта область крайне обширна, сложна и многообразна, чтобы в ней разобраться с наскока, уверяю вас. Всем успехов и спасибо за внимание!
Действительно, зачастую увидев описание или даже готовую реализацию (соответствующую описанию) криптографического протокола высокого уровня, некоторые люди пытаются её тут же внедрить в собственный проект и объявить об этом широкой общественности (просьба не воспринимать это как камень в огород AstralMan). А ведь такое решение далеко не самое удачное! Описание криптопротокола, как правило, не содержит различных необходимых проверок на стороне участников и уточнений, имеющих критическую важность при реальном использовании. История знает множество примеров, когда протокол, основанный на стойких и прошедших испытание временем алгоритмах шифрования, хеширования и т.д. оказывался взломанным именно из-за самой логики построения, и из-за таких «мелочей» как проверки и уточнения. Описание криптопротокола, демонстрирующее саму его идею, будем называть учебным.
Сразу замечу, что протокол аутентификации из статьи EugeneSukhov является учебным. Это значит, что при некоторых условиях вполне реально провести на него атаку, что и будет продемонстрировано в дальнейшем. Однако это не значит, что протокол плохой, а его автор – не профессионал. Это значит лишь то, что автор хотел донести до читателей высокоуровневую концепцию протокола, а точную дотошную спецификацию протокола, которая передана разработчикам для дальнейшей «боевой» реализации, опустил по причинам неуместности.
Возьмем для примера хоть RSA и допустим, что мы решили передать только один байт при помощи данной криптосистемы. Использование учебной RSA естественно закончится провалом! Перехватив шифртекст, злоумышленник моментально восстановит открытый текст (тот самый байт) методом полного перебора чисел от нуля до 255. «Боевая» RSA такого произвола не должна допускать, что и происходит при грамотной реализации.
В дальнейшем будем считать, что злоумышленнику (или нарушителю) доступен полный арсенал разномастных гадких действий, таких как «прослушка» канала общения, сохранение всех перехваченных сообщений, подмен сообщений, отправка ранее перехваченных сообщений и т.д. Будем также предполагать, что нарушитель может украсть базу данных с сервера. Уточню, что все эти предположения не расходятся с предположениями автора анализируемого учебного криптопротокола.
Перейдем собственно к тому виду протокола, каким представил его автор.
Обратим внимание на самую последнюю пересылку от клиента к серверу M=hash(RND). Казалось бы, зачем хеширование? Можно просто переслать RND и на этом закончить. Но не все так просто. Для начала рассмотрим ослабленную версию протокола аутентификации, без использования хеширования на последней пересылке и укажем на его недостатки. Схема протокола будет выглядеть так:
Первый недостаток состоит в том, что в ослабленной версии протокола клиент играет роль так называемого «Оракула расшифровки». Действительно, сервер высылает клиенту сообщение (в нашем случае 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.
Естественно, в ходе атаки мы могли бы вычислить и большее количество младших бит закрытого ключа. Отметим, что это количество напрямую зависит от доступной памяти на нашем компьютере, в которой мы можем хранить таблицу хэшей, и производительности ПК.
Послесловие: Данной статьей я хотел подчеркнуть, что те «готовые» решения, алгоритмы и протоколы в области криптографии, которые можно найти в открытом доступе в литературе или Интернете вовсе не «готовые», они — учебные. Если вы хотите, чтобы в вашем проекте были заложены действительно надежные защитные механизмы, позаботьтесь о наличии в вашей команде человека с профильным образованием и опытом в области защиты информации. Эта область крайне обширна, сложна и многообразна, чтобы в ней разобраться с наскока, уверяю вас. Всем успехов и спасибо за внимание!
