Получение алгоритма кодирования и написание генератора кодов

Здравствуйте, вопрос по криптографии, суть токова:

Есть игра, использующая перенос персонажа - сохранение в конце и загрузку в начале каждой игровой сессии - с помощью кодов.

Каждый код - это 5 блоков по 5 символов, плюс шестой блок переменной длины, от 2 до 4 символов.
Алфавит - латиница строчная, заглавная, плюс некоторые символы с клавиатуры в количестве 10 штук, всякие *()%!@#$. Словом, один символ влезает в 6 бит.

Во входной текст входят версия игры (предположительно 3 символа, алфавит - цифры и строчные), ник игрока, 9 параметров, из которых 2 - целые, заведомо в диапазоне 4 байт, а остальные в диапазоне 1 байта. Параметры таковы: класс персонажа, число очков опыта, текущей уровень, и т.д.

Ну и что-то я заглянул в свою папку с кодами и увидел следующее:
1) для имеющихся ~150 кодов распределение символов алфавита на первых одной-двух позициях явно не равномерное, часто встречаются коды следующего вида (далее первые символы 6 кодов, для которых это верно) :
8_(82 KRsfh... 8_1n6 +G_f0... 8_m)u 8i%Ks... 8_m)u Ea72%... 8_rjR 5)t2B... 8_xfz RJgL8...

2) а для 20-30 кодов одного персонажа, у которого с течением времени растет опыт и некоторые однобайтные характеристики, наблюдается периодическое совпадение одного или иногда даже двух блоков по 5 символов кода (далее примеры, в первом случае у двух кодов совпадают 1 и 2 блоки, во втором случае у двух кодов совпадают 5 блоки):

A3qit Ea72%...
A3qit Ea72%...

...7A80 G1e!z mk
...ENN6m G1e!z lmH

Как реконструировать алгоритм и написать кейген? Умею программировать.

 

По одним шифротекстам, даже без оригиналов, угадать алгоритм? Такое только экстрасенсы могут.

Алгоритм надо доставать из программы: искать в ней место, где данные сохраняются либо восстанавливаются, и смотреть, как выполняется преобразование. Это общий подход, конкретные шаги будут зависеть от особенностей программы. Но в любом случае для новичка задача непростая, по времени займёт, как минимум, несколько недель. Прикиньте, стОит ли овчинка выделки.

 

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

Как вы считаете, имеет ли это смысл (т.е., не описываю ли я проблему тысячелетия или нерешаемые средними умами задачи)? Если имеет, то какой бы мне почитать талмуд с методиками такового анализа?

 

sav,

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

 

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

 

Штатная задача - это реверсинг софта, который генерирует код, или исследование алгоритма кода без такового?
Сама задача не слишком интересует, а вот в криптографию я бы нырнул.

 

Описание непонятное какое-то. Эти "коды" что-то вроде пассвордов с приставки донди? То есть в них весь прогресс персонажа закодирован? Или коды нужны только для подтверждения того, что на другой аккаунт персонажа переносишь ты?

 

sav,

Как бы там небыло если ты задашь данный вопрос, то тебе сразу надают по голове, так как ты свою работу не выполнил по решению задачи.

 

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

 

Реверси игру, раз сеть в этом не участвует. Там одно или несколько полей - контрольная сумма, угадывать по-моему дело не особо перспективное.

 

Да, у меня тоже есть инсайд, что в коде содержится контрольная сумма, а именно CRC (правда конкретный полином и вводные неизвестны).

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

 

Кое-что существует. Но самая тупая побайтная(понибловая) замена a=b[a] ломает все арифметические и логические закономерности, если они там даже и были. То есть сделал ты код в одном состоянии, получил 1 копейку опыта, сделал другой, и ничего похожего на закономерность можешь между ними не обнаружить. Это всё очень интересно, но решение найдешь только если это все ну очень просто устроено. А если найдешь в игре нужный алгоритм, вероятность успеха стремится к 100%. Многократно сталкивался с чем-то отдаленно напоминающим это, поиск закономерностей почти ни разу ни к чему хорошему не привел.

ЗЫ: тем более если есть такой инсайд. Алгоритм црц это либо непосредственно сдвиги-ксоры, либо по таблицам выборки-ксоры, мимо не пройдешь. Можешь за это зацепиться.

 

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

Досадно, млин, хотел засесть за книжки, с удовольствием поковыряться в околоматане, а теперь придется (речь, кстати, о карте для warcraft 3) чинить старый лаунчер для игры в несколько окон*, ковыряться с отладчиком в asm / jass свинарнике... окей, на следующих выходных наверное поковыряю.

* - kloader для 1.26 запускает два экземпляра игры, второй - в некоем отладочном режиме, а дальше загружает во второй экземпляр dll, которая должна как-то просигнализировать и продолжить работу второго после успешного патча, но оно ничего не проверяет, пишет непонятно что непонятно куда и segfault

_
P. S. Отдельное спасибо за совет про таблицу! С другой стороны, даже если там не in-place реализация без вышеупомянутой, то подобрать пару "порождающий полином - стартовое слово" даже для CRC-16 головная боль (сталкивался в контексте встраиваемой техники), а тут вжух и CRC-32 какой-нибудь.

 

на сколько помню, читов для этой гамы хватало.

 

Из собственного опыта могу поведать следующее. В конце 90 у меня была приставка сега, в которой большинство игр позволяло продолжить прохождения, выдавая игроку пароли. Сам лично подбирал алгоритмы для таких игр как Road Rash 3, rock n roll racing, top gear, zero tolerance. В основу исследований лежало многократное прохождение уровня с разным количеством денег или патронов (zero tolerance), или наоборот, уровень другой, а патронов столько же. Пароль записывал в тетрадку, затем выявлял какие символы менялись, менял из на третьи, методом подбора контрольной суммы добивался валидности пароля, затем в игре смотрел что изменилось, результаты записывал. Будучи школьником, не имея интернета, но имея много свободного времени и желания смог сам составлять пароли, которые давали желаемые характеристики в игре. Помню, что так и не понял как генерируется пароль в игре Super Monaco Grand Prix 2, он там просто огромный) надо бы восполнить этот пробел 20+ летней давности)

 

Чисто теоретически, перейти от байт к входным и выходным битам, объединяя их в группы и смотреть strict avalanche criterion и propagation criterion. Отобрав те, которые хуже всего, заменять на линейные структуры, а те что лучше всего - оставлять для перебора.

 

Завтра (сегодня) у меня видимо будет день анализа.

На данный момент сделано следующее:

Есть выборка из ~75 шифров, в которых не менялась половина параметров, а менялись следующие: число убийств, очки опыта, и еще несколько коротких однобайтных параметров.

Для всех символов, входящих в алфавит шифра, составлена карта, в которой ключ это порядковый индекс (0, 1, 2 ... 68, 69, 70), а значение это символ (A, B, C ... a, b, c ... (, ), +, % ...).
Далее для каждого из шифров:
- Каждому символу в шифре сопоставлен его индекс. (Я не знаю, соответствует ли этот индекс машинному представлению, и на мой взгляд на этом этапе допущена ошибка, делающая бессмысленным получение дифференциала шифров)
- Каждый из индексов как целое число переведен в бинарное представление. Таким образом, весь шифр переведен в бинарную последовательность.
- Построена таблица дифференциалов всех шифров со всеми (Шифр1 XOR Шифр2), всего n^2 / 2 сочетаний. (я правильно употребляю термин "дифференциал"? подсмотрел где-то)

Распределение дифференциалов для сочетаний ~75 шифров таково:
76 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 0 до 10%,
107 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 10 до 20%,
1179 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 20 до 30%,
1458 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 30 до 40%,
105 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 40 до 50%,
1 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 50 до 60%,
0 сочетаний двух шифров имеют число изменившихся бит (дифференциал) от 60 до 100%.

Среднее значение дифференциала для всех сочетаний равно 0.296. В среднем 8.41 символ из 27-29-символьного ключа меняется.

С некоторой вероятностью установлено, что алгоритм шифрования не отвечает strict avalanche criterion.

Линейные структуры? Перебор?
https://habr.com/ru/post/215527/ это оно?

 

sav,
представьте, что у вас есть черная коробка которая что-то делает и выдает результат.
1) какая длинна входного слова? какая глубина алфавита для входного слова? бьется ли оно на независимые части, которые бы конкретно за что-то отвечали и имели свой размер? а в битах это сколько?
2) какая длинна выходного слова? какой алфавит? а в битах это сколько?

Таким образом становиться понятно, сколько стоит полный перебор, это будет 2 в какой-то степени. Взлом в криптографии - это уменьшение, на сколько возможно, этого перебора. Общая идея лавинного эффекта это описание количества изменений выходного слова от количества изменений во входном слове. Как это можно использовать есть в Бабенко Л.К., Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа.

Я бы зацепился за имя игрока. Больше какой длины, оно перестает восприниматься? Если сохранять имя А. АА. ААА что происходит? если А и B сравнить? если ВААА АВАА ААВА АААВ сравнить? Одним словом сперва найти близкие буквы, отличные в один бит друг от друга, а затем поводить этим битом туда-сюда, посмотреть на выход. И вот тут уже можно строить таблицы дифференциалов и\или искать линейные приближения булевых функций.

 

вроде, усе читкоды https://www.cheatcc.com/pc/warcraft3.html

 

Будет ли это иметь смысл, если с именем игрока будут также изменяться еще два (если очень повезет, то один) параметра? К сожалению, таковы имеющиеся ограничения генерации новых шифров. Уже есть выборка из пары десятков шифров с никами вида 1, 2 ... 111111(до предела длины ника), 22222(до предела длины ника), но у них у всех есть параметр опыта. который невозможно зафиксировать на нуле, он изменяется в пределах нескольких тысяч.