主页 / 问题 / 669462
Accepted
VladD
Asked:2020-05-23 05:16:47 +0800 CST2020-05-23 05:16:47 +0800 CST

天才黑客

  • 772

所以我们来参加另一场比赛！这场比赛不同寻常，它由两部分组成。作业的主题是密码验证。

在比赛的第一部分，参赛者想出一个函数，它接受一个字符串并返回结果，这个字符串是否是密码（是/否）。下面是比赛的第二部分：黑客攻击。

您的目标是想出（或计算！）一个密码，比赛第一部分的函数将为其返回真实值。否则它会掉下来。

密码不必与函数作者预期的密码相匹配。可以使用作者密码不超过64个字符的信息。

请注意，作者有权在发布后 24 小时内对其答案进行编辑。每个问题的 hack 发布仅在问题发布后的前 72 小时内被接受。

发布答案时，请在被黑问题中发布指向它的链接。（最好直接在问题中而不是在评论中，并像其他黑客问题一样编辑标题。）

限制：您作为输入提供的字符串必须是您所用语言的有效字符串。例如，它不能驻留在无效内存中，也不能使用反射来“破坏”字符串的内部表示并导致函数“落在”它上面。如果算法将 unicode 字符串作为输入，则您的字符串也必须是 unicode。它可能非常大（例如，MAXINT)，但不占用超过一半的可用内存（以免算法仅仅存在于内存中而无法正常工作）。如果您的答案有必要，以编程方式“组合”字符串的过程在您的计算机上应该不会超过 1 分钟，并且不应导致 UB。黑客不应试图干扰函数的运行（例如，破坏其代码或使用的库的代码，将其传递给函数后更改密码内存等）。

如果被黑客攻击的功能因某种原因退出竞争，则其黑客攻击也会随之被淘汰。如果您的密码在测试时没有导致函数评估为 true 或失败，那么它也没有参加比赛。在同一功能的多个 hack 中，只有最后编辑日期的第一个才算数。你不能破解你自己的功能。（贡献者必须在专题发布时间之前注册。）

获胜者是未被淘汰并获得最多选票的 hack。

如果您使用了一些有趣的技巧来找到正确的密码，请在答案中告诉我们！它肯定会让你投票。

比赛结束日期为密码学家比赛结束后72小时，即2017年6月1日23:59:59。请记住，每个单独的问题只能破解三天，因此，例如，如果在密码学竞赛的最后一天没有发布任何功能，那么破解也不会在黑客竞赛的最后一天发布。如果被黑客攻击的功能从比赛中移除，则成功的黑客攻击可能会被淘汰出局。

该问题在golf chat 代码中讨论，如果您不了解条件，请在那里提问（好吧，最后的手段，如果您没有足够的声誉，请在评论中提问）。

祝所有参与者好运！

любой-язык

12 个回答

  1. Best Answer

    破解pank提出的算法

    def check(s):
  try:
    return int(s[:32], 16) * int(s[32:], 16) == 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845
  except:
    return False

    一个非常简单但不幸的是非常复杂的算法，它基于大数因式分解问题。大家都很清楚，将一个大数分解为因数的问题是一个非常难的事情，不能很快解决，而这里已经有一个76位的数了。

    1.黑客入侵的一般方式

    我们知道一个号码最多可以有 32 个字符，第二个号码可以有任意多的字符。我试图随机找到 2 个乘法器，但没有结果（这并不奇怪）。我能得到的最大值是在传递参数时：

    11111111111111111111111111111111708946551217595118393411775077160869888185470

    几乎相同的数字出来了：

    787718390241772353770457527863504200469636993 3875734065358324759903345757170

    原来的十进制看起来是这样的：

    7877183902417723537704575278635042004696369934776381519304816946969514108997

    马马虎虎的结果:)

    自然而然，我可以找2个这么大的乘法器找一个非常非常长的时间，所以我决定直接在代码中找问题。

    下面，我将给出一个案例，如果您不考虑所有可能的数据输入选项，那么即使是最酷的算法也无法避免您被黑客攻击。

    2. 源码分析与漏洞查找

    简短分析后，我开始反汇编代码结构，并看到

    s[:32] - 获取字符串中最多 32 个元素的所有字符

    s[32:] - 获取字符串的 32 个元素之后的所有内容

    更进一步，我们看到以下内容：

    int(s[:32], 16) * int(s[32:], 16)

    这意味着将 2 个十六进制数相乘。因此，您需要在十六进制系统中传输 2 个数字，大约。

    3. 漏洞

    事实证明，我可以替换数字 1 并替换我需要进入这一行的密钥。

    我们采取 2 行：

    1. 00000000000000000000000000000001
    2. 0x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845

    我们连接并得到：

    000000000000000000000000000000010x116a53fdcf374e3d8a4a19ca59a8017fd3680e7b707f9ed834a8ac4538586845

    代入函数，它返回True！这是胜利:)

    • 18

  2. Alex Krass 提出的算法 hack #1：

    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; }
}

    漏洞：

    这是一个简单的算法。该函数的全部要点在于它通过将它们添加到 -997 的原始总和，将这个数字乘以数字来计算ANSI字符串中字符的总和（a==97，b==98 等）字符数，然后除以 2。之后，它从输入字符串中的第 12 个字符开始取 5 个字符，并将其与结果数字进行比较。

    事实证明，您需要一个至少包含 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 个字符得到 57800，减去 977 得到 56823。然后除以 2 得到 28411.5，舍入到 int 得到 28411。

    被黑了！函数返回真

    解决方案 - 任何键：

    ihackyourkey28411alex!bba
sdfsdfsdfsdf43531degdfgdfgdfb06
    • 14

  3. pank 的算法黑客#2

    基于大数分解问题的算法。

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

    上次我们通过漏洞攻破了算法，这次潘克先生为我们关闭了一切……现在我们要通过算力攻破它。手动找到两个主要因素肯定行不通……但我们有更有趣的东西！

    首先，我们考虑到要在十进制数字系统中获得的数字如下所示：

    44354711195682213318901868940731534954425938156569080174424467380253591366943

    我们看着并感到悲伤..如果没有余数除以 2 是行不通的......

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

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

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

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

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

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

    Ответ

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

    294214717393397322902102113848520211047 * 150756262598431142388953822991693100169

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

    dd57b184ad4252c9b59ce1b6f849fa670x716a999c7f875e33d2e211fdc5c7b489

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

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

    • 12

  4. @alexolut 的伯恩斯坦。答：lb196fehe1ptnxn5whby37jm22qqawppD;:yr。我不知道那里的密码是什么，但你可以收集一大堆碰撞。

    #include <stdint.h>
#include <stdio.h>

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') 初始化目标字符串，然后简单地逐位递增每个字符，直到我们达到目标。我们可以很容易地随机取字符串的长度（或不是随机的）。生成器使用贪心算法（这不是最好的方法，远不是最快的，但有利于演示）——也就是说，每个符号的选择方式都尽可能接近目标，即使它最终陷入僵局。这种方法有时会导致生成器循环，卡在一个地方——在这种情况下，摇晃它并生成一个随机字符串。此步骤称为“突变”。如果我们尝试在没有建议的算法的情况下生成随机字符串 - 它不会导致任何结果（我试过） - 字符串太多而无法连续迭代它们。

    # 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 或其他。

    • 11

  5. Vladimir Gamalian 的算法“*7+7”

    #include <stdio.h>
#include <sys/types.h>

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，所以不需要40亿个值的完整循环，可以减少4倍的执行时间。此外，在分析中使用了这样的加速函数。

    我查看了a+b从 0 到 16 的参数的最终哈希（循环和）的值。立即清楚低 3 位始终为 111，第四位与参数的最后一位相反。晚上开始打印0到8192的函数值，到早上，工作了不到一半，不过前300个值足够分析了。我立即决定查看散列的整个最后一个字节AF，结果发现来自 arguments 1A、3A等的散列以它结尾5A。可以看出参数的低5位应该是11010，第六位是奇数。我立马看了下hash的末尾9AF，原来是给arguments 07A, 27A, 47A。所以第一个字母正好是7A( z)，第二个字节是偶数。派生函数值来自07A以 0x200 为增量。哈希的低两个字节09AF原来是用于参数087A, 287A,487A等687A。同理，快速查看增量0x2000、0x20000、...的几个值 ，我立即收到了参数的半个字节。

    • 10

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

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

#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 & 0xC ? (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

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

    • 9

  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

  8. 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. На место последнего символа перебором получаем _.

    Всё!

    • 8

  9. Взлом алгоритма от 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 <iostream>
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};
    • 8

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

    回答：

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

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

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

相关问题