«Сложный пароль» в расшифровке не нуждается

:

Проскочил тут топик про «сложные» пароли. К сожалению, смотрю, многие серьезно восприняли этот «метод»…

Использование карточек шифрования не является надежным методом! Как правильно заметили в комментариях там — «это в войну наши деды использовали»… Но использовали более совершенные методы.

Приведенный в той статье метод использовать НЕЛЬЗЯ ни в коем случае(!), пароли по этому методу полностью расшифровываемые, Вы просто отдадите их злоумышленникам на блюдечке! И сейчас я это докажу…

Сложность и параметры

Всего существовать по такому методу может 36 таблиц, что по сложности равно паролю из одной буквы или цифры. Отличия таблиц только в одном параметре: смещение влево на [0-35] — число столбцов, равное промежутку «a-z0-9».

Можете проверить: таблица один — это z = (i+j-1) % 36, вторая — это z=(i+j+9) % 36, где i и j принимают значения: «a»=0, «b»=1, «c»=2,… Проверьте для любых остальных значений — отличие только в одной константе, даже несмотря на то, что по строке вторая таблица начинается с «s» (что вообще с т.з. математики не имело смысла).

первая:
a + b + -1 = a  (0 + 1 + -1 = 0)
a + c + -1 = b  (0 + 2 + -1 = 1)
b + a + -1 = a  (1 + 0 + -1 = 0)

вторая:
a + j + 9 = s  (0 + 9 + 9 = 18)
a + k + 9 = t  (0 + 10 + 9 = 19)
b + i + 9 = s  (1 + 8 + 9 = 18)

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
 a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
 s  t  u  v  w  x  y  z  0  1  2  3  4  5  6  7  8  9

Следовательно, зная зашифрованный пароль и название ресурса — у нас остается всего 36 исходных паролей.

Финальный пример из оригинального текста (про него и ниже):

Кстати, вот сразу и минус виден — пользоваться табличками людям сложно, ошибки — неизбежны. Это зашифрованный автором той статьи пароль. В нем ошибка — «a-a» на второй позиции — это «9» по первой табличке, а не «b».

Расшифровываем (правильно) зашифрованный пароль…
вот часть из 36 паролей (соответствующие 36 разным смещениям таблицы и названию — «habrahabr»):
+5 j4mmqil7j
+4 k5nnrjm8k
+3 l6ooskn9l
+2 m7pptloam
+1 n8qqumpbn
+0 o9rrvnqco
-1 passwordp
-2 qbttxpseq
-3 rcuuyqtfr
-4 sdvvzrugs
-5 teww0svht
-1 — это и есть искомая константа смещения таблицы.

Да, это реальная «расшифровка», да, программу написал… на конце «p» потому что повтор пароля начинается.

Заметьте, что нам нужна только одна буква из пароля и та же одна — из названия сайта для получения одной переменной (смещения).

Маленькие буквы в «зашифрованном» пароле сдадут какие буквы будут являться гласными в названии сайта (снижение криптостойкости).

Так вот из вышесказанного, если мы не знаем названия сайта, но знаем где там гласная (а она будет там, где в зашифрованном пароле маленькие буквы), то у нас получается (по одной любой букве) = 36 (табличек) * 6 (гласных = a,e,i,o,u,y) — 216 паролей ( не зная названия сайта!). Совсем немного, но в реальности см. ниже (" В реальности") — будет скорее всего только один.

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

Добивка несколько усложняет задачу, но не в приведенном примере. Поскольку название ресурса длиннее, чем пароль, то получается расшифровав короткий пароль (зная зашифрованный пароль и название ресурса), который пойдет дальше по циклу — мы восстановим легко и добивку (мы будем знать верхнюю строку и нижнюю строку — среднюю мы восстановим по той же таблице… тут, кроме пары «символов» на позициях 4,8,16 (решетки, собачки), о ней — ниже).

В худшем (но не реальном) случае злоумышленнику нужно будет без спешки перебрать 36 паролей на другой сайт, чтобы войти.

В реальности: Из 36 паролей наверняка только один будет выглядеть как слово(!), которое вы запоминали, так что в реальности даже перебора не потребуется. Так что пароль будет известен точно.

Замена на символы


Отступление про «символы». Автор предложил заменять буквы полученного пароля на позициях 4,8,16 — на символы по табличке.

Знаки препинания добавляли бы сложности, если бы не еще одна уязвимость метода — цикличность повторения пароля. Автор сдвинул знаки препинания относительно латиницы. Ну что ж — это плюс, да, это еще один параметр сложности, но учитывая что мы точно знаем что меняются 4,8 и 16 символы — то мы можем (по длине названия сайта «habrahabr») расшифровать слово «pas*wor*p» в первой табличке (что под "*" мы не знаем пока что).

Теперь хитрость в том, что на (4+8) = 12 позиции та же буква, что и на «4» (пароль-то по кругу идет — это обе буквы «s» в слове «pas s(4)wordpas s(12)word»), но на 12 месте пунктуация не использовалась!

Следовательно мы можем расшифровать 12 букву и тут же узнаем 4ую букву.

Зная 4 зашифрованную букву и соответвующую ей пунктуацию — мы линейно получили смещение пунктуации. Из этого смещения тут же узнаем 8ую букву и как бонус — 16ую (которая та же). FAIL!

Правда если бы автор зашифровал 12ую букву, а пароль был бы 7-значным — мы бы все равно ее расшифровали (повторение буквы было бы на 4+7=13ом месте).

Если будет «добивка» — это будет портить картину, но не сильно, опять же — большая часть добивки будет расшифрована (мы уже будем знать полностью или почти полностью верхнюю строку и полностью — нижнюю — из нее восстановится средняя, кроме возможно(!) 1-2 букв закрытых пунктуацией, но тут уже перебор спасет — еще *36 вариантов — немного (и это редкий будет случай, чтобы удачно пунктуация закрыла буквы, что их не восстановить из повторяющегося пароля).

Вариант еще хуже


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

Грубо говоря как система уравнений

x + Y1 + t = Z1,
x + Y2 + t = Z2,

где x = исходный пароль,
Y1,Y2 = название ресурсов (известно),
t — смещение таблицы,
Z1,Z2 = зашифрованный пароль(известно).

Два уравнения, две неизвестных — система линейна и имеет одно решение относительно x и t.

На самом деле достаточно одной буквы из обоих паролей и той же буквы названий сайтов. (Неизвестная-то величина только одна — смещение таблицы влево)

Здесь даже перебирать ничего не надо — пароль будет известен точно.

Вывод


Приведенный в оригинальной статье алгоритм шифрования аналогичен буквенно-цифровому паролю из 1(одного!) символа (log3636 = 1).

В случае если известны шифрованные пароли от двух сайтов — не является шифрованием вообще.

Можно ли усложнить


Даже если Вы усилите алгоритм тем, что будете использовать русские буквы и символы (которые смещаются независимо), даже если Вы добавите сдвиг таблицы не только по горизонтали, но и по вертикали, и даже отражения по горизонтали и вертикали, то получите: 36*36*36*36*36*2*2 = 240 млн таблиц… Выглядит страшно?

На самом деле это аналогично простому буквенно-цифровому паролю примерно из 5 букв. Что едва ли можно считать «надежным» или «сложным» (27 бит шифрования).

Сильное шифрование — это 128 бит, что примерно в 1400000000000000000000000000000 раз должно иметь больше вариантов, чем «усложненные» 240 млн. ( точно?) Это эквивалентно буквенно-цифровому паролю из 25 букв. (log 36(2 128) = 24.75)

Единственный способ, которым можно это действительно «усилить» — это если:

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

Однако, даже эта табличка не выдержит серьезной атаки при длительном использовании (как и все «таблички»). Еще раз: использование карточек шифрования не является надежным методом шифрования!

md5('site+key')


Многие посоветовали такой метод. Он неплохой, но его можно улучшить.

На самом деле, при наличии достаточных мощностей и объемов памяти для RainbowTables есть шанс, что найдется ключик. (ма-а-а-а-а-а-а-аленький, но есть — всего 103 миллиарда паролей в секунду может один компьютер перебирать — так что, например, «password»+«habr» за 10 дней расшифровать можно и на домашнем компе)

Лучше — делать раунды шифрования, проще говоря — возьмите site+key и зашифруйте его 6000 раз прямо вот md5(md5(md5(… так 6000 раз......md5('site+key')....). Это не остановит атакующего, но серьезно замедлит, настолько чтобы атака стала непрактичной. Почитайте (на английском) что KeePass про раунды пишет — очень объяснит почему я так говорю.

# Псевдокод:
k = key + site
for 0..6000 {
   k = md5(k)
}
print k

А это уже расшифровывать 150 лет, против 10 дней для обычного md5(site+key). Но даже один раз — это довольно хороший метод.

Завершение


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

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

А лучший способ хранения паролей — это, все же — менеджер паролей, например KeePass и подобные.


Йои Хаджи,
вид с Хабра