Лабораторная работа №1 «Исследование математических методов анализа стойкости парольных систем»

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ

Дисциплина «Информационная безопасность и защита информации»

для студентов направления подготовки «Экономическая безопасность»

Лабораторная работа №1

«Исследование математических методов анализа стойкости парольных систем»

Обсуждено на заседании кафедры

Протокол №___ от «  »________2016г.

Ставрополь

2016

УЧЕБНЫЕ  И  ВОСПИТАТЕЛЬНЫЕ  ЦЕЛИ

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

УЧЕБНО-МАТЕРИАЛЬНОЕ  ОБЕСПЕЧЕНИЕ

Учебное пособие, ПЭВМ.

РАСПРЕДЕЛЕНИЕ ВРЕМЕНИ ЗАНЯТИЯ 

Время: 2 часа (90 мин)

Вступительная часть – 5 мин. Принципы использования математических методов при анализе стойкости парольных систем – 5 мин. Применение формул комбинаторики для анализа стойкости парольных систем – 10 мин. Изучение обобщенного алгоритма подбора пароля – 5 мин. Решение задач по анализу стойкости парольных систем – 45 мин. Ответы на контрольные вопросы – 10 мин.

СОДЕРЖАНИЕ ЗАНЯТИЯ

Вступительная часть

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

Вопрос 1. Принципы использования математических методов при анализе стойкости парольных систем

Цель практического занятия – исследование математических методов определения стойкости парольной системы.

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

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

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

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

Вопрос 2. Применение формул комбинаторики для анализа стойкости парольных систем

Перестановки без повторений

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

Определение. Всякое упорядоченное n-элементное множество называется перестановкой из n элементов.

Теорема. Число всех перестановок из n элементов равно произведению последовательных натуральных чисел от 1 до n включительно, то есть P=1·2·3·…·n=n!

Размещения без повторений

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

Имеется множество, состоящее из n элементов. Сколько можно составить упорядоченных подмножеств, содержащих k его элементов?

Для решения этой задачи необходимо узнать число различных размещений из n элементов по k элементов.

Определение. Всякое упорядоченное k-элементное подмножество n­элементного множества при kn называется размещением из n элементов по k. 

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

Число таких размещений из n элементов по k элементов обозначают символом .

Теорема. Число различных размещений из n элементов по k равно произведению k последовательных натуральных чисел, наибольшим из которых является n, то есть

= n·(n-1)·(n-2)·…·(n-k+1) или  =.

Сочетания без повторений

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

Определение. Всякое k-элементное подмножество n-элементного множества при kn называется сочетанием из n элементов по k.

Другими словами, сочетания из n элементов по k в каждом называются такие соединения, из которых каждое содержит k элементов, взятых из числа данных n элементов, и которые отличаются друг от друга по крайней мере одним элементом. Порядок элементов в сочетании значения не имеет.

Число различных сочетаний из n элементов по k обозначаются символом .

Теорема. Число сочетаний из n элементов по k определяется по формуле =.

Перестановки с повторениями

Пусть б – кортеж длины n, составленный из элементов m-множества X. Перенумеруем элементы множества X: X={x,x,…,x}. Тогда каждому числу k, где 1km, соответствует число , показывающее сколько раз элемент встречается среди компонент кортежа б. Выписывая по порядку эти числа, получаем новый кортеж , который и называют составом кортежа б. Два кортежа, имеющие один и тот же состав, могут отличаться друг от друга порядком компонент. Их называют перестановками с повторениями данного состава.

Определение. Перестановками с повторениями из элементов a, b,…,r, в которой эти элементы повторяются соответственно раз, называется кортеж длины , среди компонент которого a встречается раз, b – раз и так далее, r – раз.

Обозначим число перестановок с повторениями символом.

Теорема. Число различных перестановок с повторениями из элементов a, b,…,r, в которых эти элементы повторяются соответственно раз, определяется по формуле .

Размещения с повторениями

Пусть имеем множество, состоящее из n элементов любой природы. Кортеж длины k, составленный из n элементов этого множества, называется размещением с повторениями. Здесь необязательно .

Определение. Кортеж длины k, составленный из n-элементного множества, называется размещением с повторениями из n элементов по k.

Число всевозможных размещением с повторениями из n элементов по k обозначают символом .

Теорема. Число различных размещений с повторениями из n элементов по k определяется по формуле .

Сочетания с повторениями

Имеются элементы n различных типов. Сколько совокупностей, содержащих по k элементов каждая, можно составить из них, если не принимать во внимание порядок расположения элементов в совокупности?

Задачи такого типа называют задачами на сочетания с повторениями.

Определение. Сочетанием с повторениями из данных n различных типов элементов по k элементов называется всякая совокупность, содержащая k элементов, каждый из которых  является одним из элементов указанных типов.

Как видно из определения, сочетания с повторениями являются неупорядоченными множествами, а различные сочетания отличаются друг от друга входящими в них элементами, причем каждый элемент может входить в сочетание несколько раз. Для сочетаний с повторениями возможен случай, когда  n < k.

  Число различных сочетаний с повторениями из n элементов по k будем обозначать символом  .

Теорема. Число различных сочетаний с повторениями из n типов элементов по k элементов определяется по формуле .

Вопрос 3. Изучение обобщенного алгоритма подбора пароля

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

Будем использовать следующие условные обозначения:

M – множество символов алфавита, используемого при переборе;

m = |M| - мощность алфавита;

t1 – время, затрачиваемое на генерирование одного хэш-значения;

t2 – время сравнения двух хэш-значений;

n – число символов пароля.

В общем виде алгоритм подбора пароля выглядит следующим образом:

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

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

Приведем основные производные комбинаторные формулы применительно к задаче анализа стойкости парольной системы:

Формула определения общего числа парольных комбинаций

если известна длина пароля n:

если известно, что длина пароля от n1 до n2 символов:

если известны l символов пароля и известны их места:

       2. Формула определения времени перебора:

Вопрос 4.  Решение задач по анализу стойкости парольных систем

Задания для самостоятельного решения:

Задача 1.

Определить время подбора 5 паролей, если известно, что длина каждого из них не превосходит n2 символов, пароли набираются на алфавитно-цифровой клавиатуре (без использования «Shift») (учесть возможность сверки всех 5 паролей для одного хэш-значения) (параметры n2,t1,t2 см. в приложении).

Задача 2.

Рассчитать вероятность успешной гибридной атаки по n-символьному словарю с использованием возможности замены 2 символов слева и справа, если длина пароля n символов, а в словаре H слов, используется m=26. (параметры n, H см. в приложении).

Задача 3.

Определить формулу для расчета общего числа парольных комбинаций, если известно, что в пароле от n1 до n2 символов, а также известно, что из m символов алфавита M={M1,M2,..Mm} символы {M1,M2..Mk} встречаются в пароле точно.

Задача 4.

Найти минимальную длину пароля n, при которой пароль не будет взломан в течение 1 года (при постоянном переборе) при количестве символов алфавита m, и скорости перебора 500000 пар/сек. (параметр m см. в приложении).

Задача 5.

Определить минимальную мощность множества символов алфавита m, при котором пароль длиной n не будет взломан в течение 3 мес. (параметр n см. в приложении).

Задача 6.

Определить время подбора пароля, если известно, что его длина не превосходит n2 символов, пароль набираются на алфавитно-цифровой клавиатуре (с использованием Shift), а также известно, что в пароле точно есть символы «а», «з», «р». (параметры n2, t1, t2 см. в приложении).

Задача 7.

Определить формулу для расчета общего числа парольных комбинаций, если известно, что в пароле от n1 до n2 символов, а также известно, что из  m символов алфавита M={M1,M2,..Mm} символы {M1,M2..Mk} встречаются в пароле точно, а символы  {Mk+1,Mk+2..Mk+r} не встречаются точно.

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

Контрольные вопросы

С какой целью производится анализ стойкости парольной системы? Какие методы используются при анализе стойкости парольной системы? Какие комбинаторные объекты используются при полном переборе? Какие параметры стойкости можно считать приемлемыми? Опишите и поясните основные шаги обобщенного алгоритма подбора паролей.

ПРИЛОЖЕНИЕ

Вар.	Задача 1	Задача 2	Зад. 4	Зад. 5	Зад. 6
n2	t1	t2	n	H	M	n	n2	t1	t2
1	10	1,0E-06	5,4E-07	10	11727	36	6	7	2,8E-07	1,2E-07
2	9	2,5E-06	7,3E-07	7	11680	38	13	8	7,2E-07	8,9E-07
3	8	2,2E-06	8,3E-07	9	12642	30	8	9	6,0E-07	8,2E-07
4	7	1,3E-06	9,7E-07	6	4749	53	7	10	2,8E-06	4,6E-07
5	9	1,3E-06	5,3E-07	8	3049	51	6	8	2,5E-06	2,2E-07
6	8	2,7E-06	4,4E-07	9	5669	46	12	8	8,2E-07	5,6E-07
7	9	5,9E-07	3,2E-07	6	15349	39	13	9	2,2E-06	6,6E-07
8	8	1,6E-06	8,2E-07	6	11427	32	13	9	3,3E-06	2,7E-07
9	7	2,8E-06	4,5E-07	10	8745	42	7	10	2,9E-06	6,6E-07
10	10	7,0E-07	8,2E-07	8	11151	53	12	6	1,8E-07	2,1E-07
11	9	1,6E-06	7,3E-07	7	18665	42	11	5	5,1E-07	1,0E-06
12	8	1,7E-06	2,3E-07	8	14245	37	7	8	1,3E-06	3,3E-07
13	6	2,1E-06	8,1E-07	5	5309	53	8	8	6,0E-08	8,4E-07
14	7	1,9E-06	1,1E-07	7	1498	38	12	9	1,5E-06	3,6E-07
15	7	1,1E-06	3,7E-07	9	18215	37	7	6	9,0E-07	7,0E-07
16	9	1,2E-06	1,3E-07	8	13991	50	8	8	1,6E-06	2,3E-07
17	7	7,1E-07	3,4E-08	8	10877	34	12	6	1,1E-06	5,3E-07
18	7	1,3E-06	3,1E-07	7	11115	36	8	6	1,3E-06	6,9E-09
19	6	3,7E-07	4,4E-07	5	4307	32	11	9	1,9E-06	3,6E-07
20	6	3,1E-06	9,5E-09	10	18900	50	10	7	2,4E-06	7,8E-07
21	6	2,3E-06	5,0E-07	5	5783	41	12	9	3,2E-06	1,9E-07
22	8	2,9E-06	4,7E-07	8	18656	31	7	6	1,8E-06	8,2E-07
23	5	2,2E-06	7,4E-07	9	7414	33	11	7	2,3E-07	3,3E-07
24	8	2,3E-06	4,6E-07	6	17754	54	6	6	9,4E-07	8,4E-07
25	7	1,8E-06	2,4E-07	5	4075	46	10	5	7,1E-07	3,6E-08
26	5	1,2E-06	3,7E-07	8	7979	30	13	8	7,6E-07	7,1E-07
27	7	1,7E-07	4,2E-07	8	3701	31	13	9	3,2E-06	4,0E-07
28	7	4,3E-07	2,6E-07	5	10550	47	8	9	1,1E-06	6,6E-07
29	9	2,6E-06	6,1E-07	8	11010	46	11	7	2,3E-06	9,1E-07
30	8	8,3E-07	2,1E-07	6	15432	37	7	10	1,9E-06	5,1E-07
31	7	1,6E-06	7,4E-07	5	17997	34	8	6	1,9E-06	9,2E-07