Забавляемся с хешами

    Привет. Я хочу показать вам небольшой фокус. Для начала вам потребуется скачать архив с двумя файлами. Оба имеют одинаковый размер и одну и ту же md5 сумму. Проверьте никакого обмана нет. Md5 хеш обоих равен ecea96a6fea9a1744adcc9802ab7590d. Теперь запустите программу good.exe и вы увидите на экране следующее.
    Попробуйте запустить программу evil.exe.
    Что-то пошло не так? Хотите попробовать сами?

    О хешах и колллизиях


    На самом деле ничего нового во всем этом нет. В действительности данный эффект достигается за счет методов быстрого поиска коллизий для хеш функции разработанных еще в 2004-2006 годах. Если кто не знает, коллизия это два разных набора данных, имеющих одно и тоже хеш-значение. Так вот, в 2004 году группа китайских исследователей разработала алгоритм, основанный на дифференциальном криптоанализе, позволяющий за относительно небольшое время находить два различных случайных блока данных, размером по 128 байт каждый, имеющих одну и ту же md5 сумму. И хотя алгоритм этот в свое время произвел эффект взорвавшейся бомбы быстродействие его оставляло желать лучшего. Но уже в 2006 году чешский криптограф Властимил Клима предложил для поиска коллизий новый метод, позволяющий найти разную пару случайных 128 байтных блоков с одной md5 суммой на персональном компьютере меньше чем за минуту.

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

    Схематично это можно представить следующим образом:
    si+1 = f(si, Mi), где si вектор инициализации для i-го блока.
    Метод Властимила Клима позволяет для любого заданного значения si подобрать два 128-байтных блока M,M` и N,N` таких, что f(f(s, M), M') = f(f(s, N), N').

    Таким образом, с помощью данной методики можно сконструировать два файла с одинаковой md5 суммой, но имеющих различные 128 байт в середине.
    M0, M1, ..., Mi-1, Mi, Mi+1, Mi+2, ..., Mn,

    M0, M1, ..., Mi-1, Ni, Ni+1, Mi+2, ..., Mn.
    Обратите внимание что хеши обоих этих файлов совпадут, т.к. различающиеся блоки Mi, Mi+1 и
    Ni, Ni+1 вернут в качестве si+2 одно и тоже значение, т.к. f(f(s, Mi), Mi+1) = f(f(s, Ni), Ni+1), а поскольку все последующие данные идентичны то последующие значения функции сжатия для обоих файлов будут совпадать.

    Что это нам дает


    Теперь перейдем от вещей абстрактных и отдаленных к вопросу практическому. Предположим, что у нас есть исполняемый файл M0, M1, X, X, …, Mn. Но его основе мы можем создать два разных файла M0, M1, N1, N1, …, Mn и M0, M1, N2, N1,…, Mn(просто меняем блоки X на N1 и N2). Если блоки N1 и N2 – это коллизии то хеш-сумма этих файлов будет совпадать.
    Теперь представим, что этот исполняемый файл имеет следующую структуру:
    if (X == X) then { good_program } else { evil_program }
    Вот собственно и весь секрет данного фокуса.

    Как сделать самостоятельно


    Теперь немного поговорим о том как это сделать самому.
    Шаг первый: пишем программу с двойным дном.
    #include <stdafx.h> 
    #include<iostream>
    #include <string>
    using namespace std;
    //переменные str1 и str2 в данном примере являются теми самыми элементами X.
    static char *str1="qwertyuioplkjhgfdaszxcvbnmkjhgfdsaqwertyuikjh"\
    "gbvfdsazxdcvgbhnjikmjhbgfvcdsazxdcfrewqikolkjnhgfqwertyuioplkjh"\
    "gfdaszxcvbnmkjhgfdsaqwertyuikjhgbvfdsazxdcvgbhnjikmjhbgfvcdsa"\
    "zxdcfrewqikolkjnhgfq123"
    ;
    static char *str2="qaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuy"\
    "gtfdeswaqscfvgyjqaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuyg"\
    "tfdeswaqscfvgyjqaswderftgyhujikolpmnbvcxzasxdcfvgbhnjmkijuygt"\
    "fdeswaqscfvgyjqwertyuikja2"
    ;

    int good()
    {
      int a;
      std::cout<<"Good, nice programme!";
      std::cin>>a;
      return 0;
    }
    int bed()
    {
      int a;
      for(int i=0; i<1000; i++)
      {
      std::cout<<"Evil, evil code!";
      }
      std::cin>>a;
      return 0;
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    //строки s и s2 содержат только блоки с коллизиями без лишних элементов
      string s=str1;  
      string s2=str2;    
      s.erase(0,56);
      s.erase(128,8);
      s2.erase(0,64);
       if (s==s2) {
      return good();
     } else {
      return bed();
     }
      return 0;
    }

    * This source code was highlighted with Source Code Highlighter.


    Особое внимание прошу обратить на переменные str1 и str2. Они служат для того, чтобы их можно было быстро найти в hex-редакторе и заменить нужными данными.
    Функция main в зависимости от содержимого переменных s вызывает хорошую или плохую версию программы.

    Шаг второй: После компиляции программы нужно будет немного поработать с hex-редактором для того чтобы найти в .exe файле наши строки str1 и str2. Скопируй полученный .exe файл. Пусть копия будет называется «обрезанная версия». Откройте копию в hex-редакторе и найди в ней строки str1 и str2. Удалите все данные идущие после первых 64 байт первой из строк. Последние строки полученного файла будут выглядеть вот таким образом: . Сохраните данный файл.

    Шаг третий: Созданный на втором шаге файл будет служить так называемым префиксом для поиска коллизий. Чтобы найти коллизию с заданным префиксом нужно скачать отсюда программу fastcoll(Спасибо ее автору Marc Stevens). Исходники лежат тут.
    Запустите программу с параметром –p. В качестве префикса укажите «обрезанную версию». В результате работы программы будут созданы два файла «обрезанная версия_msg1» и «обрезанная версия_msg2».

    Шаг четвертый: создайте еще одну копию вашей программы. Пусть оригинал будет называться good.exe, а копия evil.exe. Откройте файлы msg1 и msg2 в hex редакторе. Сперва замените блок в котором хранится str2 данными из блока str1. Пусть теперь в них будет одинаковая информация. После этого скопируйте из файла msg1 последние 128 байт и вставьте их в ваш good файл так как показано на рисунке.

    Обратите внимание, отступы должны соответствовать следующим параметрам: первый блок вставляется прямо в том месте где заканчивается файл «обрезанная версия», второй блок располагается в 96 байтах от первого. Важно: блоки вставлять одни и те же. Это будет доброй версией нашей программы. Сохраняем файл good.exe и открываем файл evil.exe. Блоки в файл evil.exe нужно будет вставить в те же места, что и в good.exe, единственное отличие заключается в том, что первый блок мы берем из файла msg2, а второй из файла msg1. Это различие и обеспечит нам невыполнение условия программы if (s==s2) и соответственно запустит злую версию программы.

    Шаг пятый: Profit! Сравниваем md5 суммы файлов, наслаждаемся полученным результатом.

    Список литературы:
    1. Замечательный сайт с описанием данного метода
    2. Сайт Властимила Клима
    3. Сайт автора программы findcoll
    Поделиться публикацией

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

      +1
      вместо programme обычно пишут program, если это на английском написано
        +20
        bed -> bad
          –1
          ха ха — точно
            +12
            да да — мне тоже эта кроватная функция понравилась =)
              +6
              Да у автора и с русским не очень:

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

              Да, я понял, он всего лишь торопился.
                –49
                Как эти Розентали уже достали. Ну что вам не имется?
                  +1
                  Хабр — не администрация N-ской области
                  habrahabr.ru/info/help/rules/
                    –8
                    Сынок родной, увидел ошибку — напиши в личку, не надо исполнять на главной, ценность таких коментов равна нулю.
                      +9
                      Я Вам не сынок.
                      Про ценность — Как и ценность комментов про Розенталей.
                      Про личку — я и не писал про ошибку. Я лишь указал на правила хабра в ответ на Ваш бесценный коммент
                        –52
                        заплачь еще
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • НЛО прилетело и опубликовало эту надпись здесь
                              +4
                              Вы, видимо, в свое время эти самые уроки не посещали… А жаль=\
                              • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Это правильно, значит тема актуальна. И потерянная карма того стоит. Я все написал верно: я люблю своя язык, но увидел ошибку — напиши в личку, это не блог русского языка
                                +10
                                я люблю своя язык


                                Моя твоя не понимай…

                                Орда детектед :)
                                  0
                                  >Я все написал верно: я люблю своя язык...

                                  Нет, вы написали это неверно. Верно будет «я люблю своя языка».
                            –1
                            Родной, ты запятую забыл.
                              0
                              таки нет, если «сынок родной» ~ «родной сынок» — одно обращение. «сынок, родной, ...» — два обращения
                          +16
                          Запомните, что «не имется» пишется как «неймется», и они начнут доставать вас меньше.
                            –46
                            Нет ты посмотри, еще один Розенталь. У вас сообщество?
                              +13
                              Ага. Международное. Даже лозунг есть: «Grammatik macht frei!»
                                –1
                                Лучше уж — Grammatisch. Praktisch. Gut! )
                                +24
                                Да, у нас тут сообщество носителей русского языка.
                                +4
                                >Запомните, что «не имется» пишется как «неймется»

                                Точкофилы протестуют! Это слово пишется как «неймётся»!
                            +10
                            Ха, вот не зря сомневался.:)
                            А вообще конечно я прошу прощения за ошибки. Код и заметка писались глубокой ночью, мозг отказывался реагировать на какие-либо раздражители.
                              +8
                              мозг хотел в bed :)
                                +3
                                оффтопик::хозяйке_на_заметку {
                                    отбивайте в коде операторы(=, ==, >> и т.д.) пробелами с обоих сторон
                                    отбивайте запятую пробелом справа (s2.erase(0, 64);)
                                    для склейки строк обратный слеш не нужен
                                }
                                
                              –1
                              Да какая блин разница…
                                +23
                                впрынцэпе ныкакой
                                  –4
                                  Такъ что же вам не нравитъся? =)
                                    +1
                                    мне кажется писать programme не правильно
                                      +15
                                      American English always uses program
                                      British English uses programme unless referring to computers
                                      Australian English recommends program for official usage, but programme is still in common use

                                      www.dailywritingtips.com/get-with-the-programme/
                                        +2
                                        А в IT, в свою очередь, в подавляющем большинстве случаев используется именно American English.
                                          +6
                                          Та ну какая разница, ну нравится человеку так писать, а вы тут тред развели на два экрана. Топик, как вы могли заметить, вообще не об этом.
                                            0
                                            Смотря кто пишет. Читал тут доку по RFB протоколу и удивлялся слову colour при том, что одно из слов на обложке про авторов — AT&T Labs. Сейчас только что поискал местонахождение компании _текущего_ автора этой доки, таки да, теперь UK. И цвета он аккуратно поправил :).
                                          +5
                                          правильно писать «аппликация»
                                            –1
                                            Мицгол? :)
                                              0
                                              Это аналогично с «резолюция»? :)
                                          0
                                          Я имел ввиду, какая разница что выводит программа? Некоторым обязательно надо что-то написать в топик, не важно что…
                                          +8
                                          en.wiktionary.org/wiki/programme
                                          UK: programme is used in all cases except for computer code, in which case program is generally used. Older sources may use programme for computer code.

                                          т.е. даже в британском английском это уже не применяется.
                                            0
                                            Оксфордский словарь: www.oxforddictionaries.com/view/entry/m_en_gb0665170;jsessionid=09EEB470BCE659BEE99758B7AAC1E7FC#m_en_gb0665170

                                            4 (program)a series of coded software instructions to control the operation of a computer or other machine.
                                              +5
                                              Я думаю то что ваша ссылка подтверждает мою точку зрения.

                                              Spelling help
                                              Remember that programme ends with — amme, unless it is used in computing senses, when program is correct. In American English, it is always spelled program.
                                                0
                                                Похоже на то, спасибо. Поставлю вам плюс в благодарность.
                                                  0
                                                  спасибо
                                          +2
                                          Походу, немецкий.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            +13
                                            Отличная статья, читал с интересом.
                                              +5
                                              «Ловкость рук и никакого мошенничества!»

                                              Спасибо, с удовольствием прочитал статью.
                                                –3
                                                Охренеть.
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                    +5
                                                    Эх, тоже самое бы, но на примере действительно Evil кода)))
                                                      +8
                                                      А ещё такие программы можно написать например проверяя название исполняемого файла самой себя же.
                                                      И да, спасибо за интересную статью.
                                                        +5
                                                        Таким образом открывается простор для злоупотреблений на сервисах хранения файлов, т.к. там они считаются идентичными при равном размере и одинаковом хэше.

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

                                                        Интересно, какие теперь можно использовать способы для проверки идентичности файлов? Высчитывать хэш рандомного куска файла небольшого размера, и сверять его с таким же куском другого?..
                                                          0
                                                          Вроде уже писали что «правообладатели» так поступают с торрентами.
                                                            0
                                                            Нет не поступают! В торрентах для идентификации используется SHA1 для которого такую атаку еще не реализовали.

                                                            Поверьте, если бы она была реализована, то каждый фильм который бы вы скачивали с торрентов, был бы битый и не проигрывался бы.
                                                            0
                                                            Хеши вообще нельзя использовать для проверки идентичности файлов. И никогда нельзя было.

                                                            Если хеши разные, то файлы разные, если одинаковые, то это ни о чём не говорит.
                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                –1
                                                                Это какой-то аргумент что ли? Мало ли где это используется. Нельзя так делать.
                                                                  0
                                                                  У нас в компании при хранении файлов используется хэш+размер файла для их идентичности — чтоб 1 файл 50000 раз не копировать каждому пользователю, физически в единственном виде (не считая бэкапов) существует. Правда, у нас наверное хэш более умный :)
                                                                    0
                                                                    Это сильно ситуацию не влияет :)
                                                                  0
                                                                  Зато как будет обидно, если коллизия всё же произойдёт? И заметят это совсем не сразу. И вообще, хрен поймёшь, что произошло.
                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                  +1
                                                                  Говорит. Вот ровно о том и говорит, что файлы НЕ [точно не идентичны]. Мало того, все-таки говорит, что идентичны, но с точностью до почти наверное (в строгом смысле этого выражения). Наличие одновременно двух хэшей логически ничего не меняет, но существенно уменьшает вероятность строгой неидентичности.

                                                                  Это, возможно, уязвимо (существование строго необратимых хэш-функций, несколько я понимаю, не доказано), но в значительном числе случаев «достаточно» для бытового использования. Вы же, обещая приехать в гости, не говорите «если только мне по дороге не упадет на голову кирпич, рояль, топор, сундук и далее еще бесконечное множество предметов». Но из этого вовсе не следует, что вам нельзя верить.
                                                                    +1
                                                                    Вы какую-то странную вещь говорите. Какая ещё бытовое использование? Что это? Хешем хлеб резать?

                                                                    Представьте, что операция сравнения в Си выдавала бы полную чушь один раз на десять миллионов? Это «бытовой точности» нам хватило бы, чтобы программировать в Си?

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

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

                                                                    И что мне делать, с вашим «бытовым использованием»? Рассказывать заказчику о хешах? Да он меня мудаком назовёт и будет прав.
                                                                      +4
                                                                      >Вы какую-то странную вещь говорите. Какая ещё бытовое использование? Что это?

                                                                      Скачиваем файл. Считаем md5 и sha. Сравниваем с опубликованными. Если совпадает, значит перескачитвать не нужно (почти наверное). Если не совпадает — нужно точно перескачать. Это и есть бытовое использование.

                                                                      Ровно то же самое происходит в голове у вашего контрагента, когда вы обещаете ему приехать в гости.

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

                                                                      Любопытно, и сколько же?
                                                                        –5
                                                                        Ох. Такое ощущение, что вы либо совсем не в теме, либо троллите. Я не хочу продолжать диалог.
                                                                          0
                                                                          Ну, хамить — дело несложное. А в чем мои рассуждения неверны, я так и не понял.

                                                                          Смысл хеша ровно в том, чтобы относительно быстро, дешево и сердито дать ответ с точностью до почти наверное.

                                                                          Ваш пример с хостингом — я также не понимаю, чем вам там хэши мешают. Ну даже совпали они (скажем, оба: и md5, и sha1, и при этом размер у файлов одинаковый) — и чего, жизнь кончилась? Взяли, посчитали для сегмента случайной длины со случайным смещением. Опять совпали? — и еще раз совпали? — «ну тогда я не знаю» © — дальше, если в этом есть коммерческий (или какой там) смысл, побайтное сравнение или что там вам больше нравится.

                                                                          Вы знаете способ эффективнее? Расскажите, я буду благодарен.
                                                                        +1
                                                                        Давайте посчитаем, сколько коллизий будет (независимо от размера файлов), удивитесь.

                                                                        Общая мощность пространства значений пары хэшей md5+sha1: 288 бит, а значит есть 2^288 возможных значений (на самом деле меньше за счёт неидеальности хэш-функций, но пока пропустим этот момент)
                                                                        Допустим у вас на хостинге 2^32 файлов (миллиард).
                                                                        Вероятность того, что случайно произойдёт хоть одна коллизия примерно 2^288 / 2^64 = 2^224
                                                                        Это 3.7*10^(-68)

                                                                        Оценка весьма грубая, но всё же.
                                                                          0
                                                                          > Общая мощность пространства значений пары хэшей md5+sha1: 288 бит, а значит есть 2^288 возможных значений (на самом деле меньше за счёт неидеальности хэш-функций, но пока пропустим этот момент)
                                                                          Во-первых, я не понял почему мы опускаем этот момент. Как относятся распределяются значения md5 + sha1 на одном и том же файле мы не знаем. Они могут давать значения куда у́же, чем 288 бит.

                                                                          Во-вторых, я не понял почему мы игнорируем длину файла. Я специально привёл в пример видеохостинг, то есть файлы примерно от 800МБ до 4ГБ. Можно ещё ухудшить ситуацию, если взять видеохостинг каких-то определёных рипов, нампример, только HDRip.
                                                                            +1
                                                                            > Как относятся распределяются значения md5 + sha1 на одном и том же файле мы не знаем. Они могут давать значения куда у́же, чем 288 бит.
                                                                            Да, действительно пространство значений меньше чем 288 бит. Мне кажется, что не намного, но аргументировать не смогу — глубоко не копал.
                                                                            Другой аргумент в их пользу: до сих пор не было найдено (сгенерировано) ни одной пары документов с одновременно совпадающими md5 и sha1. (При чём сгенерировать пару проще, чем получить коллизию случайно)

                                                                            А длина файла? Разве она вообще как-то влияет на шанс коллизии? Мне кажется тут имеет значение только количество файлов, но не их размер.
                                                                              0
                                                                              > Да, действительно пространство значений меньше чем 288 бит. Мне кажется, что не намного, но аргументировать не смогу — глубоко не копал.

                                                                              Меня, как математика сильно смущает, что в нашем споре куча переменных, влияющих на порядок вычислений. А ещё — куча зрителей, ничего в этом не понимающих.

                                                                              > А длина файла? Разве она вообще как-то влияет на шанс коллизии? Мне кажется тут имеет значение только количество файлов, но не их размер.

                                                                              Ну, например, какой может быть шанс коллизии на файле в один байт?
                                                                                +1
                                                                                > Меня, как математика сильно смущает, что в нашем споре куча переменных, влияющих на порядок вычислений. А ещё — куча зрителей, ничего в этом не понимающих.

                                                                                Переменных да, много. Но в том-то и штука, что несмотря на то, что хэш вещь непредсказуемая, и его значение нетривиальным образом зависит от хэшируемых данных — основные его свойства сохраняются. А основные свойства — это как раз то, что хотя коллизии и возможны, но их вероятность (даже в случае злонамеренного поиска) настолько мала, что в реальном мире (тем более если взять два хэш-алгоритма, чтобы предостеречься от взлома какого-то одного) можно считать что коллизий нет. Об этом salium вам выше и пытался сказать.
                                                                                А зрители — ну неужели прекращать поиски истины из-за них?)

                                                                                > Ну, например, какой может быть шанс коллизии на файле в один байт?
                                                                                Напомню, коллизия — это равенство значений хеш-функции на двух различных файлах.
                                                                                То есть «на файле» о коллизии речи быть не может.

                                                                                > Можно ещё ухудшить ситуацию, если взять видеохостинг каких-то определёных рипов, нампример, только HDRip
                                                                                Формат видео-то тут причём? Разве что заголовки будут немного совпадать, но хэши двух разных HDRip фильмов не будут иметь ничего общего, тем более что есть лавинный эффект.
                                                                              0
                                                                              Просветите же нас, как влияет длина файла на хеш этого файла?
                                                                                –1
                                                                                О, сарказм невежды!
                                                                                  0
                                                                                  Так просветите, действительно интересно )
                                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                                    0
                                                                                    Ну наверное имелся ввиду не хеш файла а «хешики» кусков или точнее будет даже «кусочков файла».

                                                                                    Конечно то что в файле есть коллизии не значит что полный хеш будет идентичен с другим файлом в котором так же есть коллизии. Ой как не значит :)
                                                                                0
                                                                                Это все конечно очень правильно, но хотелось бы услышать ваш метод для проверки идентичности видеофайлов.
                                                                                  0
                                                                                  О! Вы меня нанимаете? :)
                                                                                    +1
                                                                                    О! Вы просто болтаете? :)
                                                                                      –1
                                                                                      Нет, просто потерял интерес к теме.

                                                                                      Вообще, в который раз ругаю себя за то, что ввязался в дискуссию. В этой теме у меня, конечно, есть пара воспитанных собеседников. Но, в основном, после каждого раза, чувствуешь себя как говном облитый. И, самое противное, хочется пойти в комментарии и тоже облить кого-нибудь говном.
                                                                            +2
                                                                            >Интересно, какие теперь можно использовать способы для проверки идентичности файлов?
                                                                            SHA-1, например. в приведенных в статье примерах совпадает только MD5, a CRC32 и SHA-1 отличаются.
                                                                              0
                                                                              Я сталкивался с ситуацией, когда crc32 выдавал одинаковый хэш. Не с файлами, но всё же.
                                                                                +3
                                                                                CRC32 никогда не был криптографически стоек, для получения необходимого хеша нужно изменить значения всего лишь 4 байтов, значения которых вычисляются за то же время, что и хеш (т.е. линейное).
                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                  +8
                                                                                  Поэтому нужно сравнивать сразу несколько хешей, SHA-1 и MD5, например. Подобрать данные, дающие коллизию по нескольким разным алгоритмам, на несколько порядков сложнее.
                                                                                    0
                                                                                    Так делается в FreeBSD с ее портами, пример

                                                                                    [/usr/ports/security/sudo] cat distinfo
                                                                                    SHA256 (sudo-1.7.4p6.tar.gz) = 20091ef71018698c674c779f4b57178b2ecb4275fa34909b06219d2688ad14d5
                                                                                    SIZE (sudo-1.7.4p6.tar.gz) = 966234
                                                                                      +3
                                                                                      Эээ, прошу прощения, так делалось раньше, сейчас исключили походу MD5, а я не посмотрел — в тупую скопипастил код
                                                                                      www.freebsd.org/cgi/query-pr.cgi?pr=149657
                                                                                  +4
                                                                                  к счастью свет не сошелся клином на md5
                                                                                  Есть sha1, sha256,…
                                                                                    0
                                                                                    Есть Whirpool еще, по которому я так и не увидел ни одной годной статьи на Хабре. Если кто сможет дать линки — буду благодарен.
                                                                                    +5
                                                                                    К примеру, антивирусные лаборатории, которые работают с миллионами самплов, для их достоверной идентификации обычно используют связку хэшей, которые были взяты несколькими различными алгоритмами.
                                                                                      +5
                                                                                      Не забывайте, что тут можно найти пару блоков, для которых будет коллизия.

                                                                                      То есть если уже есть «хороший» файл, то создать «плохой» файл с тем же хэшем гораздо сложнее.

                                                                                      Атака дней рождения же.
                                                                                        +2
                                                                                        Для этого используют несколько разных хэш-функций одновременно.
                                                                                        –2
                                                                                        А ведь хеш-функции активно применяются и в сетевых технлогиях для аутентификации сторон при всяческих PPP, например.

                                                                                        Задумался… Большое спасибо за статью!
                                                                                          0
                                                                                          Openvpn по умолчанию использует TLS и SHA1.
                                                                                            0
                                                                                            Не, я имел в виду именно PPP. Там два вида аутентификации: PAP, который почти не используется, и CHAP. CHAP использует MD5.
                                                                                              0
                                                                                              А как же 128-битный MSCHAPv2?
                                                                                                0
                                                                                                Он не всеми железками подджерживается.
                                                                                          +1
                                                                                          В вашей статье не хватает вывода, ответа на вопрос: «Так что теперь делать?»
                                                                                            0
                                                                                            Использовать MD6 или SHA1
                                                                                              0
                                                                                              И виной тому служит следующая особенность работы любой хеш функции: Хеш функция по своей природе итеративна.

                                                                                              Они точно не обладают теми же недостатками, но с другими условиями ?; )
                                                                                                +2
                                                                                                И для них нужно изобретать свой алгоритм поиска коллизий. А MD6 ещё и сильно сложнее пятой версии.
                                                                                            +1
                                                                                            Спасибо, весьма познавательно. К счастью (или нет?), на практике подобные атаки мало где применимы, поскольку для построения важных/критических криптосистем в качестве хэш-функций рекомендуют использовать нечто более стойкое, нежели MD5. Это связанно не столько с объективными недостатками данного алгоритма как такового, но и с тем, что в силу высокой популярности к нему сильнее всего приковано внимание исследователей.
                                                                                            Например: SHA1 используется в большинстве SSL сертификатов и механизмах цифровой подписи исполняемых файлов в ОС Windows.
                                                                                              +4
                                                                                              А теперь то же самое, но проще: проверяем имя исполняемого файла и простым условием:
                                                                                              — если good.exe -> вывод good, если evil.exe -> вывод 'bad code'. Хэш ведь считается без учета имени файла :)
                                                                                                0
                                                                                                ну то есть вы всерьёз считаете, что человек, сумевший так хорошо замаскировать свой зловред под нечто безобидное — не догадается и название файла выставить идентичное?
                                                                                                  +4
                                                                                                  Речь не о маскировке зловреда, а о том, что в данном примере программа могла проверять argv[0] и выводить разные сообщения от имени файла.

                                                                                                  При этом md5, sha1, crc, да и вообще файлы побитово совпадали, а результат при запуске разный.

                                                                                                  Это совсем по теме статьи, но забавная идея.
                                                                                                    0
                                                                                                    Был бы хороший хабраприкол. Сколько было бы негодования в комментах, пока кто-нибудь не догадался бы переименовать.
                                                                                                      +4
                                                                                                      Эта забавная идея давно и успешно, и, главное, с пользой для дела, используется в униксах. Где может быть один бинарник (или скрипт) и кучка разных симлинков на него. В зависимости от имени единственный бинарник выполняет разные операции (из схожей серии).
                                                                                                      А, во, простейший пример:
                                                                                                      lrwxrwxrwx 1 root root 5 Дек 4 02:05 bunzip2 -> bzip2
                                                                                                      lrwxrwxrwx 1 root root 5 Дек 4 02:05 bzcat -> bzip2
                                                                                                      -rwxr-xr-x 1 root root 35224 Дек 4 02:05 bzip2
                                                                                                  +2
                                                                                                  Стоит добавить ссылку на эту статью: habrahabr.ru/blogs/infosecurity/50434/
                                                                                                    0
                                                                                                    А как это будет работать на реальный примерах с размером кода хотя бы на порядок больше?
                                                                                                    Кстати, заподозрить неладное можно уже при открытии архива:


                                                                                                    что в принципе неудивительно — код-то разный.

                                                                                                    Ну и кроме того, как правильно сказали — есть другие хеши:
                                                                                                    evil.exe:
                                                                                                    CRC32: B5917900
                                                                                                    MD5: ECEA96A6FEA9A1744ADCC9802AB7590D
                                                                                                    SHA-1: BE3AEE5D2A99BC88233E331A653D14CA3EB722F8

                                                                                                    good.exe:
                                                                                                    CRC32: A71D16A9
                                                                                                    MD5: ECEA96A6FEA9A1744ADCC9802AB7590D
                                                                                                    SHA-1: BE1DF26F1245278611739F49F610DCFF677FBEC2

                                                                                                      0
                                                                                                      Хе-хе, а есть еще такая же штука, но для crc32, только она много проще. Я когда программы правил, и у них сверка контрольных сумм шла, а мне было лень ее искать, я брал и правил crc32. Там нужно править было всего 4 байта.
                                                                                                      –2
                                                                                                      if(argv[0] == 'evil.exe') (be evil); ne?
                                                                                                        0
                                                                                                        s/argv[0] == 'evil.exe'/strcmp(argv[0], «evil.exe») == 0/, я, увидя заметку в RSS, сначала подумал об этом же :)
                                                                                                      +3
                                                                                                      Evil evil код запихан в кровать… )
                                                                                                        +1
                                                                                                        Немного не в тему: а нет рекомендаций каких-нибудь в виде «поменяй пару байтиков и получится 'красивая' контрольная сумма»? Просто интересно, такое еще не придумывали?
                                                                                                          0
                                                                                                          Навряд ли, то о чем вы говорите это скорее похоже на нахождение прообраза для заданного хеша. А такая задача на сегодняшний день пока решается только методом грубой силой.
                                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                            +2
                                                                                                            Почему не «gud»? :)
                                                                                                              +1
                                                                                                              Ха, не знаю, наверное, просто еще все не настолько плохо:)

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

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