алгоритм обратной контрольной суммы


2

Я работаю над этим псевдокодом, пытаясь найти правильный ввод для ожидаемого вычисленного значения (я не уверен, могу ли я назвать его контрольной суммой). Я не могу сфокусироваться, чтобы генерировать обратный алгоритм, тогда любая помощь приветствуется.

Я могу начать со значения 2602618273338008543 в v20 и xor обратно на случайном сгенерированном входе, но я думаю, что конечный результат был бы слишком большим, чтобы быть xored до нуля с помощью одного байта.

PS: Я прокомментировал некоторые строки, которые, я полагаю, не влияют на вычисления.

Побочный вопрос, почему результат проверяется на 2 значения (LOWORD (V20) == - 922952045 & & HIDWORD (V20) == -902699940 || v20 == 2602618273338008543i64)? будет ли результат отличаться при вычислении в двойных словах, чем с hiword/loword (dword)?

спасибо.

v20 = 0i64; 
    // salt table 
    v28="a#+EJK45fe/efJWDSlesfGe03saHHFddfdq2gr%a3ß0jm2ÜcFEF!JKMÄrAfim+wqe=WD=?f3jDKefDJ§W?)JöSeAEFj_LIeJDF"; // salt table 
    input = new byte[32] { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }; 
    for (j = 0; j < 200; ++j) 
    { 
     v24 = (v20 + j) % 60 + 1; // 0x3c 
     v15 = input[7 * j % 15]; 
     if (v24 == 32) // 0x20 
     v15 = __PAIR__(v15, HIDWORD(v15)); 
     if (v24 == 31) // 0x1f 
     { 
     // v22 = v24 & 31; // 0x1f 
     // v11 = HIDWORD(v15); 
     // v8 = v15; 
     v1 = (unsigned __int64)(v15 << (v24 & 0x1F)) >> 32; 
     LODWORD(v15) = __PAIR__((unsigned int)v15, HIDWORD(v15)) << (v24 & 0x1F) >> 32; 
     HIDWORD(v15) = v1; 
     } 
     // v6 = v15; 
     v20 += v15; 
     v25 = (v20^(unsigned __int64)j) % 62 + 2; // 0x3e + 2 
     v2 = (v20 - j) % 91; // 0x5Bui64 
     LODWORD(v16) = *(int *)((char *)&v28 + v2); 
     HIDWORD(v16) = *(int *)((char *)&v29 + v2); // &v29=&v28-4 
     if (v25 & 32) // 0x20 
     v16 = __PAIR__(v16, HIDWORD(v16)); 
     if (v25 & 31) // 0x1f 
     { 
     // v21 = v25 & 31; // 0x1f 
     // v9 = HIDWORD(v16); 
     // v10 = v16; 
     v3 = (unsigned __int64)(v16 << (v25 & 0x1F)) >> 32; 
     LODWORD(v16) = __PAIR__((unsigned int)v16, HIDWORD(v16)) << (v25 & 0x1F) >> 32; 
     HIDWORD(v16) = v3; 
     } 
     v7 = v16; 
     v20 ^= v16; 
    } 
    if ((_DWORD)v20 == -922952045 && HIDWORD(v20) == -902699940 || v20 == 2602618273338008543i64) 
     v23 = 1; 
    } 

Edit:

Вот действительный C++ код для того же алгоритма.

#define LODWORD(_qw) ((DWORD)(_qw)) 
#define HIDWORD(_qw) ((DWORD)(((_qw) >> 32) & 0xffffffff)) 

uint64_t v22, v11, v6, v7, v9, v21, v20, v24, v15, v16, v25, v2, v3, vx = 0; 
const char _v28[] = "a#+EJK45fe/efJWDSlesfGe03saHHFddfdq2gr%a3ß0jm2ÜcFEF!JKMÄrAfim+wqe=WD=?f3jDKefDJ§W?)JöSeAEFj_LIeJDF"; // salt table 
const byte input[] = { 0x3B, 0x8F, 0x80, 0x01, 0x00, 0x00, 0x53, 0x54, 0x4F, 0x4C, 0x4C, 0x4D, 0x31, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3A }; 

int j, v1, v8, v10; 

uint64_t QW_Swap(uint64_t v) 
{ 
    uint64_t temp = v & 0xFFFFFFFF; // extract the low 
    v >>= 32; // shift right 
    v |= (temp << 32); // put the previous low in the high 
    return v; 
} 

void setLODWORD(uint64_t *_var, DWORD _v) 
{ 
    *_var &= 0xFFFFFFFF00000000; 
    *_var |= (uint64_t)_v; 
} 

void setHIDWORD(uint64_t *_var, DWORD _v) 
{ 
    *_var &= 0xFFFFFFFF; 
    *_var |= (uint64_t)_v << 32; 
} 

void atrCRC() 
{ 
    v20 = 0; 
    v16 = 0; 

    byte * inp; 
    inp = (byte*)&input; 
    byte * v28; 
    v28 = (byte*)&_v28; 

    for (j = 0; j < 200; ++j) 
    { 
     v24 = (v20 + j) % 0x3C + 1; 
     v15 = *(uint64_t*)(inp+(7 * j % 15)); 
     if (v24 & 0x20) 
      v15 = QW_Swap(v15); 
     if (v24 & 0x1F) 
     { 
      v22 = v24 & 0x1F; 
      v11 = HIDWORD(v15); 
      v8 = v15; 
      v1 = (uint64_t)(v15 << (v24 & 0x1F)) >> 32; 
      setLODWORD(&v15, (QW_Swap(v15) << (v24 & 0x1F) >> 32)); 
      setHIDWORD(&v15, v1); 
     } 
     v6 = v15; 
     v20 += v15; 
     v25 = (v20^(uint64_t)j) % 0x3E + 2; 
     v2 = (v20 - j) % 0x5B; 
     setLODWORD(&v16, *(int *)((char *)(v28 + v2))); 
     setHIDWORD(&v16, *(int *)((char *)((v28 + v2) +4))); 
     if (v25 & 0x20) 
      v16 = QW_Swap(v16); 
     if (v25 & 0x1F) 
     { 
      v21 = v25 & 0x1F; 
      v9 = HIDWORD(v16); 
      v10 = v16; 
      v3 = (uint64_t)(v16 << (v25 & 0x1F)) >> 32; 
      setLODWORD(&v16, (QW_Swap(v16) << (v25 & 0x1F) >> 32)); 
      setHIDWORD(&v16, v3); 
     } 
     v7 = v16; 
     v20 ^= v16; 
    } 

    /* 
    if (v20 == -922952045 && HIDWORD(v20) == -902699940 || v20 == 2602618273338008543i64) 
     v23 = 1; 
    */ 
} 

EDIT 2: немного упрощенный код

#define LODWORD(_qw) ((DWORD)(_qw)) 
#define HIDWORD(_qw) ((DWORD)(((_qw) >> 32) & 0xffffffff)) 

uint64_t v22, v20, v24, v15, v2, v3 = 0; 
const char _v28[] = "a#+EJK45fe/efJWDSlesfGe03saHHFddfdq2gr%a3ß0jm2ÜcFEF!JKMÄrAfim+wqe=WD=?f3jDKefDJ§W?)JöSeAEFj_LIeJDF"; // salt table 
const byte input[] = { 0x3B, 0x8F, 0x80, 0x01, 0x00, 0x00, 0x53, 0x54, 0x4F, 0x4C, 0x4C, 0x4D, 0x31, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x3A }; 

int j; 

uint64_t QW_Swap(uint64_t v) 
{ 
    uint64_t temp = v & 0xFFFFFFFF; // extract the low 
    v >>= 32; // shift right 
    v |= (temp << 32); // put the previous low in the high 
    return v; 
} 

void setLODWORD(uint64_t *_var, DWORD _v) 
{ 
    *_var &= 0xFFFFFFFF00000000; 
    *_var |= (uint64_t)_v; 
} 

void setHIDWORD(uint64_t *_var, DWORD _v) 
{ 
    *_var &= 0xFFFFFFFF; 
    *_var |= (uint64_t)_v << 32; 
} 

void func(uint64_t x, uint64_t *var) 
{ 
    byte v22; 
    int t; 

    if (x & 0x20) 
     *var = QW_Swap(*var); 
    if (x & 0x1F) 
    { 
     v22 = x & 0x1F; 
     t = (uint64_t)(*var << v22) >> 32; 
     setLODWORD(var, (QW_Swap(*var) <<v22>> 32)); 
     setHIDWORD(var, t); 
    } 
} 

void atrCRC() 
{ 
    v20 = 0; 

    byte * inp; 
    inp = (byte*)&input; 
    byte * v28; 
    v28 = (byte*)&_v28; 

    for (j = 0; j < 200; ++j) 
    { 
     v24 = (v20 + j) % 0x3C + 1; // v20 = ((v24-1)*0x3c)-j; 
     v15 = *(uint64_t*)(inp+(7 * j % 15)); // *(uint64_t*)(out[j*15%7]) = v15; 

     func(v24, &v15); 

     v20 += v15; 
     v24 = (v20^(uint64_t)j) % 0x3E + 2; 

     v2 = (v20 - j) % 0x5B; 
     setLODWORD(&v15, *(int *)((char *)(v28 + v2))); 
     setHIDWORD(&v15, *(int *)((char *)((v28 + v2) +4))); 

     func(v24, &v15); 

     v20 ^= v15; 
    } 
} 
+1

Вы попробовали angr (http://angr.io/)? Символическое исполнение точно построено для таких вещей, если эти вещи не являются криптографически сильными - и вы можете видеть здесь (http://www.vantagepoint.sg/blog/81-solving-an-android-crackme-with-a- малосимволическое исполнение) пример для проверки подлинности лицензии на основе лицензии. 28 ноя. 172017-11-28 17:30:15

  0

Спасибо. Нет, я этого не делал, и на первый взгляд сомневаюсь, что это применится в моем случае, но я буду копаться в нем. 01 дек. 172017-12-01 19:11:32

1

Я бы не назвал то, что вы вывесили в вашем редактировать действительный C++ кода. Он может компилироваться, он может работать, но, хотя технический код C, это результат автоматизированного декомпилятора, и они, как правило, намного сложнее и загадочны, чем подлинный, созданный человеком код.

Когда я передал задачу создания обратного алгоритма части двоичного файла, я часто следующие три шага:

  1. Заново реализовать оригинальный алгоритм в легко читаемом виде.
  2. Убедитесь, что все части алгоритма действительно обратимы.
  3. реализовать инвертированный алгоритм по частям.

И еще несколько деталей:

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

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

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

Третьим и последним шагом будет размещение кода рядом с реализацией, которая пытается инвертировать вывод обратно на вход, начиная с небольших фрагментов всего алгоритма. Я бы начал с того, что только инвертировал небольшую часть алгоритма, запустил пару разных значений в конце моей реализации исходного алгоритма и на основе этого наращивал.

  0

спасибо. да, что я имел в виду, допустим, что он принят компилятором, я просто слегка изменил псевдокод. и да, я проверил разные входы во время отладки, и обе программы дали одинаковые результаты на всех этапах алгоритма. На самом деле я сомневаюсь, что он может быть отменен из-за потери бит при сдвиге (в func (uint64_t, * uint64_t)) Буду признателен, если это так, каковы будут мои варианты? bruteforcing 32-байтовый массив может занять некоторое время. 02 дек. 172017-12-02 19:52:16

  0

На самом деле, если вы присмотритесь ближе, я думаю, вы можете быть удивлены ... Хотя, как я уже сказал, это станет понятнее, если вы перепишите код самостоятельно. 03 дек. 172017-12-03 02:19:16

  0

Я пытаюсь, но то, что я вижу (x << y) >> 32 (где x <32) не является обратимым, поскольку это сдвиг, а не рулон, исправьте меня, если я ошибаюсь. V15 = * ((uint64_t *) (v28 + v2)); перезаписывается в зависимости от значения v2, которое зависит от v20, которое зависит от предыдущего значения v15. Возможно, что-то не хватает 03 дек. 172017-12-03 14:30:26