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

| Сообщение посчитали полезным:

Всё, что я нашел - это вот что: www.ssl.stu.neva.ru/psw/crypto/bfdobsoy.htm
В каком смысле - "ключ хранится в данных"? Ты имеешь в виду, что в зашифрованном блоке содержится сам ключ?

-----
Харе курить веники и нюхать клей, к вам едет из Америки бог Шива, и он еврей.

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

Нет, так как Blowfish устойчив к known plaintext атакам (строго говоря, вообще ко всем общеизвестным атакам). Только brute force или искать ошибки в данной конкретной реализации алгоритма.

| Сообщение посчитали полезным:

Вот у мну стотья есть:


47e0_20.09.2008_CRACKLAB.rU.tgz - Алгоритм криптования Blowfish -- Годом позже..rtf

-----
PSP-Gamer.ru

| Сообщение посчитали полезным:

Вот ещё нашёл

24d9_20.09.2008_CRACKLAB.rU.tgz - BlowFish.Tut.txt

-----
PSP-Gamer.ru

| Сообщение посчитали полезным:

Мда... ни одной успешной атаки((((
Жаль...

| Сообщение посчитали полезным:

Azur1d пишет:
этот же ключ хранится в данных
Если этот же ключ хранится в данных и
Azur1d пишет:
так проверяется правильность расшифровки

ТО с чем проверяется ? хочешь сказать что мы имеем
Ключ - К
Данные -Д
БлоуФиш - Б:
Б(К, Д)= шифрограмма (Ш)
Б(К, Ш)=К ???
то соответственно Д=К

возможен вариант конешно Б(К,(К+Д))=Ш
и тогда сложней чутка, кстати какой блок используется у блоуфиша у тебя? если 128 то тебе понадобиться всего лишь 139 дней для полного перебора a-z 0-9

| Сообщение посчитали полезным:

FleXik пишет:
если 128 то тебе понадобиться всего лишь 139 дней для полного перебора a-z 0-9
откуда взята цифра 139?

| Сообщение посчитали полезным:

BF.EncryptString("123456781234567812345678", "12345678", True) ->
2AE3113913994B13AA424A249A041275C5AF73F2C662C125015F886C2D328914818F8D 24171E85D0

->
xxx= 2AE3113913994B13AA424A249A041275C5AF73F2C662C125015F886C2D320000000000 0000000000
->
BF.DecryptString(xxx, "12345678", True) -> 123456781234½tدÊþ¨Ë

делай выводы

| Сообщение посчитали полезным:

Ara пишет:
откуда взята цифра 139?
гыг ну на моем компе было примерно столько =) 2.6Ггц =)

| Сообщение посчитали полезным:

FleXik пишет:
BF.EncryptString("123456781234567812345678", "12345678", True) ->
2AE3113913994B13AA424A249A041275C5AF73F2C662C125015F886C2D328914818F8D 24171E85D0

->
xxx= 2AE3113913994B13AA424A249A041275C5AF73F2C662C125015F886C2D320000000000 0000000000
->
BF.DecryptString(xxx, "12345678", True) -> 123456781234½tدÊþ¨Ë

делай выводы

и почему у тебя шифрование необратимым получилось?)))))))

| Сообщение посчитали полезным:

Azur1d
Шифрование обратимое, но блочное.
смотри внимательнее xxx не равен шифровке BF.EncryptString(...)

"т.к. проверяется правильность расшифровки".
На счет ключа в данных, по-моему, ты что-то перемудрил.
Расшифровка по какому ключу делается?
С чего появилась уверенность, что в данных проверяется ключ, а не их целостность в общем?


Простой пример - закриптуй текстовое сообщение. Попробуй распаковать его неправильным ключиком. В качестве элементарной проверки может подойти проверка используемого в результате алфавита - как минимум символов 0x01-0x08 в нем не будет.

| Сообщение посчитали полезным:

flamer пишет:
На счет ключа в данных, по-моему, ты что-то перемудрил.
Расшифровка по какому ключу делается?
С чего появилась уверенность, что в данных проверяется ключ, а не их целостность в общем?
Трассировал с правильным ключем)))
flamer пишет:
смотри внимательнее xxx не равен шифровке BF.EncryptString(...)
действительно) сорри, тупанул)

| Сообщение посчитали полезным:

ДЛя блоуфиша максимальная длина ключа 56 символов (ака 442 бита кажется )
если у тебя ключ <=10 то реально подыскать правильный если больше..... могут уйти годы =)))
хотя нет... впринципе блок у моего алгоритма- 64 бита (8 символов) то есть не зависит от ключа, кароч бери первые 8 бит своего шифротекста и декриптуй их на брут, а потом проверяй первые 8 букв пароля и первые 8 букв результата ..... декриптовка достаточно быстрая...... за полгода реально перебрать Очень много вариантов, или ты пишешь прогу наподобии взлома рар архивов? =)

да кстати если мне память не изменят то Брос Шнаер (создатель БФ ) вроде говорил что не стоит использовать текст в качестве ключа... я поищу поподробнее завтра отвечу

| Сообщение посчитали полезным:

FleXik, блок 64 бита. Но полгода это нереально. Нужна скорость около двух дней, это максимум.

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

drin да спасибо за поправочку , просто я когда пишу на скорую руку часто биты с байтами путаю =))) ну а символ я считаю 8 бит =)

| Сообщение посчитали полезным:

Azur1d
ну полгода это я имел ввиду практически все комбинации для 56 букв [a-z0-9]....
если бы вы предоставили дополнительных характеристики такие как
"ключ состоит только из a-z" или "длина не больше N"
было бы чуток яснее....
потому что написать прогу дело не хитрое, но вот что бы оптимизировать ее именно под вашу задачу надо подумать так как это существенно сократит время поиска приемлемого решения...
если же пароль неопределен совсем то есть любой набор печатных комбинаций то и писать что то не имеет смысла так как уже при 5 символах пароля из 50 возможных комбинаций дает уже 312500000 вариантов а на клаве вроде их больше.... для пароля из 8 символов для [a-zA-Z] (26+26=52) это 52^8=53459728531456 разных комбинаций.... продолжать нужно?

| Сообщение посчитали полезным:

Длина пароля 10 знаков, алфавит - [a..z, 0..9]. На прямой перебор время получается дикое, а plaintext-атак нет(

| Сообщение посчитали полезным:

понимаешь здесь самое плохое что надо расшифровать не только 1 блок а надо расшифровать весь шифротекст а потом только сравнивать ибо
xxx= 2AE3113913994B13AA424A249A041275C5AF73F2C662C125015F886C2D320000000000 0000000000
->
BF.DecryptString(xxx, "12345678", True) -> 123456781234½tدÊþ¨Ë

а
xxx= 2AE3113913994B13AA424A249A041275C5AF73F2C662C125015F886C2D32
->
BF.DecryptString(xxx, "12345678", True) -> €Ô2


таким образом каждый блок завязан на предыдущий ( у меня под рукой нет книжки пока что, но скоро я возму ее - может там что то будет полезное

к чему я это собственно... к тому что чем больше шифротекст тем дольше будет расшифровывать и отдельно взяты блок раскриптовать не получится без остальных ((

| Сообщение посчитали полезным:

Верно. НО!!! Каждый блок завязан на предыдущий, значит для первичного подбора ключа можно расшифровать только первый блок. Правда по моим прикидкам получается все равно долго(((

| Сообщение посчитали полезным:

FleXik, Azur1d
Это зависит от реализации.

Например в классическом варианте, с помощью ключа формируются P[] и S[][] таблицы, которые в процессе использования остаются неизменными.
И дешифровка идет блоками по 64 бита, которые ни как не связаны друг с другом.


Кстати говоря, он-лайн пример нормального (обычного) алгоритма:
http://webnet77.com/cgi-bin/helpers/blowfish.pl http://webnet77.com/cgi-bin/helpers/blowfish.pl

Пароль: 12345678
данные: 123456781234567812345678
результат(без пробелов разумеется): 14BCD3CA57275A52 14BCD3CA57275A52 14BCD3CA57275A52
В этом примере получается очень наглядно -- исходные данные -- три одинаковых восьмибайтных блока.
Результат - аналогичный -- три одинаковых восьмибайтных блока.

Ну, для "наглядности" можно и по частям распаковать:
Распаковка по частям: (пароль тот же)
данные: 14BCD3CA57275A52 ( восемь байт от начала)
Выход (decrypt): 12345678

данные: 14BCD3CA57275A52 14BCD3CA57275A52
Результат: 1234567812345678

http://www.schneier.com/blowfish-download.html http://www.schneier.com/blowfish-download.html
http://www.schneier.com/code/bfsh-koc.zip http://www.schneier.com/code/bfsh-koc.zip




Этот код можно и нужно оптимизировать. Он не самый шустрый.
От приплюснутых версий (на мой взгляд) стоит отказаться из-за перегруженности кода.
Возможно имеет смысл узкое место F(..) переписать как асмовский инлайн.
Основное торможение, которое дает этот код выявляется при получении a,b,c,d.
Оптимизировать можно, например, так
*псевдокод:


В довесок ощутимые накладные расходы заметны при разыменовывании ctx->S[][].
Огромную выгоду можно получить, если преобразовать массив S[4][256] в глобальный (точнее доступный напрямую функции F) массив S[256*4]
в этом случае можно использовать, например LEA Для подгрузки нужного адреса
-- в один регистр забросить оффсет S,
-- во второй в младший байт - забросить a,b,c,d ( что требуется на данном этапе),
а первый байт использовать как индекс таблицы. увеличивая его простым инкрементом
Т.е. для а = 0, b=1, c=2 d = 3,

в результате *адрес* нужного слова легко вычисляется практически без обращения к памяти (только с использованием регистров).

---
Если не лениться, и пойти дальше, можно еще увеличить скорость работы. Для этого требуется развернуть слова задом наперед (разумеется и в стартовых S P массивах). В результате можно будет (из предложенного мною выше варианта) выкинуть команду ror 16.



Резюме - алгоритм шифрования в классике не связывает блоки между собой.
"Узкую" функцию F можно и нужно оптимизировать под конкретный процессор, тем более, что она является самой вызываемой -- используется как в инициализации, так и в работе. Сокращение скорости ее выполнения даже на 1 процент даст колосальный прирост скорости.

| Сообщение посчитали полезным:

2flamer
гхмм отлично изложено! =) к сожалению есть одно НО
раз пароль 10 знаков и состоит из a-z0-9 то
36^8=2821109907456 возможных комбинаций
пусть прога перебирает 2милиона паролей в секунду
тогда имеем 2821109907456 \ 2 000 000 = 1410554 секунд \ 60=23509 минут \60 = 392 часа\24=16.5 суток ... я нигде не напутал?
2 милиона паролей я не загнул случайно? =)
2Azur1d впринципе из поста flamer я могу сказать следующее - надежда есть, но все в твоих руках... достанешь суперкомпутер из вашингтона и ускоришь алгоритм до тактов процессора - думаю что за 2 дня он тебе его переберет

| Сообщение посчитали полезным:

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

Но...
Сделаем одно простое решение -- ударим по неизвестности бредом и..
ПРЕДСТАВИМ, что
1. пароль не может быть только из цифр
2. пароль не может содержать три одинаковых символа подряд.
Что получится? ;) диапазон сократится многократно.
Но, не на столько, чтобы не огорчиться, когда ты заметишь ошибку в расчетах.
Пароль 10 знаков, алфавит - 36 знаков.
Каково количество "абсолютно разных" паролей?
Правильный ответ 36^10

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


| Сообщение посчитали полезным:

flamer пишет:
1. Если топикстартер говорит, что ключ внутри строки и он его расшифровывал валидным ключом. То подразумевается, что он знает маску ключа (или предполагает ее)
Никакой маски, абсолютно рандомная строка.

flamer пишет:
2. Несуразно использовать пароль длиной в десять символов, ибо десять это число, которое не кратно 4 (загляните-ка в функу инициализации).
Чего-то я не очень врубаюсь, как это поможет при подборе. Проясни плиз)

| Сообщение посчитали полезным:

Azur1d пишет:
С чего появилась уверенность, что в данных проверяется ключ, а не их целостность в общем?
Трассировал с правильным ключем)))
Откуда взят ключ?
Azur1d пишет:
Никакой маски, абсолютно рандомная строка.

К вопросу как это поможет.
Великолепно, понятие "абсолютно рандомная" это не преувеличение?
Ее создает человек? Или программа?
1. Человек, составивший защиту не использует все возможности алгоритма.
Если программа, (что скорее всего), то на что опирается? На какие данные, апи и т.п.
Это известно?
Вполне возможно, что имеет смысл после оптимизации алгоритма брута взяться за алгоритм "рандома".
Элементарный, разумеется не самый удачный, но пример - библиотечная функция C rand()
Если ее не инициализировать, то никакого рандома не будет -- получится предсказуемая (если быть точным, одинаковая для каждого запуска) последовательность.
Если же инициализировать, например временем Timestamp, либо Microtime, то перебор имеет смысл переключить на него. Озу, диски и прочая привязка к хардвару, то диапазон поисков увеличивается, но не намного -- Все меньше, чем десять знаков из алфавита в 36 символов.

| Сообщение посчитали полезным:

flamer пишет:
Правильный ответ 36^10
вариантов паролей - да , а вот я считал немножко другое
у нас вроде как шифруются всего навсего 64 бита хотя может я и ошибаюсь, но я считал для возможных вариантов первых 64 бит =)

| Сообщение посчитали полезным:

flamer, некоторые ключи были получены ранее. но не все.
"абсолютно рандомная" это конечно преувеличение, но как она получается неизвестно, к сожалению(((

| Сообщение посчитали полезным:

FleXik пишет:
раз пароль 10 знаков и состоит из a-z0-9 то
36^8=2821109907456 возможных комбинаций
пусть прога перебирает 2милиона паролей в секунду
тогда имеем 2821109907456 \ 2 000 000 = 1410554 секунд \ 60=23509 минут \60 = 392 часа\24=16.5 суток ... я нигде не напутал?
Напутал во второй строке - пароль состоит из 10-ти знаков, а не из 8-ми:
36^10=3656158440062976 возможных комбинаций
пусть прога перебирает 2 милиона паролей в секунду
тогда имеем 3656158440062976/2000000/60/60/24=21158,3 суток, то есть 60 лет

| Сообщение посчитали полезным: