xor encryption, криптоанализ.

Сейчас на форуме: Magister Yoda (+5 невидимых)

Посл.ответ	Сообщение
arnix Ранг: 210.5 (наставник), 2thx Активность: 0.14↘0 Статус: Участник	Создано: 01 мая 2009 00:44 · Поправил: arnix · Личное сообщение · #1 Попросили помочь с задачкой. Пошел-пошел, приостановился Так как сроки поджимают, решил и кому не лень тоже подклюичть к решению Итак, что есть: TEST.ENCRYTED - зашифрованный файл (размер 48443 bytes) TEST.ORIG_PART - меленькая часть (начало) из оригинального файла (размер 1272 bytes) Чтобы выяснить что это за шифровка, сначала была написана следующая программа (analyze.c): Code: #include <stdlib.h> #include <stdio.h> int main(int argc, char* argv[]) { FILE* enc; FILE* orig; int orig_byte; int enc_byte; int n = 0; enc = fopen("TEST.ENCRYTED", "rb"); dec = fopen("TEST.ORIG_PART", "rb"); if (orig != NULL && enc != NULL) { while ( ((orig_byte = fgetc(orig)) != EOF) && ((enc_byte = fgetc(enc)) != EOF) ) { printf("%04X: %02X xor %02X = %02X\n", n++, orig_byte, enc_byte, orig_byte ^ enc_byte); } fclose(enc); fclose(orig); } else { printf("file open error"); } return 0; } Запускаем программу: analyze >analyze.txt и получаем текстовый файли, одного взгляда достаточно, чтобы понять что предположения что это xor-based шифровка верны, вот кусок: Code: 0000: 2F xor 16 = 39 0001: 2A xor 1A = 30 0002: 0A xor 0A = 00 0003: 20 xor 20 = 00 0004: 2A xor 13 = 39 0005: 20 xor 10 = 30 0006: 43 xor 43 = 00 0007: 6F xor 6F = 00 0008: 70 xor A4 = D4 0009: 79 xor E0 = 99 000A: 72 xor 7A = 08 000B: 69 xor 69 = 00 000C: 67 xor B3 = D4 000D: 68 xor F1 = 99 000E: 74 xor 7C = 08 000F: 20 xor 20 = 00 0010: 28 xor CB = E3 0011: 63 xor 00 = 63 0012: 29 xor 38 = 11 0013: 20 xor 20 = 00 0014: 31 xor D2 = E3 0015: 39 xor 5A = 63 0016: 39 xor 28 = 11 0017: 37 xor 37 = 00 0018: 0A xor F4 = FE 0019: 20 xor ED = CD 001A: 2A xor 33 = 19 001B: 20 xor 20 = 00 001C: 53 xor AD = FE 001D: 69 xor A4 = CD 001E: 6C xor 75 = 19 001F: 69 xor 69 = 00 Длина ключа - 4 байта, начальный ключ - 39 30 00 00 Каждым ключем шифруются два блока по 4 байта, потом ключ каким-то образом меняется, и так до тех пор пока есть данные. Нужно понять каким образом меняется ключ. Есть определенные успехи. Самая легкая добыча - 4-й байт, он ++ится через каждые F0 байт. С 4-м байтом разобрались, чтобы помочь себе с остальными 3-я, я написал вторую программу, которая считывает разницу между байтам ключей (назовем Delta). Файл в архиве, analyze2.c. Запускаем - analyze2 >analyze2.txt, вот кусок результата: Code: 0000 39 Delta: 00 30 Delta: 00 00 Delta: 00 0001 D4 Delta: 9B 99 Delta: 69 08 Delta: 08 0002 E3 Delta: 0F 63 Delta: CA 11 Delta: 09 0003 FE Delta: 1B CD Delta: 6A 19 Delta: 08 0004 8D Delta: 8F 97 Delta: CA 22 Delta: 09 0005 98 Delta: 0B 61 Delta: CA 2B Delta: 09 0006 B7 Delta: 1F CB Delta: 6A 33 Delta: 08 0007 42 Delta: 8B 95 Delta: CA 3C Delta: 09 0008 51 Delta: 0F 7F Delta: EA 45 Delta: 09 0009 6C Delta: 1B C9 Delta: 4A 4D Delta: 08 0010 7B Delta: 0F 93 Delta: CA 56 Delta: 09 0011 16 Delta: 9B 7D Delta: EA 5F Delta: 09 0012 25 Delta: 0F C7 Delta: 4A 67 Delta: 08 0013 30 Delta: 0B 91 Delta: CA 70 Delta: 09 0014 CF Delta: 9F 7A Delta: E9 79 Delta: 09 0015 DA Delta: 0B C4 Delta: 4A 81 Delta: 08 0016 E9 Delta: 0F AE Delta: EA 8A Delta: 09 0017 84 Delta: 9B 78 Delta: CA 93 Delta: 09 0018 93 Delta: 0F C2 Delta: 4A 9B Delta: 08 0019 AE Delta: 1B AC Delta: EA A4 Delta: 09 0020 BD Delta: 0F 76 Delta: CA AD Delta: 09 Начнем с 3-й колонки (3-й байт ключа), смотрим на дельты и улыбаемя, 3-й байт тоже поддался. А вот первые 2 - полузагадки, почему полу? Потому что закономерность "дельт" между младшими 4-я битам найти можно. В случае первого байта, это один раз B другой раз F, а вторй, почти всегда A, а иногда (то через 13 раз, то через 14 раз) - 9. А старшие 4 бита в случае первого байта - один из этих - 0, 1, 8, 9, в случае второго байта - один из 4, 6, C, E. Но как они получаются? Неужели random? Никакой закономерности не вижу Или что-то достаточно хитрое, или random. Я даже не поленился вот что сделал: так как оригинальный файл - исходник C++, была найдена частота использования того или иного символа в исходниках Linux Kernel (хотя там не C++ а C). После чего написана 3-я программа (decryper.c), которая умеет правильно считывать 3-й и 4-й байты ключа, а 1-й и 2-й байты выбирает самый часто используемый из четырех кандидатов. Но полученный "расшифрованный" файл все равно не полностью расшифрован Если поможет, расшифрованный файл из инета найти можно (ropeimpl.h). P.S. Я в crypto не особо бум-бум, так что если не вижу что-то очевидное, сорри P.S.2 Компилятор C - http://download.savannah.nongnu.org/releases/tinycc/tcc-0.9.24-win32-b in.zip (275 KB) 78c5_30.04.2009_CRACKLAB.rU.tgz - crypto_analyze.zip

arnix Ранг: 210.5 (наставник), 2thx Активность: 0.14↘0 Статус: Участник	Создано: 01 мая 2009 00:50 · Поправил: arnix · Личное сообщение · #2 Забыл текстовые файлы прикрепить: 6fd4_30.04.2009_CRACKLAB.rU.tgz - analyzes_txt_results.zip
0xy Ранг: 218.5 (наставник), 2thx Активность: 0.09↘0 Статус: Участник	Создано: 01 мая 2009 03:01 · Личное сообщение · #3 arnix пишет: Неужели random? А расшифровывать потом тоже рандомом?
arnix Ранг: 210.5 (наставник), 2thx Активность: 0.14↘0 Статус: Участник	Создано: 01 мая 2009 03:34 · Личное сообщение · #4 0xy пишет: А расшифровывать потом тоже рандомом? гы нет ну может задачка специально такая чтобы расшифровать пользуясь методом анализа испольования частоты букаф. Хотя врядли Если честно, когда писал про рандом не подумал что 0xy пишет: А расшифровывать потом тоже рандомом
reversecode Ранг: 1053.6 (!!!!), 1078thx Активность: 1.06↘0.81 Статус: Участник	Создано: 01 мая 2009 07:03 · Личное сообщение · #5 может проще прогу добить которая так шифрует? хотя если таковой нет то можно в тупую взять все известные алго взять для них исходную строку и прогнать по всем алго получив результат смотреть на что больше похоже и уже от туда копать
Veliant Ранг: 301.4 (мудрец), 194thx Активность: 0.17↘0.01 Статус: Участник	Создано: 01 мая 2009 07:50 · Поправил: Veliant · Личное сообщение · #6 В первом столбце первый байт: 1 идет 1111 8 идет 888*8 при наложении складываются ну а концовки как ты и сказал чередуются b и f Во втором столбце последовательность первого байта такая(сумма этих последовательностей) 22*22222222*2222222 44444444444444444444444444444444444444444444 8888888888888888888888888888 итого маски такие 22222222* 888888888888888*88 а 4 везде как видишь у 2 и 8 наблюдается закономерности, а на их стыках появляются 9 во втором байте(а может и по их сумме, когда превышает какое то число)
Ara Ранг: 1288.1 (!!!!), 273thx Активность: 1.29↘0 Статус: Участник	Создано: 01 мая 2009 08:15 · Поправил: Модератор · Личное сообщение · #7 Больше смахивает на какую-то прогрессию - каждое последующее число в 4 байта больше предыдущего. И число 00003039 = 12345 (10) не зря вставлено... ЗЫ: это учебная задачка или реальная?
arnix Ранг: 210.5 (наставник), 2thx Активность: 0.14↘0 Статус: Участник	Создано: 01 мая 2009 12:21 · Поправил: arnix · Личное сообщение · #8 Veliant Спасибо большое Опыт или утилиты? arnix пишет: А старшие 4 бита в случае первого байта - один из этих - 0, 1, 8, 9, в случае второго байта - один из 4, 6, C, E. А ведь из этих чисел что я перечислил я мог бы и догадаться что используются наложения с складыванием, а не догадался Ara пишет: ЗЫ: это учебная задачка или реальная? учебная
Veliant Ранг: 301.4 (мудрец), 194thx Активность: 0.17↘0.01 Статус: Участник	Создано: 01 мая 2009 12:57 · Поправил: Veliant · Личное сообщение · #9 Да не за что... кстати маски гораздо длинее... и почему то в районе 113-114 символа начинает косячить расшифровка.... Ни опыта ни утилит... скажем так методом в лоб решал) Добавлено: немного помучавшись удалось расшифровать начало исходника более менее... Но чем дальше в лес тем больше дров как говорится f398_01.05.2009_CRACKLAB.rU.tgz - default.txt
arnix Ранг: 210.5 (наставник), 2thx Активность: 0.14↘0 Статус: Участник	Создано: 02 мая 2009 10:44 · Личное сообщение · #10 Veliant пишет: Но чем дальше в лес тем больше дров как говорится Да, заметил во 2-м байте ключа сначала появляются какие-то +1 и -1-ы, +2 и -2, потом вообще все меняется..
DARKA Ранг: 6.2 (гость) Активность: 0=0 Статус: Участник	Создано: 04 мая 2009 09:59 · Личное сообщение · #11 Some tool for XOR analyzes: http://progress-tools.110mb.com/xortool.html Description: This application can do some basic XOR, ADD, SUB and ROR/L calculation, crypt files with these algorithms, search for crypted string inside file (for code with 1 char length) or analyze file for byte occurrence. Read more in Readme.txt !

Для печати