Ностальгия: как работают «сохранения на бумажке»

    Признавайтесь, кто в детстве часами напролёт просиживал за игрой в «Денди» или «Сегу»? А кто по мере прохождения игры записывал пароли на бумажку или в специально заведённую тетрадку? Если это вы, и раз уж вы читаете этот сайт, то у вас наверняка хоть раз возникал вопрос: «а как же это работает?»

    Я постараюсь объяснить принципы работы классических механизмов генерации паролей на примерах из игр моего детства. Заранее прошу меня извинить за то, что все примеры будут с платформы NES (да, та, которая «Денди»), хотя тематика только ею не ограничивается. Так уж получилось, что не нашёл в себе достаточно мотивации, чтобы провести немного больше исследований и написать немного больше текста.

    Примеры буду приводить в порядке от простого к сложному. Поначалу кода будет немного, но чем дальше — тем сложнее объяснить алгоритмы языком человеческим и тем проще объяснить их языком техническим, так что не обессудьте.



    Кодовая книга


    У меня в памяти до сих пор сидят пароли некоторых уровней из игр моего детства — например, «BCHK» из «Trolls in Crazyland» («Doki! Doki! Yuuenchi»), «4660» из «Choujin Sentai — Jetman». Можно сказать, что это идеальные с точки зрения удобства пароли: их легко запомнить и трудно ошибиться при вводе. Но сколько же информации они могут содержать, и каков шанс случайно подобрать такой пароль?

    В первом случае алфавит пароля составляет 24 символа. Если посчитать количество комбинаций символов, то это будет 244 — не так уж и мало, учитывая, что в игре всего 12 уровней, и, собственно, кроме номера уровня пароль в себе ничего не хранит. Учтём несколько секретных паролей и посчитаем вероятность подобрать пароль с одной попытки: (12 + 4) / 244, что равно ~5.7×10-14. Другими словами, придётся перепробовать в среднем 17592186044416 паролей, прежде чем мы подберём какой-нибудь реальный.

    Во втором случае всё несколько иначе. Очевидно, что набор из 4-х цифр даёт нам ровно 10000 (104) комбинаций. Игра содержит пять уровней, которые можно проходить в разном порядке и два уровня сложности. Т.е. пароль хранит информацию о пройденных уровнях и уровне сложности. Таки образом, число существующих паролей равно 2×25, т.е. 64. Отсюда вероятность подобрать пароль равна 0.0064, т.е. больше, чем полпроцента. Мало ли это? В среднем примерно каждый 156-й пароль окажется верным, а учитывая довольно высокую скорость перебора, поиски долго не продлятся. И, честно признаюсь, в детстве мы часто «брутфорсили» игру, когда не хотелось начинать с самого начала.

    На самом деле информационную ёмкость таких паролей оценивать бессмысленно, поскольку они являются лишь своего рода ключами, т.е. игры просто хранят все возможные пароли, и по индексу введённого пароля получают информацию об уровне и прочем. Но интереса ради скажу, что их теоретическая ёмкость составляет 48 и 13 бит (log2244 и log2104).

    И всё же, как именно обрабатываются введённые пароли? В первом случае введённый пароль вообще не подвергается каким-либо преобразованиям, а просто ищется в хранимом массиве паролей.
    Показать код
    	const char* s_passwords[12] = 
    	{
    		"    ",
    		"BLNK",
    		// ...
    		"MZSX"
    	};
    	
    	// ...
    	
    	if (strncmp(pass, s_secretPassword1, 4) == 0)
    	{
    		callSecret1();
    		return 0;
    	}
    	
    	// ...
    
    	for (int level = 0; level < 12; level++)
    	{
    		if (strncmp(pass, s_passwords[level], 4) == 0)
    		{
    			return level;
    		}
    	}
    	return -1;
    


    А во втором случае игра поступает несколько хитрее, и сперва пароль подвергаются конвертированию в двоично-десятичный код, что уменьшает его размер ровно в два раза. Это даёт возможность и в самой игре уменьшить размер паролей в два раза.
    Показать код
    	uint16 toBCD(const char* pass)
    	{
    		uint16 result = 0;
    		for (int i = 0; i < 4; i++)
    		{
    			result <<= 4;
    			result |= (pass[i] - '0') & 0xF;
    		}
    		return result;
    	}
    
    	s_passwords[2][32] =
    	{
    		{
    			0x0000,
    			// ...
    			0x4660
    		},
    		{
    			0x7899,
    			// ...
    			0x5705
    		}
    	};
    	
    	// ...
    
    	const uint16 pass = toBCD(passStr);
    
    	for (int difficulty = 0; difficulty < 2; difficulty++)
    	{
    		for (int clearedLevels = 0; clearedLevels <= 0x1F; clearedLevels++)
    		{
    			if (pass == s_passwords[difficulty][clearedLevels])
    			{
    				setState(difficulty, clearedLevels);
    				return true;
    			}
    		}
    	}
    	return false;
    


    Числа и цифры


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

    А именно кодируются два значения: время и номер уровня. Т.к. пароль имеет длину в 8 цифр, т.е. 100 000 000 комбинаций, а в игре 14 уровней и 60 возможных значений времени (итого 840 вариантов), можно предположить, что его сложно подобрать. Но на самом деле это не так, и чтобы понять, почему, давайте сначала разберём принцип его генерации.

    Итак, сперва игра создаёт массив из 8-ми элементов, которые могут хранить значения от 0 до 9. Затем генерируется два случайных значения — тоже от 0 до 9 — и записываются в этот массив по индексам 2 и 5. Эти случайные значения — инкременты, которые будут добавляться к сохраняемым значениям по модулю 10. Это увеличивает количество возможных паролей в 100 раз, что, очевидно, усложняет выявление закономерностей.
    	const uint8 rand0 = rand() % 10;
    	const uint8 rand1 = rand() % 10;
    
    	char pass[8] = {0, 0, rand0, 0, 0, rand1, 0, 0};
    

    Далее кодируется индекс уровня (т.е. его номер минус единица): сумма двух старших бит индекса и второго инкремента по модулю 10 записывается по индексу 7, а сумма двух младших бит и первого инкремента — по индексу 1.
    	// Кодируем два старших бита номера уровня
    	pass[7] = ((level >> 2) + rand1) % 10;
    	
    	// Кодируем два младших бита
    	pass[1] = ((level & 3) + rand0) % 10;
    

    Настал черёд времени. С ним немного проще: сумма десятков и первого инкремента по модулю 10 записывается по индексу 0, а сумма единиц и второго инкремента по индексу 3. Получается, что при инкрементах, равных нулю, время запишется в десятичных цифрах, как есть. И, поскольку потолком десятков является 9, то максимально возможным значением времени является 99, а не «честные» 60 минут.
    	// Кодируем старшую цифру времени
    	pass[0] = ((time / 10) + rand0) % 10;
    
    	// Кодируем младшую цифру времени
    	pass[3] = ((time % 10) + rand1) % 10;
    

    Данные записаны, осталось посчитать контрольную сумму для проверки валидности пароля.
    	// Считаем контрольную сумму
    	sum = pass[0] + pass[1] + pass[2] + pass[3];
    	sum += (sum % 10) + pass[5];
    	sum += (sum / 10) + pass[7];
    		
    	// Записываем контрольную сумму
    	pass[4] = sum % 10;
    	pass[6] = sum / 10;
    

    Вот, например, легенда пароля 13-го уровня c 32-я оставшимися минутами — «96635134».


    Становится очевидно, что для подбора пароля достаточно, чтобы контрольная сумма подходила к закодированным данным. Тогда, если не учитывать её специфику, можно посчитать вероятность подобрать пароль: ровно 1% (единица делить на количество возможных значений суммы) — довольно много.

    Но ведь это же просто обыкновенная сумма! И для разных данных она может получиться одинаковой. Если изменить любой валидный пароль так, чтобы сумма первых 4-х цифр осталась прежней — он подойдёт. Что уж говорить о том, что у обыкновенной суммы распределение вовсе не равномерное, да и максимальное значение такой суммы никогда не превысит 72.

    Учитывая специфику такой суммы, выходит, что при линейном переборе вероятность её совпадения с данными очень велика. Именно поэтому на тематических форумах в сети можно часто встретить воспоминания людей о том, как ловко они подбирали пароли к Принцу Персии.

    Позиционные системы счисления


    Наверняка многие знакомы с Base64 и Base32. По своему определению это позиционные системы счисления с основаниями 64 и 32 соответственно. Принцип прост: разбиваем битовый поток на значения фиксированной битовой длины, а затем по определённому словарю берём символы по полученным значениям в качестве индексов.

    На таком принципе основаны многие системы паролей. И следующая игра, на примере которой я расскажу алгоритм генерации паролей, будет Takahashi Meijin no Bouken Jima IV, в простонародье больше известная как Adventure Island 4.

    Состояние игры включает в себя набор имеющихся предметов (до 12-ти), способностей (до 3-х), специальных предметов (до 6-ти), собранных сердец (до 8-ми), локацию с яйцом и информацию о пройденных уровнях. Но на самом деле за всё, кроме сердец и специальных предметов, отвечает одно значение — индекс прогресса. Это индекс в массиве, где каждый элемент хранит информацию об имеющихся предметах, способностях и прочем. Проще говоря, именно этот байт определяет набор предметов, способностей и пройденных этапов.

    Первый шаг алгоритма заключается в построении массива из четырёх байт. В первый байт записывается значение прогресса. Интересно, что допустимы только определённые его значения

    Во второй байт записывается маска имеющихся специальных предметов — 6 старших бит байта. В оставшиеся младшие 2 бита записывается константа, равная единице. Я предполагаю, что это версия формата пароля. А возможно и просто константа более строгой верификации введённых паролей.

    В третий байт записывается индекс локации, где установлено яйцо (для тех, кто не играл — своеобразный чекпоинт). Если яйцо нигде не установлено, то значение равно 0xFF. Индекс локации с яйцом тоже может принимать только определённые значения — туда входят только те локации, где яйцо можно установить.

    И, наконец, в четвёртый байт копируется маска собранных сердец и полусердец.

    Показать таблицы
    	// Маски предметов в зависимости от значения прогресса
    	const uint8 s_itemsInProgress[] = {
    		0x8000, 0xC000, 0xC000, 0xC000, 0xE000, 0xF000, 0xF000, 0xF000,
    		0xF000, 0xF800, 0xFC00, 0xFC00, 0xFC00, 0xFC00, 0xFE00, 0xFF00,
    		0xFF00, 0xFF00, 0xFF00, 0xFF00, 0xFF80, 0xFF80, 0xFF80, 0xFFC0,
    		0xFFC0, 0xFFE0, 0xFFE0, 0xFFF0, 0xFFF0, 0xFFF0, 0xFFFC, 0xFFFE,
    		0xFFFF, 0xFFFF
    	};
    	
    	// Маски способностей в зависимости от значения прогресса
    	const uint8 s_powersInProgress[] = {
    		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    		0x00, 0x00, 0x00, 0x80, 0x80, 0x80, 0x80, 0x80,
    		0x80, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xE0, 0xE0,
    		0xE0, 0xE0, 0xE0, 0xE0, 0xE0, 0xE0, 0xE0, 0xE0,
    		0xE0, 0xE0
    	};
    	
    	// Допустимые для яйца локации
    	const uint8 s_accessibleEggLocations[] = {
    		0x04, 0x07, 0x16, 0x1B, 0x2F, 0x31, 0x41, 0x43,
    		0x45, 0x47, 0x4E, 0x52, 0x57, 0x87, 0x98, 0x9C,
    		0x9E, 0xA0, 0xA1, 0xA2, 0xA4, 0xB1, 0xB3, 0xB5,
    		0xFF, 0x0C
    	};
    		
    	// Допустимые значения прогресса
    	const uint8 s_accessibleProgressValues[] = {
    		0, 1, 4, 5,
    		6, 9, 10, 11,
    		14, 15, 16, 17,
    		20, 21, 22, 23,
    		26, 27, 28, 29
    	};
    

    	const uint8 s_version = 1;
    	// ...
    	uint8 data[4] = {progress, specItems | s_version, eggLocation, hearts};
    

    Затем пароль кодируется аналогично Base32, но с другим алфавитом: из этого массива поочерёдно берётся по 5 бит и записывается в отдельные байты массива из восьми элементов. При этом с помощью операции «xor» считается контрольная сумма, которая записывается в последний байт массива.

    В свободные биты шестого байта дописывается индекс таблицы кодирования. В начале игры этот индекс вычисляется случайным образом (значение от 0 до 3), но в рамках одного прохождения всегда будет использоваться только он. Т.е. может быть 4 варианта одного и того же пароля.

    	uint8 password[8] = {};
    	
    	for (var i = 0; i < 7; i++)
    	{
    		password[i] = takeBits(data, 5);
    		password[7] ^= password[i];
    	}
    	password[6] |= (tableIndex << 3);
    	password[7] ^= password[6];
    

    Последний этап: по индексу берётся одна из четырёх таблиц кодирования «Base32», и полученный массив преобразуется в текст. Элементы массива используются как индексы символов.

    	const char* s_encodeTables[] = {
    		"3CJV?N4Y0FP78BS1GW2QL6ZM9TR5KDXH",
    		"JT1W9M3DV5?ZKX6GC0FB2SPHR4N8LY7Q",
    		"R0CXM8TWB3G56PKY4FVND7QL2JZ19HS?",
    		"8JWB3PD0?RVG5L2KX4QFZ9TN1S6MH7YC"
    	};
    
    	char passwordStr[11] = "";
    	int index = 0;
    	for (var i = 0; i < 8; i++)
    	{
    		passwordStr[index++] = s_encodeTables[tableIndex][password[i]];
    		if (i == 3 || i == 5)
    		{
    			passwordStr[index++] = '-';
    		}
    	}
    


    Существует 328 возможных вариантов пароля. Несложно посчитать количество подходящих паролей — достаточно перемножить количество допустимых значений каждой из кодируемых переменных. Итак, мы можем кодировать 26 локаций яйца, 20 различных значений прогресса, 256 (28) комбинаций собранных сердец, 64 (26) комбинации специальных предметов и 4 варианта пароля. Итого: 26×20×256×64×4 = 34078720 паролей. Отсюда вероятность подобрать пароль равна ~0.03% — нам понадобится в среднем 32264 попытки.

    Графический беспредел


    В некоторых случаях разработчики проявляют оригинальность и используют графические пароли. С ними можно было столкнуться, например, в играх серии Mega Man. Конечно, удобство таких паролей сомнительно — особенно с непривычки. Но это ничего, по сравнению с длинными паролями на японском, на освещение которых в этой статье у меня, увы, сил не хватило.

    В качестве примера я возьму игру Power Blade 2. В ней используется пароль, состоящий из 12-ти иконок бонусов, расположенных в сетке 4x3. Всего есть 8 разных иконок, включая пустую. На самом деле, разница между символьным паролем и графическим паролем такого рода лишь в представлении его элементов, если заменить иконки на символы — сути не изменится.

    Каждому значку соответствует число от 0 до 7, в соответствии с их порядком появления при наборе пароля:
    0 1 2 3 4 5 6 7

    Несложно посчитать, что мы имеем 812 комбинаций, хотя игра сохраняет лишь информацию о пройденных уровнях и имеющихся костюмах. Всего 5 уровней (не считая финального), которые можно проходить в произвольном порядке, и 4 костюма. Т.е. 5 бит и 4 бита соответственно, 9 бит в сумме. Пароль же имеет ёмкость 12×log28, т.е. 36 бит — более, чем достаточно.

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

    	uint8 pass[12] = {};
    
    	// Запись двух младших бит
    	pass[7] = (clearedLevelsMask & 0x3) << 1;
    	
    	// Запись следующих двух
    	pass[9] = (clearedLevelsMask & 0xC) >>> 1;
    	
    	// Запись последнего бита
    	pass[11] = (clearedLevelsMask & 0x10) >>> 2;
    
    	
    	// Запись двух младших бит
    	pass[8] = (suitsMask & 0x3) << 1;
    	
    	// Запись двух старших бит
    	pass[10] = (suitsMask & 0xC) >>> 1;
    

    Затем считается 6-битная контрольная сумма, представляющая собой арифметическую сумму всех элементов массива. Эта сумма затем по битам записывается в зарезервированные младшие биты ячеек.

    	uint8 calcChecksum(const uint8* pass)
    	{
    		uint8 checksum = 0;
    			
    		for (int i = 0; i < 12; i++)
    		{
    			checksum += pass[i];
    		}
    		
    		for (int i = 0; i < 6; i++)
    		{
    			pass[i + 6] |= (checksum >> i) & 1;
    		}
    	}
    

    В итоге получается примерно такая схема:


    Данные подготовлены, следующий шаг — перестановка по одной из 5-ти таблиц. Ассоциируется с криптографией, не правда ли? В зависимости от маски пройденных уровней, выбирается таблица перестановки. Таблицы содержат в себе индексы элементов в соответствии с их новым порядком.

    	char s_swizzleTableFinal[] = {0, 6, 5, 4, 10, 1, 9, 3, 7, 8, 2, 11};
    	char s_swizzleTables[][] = {
    		{0, 2, 3, 1, 4, 6, 9, 5, 7, 8, 10, 11},
    		{8, 2, 3, 6, 10, 1, 9, 5, 7, 0, 4, 11},
    		{5, 4, 3, 10, 6, 0, 9, 8, 7, 1, 2, 11},
    		{3, 4, 1, 2, 6, 5, 9, 10, 7, 8, 0, 11}
    	};
    	
    	void swizzlePassword(uint8* pass, uint8 clearedLevelsMask)
    	{
    		const uint8* swizzTable = (clearedLevelsMask == 0x1F)
    			? s_swizzleTableFinal
    			: s_swizzleTables[clearedLevelsMask % 4];
    			
    		uint8 swizzledPass[12] = {};
    		
    		for (var i = 0; i < 12; i++)
    		{
    			swizzledPass[i] = pass[swizzTable[i]];
    		}
    		
    		for (var i = 0; i < 12; i++)
    		{
    			pass[i] = swizzledPass[i];
    		}
    	}
    

    Последний шаг — применение таблицы инкрементов. Т.е. каждая ячейка суммируется с соответствующим элементом таблицы по модулю 8. Именно благодаря этому иконки будут разные даже при одинаковых значениях.

    	void applyIncrementTable(uint8* pass)
    	{
    		for (var i = 0; i < 12; i++)
    		{
    			pass[i] = (pass[i] + s_incrementTable[i]) % 8;
    		}
    	}
    

    Вот мы и имеем готовый пароль. И, выходит, что в этом пароле используется 15 бит из 36. Но почему?

    Дело в том, что эти биты не такие уж и неиспользуемые. Процедура декодирования пароля берёт из них информацию о собранных L и E-бонусах, а также их текущем количестве, но затем проверяет, чтобы все эти значения были равны нулю. Отсюда можно предположить, что изначально планировалось эту информацию сохранять, но затем было принято решение от неё отказаться.

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

    Переменные длины


    Где-то дома у меня лежит тетрадка, расписанная паролями главной RPG моего детства — Little Ninja Brothers. Несмотря на то, что игра эта из себя ничего сверхъестественного не представляет, на её прохождение мне понадобилось несколько лет. Ведь это была моя первая RPG, и поначалу я даже не знал, что там можно «качаться», поэтому где-то полгода ушло на то, чтобы без прокачки победить второго босса (благо есть возможность играть вдвоём).

    В своё время именно эта игра заставила меня задуматься об устройстве системы паролей — как-то раз я целый день, сидя перед телевизором, выискивал закономерности в паролях и пытался определить их зависимость от текущих характеристик. В итоге мне даже удалось подобрать один пароль и увеличить количество денег, но это был единственный удачный случай.

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

    Этот случай интересней предыдущих хотя бы потому, что пароль имеет переменную длину: по мере прохождения игры добавляются новые символы. Более того, в пароле хранится куда больше данных, чем во всех предыдущих вместе взятых. Как видно из скриншота, алфавит составляет 32 символа, а максимальная длина вводимого пароля — 54 символа. Это даёт нам 3254 возможных паролей максимальной длины, а с учётом переменной длины и вовсе 321 + 322 + … + 3254 вариантов. Если посчитать количество информации, которое может вместить один пароль максимальной длины, то это будет 270 бит (log23254).

    Итак, какие же данные хранит пароль? Поскольку это RPG, то характеристик достаточно много, и почти все из них необходимо сохранять.

    Список характеристик




    Характеристики:
    • Уровень персонажей (макс. 50)
    • Количество опыта (макс. 65535)
    • Максимальное здоровье (макс. 255)
    • Количество денег (макс. 99999)
    • Количество M-бонусов (макс. 6)

    Экипировка:
    • Полученные призменные колокола (красный, оранжевый, жёлтый, зелёный, голубой, синий, фиолетовый)
    • Имеющиеся артефакты (противоядие, разум)
    • Тип удара («железные когти», «сокрушающий удар», «мега-удар», «огненный удар», «тупой удар», «золотые когди», «удар Ли», «призменные когти»)
    • Имеющийся меч («меч ястреба», «тигриный меч», «орлиный меч», «призменный меч»)
    • Щит («чешуйчатый», «зеркальный», «огненный», «призменный»)
    • Роба («белая», «чёрная», «роба Ли», «священная роба»)
    • Талисман («α», «β», «γ», «σ», «ω»)
    • Амулет («I», «II», «III», «IV»)
    • Тип светильника (спичка, свеча, факел, кусочек солнца)
    • Имеющиеся типы сюрикенов («одинарные», «серийные», «бумеранги», «fixer»(не смог перевести))

    Предметы и прочее:
    • Количество сдобных булочек (аналог лёгкого лечебного зелья, до 8 шт.)
    • Количество мясных булочек (аналог сильного лечебного зелья, до 1 шт.)
    • Количество вертолётов (даналог портала в город, до 8 шт.)
    • Количество лекарств (позволяет воскрешать второго игрока, до 1 шт.)
    • Количество скейтов (позволяет сбежать с поля боя, до 8 шт.)
    • Количество бомб (до 8 шт.)
    • Есть ли драгстер (это такой гоночный автомобиль)
    • Количество батарей для драгстера
    • Доступное количество специальных ударов у обоих игроков

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

    Так как же всё это работает? Начнём с того, что игра хранит массив указателей на байты переменных, нуждающихся в сохранении. По этим указателям игра формирует массив байтов, который затем подвергнется кодированию. Этот массив делится на 4 группы по 8 байтов (6 байтов в последней группе).

    	const char s_groupsBytes[4] = {8, 8, 8, 6};
    
    	const char* s_passDataMap[30] = {
    		// Group 1
    		&currLocation, &bells, &moneyLo, &expLo
    		&moneyMed,     &expHi, &moneyHi, &kicks,
    		
    		// Group 2
    		&visitedCitiesLo, &visitedCitiesHi, &mBonusCount, &tStarsTypes,
    		&punch,           &usedTreasures,   &tStars,      &treasures,
    		
    		// Group 3
    		&sword, &bombs,    &shield,   &skboards,
    		&robe,  &dragster, &talisman, &meatbuns,
            
    		// Group 4
    		&amulet,      &sweetbuns, &light, &batteries,
    		&whirlyBirds, &medicine
    	};
    

    Чтобы сделать пароли максимально компактными, игнорируются все нулевые значения. С этой целью для каждой из четырёх групп массива составляется маска ненулевых значений — один байт, где i-й бит служит индикатором того, необходимо ли включать i-й элемент массива в пароль. В сформированном массиве эта маска будет идти перед группой, которой она соответствует.

    	uint8 valuesMask(const uint8* data, int group)
    	{
    		uint8 valuesMask = 0;
    		const int startIndex = group * 8;
    		for (int i = startIndex + s_groupsBytes[group] - 1; i >= startIndex; i--)
    		{
    			valuesMask <<= 1;
    			if (data[i] != 0)
    			{
    				valuesMask |= 1;
    			}
    		}
    		return valuesMask;
    	}
    

    Та же самая операция в конце применяется и к группам на тот случай, когда все значения группы равны нулю: существует четырёхбитная маска (4 старших бита байта), где i-й бит (от старшего к младшему) служит индикатором того, что в пароль включена i-я группа массива. Эта маска будет записана в заголовке, прямиком перед данными групп.

    Кроме того, существует таблица длин, где каждому байту массива соответствует его значимое количество бит. Т.е. в итоге будут кодироваться не байты массива целиком, а только используемые биты значений. Та же техника применяется и для масок ненулевых значений — количеству используемых бит маски соответствует число байтов в группе.

    Итоговый формируемый массив представляет собой аналог битового стека: добавление переменных происходит «подстановкой спереди» — для N добавляемых бит ко всему массиву применяется логический сдвиг вправо на N, а в освободившиеся в начале биты и записывается значение переменной.



    	const char s_bitLengths[] = {
    		8, 7, 8, 8, 8, 8, 1, 7, 8, 2,
    		3, 4, 4, 2, 4, 2, 3, 4, 3, 4,
    		3, 1, 3, 1, 3, 4, 3, 4, 4, 1
    	};
    	
    	void pushBits(uint8* data, uint8 value, int bitCount)
    	{
    		shiftRight(data, bitCount);
    		writeBits(data, value, bitCount);
    	}
    	
    	// ...
    	
    	uint8 encodedData[30] = {};
    	
    	uint8 groupsMask = 0;
    	for (int i = 3; i >= 0; i--)
    	{
    		groupsMask >>= 1;
    		uint8 currMask = valuesMask(passData, i);
    		if (currMask != 0)
    		{
    			groupsMask |= 0x80;
    			const uint8 valuesCount = s_groupsBytes[i];
    			const int startIndex = i * 8;
    			for (int j = startIndex + valuesCount - 1; j >= startIndex; j--)
    			{
    				if (passData[j] != 0)
    				{
    					pushBits(encodedData, passData[j], s_bitLengths[j]);
    				}
    			}
    			pushBits(encodedData, currMask, valuesCount);
    		}
    	}
    

    Затем в начало массива добавляются 4 байта, которые являются своеобразным заголовком. В нём будет храниться контрольная сумма, маска включенных в пароль групп и инкремент — 8-битное случайно значение от 0 до 31, которое будет складываться со значениями символов по модулю 32.

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

    	uint32 calcChecksum(uint8* data, int count)
    	{
    		uint32 sum = 0;
    		for(int i = 0; i < count; i++)
    		{
    			sum += data[i] * (i + 1);
    		}
    		return sum;
    	}
    	
    	// ...
    	
    	const uint8 increment = rand() % 32;
    	
    	shiftRight(encodedData, 32);
    	encodedData[3] = increment;
    	uint32 checksum = calcChecksum(&encodedData[3], (encodedDataBitLength + 7) / 8);
    	
    	encodedData[0] = checksum & 0xFF;
    	encodedData[1] = (checksum >> 8) & 0xFF;
    	encodedData[2] = ((checksum >> 16) & 0xF) | groupsMask;
    

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

    	uint8 password[54] = {};
    
    	uint8* header = encodedData;
    	uint8* body = &encodedData[4];
    	
    	// Encode header (3 bytes + increment = 6 chars)
    	for (int i = 0; i < 5; i++)
    	{
    		password[i] = takeBits(header, 3, 5);
    	}
    	password[5] = increment;
    
    	const int charCount = (((byteCount + 1) * 8 + 4) / 5) - 1;
    	
    	// Encode password data
    	for (var i = 0; i < charCount; i++)
    	{
    		password[i + 6] = takeBits(body, byteCount, 5);
    	}
    
    

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

    	// Apply increment skipping increment char
    	for (var i = 0; i < password.length; i++)
    	{
    		if (i != 5)
    		{
    			password[i] = (password[i] + increment) % 32;
    		}
    	}
    

    И, собственно, заключительный этап: преобразование в текст по алфавиту.

    	const wchar_t* s_passwordCharTable = L"—BCD\u25a0FGH+JKLMN\u25cfPQRST\u25b2VWXYZ234567";
    
    	for (int i = 0; i < charCount; i++)
    	{
    		std::cout << s_passChars[password[i]];
    		if (i % 6 == 5)
    		{
    			std::cout << ' ';
    		}
    	}
    


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

    Ошибка заключается в следющем: существует процедура, которая декодирует битовый поток (полученный после декодирования из «Base32») обратно в байтовый массив из 4-х групп. При отсутствии в пароле определённой группы она устанавливает текущий результирующий индекс на начало следующей.

    Группы, как уже было сказано, имеют размер 9 байтов (за исключением последней) — 8 байт значений + предшествующая маска ненулевых значений. Так вот, при отсутствии второй группы индекс должен быть установлен на начало третьей группы, т.е. стать равным 18-ти, но вместо этого значение записывается в переменную, хранящую маску существующих групп. Поскольку значение хранится ещё и в регистре, на индекс это не влияет, но маску всё же портит.

    Принимая значение 0x12 (напомню, что маской являются 4 старших бита), маска начинает указывать на то, что существует только последняя группа значений. Т.к. первая группа уже обработана, а вторая и так отсутствует, это сказывается только на третьей и четвёртой группах.

    	uint8 data[32] = {};
    	for (int index = 0; index < 34; index++)
    	{
    		register = index;
    		if (register == 0 && !(mask & 0x80))
    		{
    			register = 9;
    			index = register;
    		}
    		if (register == 9 && !(mask & 0x40))
    		{
    			register = 18;
    			// Здесь ошибка!
    			mask = register;
    		}
    		if (register == 18 && !(mask & 0x20))
    		{
    			// После ошибки всегда будет выполняться этот код
    			register = 27;
    			index = register;
    		}	
    		if (register == 27 && !(mask & 0x10))
    		{
    			return;
    		}
    
    		decodeValue(input, &data[index]);
    	}
    

    В итоге, при наличии третьей группы она всегда будет обрабатываться как четвёртая. Так почему же это никак не сказалось на работоспособности пароля? А потому, что во второй группе есть маска посещённых городов, и, учитывая, что почти все предметы, сохраняемые в 3-й группе, можно получить только посетив города (а первый город стоит прямо перед носом у игрока), то третья группа не будет существовать без второй, а значит, при проявлении бага данные из третьей группы не будут пропадать.

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


    В качестве бонуса


    Любители JavaScript могут поковыряться в написанных специально для статьи генераторах паролей для
    Adventure Island 4 (Takahashi Meijin no Bouken Jima IV) и Power Blade 2, а также в облагороженной версии генератора для Little Ninja Brothers почти пятилетней давности.

    Прошу за код строго не судить, веб-программирование далеко от моей специализации.

    Генератор паролей для Prince of Persia можно найти здесь.

    И немножко ностальгии...
     

     

     

     

     

     


    Ссылки


    Поделиться публикацией

    Похожие публикации

    Комментарии 61
      0
      > В первом случае алфавит пароля составляет 24 символа. Если посчитать количество комбинаций символов, то это будет 424 — не так уж и мало

      24^4, а не 4^24
        0
        Спасибо, исправил.
          0
          Из той же области:
          Становится очевидно, что для подбора пароля достаточно, чтобы контрольная сумма подходила к закодированным данным. Тогда, если не учитывать её специфику, можно посчитать вероятность подобрать пароль: ровно 1% (единица делить на количество возможных значений суммы) — довольно много.

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

          Хм, вероятность всё так же считается делением количества валидных паролей на количество всех, а именно:
          14(число уровней) * 100(возможные значения времени) * 10 * 10 (выбор случайных чисел) / 100000000
          Это равно 0,14%, или, что тоже самое, один верный пароль на 700 неправильных.
            0
            Не совсем верно: пароль с правильной контрольной суммой может быть невалиден, если в нем закодирован несуществующий номер уровня.

            Отнюдь: игра такой пароль примет, т.е. с её точки зрения он валиден. Но эффект будет как при проезде по памяти. :)
              0
              Хм, вероятность всё так же считается делением количества валидных паролей на количество всех

              Наверное, вы правы. Только число возможных значений номера уровня в пароле — 100. Просто значения из цифр будут браться по модулю 4 (два младших бита).
                0
                Если говорить о несуществующих номерах уровня, то приведенный алгоритм генерации пароля может различить только 40 вариантов: в зависимости от выбранного номера, pass[7] может принять любое из 10 значений, а pass[1] только четыре значения. В качестве примера можно сгенерировать пароль для уровней, скажем, 6 и 46 — получится одно и то же число.
                  0
                  Относительно игрового алгоритма генерации — да. Но алгоритм декодирования допускает любые значения этих цифр при правильной контрольной сумме. Он просто возьмёт оттуда младшие биты, не делая никаких проверок, и получит число от 0 до 15.
          +9
          В игре Rock n' Roll Racing — в конце показывали самые крутые моменты, Я тогда аж протащился — сейчас понимаю что они были у всех одинаковые :)
            0
            Кстати, генератор паролей для RRR, и для многих других. Код можно посмотреть прямо в браузере, т.к. все на JavaScript.
              0
              Помню как мы с друганом составили мощную таблицу сейвов и характеристик в них и пытались найти закономерности. Вычислили цвет и кое какие бонусы.

              А еще в RRR был клевый хак, когда в игре на двоих вводишь коды персов разных уровней. Один, например, только начал, а другой уже в следующем мире. В результате оба на самом младшем мире, но со своими тачками. Таким макаром нам удалось вытащить в первую же локацию гусеничные танки и под конец игры прокачать их до предела.
              0
              Нда, ностальгия, а я помню часами сидел и подбирал коды, чтобы получить какие-нибудь бонусы или перескочить на другой уровень, самое интересное что это получалось)
                +4
                А я вспомнил The Lost Vikings. Пароли к уровням там, конечно, «зашитые», но очень легко запоминались. TTRS для «египетского» тетрисного уровня, или MSTR для последнего уровня и борьбы с главным зеленым злодеем — как пример. 8)
                  +1
                  Да-да, я тоже первым делом вспомнил Lost Vikings :)
                    0
                    Только недавно их перепроходил. Тоже по ходу игры выписывал пароли на бумажку. :-) Чудесная все-таки игра.
                    +1
                    Последние 10 уровней в Викингах — это зло. Особенно повсеместные шипы: youtu.be/vGNURPCa0pc
                    Там пароли негуманны, в таком сохранения нужны :)
                      +1
                      «Повсеместные шипы» в The Lost Vikings? Это вы еще в суровые I Wanna Be The Guy и подобные не играли. :-)))
                        +2
                        Вариация на тему Марио:

                        • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          that's unpossible!1 %)
                          тасинг, определённо!
                          ха, у марио есть распрыжка, он с ней даже в правый край экрана влипает, RJ не нужен.

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

                          даа, границам возможного опять пришлось подвинуться!
                          зы: на POP тоже удалось пароль подобрать (лет 19 назад это было)), правда только один, зато близко к концовке (14?)
                          зыы: пришло в голову, а quake тасят ли?
                            0
                            А как Вам этот?
                            www.youtube.com/watch?v=aLrWwmnt2po
                          0
                          Ну, с учетом того что The Lost Vikings сделали еще до деления игр на хардкор и обычные — шипов там весьма ) I Wanna Be The Guy для людей с нервами из стали :)
                          0
                          Зато адреналина сколько! Проходишь с двадцатой попытки уровень почти до конца и дохнешь на последнем шипе. :D
                            0
                            Да-да-да! Вот именно так я и закончил играть в The Lost Vikings… )

                            … потом правда опять начал, но времени должно было пройти, что бы опять терпения и веры в проходимость набраться :)
                              –1
                              Я во много заходов проходил. Сначала начало честно, потом середина с кодами («хоть посмотреть»), потом конец с читами (восстановление здоровья, но не бессмертие; генерация предметов), потом середина честно, потом конец честно. На много лет хватило.

                              На последних уровнях никакие читы почти не помогают, потому что обычно не теряешь здоровье, а дохнешь с первого удара…
                            0
                            Мне, кстати, больше запомнилась PC версия — www.youtube.com/watch?v=hDg2yB83QcI
                            Перепройти ее что ли :)
                          +3
                          Было дело, у каждого уважающего себя владельца приставки, была тетрадь с паролями, а так же со всякими секретами и прочими «суперударами»
                            0
                            Читеры и тут умудрялись читерить, и покупали книги с кодами)))
                            +1
                            А теперь играю в Road Rash и Rock'n'Roll Racing на андроиде через эмулятор. Там сохранение есть… наверное поэтому эти игры теперь не кажутся настолько уж крутыми.
                              +1
                              В Road Rash 3 при помощи подбора паролей в своё время получил секретный чёрный супер-мотоцикл. На холмах он подпрыгивал далеко за пределы экрана. :)
                              0
                              Вспоминается, как впервые обнаружил зависимость между паролем и статами бойца в сеговской игрушке Best of the Best.
                              После этого я уже не мог смотреть на пароли в играх как прежде :)
                                +1
                                Не могу равнодушно читать такие посты. Эти коды мне казались чем-то мистическим.
                                  +1
                                  Да уж, как прочитал заголовок — сразу вспомнилась тоненькая тетрадка в клеточку, в которую я записывал коды уровней Lost Vikings на Sega. Как я на последнем уровне мучился, ужас… Аж сразу ностальгия замучила.
                                    0
                                    Тоненькая? оО
                                    У меня был толстенный блокнот.
                                    Там были и пароли от RRR, и всякие читы и уловки, все найденный фаталити и бруталити для Mortal Combat, читы или секреты для Twisted Metal…
                                    Между прочим он где-то еще дома лежит… Пойду поищу… :)
                                      0
                                      Помню, тот волнующий момент…
                                      Предо мной стоит только что купленная SEGA, рядом лежит девственно чистая тетрадка в клеточку 12 листов… в воздухе летает предчувствие мистического волшебства… И вот оно свершилось! Назад назад вперед и Райден летит отнимая примерно 10% силы противника, ах каким красивым почерком я делал эту первую запись :)
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                        0
                                        Дело в том, что своей Сеги у меня не было, я взял у друга погонять только из-за Lost Vikings, поэтому и тетрадка была тонкая =)
                                      0
                                      Принц Персии
                                      в игре 14 уровней и 60 возможных значений времени
                                      Это не так, лично подбирал пароли с 80+ минутами времени.
                                        0
                                        Да, вы правы. Имелось в виду 60 «честных» значений, про реальное количество упомянуть забыл.
                                        Добавил это в статью.
                                        +16
                                        Поставил плюсик за одно только оформление поста
                                          0
                                          Похожие вещи часто встречались в различных РПГ в третем воркрафте. Там с сохраняли шмот и уровень.
                                            0
                                            А ещё в Prince of Persia на PC (по крайней мере на моём 386-м так было) можно было зажать Shift+L и перескакивать с 1-го на 4-й уровни даже без кодов. Признаться честно, я только сегодня узнал что там были коды — мне понадобились годы с 1994 по 2001 чтобы пройти от начала до конца.
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                А на моей памяти, мы подбирали пароли к Prince of Persia прибавляя 1001 к уже известному, полученному после прохождения уровня паролю. Может это было самовнушение и память подводит, но помню, что так удавалось подобрать около половины паролей.
                                                  0
                                                  Прибавляя 1001, вы увеличивали один из инкрементов, тут же исправляя контрольную сумму, поскольку при её подсчёте в самую последнюю очередь тот самый инкремент и прибавлялся. Так что спустя годы могу поздравить вас с обнаружением закономерности. :)
                                                    0
                                                    Извиняюсь, не один из инкрементов, а старшую цифру уровня.
                                                    0
                                                    Тогда мы просто радовались, что взломали систему!:) Спасибо, за интересный взгляд на прошлое.
                                                      0
                                                      В первом случае алфавит пароля составляет 24 символа.

                                                      а почему 24? В английком 26 букв
                                                        0
                                                        Ну, как видно по скриншоту, там используются только согласные (кроме Y) и некоторые символы. Почему именно 24 символа — известно только разработчикам. Скорей всего, профессиональная тяга к числам, кратным восьми. :)
                                                          0
                                                          а, спасибо
                                                        0
                                                        Прочел, осмыслил, пошел хандрить
                                                          0
                                                          В детстве у меня была игра на сеге Battle in Jungle, она была полностью локализована на русский, причем достаточно неплохо, но вводимые символы были тоже локализованы, а так как пароли на уровни были на английском, то ввести их не получалось! В итоге, так как мне разрешали играть час-два в день, то до третьего уровня я добирался редко, а прохождение первого вскоре знал наизусть.
                                                            +1
                                                            Привнесу немного ясности о «неиспользуемых битах» в Power Blade 2:

                                                            И, выходит, что в этом пароле используется 15 бит из 36. Но почему? Видимо, для усложнения подбора и анализа.


                                                            На самом деле разрабочики, скорее всего, планировали сохранять собранные «плюшки» L и E при игре с пароля. Но толи поленились писать честную генерацию, толи посчитали что «слишком жирно будет» и потому возможность эту убрали, но не совсем. В пользу этой версии говорит тот факт, что код декодирования пароля честно их вычитывает в отдельные ячейки. А затем уже проверяет полученные значения на равенство 0 и если хоть где-то там получился не 0, то пароль просто отвергается как ошибочный. Однако, если воспользоваться GameGenie кодом AOZOES (9DA8:18), то эта проверка отключается и появляется возможность вводом пароля начать игру с ненулевым количеством L и E. Собственно, в своей версии генератора (извиняюсь за г… внокод) этот момент я учитывал. Так же в пароле хранится маска уже собранных L и E, если выставить биты в 1, то соответствующие «плюшки» будут считаться игрой уже подобранными и потому их не будет на этапе. В итоге можно сделать hard mode — использовать вышеприведённый GG код + пароль с установленными битами — играем без «запасов» и возможности их подобрать.

                                                            Можно вообще отключить все проверки пароля на правильность если использовать сразу все 3 GG кода:
                                                            AOZOES (9DA8:18)
                                                            AOGOSK (9CCD:18)
                                                            APAPNS (9D07:18)
                                                            После ввода пароля GG коды лучше отключить, т.к. они могут оказывать паразитное влияние на геймплей (заметил, например, что если не отключить 1й код, то ползающих роботов с электрошоком не станет).

                                                            з.ы. Если кому подробности интересны — свои «раскопки» я описывал в ЖЖ, правда преимущественно «копаю» игры на Sega (1, 2).
                                                              0
                                                              Спасибо, это многое проясняет. Надо было мне не лениться, и всё-таки поглубже вникать в процедуры декодирования.

                                                              С вашего позволения добавлю это в статью, а заодно и ссылки на ваши странички.
                                                                0
                                                                Иногда в процедурах декодирования бывают мелкие детали, на которые сразу не обращаешь внимания, а они на самом деле открывают новые возможности. Как например в Stargate на SMD.

                                                                Ок, добавляйте, правда страничка и код генераторов у меня оставляет желать лучшего, т.к. далёк от веба и его современных технологий, стыдно такое показывать :)
                                                              +1
                                                              Теперь понятно, почему к Принцу Персии подошёл первый взятый наугад код от какого-то из продуктов Довганя (по ним вроде ещё розыгрыш проходил).
                                                                0
                                                                А в бомбармене достаточно было сделать табличку соответствия букв и их численных значений, разобраться какая по счету буква за что отвечает и выставлять себе все что угодно и где угодно.

                                                                Не помню как именно строились пароли на денди (мне тогда 6 лет было), но на WinXP в бомбарменах все четко прослеживалось.
                                                                  –1
                                                                  Ипать, гениально!!! *пардон*
                                                                    0
                                                                    Особенно вспоминается момент, когда мы играя в Синдикат на сеге, записали неправильно код и получили деньги, которых мы не смогли потратить до конца игры.
                                                                      0
                                                                      1 DEMOLITION
                                                                      2 SPICESATYR
                                                                      3 BURNINGSUN
                                                                      4 DARKHUNTER
                                                                      5 EVILMENTAT
                                                                      6 ITSJOEBWAN
                                                                      7 DEVASTATOR
                                                                      8 DEATHRULER

                                                                      Последние два помню до сих пор.

                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                      Самое читаемое