Талантливые начинающие хакеры

Итак, мы поводим очередное соревнование! Это соревнование необычное, оно состои
из двух частей. Тема задания — проверка пароля.

В первой части соревнования участники придумывают функцию, которая берёт строку 
возвращает результат, является ли эта строка паролем (да/нет). Здесь у нас вторая часть соревнования: взлом.

Ваша цель — придумать (или вычислить!) пароль, на котором функция из первой части соревнования возвратит истинное значение. Или упадёт.

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

Учтите, что автор имеет право править свой ответ в течение суток после его публикации
Публикация взломов для каждого вопроса принимается лишь в первые  72 часа после публикации вопроса.

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

Ограничения: Строка, которую вы подаёте на вход, должна быть валидной строкой дл
вашего языка. Например, она не может располагаться в невалидной памяти, и вы не может
использовать рефлексию, чтобы «сломать» внутреннее представление строки и заставит
функцию «упасть» на ней. Если алгоритм принимает на вход юникодную строку, ваша строк
также должна быть юникодной. Она может быть достаточно большой (скажем, размером в MAXINT)
но не занимать более половины свободной памяти (чтобы не создавать проблем для работы алгоритма одним своим присутствием в памяти). Процесс программного «составления» строки, если он необходим для вашего ответа, должен занимать не более 1 минуты на вашем компьютере, и не приводить к UB. Взлом не должен пытаться вмешиваться в работу функции (например, портить её код или код используемых библиотек, менять память пароля после передачи его в функцию и т. п.).

Если взламываемая функция выбывает из конкурса по той или иной причине, её взлом
выбывают вместе с ней. Если ваш пароль при проверке не заставляет функцию выдать истинно
значение или упасть, он также выбывает из конкурса. Из нескольких взломов одной функции засчитывается только первый по дате последней правки. Взламывать свои собственные функции нельзя. (Участник должен быть зарегистрирован до времени публикации функции.)

Победителем является взлом, не выбывший из конкурса и набравший наибольшее количество голосов.

Если вы использовали какой-то интересный приём для нахождения подходящего пароля, расскажите о нём в ответе! Это наверняка прибавит вам голосов.

Срок окончания конкурса — 72 часа после окончания конкурса криптографов, то есть
23:59:59 1.06.2017. Не забудьте, что каждый отдельный вопрос можно взламывать всег
три дня, так что если, например, в последний день конкурса криптографов не будет опубликовано ни одной функции, то в последний день конкурса хакеров нельзя будет публиковать взломы тоже. Удачный взлом может выбыть из конкурса, если взламываемая функция будет удалена из конкурса.

Обсуждение вопроса ведётся в code golf-чате, если вам непонятно условие, спрашивайте там (ну в крайнем случае в комментариях, если у вас недостаточно репутации).

Удачи всем участникам!
    

Ответы

Ответ 1

Взлом алгоритма представленного 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! Это победа :)


Ответ 2

Взлом алгоритма №1 представленного Alex Krass:

public static bool check(string p)
{
    try
    {
        int n = -977;
        foreach(var c in p)
            n += p.Aggregate((_, __) => (char)(_ + __));

        return p.Substring(12, 5) == (n / 2).ToString() ? true : false; 
    } catch { return false; }
}


Уязвимость:

Это простой алгоритм. Весь смысл функции, что она делает сумму символов в строк
ANSI (a==97, b==98 и т.д) добавляя их к изначальной сумме -997, умножает это число на количество символов, а потом делит на 2. После чего что она берет 5 символов начиная с 12 символа в введенной строке и сравнивает с полученным числом.

Получается нужна строка минимум 17 символов в которой с 12 по 17 символ будет число
а также в которой сумма всех символов деленная на 2 будет равна этому числу. Зная алгоритм, мы спокойно можем подобрать строку несложной математикой. 

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

105+104+97+99+107+121+111+117+114+107+101+121+50+56+52+49+49+97+108+101+120+33+98+98+97

Умножаем на 25 символов строки и получаем 57 800, вычитаем 977 и получаем 56 823. Далее делим на 2 и получаем 28 411.5, округляем до int и получаем 28 411. 

Взломали! Функция возвращает true

Решение - любой из ключей:

ihackyourkey28411alex!bba
sdfsdfsdfsdf43531degdfgdfgdfb06


Ответ 3

Взлом алгоритма №2 от pank

Алгоритм основанный на проблеме факторизации больших чисел. 

def check(s):
  try:
    x = int(s[:32], 16)
    return x > 1 and x * int(s[32:], 16) == 0x620fe07bca360829f97c33bd0aa64795a27c2cc4f67dd5d699a0af7cccb86d1f
  except:
    return False


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

Для начала учитываем, что число которое нужно получить, в десятичной системе счисления выглядит так:

44354711195682213318901868940731534954425938156569080174424467380253591366943


Смотрим и печалимся.. что разделить на 2 не получится без остатка...

Проведем краткий анализ и на основе кода программы предположим, что 77-значное числ
имеет всего два простых множителя,  размером 39 знаков или 32 знака в hex. @Abyx еще не успел начать брутить множители, поэтому это сделаю я :)

Как разложить-то?

Далее, окунемся в теорию вычислительной сложности и оценим примерно сколько же на
нужно времени в 2017 году, чтобы разложить 77 значное число на простые множители. Честно говоря, немного, ведь 100 значное число уже разложили в 1991 году на RSA Factoring Challenge. 

На старом 2200 MHz Athlon 64 это потребовало бы 4 часа, на 3.5 GHz Intel Core2 Qua
q9300 требует 70 минут. Число до 60 знаков можно разложить в несколько секунд на одном из онлайн ресурсов, но у нас то 77!

Открываем другой ресурс на котором есть возможность факторизации большого числа прям
в браузере и раскладываем число на простые множители. Жмем factor и ждем...у меня на это ушло 8 минут. Есть еще консольные программы GGNFS и т.д. но мне подошло решение в браузере.

Еще есть встроенная в Ubuntu консольная утилита factor, с помощью нее тоже можн
раскладывать числа на множители.

Ответ

Получаем простые множители:

294214717393397322902102113848520211047 * 150756262598431142388953822991693100169

Следовательно переводим это 16-ричную систему счисления и получаем следующий код

dd57b184ad4252c9b59ce1b6f849fa670x716a999c7f875e33d2e211fdc5c7b489


Учитывайте, что вначале строки мы не ставим 0x, чтобы число залезло в 32 символа, а Python и так все поймет :)

Подставляем в функцию..Она вернула True! Взломали!


Ответ 4

Алгоритм "*7+7" от Vladimir Gamalian

#include 
#include 

int f(char* s) {
    u_int32_t a = 0, b, i = 0;
    if (s[0] && s[1] && s[2])
        a = *(u_int32_t*)s;
    b = a;
    while (++i)
        a = a * 7 + 7;
    return a + b == 980355503;
}

int main(){
    printf("%d",f("z(!3"));
}


В функции берется только первые 4 байта пароля. Это значение является стартовым дл
цикла модификации бит и прибавляется один раз в самом конце. Причем цикл постоянно сдвигает биты влево. Отсюда следует, что младшие биты аргумента играют ключевую роль в результате, в то время, как старшие 3 ни на что не влияют.

Математик из меня никакой, так что пытаться искать математическую формулу заменяющу
цикл модификации бит не стал. Пошел по пути анализа зависимости результата от аргумента
Для начала решил посмотреть повторимость значений в цикле. Для стартового значения 0 цикл выдавал результат 0xFFFFFFFF такое же значение встретилось на итерации 1073741823, таким образом полный цикл на 4 млрд значений не требуется, можно сократить время выполнения в 4 раза. Далее при анализе использовалась такая ускоренная функция.

Посмотрел значения итогового хеша (цикл и a+b) для аргументов от 0 до 16. Сразу выяснилось
что младшие 3 бита всегда 111, а четвертый бит противоположен последнему биту аргумента
Запустил на ночь печать значений функции от 0 до 8192. К утру она отработала менее че
на половину, но первых 300 значений оказалось достаточно для анализа. Сразу решил посмотрет
целый последний байт хеша AF, оказалось, что на него оканчиваются хеши от аргументо
1A, 3A, 5A и т.д. Видно, что младшие 5 бит аргумента должны быть 11010, а шестой бит нечетным. Посмотрел сразу окончание хеша 9AF, оно оказалось для аргументов 07A, 27A, 47A. И так первая буква точно 7A (z), второй байт четный. Вывел значения функции от 07A с приращением 0x200. Младшие два байта хеша 09AF оказались для аргументов 087A, 287A, 487A, 687A и т.п. Таким же образом быстро просмотрев по несколько значений для приращений 0x2000, 0x20000, ... получал сразу по полбайта аргумента.


Ответ 5

Бернштейн от @alexolut. Ответ: lb196fehe1ptnxn5whby37jm22qqawppD;:yr. Уж не зна
какой там был пароль, но коллизий можно насобирать целую кучу.

#include 
#include 

int check(const char *str)
{
    uint64_t h = 5381;
    int c;

    while (c = *str++)
        h = ((h << 5) + h) + c;

    return h == 1180004904744509286;
}

int main()
{
    char * kek = "lb196fehe1ptnxn5whby37jm22qqawppD;:yr";
    if (check(kek))
        printf("HOORAY!");
    getchar();
}


Более того, любые подобные функции уязвимы с точки зрения коллизий.

Теперь что вкуснее: генератор коллизий для любого данного хеша. Как пример буде
использовать 1180004904744509286.

В моем решении эксплуатируется тот факт, что при возрастании входа - также линейно возрастает и выход функции. Примеры:

print(check(b"lb196fehe1ptnxn5whby37jm22qqawppD;:ot"))
print(check(b"lb196fehe1ptnxn5whby37jm22qqawppD;:xt"))
print(check(b"lb196fehe1ptnxn5whby37jm22qqawppD;:yt"))
print(check(b"lb196fehe1ptnxn5whby37jm22qqawppD;:ys"))
print(check(b"lb196fehe1ptnxn5whby37jm22qqawppD;:yr"))

(False, 9722971096724074958)
(False, 9722971096724075255)
(False, 9722971096724075288)
(False, 9722971096724075287)
(False, 9722971096724075286)


Обратите внимание - поменяли 2 с конца символ - значение хеша прыгнуло на десятки
поменяли последний символ - хеш изменился на единицу. Соответственно, мы можем "контролировать", что нам отдаст хеш функция, изменяя ввод - корреляция явная. Увеличим вход - увеличиться выход. От этого и будем исходить далее.

Без сложных подробностей просто выберем случайное число - это будет длина нашей строки для коллизии. Возьмем 20. 

Инициализируем целевую строку нулями ('\x00') и будем просто поразрядно увеличиват
каждый символ до тех пор, пока не попадем в цель. Мы можем без проблем позволить себ
наугад брать длину строки (можно и не наугад). Генератор использует жадный алгорит
(это не самый оптимальный способ, далеко не самый быстрый, но хорош для демонстрации
- то есть каждый символ выбирается с таким расчетом, чтобы максимально приблизитьс
к цели, даже если в итоге это приведет в тупик. Такой подход иногда приводит к тому, что генератор зацикливается, застревает на одном месте - в таком случае встряхиваем его и генерируем случайную строку. Этот шаг назывется "мутация". Если мы попробуем генерировать случайные строки без предложенного алгоритма - это не приведет к каким-либо результатам (я пробовал) - строк слишком много, чтобы перебирать их подряд. Наконец, код (Python3) - все функции отлично мигрируют в Cython:

# coding: utf-8

from ctypes import c_int8
import numpy
import copy


def check(password):
    # cdef char* c_str = str
    h = 5381
    ht = 0
    modulo = 2 ** 64

    for c in password:
        # Имимтимируем C - в питоне длинные числа по умолчанию
        # Имитируем даже то, что char со знаком
        # Потребуется ли char со знако или без зависит от конкретной реализации целевой хеш-функции
        ht = (h * 33) % modulo
        h = (ht + c_int8(c).value) % modulo

    target = 1180004904744509286

    return h == target, h

TOTAL_LETTERS = 20

HASH_PAWN = bytearray(b"\0" * TOTAL_LETTERS)
HASH_GENERAL = bytearray(b"\0" * TOTAL_LETTERS)

def mutate(general):
    general = numpy.random.bytes(TOTAL_LETTERS)
    return bytearray(general)


def paste_to_c(general, total_letters):
    paster = "char kek[%d] = {" % (total_letters + 1)
    # little endian
    numbs = ", ".join([str(bt) for bt in general])
    paster += numbs + ", 0x00 };"
    return paster

target = 1180004904744509286

got_it = False
is_stuck = False
while not got_it:
    for letter_index in range(TOTAL_LETTERS):
        all_possible_values = {}
        for i in range(256):
            # ascii, можно юникод
            HASH_PAWN[letter_index] = i
            got_it, hash_value = check(bytes(HASH_PAWN))
            if got_it:
                HASH_GENERAL = copy.copy(HASH_PAWN)
            all_possible_values[i] = hash_value
        sorted_hashes = [k for k in all_possible_values.keys()]
        # Жадно отбираем победившую букву. Победила та, что ближе всех перенесл
нас к цели
        sorted_hashes.sort(key=lambda asc_letter: abs(target - all_possible_values[asc_letter]))
        HASH_PAWN[letter_index] = sorted_hashes[0]
        print("%d ITERATION:" % letter_index, all_possible_values[sorted_hashes[0]])
    # Мутируем только, если результата достичь не удалось.
    # Второго шанса не предоставляем
    # Всякими штуками, типа "отбора" и "скрещивания" не занимаемся
    HASH_PAWN = mutate(HASH_PAWN)

print(bytes(HASH_GENERAL))
print(paste_to_c(HASH_GENERAL, TOTAL_LETTERS))


Можно запустить скрипт несколько раз - строки разные:

b'x<}$x2y\x8c!\x0e\xdb\xa3\xbb\xaa\x8dCOY4\xff'
char kek[21] = {120, 60, 125, 36, 120, 50, 121, 140, 33, 14, 219, 163, 187, 170
141, 67, 79, 89, 52, 255, 0x00 };

b'fsrbY0^d\xab\x1en\x9c\x96\x08\x96\x8d\xfe\x9d\x1b\xff'
char kek[21] = {102, 115, 114, 98, 89, 48, 94, 100, 171, 30, 110, 156, 150, 8, 150, 141, 254, 157, 27, 255, 0x00 };

b'U(\xcd\x99\xc8,r\x9a\x1eB\xd8o\n\xe8\xe8\xe7T\xf5\x0e\xff'
char kek[21] = {85, 40, 205, 153, 200, 44, 114, 154, 30, 66, 216, 111, 10, 232, 232, 231, 84, 245, 14, 255, 0x00 };

b'\x86\x932\xbb\x89\xf8Bx\xbc&\x86\xe2\xe1P\xa3\xe4\x9fk\xb5\xff'
char kek[21] = {134, 147, 50, 187, 137, 248, 66, 120, 188, 38, 134, 226, 225, 80, 163, 228, 159, 107, 181, 255, 0x00 };


И так далее, длиной 21, 200, 15 или сколько угодно.


Ответ 6

Взлом алгоритма представленного Vitaly

#include 
#include 
#include 

#define M 0x2B72576B913FD740
#define S 0xB72576B913FD7400

typedef unsigned char uchar;

int check(uchar * pwd) {
    ulong s = M, i, j, k;
    for (i = 0, j = strlen(pwd); i < j; i++) for (k = 0; k < 8; k++) s = k & 0x
? (i[pwd] & (1 << k) ? s ^ i[pwd] : s >> 1) : (*(pwd + i) & k ? s << 2 : s ^ S);
    return s == 0x0832CB347454C8AF;
}

int main(int argc, char ** argv) {
    printf("Result: %s\n", check("\x1A\xF2\x22\xD2\x32\xB6\x32\x1A\xF2\x32\x46\xF2\xD2\x30\xD2\xEA\x30\xD2\xF2\x32\xD8\xF2\x7A\xAA\x32\x80\x32\xAA\x02") ? "OK" : "FAIL");
    return 0;
}


При изучении алгоритма операции для начала перевел в более читаемый вид, замени
все ? на if. Стало видно, что алгоритм в зависимости от конкретных бит входной строк
выполняет с хешем одно из действий: "xor с S", "сдвиг вправо на 1" или "влево на 2"
"xor с байтом строки". Посмотрел на это как на то, что данные действия по сути система команд, где входной байт является кодом команды, на основе которого производятся действия над хешем. Далее в тексте символы входной строки называю команда и обозначаю шестнадцеричным ascii кодом символа.

Вписал в if алгоритма printf печатающие, что конкретно сейчас делает команда. Прогнал в цикле все 255 символов и получил подобное:

i=0, pwd[i]=1A, bit 0 s^S               9C5721D282C2A340
i=0, pwd[i]=1A, bit 1 s^S               2B72576B913FD740
i=0, pwd[i]=1A, bit 2 s<<2              ADC95DAE44FF5D00
i=0, pwd[i]=1A, bit 3 s<<2              B72576B913FD7400
i=0, pwd[i]=1A, bit 4 s^pwd             B72576B913FD741A
i=0, pwd[i]=1A, bit 5 s>>1              5B92BB5C89FEBA0D
i=0, pwd[i]=1A, bit 6 s>>1              2DC95DAE44FF5D06
i=0, pwd[i]=1A, bit 7 s>>1              16E4AED7227FAE83
1A: 16E4AED7227FAE83


Тут мы видим, что команда 1A выполняет два "xor S" (а два xor с одним числом даю
нулевой результат), сдвигают хеш на 4 бита влево, делают xor с входным байтом (т.е
с кодом команды 1A) и сдвигают на 3 бита вправо. Примерно половина команд выполняю
нечетное количество "xor S" и в итоге безнадежно "портят" хеш. Еще 1/8 команд не делают ничего. А вот все остальные позволяют манипулировать битами младшего байта и выполнять сдвиги. Прогнал те же 255 значений через функцию выполняющую команду над числами "все FFFF", "0" и "F123..EF" получил распечатку вида (тестовые числа, код комадны, мои комментарии):

0FFFFFFFFFFFFFFF 0000000000000000 0123456789ABCDEF 02 <<4 >>4
0FFFFFFFFFFFFFFF 0000000000000000 0F123456789ABCDE 04 >>4
1FFFFFFFFFFFFF7F 0000000000000080 1E2468ACF135793D 80 >>3 0x80  10000000
1FFFFFFFFFFFFFFD 0000000000000003 02468ACF13579BDD 1A  <<4 ^0x1A >>3  00011010
3FFFFFFFFFFFFFFC 0000000000000000 048D159E26AF37BC 32 <<2 (<<4, >>2)
3FFFFFFFFFFFFFFF 0000000000000000 3C48D159E26AF37B 30 >>2


Комментарии дописывал по ходу работы, читая первую распечатку с точными действиями.
Взял требуемое число 0x0832CB347454C8AF в двоичном виде: 0000100000110010110010110011010001110100010101001100100010101111
Стартовое число M оканчивается на 1000000, это стало отправной точкой для формировани
нужного результата. Постепенно дописывал к нему/модифицировал несколько бит в конец
добавляя в входную строку команду. Очень напрягало, что в системе команд отсутствуют сдвиги на нечетное количество бит без выполнения побочных действий вроде "xor код-команды". Это сильно усложняло жизнь. Процесс проходил в текстовом файле (разумеется с добалением каждой команды в отладочную программу для проверки результата), примерно так:

1A: ........................................................10000011
F2: ....................................................100000110000
22: ...................................................1000001101000
D2: ................................................1000001100101001
------
32: .....10000011001011001011001101000111010001010100110000000101100
80: ........10000011001011001011001101000111010001010100110010000101
32: ......1000001100101100101100110100011101000101010011001000010100
AA: 0110100000110010110010110011010001110100010101001100100010101111
02: 0000100000110010110010110011010001110100010101001100100010101111


Так по битику и родилось нужное значение ...


Ответ 7

Взлом разминочного алгоритма от Firepro

Для интереса решил попробовать тупой перебор на поиск. Что бы поиск шел быстрее
поставил ограничение на символы до 5000.

int check = 766862343;
int hash = 0;

for (int i = 0; i < int.MaxValue; i++) 
{
    for (int ch = 0; ch < 5000; ch++)
    {
        if ((hash ^ (hash * 23 + ch)) == check)
            Console.WriteLine(hash + ":" + ch);
    }
    hash++;
}


Где-то через 20 минут на 32 000 000 получаем пару сотен коллизий.

32348910:4999
32348911:4975
32348912:4967
32348913:4943
32348914:4919
...


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

32349132 : 119 w
1446183 : 106 j
65727 : 111 o
2970 : 79 O
85 U : 1068 Ь


Один из вариантов пароля UЬOojw


Ответ 8

Взлом алгоритма  от Eanmos 

Алгоритм действительно очень простой.

Первое, что я сделал это нашел строку на которой функция дает значение чуть большее, чем нужно:

wchar_t a[] = {
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0x6FFF,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0};


А далее перебирается первый аргумент от 1 до 0xFFFF.

#include 
using namespace std;

int h(wchar_t* s)
{
    uint64_t h = 0;
    if (wcslen(s) < 60) return 0;
    for (uint64_t i = 1; *s++; h += *s*i + *(s-1) * i, i++);
    return h; // == 0x75F00B5; // 123666613
}

int f(wchar_t* s)
{
    uint64_t h = 0;
    if (wcslen(s) < 60) return 0;
    for (uint64_t i = 1; *s++; h += *s*i + *(s-1) * i, i++);
    return h == 0x75F00B5;
}

int main() {
    wchar_t a[] = {
    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
    0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
    0xFFFF, 0xFFFF, 0xFFFF, 0x6FFF,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0};
    for (int i = 1; i < 0xFFFF; i++) {
        a[0] = i;
        if (h(a) == 123666613) {
            cout << i << endl;
            break;
        }
    }
    cout << f(a);
    return 0;
}


Ответ:

wchar_t a[] = {
56656, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 
0xFFFF, 0xFFFF, 0xFFFF, 0x6FFF,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0};


Ответ 9

https://ru.stackoverflow.com/a/669698/10105

Пароль: "My_Extra_Fix_Passord-(836199132".

Глядя в алгоритм, видно, что функцию сравнения использует лишь partition3. Эта функци
сравнения «выплёвывает» в вывод 75% символов партиционируемого отрезка, а в остальны
позиции кладёт символ, по которому ведётся партиционирование. Порядок сравнения символов в партиционируемом отрезке — строго от начала к концу. Кроме того, в функции Array::qsort видно, что партиционирование всегда ведётся по первому символу. Смотря в кодовое слово

My_EMtraMFixMPasMordM(83M199M32EE-(8E619E132-(83-199-328861


замечаем повторяющийся через 4 символ M. Это вывод одного и того же, первого партиционировани
по всей длине пароля (т. к. больше символ M ни в левой, и в правой группе не встретится). Итак, наш пароль имеет вид

My_E?tra?Fix?Pas?ord?(83?199?32E


причём последние символы до ? могут и не присутствовать в пароле. Предположим, чт
длина ровно 32 символа, то есть строка заканчивается на E. Модифицируем функцию qsort, чтобы она выводила свои промежуточные результаты:

def qsort(&block)
  return self.dup if size <=1
  c,l,r = partition3 {|x| block.call(first,x)}
  puts("partition, pivot = #{first}, l=#{l.join}, r=#{r.join}, c=#{c.join}")
  l.qsort(&block) + c + r.qsort(&block)
end

$z = 'My_EMtraMFixMPasMordM(83M199M32EE-(8E619E132-(83-199-3288619813236113211199yyxtry_ixyPasyord_xtr__ix_Pas_ordxtraxxasxordtraitssotdrarassrrdaaaodiodss'

def check(password)
  z = $z
  h = g_c(password)
  i = 0; // увеличиваем, когда есть общий кусок
  if (h[0...i] == z[0...i])
    puts("starting #{i} symbols match")
  else
    puts("starting #{i} symbols DIFFER")
  end
  puts(h[i..-1])
  puts(z[i..-1])
  puts("diff = #{dist(h, z)}")
  h == z
end


(функция dist считает количество несовпадающих символов в двух строках)

Получаем первую партицию:

pivot = M, l=EF(8319932E, r=y_~tra~ix~Pas~ord~~~, c=M


Следующее партиционирование должно быть, согласно алгоритму, у последовательност
EF(8319932E, и вывод должен тогда иметь вид EF(8E199E.... Но в реальной строке F отсутствует
а на его месте -: E-(8E.... Спасти ситуацию, вставив другие символы на место ~, не получается. Это означает, что предположение о длине строки неверно. Пробуем длину на единицу меньше.

My_E?tra?Fix?Pas?ord?(83?199?32


Первая партиция

pivot = M, l=EF(8319932, r=y_~tra~ix~Pas~ord~~~, c=M


Вывод второй партиции выглядит как EE(83E..., из которых второй и третий экземпля
E означает элемент, по которому проводилось партиционирование. Фактически мы видим EE-(8E...
это означает, что один из символов ~ перед скобкой должен быть на самом деле -, чтобы попасть в партиционируемую группу (а остальные больше M). В первых двух позициях получается плохой результат, а в третей EE-(8E, как и нужно.

Далее, в следующем партиционировании

pivot = E, l=-(8319932, r=F, c=E


у нас получается группа -(8E199E2, а в реальности -(8E619E132, что даёт хвост парол
(836199132. С таким паролем у нас уже выходит верная первая половина кодового слова, отвечающего за первую партицию:

My_EMtraMFixMPasMordM(83M199M32EE-(8E619E132-(83-199-3288619813236113211199


Переходим ко второй половине. Партиционирование y_~tra~ixPas~ord~

pivot = y, l=_traixPasord, r=~~~~, c=y


выдаёт строку yy~try~, а должно получиться yyxtry_. Похоже на то, что  вместо перво
~ у нас x, а вместо второй — _. Получаем уточнённый пароль My_Extra_Fix-Pas~ord~(836199132
Дальнейший вывод yas~yrd~, а должен быть yPasyord, это значит, что у нас сдвиг на один символ, а значит, предположение о том, где находится -, было неверно. Из двух вариантов My_Extra_Fix~Pas-ord~(836199132 и My_Extra_Fix~Pas~ord-(836199132 второй производит намного более длинную совпадающую строку.

В этой точке осталось разгадать два символа. Проще всего их сбрутфорсить, но исход
из человеческого фактора, на месте второй тильды должен бы быть s или w. Поскольку у нас нигде не встречается буква w, пробуем букву s. На место последнего символа перебором получаем _.

Всё!


Ответ 10

https://ru.stackoverflow.com/a/669774/182935

Ответ:

int P[2] = {0x9FC1C7F6,0};
    char *cc = (char *)&P;

Переводить в символы не стал).

В коде баг или как? Часть с использованием `m[]` не работает (xor от него равен 0)


Ответ 11

Взлом еще одного алгоритма представленного Vitaly

Пароль:

AeMzQ8oZk31W4B(L\1Uh$,9m
#include 
#include 

typedef unsigned char uchar;
uchar need[]="Tp9?k=HDN&nD{9 ~JzUYG3h>lF {`> K<% pm~J>y E=2B=y+Z";

int check(uchar * pwd) {
    uchar * a = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
    int d = strlen(a), i, j;
    for (i = 0, j = strlen(pwd); i < j; i++) {
        if (strchr(a, pwd[i]) == NULL) pwd[i] = a[pwd[i] % d];
        if (i > 0) pwd[i - 1] = a[(((pwd[i - 1] ^ pwd[i]) << 1) * pwd[i]) % d];
    }
    return !strcmp(pwd, need);
}
int main(int argc, char ** argv) {
    uchar pwd[3];
    int len=strlen(need);
    uchar * pwd2 = calloc(len+5, sizeof(char));
    int i;
    memset(pwd2,31,255);
    pwd2[len-1]=need[len-1]; pwd2[len]=0;
    pwd[2]=0;
    for(i=len-2;i>=0;i--) {
      char c,found;
      found=0;
xx:
      pwd[1]=pwd2[i+1];
      for(pwd2[i]++;pwd2[i]<0x7F;pwd2[i]++) {
       pwd[0]=pwd2[i];
       check(pwd);
       if(pwd[0]==need[i]) { found++; break; }
      }
     if(!found) {
      pwd2[i]=31;
      if(++i>len-2) break;
      goto xx;
     }
   }
   printf("\n%s\n",pwd2);
   printf("Result: %s\n", check(pwd2) ? "OK" : "FAIL");
   return 0;
}


Ответ 12

Действительно, было бы смешно не взломать Алгоритм

Я конечно не очень шарю в С++, да и фиг его знает какой тип подкинет компилятор вмест
auto для h. Скорее всего в вашем случае он подставил тип int. И коллизий будет мног
уже при длине слова 2, например 237 и 84 символы. И даже если он каким-то чудом определит h как long, то тот же вагон коллизий случится на словах в три символа, например 187, 44, 77

Подходит, например, пароль "yBw".