«Сложный пароль» в расшифровке не нуждается

    Проскочил тут топик про «сложные» пароли. К сожалению, смотрю, многие серьезно восприняли этот «метод»…

    Использование карточек шифрования не является надежным методом! Как правильно заметили в комментариях там — «это в войну наши деды использовали»… Но использовали более совершенные методы.

    Приведенный в той статье метод использовать НЕЛЬЗЯ ни в коем случае(!), пароли по этому методу полностью расшифровываемые, Вы просто отдадите их злоумышленникам на блюдечке! И сейчас я это докажу…

    Сложность и параметры

    Всего существовать по такому методу может 36 таблиц, что по сложности равно паролю из одной буквы или цифры. Отличия таблиц только в одном параметре: смещение влево на [0-35] — число столбцов, равное промежутку «a-z0-9».

    Можете проверить: таблица один — это z = (i+j-1) % 36, вторая — это z=(i+j+9) % 36, где i и j принимают значения: «a»=0, «b»=1, «c»=2,… Проверьте для любых остальных значений — отличие только в одной константе, даже несмотря на то, что по строке вторая таблица начинается с «s» (что вообще с т.з. математики не имело смысла).

    первая:
    a + b + -1 = a  (0 + 1 + -1 = 0)
    a + c + -1 = b  (0 + 2 + -1 = 1)
    b + a + -1 = a  (1 + 0 + -1 = 0)
    
    вторая:
    
    a + j + 9 = s  (0 + 9 + 9 = 18)
    a + k + 9 = t  (0 + 10 + 9 = 19)
    b + i + 9 = s  (1 + 8 + 9 = 18)
    
     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
     a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r
    
    18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
     s  t  u  v  w  x  y  z  0  1  2  3  4  5  6  7  8  9


    Следовательно, зная зашифрованный пароль и название ресурса — у нас остается всего 36 исходных паролей.

    Финальный пример из оригинального текста (про него и ниже):



    Кстати, вот сразу и минус виден — пользоваться табличками людям сложно, ошибки — неизбежны. Это зашифрованный автором той статьи пароль. В нем ошибка — «a-a» на второй позиции — это «9» по первой табличке, а не «b».

    Расшифровываем (правильно) зашифрованный пароль…
    вот часть из 36 паролей (соответствующие 36 разным смещениям таблицы и названию — «habrahabr»):
    +5 j4mmqil7j
    +4 k5nnrjm8k
    +3 l6ooskn9l
    +2 m7pptloam
    +1 n8qqumpbn
    +0 o9rrvnqco
    -1 passwordp
    -2 qbttxpseq
    -3 rcuuyqtfr
    -4 sdvvzrugs
    -5 teww0svht
    -1 — это и есть искомая константа смещения таблицы.

    Да, это реальная «расшифровка», да, программу написал… на конце «p» потому что повтор пароля начинается.

    Заметьте, что нам нужна только одна буква из пароля и та же одна — из названия сайта для получения одной переменной (смещения).

    Маленькие буквы в «зашифрованном» пароле сдадут какие буквы будут являться гласными в названии сайта (снижение криптостойкости).

    Так вот из вышесказанного, если мы не знаем названия сайта, но знаем где там гласная (а она будет там, где в зашифрованном пароле маленькие буквы), то у нас получается (по одной любой букве) = 36 (табличек) * 6 (гласных = a,e,i,o,u,y) — 216 паролей (не зная названия сайта!). Совсем немного, но в реальности см. ниже ("В реальности") — будет скорее всего только один.

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

    Добивка несколько усложняет задачу, но не в приведенном примере. Поскольку название ресурса длиннее, чем пароль, то получается расшифровав короткий пароль (зная зашифрованный пароль и название ресурса), который пойдет дальше по циклу — мы восстановим легко и добивку (мы будем знать верхнюю строку и нижнюю строку — среднюю мы восстановим по той же таблице… тут, кроме пары «символов» на позициях 4,8,16 (решетки, собачки), о ней — ниже).

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

    В реальности: Из 36 паролей наверняка только один будет выглядеть как слово(!), которое вы запоминали, так что в реальности даже перебора не потребуется. Так что пароль будет известен точно.

    Замена на символы


    Отступление про «символы». Автор предложил заменять буквы полученного пароля на позициях 4,8,16 — на символы по табличке.

    Знаки препинания добавляли бы сложности, если бы не еще одна уязвимость метода — цикличность повторения пароля. Автор сдвинул знаки препинания относительно латиницы. Ну что ж — это плюс, да, это еще один параметр сложности, но учитывая что мы точно знаем что меняются 4,8 и 16 символы — то мы можем (по длине названия сайта «habrahabr») расшифровать слово «pas*wor*p» в первой табличке (что под "*" мы не знаем пока что).

    Теперь хитрость в том, что на (4+8) = 12 позиции та же буква, что и на «4» (пароль-то по кругу идет — это обе буквы «s» в слове «pass(4)wordpass(12)word»), но на 12 месте пунктуация не использовалась!

    Следовательно мы можем расшифровать 12 букву и тут же узнаем 4ую букву.

    Зная 4 зашифрованную букву и соответвующую ей пунктуацию — мы линейно получили смещение пунктуации. Из этого смещения тут же узнаем 8ую букву и как бонус — 16ую (которая та же). FAIL!

    Правда если бы автор зашифровал 12ую букву, а пароль был бы 7-значным — мы бы все равно ее расшифровали (повторение буквы было бы на 4+7=13ом месте).

    Если будет «добивка» — это будет портить картину, но не сильно, опять же — большая часть добивки будет расшифрована (мы уже будем знать полностью или почти полностью верхнюю строку и полностью — нижнюю — из нее восстановится средняя, кроме возможно(!) 1-2 букв закрытых пунктуацией, но тут уже перебор спасет — еще *36 вариантов — немного (и это редкий будет случай, чтобы удачно пунктуация закрыла буквы, что их не восстановить из повторяющегося пароля).

    Вариант еще хуже


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

    Грубо говоря как система уравнений

    x + Y1 + t = Z1,
    x + Y2 + t = Z2,

    где x = исходный пароль,
    Y1,Y2 = название ресурсов (известно),
    t — смещение таблицы,
    Z1,Z2 = зашифрованный пароль(известно).

    Два уравнения, две неизвестных — система линейна и имеет одно решение относительно x и t.

    На самом деле достаточно одной буквы из обоих паролей и той же буквы названий сайтов. (Неизвестная-то величина только одна — смещение таблицы влево)

    Здесь даже перебирать ничего не надо — пароль будет известен точно.

    Вывод


    Приведенный в оригинальной статье алгоритм шифрования аналогичен буквенно-цифровому паролю из 1(одного!) символа (log3636 = 1).

    В случае если известны шифрованные пароли от двух сайтов — не является шифрованием вообще.

    Можно ли усложнить


    Даже если Вы усилите алгоритм тем, что будете использовать русские буквы и символы (которые смещаются независимо), даже если Вы добавите сдвиг таблицы не только по горизонтали, но и по вертикали, и даже отражения по горизонтали и вертикали, то получите: 36*36*36*36*36*2*2 = 240 млн таблиц… Выглядит страшно?

    На самом деле это аналогично простому буквенно-цифровому паролю примерно из 5 букв. Что едва ли можно считать «надежным» или «сложным» (27 бит шифрования).

    Сильное шифрование — это 128 бит, что примерно в 1400000000000000000000000000000 раз должно иметь больше вариантов, чем «усложненные» 240 млн. (точно?) Это эквивалентно буквенно-цифровому паролю из 25 букв. (log36(2128) = 24.75)

    Единственный способ, которым можно это действительно «усилить» — это если:

    1) Табличка будет во-первых «вывернута» (сейчас нужно по вертикали, а потом по этой строке пальцем идти, а нужно сделать чтобы на пересечении вертикальной и горизонтальной полосы был «зашифрованный» символ) — это уменьшит повторяемость и предсказуемость, которая сейчас на максимуме,
    2) Строки и столбцы надо растянуть, чтобы не было соответствия латинского-русского-символа, все отделить друг от друга — это еще уменьшит повторяемость и предсказуемость,,
    3) Табличка будет содержать только абсолютно случайные числа-цифры-символы в теле — и я имею в виду абсолютно случайные в каждой ячейке — никаких сдвигов по рядам,
    4) Никаких повторов (пароля, названия сайта),
    5) Никаких «позиционных» замен.

    Однако, даже эта табличка не выдержит серьезной атаки при длительном использовании (как и все «таблички»). Еще раз: использование карточек шифрования не является надежным методом шифрования!

    md5('site+key')


    Многие посоветовали такой метод. Он неплохой, но его можно улучшить.

    На самом деле, при наличии достаточных мощностей и объемов памяти для RainbowTables есть шанс, что найдется ключик. (ма-а-а-а-а-а-а-аленький, но есть — всего 103 миллиарда паролей в секунду может один компьютер перебирать — так что, например, «password»+«habr» за 10 дней расшифровать можно и на домашнем компе)

    Лучше — делать раунды шифрования, проще говоря — возьмите site+key и зашифруйте его 6000 раз прямо вот md5(md5(md5(… так 6000 раз......md5('site+key')....). Это не остановит атакующего, но серьезно замедлит, настолько чтобы атака стала непрактичной. Почитайте (на английском) что KeePass про раунды пишет — очень объяснит почему я так говорю.

    # Псевдокод:
    k = key + site
    for 0..6000 {
       k = md5(k)
    }
    print k

    А это уже расшифровывать 150 лет, против 10 дней для обычного md5(site+key). Но даже один раз — это довольно хороший метод.

    Завершение


    Вот так даже очень впечатляюще выглядящие алгоритмы оказываются совсем нестойкими.

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

    А лучший способ хранения паролей — это, все же — менеджер паролей, например KeePass и подобные.


    Йои Хаджи,
    вид с Хабра

    Средняя зарплата в IT

    120 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 7 122 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

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

      +102
      Сразу видна разница между дилетантом и профи. У одного — таблички, разнономастно-вырвиглазные соцветия и «инновационный» метод, у другого — математические выкладки и достаточные для этого познания в криптоаналитике.

      Браво.
      • НЛО прилетело и опубликовало эту надпись здесь
          +1
          "Cjhjr nsczx j,tpmzy d ;jge ceyekb ,fyfy" :)

          Автор не учитывает что для расшифровки могут использоваться собственноручно изготовленные карточки, при отсутствии физического доступа к которым у злоумышленника нет шансов подобрать пароль.
          • НЛО прилетело и опубликовало эту надпись здесь
            0
            Видел на Хабре предложение использовать русский трёхэтажный мат в английской раскладке в качестве паролей.
            Такой-то хабр.
            Разтакой-то яндекс.
            Да утробой вам в гугл.
            Мы очень любим в контакте.
            • НЛО прилетело и опубликовало эту надпись здесь
                +2
                Ога, а у Лукяненко было про банан и обезьян
            –3
            x + Y1 + t = Z1,
            x + Y2 + t = Z2,

            где x = исходный пароль,
            Y1,Y2 = название ресурсов (известно),
            t — смещение таблицы,
            Z1,Z2 = зашифрованный пароль(известно).

            Два уравнения, две неизвестных — система линейна и имеет одно решение относительно x и t.

            Интересно, как же наш «криптограф» будет решать линейную систему из двух равносильных уравнений (т.е. с нулевым определителем) и получать единственное решение?!

            x + Y1 + t = Z1, x + t = Z1 — Y1,
            x + Y2 + t = Z2, x + t = Z2 — Y2.
              0
              Z1,2 и Y1,2 это не числа, это слова.
              Система приведена просто для наглядности.
                0
                Уважаемый yoihj, а эту табличку можно также просчитать?
                входящие данные: таблица, сайт — хабр, логин — мой.
                  +2
                  вы меня с кем-то путаете ;)
            +25
            Мужииик!
              –12
              Человек просто привёл один из методов. Использование различных систем шифрования с ключом, также как и придумывание своих определённо имеет право на жизнь. Хотя бы потому, что взломщики не всегда смогут понять что используется именно какой-то алгоритм шифрования, а не просто набор символов в непонятной последовательности. То есть грубо говоря не знай вы систему по которой шифровался пароль вы бы расшифровали его с гораздо большими затратами.
              • НЛО прилетело и опубликовало эту надпись здесь
                  +11
                  В криптоанализе как правило принимают за факт то, что взломщик знает, каким алгоритмом зашифрован текст (для оценки сложности взлома)
                    +7
                    «При оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей.»
                    ru.wikipedia.org/wiki/Принцип_Керкгоффса
                    0
                    Вот тебе и таблички с ключевыми фразами. =)
                      0
                      а зачем вообще эти танцы с бубной? почему не использовать сугубо ключи на токенах, пинкод запомнить-то осилите? а то что по токену не авторизируется, можно держать в любом е-валлете. я что-то пропустил почему тут западло валлеты использовать. хабралюдям мозга не хватает на один сложный пароль на валлет? если случайно не спалиться, в течении жизни можно его вообще не менять.
                        –1
                        Вы Параноики, 8 символов за глаза, а карточки, лучше все хранить в зашифрованном виде в программе, с бекапами, и запоминать только нужные пароль, что я и делаю, а пароли к редко посещаемым ресурсам в голове не храню
                        Причем у меня нет совершенно логической памяти, я все запоминаю как картинки.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            +1
                            Хэй, тссс, не палите контору!
                              +1
                              А как вводить пароль с устройства, где нельзя посмотреть, какая английская клавиша соответствует русской? Например, с iPhone?
                                0
                                Купить какое-нибудь замечательное приложение для этой возможности.
                                  0
                                  Сомневаюсь, что такое есть в легальной природе App Store.
                                    0
                                    Тогда носить с собой табличку соответствия раскладок. :) Можно даже в виде картинки прямо на iPhone.
                                  –2
                                  я в итоге запомнил расположение букв ) А потом уже и сами эти пароли, основанные на этом способе, т.е. больше не нуждаюсь в наличии клавиатуры перед глазами.
                                  Но этот метод крайне не надежен, потому я перешел на что-то вроде этого:
                                  echo 'domain.com+secret' | sha512sum | md5sum
                                  a7a33e309da37b9cb01f31d9ff577b6e

                                  о чём я и писал в исходном топике про табличку )
                                    –1
                                    Еще один, накладывающий хэш на хэш…
                                      –4
                                      попробуйте взломать ) Я даже алгоритм скрывать не стану, как многие делают, прямо из этого примера, узнайте мой пароль на habrahabr.ru (я его сейчас сменил на сгенерированный по этому простому примеру):
                                      echo 'habrahabr.ru+key' | sha512sum | md5sum
                                      *****************************

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

                                          Оставьте свою хабрадушу себе, тем более, вы блефуете — не выложили сам хэш. Укажете, ради интереса могу поставить на подбор.

                                          Суть не во взломе вашего аккаунта.

                                          Суть в том, что взломать
                                          echo 'habrahabr.ru+key' | sha512sum,
                                          сложнее чем
                                          echo 'habrahabr.ru+key' | sha512sum | md5sum

                                          И вообще не понятно, почему сильный хэш стоит перед слабым.
                                            –6
                                            вы блефуете — не выложили сам хэш.

                                            Результат работы хеш-функции и есть пароль, разве непонятно? У вас есть алгоритм, есть первая часть исходной фразы, но нет второй. Подберите такой пароль. Если не можете — нечего ворчать.
                                              +2
                                              Вы издеваетесь?
                                              Может вам мой swap на почту выслать?

                                              Логично просить подобрать ваш key, по хешу, и поиметь остальные пароли.

                                              Я ж говорю, блефуете.
                                                –2
                                                я не настолько глуп, чтобы в реальной жизни применять этот алгоритм в чистом виде. После хеширования я выполняю некоторые операции сдвига и перемешивания над результатом. Но даже в чистом виде этот метод гораздо лучше, чем ytrewq или CegthG@hjkm или обсуждаемая табличка.
                                                  +1
                                                  Ну мы с вами сошлись, что табличка — фигня =)
                                                    0
                                                    однозначно! )
                                                    0
                                                    Не обижайтесь, но мне кажтся что вы параноик )))

                                                    2 хэша + сдвиги + перемешивание +… = 1 (хэш+соль)
                                                      –3
                                                      это комплимент, спасибо
                                                0
                                                Суть в том, что взломать
                                                echo 'habrahabr.ru+key' | sha512sum,
                                                сложнее чем
                                                echo 'habrahabr.ru+key' | sha512sum | md5sum

                                                В данном случае под «взломом» понимается узнать key по сгенерированному хешу, или просто подобрать комбинацию, дающею такой же хеш?
                                                  0
                                                  key
                                                    0
                                                    Тогда моих знаний явно недостаточно, чтобы понять, почему это проще.
                                                      0
                                                      Снижение удельной энтропии.
                                                        0
                                                        Извините, не помогло.
                                                        Ушел курить Гугл
                                                          +1
                                                          Советую классическую «Прикладную криптографию» Шнайера и относительно новую «Криптография» А. Саломаа (финн такой).
                                                            0
                                                            Первая книга — шедевр!
                                                            Вторую пойду в книжном искать сегодня. Спасибо за наводку.
                                                              0
                                                              PDFку найти проще, чем книгу.
                                                                0
                                                                Я приверженец чтения с бумажного носителя информации ))
                                                                Но для краткого ознакомления скачаю PDF'ку.
                                                  +3
                                                  самоучки-криптологи спорят о высоких материях. причем тут сильный-слабый хеш? во-первых хеш используется именно как сам пароль. во-вторых допустим мы даже выдернули пароль к некому ресурсу, пусть к хабру и мы знаем что habrahabr.ru+KEY|md5sum = HASH где неизвестное только KEY.

                                                  вы думате так легко подобрать KEY? MD5 дыряв не потому что он позволяет расшифровать хеш, это вообще невозможно теоретически. иначе бы все архиваторы тупо хешировали. максимум что вы можете найти — какую-то абстрактную коллизию типа 92#lp.,87' которая будет давать тот же хеш, но при этом KEY вы никогда не вытащите.
                                                    –1
                                                    Я то как раз не самоучка, но судя по вашему профилю, вас это все равно не волнует.
                                                      0
                                                      если не самоучка, тогда не пишите ерунду. совершенно же понятно что _оригинальную_ информацию с которой брался самый элементарный хеш, пусть вообще даже не хеш а crc32 — вытащить невозможно. а для вытаскивания KEY нужна или оригинальная фраза или можно не пытаться.
                                                    0
                                                    по просьбам трудящихся, выкладываю хеш:

                                                    echo 'habrahabr.ru+ключ' | sha512sum | md5sum
                                                    ce8d927248d6c5b6b4f8adce38647a29
                                                    echo 'microsoft.com+ключ' | sha512sum | md5sum
                                                    b249bbb0843b15d70276c7a8cec498a9
                                                    echo 'example.com+ключ' | sha512sum | md5sum
                                                    ff130d4f935b9481ab0225eebf8af98d


                                                    Даже три, для облегчения вашей задачи, представим себе на минутку, что вы заставили меня зарегаться на 3-х ваших сайтах.
                                                      0
                                                      если вы зарегались хоть на 1 их сайте, то пароли можно записать раньше, чем произвести над ними хеширование )
                                                        0
                                                        хеширование выполняю я, а результат хеш-функции — это мой пароль на ресурс. Что там происходит дальше — меня не волнует.
                                                          0
                                                          то есть вы каждый раз используте хеш при входе?
                                                            0
                                                            я описал свой подход для генерации паролей, суть которого очень проста и на выходе я получаю стойкий пароль, который уникален для каждого ресурса, но который я легко могу «вспомнить», т.к. знаю все исходные компоненты и нужные утилиты всегда под рукой.
                                          +1
                                          Спасибо за пост, а то я уже думал и вправду весь этот геморой с табличкой теперь не даст мне спокойно заснуть и не видеть больше красивых девушек в снах, а не какие то задротские таблички.
                                            0
                                            За это я и люблю хабрахабр.
                                              +4
                                              «Скандалы недели!!!!»

                                              «Хабрапользователь разоблачает фейковый взлом вконтакте.»

                                              «Математика против табличек: как создать сложный пароль и как его сломать?»

                                              «А так же в каждом выпуске: священные хабравойны!!»

                                              «Не пропустите! Только у нас!!»
                                              +4
                                              for 0..6000 {
                                              k = md5(k)
                                              }
                                              Это типичное заблуждение. Криптостойкость только уменьшается от таких преобразований.
                                                0
                                                Поясните.
                                                  +9
                                                  md5 есть функция, отдающая хеш по ключу. При этом взломать функцию, означает — найти ключ, который вернет такой же хеш, что и оригинальный.

                                                  Так вот оригинальный ключ и найденный совершенно не обязательно должны совпадать.

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

                                                    –3
                                                    тем не менее 3DES более криптостойкий чем DES
                                                      +3
                                                      да, 3DES более стоек, но при этом его длина ключа в 3 раза больше. 3DES был мерой усилить стойкость путем увеличения ключа — по сути в основе остался тот же DES, выполняемый 3 раза. Даже если ключи на каждом раунде выполнения DES будут разные и режим работы будет EDE, эффективная длина ключа составит 112 бит (против реальной длины ключа в 168 бит). Если использовать схему EDE2 эффективная стойкость алгоритма всего 80 бит, т.е. простыми словами в 2^88 раз менее стойким (26 порядков !)
                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                          0
                                                          ферштейн, мерси
                                                          да все логично
                                                        0
                                                        По-моему речь не шла об увеличении криптостойкости
                                                        (тем более, что её можно слегка повысить обратно, усложнив алгоритм до, например, for 0..6000 { k = md5(k + '.' + originalPassword) }, или что-то подобное)
                                                        Речь шла о том, что мы вручную сознательно увеличиваем количество времени, которое надо потратить на проверку одного значения пароля при прямом подборе, в 6000 раз.
                                                          +2
                                                          Не увеличиваете. Множество значений на выходе тоже самое, а криптостойкость добавлением «константы в периоде» не увеличить.
                                                            0
                                                            Ну множество значений-то на выходе в любом случае то же самое от 00000000000000000000000000000000 до FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, если брать за данность, что ресурсы хранят в большинстве случаев MD5 от пароля. Про невозможность криптойстойкость добавлением константы — может быть, чего не знаю, того не знаю.
                                                            А есть какие-нибудь эффективные методы сузить поле перебора, обладая знанием о том, что использован такой алгоритм и, следовательно, криптостойкость пароля снижена? Дадут ли эти методы прирост в производительности перебора (сужении поля перебора), который компенсирует потери производительности проверки одного значения?
                                                              +3
                                                              В случае готовых алгоритмов (md5, sha и т.д.) самое простое и эффективное — добавить соль и переставить пару символов на выходе. Это отсечет возможность нахождения подходящего ключа в лоб по имеющимся просчитанным таблицам.

                                                              Ну или изобретать свои криптостойкие алгоритмы :)
                                                                0
                                                                Бесполезно им объяснять, я постоянно в комментах вижу бред про каскадное хеширование.
                                                                  0
                                                                  Объясни нам, будь добр, может тогда не будешь больше видеть бреда в комментах.
                                                                  Мне казалось, что с точки зрения birthday paradox attack, или вот с точки зрения атаки на мультиколлизии из статьи ниже по ветке, каскадная функция hash(n) = MD5(hash(n-1)+original_value) не хуже (впрочем, и не лучше) оригинальной hash = MD5(original_value). Где можно было бы почитать про обратное?
                                                                  И, безусловно, на MD5 в большинстве случаев проводить такие атаки не имеет смысла, потому как искомое исходное сообщение часто имеет ограничения по длине и входящим в неё символам, а не только по значению её хеша.
                                                                  А с точки зрения перебора паролей по схеме пароль ---> алгоритм хеширования ---> хеш, каскадная функция линейно усложняет жизнь переборщику. Не очень впечатляет, конечно… тем более что мы так же линейно усложняем себе жизнь при проверке пароля от легального пользователя. Но зато даже хеши от пятибуквенных паролей не найдутся в Rainbow Tables и 10000 итераций делают разницу между 1 часом перебора и 1.5 годами.
                                                                  Короче говоря, для аутентификации на каком-нибудь форуме схема с каскадным хешированием звучит достаточно оправданно.
                                                                    0
                                                                    Речь шла не о hash(n) = MD5(hash(n-1)+original_value)
                                                                    а о hash(n) = MD5(MD5(MD5(MD5(original_value))))

                                                                    «на каком-нибудь форуме» убивает желание вам что-то разжёвывать.

                                                                    Я что, должен компенсировать недостатки вашего универа, где вам об величине энтропии на байт не рассказывали?
                                                                      0
                                                                      Так в том то и дело, что понты кидать легко и приятно, в отличие от обоснованного ответа.
                                                                      «Вижу бред про каскадное хеширование»… hash(n) = MD5(hash(n-1)+original_value) — это не каскадное хеширование?
                                                                      А даже если MD5(MD5(...MD5(original_value))… неужели вы хотите сказать, что результат будет иметь меньше энтропии, чем MD5(original_value)? Рассматривается ситуация, когда результат функции MD5 есть 16 байт, а не строка из 32 символов, разумеется.
                                                                        0
                                                                        Меньше. И любой первокурсник кафедры ЗИ это знает.

                                                                        for 0..6000 {
                                                                        k = md5(k)
                                                                        }
                                                                        Обсуждалось это, и только это. Хотя ваш вариант, ничем не лучше, там константа.

                                                                        Можете сколько угодно со слюной требовать доказательств и обоснований. Nobody cares. В комментах ниже, проскакивали пруфлинки, если на то пошло.

                                                                        Хешируйте хеши сколько влезет, от вашей самоуверенности, качество каскадного хеширования не повысится.
                                                                          0
                                                                          Та кто ж со слюной требует… Мирно себе беседуем. Только вы вот растопыриваетесь, чешете самолюбие…
                                                                          Я, увы, не любой первокурсник кафедры ЗИ, и ЗИ лежит довольно далеко от моих профессиональных интересов, но с удовольствием любопытствую в свободное от работы время.
                                                                          Поэтому попробую порассуждать с точки зрения обывателя, а светлый венценосный гуру меня поправит, ладно?
                                                                          Если взять за данность неидеальность md5 в терминах, что существуют два разных 16-байтных входных сообщения, дающие одинаковые 16-байтные значения md5, то действительно складывается впечатление, что последовательное применение md5 к собственным результатам понижает уровень энтропии, действительно можно согласиться.
                                                                          Но в схеме hash(n) = md5(hash(n-1)+original_value) (где операция +, допустим, конкатенация… или даже паддинг original_value слева или справа до фиксированной длины байтами хеша с прошлого раунда) предпосылки для потерь энтропии абсолютно неочевидны… Здравый смысл где-то меня подводит?
                                                                            0
                                                                            Ehash < E text

                                                                            Ehash < Ehash*hash

                                                                            Устал объяснять очевидное. Гуглите.
                                                                              0
                                                                              Парсер лох.

                                                                              E(hash(text)) < E(text)
                                                                              E(hash(hash(text))) < E(hash(text))
                                                                                0
                                                                                Я из интереса, когда это вы устали объяснять очевидное, пролистал ваши коментарии и нашёл похожую дискуссию в начале марта. Там тоже собственно тоже состоялся разговор слепого с глухим, такой же как тянется у нас тут. Больше не буду вас утруждать. Отмечу лишь, что если мы опредилим хеширующую функцию hath(text) = text (а мы можем это сделать, так как разговор у нас изначально шёл о паролях фиксированной длины, или о входных сообщениях фиксированного размера), то E(text) = E(hash(text)) = E(hash(hash(text))).
                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                    0
                                                                                    Молодец, упрощено, но верно.

                                                                                    Не только MD5, все односторонние функции
                                                                                      0
                                                                                      Да, только это рассуждения о стойкости к коллизиям. Имея md5(md5('resource+key')) можно подобрать такое изначальное сообщение, которое после первого хеширования будет отличаться, а после второго совпадет.

                                                                                      Но это сообщение не обязательно будет иметь формат 'resource+key'.

                                                                                      И даже если подобрать сообщение типа 'resource+keyX', то не факт что оно сработает для 'resource2+keyX'
                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                    0
                                                                    Диапазон тот же самый, а множество — совсем другое.
                                                                      0
                                                                      Да, есть. Мультиколлизии.
                                                                      Подробнее — в статье Antoine Joux. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. LNCS 3152/200
                                                                      Вас особенно заинтересует часть 4, «On the Security of Cascaded Hash Functions»
                                                                        0
                                                                        Очень интересная статья, спасибо.
                                                                    0
                                                                    А не проще ли считать количество попыток авторизации от одного логина и если за 1 минуту было более 10ти попыток, то банить, например, на 30 секунд?

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

                                                                        В таком случае тоже никак не получится ограничить количество попыток и препятствовать брутфорсу.
                                                                          0
                                                                          Никто не отменял и пентотал натрия внутривенно, также известный как «сыворотка правды».

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

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

                                                                                  Ну и никто не отменял пытки под пентоталом.
                                                                                    0
                                                                                    Значит так, пентотал — это анестетик. Если бы он действительно развязывал языки, то в тоталитарном светоче демократии уже давно бы допрашивали под пентоталом, «в целях установления истины и избежания ложных осуждений». Опыты в этом направлении у них были, закончились ничем. Так что среднему хабраюзеру от пентотала станет сонно и не больно.
                                                                                    Как ты понимаешь, пытки эффективнее без пентотала :-)
                                                                                      +1
                                                                                      Насколько я помню, это блокиратор нейромедиаторов.

                                                                                      Но глядя на ваш ник, спорить не буду.
                                                                          –1
                                                                          Это вообще к чему? Речь шли о том, что по md5 можно при большом желании восстановить секретный ключ и нагенерировать правильные пароли для нужных ресурсов. 600 md5 нужно затем, чтобы помимо желания взломщику понадобились бы ещё значительно бОльшие ресурсы.
                                                                            0
                                                                            не в курсе — есть ли где-то реальные истории про создание веб-приложений, которые блокируют доступ, если х попыток получить доступ для такого логина, y попыток восстановить пароль, z запросов с такого-то IP и так далее

                                                                            было бы интересно почитать
                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                        0
                                                                        От куда такие сведения?
                                                                        Взятие md5 от md5 только удаляет злоумышленника от реального значения.
                                                                          +2
                                                                          Ему не надо знать реальное значение. У злоумышленника нет задачи найти именно ваш пароль, который вы ввели при регистрации.
                                                                            0
                                                                            Ну это опять возвращает нас к открытому пока еще вопросу коллизий.
                                                                              +2
                                                                              Если я правильно понял, то если там, куда вводить пароль, применяется хеш md5, то достаточно подобрать комбинацию, хеш которой совпадает с хешем исходного пароля. Но это ведь не зависит от самого пароля.

                                                                              А в данном случае говорят о том, чтобы по паролю получить связку ресурс+соль, чтобы применить соль на другом ресурсе.

                                                                              И что в таком случае дает злоумышленику знание 5999*md5 (ресурс+соль)?
                                                                            0
                                                                            имхо имелось ввиду генерировать ключ таким методом. добавив свое хитрое преобразование на выходе, получаем маленькую программку которая не хранит пассы а генерит их на лету. чтобы злоумышленнику подобрать ключь к ресурсу нужен будет алгоритм взятия хэшей от sitename + nikname, что в свою очередь гораздо устойчивей чем приведённая выше таблица.
                                                                            +1
                                                                            Эм, ну вот минус, никто ни когда не ломает нормальные пароли брудфорсом, это нереально, ну не бывает таких мощностей в свободном доступе. Социальная инженерия рулит и бикает.
                                                                            Вы хоть 500 символьный пароль придумайте, вломятся все равно если очень надо
                                                                            Пароль пароль
                                                                            а. Должен иметь смысл только для вас (ну что делать если кто то не умеет свободно мыслить, для них придумали генераторы) для другого человека это другого человека это должна быть непонятная абракадабра и вы его ни когда не забудете
                                                                            b. Содержать парочку спец символов
                                                                            с. Быть не короче 6, да именно 6 символов это по моему мнению слабый но хороший пароль. 8 это уже золотая середина, а больше это уже паранойя
                                                                            (Карточку можно забыть, потерять, и вообще оказаться в положении без доступа к ней, глупо придумывать пароль, который ты никогда не запомнишь)
                                                                              +1
                                                                              Брутфорсом не ломают в онлайне.
                                                                                0
                                                                                Пример. Человек слил базу данных пользователей с известного форума. Узнал что пароли в базе лежат как просто md5 от исходного пароля, посмотрел соотв. емейлы, прогнал все хеши через rainBow таблицы, уже получил часть исходных паролей (тут же попробовал их же к почте применить), а если уж ему необходим пароль от конкретного пользователя то можно и побрутфорсить, на локальной машине число попыток в секунду поистине огромно.
                                                                                  0
                                                                                  Тогда уже он точно все взломает не зависимо от длинны пароля, опять же просто так слить базу не получиться, социальная инженерия! Везде она, самое безопасное место это жесткий диск залитый бетоном толщиной 80 метров на глубине полуторакилометров под землей без доступа из вне
                                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                                  +1
                                                                                  сам на своем ресурсе использую генерацию пароля через md5(и несколько параметров, как случайных, так и не очень). а потом еще добавляю перестановки и некоторые символы перевожу в верхний регистр. и несколько раз прогоняю этот алгоритм.
                                                                                    0
                                                                                    лучше применять sha, md5 уязвим к коллизиям.
                                                                                      0
                                                                                      спасибо, учту
                                                                                    +2
                                                                                    Просто табличка неправильно составлена. Порядок символов должен быть случайным и несовпадающим для каждой строки, а не просто сдвинут. Тогда будет 36! вариантов таблички.
                                                                                      –2
                                                                                      Это все замечательно и спасибо за выкладки. НО! КТО ЭТИМ БУДЕТ ЗАНИМАТЬСЯ?

                                                                                      О каком брутфорсе, названия сайта и тд?!

                                                                                      Какой-то вероятный злоумышленник которых хочет узнать пароль. что за бред?
                                                                                      Он увидит 42de3f1e2abcde5352124 (мд5 вариант) или 58jfzz984g2zga (в первом варианте с табличками)
                                                                                      Все, откуда он знает про метод шифрования, про раунды 600 раундов, про какие-то таблички и тд

                                                                                      в общем проблема высосанная из пальца.
                                                                                        0
                                                                                        Не «высосанная».
                                                                                        Зная законы распределения каждой буквы в нашем (или любом другом «натуральном» языке) можно легко расшифровать ЛЮБОЙ шифр (если вы не знаете — в обычных естественных языках буквы повторяются одинаковое количество раз) основанный на обычной замене одних символов другими.

                                                                                        В нашем случае есть еще сдвиг. Когда первый метод который я написал не прокатит, очевидно что применяется сдвиг, и его тоже очень легко взломать — шифртекст разбивают на одинаковые куски, и сравнивают символы на каждой из позиций — например на позициях 1, 3, 5 с законами распределения букв, если совпадений нет — изменяют промежутки разбивки, например сравнивают 2, 4, 6, и так до тех пор пока не получим совпадение, и все, — мы знаем длину ключа. После этого ломаем как простую «замену».

                                                                                        П.С. Обычно если ломают именно вас, атакующий уже знает информацию личного характера, вполне логично предположить что сидя за табличкой по 1-2 минуты по 10 раз в день — все будут знать как вы «шифруете» пароли.
                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                          0
                                                                                          Можно дилетанту задать вопрос? А бессвязные, более чем 10-ти значные пароли уже не?
                                                                                            0
                                                                                            У них только одна проблема — их сложно запомнить.
                                                                                            Если у вас всегда есть с собой KeePass то вполне.
                                                                                              0
                                                                                              Да, но если настолько озаботиться качеством пароля, то может сразу переступить неудосбтва и хранить все пароли в блокнотике бумажном?
                                                                                                0
                                                                                                Опять же, пока зашифруешь забытое написание пароля заново… Шило на мыло, на мой взгляд…
                                                                                                  0
                                                                                                  Если вы будете хранить свои пароли в бумажном блокнотике то для вас может оказаться шоком когда после пьянки с малознакомыми людьми (например с другом и его друзьями) вы этого блокнотика не обнаружите и никто ничего знать не будет.
                                                                                                  Я лично лучше буду хранить пароли в кипасе и жить спокойно чем хранить в блокноте и параноить на тему как бы он не пропал.

                                                                                                  Насчет
                                                                                                  зашифруешь забытое написание пароля заново

                                                                                                  не понял
                                                                                                    –1
                                                                                                    Ну, малознакомые люди у меня не пьянствуют. Столь важный документ я все равно надежно спрячу.
                                                                                                    Чесно говоря, доверяю гораздо больше документам, которые не подверженые электронному доступу.

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

                                                                                                      Смысл в том, что люди придумывают способы, которые позволят легко восстановить нужный пароль в месте, где нет доступа к хранилищу паролей (например в отпуске, когда блокнот остался дома).
                                                                                                        0
                                                                                                        Уровень параноидальности способа позволяет вспомнить о блокноте. Я говорю об этом. Опять же, сам способ показывает что он в теории взамывыаемый.
                                                                                            0
                                                                                            вы немного не правы — про 36 таблиц.
                                                                                            если потрудиться, то можно составить строки случайным образом меняя символы местами. и так для каждой строки.

                                                                                            просто в начале дан квадрат виженера, в котором идёт смещение не вправо, а влево. такой квадрат использовать удобнее, потому что не надо тратить много времени на его построение.
                                                                                              0
                                                                                              Удобная реализация md5('site+key'): pwdhash.com
                                                                                              Есть он-лайн сервис (считает клиентский javascript, key в сеть не передается), есть расширения для браузеров.
                                                                                              Пользуюсь около трех лет.
                                                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                0
                                                                                                Можно использовать многократное использование нескольких хеш функций md5 SHA1 3DES:
                                                                                                md5(sha1(des(… так 1000 раз......md5('site+key')....). причем можно задать определенный алгоритм для этой процедуры. Это должно уменьшить коллизии хешей.
                                                                                                Такой подход теже усложнит сильно подбор.
                                                                                                  0
                                                                                                  Простите, а зачем уменьшать коллизии? Их увеличивать нужно, для того что-бы сложнее было вычислить исходную фразу :)
                                                                                                    0
                                                                                                    Коллизией хеш-функций (обозначим её H) называется два различных входных блока данных (например пароли) a и b таких, что H(a) и H(b) равны. Тоесть хеш a входных данных и b входных данных одинаковы. Соответственно, чем больше у хеш-функции коллизий тем больше шансов её подобрать.

                                                                                                    Представьте, что вы ввели некий пароль «Андрей» и получили по определенной хеш-функции некий хеш этого пароля, например «f65hde45», коллизии это когда есть ещё какой-либо один (или даже несколько) паролей хеш которых будет точно такой же как и у вас «f65hde45». Это и называется коллизиями хеш-функций.
                                                                                                      0
                                                                                                      Вы абсолютно верно описали определение…
                                                                                                      Давайте вместе разберем наш случай:
                                                                                                      md5('x1'+'x2') = 'y', где x1 — наименование пользователя (сайт… и т.д.) и x2- это супер секретный Ваш личный пароль.
                                                                                                      Наша цель сохранить не дать злоумышленнику вычислить 'x2' при известной подстроке 'y' и тем самым получить алгоритм расчета всех ваших паролей на все сайты.
                                                                                                      Наша коллизия, это:
                                                                                                      md5('x1'+'x2') = md5('x3'+'x4')
                                                                                                      В общем возникает вопрос, чем это поможет злоумышленнику?
                                                                                                      Правильно… ничем… только еще больше все запутает. Конечно, все это IMHO.
                                                                                                  –1
                                                                                                  Вы забыли вероятностные выкладки.

                                                                                                  Какова вероятность, что «жертва» атаки использует метод «с табличками»? Какова вероятность, что «атакующий» знает и понимает все то, что вы здесь описали?
                                                                                                  0
                                                                                                  Люди добрые, ну чего вы прицепились к коллизиям?
                                                                                                  В MD5 выдает шестнадцатиричный результат, что делает его хоть в чистом, хоть в цикличном варианте или последней итерацией (читай последней операцией в конвейере) неприемлемым.
                                                                                                  Как вариант, нужно усложнять:

                                                                                                  echo 'бурёнка+habrahabr.ru' | md5sum | base64 | cut -b1-20
                                                                                                    +2
                                                                                                    Вы положили меня на лопатки и закатали под асфальт. И это правильно. По понятным причинам использовать полиалфавитное шифрование для шифрования нельзя. Это всё равно что ключ под коврик положить. Но ведь я не шифрование предложил. Это только идея генерации сложных паролей которые сложно в разумные сроки взломать методом перебора.

                                                                                                    Методы социальной инженерии никто ещё не отменял. Вы узнали пароль к моей учётной записи на habrahabr. Вам повезло.
                                                                                                    Теперь вы хотите узнать мою ключевую фразу. А почему вы решили что я использую имя ресурса habrahabr как есть? У меня-то много вариантов: rbaharbah, habrlubithabr, bestrbaharbah…
                                                                                                    Вы правильно посчитали, для размещения английских буквы в алфавитном порядке и цифр существует 36 способов. А если их располагать псевдослучайным образом? Тогда будет 36!=3.7199e41 вариантов.

                                                                                                    Псевдослучайным образом разместим символы в левом поле (пустые клетки считаем как отдельные символы), в верхнем поле и в основном поле. Тогда получим (36!)^7=9.857e290 вариантов таблицы.
                                                                                                    А если расширить таблицу по горизонтали и вертикали, как Вы предлагаете, то получим (102!)^3=8.8874e485 вариантов.
                                                                                                    А теперь попробуйте узнать мою ключевую фразу. А ведь это может быть что угодно, например сумма некоторых чисел Фибоначчи (седьмого, семнадцатого и сто семидесятого).

                                                                                                    Согласен абсолютно с тем, что пользоваться бумажной (и даже электронной) портянкой, мягко говоря, сложно. Ещё сложнее сгенерировать таблицу так, что бы потом её можно было восстановить. Но я предложил только идею, а не конечный продукт. Поэтому предложил желающим и умеющим программировать создать что-то реальное. Например приложение для мобильника.

                                                                                                    Когда-то давно кто-то предложил для полётов человека использовать крылья. Над этой идиотской идеей громко смеялись. Но нашлись энтузиасты и доработали эту глупость до реального железного самолёта.

                                                                                                    P. S. Вроде всё правильно посчитал.
                                                                                                      0
                                                                                                      rbJJkjwqmIyLm7er — это пароль к сайту mojdomen. Восстановите ключевую фразу, и я признаюсь в том, что я идиот.
                                                                                                        0
                                                                                                        Облегчу Вашу задачу.

                                                                                                        habrahabr — xsB6bFINNADm4fbF
                                                                                                        pavelpavlov — iKihopD8HJ1zd9Nt
                                                                                                        yandex — tkwp02TSPwEPvem8
                                                                                                        google — cswdwcR619sTAOTA
                                                                                                        yahoo — riSbRrvc2RcXGkv0

                                                                                                        И какое ключевое слово?
                                                                                                          0
                                                                                                          Добавить?
                                                                                                            0
                                                                                                            Да, табличку еще)
                                                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                              +1
                                                                                                              Я не стану отвечать на вопросы социальной инженерии. Иначе мне тут же придётся признать что я идиот.
                                                                                                              По условиям задания злоумышленнику удалось заполучит пароли к шести ресурсам. И всё.
                                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                            –5
                                                                                                            статья — полная лажа, и эта лажа начинается со слов «Всего существовать по такому методу может 36 таблиц», дальше не читал
                                                                                                              +1
                                                                                                              А Вы читали статью которую здесь критикуют? Там ничего прямо не говорится о том что существует более 36 таблиц. Я точно не нашёл. Хотя косвенные предпосылки есть. Но ведь критика основана на конкретной статье с конкретными примерами. А значит автор этой критики прав. Прав и всё.
                                                                                                                –5
                                                                                                                ну я тогда скажу что он пернул в лужу взяв какой чмошный частный случай в паралелльной вселенной где какие-то дебилы используют неизвестное в этой вселенной ограничение и у них там не больше 36-и вариантов получается, и пусть даже он прав в своей лажовой правоте, меня проблемы негров не волнуют
                                                                                                                +2
                                                                                                                Статья не лажа, хотя-бы потому, что заставила народ поскрипеть мозгами чутка, что во всех смыслах полезно.
                                                                                                                  –2
                                                                                                                  ну вы загнули — это все-равно что окунуть кого-то в дерьмо с целью чтобы он отмылся
                                                                                                                    +1
                                                                                                                    «При философской дискуссии больше выигрывает побежденный — в том отношении, что он умножает знания». © Эпикур
                                                                                                                    Я выиграл.
                                                                                                                  0
                                                                                                                  Даже не думал, что о паролях можно столько написать :)

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

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