22 August 2018

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

Information SecurityAlgorithmsMathematics
Translation
Original author: Somdev Sangwan

В Индии есть местный аналог нашего ИНН — «адхар». К нему прикручена электронная система «еАдхар». В «еАдхаре» каждое письмо блокируется паролем. И всё бы хорошо, но пароль составляется по простому шаблону: первые четыре буквы имени капсом плюс год рождения.


Четыре заглавные буквы и четыре цифры. Из них можно составить 2 821 109 907 456 комбинаций. Если проверять тысячу комбинаций в секунду, на один пароль уйдёт лет девяносто.


Долговато. Может ускоримся в пару (миллиардов) раз?


92 года → 52 дня. Группируем


С тремя триллионами комбинаций мы чуть-чуть хватили лишнего. Всё-таки шаблон известен:


([A-Z][A-Z][A-Z][A-Z])  ([0–9][0–9][0–9][0–9])
  (4 заглавные буквы)         (4 цифры)
      (Группа 1)              (Группа 2)

Если учесть этот шаблон, то строки вроде S2N65GE1 можно сразу отбросить. Сколько тогда получится комбинаций?


Первая группа — четыре буквенных символа. 26 вариантов, 4 позиции, получаем:


$26^4= 456 976$


4 позиции по 10 цифр, аналогично:


$10^4= 10 000$


Из этого получаем суммарное число комбинаций:


$456976 × 10000= 4569760000$


Прикинем, насколько быстрее теперь будет брутфорс. Снова исходим из 1000 попыток в секунду:


$4569760000 / 1000 = 4569760$


Или 52 дня, 21 час, 22 минуты и 40 секунд. Вместо 92 лет. Неплохо. Но всё равно долго. Что ещё можно сделать? То же самое — уменьшить количество комбинаций.


52 дня → 12 часов. Включаем здравый смысл


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


Подбирать пароли для родившихся в 1642 или 2594 смысла нет. Так что диапазон комбинаций можно смело уменьшить с 0000–9999 до 1918–2018. Так мы охватим плюс-минус всех ныне живущих в возрасте от 0 до 100 лет. Благодаря этому сокращается и число комбинаций, и время соответственно:


$456976 × 100 = 45 697 600$


$45697600 / 1000 = 45697.6$


Или 12 часов, 41 минута и 37 секунд.


12 часов → 2 минуты. Жертвуем точностью


12 часов — это классно, но… We need to go deeper.


Сейчас у нас есть 45 миллионов комбинаций, которые точно покрывают всех пользователей «еАдхара». Но что если пожертвовать их малой долей ради прироста скорости?


Цифровые комбинации мы довели до совершенства. С буквами сделаем нечто подобное. Логика проста: нет года рождения 9999, и точно так же нет индийского имени c «AAAA» в начале. Но как определить все подходящие комбинации?


Python Photon


Я собрал индийские имена с сайта-каталога, в этом мне очень помог Photon. В итоге получилось 3 283 уникальных имени. Осталось обрезать первые четыре буквы и убрать дубликаты:


grep -oP ”^\w{4}” custom.txt | sort | uniq | dd conv=ucase

Grep, sort, uniq, dd


Получилось 1 598 префиксов! Дубликатов оказалось довольно много, потому что первые четыре буквы в таких именах как «Sanjeev» и «Sanjit» — одинаковые.


1 598 префиксов — маловато для полуторамиллиардного населения? Согласен. Но не забывайте, что это именно префиксы, а не имена. Я выложил получившийся список на Гист. На самом деле их должно быть больше. Можно заморочиться, собрать 10 000 имён с других сайтов и получить 3 000 уникальных префиксов, но у меня не было на это времени. Так что будем отталкиваться от 1 598.

Подсчитаем, сколько времени нужно теперь:


$1598 × 100 = 159800$


$159800 / 1000 = 159.8$


Или 2 минуты и 39.8 секунды.


2 минуты → 2 секунды. Википедия в помощь


2 минуты 40 секунд — это время, которое понадобится на перебор всех комбинаций. А что если одиннадцатая комбинация правильная? Или последняя? Или первая?


Сейчас перечень комбинаций отсортирован по алфавиту. Но это бессмысленно — кто сказал, что имена на «А» встречаются чаще, чем на «B», или что годовалых детей больше, чем семидесятилетних стариков?


Нужно учесть вероятность каждой комбинации. На Википедии пишут:


В Индии более 50% населения младше 25 лет и более 65% — младше 35.

Исходя из этого, вместо перечня 1–100 можно попробовать такой:


25–01 (в обратном порядке, потому что с возрастом выше шанс того, что у человека есть адхар)
25–35
36–100

Тогда получается, что вероятность первых $1598 × 25 = 39 950$ комбинаций возрастает до 50%. Мы взломали половину паролей за $39950 / 1000 = 39.95$ секунд! В следующие $1598 × 10 / 1000 = 15.8$ секунд, мы подберём ещё 15% паролей. Итого — 65% паролей за 55.9 секунды.


Теперь к именам.


В Гугле легко найти ТОП-100 имён любой страны. Исходя из данных по Индии, я передвинул соответствующие комбинации наверх списка. Будем считать, что 15% населения Индии носит популярные имена. Значит 15% паролей можно взломать практически мгновенно.


Индусы — 80% населения Индии. Значит, если поставить индуистские имена выше в списке, то это ускорит 80% попыток. После предыдущего шага у нас осталось $100% – 15% = 85%$ попыток. Если из них 80% имён — индуистские, то 79% (оставляем 1% на популярные, но не индуистские имена) мы взломаем в следующие 65% попыток.


Посчитаем всё вместе, с учётом возрастной статистики. Разобьем на группы:


100: Общее количество {
    50: от 00 до 25 лет {
        7: популярные имена,
        43: непопулярные имена {
            34: индусы,
            9: не индусы
        }
    }
    15: от 26 до 35 лет {
        3: популярные имена,
        13*: непопулярные имена {
            10: индусы,
            3: не индусы
        }
    }
    45: от 36 до 100 лет {
        7: популярные имена,
        38: непопулярные имена {
            30: индусы,
            8: не индусы
        }
    }
}

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



Красные числа — это поисковый приоритет. Комбинации для людей первой группы протестируем первыми, потом вторые, потом третьи и так далее.


Сколько теперь нужно времени для взлома?


Фаза №1
1 = 11 секунд для взлома 7 паролей
2 = 3 секунды для взлома 3 паролей
3 = 11 секунд для взлома 7 паролей

Мы взломали пароли 17 человек, осталось 83. Удалим предыдущие комбинации из списка и будем пробовать следующие наборы — 4, 5, 6.


Фаза №2
4 = 54 секунды для взлома 34 паролей
5 = 16 секунд для взлома 10 паролей
6 = 47 секунд для взлома 30 паролей

Снова удаляем комбинации предыдущих фаз.


Фаза №3
7 = 14 секунд для взлома 9 паролей
8 = 5 секунд для взлома 3 паролей
9 = 12 секунд для взлома 8 паролей

Суммарное время: $11 + 3 + 11 + 54 + 16 + 47 + 14 + 5 + 12 = 173$ секунды или 2 минуты и 13 секунд.


Взломанных паролей: 100


Среднее время для одного пароля: $173 / 100 = 1.73$ секунды.


92 года → 1.73 секунды. Ниче так, да?

Tags:брутфорсиндияматематика
Hubs: Information Security Algorithms Mathematics
+86
34.7k 133
Comments 70