пятница, 10 сентября 2010 г.

Политика управления персональными паролями, часть вторая. Краткий ликбез по парольной защите: устойчивость пароля.

Предыдущая часть:
Политика управления персональными паролями, часть первая. Определяем проблему.

-- Диктую... Вначале цифры. Семь. Четыре. Шесть. Ноль. Шесть. Два.
Четыре. Семь. Теперь буквы. W. H. O. Все прописные. d. s. Все строчные.
Снова цифры. Один. Три. Шесть. Восемь. Один. Строчная y. Прописная Z.
Символ доллара. Собака.
-- Которая в адресах? Или слово собака? -- деловито спрашивает Пат.
-- Значимые слова в шифрах используют только ламеры, -- говорю я. --
Знак, конечно. Теперь три открытые скобки, цифра восемь. И восклицательный знак.
(c) "Фальшивые зеркала", Лукьяненко С.
   Для начала, давайте разберемся с тем, какие же меры обеспечения безопасности собственных паролей доступны рядовому пользователю и каким образом пользователь может их применять. Таких мер всего три: обеспечение устойчивости паролей к взломам методом грубого (полного) перебора и перебора по словарю, посильное обеспечение безопасности каналов передачи и восстановления паролей и обеспечение безопасности мест хранения паролей. В этой заметке, мы рассмотрим первую из них...

    Привить паролю иммунитет к словарным атакам элементарно: достаточно не использовать в нем осмысленные слова из естественных языков, помня при этом, что слова "gfhjkm", "parol'", "par01'" и им подобные, мало чем отличаются от оригинала и также попадают под определение словарных, так как общепринятые и очевидные правила подобных преобразований уже давно учитываются атакующими при осуществлении словарных атак.

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

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

    Таким образом, чтобы обеспечить устойчивость пароля к атакам грубого перебора, мы должны найти компромисс между длиной пароля и мощностью алфавита, используемого при его построении. Но как оценить устойчивость полученного пароля? Еще в 1948 году, американский ученый по имени Клод Шеннон, основоположник теории информации, предложил рассчитывать так называемую эффективную длину пароля, основанную на оценке количества информационной энтропии в рассматриваемом сочетании символов из заданного алфавита и вычисляемую по формуле , где n - размер множества допустимых символов, а m - фактическая длина пароля. Иными словами, 64-битный пароль "password", построенный из 26-символьного алфавита (строчные английские буквы, ANSI-кодировка: 8 бит на символ) с точки зрения устойчивости эквивалентен 37-битному паролю, составленному путем равновероятных выборок из используемого алфавита. Своего рода КПД такого пароля составляет 37/64=~0,57. Если же мы удвоим исходный алфавит, просто изменив первую букву на заглавную, то получим уже 45 бит эффективной длины, т.е. КДП = ~0,7. Чем больше энтропии будет внесено в пароль, тем он будет устойчивее к атакам прямого перебора. Эффективную длину пароля также можно рассматривать как показатель степени двойки, определяющей максимальное количество операций прямого перебора, которые необходимо совершить для успешной атаки на пароль с такими характеристиками. То есть, для подбора пароля "Password" (а также любых других 8-символьных паролей, построенных из 52-символьного алфавита) атакующему будет необходимо перебрать не более 2^45=35184372088832 вариантов. Из чего следует, что увеличение энтропии пароля на один бит удваивает максимально-необходимое количество операций перебора.

    Существует несколько правил построения паролей, следуя которым можно добиться гарантированно высокой энтропии построить достаточно устойчивый пароль (см. UPD ниже):
  1. в качестве исходного алфавита должно использоваться максимально-доступное множество групп символов;
  2. в пароле должен присутствовать хотя бы один символ из каждой группы;
  3. символы, принадлежащие одной и той же группе, не должны встречаться в пароле на соседних позициях;
  4. количество символов, принадлежащих каждой из групп, должно быть одинаково;
  5. один и тот же символ не должен встречаться в пароле более одного раза;
    Оценить пароль на соответствие большинству из этих правил (а также еще нескольким, определяющим требования к длине пароля) можно, воспользовавшись приложением The Password Meter.

UPD: Как справедливо заметили в комментариях, точное следование данным правилам уменьшает энтропию пароля, позволяя атакующему оптимизировать атаку перебором в том случае, если ему будет достоверно известно об их использовании. Чтобы избежать этого, достаточно следовать любым трем из четырех последних правил, либо рассматривать их как граничные критерии, к которым стоит стремиться, но не стоит соблюдать неукоснительно. Либо, наконец, при построении пароля использовать равновероятную выборку из алфавита и забыть о правилах вообще :)

    Так каково же пороговое значение эффективной длины пароля, достаточное, чтобы сделать его устойчивым? К сожалению, однозначного ответа на этот вопрос не может быть из-за того, что скорость перебора паролей при проведении атаки, напрямую зависит от реализации парольной защиты, применяемой в конкретной информационной системе и вычислительных мощностей системы, на которой осуществляется перебор. Так, например, подбор пароля по его MD5-хэшу (алгоритм, до сих пор применяющийся на большинстве сайтов и веб-приложений средней руки, между прочим), на компьютере с Intel Core 2 Duo 6300, 1.86 GHz + NVIDIA GeForce 8600 GTS, 675 MHz, с распараллеливанием вычислений между обоими ядрами CPU и с использованием вычислительных возможностей видеокарты, осуществляется со средней скоростью 160 миллионов паролей в секунду. Это означает, что для взлома методом полного перебора паролей аналогичных нашему "Password" по их MD5-хэшу потребуется не более 61 часа. А вот, например, с зашифрованными RAR-архивами все несколько сложнее, в силу особенностей реализации механизма шифрования в этом формате: скорость перебора паролей (на железе, аналогичном приведенному в предыдущем примере) там колеблется от 40-50 паролей в секунду до 2-3 тысяч, в зависимости от длины пароля, размера архива и использования в архиве возможности шифрования имен файлов (если эта возможность используется, то скорость перебора приближается к максимально-возможной). Допуская, что атака на RAR-архив с зашифрованными именами файлов будет осуществляться со скоростью 3 тысячи вариантов в секунду, мы получаем 371 год, необходимый для перебора всех вариантов паролей, составленных аналогично "Password"...

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

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

    Однако, есть еще один способ усилить устойчивость пароля. Что если мы будем регулярно менять пароль в меньшие промежутки времени, чем требуется атакующему для атаки перебором? Ответ очевиден: атака на такой пароль будет бессмысленной. Соответственно, прикинув ожидаемые вычислительные мощности атакующего, мы можем определить промежуток времени, в течении которого пароль будет оставаться в безопасности, после чего мы изменим его на другой с аналогичной стойкостью, что и будем проделывать регулярно, не оставляя ни одного шанса возможному атакующему. Здесь есть одно "но": если мы ошибемся с оценкой вычислительной мощности атакующего, то у него есть все шансы успеть подобрать наш пароль до его замены. Поэтому модель атакующего необходимо брать "с запасом" и исходя из ее наиболее пессимистичного варианта. Есть также и второе "но": в случае с регулярно меняющимися паролями, нам не следует использовать в качестве нового какой-либо из старых паролей. В идеале - никогда. Причина тому проста: осуществляющий атаку перебором не имеет возможности отследить замену пароля, поэтому начав атаку, он будет продолжать ее до тех пор, пока перебор всех вариантов не завершится, либо пока он не достигнет желаемого результата. Если у атакующего на руках есть хэш нашего пароля или какая-либо еще информация, позволяющая ему оценить успешность очередной итерации подбора не осуществляя попытку входа в систему, то использовав старый пароль в качестве нового, мы сведем на нет все наши усилия по осложнению жизни атакующему. Потому что его атака снова станет актуальной в том случае, если искомая им комбинация еще не была рассчитана ранее.

    Итак, подытожим: пользователь имеет возможность, варьируя тремя характеристиками пароля, обеспечить его устойчивость к атакам перебора:
  1. сложностью;
  2. длиной;
  3. сроком актуальности;
на протяжении всей времени жизни пароля. Практические способы варьирования, мы также рассмотрим позднее, разрабатывая собственную политику.

UPD: на основе сказанного, несложно вывести формулу вероятности взлома пароля атакой прямого перебора:

, где:

V — количество паролей, которые атакующий может перебрать в единицу времени,
T — время актуальности пароля,
n — мощность алфавита,
m — длина пароля.


Продолжение следует... ;)

14 комментариев:


  1. 2. в пароле должен присутствовать хотя бы один символ из каждой группы;
    3. символы, принадлежащие одной и той же группе, не должны встречаться в пароле на соседних позициях;
    4. количество символов, принадлежащих каждой из групп, должно быть одинаково;
    5. один и тот же символ не должен встречаться в пароле более одного раза;

    А самое интересное, что вот эти советы (будучи известными злоумыщленнику) снижают энтропию пароля ;)

    ОтветитьУдалить
  2. Так, например, подбор пароля по его MD5-хэшу (алгоритм, до сих пор применяющийся на большинстве сайтов и веб-приложений средней руки, между прочим)

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

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

    ОтветитьУдалить
  3. 2doom: А самое интересное, что вот эти советы (будучи известными злоумыщленнику) снижают энтропию пароля ;)

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

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

    ОтветитьУдалить
  4. 2ilih: Для этого надо знать сам md5-хэш, а обычно его наличие означает, что полный доступ уже есть.

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

    ОтветитьУдалить
  5. Ну почему в теории?
    Вот конкретный случай:

    3. символы, принадлежащие одной и той же группе, не должны встречаться в пароле на соседних позициях;

    Это значит, что, если на позици i у нас представитель группы G, то в позиции i+1 вероятность появления символа из группы G равна 0 - т.е. уже не полная неопределенность, следовательно энтропия снижена (как известно, энтропия максимальна, когда появление символов в слове равновероятны на каждой позиции).

    Надо будет запомнить этот пример и добавить как задачку с конкретными числами по случаю.

    P.S. И вообще - вот ты тут распинаешься, а я тут играюсь с коммутатором одной фиромочки, где управление построено на широковещательных UDP пакетах, для аутентификации которых применяется пароль... передаваемый открытым текстом :)
    А я этот коммутатор на границу домашней сети планировал поставить :)

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

    P.S. А почему у тебя даже пользователям блоггера надо капчу вводить?

    ОтветитьУдалить
  7. 2doom: Ну почему в теории? Вот конкретный случай:

    Ок, согласен (синдром КСВ не дал сразу), правда с одной оговоркой. Ты говоришь о снижении энтропии по сравнению с равновероятной выборкой из алфавита. Но выборку, сделанную простым пользователем, за редким исключением можно назвать равновероятной. Вряд ли сильно ошибусь, если скажу, что большая часть таких пользователей строит пароли по шаблонам типа: "Someword9999" иногда вставляя куда-нибудь в середину тире или символы подчеркивания. Понятно, что эта информация, не будучи известна атакующему, не влияет на энтропию. Но даже безотносительно нее, количество итераций для подбора "Someword_9999" будет значительно меньше, чем для чего-то типа: "S!1o№2m3%e?4_", построенного в соответствии с приведенными правилами. Keepass, использующий для расчета энтропии куда более сложную эвристику нежели формула Шеннона (хотел рассказать о ней в последующих заметках), утверждает, что в первом случае энтропия составляет 64 бита, тогда как во-втором - 101 бит. Согласись, для паролей одинаковой длины и мощности алфавита - разница внушительная.

    Правила являются не более чем компромиссным решением, позволяющим легко построить выборку, близкую к равновероятной по своим свойствам. В связи с чем, предлагаю сойтись на введении 6-го правила, говорящего о том, что из четырех правил 2,3,4,5 должны быть применены любые три ;)

    Надо будет запомнить этот пример и добавить как задачку с конкретными числами по случаю.

    Конечно давай, это действительно неплохой пример.

    И вообще - вот ты тут распинаешься, а я тут играюсь с коммутатором одной фиромочки

    Ну, когда на стороне информационной системы в реализации ее парольной защиты допущены такие ошибки, все что может сделать пользователь - это отказаться от ее использования :)

    Надо было привести пример с билетами Kerberos

    Точно. Пасиб. Ну, думаю, что я еще успею :)

    А почему у тебя даже пользователям блоггера надо капчу вводить?

    Я так понимаю, что после всего написанного на RSDN и тут, ты мне не поверишь, если я скажу, что это оно само и было установлено по дефолту? :) В любом случае, пока убрал, там посмотрим.

    ОтветитьУдалить
  8. Кстати, не знаю видел ты или нет, но в Rainbow Series есть документ по управлению паролями, в котором приведен достаточно полный алгоритм определения минимальной длины пароля (учитывающий и вероятность угадывания и еще некоторые моменты): http://www.fas.org/irp/nsa/rainbow/std002.htm

    ОтветитьУдалить
  9. Я его определенно видел, но определенно не помнил где именно, спасиб :)

    ОтветитьУдалить
  10. Я его определенно видел, но определенно не помнил где именно, спасиб :)

    ОтветитьУдалить
  11. Кстати, не знаю видел ты или нет, но в Rainbow Series есть документ по управлению паролями, в котором приведен достаточно полный алгоритм определения минимальной длины пароля (учитывающий и вероятность угадывания и еще некоторые моменты): http://www.fas.org/irp/nsa/rainbow/std002.htm

    ОтветитьУдалить
  12. Ну почему в теории?
    Вот конкретный случай:

    3. символы, принадлежащие одной и той же группе, не должны встречаться в пароле на соседних позициях;

    Это значит, что, если на позици i у нас представитель группы G, то в позиции i+1 вероятность появления символа из группы G равна 0 - т.е. уже не полная неопределенность, следовательно энтропия снижена (как известно, энтропия максимальна, когда появление символов в слове равновероятны на каждой позиции).

    Надо будет запомнить этот пример и добавить как задачку с конкретными числами по случаю.

    P.S. И вообще - вот ты тут распинаешься, а я тут играюсь с коммутатором одной фиромочки, где управление построено на широковещательных UDP пакетах, для аутентификации которых применяется пароль... передаваемый открытым текстом :)
    А я этот коммутатор на границу домашней сети планировал поставить :)

    ОтветитьУдалить

  13. 2. в пароле должен присутствовать хотя бы один символ из каждой группы;
    3. символы, принадлежащие одной и той же группе, не должны встречаться в пароле на соседних позициях;
    4. количество символов, принадлежащих каждой из групп, должно быть одинаково;
    5. один и тот же символ не должен встречаться в пароле более одного раза;

    А самое интересное, что вот эти советы (будучи известными злоумыщленнику) снижают энтропию пароля ;)

    ОтветитьУдалить
  14. хорошее начало

    ОтветитьУдалить

Пожалуйста, будьте вежливы к автору и остальным посетителям этого блога