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

 eXeL@B —› Основной форум —› xor encryption, криптоанализ.
Посл.ответ Сообщение

Ранг: 210.5 (наставник), 2thx
Активность: 0.140
Статус: Участник

Создано: 01 мая 2009 00:44 · Поправил: arnix
· Личное сообщение · #1

Попросили помочь с задачкой. Пошел-пошел, приостановился Так как сроки поджимают, решил и кому не лень тоже подклюичть к решению

Итак, что есть:
TEST.ENCRYTED - зашифрованный файл (размер 48443 bytes)
TEST.ORIG_PART - меленькая часть (начало) из оригинального файла (размер 1272 bytes)

Чтобы выяснить что это за шифровка, сначала была написана следующая программа (analyze.c):
Code:
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. int main(int argc, char* argv[])
  4. {
  5.     FILE* enc;
  6.     FILE* orig;
  7.     int orig_byte;
  8.     int enc_byte;
  9.     int n = 0;
  10.     enc = fopen("TEST.ENCRYTED", "rb");
  11.     dec = fopen("TEST.ORIG_PART", "rb");
  12.     if (orig != NULL && enc != NULL)
  13.     {
  14.         while ( ((orig_byte = fgetc(orig)) != EOF) &&
  15.                 ((enc_byte = fgetc(enc)) != EOF) )
  16.         {
  17.             printf("%04X: %02X xor %02X = %02X\n", n++, orig_byte, enc_byte, orig_byte ^ enc_byte);
  18.         }
  19.         fclose(enc);
  20.         fclose(orig);
  21.     }
  22.     else
  23.     {
  24.         printf("file open error");
  25.     }
  26.     return 0;
  27. }


Запускаем программу: analyze >analyze.txt
и получаем текстовый файли, одного взгляда достаточно, чтобы понять что предположения что это xor-based шифровка верны, вот кусок:

Code:
  1. 0000: 2F xor 16 = 39
  2. 0001: 2A xor 1A = 30
  3. 0002: 0A xor 0A = 00
  4. 0003: 20 xor 20 = 00
  5. 0004: 2A xor 13 = 39
  6. 0005: 20 xor 10 = 30
  7. 0006: 43 xor 43 = 00
  8. 0007: 6F xor 6F = 00
  9. 0008: 70 xor A4 = D4
  10. 0009: 79 xor E0 = 99
  11. 000A: 72 xor 7A = 08
  12. 000B: 69 xor 69 = 00
  13. 000C: 67 xor B3 = D4
  14. 000D: 68 xor F1 = 99
  15. 000E: 74 xor 7C = 08
  16. 000F: 20 xor 20 = 00
  17. 0010: 28 xor CB = E3
  18. 0011: 63 xor 00 = 63
  19. 0012: 29 xor 38 = 11
  20. 0013: 20 xor 20 = 00
  21. 0014: 31 xor D2 = E3
  22. 0015: 39 xor 5A = 63
  23. 0016: 39 xor 28 = 11
  24. 0017: 37 xor 37 = 00
  25. 0018: 0A xor F4 = FE
  26. 0019: 20 xor ED = CD
  27. 001A: 2A xor 33 = 19
  28. 001B: 20 xor 20 = 00
  29. 001C: 53 xor AD = FE
  30. 001D: 69 xor A4 = CD
  31. 001E: 6C xor 75 = 19
  32. 001F: 69 xor 69 = 00


Длина ключа - 4 байта, начальный ключ - 39 30 00 00
Каждым ключем шифруются два блока по 4 байта, потом ключ каким-то образом меняется, и так до тех пор пока есть данные. Нужно понять каким образом меняется ключ. Есть определенные успехи. Самая легкая добыча - 4-й байт, он
++ится через каждые F0 байт.

С 4-м байтом разобрались, чтобы помочь себе с остальными 3-я, я написал вторую программу, которая считывает разницу между байтам ключей (назовем Delta). Файл в архиве, analyze2.c. Запускаем - analyze2 >analyze2.txt, вот кусок результата:

Code:
  1. 0000     39 Delta: 00          30 Delta: 00         00 Delta: 00                 
  2. 0001     D4 Delta: 9B          99 Delta: 69         08 Delta: 08                 
  3. 0002     E3 Delta: 0F          63 Delta: CA         11 Delta: 09                 
  4. 0003     FE Delta: 1B          CD Delta: 6A         19 Delta: 08                 
  5. 0004     8D Delta: 8F          97 Delta: CA         22 Delta: 09                 
  6. 0005     98 Delta: 0B          61 Delta: CA         2B Delta: 09                 
  7. 0006     B7 Delta: 1F          CB Delta: 6A         33 Delta: 08                 
  8. 0007     42 Delta: 8B          95 Delta: CA         3C Delta: 09                 
  9. 0008     51 Delta: 0F          7F Delta: EA         45 Delta: 09                 
  10. 0009     6C Delta: 1B          C9 Delta: 4A         4D Delta: 08                 
  11. 0010     7B Delta: 0F          93 Delta: CA         56 Delta: 09                 
  12. 0011     16 Delta: 9B          7D Delta: EA         5F Delta: 09                 
  13. 0012     25 Delta: 0F          C7 Delta: 4A         67 Delta: 08                 
  14. 0013     30 Delta: 0B          91 Delta: CA         70 Delta: 09                 
  15. 0014     CF Delta: 9F          7A Delta: E9         79 Delta: 09                 
  16. 0015     DA Delta: 0B          C4 Delta: 4A         81 Delta: 08                 
  17. 0016     E9 Delta: 0F          AE Delta: EA         8A Delta: 09                 
  18. 0017     84 Delta: 9B          78 Delta: CA         93 Delta: 09                 
  19. 0018     93 Delta: 0F          C2 Delta: 4A         9B Delta: 08                 
  20. 0019     AE Delta: 1B          AC Delta: EA         A4 Delta: 09                 
  21. 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



Ранг: 210.5 (наставник), 2thx
Активность: 0.140
Статус: Участник

Создано: 01 мая 2009 00:50 · Поправил: arnix
· Личное сообщение · #2

Забыл текстовые файлы прикрепить:

6fd4_30.04.2009_CRACKLAB.rU.tgz - analyzes_txt_results.zip



Ранг: 218.5 (наставник), 2thx
Активность: 0.090
Статус: Участник

Создано: 01 мая 2009 03:01
· Личное сообщение · #3

arnix пишет:
Неужели random?

А расшифровывать потом тоже рандомом?



Ранг: 210.5 (наставник), 2thx
Активность: 0.140
Статус: Участник

Создано: 01 мая 2009 03:34
· Личное сообщение · #4

0xy пишет:
А расшифровывать потом тоже рандомом?


гы нет ну может задачка специально такая чтобы расшифровать пользуясь методом анализа испольования частоты букаф. Хотя врядли Если честно, когда писал про рандом не подумал что 0xy пишет:
А расшифровывать потом тоже рандомом





Ранг: 1053.6 (!!!!), 1078thx
Активность: 1.060.81
Статус: Участник

Создано: 01 мая 2009 07:03
· Личное сообщение · #5

может проще прогу добить которая так шифрует?
хотя если таковой нет
то можно в тупую взять все известные алго
взять для них исходную строку и прогнать по всем алго
получив результат смотреть на что больше похоже
и уже от туда копать



Ранг: 301.4 (мудрец), 194thx
Активность: 0.170.01
Статус: Участник

Создано: 01 мая 2009 07:50 · Поправил: Veliant
· Личное сообщение · #6

В первом столбце первый байт:
1 идет 1*1**1**1
8 идет 8**8**8***8

при наложении складываются ну а концовки как ты и сказал чередуются b и f


Во втором столбце последовательность первого байта такая(сумма этих последовательностей)
2*2**2*2**2**2*2**2**2*2**2*2**2**2*2**2**2*
44444444444444444444444444444444444444444444
*8*88*88*88*88*88*88*88*88*8*88*88*88*88*88*

итого маски такие
2*2**2*2**2**2*2**2**
*8*88*88*88*88*88*88*88*88
а 4 везде

как видишь у 2 и 8 наблюдается закономерности, а на их стыках появляются 9 во втором байте(а может и по их сумме, когда превышает какое то число)




Ранг: 1288.1 (!!!!), 273thx
Активность: 1.290
Статус: Участник

Создано: 01 мая 2009 08:15 · Поправил: Модератор
· Личное сообщение · #7

Больше смахивает на какую-то прогрессию - каждое последующее число в 4 байта больше предыдущего. И число 00003039 = 12345 (10) не зря вставлено...

ЗЫ: это учебная задачка или реальная?



Ранг: 210.5 (наставник), 2thx
Активность: 0.140
Статус: Участник

Создано: 01 мая 2009 12:21 · Поправил: arnix
· Личное сообщение · #8

Veliant
Спасибо большое Опыт или утилиты?

arnix пишет:
А старшие 4 бита в случае первого байта - один из этих - 0, 1, 8, 9, в случае второго байта - один из 4, 6, C, E.


А ведь из этих чисел что я перечислил я мог бы и догадаться что используются наложения с складыванием, а не догадался

Ara пишет:
ЗЫ: это учебная задачка или реальная?


учебная



Ранг: 301.4 (мудрец), 194thx
Активность: 0.170.01
Статус: Участник

Создано: 01 мая 2009 12:57 · Поправил: Veliant
· Личное сообщение · #9

Да не за что... кстати маски гораздо длинее... и почему то в районе 113-114 символа начинает косячить расшифровка....
Ни опыта ни утилит... скажем так методом в лоб решал)

Добавлено:
немного помучавшись удалось расшифровать начало исходника более менее... Но чем дальше в лес тем больше дров как говорится



f398_01.05.2009_CRACKLAB.rU.tgz - default.txt



Ранг: 210.5 (наставник), 2thx
Активность: 0.140
Статус: Участник

Создано: 02 мая 2009 10:44
· Личное сообщение · #10

Veliant пишет:
Но чем дальше в лес тем больше дров как говорится


Да, заметил во 2-м байте ключа сначала появляются какие-то +1 и -1-ы, +2 и -2, потом вообще все меняется..



Ранг: 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 !


 eXeL@B —› Основной форум —› xor encryption, криптоанализ.
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати