Старый топик с WASM: 'Помогите с криптоанализом'
WASM Phorum -> WASM.CRYPTOGRAPHY -> Помогите с криптоанализом
Дата: Мар 22, 2006 07:57:58
Прошу прощения за бессодержательное название темы, но лучше придумать не смог. ;)
Итак, есть мобила. У мобилы есть бутлоадер. Бутлоадер играется в аутентификацию. Смысл какой:
бутлоадер -> посылает байты программе: 3D D4 D6 DC программа над ними мудрит и -> посылает назад ответ: D7 04 2D FD бутлоадер использует функцию дешифрования и сравнивает расшифрованные байтики (D7 04 2D FD) со своим начальным запросом (3D D4 D6 DC).
В программе, с которой общается бутлоадер, сидит execryptor и, следовательно, анализ алгоритма в самой программе отпадает. Функция дешифрования написана на Arm - ее полный декомпилированный код ниже.
Теперь вопрос - можно ли по знанию 3D D4 D6 DC, знанию процедуры дешифрования и знанию ответа D7 04 2D FD, исхитриться сделать так, чтобы на каждый запрос бутлоадера приходил валидный ответ?
function AuthorisationKey(A, B, C, D:Byte):Dword;
const unk_40000A24:array[0..15] of byte = ( $F, $5, $2, $6, $0, $9, $B, $3, $7, $C, $1, $A, $4, $D, $E, $8 );
const unk_40000A34:array[0..15] of byte = ( $C, $2, $6, $4, $E, $3, $5, $F, $B, $A, $0, $8, $1, $D, $9, $7 );
var E, F, G, H:Byte;
begin
E:=(unk_40000A24[($0F and A)] shl 4) or unk_40000A34[(A shr 4)];
G:=(unk_40000A24[($0F and C)] shl 4) or unk_40000A34[(C shr 4)];
F:=(unk_40000A24[(A xor B) shr 4] shl 4) or unk_40000A34[($F and (A xor B))];
H:=(unk_40000A24[(C xor D) shr 4] shl 4) or unk_40000A34[($F and (C xor D))];
Result:=(((((E shl 8) or F) shl 8) or G) shl 8) or H;
end;
Solution:
------------------------------------------------------
*** НЕ ЧИТАЙ, ПОКА САМ НЕ ПОИГРАЕШЬСЯ !!! ***
------------------------------------------------------
Ошибка в условии :-)
Для D7 04 2D FD ответный код DC D6 D4 3D (обратный порядок байт)
> Теперь вопрос - можно ли по знанию 3D D4 D6 DC, знанию процедуры дешифрования и знанию ответа D7 04 2D FD, исхитриться сделать так, чтобы на каждый запрос бутлоадера приходил валидный ответ?
Иными словами, по заданному дешифратору и известной паре plain-cipher text (избыточно) требуется написать шифратор (инверсную функцию).
Поскольку нелинейных операций в дешифраторе не содержится (SBoxes считаем обратимыми), то краткий ответ - да, можно.
развернутый ответ выглядит так:
1. Перепишем код на С (для ясности)
const BYTE S1[16] =
{
'\x0F', '\x05', '\x02', '\x06',
'\x00', '\x09', '\x0B', '\x03',
'\x07', '\x0C', '\x01', '\x0A',
'\x04', '\x0D', '\x0E', '\x08'
};
const BYTE S2[16] =
{
'\x0C', '\x02', '\x06', '\x04',
'\x0E', '\x03', '\x05', '\x0F',
'\x0B', '\x0A', '\x00', '\x08',
'\x01', '\x0D', '\x09', '\x07'
};
static DWORD AuthorisationKey(BYTE A,BYTE B,BYTE C,BYTE D)
{
BYTE E = (S1[(0x0F & A)] << 4) | S2[(A >> 4) & 0x0F]; // x3
BYTE G = (S1[(0x0F & C)] << 4) | S2[(C >> 4) & 0x0F]; // x1
BYTE F = (S1[((A ^ B) >> 4) & 0x0F] << 4) | S2[(0x0F & (A ^ B))]; // x2
BYTE H = (S1[((C ^ D) >> 4) & 0x0F] << 4) | S2[(0x0F & (C ^ D))]; // x0
return (((((E << 8) | F) << 8) | G) << 8) | H;
}
2. Из анализа возвращаемого значения, очевидно следует, что все байты ответа являются независимыми функциями от E, F, G, H (совпадают с ними). Таким образом решение распадается на 4 независимых подзадачи нахождения функций, обратных к вычисляющим байты E, F, G, H.
3. E и G являются функциями только одной переменной (A и C соответственно), так что инвертирование следует начинать с них.
4. Старший и младший nibbles от E вычисляются независимо, это же верно и для G, так что подзадачи инверсии этих байт в свою очередь, также, распадаются на две независимые подзадачи (в силу ограниченности S1 и S2 сверху значением 0x0F).
EH = S1[(0x0F & A)];
EL = S2[(A >> 4)];
GH = S1[(0x0F & C)];
GL = S2[(C >> 4)];
Из приведенных выражений следует, что старший и младший nibbles функции зависимы только от младшего и старшего (в указанном порядке) nibbles аргумента, что еще раз делит указанные подзадачи на две независимых, сводящихся к инверсии одного полубайта.
Умножая слева на подходящую инверсную функцию SI*, получаем:
SI1 * EH = SI1 * S1[(0x0F & A)];
SI2 * EL = SI2 * S2[(A >> 4)];
SI1 * GH = SI1 * S1[(0x0F & C)];
SI2 * GL = SI2 * S2[(C >> 4)];
или
SI1[EH] = AL;
SI2[EL] = AH;
SI1[GH] = CL;
SI2[GL] = CH;
где через *H и *L обозначены, соответственно, старший и младший полубайты.
Таким образом,
A = (AH << 4) | AL = (SI2[EL] << 4) | SI1[EH];
C = (CH << 4) | CL = (SI2[GL] << 4) | SI1[GH];
или, выражая через E и H
A = (SI2[E & 0x0F] << 4) | SI1[(E >> 4) & 0x0F];
C = (SI2[G & 0x0F] << 4) | SI1[(G >> 4) & 0x0F];
5. Рассмотрим два оставшихся уравнения.
BYTE F = (S1[((A ^ B) >> 4) & 0x0F] << 4) | S2[(0x0F & (A ^ B))]; // x2
BYTE H = (S1[((C ^ D) >> 4) & 0x0F] << 4) | S2[(0x0F & (C ^ D))]; // x0
Легко заметить, что эти уравнения также распадаются на два независимых относительно старшего и младшего полубайта (в силу ограниченности S1 и S2 сверху значением 0x0F).
FH = S1[((A ^ B) >> 4) & 0x0F];
FL = S2[(0x0F & (A ^ B))];
HH = S1[((C ^ D) >> 4) & 0x0F];
HL = S2[(0x0F & (C ^ D))];
Введем переменные Y = (A ^ B) и Z = (C ^ D), тогда
FH = S1[YH];
FL = S2[YL];
HH = S1[ZH];
HL = S2[ZL];
где через *H и *L обозначены, соответственно, старший и младший полубайты.
Из приведенных выражений следует, что старший и младший nibbles функции зависимы только от старшего и младшего (в указанном порядке) nibbles аргумента, что еще раз делит указанные подзадачи на две независимых, сводящихся к инверсии одного полубайта.
Умножая слева на подходящую инверсную функцию SI*, получаем:
SI1 * FH = SI1 * S1[YH];
SI2 * FL = SI2 * S2[YL];
SI1 * HH = SI1 * S1[ZH];
SI2 * HL = SI2 * S2[ZL];
или
SI1[FH] = YH;
SI2[FL] = YL;
SI1[HH] = ZH;
SI2[HL] = ZL;
таким образом
YH = SI1[FH];
YL = SI2[FL];
ZH = SI1[HH];
ZL = SI2[HL];
Вспоминая, что Y = (A ^ B) и Z = (C ^ D) и используя отсутствие переноса в операции XOR, получаем:
AH ^ BH = SI1[FH];
AL ^ BL = SI2[FL];
CH ^ DH = SI1[HH];
CL ^ DL = SI2[HL];
Поскольку значения для A и C уже были найдены ранее (п.4), разрешим уравнения для B и D, XOR'ом с подходящей переменной (в силу линейности операции XOR, это можно сделать как слева, так и справа)
AH ^ AH ^ BH = AH ^ SI1[FH];
AL ^ AL ^ BL = AL ^ SI2[FL];
CH ^ CH ^ DH = CH ^ SI1[HH];
CL ^ CL ^ DL = CL ^ SI2[HL];
Упрощая, получаем:
BH = AH ^ SI1[FH];
BL = AL ^ SI2[FL];
DH = CH ^ SI1[HH];
DL = CL ^ SI2[HL];
Следовательно, произведя элементарные подстановки, получаем:
B = ((((A >> 4) & 0x0F) ^ SI1[(F >> 4) & 0x0F]) << 4) | ((A & 0x0F) ^ SI2[F & 0x0F]);
D = ((((C >> 4) & 0x0F) ^ SI1[(H >> 4) & 0x0F]) << 4) | ((C & 0x0F) ^ SI2[H & 0x0F]);
Осталось инвертировать S-Boxes и записать алгоритм на подходящем языке программирования.