Опасный алгоритм SHA-1 убирают из библиотек SSH


    Сложность атак на SHA-1. Стоимость указана из расчёта стоимости аренды одного GTX 1060 в 35 долларов/месяц

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

    Об отключении SHA-1 по умолчанию одновременно объявили разработчики опенсорсных библиотек OpenSSH (release notes) и libssh (изменение кода).

    Алгоритм SHA (Secure Hash Algorithm) разработан АНБ совместно с NIST. Первую версию SHA-0 представили в 1993 году, но вскоре АНБ отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта.

    Исправленную версию АНБ опубликовала в 1995 году, она получила название SHA-1.

    Криптографическая хеш-функция SHA-1 (Secure Hash Algorithm 1) генерирует строку из 160 бит, которая называется хэш-дайджестом. Теоретически, дайджесты должны быть уникальными для каждого файла, сообщения или другого входного сигнала, подаваемого в функцию. В качестве входного значения SHA-1 принимает сообщение не более $2^{64}-1$ бит, то есть примерно 2 эксабайта.

    Понятно, что область значений дайджеста меньше области входных значений. Но на практике дайджест-коллизии должны быть неосуществимы, учитывая возможности производительности имеющихся вычислительных ресурсов. К сожалению, SHA-1 уже не соответствует этому критерию.

    В 2017 году сотрудники компании Google и Центра математики и информатики в Амстердаме представили первый способ генерации коллизий для SHA-1.

    Они опубликовали и доказательство: два документа PDF с разным содержимым, но одинаковыми цифровыми подписями SHA-1.


      $ls -l sha*.pdf 
      -rw-r--r--@ 1 amichal  staff  422435 Feb 23 10:01 shattered-1.pdf
      -rw-r--r--@ 1 amichal  staff  422435 Feb 23 10:14 shattered-2.pdf
      $shasum -a 1 sha*.pdf
      38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
      38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf



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

    В последние годы множество программ и сервисов перестали использовать SHA-1 после того, как исследователи продемонстрировали практические способы подделки цифровых подписей, использующих SHA-1. Единодушное мнение экспертов состоит в том, что этот алгоритм теперь не безопасен почти во всех контекстах безопасности.

    Компания Google давно выразила своё недоверие SHA-1, особенно в качестве использования этой функции для подписи сертификатов TLS. Ещё в 2014 году группа разработчиков Chrome объявила о постепенном отказе от использования SHA-1.

    В 2017 году исследователи использовали инфраструктуру Google, чтобы произвести вычисления и проверить теоретические выкладки, сколько займёт поиск коллизии. Разработчики говорят, что это было одно из самых крупных вычислений, которые когда-либо проводила компания Google. В общей сложности было произведено девять квинтиллионов вычислений SHA-1 (9 223 372 036 854 775 808), что потребовало 6500 процессорных лет на первой фазе и 110 лет GPU на второй фазе атаки.

    Блоки сообщений с одинаковым хешем SHA-1


    В 2019 году исследователи Гаэтан Лоран и Томас Пейрин продемонстрировали атаку на отыскание коллизии с выбранным префиксом (chosen-prefix), которая имеет практический смысл для подбора конкретных ключей шифрования PGP/GnuPG. Наконец, в январе 2020 года авторам удалось на порядок оптимизировать атаку и снизить её теоретическую стоимость до коммерчески приемлемой цены (см. таблицу выше и pdf). Для демонстрации они создали пару разных ключей PGP/GnuPG с одинаковыми сертификатами SHA-1.

    В качестве защиты от атаки на отыскание коллизий SHA-1 рекомендуется перейти на более качественные криптографические хеш-функции SHA-256 и SHA-3.

    На это исследование от января 2020 года ссылаются разработчики OpenSSH, которые написали в примечаниях к последнему релизу: «Теперь можно выполнять атаки с выбранным префиксом по алгоритму SHA-1 менее чем за 50 тысяч долларов США. По этой причине в ближайшем будущем мы будем отключать алгоритм подписи открытого ключа "ssh-rsa" по умолчанию. К сожалению, этот алгоритм всё еще широко используется. Несмотря на существование лучших альтернатив, он долгое время оставался единственным алгоритмом подписи открытого ключа, заданным оригинальными SSH RFC».

    В числе лучших альтернатив разработчики OpenSSH называют алгоритмы RFC8332 RSA SHA-2 (поддерживается с версии OpenSSH 7.2 и уже используется по умолчанию, если сервер и клиент его поддерживают), ssh-ed25519 (поддерживается с версии 6.5) и RFC5656 ECDSA (с версии 5.7).

    Для проверки, что сервер при генерации открытого ключа для аутентификации использует слабый алгоритм SHA-1, попробуйте подключиться к нему после удаления алгоритма ssh-rsa из списка разрешённых в ssh(1):

    ssh -oHostKeyAlgorithms=-ssh-rsa user@host

    Если верификация не проходит и другие типа ключей недоступны, то серверное программное обеспечение следует обновить.

    В будущих версиях OpenSSH по умолчанию будет включена опция UpdateHostKeys, при которой клиент будет автоматически переходить на лучшие алгоритмы. Её можно активировать вручную.

    Судя по всему, полное отключение SHA-1 займёт немало времени. Гаэтан Лоран из Национального института исследований в информатике и автоматике (Франция), один из соавторов январского исследования, не ожидает, что разработчики OpenSSH быстро это сделают: «Когда они полностью отключат SHA-1, будет невозможно подключиться с новой версии OpenSSH к устройству со старым SSH-сервером, — пишет он. — Вероятно, перед этим они предпримут ряд постепенных шагов (с громкими предупреждениями). С другой стороны, во встроенных системах с SSH, которые не обновлялись в течение многих лет, вероятно, много проблем с безопасностью, так что, возможно, не так уж плохо будет нарушить их работу… Во всяком случае, я вполне доволен этим ходом, это именно то, чего мы хотели добиться :-)».

    После того как OpenSSH и libssh объявили о планах отключения SHA-1, список пользователей SHA-1 стал короче, но не исчез. Функция всё еще поддерживается в последних версиях библиотеки OpenSSL, которую многие веб-сайты и интернет-службы используют для реализации HTTPS и других протоколов шифрования. Последняя версия компилятора GNU Collection, выпущенная ранее в этом месяце, подписана цифровой подписью с хешем SHA-1.

    Линус Торвальдс сказал, что в репозиториях Git коллизии хеша не представляют угрозы безопасности. Он пояснил, что сть большая разница между использованием криптографического хеша для цифровых подписей в системах шифрования и для генерации «идентификации контента» в системе вроде Git. Когда все данные лежат в открытом доступе, то реальная атака практически невозможна. Авторы научной работы приводят пример атаки на документы с идентичным префиксом. Эта атака успешна, потому что сам префикс «закрыт» внутри документа, как блоб. Если же у нас открытые исходники в репозитории, то это совсем другое дело. Вряд ли можно сделать такой префикс из исходного кода (только из блоба). Другими словами, для создания идентичного префикса и последующей генерации веток кода с одинаковыми хешами SHA-1 придётся внедрить в код некие случайные данные, что сразу же будет замечено. Линус говорит, что есть места, куда можно спрятать данные, но git fsck уже вылавливает такие фокусы. Тем не менее, у Линуса есть план, как уйти от использования SHA-1, чтобы никому даже не пришлось конвертировать свои репозитории.
    Дата-центр «Миран»
    Решения для аренды и размещения ИТ-инфраструктуры

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

      +2
      Какая-то непонятна табличка, стоимость $45k — это за какое время взлома? Если одна 1080ti ломает 34 года, то нужно 34*365=12410 видеокарт для взлома за сутки, к примеру (и то, если оно идеально параллелится) и т.д.
        +7
        $45k это за аренду 1080 Ti на 34 года.

        Стоимость указана из расчёта стоимости аренды одного GTX 1060 в 35 долларов/месяц

        $35 * 12 мес * 107 лет = $44940 за все время использования, что соответствует 45k в таблице. Ну а чтоб за сутки взломать потребуются все те же 45k (при условии аренды на месяц).
          +4
          Ну табличка непонятная, если не читать текст под ней. Хотя и без него можно догадаться.
          «Стоимость указана из расчёта стоимости аренды одного GTX 1060 в 35 долларов/месяц».
          На 1060 ломается 27 лет => 27*12*35 = 11340 USD стоит взлом.
          Вопрос про время взлома какой-то смешной, ясное дело, что параллелится.
          Upd.: ПРостите< не обновил комментарии :(
            +3
            В этом и прелесть облаков, в которую многие не врубаются. Денег стоит решение задачи. А время может быть любым — можно арендовать один серврер и решать 22 года, можно арендовать 8000 серверов и решать один день. ЦЕНА ОДНА И ТА ЖЕ.
              +1
              1. Какое облако предоставит 8000 серверов?


              2. Цена за 22 года точно не изменится?


                0
                1. aws без проблем несколько тысяч предоставит.
                2. разве что снизится.
                  0

                  И будут эти тысячи виртуальными? Тут же нужны реальные железки. Плюс оплата Амазона, насколько я знаю, округляется до часа в большую сторону :)

                    0
                    И будут эти тысячи виртуальными? Тут же нужны реальные железки.
                    а кто мешает взять виртуалки с проброшенным GPU?

                    Плюс оплата Амазона, насколько я знаю, округляется до часа в большую сторону :)
                    уже давно поминутная
                      0
                      кто мешает взять у амазона реальные железки?
              –7
              Сломается куча оборудования, которое вполне работает и еще долго будет работать.
              Вариант, когда лучшее враг хорошего. Уже и так без настройки клиента ssh к коммутатору не подключишься…
              Никто не будет менять оборудование, просто сменят ssh-клиента.
                +1
                Интересно, еще в 2009 читал про то, что специалисты рекомендуют отказываться от MD5 и SHA-1, а некоторые и от SHA-2, потому что кто-то демонстрировал возможность нахождения коллизий в разумное время. И вот спустя 11 лет этот отказ, наконец-то происходит. То ли те специалисты спешили с выводами, то ли сегодняшние отказники не очень торопились.
                  +5
                  Происходит сейчас вторая степень отказа. Первая степень — отказывались от работы с этим в новых программах и переходили на работу по умолчанию с новыми версиями криптографии. А сейчас происходит отказ от совместимости, так что уже нельзя вообще будет работать со старой криптографией.

                  Именно для того, чтобы переход не приводил к проблемам, отказ настолько постепенный, так как в железе обновить криптографию существенно сложнее.
                    0
                    Отрицание — Злость — Торг — Депрессия — Принятие.

                    Ой, хотя это не про SHA-1 было.
                    0
                    вопрос в другом: а что будет если через пару лет найдут ошибки в новых алгоритмах шифрования? Опять весь мир будет кучу времени переходить на надежные?
                      +1
                      Это не только ошибки, но и рост мощности. На какой-нибудь RIVA TNT2 вообще ничего взломать не получилось бы, а вот на современных 1080 уже вон, вполне. Так что через 10 лет буду видюхи, которые за минуты подберут хеши.

                      Короче, да, будет переходить.
                        +1
                        Разве есть какой-то вариант другой? Это как обновления ОС, если есть уязвимость, надо обновляться.
                          0
                          вопрос скорее в другом — позаботились ли разработчики о том, чтобы в дальнейшем замена алгоритма шифрования на более надежный (в случае нахождения изъянов ныне рекомендуемых) требовала минимум усилий со стороны пользователей библиотек шифрования.
                          0
                          Скорее всего появятся девайсы генерирующие ключи с помощью квантовой запутанности.
                          +2
                          А где посмотреть стоимость взлома для актуальных алгоритмов? (SHA-256 etc)
                            0
                            Если в начале не ошиблись, то для SHA-256 умножайте на 7E19
                            (Уязвимости полной не нашли, коллизия за 2^128)
                            0

                            Кстати, а что использовать для идентификации контента взамен? sha1 хороший, имхо, компромисс между скоростью и длиной. Но, похоже, надо искать замену

                              0

                              Например, BLAKE3. Быстрая, длинная и надежная.

                                0

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

                                  0

                                  Ну, тогда используйте identity function :) Правда, для файла в 10 гб идентификатор будет все те же 10 гб, потому что это и будет сам файл, но что стоят такие маленькие неудобства?

                                    0

                                    Я имею ввиду хэш-функции типа CRC32 — быстрые, надёжные, но криптостойкость их абсодютна неважна в таком применении

                                      +1

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


                                      Если же вам нужна хэш функция для балансинга, или, например, для построения хэшмапа, то подойдет и SHA1, и RC4-Hash.


                                      Если же вам вообще нужна контрольная сумма для противодействия непреднамеренному искажению (не для контроля целостности) — то и CRC32 хороший вариант.


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

                                        0

                                        Мне нужно "один хеш — один контент", но мне не нужна защита от преднамеренного взлома. Использовал сначала MD5, потом SHA1 без оглядки на их криптографическую природу. Но MD5 уже много где выпилили потому что она по нынешним временам не криптостойкая, а теперь вот и с SHA1 процесс пошёл.

                                          0

                                          Ну как раз тут речь и идет о том, что для SHA1 правило "один хэш — один контент" больше не выполняется? Какая разница, преднамеренно или нет.


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

                                            0

                                            Это правило не выполняется для любой хеш-функции по определению хеш-функции.


                                            Если бы я хотел использовать sha1 дальше, то я бы не спрашивал на что её заменить. Просто есть мнение,, что криптострйкость в хеш-функциях не бесплатна.

                                            0
                                            > но мне не нужна защита от преднамеренного взлома

                                            Тогда вам и MD5 подойдёт, потому что _случайная_ коллизия в нём имеет вероятность 2^-128. И менять не надо было ничего.

                                            И md5crypt живее всех живых, потому что для second preimage attack нужно уже видеть оригинальный вход функции.

                                            Просто сейчас делают по принципу «нашли одну проблему в MD5/SHA1/etc. — уберём все её использования».
                                              0

                                              На sha1 перешёл, потому что схватил коллизию

                                                0
                                                И вы не думаете, что её создали намеренно?
                                                  0

                                                  Нет, не думаю.

                                            0

                                            В чем разница между "контрольная сумма для противодействия непреднамеренному искажению" и "для контроля целостности"? Можете привести пример?

                                              0

                                              Да, конечно. Разница между ними, как вы заметили, в преднамеренности и, как следствие, в наличии секретной компоненты для противодействия преднамеренности.


                                              Если искажение непреднамеренное (например, случайно флипнулся бит в оперативке, или в ходе передачи по сети) — оно с некоторой равной вероятностью случится в любом бите контента, и построение статистической модели такого искажения не выявит зависимости положения искажения от содержимого измененного бита или его соседей.


                                              Для обнаружения таких случайных модификаций достаточно самых простых мер — раньше, например, для очень небольших пакетов (7-10 бит) использовались биты четности (суммирование по полиному x+1). Для данных большего размера хорошо подходят CRC32 и CRC64, которые тоже суммирование по полиному, просто большего порядка.


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


                                              Почему CRC и коды Рида-Соломона нельзя использовать для контроля целостности? Активный атакующий, цель которого — выдать свои данные за данные изначального отправителя, уже не вписывается в модель случайного шума, меняющего биты, т.к. его изменения зависят от положения в контенте и от значений конкретных бит соседей (например, атакующий ищет "authorized": false, и хочет поменять это на "authorized": true ,). Почему CRC и RS не подходят для защиты от таких изменений? Очевидно, что так как эти алгоритмы не содержат в себе секретной компоненты, атакующий может просто посчитать CRC и RS заново. Даже если используется нестандартный полином, не представляет проблемы его отреверсить при достаточно большом количестве наблюдаемого открытого текста — ни CRC, ни RS не являются криптографически безопасными примитивами, и не обеспечивают защиту от преднамеренной модификации.


                                              Для контроля же целостности можно использовать HMAC — семейство функций с секретным симметричным ключом, основанные на криптографических хэш-функциях. Пересчитать HMAC повторно, даже зная низлежащую функцию (SHA3-256, например), не зная ключа, невозможно, а HMAC безопасен ровно настолько, насколько безопасна низлежащая функция. Поэтому если низлежащая функция (SHA1) уязвима к второй preimage атаке (для оригинального текста x найти такой x', который sha1(x) == sha1(x') при x != x'), то и HMAC-подпись небезопасна. Для CRC же поиск такого поддельного текста тривиален.


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

                                                0

                                                Спасибо, теперь понятно

                                    0
                                    RIPEMD160 той же длины, но проблемами с second preimage attack не страдает.
                                    0
                                    Есть и положительные стороны — можно будет делать свои прошивки для девайсов с обязательной проверкой подписи. Недавно была статья про XBOX — там как раз SHA1.

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

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