— unknown (05/02/2015 09:43)   
Если используется:


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

— gegel (05/02/2015 11:48)   

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

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

— Гость (05/02/2015 12:54)   
Скорее всего, буду освежован :-), но мне не дает покоя мысль избежать необходимости запоминать случайную парольную фразу.

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

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

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

Возьмем, для примера, ужасное травматическое воспоминание "мышь злобно таращила глаза дико кричала и хотела съесть меня". Если я никогда это никому не сказал, энтропия такой парольной фразы будет отличаться от значения (полный словарный фонд языка)^10, поскольку в предложении использовано шесть устойчивых и распространенных языковых единиц:

"мышь"
"я"
"и"
"злобно таращить глаза"
"дико кричать"
"хотеть съесть"

Таким образом, более полное значение энтропии будет (полный состав языковых единиц языка)^6.

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

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

– исходный объем языковых единиц
– длинна парольной фразы
– (форма, в которой представленна парольная фраза)

— unknown (05/02/2015 13:39, исправлен 05/02/2015 13:41)   

Носители с долговременной сохранностью пока не очень распространены.

Проблема в том, что если вы используете этот метод многократно, то где-то в другом месте эта ваша уловка может всплыть и противник будет действовать по аналогии. Уловка должна быть каждый раз разной или считайте энтропию пароля^[link3] точно. В ходе обсуждений^[link4] каждый остался при своём в плане выбора методики запоминания, в соответствии со своими особенностями памяти.

— Гость (06/02/2015 00:04)   

В частности, это следует из того, что новая информация не может быть получена из ничего, см. неравенство обработки данных^[link5] (DPI). На эту тему статьи есть^[link6]:

The data processing inequality (DPI) is a fundamental feature of information theory.

DPI — хорошая теорема запрета (наподобие запрета вечных двигателей).

— Гость (06/02/2015 00:08)   
Если у вас есть кусок данных, как бы вы его ни меняли и не обрабатывали, вы не сможете увеличить количество информации, которое в нём содержится. Уменьшить сможете. Количество информации в случае пароля есть степень его случайности, а взятие хэша — способ обработки.

— Гость (06/02/2015 12:51)   
Уяснил для себя следующее.

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

В частном случае, хеш-преобразование источником энтропии не является, поэтому в идеальном результате энтропия исходного пароля теоретически может, всего-лишь, не понизиться.

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

Большое всем спасибо за помощь и терпение.

— unknown (06/02/2015 13:41, исправлен 06/02/2015 13:43)   

Есть немного надуманное и условное понятие «вычислительной энтропии». Иногда его используют при описании алгоритмов, замедляющих подбор ключей выведенных из паролей — Password Based Key Derivation Function^[link7].

Вот примерно что^[link8] сейчас на эту тему разрабатывают.

— ressa (06/02/2015 16:57)   

Вот^[link9] неплохой вариант для договременного хранения, своими руками. Дешево, просто и сердито. Металл поверх можно покрыть полимером.

— ressa (06/02/2015 17:53)   
unknown, спасибо, я в подобных технических вопросах ноль.
По личному опыту – сохранена первая моя флешка на 64Мб. О ее существовании забыл, нашел года два назад – работала.
Срок 10 лет – это много. Очень даже. Будто человека сажают в тюрьму. ну грубо говоря. При каких еще обстоятельствах подобный срок понадобится? Если что-то важное – можно смело на год. Раз в год обновлять носитель. И то, я бы на три года оставлял не заморачиваясь. Так как на ключах висит вот такая^[link11] подружка уже четвертый год. Пользуюсь регулярно.

— Гость (06/02/2015 18:30)   
Вот^[link12] и вот^[link13] ещё один относительно доступный способ долговременного хранения данных.

— Гость (08/02/2015 02:18)   

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

— Гость (09/02/2015 02:36)   

Можно и с другой стороны подойти к этому вопросу. Мы сейчас читаем информацию, которая изначально была записана на носители, которых уже наверняка не существует, да и считывающие устройства с них найти чтобы, надо облазить все музеи очень постараться. Т.е., тот код, который был написан в 70-ых, можно читать и сейчас. Он сохраняется не за счёт долговременности носителей, а за счёт их реплицируемости. По этому же пути идут фермы гугла, да и вообще серверные стойки корпораций, raid-массивы и т.д.: сломалось — заменяем, восстаналиваем из резерва, и всё это на лету. Если информация имеет хоть какую-то ценность, её будут так копировать до бесконечности. Более того, с учётом роста ёмкости носителей, чем старее информация, тем меньше она занимает в нормировании на типичную единицу ёмкости, и тем легче будет делать её копию. ☺

— Гость (10/02/2015 17:28)   

В частности, это следует из того, что новая информация не может быть получена из ничего, см. wwwнеравенство обработки данных (DPI). На эту тему wwwстатьи есть:

Во-первых, речь идет за энтропию, или вы таки будете отрицать эффективность конструкции sponge?

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

Этим утверждением вы отрицаете возможность получения новых знаний на основе уже имеющихся :)))))

— Гость (10/02/2015 17:51)   

Настоящая энтропия — это и есть информация.


Да, что-то в этом есть. Кажется, в каких-то серьёзных работах от Реннера и Co. этот вопрос обсуждался. Но нужно понимать, что это касается только полностью закрытой изолированной системы. Если мы примем за неё Вселенную, то так и будет.

c^[link15]an we trust ourselves, our freedom of choice, our free will?

— Гость (10/02/2015 18:17)   

Настоящая энтропия — это и есть информация.

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

это касается только полностью закрытой изолированной системы. Если мы примем за неё Вселенную, то так и будет.

Предлагаю в этом случае исходить из фактических данных.

— Гость (10/02/2015 18:33)   

Не выходит. Там энтропия не настоящая, а вычислительная.

— Гость (10/02/2015 18:39)   

Не выходит. Там энтропия не настоящая, а вычислительная.

Значит этот аргумент^[link16] здесь приводить не следует, поскольку в данном случае это не правомерно.

— Гость (11/02/2015 09:07)   

Всё тоньше. Если вы не придерживаетесь принципа security through obscurity и потому раскрываете методику генерации паролей, то всё так, DPI даёт вам ответ: невозможно. Если же вы всё же играете в безопасность через неясность, то можно спекулировать об увеличении стойкости, но все аргументы против такого подхода уже сказаны unknown'ом [1]^[link17], [2]^[link18]. Если быть более точным, то для второго способа нужно чётко формализовывать, что знает атакующий, что не знает, какая у него будет оптимальная стратегия по взлому и т.д. Если предположить, что это нагромождение предположений сколь-нибудь сносно моделирует реальность, то ответ ищется как оптимальная стратегия в рамках теории игр.

Понятно, что если есть возможность не играться в это полуиллюзорное и зыбкое увеличение безопасности, то это лучше. Здесь используются ровно те же аргументы, как и при подборе словарных паролей [3]^[link19], [4]^[link20], [5]^[link21]: противник составляет игровую стратегию как «перебор от наиболее часто встречающихся трюков при придумывании паролей к более редким», а защищающийся пытается придумать стратегию, которая позволит придумать пароль, который не будет учтён на ранних стадиях перебора атакующим. Каждый пытается перехитрить другого. Итоговые оценки стойкости получаются очень спекулятивными. Именно поэтому настоятельно рекомендуется не обманывать самого себя, а взять RNG, сгенерировать пароль заранее заданной стойоксти, а потом, при необходимости, перекодировать его в более удобно запоминаемый вид (стойкость при этом сохраняется).

— unknown (11/02/2015 09:27, исправлен 11/02/2015 09:29)   

Энтропия на выходе Sponge ограничена двумя параметрами: энтропией на входе и размером внутреннего состояния хэша (1600 бит в случае Keccak^[link23]). Т.е., больше 1600 бит энтропии на выходе не бывает в любом случае, а если на вход подали менее 1600 бит, то энтропия выхода будет равна энтропии входа. Всё остальное — вычислительная неразличимость от реальной энтропии. В любом случае, максимум, что потребуется противнику — это сбрутфорсить эти 1600 бит. А во многих сценариях и допущениях и меньше этого.

— Гость (11/02/2015 10:08)   

security through obscurity

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

1600 бит.

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

— Гость (11/02/2015 10:19)   

С бесконечным размером внутреннего состояния хэша? :-)


Системы стараются делать настолько открытыми, насколько это возможно. Метод генерации пароля также полностью раскрывается. Если вы начинаете ещё и его засекречивать, вы двигаетесь в сторону securty thorough obscurity, которая, как уже выше сказал unknown, не масштабируется [1]^[link24], [2]^[link25].

— unknown (11/02/2015 10:20, исправлен 11/02/2015 10:23)   

И у неё будет квадратичный рост памяти и количества вычислений в зависимости от размера входных данных? Даже если и (не) так, то энтропия выхода будет равна энтропии входа (или даже чуть меньше). Это будет просто экстрактор энтропии (или близкие ему конструкции), а не вычислитель её из ничего.

RO нельзя представить реально вычислимой функций, но некоторым хочется считать, что абстракция — это реальность на всех уровнях :-)

— Гость (11/02/2015 11:09)   

Это будет просто экстрактор энтропии (или близкие ему конструкции), а не вычислитель её из ничего.

Если это сделает перебор невыгодным (экономически, энергетически и т.д.) то цель достигнута.

[1], [2].

Ссылки хорошие, но если размер внутреннего состояния защищает ХФ от перебора, то этот подход не канает.
P.S. "защищает ХФ от перебора" = делает перебор невыгодным даже по множеству, много меньшему мощности полного перебора.

— unknown (11/02/2015 11:24)   
Тогда вам надо PBKDF, Scrypt, Lyra^[link8] и всё такое. Но это только добавляет несколько десятков бит фиктивной вычислительной энтропии к плохому паролю за счёт затруднения перебора.

— gegel (11/02/2015 11:41)   

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

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

— Гость (11/02/2015 12:00)   

Но, учитывая, что секретность любого алгоритма не

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

— unknown (11/02/2015 12:09, исправлен 11/02/2015 12:11)   

Пусть обычная схема: K = H(P) (1)

Пусть такая схема: K = H(H(H(P))) ║ 0x01 (2)

И что даёт (2) по сравнению с (1)?

— Гость (11/02/2015 12:23)   

И что даёт (2) по сравнению с (1)?

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

— Гость (11/02/2015 12:25)   
fxd
требует от атакующего совершить ряд дополнительных неочевидных телодвижений для вскрытия криптосхемы.

— SATtva (11/02/2015 12:25)   
Security through obscurity в полный рост.

— Гость (11/02/2015 12:28)   

Насколько я знаю, ничего он не добавляет. Все эти Lyra и прочие PBKDF затрудняют подбор пароля лишь по тому, что на проверку каждого пароля требуются дополнительные вычислительные ресурсы. Как детерминистичная функция вообще может менять энтропию?!


Да, но стойкость криптосхемы (в рамках того же RO) оценивается полагаясь на то, что пароль абсолютно случаен и абсолютно безопасен. У условного AES-128 есть 128 бит энтропии только при том условии, если пароль действительно и объективно (в смысле настоящей энтпропии, а не вычислительной) имеет хотя бы 128 бит случайности.


Опять начались прятки, вытаскивание самого из себя из болота, security through obscurity и прочее откровенное клухацкерство и фричество. Есть желание затруднить перебор — надо брать грамотно сконструированные KDF. Они не секретны от атакующего ни разу. А утаивать сам метод генерации исходного пароля — это именно что путь в никуда.

— unknown (11/02/2015 12:32)   

Так это и есть суть вычислительной энтропии. Если вам каждый пароль для проверки в переборе надо похэшировать четыре раза вместо одного — то вы добавили два бита, если 8 раз — то три, 16 — четыре и т.д. В этом смысле ничего и не добавляется, вычислительная энтропия — фикция (она не имеет никакого отношения к реальной энтропии), растёт только расход ресурсов на проверку (количество операций, память).

— Гость (11/02/2015 12:34)   
Напоминает знаменитые цитаты:

C^[link26]ontrary to a view in the I&C community, compression does not render data random, as can be seen from the case of votes, where the message space has very low entropy.

In the wiretap literature it is sometimes argued that the assumption of uniformly distributed messages is tenable because messages are compressed before transmission. But compression does not result in uniformly distributed messages. Compression is a deterministic, injective function and does not change the entropy.

Сжатие — тоже разновидность «повышения энтропии» и «рандомизации», как некоторые ошибочно думают.


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

— unknown (11/02/2015 12:40, исправлен 11/02/2015 12:42)   

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

— Гость (11/02/2015 13:02)   
Мне кажется, что с практической точки зрения можно получить некоторое сужение проблемы, если учесть, что взломщик фундаментально или практически ограничен.

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

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

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

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

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

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

— Гость (11/02/2015 13:12)   
Извините, во втором абзаце ошибка. Должно быть:

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

— Гость (11/02/2015 13:26)   

Словарное выражение само по себе не является чем-то стойким, это просто уловка. Ссылки на методики работы john были приведены. Вся мировая литература и словари всё равно дают меньше энтропии, чем нужно, а если ещё и выбор фразы из литературы будет делаться неслучайно, то тем более.

Нет смысла реализовывать у себя часть KDF в виде хэша. Всё хэшифрование уже есть в KDF. Попытка вынести часть KDF в юзерский функционал и засекретить от атакующего — security through obscurity. Перефразируя известные фразы unknown'а из срачей про каскады и перестраховочную криптографию, «если ваш пароль так плох, что требуется к нему городить костыли, то надо не переопределять KDF, засекречивая её части, а менять сам пароль на более стойкий». Примите себе за максиму, что нет возможности сделать чудо, когда в голове ничего держать не надо, а криптостойкость ровно та же.


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

— unknown (11/02/2015 13:54, исправлен 11/02/2015 13:58)   

Пусть множество всех известных (доступных для подбора) вам и вашему противнику паролей P имеет мощность 2ⁿ. Пусть пароль может быть равновероятно выбран в виде P или некоего преобразования f(P), где f — любая известная вам и противнику функция, не снижающая энтропию (хэширование, инвертирование, приписывание единицы). Применение или не применение этой функции даёт один дополнительный бит неопределённости (энтропии): 2ⁿ⁺¹.

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

— Гость (11/02/2015 14:17)   

Пусть множество всех известных (доступных для подбора) вам и вашему противнику паролей P имеет мощность 2n. Пусть пароль может быть равновероятно выбран в виде P или некоего преобразования f§, где f — любая известная вам и противнику функция, не снижающая энтропию (хэширование, инвертирование, приписывание единицы). Применение или не применение этой функции даёт один дополнительный бит неопределённости (энтропии): 2n+1.

тогда уж и ссылку на доказательство киньте :)

— SATtva (11/02/2015 14:20)   
Вам доказательство и привели в процитированном фрагменте.

— unknown (11/02/2015 14:25, исправлен 11/02/2015 14:31)   

А какое ещё нужно доказательство, если параметр неопределённости (энтропии) добавляется не во входные аргументы функции (пароль), а в саму функцию? Если это не доказательство, то демонстрация того, что постановка задачи некорректна для сделанных выводов о росте стойкости: истинная неопределённость (энтропия) какая есть на входе вычислительной функции, такая и есть на выходе. Добавлять её на вход в виде аргументов или запихивать в саму функцию (в виде порядка преобразований) — ничего не меняет. Просто первый вариант проще и корректнее для описания.

Или вам нужно доказательство того, что 2 • 2ⁿ = 2ⁿ⁺¹? Ну тогда почитайте что-нибудь из школьной алгебры, не помню за какой класс, но там это должно быть.

— Гость (11/02/2015 14:36)   

Между тем, добавка всего одного печатного символа к паролю добавляет^[link28] примерно log₂95 ≈ 6.56 бит энтропии.


Для каждого пароля есть два варианта: либо хэшифрование применяется, либо нет. Следовательно, количество всех вариантов теперь не P, а 2P. Если было изначально n бит энтропии в P, т.е. мы имели 2ⁿ=P, то теперь имеем 2P=2ⁿ⁺¹. Показатель двойки увеличился на единицу. Это и соответствует увеличению битовой стойкости на один.

Аналогично можно рассмотреть случай выбора одного из нескольких вариантов преобразований пароля. Чтобы получить тот же эффект, что и при добавлении одного дополнительного символа к паролю, нужно иметь возможность выбора одного из 2⁶ – 2⁷ вариантов преобразований. Так один символ, пожалуй, проще запомнить, чем 2⁷ типов хэширований?

— Гость (11/02/2015 14:42)   

Или вам нужно доказательство того, что 2 • 2n = 2n+1? Ну тогда почитайте что-нибудь из школьной алгебры, не помню за какой класс, но там это должно быть.

не факт, зависит от того, как мы определим операцию "•"

— unknown (11/02/2015 14:49)   
Всякие экзотические алгебры^[link29] мы здесь не рассматриваем.

— Гость (11/02/2015 14:51)   
Раз речь идёт о конвенциональной стойкости, построенной на стандартной арифметике, умножение всюду тоже придётся использовать конвенциональное.

— Гость (11/02/2015 15:37)   

Уважаемый Гость, я писал, разумеется, не в порядке спора. Отдаю себе полный отчет, что мое сообщение могло выглядеть нелепо. :-) Это, однако, не означает, что пропускаю чужие мысли, советы и подсказки мимо ушей. Снисхожденья просим. :-)

— Гость (11/02/2015 18:11)   

Я и unknown нашли, что ответить, но все же понимают, что ваш /comment87977^[link30] — чистейший троллинг.

— Гость (11/02/2015 18:25)   

Гость (11/02/2015 18:11)

spinore, тут вы промахнулись, однако. Я просто поддержал ТС-а, мне тоже интересна эта тема.

— Гость (12/02/2015 16:38)   

Нет. Это неверное продположение. Я – топикстартер, мои посты эти:

/comment87541^[link31]
/comment87604^[link32]

Потом тема получила продолжение, что и подтолкнуло меня на написание следующих

/comment87953^[link27]
/comment87955^[link33]
/comment87985^[link34]

Остальные "гостевые" посты не мои. Клянусь ушами. :-)

Повторюсь, что для себя я один раз и навсегда уяснил следующие краеугольные принципы (организации) криптографической защиты:

– мерой стойкости криптосистемы является качество энтропии в самом слабом звене (любая проблематика всегда сводится к этому принципу)
– нельзя получить энтропию из ничего
– противнику всегда известно все и у него всегда достаточно средств для атаки
– безопасность через неясность является явной точкой отказа в системе криптозащиты, причем вероятность отказа ненулевая

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

— unknown (12/02/2015 17:04, исправлен 12/02/2015 17:11)   

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

В общем, правильно.
Про энтропию — это вообще теория инфомации. Информационная энтропия^[link35] — это определения, которые дал ещё Клод Шеннон. Информационную энтропию нельзя получить из ничего — в смысле вычислениями, она предзадана на входе в функцию, систему, берётся из взаимодействия с реальным физическим миром.

Известно устройство системы, алгоритмы её работы, всё кроме ключа, пароля, секрета. Принцип Керкгоффса^[link36] про это всё.

Это тоже Керхгоффс. В современной интерпретации.

— Гость (12/02/2015 21:57)   
Когда-то я думал, что Керкгоффс и Кирхгоф — один и тот же человек ☺:
Типа одна и то же фамилия, просто транслитерирование на кириллицу разное. Судя по замечаниям в википедии, я не один такой.