Когда вредно хешировать

    Предисловие
    Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам.

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

    Под сложностью восстановления понимается тот факт, что для нахождения первого прообраза [надёжной криптографической хеш-функции] требуется совершить в среднем не менее $2^{n-1}$ операций хеширования, где $n$ — количество бит в выходе криптографической хеш-функции. Взяв современную хеш-функцию с большим размером выхода (начиная от 256 бит) разработчик информационной системы уверен, что восстановить исходные данные по значению хеш-функции нельзя. Чаще всего он прав.

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

    Пример: номер телефона. Разных номеров телефона с префиксом «+7» и 10 цифрами составляет $10^{10} \approx 2^{33}$. Современные устройства, оптимизированные для перебора значений хеш-функций перебирают миллионы хешей в секунду. Значит, подсчёт значений хеш-функций для всех возможных номеров телефонов с префиксом составляет не более нескольких секунд.

    Пример: номер кредитной карты (PAN, payment card number). Часто номер карты маскируют, открывая первые 4 (6) и/или последние 4 цифры, а остальные скрывая. Всего цифр на карте 16. Можно ли хешировать номера карт с целью скрыть их от злоумышленника? Нет. Если злоумышленник получил 8 цифр из 16 (первые 4 и последние 4), а также значение хеш-функции от полного номера карты, то восстановить полный номер он сможет менее чем за секунду. Для этого ему потребуется перебрать всего $10^{8} \approx 2^{26}$ вариантов номера.

    Интересен пример с адресом электронной почты. Казалось бы, что по значению надёжной хеш-функции невозможно восстановить оригинальный адрес. Количество разных вариантов из 8 латинских букв и 10 цифр уже даёт $36^8 \approx 2^{41}$ вариантов названий почтовых ящиков без учёта разных доменов почтовых служб (@mail.ru, @gmail.com, etc.). Если брать и другие разрешённые символы, а также удлинить адрес, вариантов ещё больше. Но… До 2006 года работал проект «Blue Frog» («голубая лягушка»), который предлагал своим пользователям защиту от спама. Он использовал автоматическое уведомление провайдеров о рассылаемом с их серверов спаме, что заставляло распространителей рекламы отказаться от рассылки спама как минимум на те адреса, которые являлись участниками проекта. Чтобы понять, принадлежит ящик участнику или нет, распространялся файл со списком значений криптографической хеш-функции от каждого адреса почтового ящика участника.

    Предполагалось, что спамеры проверят каждый свой адрес для рассылки рекламы по этому списку и исключат найденные совпадения. Однако наличие файла со значениями хеш-функции позволило злоумышленникам сделать ровно наоборот: идентифицировать именно участников проекта и направить на них усиленные потоки бессмысленных сообщений с целью отказаться от использования проекта «Blue Frog». Через некоторое время после этой атаки (а также других, в том числе DDoS-атак на сервера) проект прекратил свою работу.

    Как и прежде, использование любой соли, которая поставляется вместе со значением хеш-функции, не влияет на время перебора (но по прежнему защищает от атаки по словарю).

    Возможные решения для описанных случаев.

    1. Хешировать не сами значения, а конкатенацию исходного значения и некоторого секрета, который хранится отдельно. Например, не в таблице базы данных (вместе со значениями хеш-функций), а в конфигурации сервера приложений. С аналогичным успехом вместо хеширования можно использовать функцию блочного шифрования на некотором секретном ключе.
    2. Использовать такие хеш-функции, которые являются не только надёжными, но и медленными в вычислении. Как для криптоаналитика, так и для легального пользователя. Примером таких функций являются PBKDF2, bcrypt, scrypt, Argon2, для которых при вызове функции мы дополнительно указываем количество итераций хеширования. Однако если увеличение длины выхода хеш-функции всего на один бит (из 256 или 512) увеличивает сложность атаки криптоаналитика на двоичный порядок (в два раза), то увеличение количества итераций для хеш-функции PBKDF2 в два раза увеличит сложность атак также только в два раза. То есть получение значения хеш-функции даже легальным пользователем становится затратно с точки зрения вычислительных ресурсов и затраченной энергии.

    Послесловие
    Автор будет благодарен за фактические и другие замечания к тексту.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 28

      +2
      Откуда в email только латинские буквы и цифры? И почему 8 символов?
      en.wikipedia.org/wiki/Email_address#Valid_email_addresses
        0

        Речь про оценку снизу. Если брать и другие символы, а также удлинить адрес, вариантов ещё больше. Но...


        Спасибо за комментарий, подумаю, как переформулировать понятнее.

        +1

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

          +2
          Вообще как раз вредно, потому что даёт ложную надежду, что всё безопасно.
          0
          «Однако если увеличение длины выхода хеш-функции всего на один бит (из 256 или 512) увеличивает сложность атаки криптоаналитика на двоичный порядок (в два раза), то увеличение количества итераций для хеш-функции PBKDF2 в два раза увеличит сложность атак также только в два раза.»
          и то и то в 2 раза? либо я что-то не понял, либо криво написано.
            0

            В первом случае сложность удваивает добавление одного бита, во втором — удвоение количества итераций, разве нет?

            0
            Стандарт PCI DSS, описывающий требования к защите карточных данных, запрещает хранить полные номера карт в открытом виде. они должны быть превращены в «нечитаемый формат». Это связано с тем, что большинство платёжных систем имеют анти-фрод защиту и тупой перебор PAN+CVC+expire date поэтому смысл в 6+4 всё таки есть — он не позволяет просто взять и использовать идентификатор из какого-нибудь чека в мусорке.
              +1
              6+4 хранить можно. Но вот держать рядом с ними хешированное значение нельзя.
                0
                хранить хеш от полного номера карты как автор пишет это в принцыпе == хранить номер карты в открытом виде, за такое когда вскорется будет гарантировано ататата!
                  0
                  как вскроется? и зачем вообще это хранить? в логи написал, напечатал на чеке и всё.
                    0
                    как? — случайно или в результате утечки/взлома, ну как обычно это происходит))

                    зачем хранить? — я бы тоже хотел знать ответ на этот вопрос.

                    чем запись в логи отличается от записи в базу? Особенно в ситуации если вы в юрисдикции где логи по закону нужно хранить долго. И на чеке такое тоже не стоит печатать, никто ведь не печатает на чеках полный номер карты, так зачем хеш печатать?
                      0
                      Запись в лог от записи в базу отличается тем что лог это как правило то, что регулярно просматривают в случае возникновения вопрос по той или иной операции, могут отправить его по почте в соседний отдел, а то и вовсе распечатать и выкинуть в мусорку — вещь относительно неконтролируемая. База же в соответствии с PCI DSS имеет ограниченный доступ и по хорошему даже DBA не должен видеть содержимое некоторых столбцов.
                        0
                        суть мысли была в том что «хранить номера карт нельзя, нигде и никогда».

                        И не важно в каком месте или виде, просто открыто номер карты или в виде хеша полного номера карты. Так же не имеет значения куда вы записали номер, в базу или в лог. Вы его сохранили и, «это фиаско...».
                          0
                          А ну это бред — хранить его можно и нужно. Он хранится в процессинге, он хранится в бек-офисе. Он хранится в амазоне и гугл плее. Просто нужно соответствовать стандартам PCI.

                          В открытом видел, там где его могут увидеть случайные люди — на чеках и на логах — его нужно маскировать. Но это и не хранение по сути.
                0
                чтобы не хранить в открытом виде есть шифрование таблиц. 6+4 хранить смысла нет так как данные в таком виде не нужны. В логах и прочих чеках — да, только с маской.
                +1
                Большое спасибо за статью! Прочел на одном дыхании и с удовольствием ознакомлюсь с книгой, когда появится немного времени.

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

                Лично я как-то далеко не сразу понял, почему поставляющаяся вместе с хешом соль не влияет на время перебора. Возможно просто голова задурена работой, а возможно это и правда не на столько очевидно, как кажется когда дошло.
                  +1
                  Я и сейчас не понимаю. Соль нужна для того, чтобы нельзя было сразу всю пачку хэшей отбрутфорсить — т.е. придется перебирать для каждого хэша отдельно.
                    0
                    Просто это не усложняет перебор совсем.
                    Вместо формулы hash(cardnumber) получается hash(salt+cardnumber). А функции хэширования пофиг, что вы в неё подставляете, если не гигабайты, конечно.
                    +3
                    1. Хешировать не сами значения, а конкатенацию исходного значения и некоторого секрета, который хранится отдельно.

                    Надо только учитывать, что сам секрет (соль) должен быть достаточно длинным.
                    Иначе, зная алгоритм хеширования и пару логин/хеш, можно подобрать эту «соль». А потом уже получать исходные данные по любому хешу.
                    Т.е. «соль» и исходный текст при подборе как бы меняются функционалом. Поэтому требования к длине исходного текста переносится на требование к длине секрета.
                      0
                      Ну да, секрет должен занимать террабайт, например. Чтобы усложнить перебор.
                        0
                        Достаточно 128 бит энтропии. Примерно 25 случайных символов или же 160 букв произвольного текста.
                          0
                          Если он лежит рядом, то это не поможет.
                            0
                            Разумеется, он не должен лежать рядом.
                          0
                          Совсем не обязательно. Достаточно комбинации из не менее 8-ми цифр, строчных и прописных букв латинского алфавита (некоторые можно исключить, чтобы не путались с цифрами), чтобы среднее время брутфорса уже превысило все рациональные сроки в большинстве случаев.
                          Ну а если длина текстовой «соли» будет 40-48 случайных символов из указанного набора, то подбирать можно будет до скончания веков.

                          Т.е. требования к длине «соли» должно быть таким же, как и требование к ключам шифрования.
                            0
                            Если он лежит рядом, то это не поможет.
                              0
                              Что Вы имеете в виду под «рядом»?

                              Допустим, «соль» хранится в области, куда доступ напрямую запрещен. Только функции шифрования (хеширования). Это «рядом»?
                                0
                                Рядом это в той же таблице. Ведь так рекомендуют сейчас хранить пароли. Хэш с солью, а соль в соседней ячейке. Или даже в этой, но отделена от хэша разделителем. Тупо, согласен, но так рекомендуют.
                                  –1
                                  На самом деле не так страшен черт… Все зависит от ценности данных.

                                  В некоторых не особо критичных случаях можно не только хранить соль рядом, но и передавать ее открытым текстом:

                                  1. При авторизации сервер передает клиенту случайную «соль» и запоминает ее и время ее генерации.
                                  2. Клиент вычисляет, допустим, MD5(MD5(pass)+salt) и передает серверу.
                                  3. Сервер проверяет время действия «соли». Если «протухла», то отвергает. Иначе вычисляет хеш от хеша с солью и сравнивает с пришедшим.
                                  5. После проверки соль сбрасывается (если удачно) или перегенерируется, если предлагается повторная попытка авторизации.
                                  Можно так же хранить не соль, а уже хеш от посоленного хеша. Кажется, разницы никакой.

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

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

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое