Реверсивный хеш, поиск коллизий (XOR с суммами и сдвигами влево / вправо)
A ^ ( (A >> 2) + (A << 5) + C ) == B
Как найти A, если B является const, а C является переменной? (C можно изменить, если с ним нет решения)
A это DWORD, B это DWORD, C это БАЙТ! = 0
Edit1: после ответа GalacticJello у меня есть еще один вопрос: Есть ли способ сделать это без цикла (упрощение выражения)?
Зачем мне это нужно:
Я пытаюсь сделать обратную функцию (поиск столкновений) для
unsigned int X(const char* const in) { //strlen(in) is always < 127
unsigned int result = 0x12345678; //just for an example
for(int i = 0; in[i] != 0; ++i)
result ^= (result >> 2) + (result << 5) + in[i];
return result;
}
В настоящее время у меня есть цикл, который генерирует случайный C, а затем ищет A.
(Я ищу A, используя цикл, который генерирует случайное значение [для A] и проверяет, верно ли приведенное выше выражение)
Edit2: Это мой текущий код для поиска коллизий, который я сейчас тестирую ..
#include <stdio.h>
#include <conio.h>
using namespace std;unsigned int originalHash(const char* const in) {
unsigned int result = 0x12345678;
for(int i = 0; in[i] != 0; ++i) {
result = result ^ ((result >> 2) + (result << 5) + in[i]);
}
return result;
}//A ^ ( (A >> 2) + (A << 5) + C ) == B
bool findSolutions(unsigned int inHash, char* _C, unsigned int* _A) { //Starts searching from *A and *C and writes there values on success.
unsigned int C = *_C;
if(C == 0) ++C;
unsigned int A = *_A;
for(C; C < 256; ++C) {
for(A; A < 0xFFFFFFFF; ++A) {
if((A ^ ( (A >> 2) + (A << 5) + C )) == inHash) {
*_C = C;
*_A = A;
return true;
}
}
A = 0;
}
return false;
}bool findCollisions(unsigned int inHash, char* szOutStr) {
const unsigned int REQ_HASH = 0x12345678;
unsigned int prevHash = 0;
int curChar = 0;
do {
printf("Loop Begin:\tI = %i | H = %08x | rH = %08x\n", curChar, inHash, REQ_HASH);
if(!findSolutions(inHash, &szOutStr[curChar], &prevHash)) {
printf("Unable to find solutions for %08x\n", inHash);
if(curChar == 0) return false;
--curChar;
continue;
}
if(prevHash == REQ_HASH) {
szOutStr[curChar] = 0;
return true;
}
printf("Found solution:\tC = %02x (%c) | A = %08x\n", szOutStr[curChar], szOutStr[curChar], prevHash);
char firstSolutionC = szOutStr[curChar];
unsigned int firstSolutionA = prevHash;
printf("Trying to find alternative solutions..\n");
do {
if(!findSolutions(inHash, &szOutStr[curChar], &prevHash)) {
printf("Alternative solution not found!\n");
break;
}
printf("Alternative solution found [%s valid]:\tC = %02x (%c) | A = %08x\n", prevHash == REQ_HASH ? "" : "not", szOutStr[curChar], szOutStr[curChar], prevHash);
if(prevHash == REQ_HASH) {
szOutStr[curChar] = 0;
return true;
}
++prevHash;
} while(true);
szOutStr[curChar] = firstSolutionC;
prevHash = firstSolutionA;
printf("Using first solution:\tC = %02x (%c) | A = %08x\n", szOutStr[curChar], szOutStr[curChar], prevHash);
++curChar;
inHash = prevHash;
} while(curChar < 127);
return false;
}
int main(void) {
char mask[] = "hQh";
DWORD original = originalHash(mask);
printf("%s == %08x\n", mask, original);
char out[128];
memset(out, 0, sizeof out);
if(findCollisions(original, out))
printf("%08x == %s\n", original, out);
else
printf("Unable to find collisions\n");
getch();
return 0;
}
Решение
Я просто собираюсь ответить на вопрос (извините за код C #, но вы должны быть в состоянии понять суть):
A ^ ((A >> 2) + (A << 5) + C) == B
static List<Tuple<uint, uint>> FindSolutions(uint B)
{
var solutions = new List<Tuple<uint, uint>>();
for (uint C = 0; C < uint.MaxValue; C++)
{
for (uint A = 0; A < uint.MaxValue; A++)
{
uint guess = A ^ ((A >> 2) + (A << 5) + C);
if (guess == B)
solutions.Add(new Tuple<uint,uint>(A, C));
}
}
return solutions;
}
var solutions = FindSolutions(0x00000001);
Если B — ваша константа (в данном случае 0x00000001), то первые несколько решений для A и C:
A = 0x8b439581, B= 0x00000001, C = 0x00000000
(0x8b439581 ^ ((22d0e560) + (6872B020) + 0)) == 0x00000001
0x8b439581 ^ (0x8b439580) == 0x00000001
0x00000001 == 0x00000001
другие:
A = 0x9ba5e354, B= 0x00000001, C = 0x00000000
A = 0x00000000, B= 0x00000001, C = 0x00000000
A = 0x6a7ef9db, B= 0x00000001, C = 0x00000004
… и т.п.
РЕДАКТИРОВАТЬ:
Чтобы найти столкновения, вы можете просто выполнить грубую силу через пространство клавиш.
Опять извините за код C #:
static uint originalHash(string input)
{
unt result = 0x12345678;
for (int i = 0; i < input.Length; i++)
result ^= (result >> 2) + (result << 5) + input[i];
return result;
}var charset = new string(Enumerable.Range(1, 255).Select(i => (char)i).ToArray());
var hits = new List<string>();
var hashToFind = originalHash("hQh");
for (int wordNum = 1; wordNum < int.MaxValue; wordNum++)
{
var word = Utils.NumberToString(wordNum, charset);
var guess = originalHash(word);
if (guess == hashToFind)
{
Console.WriteLine("Found: " + word);
hits.Add(word);
}
}
Выполнение вышеуказанного кода дало мне следующие коллизии через минуту или две:
cê cë1 côÌ cõí cö c ÷ ¦ cøG cùh dÌ1 dÍ dÒí dÓÌ dÖh d × G dئ dÙ e¬
e1 e²Ì e³í e¶G e · h e¸ f1 f f f f f f f f f f gg gn1
gq gr¦ gsG gth gwÌ gxí hO1 hP hQh hRG hS¦ hT hUí hVÌ i / i01 i1G
i2h i3 i4¦ i5Ì i6í
Это не очень хорошо, вот значения байтов:
{ 0x63, 0xEA, 0x10, }
{ 0x63, 0xEB, 0x31, }
{ 0x63, 0xF4, 0xCC, }
{ 0x63, 0xF5, 0xED, }
{ 0x63, 0xF6, 0x85, }
{ 0x63, 0xF7, 0xA6, }
{ 0x63, 0xF8, 0x47, }
{ 0x63, 0xF9, 0x68, }
{ 0x64, 0xCC, 0x31, }
{ 0x64, 0xCD, 0x10, }
{ 0x64, 0xD2, 0xED, }
{ 0x64, 0xD3, 0xCC, }
{ 0x64, 0xD6, 0x68, }
{ 0x64, 0xD7, 0x47, }
{ 0x64, 0xD8, 0xA6, }
{ 0x64, 0xD9, 0x85, }
{ 0x65, 0xAC, 0x10, }
{ 0x65, 0xAD, 0x31, }
{ 0x65, 0xB2, 0xCC, }
{ 0x65, 0xB3, 0xED, }
{ 0x65, 0xB6, 0x47, }
{ 0x65, 0xB7, 0x68, }
{ 0x65, 0xB8, 0x85, }
{ 0x65, 0xB9, 0xA6, }
{ 0x66, 0x8D, 0x31, }
{ 0x66, 0x8E, 0x10, }
{ 0x66, 0x91, 0xA6, }
{ 0x66, 0x92, 0x85, }
{ 0x66, 0x93, 0x68, }
{ 0x66, 0x94, 0x47, }
{ 0x66, 0x97, 0xED, }
{ 0x66, 0x98, 0xCC, }
{ 0x67, 0x6D, 0x10, }
{ 0x67, 0x6E, 0x31, }
{ 0x67, 0x71, 0x85, }
{ 0x67, 0x72, 0xA6, }
{ 0x67, 0x73, 0x47, }
{ 0x67, 0x74, 0x68, }
{ 0x67, 0x77, 0xCC, }
{ 0x67, 0x78, 0xED, }
{ 0x68, 0x4F, 0x31, }
{ 0x68, 0x50, 0x10, }
{ 0x68, 0x51, 0x68, }
{ 0x68, 0x52, 0x47, }
{ 0x68, 0x53, 0xA6, }
{ 0x68, 0x54, 0x85, }
{ 0x68, 0x55, 0xED, }
{ 0x68, 0x56, 0xCC, }
{ 0x69, 0x2F, 0x10, }
{ 0x69, 0x30, 0x31, }
{ 0x69, 0x31, 0x47, }
{ 0x69, 0x32, 0x68, }
{ 0x69, 0x33, 0x85, }
{ 0x69, 0x34, 0xA6, }
{ 0x69, 0x35, 0xCC, }
{ 0x69, 0x36, 0xED, }
Другие решения
Других решений пока нет …