Талантливые начинающие хакеры
1,00
р.
Итак, мы поводим очередное соревнование! Это соревнование необычное, оно состоит из двух частей. Тема задания — проверка пароля.
В первой части соревнования участники придумывают функцию, которая берёт строку и возвращает результат, является ли эта строка паролем (да/нет). Здесь у нас вторая часть соревнования: взлом.
Ваша цель — придумать (или вычислить!) пароль, на котором функция из первой части соревнования возвратит истинное значение. Или упадёт.
Пароль не обязательно должен совпадать с тем, который задумал автор функции. Вы можете воспользоваться информацией о том, что авторский пароль не длиннее 64 символов.
Учтите, что автор имеет право править свой ответ в течение суток после его публикации. Публикация взломов для каждого вопроса принимается лишь в первые 72 часа после публикации вопроса.
При публикации ответа публикуйте, пожалуйста, ссылку на него во взламываемом вопросе. (Лучше прямо в вопросе, а не в комментарии, и правьте заголовок, как в других взломанных вопросах.)
Ограничения: Строка, которую вы подаёте на вход, должна быть валидной строкой для вашего языка. Например, она не может располагаться в невалидной памяти, и вы не можете использовать рефлексию, чтобы «сломать» внутреннее представление строки и заставить функцию «упасть» на ней. Если алгоритм принимает на вход юникодную строку, ваша строка также должна быть юникодной. Она может быть достаточно большой (скажем, размером в MAXINT), но не занимать более половины свободной памяти (чтобы не создавать проблем для работы алгоритма одним своим присутствием в памяти). Процесс программного «составления» строки, если он необходим для вашего ответа, должен занимать не более 1 минуты на вашем компьютере, и не приводить к UB. Взлом не должен пытаться вмешиваться в работу функции (например, портить её код или код используемых библиотек, менять память пароля после передачи его в функцию и т. п.).
Если взламываемая функция выбывает из конкурса по той или иной причине, её взломы выбывают вместе с ней. Если ваш пароль при проверке не заставляет функцию выдать истинное значение или упасть, он также выбывает из конкурса. Из нескольких взломов одной функции засчитывается только первый по дате последней правки. Взламывать свои собственные функции нельзя. (Участник должен быть зарегистрирован до времени публикации функции.)
Победителем является взлом, не выбывший из конкурса и набравший наибольшее количество голосов.
Если вы использовали какой-то интересный приём для нахождения подходящего пароля, расскажите о нём в ответе! Это наверняка прибавит вам голосов.
Срок окончания конкурса — 72 часа после окончания конкурса криптографов, то есть, 23:59:59 1.06.2017. Не забудьте, что каждый отдельный вопрос можно взламывать всего три дня, так что если, например, в последний день конкурса криптографов не будет опубликовано ни одной функции, то в последний день конкурса хакеров нельзя будет публиковать взломы тоже. Удачный взлом может выбыть из конкурса, если взламываемая функция будет удалена из конкурса.
Обсуждение вопроса ведётся в code golf-чате, если вам непонятно условие, спрашивайте там (ну в крайнем случае в комментариях, если у вас недостаточно репутации).
Удачи всем участникам!
Ответ
Взлом алгоритма представленного pank
def check(s): try: return int(s[:32], 16) * int(s[32:], 16) == 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845 except: return False
Очень простой свиду, но к сожалению очень сложный алгоритм основанный на проблеме разложения больших чисел на множители. Все отлично знают, проблема разложения большого числа на множители это очень сложная задача, которая не решается быстро, а тут аж 76-ти значное число.
1. Общий способ взлома
Нам известно, что одно число может быть до 32 символов, а второе сколько угодно. Я пытался найти 2 множителя случайным способом, но у меня ничего не выходило (что не удивительно). Максимум, что я смог получить, что при передаче параметра:
11111111111111111111111111111111708946551217595118393411775077160869888185470
Выходило почти похожее число:
7877183902417723537704575278635042004696369933875734065358324759903345757170
А исходное в десятичной системе выглядит вот так:
7877183902417723537704575278635042004696369934776381519304816946969514108997
Так себе результат :)
Естественно, искать и подбирать 2 таких больших множителя я могу очень-очень долго, поэтому я решил поискать проблему непосредственно в коде.
Ниже, я приведу случай, что вас не спасет даже самый крутой алгоритм от взлома, если вы не учитываете все возможные варианты ввода данных.
2. Анализ исходного кода и поиск уязвимости
После недолго анализа я начал разбирать конструкции кода, и увидел, что
s[:32] - получить все символы до 32 элемента строки
s[32:] - взять все что после 32 элемента строки
Идем дальше, видим следующее:
int(s[:32], 16) * int(s[32:], 16)
Это означает умножить 2 числа в шестнадцатеричной системе счисления. Следовательно, туда нужно передать 2 числа в шестнадцатеричной системе, ок.
3. Уязвимость
Получается, что я могу подставить число 1 и подставить в эту строку тот ключ который нужно получить.
Берем 2 строки:
00000000000000000000000000000001 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845
Конкатенируем и получаем:
000000000000000000000000000000010x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845
Подставляем в функцию, и она вернула True! Это победа :)
В первой части соревнования участники придумывают функцию, которая берёт строку и возвращает результат, является ли эта строка паролем (да/нет). Здесь у нас вторая часть соревнования: взлом.
Ваша цель — придумать (или вычислить!) пароль, на котором функция из первой части соревнования возвратит истинное значение. Или упадёт.
Пароль не обязательно должен совпадать с тем, который задумал автор функции. Вы можете воспользоваться информацией о том, что авторский пароль не длиннее 64 символов.
Учтите, что автор имеет право править свой ответ в течение суток после его публикации. Публикация взломов для каждого вопроса принимается лишь в первые 72 часа после публикации вопроса.
При публикации ответа публикуйте, пожалуйста, ссылку на него во взламываемом вопросе. (Лучше прямо в вопросе, а не в комментарии, и правьте заголовок, как в других взломанных вопросах.)
Ограничения: Строка, которую вы подаёте на вход, должна быть валидной строкой для вашего языка. Например, она не может располагаться в невалидной памяти, и вы не можете использовать рефлексию, чтобы «сломать» внутреннее представление строки и заставить функцию «упасть» на ней. Если алгоритм принимает на вход юникодную строку, ваша строка также должна быть юникодной. Она может быть достаточно большой (скажем, размером в MAXINT), но не занимать более половины свободной памяти (чтобы не создавать проблем для работы алгоритма одним своим присутствием в памяти). Процесс программного «составления» строки, если он необходим для вашего ответа, должен занимать не более 1 минуты на вашем компьютере, и не приводить к UB. Взлом не должен пытаться вмешиваться в работу функции (например, портить её код или код используемых библиотек, менять память пароля после передачи его в функцию и т. п.).
Если взламываемая функция выбывает из конкурса по той или иной причине, её взломы выбывают вместе с ней. Если ваш пароль при проверке не заставляет функцию выдать истинное значение или упасть, он также выбывает из конкурса. Из нескольких взломов одной функции засчитывается только первый по дате последней правки. Взламывать свои собственные функции нельзя. (Участник должен быть зарегистрирован до времени публикации функции.)
Победителем является взлом, не выбывший из конкурса и набравший наибольшее количество голосов.
Если вы использовали какой-то интересный приём для нахождения подходящего пароля, расскажите о нём в ответе! Это наверняка прибавит вам голосов.
Срок окончания конкурса — 72 часа после окончания конкурса криптографов, то есть, 23:59:59 1.06.2017. Не забудьте, что каждый отдельный вопрос можно взламывать всего три дня, так что если, например, в последний день конкурса криптографов не будет опубликовано ни одной функции, то в последний день конкурса хакеров нельзя будет публиковать взломы тоже. Удачный взлом может выбыть из конкурса, если взламываемая функция будет удалена из конкурса.
Обсуждение вопроса ведётся в code golf-чате, если вам непонятно условие, спрашивайте там (ну в крайнем случае в комментариях, если у вас недостаточно репутации).
Удачи всем участникам!
Ответ
Взлом алгоритма представленного pank
def check(s): try: return int(s[:32], 16) * int(s[32:], 16) == 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845 except: return False
Очень простой свиду, но к сожалению очень сложный алгоритм основанный на проблеме разложения больших чисел на множители. Все отлично знают, проблема разложения большого числа на множители это очень сложная задача, которая не решается быстро, а тут аж 76-ти значное число.
1. Общий способ взлома
Нам известно, что одно число может быть до 32 символов, а второе сколько угодно. Я пытался найти 2 множителя случайным способом, но у меня ничего не выходило (что не удивительно). Максимум, что я смог получить, что при передаче параметра:
11111111111111111111111111111111708946551217595118393411775077160869888185470
Выходило почти похожее число:
7877183902417723537704575278635042004696369933875734065358324759903345757170
А исходное в десятичной системе выглядит вот так:
7877183902417723537704575278635042004696369934776381519304816946969514108997
Так себе результат :)
Естественно, искать и подбирать 2 таких больших множителя я могу очень-очень долго, поэтому я решил поискать проблему непосредственно в коде.
Ниже, я приведу случай, что вас не спасет даже самый крутой алгоритм от взлома, если вы не учитываете все возможные варианты ввода данных.
2. Анализ исходного кода и поиск уязвимости
После недолго анализа я начал разбирать конструкции кода, и увидел, что
s[:32] - получить все символы до 32 элемента строки
s[32:] - взять все что после 32 элемента строки
Идем дальше, видим следующее:
int(s[:32], 16) * int(s[32:], 16)
Это означает умножить 2 числа в шестнадцатеричной системе счисления. Следовательно, туда нужно передать 2 числа в шестнадцатеричной системе, ок.
3. Уязвимость
Получается, что я могу подставить число 1 и подставить в эту строку тот ключ который нужно получить.
Берем 2 строки:
00000000000000000000000000000001 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845
Конкатенируем и получаем:
000000000000000000000000000000010x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845
Подставляем в функцию, и она вернула True! Это победа :)
