2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Оптимальный алгоритм декодирования AES - посоревнуемся? ;)
Сообщение13.08.2013, 22:41 


21/03/06
1545
Москва

(Оффтоп)

Очень приятно посмотреть на такой код. Отформатировано и структурировано именно так, как будто я сам писал :).


_Ivana, вы не ответили на принципиальный вопрос: возможно ли вытащить код (или перезаписать часть кода, не затерев другую его часть) уже записанного кастомного бутлоадера вашего целевого МК? Если да, то, боюсь, ваша защита неэффективна.
Также важно в какой момент происходит дешифровка и куда записывается ее результат (откуда выполняется код полезной программы).

 Профиль  
                  
 
 Re: Оптимальный алгоритм декодирования AES - посоревнуемся? ;)
Сообщение13.08.2013, 22:50 


05/09/12
2587

(Оффтоп)

e2e4, спасибо. Было бы не менее интересно также обсудить суть кода, а не только его форму :-) А то критика закончилась как раз с появлением возможного её объекта...


e2e4, я заметил ваши вопросы. А не отвечаю на них только потому, что не полностью уверен в ответах :-) Разобраться с AES и написать код кодирования/декодирования было моей частью задачи, собственно самим бутлоадером занимается другой человек (в компетентности которого я не сомневаюсь). И, кстати, в данной теме это совсем не принципиальные вопросы.

 Профиль  
                  
 
 Re: Оптимальный алгоритм декодирования AES - посоревнуемся? ;)
Сообщение14.08.2013, 17:15 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А, у Вас ключ фиксирован. Я думал, у Вас полная реализация будет, с расширением ключа.

Что-то я уже два раза пересчитываю, и у меня получается, что Ваше invMixColumns неправильно работает. В стандарте в конце приведены тестовые векторы, проверьте.

_Ivana в сообщении #754540 писал(а):
#define xtime(a) (((a)<0x80)?(a)<<1:(((a)<<1)^0x1b) )
Конечно, я практически уверен, что вам эта защита нафиг не сдалась и никто не будет применять к вам криптоанализ (а если и будет, то скорее попытается достать ключ оттуда, где он лежит), но эту вещь надо писать
(((a)<<1)^(0x1b*((a)>>7))), иначе invMixColumns может выполняться разное число тактов для разных данных и, искусственно понизив тактовую частоту, можно будет по времени выполнения узнать информацию о первых битах байтов ключа.

 Профиль  
                  
 
 Re: Оптимальный алгоритм декодирования AES - посоревнуемся? ;)
Сообщение14.08.2013, 18:26 


05/09/12
2587
Xaositect в сообщении #754690 писал(а):
А, у Вас ключ фиксирован. Я думал, у Вас полная реализация будет, с расширением ключа.
Это совершенно непринципиальный момент. И это такая же полная реализация. В данном случае я сразу храню в памяти расширенный ключ (расширение было проведено по стандарту, первые 16 байт - собственно исходный ключ), чтобы не тратить ресурсы на его расширение. Но никто не мешает мне получить его расширенный из первоначального, перед всей расшифровкой. Только для этого потребуется прямая таблица Sbox, но можно это сделать и из таблицы обратных замен, в цикле перебирая её, пока не встретим нужное значение - все равно это делается один раз, для расширения ключа.

Xaositect в сообщении #754690 писал(а):
Что-то я уже два раза пересчитываю, и у меня получается, что Ваше invMixColumns неправильно работает. В стандарте в конце приведены тестовые векторы, проверьте.
Проверю. Хотя, я проверял на других данных - все работало нормально. Кстати, вы так и не привели образцово-показательный пример оптимального кода. Разумеется, в первую очередь это касается процедуры invMixColumns, ибо все остальное там тривиально. Я видел много вариантов реализации этой процедуры, но все или с дополнительными (обычно объемными) таблицами, типа как пример в википедии (нужен килобайт таблиц (4 шт. по 256 байт)) или приведенная ссылка на первой странице, или достаточно сложные и долгие.

ЗЫ спасибо за макрос, нравится что он не содержит условие, хотя и содержит умножение. Но это уже к вопросу о платформе.

UPD не знаю, почему ваши проверки показывают ошибку, я проверил по вашей ссылке пример: на входе
Код:
0x69,0xc4,0xe0,0xd8,0x6a,0x7b,0x04,0x30,0xd8,0xcd,0xb7,0x80,0x70,0xb4,0xc5,0x5a
ключ
Код:
0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f
расширенный ключ
Код:
0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
0xd6,0xaa,0x74,0xfd,0xd2,0xaf,0x72,0xfa,0xda,0xa6,0x78,0xf1,0xd6,0xab,0x76,0xfe,
0xb6,0x92,0xcf,0x0b,0x64,0x3d,0xbd,0xf1,0xbe,0x9b,0xc5,0x00,0x68,0x30,0xb3,0xfe,
0xb6,0xff,0x74,0x4e,0xd2,0xc2,0xc9,0xbf,0x6c,0x59,0x0c,0xbf,0x04,0x69,0xbf,0x41,
0x47,0xf7,0xf7,0xbc,0x95,0x35,0x3e,0x03,0xf9,0x6c,0x32,0xbc,0xfd,0x05,0x8d,0xfd,
0x3c,0xaa,0xa3,0xe8,0xa9,0x9f,0x9d,0xeb,0x50,0xf3,0xaf,0x57,0xad,0xf6,0x22,0xaa,
0x5e,0x39,0x0f,0x7d,0xf7,0xa6,0x92,0x96,0xa7,0x55,0x3d,0xc1,0x0a,0xa3,0x1f,0x6b,
0x14,0xf9,0x70,0x1a,0xe3,0x5f,0xe2,0x8c,0x44,0x0a,0xdf,0x4d,0x4e,0xa9,0xc0,0x26,
0x47,0x43,0x87,0x35,0xa4,0x1c,0x65,0xb9,0xe0,0x16,0xba,0xf4,0xae,0xbf,0x7a,0xd2,
0x54,0x99,0x32,0xd1,0xf0,0x85,0x57,0x68,0x10,0x93,0xed,0x9c,0xbe,0x2c,0x97,0x4e,
0x13,0x11,0x1d,0x7f,0xe3,0x94,0x4a,0x17,0xf3,0x07,0xa7,0x8b,0x4d,0x2b,0x30,0xc5
на выходе
Код:
0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff
, то есть что надо. Но я то в этом был уверен, проверил по вашей просьбе. Можете накидать еще примеров для проверки, если еще сомневаетесь.

 Профиль  
                  
 
 Re: Оптимальный алгоритм декодирования AES - посоревнуемся? ;)
Сообщение14.08.2013, 19:26 
Заслуженный участник
Аватара пользователя


06/10/08
6422
_Ivana в сообщении #754712 писал(а):
Проверю. Хотя, я проверял на других данных - все работало нормально.
Извиняюсь, это я ошибся, у Вас все верно.

_Ivana в сообщении #754712 писал(а):
Разумеется, в первую очередь это касается процедуры invMixColumns, ибо все остальное там тривиально. Я видел много вариантов реализации этой процедуры, но все или с дополнительными (обычно объемными) таблицами, типа как пример в википедии (нужен килобайт таблиц (4 шт. по 256 байт)) или приведенная ссылка на первой странице, или достаточно сложные и долгие.
Я бы тоже взял что-нибудь тупо на таблицах, как, например, тут: http://git.lysator.liu.se/nettle/nettle/trees/master Таблицы можно сгенерировать перед расшифрованием и убрать из памяти сразу после него.

 Профиль  
                  
 
 Re: Оптимальный алгоритм декодирования AES - посоревнуемся? ;)
Сообщение14.08.2013, 19:39 


05/09/12
2587
Xaositect в сообщении #754726 писал(а):
Таблицы можно сгенерировать перед расшифрованием и убрать из памяти сразу после него.
Да, вы правы. И даже для применения в бутлоадере МК такой вариант вполне хорош - насколько я помню (у меня есть исходники) вот здесь http://www.atmel.com/Images/doc2589.pdf именно так и реализовано. Что ж, получается тема исчерпана? И моя бестабличная относительно быстрая реализация invMixColumns не нашла поддержки :-)

ЗЫ на закуску, если вдруг кому будет интересно - несколько из многих статей по теме оптимизации процедуры invMixColumns
http://eprint.iacr.org/2011/184.pdf
http://www.wseas.us/e-library/conferenc ... /AIC44.pdf
http://www.kmitl.ac.th/~kchsomsa/somsak ... 04_163.pdf
http://www.cs.tau.ac.il/~fiat/crypt07/papers/aes.pdf
http://www.kemt.fei.tuke.sk/personal/dr ... si2005.pdf

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:57 
Основатель
Аватара пользователя


11/05/05
4312
 i  Тема перемещена из форума «Computer Science» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group