SHA-1 взломан

>в сети даже ресурс такой был - который по md5 хешу выдавал точный текст фокус в том что на том серваке были сгенерированы хеши для всех более менее распространенных слов, так что задача фактически сводится к обратному поиску по базе данных текст-хеш (

Бред. Или мы о разных серверах. Мне товарищ, игравший с таким сервером (самому влом было пробовать) прислал мой пароль из несловарного набора букв, цифр и знаков препинания. Только там было ограниение - меньше 8 символов. Хотя, конечно, могли под это дело забить тупо массив на (8+16)*2^64 байт :D

В волшебной статье сказано что она успела родить дочь и вырастить балкон цветов.

Этому - верю, а вот слова "cracked SHA-1" она понимает как-то странно : "I knew I was the only person who knew this world-class secret."

Да, а еще китайцы изобрели порох, бумагу и компас. Но не использовали - зачем ? - так и сидели за своей Великой стеной...

> Этому - верю, а вот слова "cracked SHA-1" она понимает как-то странно : "I knew I was the only person who knew this world-class secret."

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

Там написано примерно: "В тот день когда я взломала SHA-1, я так была взволнована, что даже не ела. Я была единственным человеком, который знал этот мировой секрет". Причём тут порох и Китайская Стена?

>>Это не брутфорс, а использование словаря. >Принципиально разные подходы.

>Разница в тупом переборе конечного набора символов или слов словаря. Очень принципиально ;)))

На самом деле да, очень принципиально. Представь себе такое - к тому же jack'у модуль добавить, что бы:

1. сначала лез бы на сервак в инете и искал бы там хэш. 2. если не находим, начинаем перебирать. 3. при переборе используем накопительные данные о тех промежутках где хэша точно нет (см пункт 1.), при нахождении хэша заливаем его на сервак. При переборе диапазонов которых нет на серваке (периодически ходим туда и смотрим че как, мож наш хэш уже кто нашел и диапазоны изменились) - заливаем туда эти данные, все в сжатом виде

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

тпфу, к джону в смысле. /me накурен в говно и пьян просто

>>Значит на серваке хранится пароль открытым текстом? О какой безопасности тогда может идти речь?

Ежели вам посчасливится стянуть файл паролей с чужого сервака можете сами посмотреть как они хранятся. По любому пароль знают 2 стороны. Одна которая говорит и одна которая пропускает. Узкое место - авторизация, кабы третья сторона уши не развесила. Там юзают одноразовый однонаправленный (это как раз и под вопросом) хеш. Собсно теоретическая однонаправленность делает перехват бесполезным. Перебор случайного хеша по словарю принципиально невозможен. Алгоритм взлома методом перебора выглядит приблизительно так:

1)Перехват ключа.

2)Перехват ответа

3)Перебор вариантов паролей дабы сравнить хеш варианта с перехваченным образцом.

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

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

В данном случае узкое место не авторизация, а регистрация. Сиди да перехватывай пароли, идущие открытым текстом.

>Китаянка утверждает что может за приемлемое время (меншее чем для при переборе вариантов) вытащить их хеша пароль.

В общем случае время перебора вариантов бесконечно. А полбесконечности это тоже бесконечность.

Простите, а что значит "одноразовый однонаправленный хеш"? У меня создается впечатление что Вы не в "теме"

Погодите, сторона которая пропускает, знает пароль или хэш пароля?

Если сам пароль то сразу вилы. Если хеш, то по описанному вами алгоритму

>1) Сервер посылает случайный ключик длиной эдак байтов в 50

>2) Клиент дописывает туды байтов 8 (ну типа пароль) и получает мд5 хэш этой байды, который затем отсылает на сервак.

>3) Сервак сравнивает этот хеш с тем что у него самого получилось.

действовать невозможно - ответ клиента серваку сравнивать не с чем.

Кто восстановит текст по его SHA1?

2e1b3bfe51999a4791e5b25c48c74cba54e8520d

Подсказка: это приветственное слово посетителям LOR.

Тебе не на ЛОР , тебе в китай нужно !

>Кто восстановит текст по его SHA1?

Это очень сильное колдунство. Всуе его использовать нельзя.

> В общем случае время перебора вариантов бесконечно. А полбесконечности это тоже бесконечность.

Не может оно быть бесконечным, поскольку имеются ограничения на длину пароля. Например, скорость, с которой компьютер может обрабатывать данные от клавиатуры (типа, быстрее частоты синхроимпульсов контроллера клавиатуры никто ничего не введет даже при всё желании). Другое ограничение - TTL набирающего пароль. Причем, TTL должен отсчитываться максимум от появления первого компьютера. Третье ограничение - конечное число всех символов всех языков мира. Ну и тому подобное :)

мда.. ЛОР плохеет =(

уберите _это_ из новостей

>Не может оно быть бесконечным, поскольку имеются ограничения на длину пароля. Например, скорость, с которой компьютер может обрабатывать данные от клавиатуры (типа, быстрее частоты синхроимпульсов контроллера клавиатуры никто ничего не введет даже при всё желании). Другое ограничение - TTL набирающего пароль. Причем, TTL должен отсчитываться максимум от появления первого компьютера. Третье ограничение - конечное число всех символов всех языков мира. Ну и тому подобное :)

Ну вообще-то да. Но тут возникает проблема -- какое бы ограничение мы не выбрали, обязательно найдется извращенец, у которого пароль длиннее. И TTL не поможет -- можно вытянуть пару гигабайт из /dev/urandom и использовать их.

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

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

>Кто восстановит текст по его SHA1?

Там написано "всем лоровцам сосать писю, sha1 ни одна баба не взломает".

Я угодал?:)

> интересно какая БД требуется чтобы хранить хеши всех возможных паролей из максимум 16 символов ?

Давным-давно я слышал что якобы где-то в Австралии стоит кластерочек с суммарным объемом базы в 120ТБ и в базе всего одна табличка с хэшами MD5 :)

одна табличка и одна колонка :)

>Давным-давно я слышал что якобы где-то в Австралии стоит кластерочек с суммарным объемом базы в 120ТБ и в базе всего одна табличка с хэшами MD5 :)

Для 128-битного алгоритма MD5 база должна содержать 2^128 или 3.4*10^38 строк и двух столбцов: хеш (16 байт) и вариант расшифровки (будем считать, что тоже 16 байт).

Итого в базе должно хранится (16+16)*3.4*10^38 байт == 10^28 TB

Эти 120ТБ кажутся жалкими на фоне такого числа.

> Погодите, сторона которая пропускает, знает пароль или хэш пароля?

> Если сам пароль то сразу вилы. Если хеш, то по описанному вами алгоритму

>> 1) Сервер посылает случайный ключик длиной эдак байтов в 50

>> 2) Клиент дописывает туды байтов 8 (ну типа пароль) и получает мд5 хэш этой байды, который затем отсылает на сервак.

>> 3) Сервак сравнивает этот хеш с тем что у него самого получилось.

> действовать невозможно - ответ клиента серваку сравнивать не с чем.

На сервере хранится хэш пароля, он посылает ключик клиенту, клиент от пароля берёт хэш и дописывает к ключику, сервер делает у себя так же, клиент посылает серверу результат и сервак сравнивает

>На сервере хранится хэш пароля, он посылает ключик клиенту, клиент от пароля берёт хэш и дописывает к ключику, сервер делает у себя так же, клиент посылает серверу результат и сервак сравнивает

Окей, нахрена тогда сам пароль, если все пользуются его хэшем?

>На сервере хранится хэш пароля, он посылает ключик клиенту, клиент от пароля берёт хэш и дописывает к ключику, сервер делает у себя так же, клиент посылает серверу результат и сервак сравнивает

Слишком много хеширования в одном месте. Ты, между прочим, забыл сказать, что "ключ" + хеш пароля тоже должны обязательно хешироваться (иначе взлом банален). То есть ты просто подменяешь пароль его хешем, знание хеша пароля позволяет взломать систему. А это глупо, проще уж его совсем не хешировать (устройчивее будет).

> нахрена тогда сам пароль...?

Мозги закипели и пошел стёб.

Сабж: китайцы, опираясь на коллизии, просто создали таблицу для всех хэшей ща-1, я правильно понял?

>Ты, между прочим, забыл сказать, что "ключ" + хеш пароля тоже должны обязательно хешироваться

Он сказал :)

> Слишком много хеширования в одном месте. Ты, между прочим, забыл сказать, что "ключ" + хеш пароля тоже должны обязательно хешироваться (иначе взлом банален). То есть ты просто подменяешь пароль его хешем, знание хеша пароля позволяет взломать систему. А это глупо, проще уж его совсем не хешировать (устройчивее будет).

Вспомнил в тему - давным давно один вася на ixbt собирался сделать raid0 из нескольких тысяч винтов, типа базы некие некритические хранить на канале с феерической пропускной способностью. Не помню, правда, был ли он китайцем...

Не говорите мне, что MD5 вскрыли. Если вскрыли - приведите для примера хотя бы 1 коллизию (т.е. 2 разные строки дающие один и тот же хеш). Пока такого не будет, говорить о взломе нет смысла.

В MD5 коллизии уже давно нашли. Почитайте википедию: http://en.wikipedia.org/wiki/MD5

Вот ссылки с этой страницы:
http://www.cits.rub.de/MD5Collisions/
http://www.mathstat.dal.ca/~selinger/md5collision/

Коллизии - дело хорошее. Но малоприменимое.

Пример : рассмотрим MD5 хэши всех возможных 8-символьные пароли (26 букв и 10 цифр). Вопрос : есть коллизии ? Если нет, то с паролями у нас все в порядке :-)

Если рассматривать MD5 простого текстового сообщения, то интересной была бы возможность изменения текста сообщения злоумышленником для извлечения выгоды с сохранением того же MD5 хэша.

Сколь я помню, была пример с 2-мя файлами PostScript, но не текстовыми файлами.

все случилось за год до того, как мир поработили холодильники, подключенные к сети Internet

> Окей, нахрена тогда сам пароль, если все пользуются его хэшем?

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

>Сабж: китайцы, опираясь на коллизии, просто создали таблицу для всех хэшей ща-1, я правильно понял?

Не могли они этого сделать. Тут считали уже, сколько места потребуется.

>Не говорите мне, что MD5 вскрыли. Если вскрыли - приведите для примера хотя бы 1 коллизию (т.е. 2 разные строки дающие один и тот же хеш). Пока такого не будет, говорить о взломе нет смысла.

Гугль в руки. Примеры коллизий в новости приводились.

>что показательно, ученый то китайский...

Ну, так у них свой алгоритм взлома.
Все китайцы собираются и шлют пароль "Мао Дзедун", пока сервер не 
соглашается, что это правильный пароль.

>Эти 120ТБ кажутся жалкими на фоне такого числа.

У тебя в пароль входят русские символы? %). В подавляющем большинстве случаев можно выкинуть половину ascii-кодов и дело идет значительно шустрее.

>У тебя в пароль входят русские символы? %). В подавляющем большинстве случаев можно выкинуть половину ascii-кодов и дело идет значительно шустрее.

md5 использует все 128 бит, двоечник. а пароли тут вообще не при чем.

Можно так прикинуть. Хешей 2^128 или 0.25*1024^13. Будем считать, что доступный ныне объем -- около 1Пб (1025^5 б), а емкость за 10 лет увеличивается в 1024 раза (за прошедшее десятилетие примерно настолько выросла). Значит можно ожидать создания такой базы примерно через 80 лет.

>> eDonkey - крупнейший восстанавливатель файла по его md5

>eDonkey использует MD4

модифицированный. там финализация по другому сделана. соответственно результат разный

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

>Кто восстановит текст по его SHA1?

>Там написано "всем лоровцам сосать писю, sha1 ни одна баба не >взломает".

>Я угодал?:)

Нет. Я же сказал приветственное слово, а не предложение. К слову сказать, слово "угодал" ты всегда можешь проверить однокоренным словом "догАдка", а то тебя скоро и без крипто никто поймет. ;)

>К слову сказать, слово "угодал" ты всегда можешь проверить >однокоренным словом "догАдка", а то тебя скоро и без крипто никто >поймет. ;)

Блин, ступил :(. То-то смотрю предложение как-то странно выглядит. Пойду книжку почитаю.

PPS а слово-то длинное? А то я на него johntheripper натравлю если он sha1 держит :).

>> Не может оно быть бесконечным, поскольку имеются ограничения на длину пароля. Например, скорость, с которой компьютер может обрабатывать данные от клавиатуры (типа, быстрее частоты синхроимпульсов контроллера клавиатуры никто ничего не введет даже при всё желании). Другое ограничение - TTL набирающего пароль. Причем, TTL должен отсчитываться максимум от появления первого компьютера. Третье ограничение - конечное число всех символов всех языков мира. Ну и тому подобное :)

> Ну вообще-то да. Но тут возникает проблема -- какое бы ограничение мы не выбрали, обязательно найдется извращенец, у которого пароль длиннее. И TTL не поможет -- можно вытянуть пару гигабайт из /dev/urandom и использовать их.

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

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

Не спорьте. Вы оба вообще не соображаете в хеширующих криптографических алгоритмах.

>К слову сказать, слово "угодал" ты всегда можешь проверить >однокоренным словом "догАдка", а то тебя скоро и без крипто никто >поймет. ;)

>Блин, ступил :(. То-то смотрю предложение как-то странно выглядит. >Пойду книжку почитаю.

>PPS а слово-то длинное? А то я на него johntheripper натравлю если >он sha1 держит :).

>anonymous (*) (23.01.2007 21:05:23)

Нет, короткое. Первая буква "х", последняя буква как первая в слове "йогурт", а вторая как в слове "хуй". :)

>> На сервере хранится хэш пароля, он посылает ключик клиенту, клиент от пароля берёт хэш и дописывает к ключику, сервер делает у себя так же, клиент посылает серверу результат и сервак сравнивает

> Слишком много хеширования в одном месте. Ты, между прочим, забыл сказать, что "ключ" + хеш пароля тоже должны обязательно хешироваться (иначе взлом банален). То есть ты просто подменяешь пароль его хешем, знание хеша пароля позволяет взломать систему. А это глупо, проще уж его совсем не хешировать (устройчивее будет).

Млин, целая дискуссия с кучей догадок и гипотез. А найти описание и прочесть слабо?

http://en.wikipedia.org/wiki/Digest_access_authentication

>Не спорьте. Вы оба вообще не соображаете в хеширующих криптографических алгоритмах.

Во-первых мы не спорим, а во-вторых не похоже, что тебе есть что сказать по существу.

>Млин, целая дискуссия с кучей догадок и гипотез. А найти описание и прочесть слабо?

Ты хоть почитай о чем речь, прежде чем "каммент пейсать", аффтар.

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

Достаточно хранить хеши паролей. А чтобы затруднить использование словарей для извлечения паролей из хешей в случае их утечки, лучше хранить хеш(пароль+логин+ещё какая-нибудь константа).

> В данном случае узкое место не авторизация, а регистрация. Сиди да перехватывай пароли, идущие открытым текстом.

Авторизация - это разграничение прав доступа. Ты имеешь ввиду аутентификацию.

>> Китаянка утверждает что может за приемлемое время (меншее чем для при переборе вариантов) вытащить их хеша пароль.

Бред. Задача не решаема, т.к. хеш имеет конечную длинну, поэтому всегда есть разные исходные данные, имеющие одинаковые хеши. При взломе ищут исходные данные, дающее заданный хеш. А совпадают ли они с первоначальными - никого не интересует.

> В общем случае время перебора вариантов бесконечно. А полбесконечности это тоже бесконечность.

Хеш имеет конечную длинну, поэтому для устойчивого к коллизиям алгоритма задача решается перебором числа вариантов, примерно равному числу вариантов самого хеша, что зависит от его длинны.

>> Млин, целая дискуссия с кучей догадок и гипотез. А найти описание и прочесть слабо?

> Ты хоть почитай о чем речь, прежде чем "каммент пейсать", аффтар.

Почитал. Бред любителей писать, а не читать и думать.

>> Давным-давно я слышал что якобы где-то в Австралии стоит кластерочек с суммарным объемом базы в 120ТБ и в базе всего одна табличка с хэшами MD5 :)

> Для 128-битного алгоритма MD5 база должна содержать 2^128 или 3.4*10^38 строк и двух столбцов: хеш (16 байт) и вариант расшифровки (будем считать, что тоже 16 байт).

Практическая ценность такой базы равна нулю, потому что требуется решать следующую задачу: hash(X + A) = B, найти X при известных A и B.