Талантливые начинающие криптографы
1,00
р.
Подача ответов на конкурс завершена! Промежуточные итоги будут скоро подведены, окончательные итоги — после завершения параллельного конкурса взломщиков. Спасибо всем, кто принимал участие!
Итак, мы проводим очередное соревнование! Это соревнование необычное, оно состоит из двух частей. Тема задания — проверка пароля.
Мы ведь все помним, что краткость — сестра таланта? Первая часть задания состоит в разработке как можно более короткой функции, проверяющей пароль. На вход функция должна получать строку в идиоматичном для выбранного вами языка виде (char* или wchar_t* для C, то же или std::stringtd::wstring для C++ и т. д.), на выход выдавать логическое значение (снова-таки в принятой в вашем языке форме, например, int в C и bool в C++). Логическое значение «истина» соответствует тому, что введённая строка является правильным паролем.
Пароль придумываете вы сами, и должны будете раскрыть его в конце конкурса. Длина вашего пароля не должна превышать 64 символов (code point'ов для unicode-строк), но функция должна уметь обрабатывать строки разумно произвольной длины (помещающиеся в половину доступной виртуальной памяти). Если ваша функция выдаёт true и для других строк, ничего страшного, все они тоже считаются подходящими паролями.
Оцениваться будет длина этой функции в символах за вычетом синтаксически незначимых пробелов, причём идентификатор тоже считается одной буквой, при условии, что замена этого идентификатора на однобуквенный во всех местах, где он ссылается на ту же сущность, не поменяла бы смысл программы. Также ключевые слова языка считаются за один символ.
Почему же это задание сложное? Почему тривиальная функция () => true не подходит? Дело в том, что в ход игры вмешиваются игроки второй части вопроса — начинающие талантливые хакеры. Любой из хакеров может попытаться взломать вашу функцию: подобрать такую строку (возможно, длиннее 64 символов и не обязательно совпадающую с задуманным вами паролем), что ваша функция вернёт на ней true. Взломанные функции выбывают из конкурса. Править вашу функцию после того, как опубликован взлом, нельзя. Править вашу функцию более чем через сутки после опубликования нельзя. Но вы можете написать альтернативную функцию отдельным ответом, не более трёх в общей сложности на одного участника. Красть чужие функции нехорошо. Хакерам будет дано 3 дня на взлом каждой их ваших функций.
С одной стороны, вам следует создавать не слишком сложную функцию, чтобы она не проиграла по длине другим, а с другой стороны, не слишком и простую, чтобы хакеры не смогли её так просто взломать.
Ограничения: Функция не должна содержать undefined behaviour (если оно есть в вашем языке/компиляторе), предполагать стабильность или нестабильность вычислений с плавающей точкой, полагаться на случайные числа или текущие дату/время/информацию из внешних источников (включая обращение к сторонним сервисам, в том числе и в интернете). Функция должна быть детерминистической, то есть, менять свой результат лишь при изменении входных данных, и данные должны передаваться в неё лишь через входной параметр. Функция не должна пользоваться библиотеками кроме стандартных библиотек языка, и ни в коем случае не должна пользоваться сторонними крипто-, хэширующими и математическими библиотеками (или отдельными функциями/процедурами/методами/...). Функция не должна также обращаться к специальным криптографическим конструкциям, встроенным в оборудование (пример). Функция не должна запускать сторонних процессов (кроме возможно копий/частей программы). Функция должна на вашем пароле на вашем компьютере выдавать положительный результат за не более чем минуту вычислений. Функция имеет право упасть, это также считается положительным ответом. То есть, если хакер сможет «положить» вашу функцию, она считается взломанной. (Но он не может передавать в функцию испорченную строку: nullptr, невалидную память, или например содержащую встроенные нули для C. Другими словами: хакер не должен использовать UB или рефлексию сам.)
Если для компиляции вашей программы нужны нестандартные ключи, их полная длина в символах добавляется к количеству символов функции.
При неоднозначности лучше переспросите в code golf-чате. Окончательное решение при отсутствии консенсуса остаётся за организатором конкурса.
Продолжительность конкурса — одна неделя, а точнее, окончание в 23:59:59 29.05.2017 по UTC. Новые решения после этого срока в зачёт не принимаются. Время окончания конкурса хакеров равно времени окончания конкурса криптографов плюс трое суток взломанные после этого срока функции считаются выдержавшими испытание. Вы должны будете предоставить пароль после окончания конкурса хакеров. Если ваша функция не выдаёт истину или падает на вашем пароле, она снимается с конкурса.
Победителем конкурса будет объявлена самая короткая невзломанная программа, которая выдержит проверку «своего» пароля.
Языки для конкурсных программ допускаются лишь те, для которых есть общедоступный компилятор под общедоступные платформы (одна из: Windows XP+, Linux не более, чем пятилетней свежести, Mac OS). Просьба не злоупотреблять экзотическими языками. В ответ желательно включить полную компилируемую программу, будет учитываться лишь длина функции проверки (а также ваших функций, вызываемых из неё).
Конкурс хакеров проходит здесь.
Обсуждение вопроса ведётся в code golf-чате, если вам непонятно условие, спрашивайте там (ну в крайнем случае в комментариях, если у вас недостаточно репутации).
Удачи всем участникам!
Турнирная таблица:
#leadership { border-collapse: collapse } #leadership td, #leadership th { padding: 5px } #leadership th { text-align: center }
Ответ
Python 3.2+, 172 токена (время на взлом истекло)
def check(p): i=lambda x:int.from_bytes(x.encode('utf-16le','surrogatepass'),'big') try:return i(p)**65537%i('쳞\ue7e2䄝\uf03a듌垴ﮍ믚騾갢䳡︪ۡ䓽㒞䇑⮚⯎사᳀ᗦ딵㎹勤ㅵᕛ\uda35竹彽㝼꤅熎')==i('꼬㶳ꖅ慘钽\uf0fe젬\uf4fcᆎ횹鸝ᝄ幎垡륿ᖽﮠ鹰\uec89ᮒ핪篜Ⱃ⏾≅刳ﬖ睘쁽뭊㧇읚') except:return False
Ответ:
>>> check('簅䊆蓐鷃礤匹崚콂퉾횏練\ue611ﯻ⁼\uec77酢툖ᒆ뻉쇓\ufbcf') True
Алгоритм - возведение в степень по модулю, как в RSA. Пароль - выхлоп os.urandom.
Использование decode с 'surrogatepass' позволяет преобразовать практически любой набор байт в строку. Помогает уменьшить количество токенов.
Итак, мы проводим очередное соревнование! Это соревнование необычное, оно состоит из двух частей. Тема задания — проверка пароля.
Мы ведь все помним, что краткость — сестра таланта? Первая часть задания состоит в разработке как можно более короткой функции, проверяющей пароль. На вход функция должна получать строку в идиоматичном для выбранного вами языка виде (char* или wchar_t* для C, то же или std::stringtd::wstring для C++ и т. д.), на выход выдавать логическое значение (снова-таки в принятой в вашем языке форме, например, int в C и bool в C++). Логическое значение «истина» соответствует тому, что введённая строка является правильным паролем.
Пароль придумываете вы сами, и должны будете раскрыть его в конце конкурса. Длина вашего пароля не должна превышать 64 символов (code point'ов для unicode-строк), но функция должна уметь обрабатывать строки разумно произвольной длины (помещающиеся в половину доступной виртуальной памяти). Если ваша функция выдаёт true и для других строк, ничего страшного, все они тоже считаются подходящими паролями.
Оцениваться будет длина этой функции в символах за вычетом синтаксически незначимых пробелов, причём идентификатор тоже считается одной буквой, при условии, что замена этого идентификатора на однобуквенный во всех местах, где он ссылается на ту же сущность, не поменяла бы смысл программы. Также ключевые слова языка считаются за один символ.
Почему же это задание сложное? Почему тривиальная функция () => true не подходит? Дело в том, что в ход игры вмешиваются игроки второй части вопроса — начинающие талантливые хакеры. Любой из хакеров может попытаться взломать вашу функцию: подобрать такую строку (возможно, длиннее 64 символов и не обязательно совпадающую с задуманным вами паролем), что ваша функция вернёт на ней true. Взломанные функции выбывают из конкурса. Править вашу функцию после того, как опубликован взлом, нельзя. Править вашу функцию более чем через сутки после опубликования нельзя. Но вы можете написать альтернативную функцию отдельным ответом, не более трёх в общей сложности на одного участника. Красть чужие функции нехорошо. Хакерам будет дано 3 дня на взлом каждой их ваших функций.
С одной стороны, вам следует создавать не слишком сложную функцию, чтобы она не проиграла по длине другим, а с другой стороны, не слишком и простую, чтобы хакеры не смогли её так просто взломать.
Ограничения: Функция не должна содержать undefined behaviour (если оно есть в вашем языке/компиляторе), предполагать стабильность или нестабильность вычислений с плавающей точкой, полагаться на случайные числа или текущие дату/время/информацию из внешних источников (включая обращение к сторонним сервисам, в том числе и в интернете). Функция должна быть детерминистической, то есть, менять свой результат лишь при изменении входных данных, и данные должны передаваться в неё лишь через входной параметр. Функция не должна пользоваться библиотеками кроме стандартных библиотек языка, и ни в коем случае не должна пользоваться сторонними крипто-, хэширующими и математическими библиотеками (или отдельными функциями/процедурами/методами/...). Функция не должна также обращаться к специальным криптографическим конструкциям, встроенным в оборудование (пример). Функция не должна запускать сторонних процессов (кроме возможно копий/частей программы). Функция должна на вашем пароле на вашем компьютере выдавать положительный результат за не более чем минуту вычислений. Функция имеет право упасть, это также считается положительным ответом. То есть, если хакер сможет «положить» вашу функцию, она считается взломанной. (Но он не может передавать в функцию испорченную строку: nullptr, невалидную память, или например содержащую встроенные нули для C. Другими словами: хакер не должен использовать UB или рефлексию сам.)
Если для компиляции вашей программы нужны нестандартные ключи, их полная длина в символах добавляется к количеству символов функции.
При неоднозначности лучше переспросите в code golf-чате. Окончательное решение при отсутствии консенсуса остаётся за организатором конкурса.
Продолжительность конкурса — одна неделя, а точнее, окончание в 23:59:59 29.05.2017 по UTC. Новые решения после этого срока в зачёт не принимаются. Время окончания конкурса хакеров равно времени окончания конкурса криптографов плюс трое суток взломанные после этого срока функции считаются выдержавшими испытание. Вы должны будете предоставить пароль после окончания конкурса хакеров. Если ваша функция не выдаёт истину или падает на вашем пароле, она снимается с конкурса.
Победителем конкурса будет объявлена самая короткая невзломанная программа, которая выдержит проверку «своего» пароля.
Языки для конкурсных программ допускаются лишь те, для которых есть общедоступный компилятор под общедоступные платформы (одна из: Windows XP+, Linux не более, чем пятилетней свежести, Mac OS). Просьба не злоупотреблять экзотическими языками. В ответ желательно включить полную компилируемую программу, будет учитываться лишь длина функции проверки (а также ваших функций, вызываемых из неё).
Конкурс хакеров проходит здесь.
Обсуждение вопроса ведётся в code golf-чате, если вам непонятно условие, спрашивайте там (ну в крайнем случае в комментариях, если у вас недостаточно репутации).
Удачи всем участникам!
Турнирная таблица:
#leadership { border-collapse: collapse } #leadership td, #leadership th { padding: 5px } #leadership th { text-align: center }
Таблица лидеров
| Автор | Язык | Ток. | Взлом? | Осталось | Хор? |
|---|
Ответ
Python 3.2+, 172 токена (время на взлом истекло)
def check(p): i=lambda x:int.from_bytes(x.encode('utf-16le','surrogatepass'),'big') try:return i(p)**65537%i('쳞\ue7e2䄝\uf03a듌垴ﮍ믚騾갢䳡︪ۡ䓽㒞䇑⮚⯎사᳀ᗦ딵㎹勤ㅵᕛ\uda35竹彽㝼꤅熎')==i('꼬㶳ꖅ慘钽\uf0fe젬\uf4fcᆎ횹鸝ᝄ幎垡륿ᖽﮠ鹰\uec89ᮒ핪篜Ⱃ⏾≅刳ﬖ睘쁽뭊㧇읚') except:return False
Ответ:
>>> check('簅䊆蓐鷃礤匹崚콂퉾횏練\ue611ﯻ⁼\uec77酢툖ᒆ뻉쇓\ufbcf') True
Алгоритм - возведение в степень по модулю, как в RSA. Пароль - выхлоп os.urandom.
Использование decode с 'surrogatepass' позволяет преобразовать практически любой набор байт в строку. Помогает уменьшить количество токенов.
