22.08.2018 19:10
atamanenko 58 26700 Источник

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


Четыре заглавные буквы и четыре цифры. Из них можно составить 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 секунды. Ниче так, да?

Комментарии (58)


  1. Sabubu
    22.08.2018 22:14
    #19022819

    Это известная особенность, что естественные идентификаторы (имена, фамилии итд) легко перебираются. То же самое, если зашехировать имя или телефон — их легко восстановить, так как их очень ограниченное количество.


    1. atamanenko Автор
      22.08.2018 22:23
      #19022847

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


      1. Mike_soft
        22.08.2018 22:56
        #19022937
        +7

        не зря ж есть понятие «индусский код»


      1. Zet_Roy
        23.08.2018 01:21
        #19023207
        -3

        Только данные отсталой страны никому ненужны.


        1. TimsTims
          23.08.2018 10:59
          #19024227
          +5

          Ошибаетесь. Индия многим людям видится как один из самых крупнейших и перспективных рынков сбыта всего чего угодно. Там много бедных людей, но и ещё больше богатых, их в больше, чем в других странах.


        1. scruff
          23.08.2018 11:39
          #19024397
          +1

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


        1. bask
          23.08.2018 12:56
          #19024839

          Я однажды смотрел интервью с одним болливудским известным актёром. Его спросили: «Почему бы вам не поехать сниматься в Голливуде?». Он ответил: «А зачем? Здесь, в Индии, меня смотрит миллиард зрителей, а в Голливуде меня покажут меньше чем 500 млн»


      1. ICELedyanoj
        23.08.2018 14:53
        #19025271
        +1

        Это известная проблема с государственными органами. Часто любые, даже самые благие начинания, сталкиваются с ленью на местах.
        Живой пример. Украинская налоговая выдаёт каждому человеку свой собственный ИНН. Кроме этого внедрены цифровые сертификаты, которые могут быть использованы человеком в качестве цифровой подписи. Например — при получении кредита, или сдаче налоговых документов онлайн.
        И переходим к смешному моменту. Налоговая выдаёт человеку сертификат на диске, при этом пароль к этому сертификату уже установлен (и, довольно часто, написан маркером на конверте с диском). И угадайте с трёх раз что это за пароль? Я опросил нескольких знакомых — у всех одно и то же. В качестве пароля налоговая использует ИНН, который является открытой информацией.
        Понятно, что сертификат можно перевыпустить онлайн. Понятно, что пароль нельзя использовать без сертификата. Тем не менее — вот такая безопасность.


        1. saipr
          24.08.2018 10:08
          #19028147

          А у нас что по-другому?


          Понятно, что сертификат можно перевыпустить онлайн.

          Это как? Не в смысле техники, а юридически!


          Понятно, что пароль нельзя использовать без сертификата.

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


    1. alexeykuzmin0
      23.08.2018 14:34
      #19025187

      А с телефоном-то что не так? Их в России пара сотен миллионов


  1. RedComrade
    22.08.2018 23:16
    #19022985

    Раджит Кутропали говорит:«Святая корова!», если материал оригинальный — похвально, сам себе CTF


    1. zzzmmtt
      23.08.2018 10:21
      #19024027
      +2

      zanuda_mode_on Раджеш Кутраппали zanuda_mode_off


      1. fireSparrow
        23.08.2018 10:36
        #19024101
        +2

        Префикс всё равно «РАДЖ».


        1. zzzmmtt
          23.08.2018 10:38
          #19024115
          +1

          В кириллическом написании верно, если там латиница, то RAJI и RAJE — таки отличаются.


          1. fireSparrow
            23.08.2018 10:55
            #19024217
            +4

            На этот раз вы забыли включить zanuda_mode ;)


        1. Torps
          23.08.2018 16:24
          #19025717

          или СИНГХ


    1. walkman7
      23.08.2018 14:49
      #19025253

      Secret password
      RAJE1982


  1. Alek_roebuck
    22.08.2018 23:35
    #19023011
    +1

    Очень впечатлили первые два шага. Сделаем дикую, абсурдную ошибку в исходном подсчёте, получим три триллиона комбинаций. Затем ошибку очевидным образом исправим — и вот мы получили всего 46 миллионов, какая титаническая работа!

    Следующие пункты не читал, но позвольте угадать: вы посмотрели популярные имена, верно?


    1. atamanenko Автор
      23.08.2018 00:08
      #19023093

      Либо автор просто добивался «вау-эффекта», как писал KennyGin ниже, либо пытался продемонстрировать, насколько большая разница в количестве комбинаций между случайным набором буквоцифр и шаблонным.

      Следующие пункты не читал, но позвольте угадать: вы посмотрели популярные имена, верно?

      Это перевод :)


      1. taujavarob
        23.08.2018 22:12
        #19027025

        Это перевод :)

        Редакторам Хабра 101 раз говорили как правильно сделать оформление переводной статьи. — Им что горохом об…


  1. aamonster
    22.08.2018 23:37
    #19023015

    /me не очень понял, как оный индус собирается брутфорсить 1000 паролей в секунду. Его что, сайт пароле эдак на третьем или пятом не заблокирует минут на пять?


    А "пароль" из первых букв имени и года рождения — это вообще гордо :-). Если ломать конкретную учётку — брутфорс не нужен, просто зайти...


    1. atamanenko Автор
      23.08.2018 00:09
      #19023095

      Пароли на PDF-письмах, а не на сайте.


      1. ris58h
        23.08.2018 11:32
        #19024369

        Меня интересует вопрос: от кого вообще должен защитить этот пароль? От недобросовестного работника еАдхара? Почтового сервера/клиента? Соседа по индийской общаге?
        Злоумышленник же сперва должен это письмо как-то получить.

        Автора спросили об этом в комментариях. Его ответ в моём вольном переводе:
        1. Множество этих файлов проиндексировано гуглом.
        2. А что если сервер взломают?

        Но это проблема безопасного хранения, на мой взгляд.


    1. darthmaul
      23.08.2018 14:19
      #19025129
      +1

      как оный индус собирается брутфорсить 1000 паролей в секунду
      большинство брутфорсов пишут сразу с переключалкой прокси.


      1. 0ther
        23.08.2018 17:54
        #19026087

        А толку, если лок будет на учётную запись?
        Я видел ответ что это оказалось PDF, но всё же.


        1. Goodkat
          23.08.2018 20:22
          #19026687

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


          1. Zidian
            23.08.2018 22:14
            #19027029

            Можно просто выдавать капчу.
            Или запрашивать иную верификацию.


          1. 0ther
            24.08.2018 14:15
            #19029415

            Зачем к любому?


  1. KennyGin
    22.08.2018 23:37
    #19023019
    +1

    Какая забавная статья.

    Берётся исходная задача «Перебрать комбинации из первых четыре буквы имени капсом плюс год рождения». Дальше число этих комбинаций грубейшим образом оценивается сверху как "Всевозможные комбинации из четырёх заглавных букв и четырёх цифр".
    Получаем исполинские 92 года на перебор. Дальше за два шага просто возвращаемся к исходной задаче, и вот мы уже сократили перебор до 12 часов. Дешёвый ВАУ-эффект обеспечен!

    P.S. К оставшимся двум шагам оптимизации претензий нет, путь это и довольно тривиальные вещи. Но ведь «12 часов -> 2 секунды» это совсем не так круто как «92 года -> 2 секунды», да?..


    1. atamanenko Автор
      23.08.2018 00:19
      #19023129

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


  1. denis-19
    23.08.2018 07:02
    #19023453

    Годы и секунды это замечательно. Как и regular expressions.

    Константы для первого, которые всегда лучше помнить.
    Год — 8760 часов, 31 536 000 секунд.
    Один миллион секунд — 11,5 суток.
    Один миллиард секунд — 31 и ? лет.
    Один триллион секунд — 31?710 лет.


    1. hdfan2
      23.08.2018 08:38
      #19023609

      Мне нравится соотношение "? секунд — один нановек" (с точностью 5%).


    1. TimsTims
      23.08.2018 11:02
      #19024245
      +1

      Редко, когда нужно считать года в секундах, но даже если это использовать в коде, то читающий код ничего бы не понял, откуда взялась константа 31536000. Я бы написал более менее явно: 60*60*24*365. Уж что-что, а 24 и 365 обычного человека подтолкнут на мысль, что это время. Ну и опять-же 31536000 в отличии от 86400 вовсе не константа, а зависит от високосности года…


      1. Fortop
        23.08.2018 15:28
        #19025439
        +1

        И даже 86400 не константа

        Дополнительная секунда


        1. alexeykuzmin0
          23.08.2018 15:40
          #19025511

          Смотря в какой предметной области. Если мне система нагрузочного тестирования пишет «тест выполнялся 1 сутки, 2 часа 3 минуты 4 секунды», то я ожидаю, что продолжительность суток — константа.


  1. yurisv3
    23.08.2018 09:10
    #19023705

    Уже с первого взгляда бросаются в глаза две большие лажи:

    1) Индийский ИНН — это PAN, а не Aadhaar.

    2) Aadhaar — это БИОМЕТРИЧЕСКИЙ личный ID.

    Примитивный пароль точно соответствует «ценности» закрытого им PDF. Который просто ваша копия, исключительно для удобства — точно такую же может невозбранно сделать ЛЮБОЙ, тупо сфотографировав или отсканировав оригинал (саму карточку).

    Практическая ценность этой копии для левого человека равна НУЛЮ, ибо персональные БИОМЕТРИЧЕСКИЕ данные лежат в центральной базе. Доступа к которой собственно карточка никак не дает.

    Зачем вообще там (ПДФ) пароль? А фиг его знает. Чисто «для порядка». Тут так принято.


    1. DimaTiunov
      23.08.2018 09:35
      #19023803

      Будет слив баз связанных с этой, будет смысл)


      1. yurisv3
        23.08.2018 12:02
        #19024561

        Хахаха, имея копию базы биометрии — можно сгенерировать сколько угодно ВАЛИДНЫХ Aadhaar ID, на любые входные персональные данные (ФИО/адрес), и никаких «запароленных» PDF для этого не надо.

        Так в в чем «будет смысл»? — раскройте пожалуйста.


  1. Kaylent0
    23.08.2018 10:24
    #19024041

    А где тут математика?


    1. sumanai
      23.08.2018 20:41
      #19026765

      Числа перемножали.


  1. tangro
    23.08.2018 10:48
    #19024183

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


  1. ris58h
    23.08.2018 11:29
    #19024353
    +2

    Когда получал визу в Финляндию, тоже получал зашифрованный PDF. Пароль: первые четыре символа номера паспорта + дата рождения.
    Link

    Open PDF attachment (using 4 characters of Passport Number + Date Of Birth (ddmmyyyy) as entered in the online visa application form)

    Предлагаю поломать!


    1. scruff
      23.08.2018 11:44
      #19024433

      Инересно, как сложно сломать PDF? Знаю точно, что MS-документы ломаются на 1-2-3 даже без брутфорса.


      1. Busla
        23.08.2018 12:43
        #19024775

        для шифрования что pdf, что docx используется AES-256
        на 1-2-3 ломается «защита» от изменения


    1. vlivyur
      23.08.2018 12:28
      #19024695

      Только если номер паспорта был указан с пробелом, я так и не смог подобрать пароль. Там где-то про пробел было упомянуто, но ни с ним, ни без него не получалось.


      1. ris58h
        23.08.2018 12:48
        #19024797

        Для просмотра и печати визовой анкеты, пожалуйста, используйте пароль в формате, указанном ниже:
        Первые 4 цифры номера паспорта+ дата рождения(ддммггг), как указано в визовой анкете

        — Если Вы ввели номер паспорта в следующем формате: 72 1234567 и дату рождения: 01.01.1990, пожалуйста, используйте пароль: 72 101011990, чтобы открыть PDF.
        — Если Вы ввели номер паспорта в следующем формате: 721234567 и дату рождения: 01.01.1990, пожалуйста, используйте пароль: 721201011990, чтобы открыть PDF.


        1. vlivyur
          23.08.2018 14:13
          #19025105

          Вот-вот. Именно в таком виде у меня и не сработало. И первые четыре символа и первые четыре цифры с пробелами и без пробелов никак не распознавались как валидные (72 1, 72 12, 7212 не подходили). А если в анкете без пробела указывать, то всё хорошо.


          1. Arty_Fact
            23.08.2018 15:29
            #19025447

            У меня принял «3 2 3 4 23313», «DF23 124531», " 1 2 3 4". Символы не принимает. А вот пробелы и буквы в любом порядке.


            1. vlivyur
              23.08.2018 17:34
              #19026003
              +1

              А открыть pdf'ку с пробелами смогли?


              1. Arty_Fact
                23.08.2018 17:43
                #19026039

                К сожалению, времени нет дозаполнить до конца. Можете сами попробовать на их страничке.


      1. Arty_Fact
        23.08.2018 12:54
        #19024831

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


  1. Zencaster
    23.08.2018 11:45
    #19024443

    100: Общее количество {
    50: от 00 до 25 лет
    15: от 26 до 35 лет
    45: от 36 до 100 лет
    }

    итого 110?


    1. atamanenko Автор
      23.08.2018 11:46
      #19024447

      О, спасибо, даже не заметил. Там, очевидно, 35 вместо 45 должно было быть.
      UPD: Хотел исправить, но у автора всё подогнано под 45. То ли я чего-то неправильно понял, то ли он всё-таки ошибся.


      1. Yuretz85
        23.08.2018 15:09
        #19025355

        Скорей всего, потому как он писал что 65% это люди до 35 лет, соответственно остальные 35% — это люди от 36 лет


  1. celebrate
    23.08.2018 17:29
    #19025981

    Как обладатель Aadhar карты, я не очень понимаю, как можно воспользоваться полученным номером. Это все равно, что в России получить список всех ИНН. Ну получили и что дальше?

    И вообще говоря, при использовании Аадхар карты там надо предоставлять отпечаток своего пальца.


  1. hippohood
    23.08.2018 18:04
    #19026117
    +1

    Мне всегда было интересно насколько случайны биометрические пароли. То есть, допустим отпечаток пальца позволяет снять 15 параметров некоторые принимают 10 значений (от балды цифры). Вот вам полтриллиона возможных значений. Но как бы очевидно что они распределены сильно неравномерно и почти наверняка не независимы. Наверняка какая-то хэш функция делает на это поправку, растягивая поле значений там где они кучкуются, и, соответсвенно, сжимает для редких комбинаций. Но насколько эффективно она работает зависит от использованной выборки отпечатков пальцев. Возможно в Силиконовой долине использовали местную полицейскую БД для определения как распределены измеряемые параметры. Тогда весьма вероятно что алгоритм хорошо различает отпечатки пальцев афроамериканцев и латиноамериканцев, но шведы для нее все на одно "лицо" и для многих шведов она генерирует один и тот же хэш. Знающий хакер может написать таргетирванный червь, который будет подбирать хэш исходя из дополнительной информации (место проживания, раса, национальность, родственники) и будет удаленно ломать большой процент биометрик, просто потому что будет часто натыкаться на кластеры родственников, чьи биометрики неразличимы для алгоритма распознавания.
    Это уже известная проблема в распознавании лиц (азиаты все на одно лицо для калифорнийских алгоритмов) и наоборот.


    1. alexeykuzmin0
      23.08.2018 18:25
      #19026239

      У биометрических систем свои минусы есть. Например, сложно пароли менять в случае утечки.


      1. hippohood
        23.08.2018 21:41
        #19026959

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