Криптография для эмбеддера



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

Криптография – это просто!

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

Шифрование.

Шифрование — это преобразование исходных данных («открытого текста») в видоизмененное состояние («закрытый текст») с целью скрыть содержимое «открытого текста» от потенциального «злоумышленника». Как подсказывает Кеп, дешифрование — это обратная процедура, восстановление «открытого текста» из «закрытого».

В данном случае понятия «открытый текст» и «закрытый текст» — это термины, которые подразумевают любую, не обязательно текстовую информацию.

Например, для того чтобы «зашифровать» данные, можно переставить местами символы в исходном тесте по определенному, известному только нам алгоритму. :) Сами понимаете, что подобный «алгоритм шифрования» походит разве что для учеников младших классов… Современная криптография такие алгоритмы всерьез не рассматривает.

Современные алгоритмы шифрования предполагают, что «злоумышленник» потенциально знает сам алгоритм шифрования (алгоритм преобразования над открытым тестом), имеет доступ к закрытому тексту, может знать фрагменты открытого текста (например «злоумышленник» предполагать, что открытый текст сообщения начинается с фразы «Добрый день!»).

Единственное, что неизвестно злоумышленнику, это некий «секрет» (секретный ключ шифрования). Это единственный «секретный» компонент, который не дает расшифровать закрытый текст. Единственный для «злоумышленника» способ вычислить секретный ключ (и расшифровать информацию целиком) — это полный перебор всех возможных вариантов секретного ключа. Считается, что длина применяемых в современных алгоритмах ключей (например, 256 бит) не позволяет подобрать ключ перебором за приемлемое время.

На этом, по сути, базируются все современные алгоритмы шифрования.

Даже устаревший алгоритм «DES» с фиксированной длиной секретного ключа в 56 бит до сих пор вполне годится для применения на «бытовом» уровне. Затраты на подбор такого ключа за приемлемое (например несколько часов) время будут, скорее всего, на несколько порядков превышать «ценность» расшифрованной информации. Согласно Википедии, «в 1998 году используя суперкомпьютер стоимостью 250 тыс. долл., сотрудники RSA Laboratory «взломали» утвержденный правительством США алгоритм шифрования данных (DES) менее чем за три дня».

В качестве примера, мы будем использовать «отечественный» алгоритм шифрования ГОСТ 28 147-89 (вернее один из режимов шифрования описанном в данном стандарте, режим «простой замены»). По идеологии, он мало чем отличается от DES, Triple DES, AES. Все примеры, приведенные в статье, актуальны для любого из причисленных алгоритмов шифрования. Более того, многие МК на уровне «железа» поддерживают аппаратную реализацию алгоритмов Triple DES и/или AES, чем грех не воспользоваться.

Все перечисленные выше алгоритмы шифрования относятся к симметричным блочным алгоритмам.

С этого момента подробнее:

Симметричный – значит, что для шифрования и дешифрования используется один и тот же секретный ключ (есть ассиметричные алгоритмы, для шифрования используется один ключ, для дешифрования – другой)

Блочный – значит, что алгоритм шифрования рассчитан на работу с блоками данных определенной длины. ГОСТ 28 147-89 шифрует данные блоками по 8 байт. На практике, «открытый текст» разбивается на боки по 8 байт, каждый блок пропускается через алгоритм шифрования, после чего, полученные зашифрованные блоки «склеиваются». Если нам нужно зашифровать данные размером меньше чем 8 байт, то данные дополняются «рандомными» байтами до размера блока.
На практике все проще, чем в теории. Для иллюстрации работы алгоритма к статье прикреплена простая реализация ГОСТ 28 147-89 найденная в интернете (Код не мой я просто разместил …).

Приведенная реализация алгоритма шифрования состоит всего из трех функций.

void kboxinit(void) –данная функция «инициализирует» криптоядро. На самом деле, она выполняет некоторые предвычисления, которые позволяют в дальнейшем ускорить шифрование/дешифрование.

void gostcrypt(const uint32_t in[2], uint32_t out[2], const uint32_t key[8]) – шифрование, in – открытый текст, out – закрытый текст, key – ключ шифрования.

void gostdecrypt(uint32_t const in[2], uint32_t out[2], uint32_t const key[8]) – дешифрование, in – закрытый текст, out – открытый текст, key – ключ шифрования.

Лучше всего продемонстрировать работу на примере


	uint32_t key[8] = {0x11111111, 0x22222222, 0x33333333, 0x44444444, 0x55555555, 0x66666666, 0x77777777, 0x88888888};
	uint32_t plain[2] = {0xAAAAAAAA, 0xBBBBBBBB};
	uint32_t cipher[2];
	uint32_t result[2];

	//Инициализация "крипторядра"
	kboxinit();

	//Шифруем plain ключом key, результат шифрования помешаем в cipher
	gostcrypt(plain, cipher, key);
	
	//Дешифруем cipher ключом key, результат шифрования помешаем в result
	gostdecrypt(cipher, result, key);
		
	//Проверяем результат работы алгоритма, сравниваем исходный текст с расшифрованным
	if(memcmp(plain, result, sizeof(plain)) != 0) {
	    printf("encrypt/decrypt error\n");
	} else {
	    printf("encrypt/decrypt success\n");
	}


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

Теперь рассмотрим пример поинтересней.

Предположим, у нас есть передатчик, который связан двухсторонним цифровым радиоканалом с приемником. Приемник управляет исполнительным механизмом (например, открывает дверь). Мы хотим открывать дверь по команде с передатчика. Естественно, мы хотим обезопасить себя, приемник должен реагировать только на «родной» передатчик.

Решение «в лоб»: записываем в передатчик и приемник одинаковый «секретный» пароль (ключ). Приемник предает пароль передатчику, передатчик сравнивает полученный пароль со своим, если все сходится – открываем двери. НО! Если быть немного «параноиком», то можно предположить, что пароль может быть перехвачен по радиоканалу, и после первого использования нашего устройства «секретный» пароль потенциально уже не такой и «секретный».

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

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

А теперь предположим, что у меня и у друга есть одинаковый «секрктный» ключ шифрования. Я отправляю ему любой, абсолютно случайный фрагмент текста и прошу его зашифровать данный фрагмент. Он шифрует фрагмент своим ключом и отправляет зашифрованный текст мне. Я расшифровываю полученный текст и сравниваю с оригиналом. Если исходный и расшифрованный фрагмент идентичны – значит я общаюсь действительно с другом, так как «правильно» зашифровать текст мог только он. В следующий раз, при необходимости авторизовать собеседника я вышлю новый, случайный, фрагмент текста, соответственно даже если «злоумышленник» перехватил предыдущий «сеанс авторизации» — это ему ничего не даст, так как каждый раз будет новый запрос (новый фрагмент открытого текста) и соответственно новый ответ (закрытый текст).

Говоря официальным языком, получается следующее – я смог убедится, что мы с собеседником владеем неким общим «секретом» не выдав (не передав) сам «секрет».

Теперь вернемся к нашему приемнику и передатчику. Итак, нам нужно записать в передатчик и приемник общий «секрет» — ключ шифрования. Можно просто вкомпилить ключ в прошивку или сохранить ключ в EEPROM.

Алгоритм авторизации будет следующий:
1. Приемник шлет передатчику сообщение, что он хочет начать процедуру авторизации (по сути абсолютно любое сообщение, например сигнатуру).
2. Передатчик генерирует случайную последовательность байт (например 8 байт, один блок шифрования) и предает эти данные приемнику (сами данные он сохраняет в памяти как «исходные»).
3. Приемник шифрует полученный блок данных и отправляет обратно, передатчику.
4. Передатчик расшифровывает полученные данные и сравнивает с «исходными». Если данные совпадают – авторизация прошла успешно.

Подобный алгоритм является достаточно надежным и применяется во многих «промышленных» решениях.

Если данная тематика интересна Сообществу, возможно, я продолжу цикл статей. Например данный алгоритм можно применить в bootloader’е, для того чтобы устройство можно было прошить только «авторизированной» прошивкой.
  • +10
  • 24 ноября 2011, 15:07
  • e_mc2
  • 1
Файлы в топике: gost.zip

Комментарии (96)

RSS свернуть / развернуть
Хорошо написано и однозначно полезно. Буду ждать продолжения.
За ГОСТовский алгоритм спасибо, можно будет воспользоваться.
0
  • avatar
  • ACE
  • 24 ноября 2011, 15:33
А вот насколько алгоритм оптимален для микроконтроллера?
AES изначально заточен под 8ми битки. А вот ГОСТ 28 147-89 критикуют за набор сложных операций.
0
  • avatar
  • a9d
  • 24 ноября 2011, 16:25
Также более интересны алгоритмы с публичными ключами. Там процесс установки защищенного соединения достаточно прост.
0
Реализацию ГОСТ 28 147-89 я привел для примера. Внутри стандарт оперирует 32-битными данными, соответственно никакой оптимизации под 8-биную архитектуру нет. Просто данный пример реализации очень лаконичен – приблизительно 250 строк кода треть из которых – комментарии. Найти аналогичную простую и понятную реализацию AES мне не удалось, а тянуть монстроподобную библиотеку не хотелось.
Как отмечено в статье, все сказанное применимо и к алгоритмам Triple DES и AES.

По поводу ассиметричных алгоритмов – что именно интересует? Алгоритм распределения клоча типа алгоритма Диффи — Хеллмана?
0
Я в своих работах использовал либу на 1.5-1.8Кб. Размер зависел от размера AES.

А фот по поводу ассимитричных интересует хоть, что-то надежное и юзабельное.
Они более жирные выходят(
0
*от длины ключа
0
Простых в реализации ассиметричных алгоритмов я не знаю. Там, как и в ЭЦП, либо операции над большими простыми числами, либо эллиптические кривые.
0
Может именно ассиметричное шифрование Вам и не так необходимо. Ведь можно Использовать стойкий симметричный шифр, а для обмена ключами сделать примерно следующее:
Алиса отправляет открытый ключ Бобу
Боб генерирует случайное число, которое и будет ключом для переписки, шифрует открытым ключом Алисы и ей отправляет. Она уже с помощью закрытого ключа расифровывает ключ сгенерированный Бобом. В качестве ассиметричного шифрования можно использовать Эль-Гамаля.
0
Вы все правильно написали, обычно ассиметричные алгоритмы используются именно для передачи секретного ключа, а сами данные шифруются симметричным шифрованием, т. к. асимметричное шифрование очень медленное.

Просто я не знаю простой (легковесной) реализации механизма распределения клоча (совместной выработки ключа) подобных алгоритму Диффи — Хеллмана или схемы Эль-Гамаля.
0
Собственно реализацией Эль-Гамаля на AVR (в качестве эксперимента) и хотел после сессия заняться. Посмотрим насколько много займет памяти.
На мой взгляд, обмен ключами стоит рассматривать только в реальных условиях. Каналы передачи, атаки на реализации и т.п. разные могут быть. не всегда треюуется ж 100летняя криптостойкость)
0
Интересно. Жду статью :)
0
Придется долго Вам её ждать) Эль-Гамаля после сессии писать буду, а это где-о середина — конец января.
0
Займитесь, займитесь. Только не забывайте, что в Bluetooth добавили Diffie-Hellman только в версии 2.1, всего лишь 3 года назад, через 10 лет после выхода BT в широкий свет и аж через 3 года после публикации аццких атак.

А почему? Да потому что у типичной гарнитурки мозгов мало (как RAM так и CPU) множить много-многобитные числа. Много лет и эллиптические кривые понадобились, чтобы сдвинуться с места.

Так что в тиньку вряд ли влезет. В меге конечно можно, только цена голой меги сравнима с ценой готового BT модуля. Поэтому для эксперемента — интересно, а практически — пользы немного.
0
Хорошая статья, плюсану. Но по работе уже так достали эти ключи, сертификаты, ЭЦП, хэш, буеееееээээ
0
бля хеш
0
Хорошая статья, плюсану

Что-то не видно)
0
я плюсанул
0
достали эти ключи, сертификаты, ЭЦП
Поверьте, коллега, я вас понимаю…
0
А как криптография уживается с ФСБ? в коммерческие проекты ведь её просто так не засунешь. или не смотрят за этим?
0
Зависит от того, где и как вы хотите применять коммерческие продукты. В некоторых случаях нужна лицензия на работу с криптографией и экспертиза. Так было раньше, сейчас не знаю.
0
2 примера:
1. скажем, сетевое железо с криптухой
2. лабуда типа беспроводных датчиков (пожарка, охрана)

Так понимаю если как-то задевать государство то лицензию все равно надо получать. а что в том случае если вышеперечисленное пихать по другим фирмам, лицам и т.д. и обслуживать самому?
0
Это юридический вопрос, а я не юрист :) Могу высказать только свое понимание. Если Вы позиционируете устройство как средство криптографической защиты информации – Вам нужна лицензия, экспертиза и т. д. Если Вы просто используете криптоалгоритм для реализации, например, автомобильной сигнализации – лицензия Вам не нужна.
0
С юридической точки зрения нам в любом случае нужна лицензия. Думал что вы сталкивались с подобными ситцациями. Прост вы в России живем, законы есть, а вот их соблюдение хромает) Вот и хотел узнать)
0
Да че ж меня руки не слушаются) хотел написать «МЫ в России живем,»
0
Процессорами с хардварным ускорение AES торгуют уже не первый год. Многие трансиверы умеют шифровать данные на лету.
Так, что «лицензией» никто не замарачивается.
0
Ага, ага, только если попробовать сделать на таком чипе что то вроде eToken или ruToken, для использования в организациях для защиты данных, лицензии ой как потребуются. Для себя то конечно да, лицензии не нужны. Так же и ПО криптографическое.
0
вот именно что в таких процах именно ускорение AES. насколько помню имеется 4 функции для шифрования и дешифрования и 1 для генерации ключей. А сам аес мы удобно реализуем в виде пачки вышеперечисленных инструкций и кода для оставшейся инифицализации, обраотки и т.д. Так что это не процессоры с шифрованием, а всего лишь с удобными инструкциями для реализации шифрования AES.
0
Интересно почитать статьи на эту тему, с примерами. Чтоб потом воспользоваться можно было.
+1
Интересная статья… Но в описанном подходе имхо есть один минус — если не менять ключи то за недельку-другую можно и подобрать… Мне всегда было интересно, к примеру в автомобильных сигналках вообще хитрее сделано, или все так просто? )
0
  • avatar
  • N1X
  • 24 ноября 2011, 18:58
За недельку не получится. AES128 до сих пор не взломан. Есть только теории, не более.
Алгоритм ГОСА серьезным проверкам не подвергался, но и его взломать так быстро не получится.
0
Даже 3DES не взломан.
0
Помнится проскакивала компроментация ГОСТа. Ссыль ща уже не найду. Атаку проводили на слегка упрощенный ГОСТ. Глядишь, так и через пару лет до полнораундового доберутся)
У ГОСТа также есть ещё слабое место — его sbox`ы. В стандарте насколько помню они есть, но в качестве примера. Наши органы с этими sbox`ами хитрят.

На мой взгляд в МК, особенно 8-ми битных логичней использовать поточные шифры(RC4 и подобные) или AES.

P.S.: криптографией интересуюсь, алгоритмы по-тихоньку реализовываю, могу и статей написать по криптографии. Если автор конечно не против) Писать?
0
Да информация о «взломе» ГОСТа проскакивала, но пруфов я не видел. Я не агитирую использовать именно ГОСТ – просто привел в качестве примера.
А статью обязательно напишите. Почему я должен быть против? Больше статей, хороших и разных!
0
не, не. ГОСТ не взломали, а всего лишь скомпроментировали. т.е. это все равно что Вы бы нашли уязвимость в 4 раундовом DES`e а не в полноценном 16ти.
Гост претендует на замену AES и 3DES. за 20 лет как-то не густо в области анализа, на мой взгляд. Но, повторюсь, меня смущат блоки подстановки)

кстати вот статья по анализу криптостойкости ГОСТа(на англицком) eprint.iacr.org/2011/211.pdf
0
Я специально написал «взломали» в кавычках, т. к. все статьи, которые я видел по этому поводу отдавали «желтизной» :) Например эта статья.
0
Пардон, не заметил)
0
Пишите пишите, мне тоже это интересно!
0
За недельку не получится :) Давайте считать. Предположим, что алгоритм шифрования выполняется за один такт процессора (например, у нас специализированный процессор). И процессор работает на частоте 2^28 Гц (приблизительно 248 ГГц). Тогда время полного перебора ГОСТ 28 147 ключа (256 бит) займет 2^256 / 2^28 = 2^228 секунд. Очень длинная будет неделька :)
Ключи шифрования в серьезных криптосистемах действительно периодически меняют, однако срок действия ключа обычно исчисляется годами. Дело в том, что при переборе работает теория вероятностей, есть шанс, что мы «угадаем» секретный ключ с первой попытки. Правда, вероятность такого везения 1 / 2^256
0
в нашей стране срок действия ключа обычно один год, ФСБ так требует, естественно если ключ не скомпроментирован.
0
В хороших сигналках используют диалоговый код — forum.ugona.net/topic6957.html, пример алгоритма — алгоритм Фиата-Шамира.

Если система сделана нормально — то это ассиметричные ключи.
В базе записан открытый ключ брелка. Посылается случайное число. Оно шифруется закрытым ключом брелка и посылается обратно. Открытым ключом его можно дешифровать. Если дешифровка совпадет, то значит это свой брелок. Это принцип цифровой подписи. Надежность его очень высока. Никакие там 20-1000-1000000 записанных ответов не подойдут, только если база не пошлет точно такое же число с ранее посланным (но это бред). Подбор ключа по открытому и закрытому числу можно сделать математически, т.е. дома. Но если ключ 256 бит, то это тысячи лет компа с учетом роста производительности по экспоненте.
0
Используют ещё KeeLoq («прыгающий код»), но это вчерашний день. Математика у Килога абсолютно достаточна для того, чтобы его нальзя было расшифровать и в самой простой конфигурации. По крайней мере раскрутить Киложный код пока еще никто не смог и упоминаний об этом я нигде не встречал.
Вопрос же в том, что при ОДНОСТОРОННЕМ канале никто и не собирается раскручивать килог, его просто подменяют методом подстановки.(портят хорошую посылку, запоминают ее и передают в следующий раз). Суть перехвата в данном случае главным образом зависит не от крутости математики, а от физических свойств канала.
Поэтому нет никакой разницы, будь там 100 или 1000 битные ключи. Не в них дело.
Принципиально решается вопрос в двустороннем диалоговом протоколе авторизации, описанном в предыдущем комменте.
0
Сигналка <--запрос-- Брелок
Сигналка --случайное число--> Брелок
… брелок шифрует случайное число закрытым ключом…
Сигналка <--Шифрованное закрытым ключом случ.число-- Брелок
… Открытым ключом сигналка дешифрует шифр-е число с брелка,
если числа совпадают — значит этой свой брелок

При привязке брелка передаётся закрытый ключ, потому лучше привязку делать по проводам или оптическому каналу (led-фотодатчик).
0
В плане аппаратной реализации для диалогового режима можно посмотреть в сторону XBee 24 (http://www.terraelectronica.ru/pdf/DIGI/XB24-ACI-001.pdf) — этот модуль имеет на борту шифрование по стандарту AES с ключом 128 бит, осуществляемое «на лету», причём скорость передачи данных до 115200 бит/с. Потребление всего модуля 140 мВт — и это на всё, включая передатчик, контроллер и модуль шифрования.

Если народ еще знает компактные, дальнобойные и недорогие решения для брелка (конкретно двусторонний режим обмена данными с аппаратным шифрованием) — отпишитесь)
0
А такие штуковины согласуются с чекистами? Что дома используют пофиг, а в коммерческих изделиях как бе лицензию надо получать.
0
Недавно обнаружил нордиковские чипы www.nordicsemi.com/eng/Products/2.4GHz-RF/nRF24L01 где-то видел, что удавалось наладить связь на расстоянии 800 метров
0
Старый-добрый HC-04 на BlueCore. Подумать только — не прошло и 15 лет, как Bluetooth революция свершилась, модуль теперь действительно стоит менее $10. А XBee еще махать десяток строго режима, пока он станет интересен.

Еще nRF24LE1 станет интересным, когда будет стоить по 20 копеек штучка, по баксу пучок (модуль). Правда, китайцы не ждут 10 лет, и собирают революционных матросов уже сегодня.
0
И сколько вы таких систем видели — с привязкой по оптическому каналу? ;-) Тут варианта два: либо не заморачиваться и ставить классегу на ASK с «железным» декодером на 128 значений, либо уже делать нормально, где можно и привязку делать по RF. Но нормально делать сложно, поэтому я думаю, в большинстве «сигналок» стоит ASKашка.
0
А хэш-функции какие используются. пробежаться по самым известным, да «присолить» их номером брелка, команды и т.д. Возможно и можно будет вычислить алгоритм, если он не самопальный конечно)
0
вместо вопроса точку поставил.
0
В подробности не вникал, у меня до сих пор лишь поверхностный интерес к этому был. Надеюсь, более знающие люди подскажут.
0
Скорее всего, они подписываю сами данные (случайное число) а не хеш от данных.
0
Если размер данных (случайного числа) сопоставим с размером хеш от этих данных – зачем считать и подписывать хеш – можно подписать сам данные.
0
Теперь понял Вас. о разном говорим, я к тому что по ссылке говрится именно про передачу хэша, и про открытую криптографию никакой речи не велось в той ветке. Это то меня и в непонятки вогнало
0
Не совсем понял что вы имеете виду под подписыванием. По сслыке, которую предоставил tzirulnicov forum.ugona.net/topic6957.html — про ассиметричную криптографию не пишут. Пишут что схема такая:
сигнашка посылает брелку случайное число. Брелок хэширует и отправляет обратно. Поправьте, мож я че не увидел в ссылке. Опять же про протокол Фиата-Шамира ни слова. интересно аж стало с сигнашками)
0
Упс, я извиняюсь. Ссылку не смотрел, а из комментариев
Это принцип цифровой подписи.
я решил, что там используется ЭЦП.
0
Отличная статья, +1. За алгоритм спасибо.
0
  • avatar
  • _YS_
  • 24 ноября 2011, 19:17
Спасибо. Ждем продолжения.
0
Хорошая статья, спасибо. Хотелось бы далее услышать про скремблеры, так как их алгоритмы относительно просты, и заточены как раз на постоянный обмен информацией в реальном времени.
0
Вы имеет в виду скремблеры аналоговые? или цифровые варианты? По сути это генератор гаммы известный обеим сторонам, учавствующих в обмене информацией. В качестве скрэмблирования можно сжать исходные данные)
0
Ну коль речь о МК, то цифровые. Но и про аналоговые, тоже было бы интересно, так раньше их описания не встречал. Просто для МК типа авр и тп, главная проблема с шифрами и это тормознутость и громоздкость либ. Скремблер насколько я помню в теории, хоть и менее криптоустойчив, но значительно проще в реализации. Хотя и менее надежен для разовых посылок, типа автосигнализаций.
ЗЫ(мысли в слух) Помнится что методы криптографии не возбраняется комбинировать между собой (даже самые простые), и хотя правильность такой махинации, это уже матан. Возможно это и есть выход для слабеньких МК.
0
Для МК самым удобным вариантом, на мой взгляд, я вляется RC4 — довольно гибкий, надежный шифр, ну и шустрый конечно.
0
Почитал описание RC4, действительно простой, надо будет проверить его насколько он загружает МК (как понял из статьи на вики, самая сложная операция (по времени) это инициализация).
0
нагружать будет не сильно. но вот памяти расходует прилично. 256 байт на «Sbox» (при размере слова в 8 бит) + 2 счетчика по 2 байта. итого 258 байт. Сейчас допиливаю алгоритм генератора гаммы (RC4 — тоже генератор гаммы) конечно число состояний меньше чем у RC4: ~2^142 против 2^256. Но у моего алгоритма есть класс слабых ключей, ну и гамма не всем тестам удовлетворяет. Фишка моег алгоритма в том что памяти расходует мало, как ОЗУ так и ПЗУ, но плата за это — медленне чем RC4, но побыстрее блочных, и существование слабых ключей. Если Вам интересно то после сессии могу опубликовать здесь свои наработки.
0
Прилично — в масштабах 8мибитного МК
0
Конечно интересно, как сможете то выкладывайте. Так как в инете по шифрованию либо матан, либо монструозные библиотеки. Буду ждать.
+1
а вот комбинировать как правило настойчиво не рекомендуется, т.к. в итоге можно получить гораздо меньшую устойчивость к взлому.
0
ну, аналоговые скремблеры обычно юзали простой сдвиг(замену) частот. это даже не прошлый, а позапрошлый век.
для цифровых применяются потоковые шифры, хотя при небольшом размере блока и достаточной скорости канала вполне применимы и блочные шифры.
0
обычно юзали простой сдвиг(замену) частот

А та смена частот, в те «века», была предсказуема или происходила по алгоритму известному только приёмнику и передатчику? А сейчас при наличии широкополосного сканера, менять частоты по определённому алгоритму уже нет смысла, получается? Или есть смысл? А если по известному только паре передатчик-приёмник менять параметры модуляции?
0
Слово прропустил )
… если по известному только...
… если по алгоритму, известному только комплекту передатчик-приёмник…

Хотя каждый из них уже не полукомплект, а полноценный трансивер.
0
Статья полезная! Но вот вопрос, где реализация самого алгоритма, а не библиотечной функции?
Кстати, вот реализация

Вот, например, реализация алгоритма xtea:

void xtea();
{  
     xs=0;     
     xd=0x9E3779B9;      
     for (xi=0; xi < 32; xi++) 
     {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (xs + kx[xs & 3]);
        xs += xd;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (xs + kx[(xs>>11) & 3]);
    }   
}

используется в разработанной мной проивоугонке, которая работает по следующему принципу:
1. Базовый блок генерирует 2 32-х битных случайных числа, из двух последних бит помехи на АЦП.
2. Передаем на электронный ключ.
3. Электронный ключ их шифрует своим ключом и пересылает на базовый блок.
4. Базовый блок тоже шифрует исходный случайный текст тем же ключом что и электронный ключ.
5. Сравниваем зашифрованное в базовом блоке с полученным от ключа…

Короче все банально просто…
0
Пример реализации ГОСТ 28 147 прикреплен отдельным файлом к статье, вместе с примером использования.
0
О!.. Спасиб, не заметил!
0
По сути вы реализовали обычный такой протокол challenge-response и вам на самом деле была нужна функция хеширования, по сути вы изобразили какой-то подвид оного используя вместо нее варант. Если не рассматривать суперзлобных MITM, даже вроде вполне себе вариант.
0
однозначно плюс и просьба о дальнейшем продолжении цикла статей
0
Спасибо. Просим RSA.
0
  • avatar
  • dnf
  • 25 ноября 2011, 13:24
По части криптографии позволю себе немного критики.
1. DES — гадость! Люди! Забудьте о нем и никогда не вспоминайте. Считайте что его никогда не существовало. Он медленный и нестойкий. Одновременно! Для чисто практических целей, несколько машин считающих на GPU при современном уровне развития технологий совершенно без проблем переберут 56 бит ключа брутфорсом за какие-то дни. Если планка настолько низко — а может вам и не нужно шифрование вообще? Иллюзия защиты — хуже чем полное отсутствие оной.
2. Лично я ГОСТу не доверяю. Там используются S-BOX'ы заполненные по никому не известному алгоритму. Разным конторам выдают разные s-box, что является плохим признаком. У криптографов есть подозрения что некие сочетания s-box'ов могут сильно просаживать стойкость алгоритма. Я бы такому алгоритму доверять секреты не стал бы.
3. Из простеньких но не идеально защищенных от всего и вся алгоритмов имхо заслуживают внимание штуки типа XTEA (но ни в коем разе не TEA и не XXTEA!) и (при грамотном использовании!) ARCfour (aka RC4). Хороши тем что просто реализуются, даже на голом асме. Любители экспериментов на свой зад могут рискнуть и глянуть на VMPC но он малоизучен криптографами, по сути — видоизменение ARC4 с похожими свойствами.
4. Из кондовых — внушают доверие blowfish, twofish. Есть еще AES, но опять же, может так выйти что американцы выбрали стандартом шифр которые кому надо умеют более просто вскрывать чем все остальные. Хотя общеизвестных методов его более-менее практически осуществимого вскрытия вроде как не нашлось пока.
+1
ARCfour (aka RC4). Хороши тем что просто реализуются, даже на голом асме.
О да. Я был впечатлен, заглянув в плагин iscrypt от Inno Setup. 3 строчки на С.

А в чем заключается грамотное использование?

Алсо, чем именно плохи TEA и XTEA? Для остальных (ГОСТ, DES, etc) ты хотя бы кратко указал причины.
0
И на асме — около 40 команд:)
0
Грамотное использование любого потокового шифра заключается в том, что никогда и не при каких условиях нельзя использовать один и тот же ключ. RC4 не имеет вектора инициализации, поэтому необходимо в качестве его ключа использовать, скажем, хэш от склейки сессионного и «постоянного» ключа. Но никак не их простую склейку.
0
Честно говоря, не понял.
Алсо, чем именно плохи TEA и XTEA?
Тьфу, XXTEA.
0
чем XXTEA не угодил? является исправлением всех своих предшественников.
0
Во первых, у ARCFOUR надо пропустить первые 1024 байта вывода этого PRNG, в них содержится достаточно сильная утечка сведений о ключах.
0
И я опять ничего не понял. Можно поподробнее? К тому же «во первых» обычно подразумевает, что есть и «во вторых».
0
Упс, комент убежал досрочно :(
3 строчки на С.
Ну не 3 конечно, но реально простой и чертовски быстрый алгоритм, что дает ему явную фору на uC'ах.

А в чем заключается грамотное использование?
1) Во первых, у ARCFOUR надо пропустить первые 512...1024 байта вывода этого PRNG, в них содержится достаточно сильная утечка сведений о ключе. Лучше 1024, если можно позволить себе это.
2) Во вторых, вот так влобовую им нельзя шифровать одним ключом разные данные и данные заведомо известные злоумышленнику. Это всего лишь генератор псевдослучайных чисел XORимый с потоком. Ключ инициализирует его в некое состояние. С одним и тем же ключом вывод PRNG будет, очевидно, каждый раз одинаковый. А т.к. выход оного всего лишь XORится с входными данными, в ряде случаев это дает атакующему невкусные возможности. Скажем, если он может всучить свои данные, то зная их и имея их зашифрованный вариант — можно восстановить последовательность выднную PRNG, элементарно проксорив шифрованый поток с нешифрованными известными данными. Ну а потом когда надо что-то секретное перехватить — мы же уже знаем что выдаст PRNG! Поэтому можем проксорить и это, получив и неизвестные нам данные. А вот это уже нехорошо с точки зрения шифрования :). Лечится все это путем добавления «initialization vector» в начало шифрованных данных. Цель существования этого числа: поток шифрованных данных должен быть каждый раз разным даже при одинаковом ключе. Что достигается разными IV. Поэтому и требование случайности и достаточной разрядности: совпаление IV недопустимо, на этом WEP и погорел как раз, там всего 24 бита и при достаточном числе пакетов IV совпадает и получается ай-яй-яй описаный выше. У arcfour в самом алгоритме нет стандартного оговоренного алгоритма как донавешивать IV. Это на усмотрение реализующего. Мне кажется логичным делать примерно так: генерим себе 192...256 битов случайных данных. Они будут новым ключом («сессионным»). Шифруем сие основным ключом. Поскольку это рандом, мы не палим arcfour'овский PRNG на одном и том же дважды (вероятность сгененить 256 битов одинаково при честном random можно считать нулевой). Остальное (т.е. сами данные) шифруем уже новым ключом (т.е. своим сгенеренным рандомом). Очевидно, каждый раз разным (рандом же). А для расшифровки сперва расшифровываем те 128...256 битов, откуда узнаем какой был рандомный ключ. И вот им уже расшифровываем остальное. Так у нас каждый раз разные потоки даже на одинаковых наборах данных и ключах. Не вижу очевидных ляпусов в подобной схеме. Сие несколько усложняет дело и получается чуть побольше — надо 2 раза инициализировать алгоритм. Ну и скипать 1024 байта очень желательно, опять же.
3) Кстати насколько я знаю, есть техника атаки позволяющая отличить истинный рандом от выхода ARC4 если можно набрать порядка 16Мбайтов шифрованного материала. Это плохой признак в криптографии. Правда ничего суперполезного на практике это вроде как атакующим не дает, но все-таки.

То-есть, arcfour в принципе то можно использовать. Но осторожно. Понимая слабые места. С их учетом он будет поболее 3 строчек, увы.

Алсо, чем именно плохи TEA и XTEA?
TEA плох тем что поломан. XTEA ничем не плох, известных проблем которые что-то меняют — нет. Но еще есть XXTEA, а вот он — поломан. Правда частично и менее сурово чем TEA, но лучше и его обойти сторонкой. Более подробно про атаки и их подробности есть в вике, как минимум английской. Поэтому из всех tea я бы обращал внимание разве только на XTEA как раз (использовать поломанные алгоритмы не умно если можно взять нормальные :P).
0
1) Во первых, у ARCFOUR надо пропустить первые 512...1024 байта вывода этого PRNG, в них содержится достаточно сильная утечка сведений о ключе. Лучше 1024, если можно позволить себе это.
Т.е. перед основными данными зашифровать килобайт чего попало, отправив результат кодирования в null, а на приемном конце сперва расшифровать килобайт же чего попало?
0
Т.к. шифрование сводится к XOR входных данных с выводом PRNG, а состояние PRNG не зависит от подаваемых данных, а только от ключа и числа итераций, логично что на подачу данных и их ксорку можно честно забить. PRNG и без этого поток псевдослучайных чисел генерит. Т.е. прокрутить только саму тасовку значений PRNG в цикле вполне хватит, на XOR с входом и передачу-забить. На приемнике сделать то же самое. Поскольку PRNG при одинаковом ключе синхронны, скипание 1024 значений PRNG на приемнике приведет его в то же состояние как было в этот же момент на передатчике. И передавать ничего не надо, и битики ключа не утекут.
0
Понятно. А поясни более подробно, что такое IV.
0
будте добры, пожалуйста, ссылку на доказательство взлома XXTEA.
0
Спасибо за критику.
На самом деле я не пропагандирую какой либо конкретный алгоритм, хотелось просто рассказать о блочном симметричном шифровании и его применении. ГОСТ я привел для примера.

Если говорить о серьезной защите и криптоанализе, то хочу добавить, что лучше не использовать алгоритмы работающие в режиме «электронной кодовой книги» (ECB) так как после шифрования могут сохранится статистические особенности открытого текста.
0
я так понял, чтобы взломать например брелок автосигнализации нужно:
1) поймать текст который нужно зашифровать
2) поймать зашифрованый текст
3) унать тип шифрования (например по модели сигнализации и формату посылки брелка)
4) брутфорсом шифровать открытый текст пока результат не совпадет с зашифрованным
5) ПРОФИТ!
хотябы частично верно?

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

Я конечно не рассматриваю случаи когда этим хранят секретные документы государтва, а например открывалку ворот на дачу на 8 битной тиньке. А как на счет такой системы в самодельной сигнализации?

О_о
0
Да, вы все правильно поняли. Ключевой момент

брутфорсом шифровать открытый текст пока результат не совпадет с зашифрованным

Попробуйте методом грубой силы сломать тот-же DES (хотя от данного стандарта уже отказались), оцените временные и денежные затраты на взлом.

Изобретать свой алгоритм не эффективно – он Вам может казаться супер надежным, но быть уязвимым пред современными методами криптоанализа.
0
Если говорить о современных брелках автосигнализации – там используют ассиметричные алгоритмы, ЕЦП, методы непосредственной аутентификации отправителя.
0
Грамотно сделанная сигналка не позволит «брутфосить» и через пару-тройку неправильных «ответов» от якобы брелка уйдет в игнор на некоторое время.
Кстати, плюсом самописного алгоритма шифрования является то, что никто о нем не знает, т.е. вероятность взлома становится крайне мала, хотя это и не принято в криптографии, т.к. обычно исходят из того, что злоумышленнику известен алгоритм, а не известен только ключ и, как правило, исходное сообщение.
0
наверно рядовой взломщик пользуется каким то прибором, с заданными алгоритмами так что никто не будет смотреть логи вручную и решать даже пусть супер легкий алгоритм)))
0
Для брутфорса не нужно постоянно контактировать с «брелком». Достаточно перехватить «запрос» и «ответ» и можно дома, не спеша, брутфорсить. Здесь только одна проблема – когда программа методом грубой силы подберет ключ, не будет уже ни Вас, ни машины, которую вы хотели открыть, да и существование человечества может быть под вопросом :)

Касательно «самописных алгоритмов» — помимо проблем, которые я уже описывал, есть еще одна – как гарантированно обеспечить «секретность» алгоритма? Например, в компании, в которой несколько человек работают над кодом и еще куча человек имеет доступ к скомпилированной прошивке. С секретным ключом все просто, он может гарнироваться самостоятельно, внутри устройства или, например, генерироваться по инициативе конечного пользователя.
0
Да интересная статья. Слышал что у спецслужб есть универсальный взломщик любых защит и паролей. Называется ректально-термальный криптоанализатор.
+1
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.