RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 669462
Accepted
VladD
VladD
Asked:2020-05-23 05:16:47 +0000 UTC2020-05-23 05:16:47 +0000 UTC 2020-05-23 05:16:47 +0000 UTC

天才黑客

  • 772

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

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

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

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

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

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

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

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

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

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

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

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

祝所有参与者好运!

любой-язык
  • 12 12 个回答
  • 10 Views

12 个回答

  • Voted
  1. Best Answer
    Firepro
    2020-05-24T18:43:33Z2020-05-24T18:43:33Z

    破解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. Firepro
    2020-05-23T07:34:10Z2020-05-23T07:34:10Z

    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. Firepro
    2020-05-25T09:37:27Z2020-05-25T09:37:27Z

    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. m9_psy
    2020-05-23T13:03:13Z2020-05-23T13:03:13Z

    @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. Mike
    2020-05-23T15:51:51Z2020-05-23T15:51:51Z

    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. Mike
    2020-05-26T15:41:54Z2020-05-26T15:41:54Z

    Взлом алгоритма представленного 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. Alex Krass
    2020-05-25T18:38:59Z2020-05-25T18:38:59Z

    Взлом разминочного алгоритма от 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. VladD
    2020-05-25T21:36:46Z2020-05-25T21:36:46Z

    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. pank
    2020-05-26T01:31:55Z2020-05-26T01:31:55Z

    Взлом алгоритма от 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. pavel
    2020-05-24T05:15:14Z2020-05-24T05:15:14Z

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

    回答:

    int P[2] = {0x9FC1C7F6,0};
        char *cc = (char *)&P;
    
    Переводить в символы не стал).
    
    В коде баг или как? Часть с использованием `m[]` не работает (xor от него равен 0)
    
    • 6

相关问题

  • 是否可以使用指示语气来构建程序?[关闭]

  • 代码中的注释应该怎么说?

  • “生产”和“研究”编程语言

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    Python 3.6 - 安装 MySQL (Windows)

    • 1 个回答
  • Marko Smith

    C++ 编写程序“计算单个岛屿”。填充一个二维数组 12x12 0 和 1

    • 2 个回答
  • Marko Smith

    返回指针的函数

    • 1 个回答
  • Marko Smith

    我使用 django 管理面板添加图像,但它没有显示

    • 1 个回答
  • Marko Smith

    这些条目是什么意思,它们的完整等效项是什么样的

    • 2 个回答
  • Marko Smith

    浏览器仍然缓存文件数据

    • 1 个回答
  • Marko Smith

    在 Excel VBA 中激活工作表的问题

    • 3 个回答
  • Marko Smith

    为什么内置类型中包含复数而小数不包含?

    • 2 个回答
  • Marko Smith

    获得唯一途径

    • 3 个回答
  • Marko Smith

    告诉我一个像幻灯片一样创建滚动的库

    • 1 个回答
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Алексей Шиманский 如何以及通过什么方式来查找 Javascript 代码中的错误? 2020-08-03 00:21:37 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    user207618 Codegolf——组合选择算法的实现 2020-10-23 18:46:29 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5