Надёжность алгоритмов усиления паролей

[epros]

Есть такие штуки: Key derivation functions (KDF). Они используются для генерации криптографических ключей. Смысл такой: Нормальный пользователь не в состоянии держать в голове достаточно надёжный ключ. Например, достаточно надёжен 256-ти битный ключ AES, но нет никакой надежды, что пользователь запомнит его. Нормальные пароли гораздо проще, но если их использовать в качестве ключей, то они элементарно находятся автоматическим подбором. Поэтому идея заключается в том, чтобы сделать функцию, отображающую пароль на ключ (т.е. KDF) саму по себе достаточно вычислительно сложной. Скажем, если отдельный ключ вычисляется за 1 секунду, а вариантов аргументов (т.е. паролей) существуют триллионы, то подобрать пароль становится вычислительно сложно.

Проблема в том, что нынче появились дешёвые высокоэффективные устройства как раз для решения подобных задач, ибо оные допускают практически неограниченное распараллеливание. Т.е. если имеется миллион специализированных «процессоров» на одном чипе, то задача подбора пароля сразу становится в миллион раз легче. Интересное решение предложили авторы алгоритм Scrypt: Они заложили в алгоритм не только вычислительную сложность, но и достаточно большой объём требуемой оперативной памяти (например, 32Mb). Т.е. алгоритм заполняет эту память псевдослучайной последовательностью, а потом многократно в псевдослучайном порядке обращается к различным ячейкам. Без существенного увеличения вычислительной сложности уменьшить объём требуемой оперативной памяти не получится. Поэтому если у криптоаналитика есть миллион процессоров, ему этого недостаточно — нужно иметь ещё и миллион раз по 32Mb оперативной памяти.

Так вот что мне бы хотелось обсудить:
Насколько всё это всё-таки надёжно? Скажем, у нас есть обычный пользователь, способный запомнить не слишком сложный пароль (допустим, триллион вариантов), с обычным ПК, на котором ключ должен генерироваться не дольше секунды. И есть угроза раскрытия зашифрованных этим пользователем данных криптоаналитиками какой-нибудь авторитетной государственной службы, которые, допустим, заинтересованы настолько, что не пожалеют месяца своего времени и современных вычислительных средств (в пределах разумного бюджета, т.е. всё же не суперкомпьютер). Может ли пользователь считать свои данные находящимися в безопасности, если он применил правильный алгоритм KDF?

[Gaudi]

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

[Xaositect]

epros в сообщении #754767 писал(а):

нужно иметь ещё и миллион раз по 32Mb оперативной памяти.

Не обязательно оперативной, можно массивы сгенерить и кинуть на SSD. Сейчас вроде есть 512Гб SSD за ~10000р. Время доступа, конечно, больше, но всего в несколько десятков раз.

epros в сообщении #754767 писал(а):

Может ли пользователь считать свои данные находящимися в безопасности, если он применил правильный алгоритм KDF?

Нет, триллион вариантов по нынешним меркам очень мало.

-- Ср авг 14, 2013 23:30:24 --

Можно использовать для этих целей вместо паролей автогенерированные предложения естественного языка из пары десятков слов. Их и запоминать легче.

[epros]

Xaositect в сообщении #754775 писал(а):

можно массивы сгенерить и кинуть на SSD. Сейчас вроде есть 512Гб SSD за ~10000р. Время доступа, конечно, больше, но всего в несколько десятков раз.

А как быть с параллельностью доступа? Насколько я понимаю, типичный диск 512Гб имеет единственный интерфейс доступа, т.е. разбить его на 16 тыс. блоков по 32Мб и обеспечить параллельный доступ к ним, наверное, технически непросто.

Xaositect в сообщении #754775 писал(а):

Можно использовать для этих целей вместо паролей автогенерированные предложения естественного языка из пары десятков слов. Их и запоминать легче.

Да, passphrases — это интересное решение. Но, опять же, они должны быть достаточно длинными. Во-первых, при этом используются только буквы, т.е. цифры и специальные символы включить в эту схему без существенного затруднения запоминаемости не получится. Во-вторых, нет легко запоминаемого механизма для перемешивания больших и маленьких букв. Значит будет использоваться только один тип букв. В английском алфавите их всего 26 штук. К тому же, многие из букв редко используются в качестве начала слов. Это еще уменьшает эффективное количество символов пароля (возможно, где-то до 16 — 18-ти). Т.е. даже пресловутый триллион вариантов достигается только при passphrase не короче 10-ти слов. 20 слов — уже, конечно, лучше. Но я не слишком уверен, что мне будет сильно проще заучить трактат из 20-ти слов, чем, скажем произвольную строку из 12-ти больших и малых букв, цифр и спецсимволов (что почти аналогично по количеству вариантов).

[Xaositect]

epros в сообщении #754886 писал(а):

А как быть с параллельностью доступа? Насколько я понимаю, типичный диск 512Гб имеет единственный интерфейс доступа, т.е. разбить его на 16 тыс. блоков по 32Мб и обеспечить параллельный доступ к ним, наверное, технически непросто.

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

epros в сообщении #754886 писал(а):

Да, passphrases — это интересное решение. Но, опять же, они должны быть достаточно длинными. Во-первых, при этом используются только буквы, т.е. цифры и специальные символы включить в эту схему без существенного затруднения запоминаемости не получится. Во-вторых, нет легко запоминаемого механизма для перемешивания больших и маленьких букв. Значит будет использоваться только один тип букв. В английском алфавите их всего 26 штук. К тому же, многие из букв редко используются в качестве начала слов. Это еще уменьшает эффективное количество символов пароля (возможно, где-то до 16 — 18-ти). Т.е. даже пресловутый триллион вариантов достигается только при passphrase не короче 10-ти слов. 20 слов — уже, конечно, лучше. Но я не слишком уверен, что мне будет сильно проще заучить трактат из 20-ти слов, чем, скажем произвольную строку из 12-ти больших и малых букв, цифр и спецсимволов (что почти аналогично по количеству вариантов).

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

[epros]

Xaositect в сообщении #754932 писал(а):

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

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

[Pavia]

Миллиона специализированных процессоров это конечно круто. Обычно не более 100-1000 ядер в чипе. И таких процессоров(чипов) штук 100-10 000.
В сутках 86 400 секунд.

Количество слов в языке не более 1 000 000, а их вариантов не более 20.
Таким образом собственно все пароли и ломаются. Обычный компьютер за сутки максимум месяц переберёт все варианты. А распределенная сеть обычно перебирает более сложные варианты или всё подряд.
Если генерировать осмысленную фразу, то сложность может и упасть ниже миллиона. Так что лучше генерировать просто набор из 3-5 случайных слов их и использовать.

[epros]

Pavia в сообщении #755121 писал(а):

Количество слов в языке не более 1 000 000, а их вариантов не более 20.
Таким образом собственно все пароли и ломаются. Обычный компьютер за сутки максимум месяц переберёт все варианты.

Что Вы имеете в виду? Мы здесь не рассматриваем пароли из единственного осмысленного слова. Разумеется, такой пароль был бы слишком слабым.

Pavia в сообщении #755121 писал(а):

Если генерировать осмысленную фразу, то сложность может и упасть ниже миллиона. Так что лучше генерировать просто набор из 3-5 случайных слов их и использовать.

Не нужны осмысленные фразы, достаточно просто запоминаемых. Xaositect предложил фразу из четырёх слов по шаблону «прилагательное существительное глагол существительное», что по его оценкам уже составит не менее триллиона вариантов. А можно ещё усилить, например, до шаблона двойной фразы: «прилагательное существительное глагол прилагательное существительное», а «прилагательное существительное глагол прилагательное существительное», что по тем же оценкам составит не менее $10^{30}$ вариантов. Например: «Печатный дирижабль излучает бедного интеграла, а истинный смех выравнивает редкого матроса». В принципе, не смотря на бессмысленность, получается достаточно запоминаемо. Хотя вся проблема в хорошей программе для генерации таких псевдофраз, потому что если брать из головы, то предсказуемость получится гораздо выше.

Но это не отменяет потребности в хорошей KDF.

[bin]

Сначала четыре замечания:

1)

Pavia в сообщении #755121 писал(а):

Количество слов в языке не более 1 000 000

О каком языке речь? Используя набор в 256 однобайтных символов, могу записать пароли: "Количество слов в языке не более","Koliczhestvo slov v yazike ne bolee", "The number of words in the language is not more than" и т.д. А можно использовать и украинскую мову и французский, немецкий и т.д. - раскладку клавиатуры только надо поменять, но 256 однобайтных символов в любом случае будет достаточно. А можно изобрести свой язык, например, "то" (добавление к каждому слогу $dx$ слога т$x$): "Котолитичетеството слотов в язытыкете нете ботолетее", можно перевернуть фразу наоборот и т.д. Т.о. оценить количество возможных паролей не очень просто.

2) Теперь про память. Прямой доступ к памяти (DMA) и виртуальная память наверняка снимут все затруднения c памятью для взломщиков. Физические характеристики устройства не важны.

3) И еще про вычислительные ресурсы. Хакерам, например, не доступны суперкомпы, но грид с успехом их заменяет.

4) Случайные и псевдослучайные последовательности - очень трудная проблема для многих криптоалгоритмов.

А теперь нужно уточнить задачу: 1) нужно ли учитывать возможность кражи пароля с помощью клавиатурного шпиона? 2) нужно ли учитывать возможность кражи ключа с помощью трояна?

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

А если говорить про спецслужбы, то недавний скандал (широко освещенный СМИ), с перехватом корреспонденции дип.представительств ряда европейских стран - достаточно демонстрирует возможности. Думаете, дипломаты не шифруют свои сообщения? Т.о. "обычный пользователь с обычным ПК" даже от хакеров мало защищен, гораздо меньше, чем банки и чем дипломаты, где работают не обычные пользователи, а лучшие специалисты по криптографии.

При этом с течением времени (т.е. с прогрессом) ситуация для обычного пользователя только ухудшается. Как я написал несколько лет назад на одном из блогов Интела: еще совсем недавно пароль в 6-8 символов казался достаточным, а теперь с появлением многоядерных процессоров и 16 символов представляется мало. У меня нет ничего против KDF, предполагаю, что этот метод может принести большую пользу, но грамотно использовать его обычному пользователю вряд ли возможно.

[rtfai]

Не советую иметь дело с одноразовыми ключами. Месяц назад выступал в суде по просьбе истца, неделю назад была еще одна просьба. Тупо, без всякого криптоанализа воруют.

Лучше всего ключ на сменном носителе и на чистом компьютере :)

[epros]

bin в сообщении #755223 писал(а):

О каком языке речь?

Речь была о любом естественном языке типа русского или английского. Наборы из 256 произвольных байт нормальный человек не запомнит.

bin в сообщении #755223 писал(а):

2) Теперь про память. Прямой доступ к памяти (DMA) и виртуальная память наверняка снимут все затруднения c памятью для взломщиков. Физические характеристики устройства не важны.

DMA не обеспечивает миллион параллельных каналов доступа к массиву памяти. Шина всё равно одна.

Я так думаю, что на сегодняшний день такого технического решения нет, поэтому алгоритм Scrypt можно считать условно надёжным. Но наверняка в скором времени появятся терабайтные массивы памяти, разбитые на блоки по 16Мб с параллельным доступом, и тогда Scrypt-у хана.

bin в сообщении #755223 писал(а):

3) И еще про вычислительные ресурсы. Хакерам, например, не доступны суперкомпы, но грид с успехом их заменяет.

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

bin в сообщении #755223 писал(а):

4) Случайные и псевдослучайные последовательности - очень трудная проблема для многих криптоалгоритмов.

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

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

bin в сообщении #755223 писал(а):

А теперь нужно уточнить задачу: 1) нужно ли учитывать возможность кражи пароля с помощью клавиатурного шпиона? 2) нужно ли учитывать возможность кражи ключа с помощью трояна?

1) нет 2) нет. Здесь рассматривается только защита от подбора пароля. Риски кражи — за пределами темы.

bin в сообщении #755223 писал(а):

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

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

rtfai в сообщении #755374 писал(а):

Лучше всего ключ на сменном носителе и на чистом компьютере :)

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

[bin]

epros в сообщении #755452 писал(а):

Наборы из 256 произвольных байт нормальный человек не запомнит.

Никто не говорит, что в пароле должны присутствовать все 256 символов. Речь о количестве допустимых. Допустим, что буквы русского и английского алфавита различаются (так оно и реализуется в большинстве стандартных кодировок): например, "a" англ. - $61_{16}$, а "а" русск. - $\mathrm{E}0_{16}$. Также должны различаться прописные и строчные буквы (русские и английские). Далее можно добавить греческий алфавит, алфавиты европейских языков с умлаутами и ангстремами, цифры, спец. символы (запятая, амперсанд и т.д.). Т.о. получаем кодировку, где любое значение от $0$ до $255$ имеет смысл для пользователя. Т.о. пароль "площадь круга <>$\pi r^{2.718281828459045}$" не будет равен паролю "ploщadь kryga <>$\pi r^{2.718281828459045}$". И взломщику придется перебирать все значения от $0$ до $255$ для каждого байта. (Запомнить число $e$ до 15-го знака нормальному человеку не трудно, если помнить год рождения Л.Н.Толстого )

[epros]

bin в сообщении #755498 писал(а):

"ploщadь kryga <>$\pi r^{2.718281828459045}$".

Нормальный человек такого ни за что не запомнит.

[bin]

epros в сообщении #755452 писал(а):

DMA не обеспечивает миллион параллельных каналов доступа к массиву памяти. Шина всё равно одна.

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

epros в сообщении #755452 писал(а):

Или Вы имели в виду, что будут сложности при автоматическом генерировании достаточно случайной passphrase? Тут я согласен.

Да.

epros в сообщении #755452 писал(а):

Обычному пользователю не составит труда использовать готовый софт.

Труда не составит, как и не составит поставить бронированную дверь на входе в свое жилище. Но если это жилище - летний дачный домик из тонкого теса, а на окнах нет решеток, то стальная дверь не защитит. То, что "Риски кражи — за пределами темы", выводит разговор за пределы практики, делает его чисто теоретическим. Широко известно, например, что базовые домашние дистрибутивы "виндоуз" содержат не самые плохие средства защиты, но большинство пользователей ими не пользуются. То же большинство любит пароли "123456", "qwerty" и т.д.(см. в инете списки любимых паролей). Я хочу сказать, что основная проблема - это грамотность конечного пользователя.

epros в сообщении #755452 писал(а):

Ключ на любом носителе (хоть на сменном, хоть на бумажном) можете автоматически считать уже переданным в руки противникам.

Тут, похоже, путаница в терминах: в условиях (в первом посте) говорилось:

epros в сообщении #754767 писал(а):

Они используются для генерации криптографических ключей. Смысл такой: Нормальный пользователь не в состоянии держать в голове достаточно надёжный ключ.

Я так понял, что длинный надежный пароль(названый ключем) получают из короткого "ключа"?

-- Сб авг 17, 2013 16:08:01 --

epros в сообщении #755511 писал(а):

bin в сообщении #755498 писал(а):

"ploщadь kryga <>$\pi r^{2.718281828459045}$".

Нормальный человек такого ни за что не запомнит.

Сколько исторических дат, сколько формул и сколько десятизначных телефонных номеров помнит средний нормальный человек? Сколько цифр числа $e$ он помнит? А такой пароль запомнит: "ploщadь kryga <>$\pi r^e$"? А такой: "ploщadь kryga $=\pi r^2$"?

-- Сб авг 17, 2013 16:58:05 --

rtfai в сообщении #755374 писал(а):

Не советую иметь дело с одноразовыми ключами. Месяц назад выступал в суде по просьбе истца, неделю назад была еще одна просьба. Тупо, без всякого криптоанализа воруют.

Лучше всего ключ на сменном носителе и на чистом компьютере :)

ИМХО два случая - недостаточная статистика для такого совета. Но скажите, пожалуйста: а суд хоть один раз признал иск? Признал, что система не обладала достаточной защитой, а пользователь соблюдал все правила безопасности, предписанные ему банком? И второе, я не очень понимаю, чем поможет вломщику кража пароля, который приходит по SMS на телефон клиента и имеет срок действия 5 минут? Или у клиента украли телефон? Тогда он должен был блокировать счет. Для входа в систему обычно нужен и неодноразовый пароль, известный только пользователю, как его смогли украсть? И как очистить компьютер? Каждый раз форматировать диск и ставить ОС заново?

[Xaositect]

bin в сообщении #755516 писал(а):

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

Я не знаю насчет среднего нормального человека, лично я помню 4 исторические даты и 1 телефонный номер.

bin в сообщении #755516 писал(а):

Каждый раз форматировать диск и ставить ОС заново?

Последнее время все чаще вижу советы использовать интернет-банк только загружаясь с Read-only носителя. В качестве компромисса - загружать виртуальную машину с физического read-only носителя.