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

В данной статье я попытаюсь «на пальцах» (насколько это возможно) рассказать об одном из криптографических алгоритмов и показать, как данный алгоритм можно применять на практике в контексте устройств на базе МК.
Описание будет максимально упрощено, мы не будем вникать в саму реализацию алгоритма (математику) и тонкости криптоанализа :)
Криптография – это просто!
Криптография включает в себя множество различных направлений, таких как шифрование, электронно-цифровая подпись, хеширование и т. д. Мы рассмотрим один из них – шифрование. Дело в том, что шифрование помимо основного назначения (предотвращение утечки информации) может использоваться для иных целей, например, для косвенной аутентификации отравителя, но об этом позже.
Шифрование.
Шифрование — это преобразование исходных данных («открытого текста») в видоизмененное состояние («закрытый текст») с целью скрыть содержимое «открытого текста» от потенциального «злоумышленника». Как подсказывает Кеп, дешифрование — это обратная процедура, восстановление «открытого текста» из «закрытого».
В данном случае понятия «открытый текст» и «закрытый текст» — это термины, которые подразумевают любую, не обязательно текстовую информацию.
Например, для того чтобы «зашифровать» данные, можно переставить местами символы в исходном тесте по определенному, известному только нам алгоритму. :) Сами понимаете, что подобный «алгоритм шифрования» походит разве что для учеников младших классов… Современная криптография такие алгоритмы всерьез не рассматривает.
Современные алгоритмы шифрования предполагают, что «злоумышленник» потенциально знает сам алгоритм шифрования (алгоритм преобразования над открытым тестом), имеет доступ к закрытому тексту, может знать фрагменты открытого текста (например «злоумышленник» предполагать, что открытый текст сообщения начинается с фразы «Добрый день!»).
Единственное, что неизвестно злоумышленнику, это некий «секрет» (секретный ключ шифрования). Это единственный «секретный» компонент, который не дает расшифровать закрытый текст. Единственный для «злоумышленника» способ вычислить секретный ключ (и расшифровать информацию целиком) — это полный перебор всех возможных вариантов секретного ключа. Считается, что длина применяемых в современных алгоритмах ключей (например, 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
А вот насколько алгоритм оптимален для микроконтроллера?
AES изначально заточен под 8ми битки. А вот ГОСТ 28 147-89 критикуют за набор сложных операций.
AES изначально заточен под 8ми битки. А вот ГОСТ 28 147-89 критикуют за набор сложных операций.
Также более интересны алгоритмы с публичными ключами. Там процесс установки защищенного соединения достаточно прост.
Реализацию ГОСТ 28 147-89 я привел для примера. Внутри стандарт оперирует 32-битными данными, соответственно никакой оптимизации под 8-биную архитектуру нет. Просто данный пример реализации очень лаконичен – приблизительно 250 строк кода треть из которых – комментарии. Найти аналогичную простую и понятную реализацию AES мне не удалось, а тянуть монстроподобную библиотеку не хотелось.
Как отмечено в статье, все сказанное применимо и к алгоритмам Triple DES и AES.
По поводу ассиметричных алгоритмов – что именно интересует? Алгоритм распределения клоча типа алгоритма Диффи — Хеллмана?
Как отмечено в статье, все сказанное применимо и к алгоритмам Triple DES и AES.
По поводу ассиметричных алгоритмов – что именно интересует? Алгоритм распределения клоча типа алгоритма Диффи — Хеллмана?
Я в своих работах использовал либу на 1.5-1.8Кб. Размер зависел от размера AES.
А фот по поводу ассимитричных интересует хоть, что-то надежное и юзабельное.
Они более жирные выходят(
А фот по поводу ассимитричных интересует хоть, что-то надежное и юзабельное.
Они более жирные выходят(
Простых в реализации ассиметричных алгоритмов я не знаю. Там, как и в ЭЦП, либо операции над большими простыми числами, либо эллиптические кривые.
Может именно ассиметричное шифрование Вам и не так необходимо. Ведь можно Использовать стойкий симметричный шифр, а для обмена ключами сделать примерно следующее:
Алиса отправляет открытый ключ Бобу
Боб генерирует случайное число, которое и будет ключом для переписки, шифрует открытым ключом Алисы и ей отправляет. Она уже с помощью закрытого ключа расифровывает ключ сгенерированный Бобом. В качестве ассиметричного шифрования можно использовать Эль-Гамаля.
Алиса отправляет открытый ключ Бобу
Боб генерирует случайное число, которое и будет ключом для переписки, шифрует открытым ключом Алисы и ей отправляет. Она уже с помощью закрытого ключа расифровывает ключ сгенерированный Бобом. В качестве ассиметричного шифрования можно использовать Эль-Гамаля.
Вы все правильно написали, обычно ассиметричные алгоритмы используются именно для передачи секретного ключа, а сами данные шифруются симметричным шифрованием, т. к. асимметричное шифрование очень медленное.
Просто я не знаю простой (легковесной) реализации механизма распределения клоча (совместной выработки ключа) подобных алгоритму Диффи — Хеллмана или схемы Эль-Гамаля.
Просто я не знаю простой (легковесной) реализации механизма распределения клоча (совместной выработки ключа) подобных алгоритму Диффи — Хеллмана или схемы Эль-Гамаля.
Собственно реализацией Эль-Гамаля на AVR (в качестве эксперимента) и хотел после сессия заняться. Посмотрим насколько много займет памяти.
На мой взгляд, обмен ключами стоит рассматривать только в реальных условиях. Каналы передачи, атаки на реализации и т.п. разные могут быть. не всегда треюуется ж 100летняя криптостойкость)
На мой взгляд, обмен ключами стоит рассматривать только в реальных условиях. Каналы передачи, атаки на реализации и т.п. разные могут быть. не всегда треюуется ж 100летняя криптостойкость)
Займитесь, займитесь. Только не забывайте, что в Bluetooth добавили Diffie-Hellman только в версии 2.1, всего лишь 3 года назад, через 10 лет после выхода BT в широкий свет и аж через 3 года после публикации аццких атак.
А почему? Да потому что у типичной гарнитурки мозгов мало (как RAM так и CPU) множить много-многобитные числа. Много лет и эллиптические кривые понадобились, чтобы сдвинуться с места.
Так что в тиньку вряд ли влезет. В меге конечно можно, только цена голой меги сравнима с ценой готового BT модуля. Поэтому для эксперемента — интересно, а практически — пользы немного.
А почему? Да потому что у типичной гарнитурки мозгов мало (как RAM так и CPU) множить много-многобитные числа. Много лет и эллиптические кривые понадобились, чтобы сдвинуться с места.
Так что в тиньку вряд ли влезет. В меге конечно можно, только цена голой меги сравнима с ценой готового BT модуля. Поэтому для эксперемента — интересно, а практически — пользы немного.
А как криптография уживается с ФСБ? в коммерческие проекты ведь её просто так не засунешь. или не смотрят за этим?
Зависит от того, где и как вы хотите применять коммерческие продукты. В некоторых случаях нужна лицензия на работу с криптографией и экспертиза. Так было раньше, сейчас не знаю.
2 примера:
1. скажем, сетевое железо с криптухой
2. лабуда типа беспроводных датчиков (пожарка, охрана)
Так понимаю если как-то задевать государство то лицензию все равно надо получать. а что в том случае если вышеперечисленное пихать по другим фирмам, лицам и т.д. и обслуживать самому?
1. скажем, сетевое железо с криптухой
2. лабуда типа беспроводных датчиков (пожарка, охрана)
Так понимаю если как-то задевать государство то лицензию все равно надо получать. а что в том случае если вышеперечисленное пихать по другим фирмам, лицам и т.д. и обслуживать самому?
Это юридический вопрос, а я не юрист :) Могу высказать только свое понимание. Если Вы позиционируете устройство как средство криптографической защиты информации – Вам нужна лицензия, экспертиза и т. д. Если Вы просто используете криптоалгоритм для реализации, например, автомобильной сигнализации – лицензия Вам не нужна.
С юридической точки зрения нам в любом случае нужна лицензия. Думал что вы сталкивались с подобными ситцациями. Прост вы в России живем, законы есть, а вот их соблюдение хромает) Вот и хотел узнать)
вот именно что в таких процах именно ускорение AES. насколько помню имеется 4 функции для шифрования и дешифрования и 1 для генерации ключей. А сам аес мы удобно реализуем в виде пачки вышеперечисленных инструкций и кода для оставшейся инифицализации, обраотки и т.д. Так что это не процессоры с шифрованием, а всего лишь с удобными инструкциями для реализации шифрования AES.
Интересная статья… Но в описанном подходе имхо есть один минус — если не менять ключи то за недельку-другую можно и подобрать… Мне всегда было интересно, к примеру в автомобильных сигналках вообще хитрее сделано, или все так просто? )
За недельку не получится. AES128 до сих пор не взломан. Есть только теории, не более.
Алгоритм ГОСА серьезным проверкам не подвергался, но и его взломать так быстро не получится.
Алгоритм ГОСА серьезным проверкам не подвергался, но и его взломать так быстро не получится.
Помнится проскакивала компроментация ГОСТа. Ссыль ща уже не найду. Атаку проводили на слегка упрощенный ГОСТ. Глядишь, так и через пару лет до полнораундового доберутся)
У ГОСТа также есть ещё слабое место — его sbox`ы. В стандарте насколько помню они есть, но в качестве примера. Наши органы с этими sbox`ами хитрят.
На мой взгляд в МК, особенно 8-ми битных логичней использовать поточные шифры(RC4 и подобные) или AES.
P.S.: криптографией интересуюсь, алгоритмы по-тихоньку реализовываю, могу и статей написать по криптографии. Если автор конечно не против) Писать?
У ГОСТа также есть ещё слабое место — его sbox`ы. В стандарте насколько помню они есть, но в качестве примера. Наши органы с этими sbox`ами хитрят.
На мой взгляд в МК, особенно 8-ми битных логичней использовать поточные шифры(RC4 и подобные) или AES.
P.S.: криптографией интересуюсь, алгоритмы по-тихоньку реализовываю, могу и статей написать по криптографии. Если автор конечно не против) Писать?
Да информация о «взломе» ГОСТа проскакивала, но пруфов я не видел. Я не агитирую использовать именно ГОСТ – просто привел в качестве примера.
А статью обязательно напишите. Почему я должен быть против? Больше статей, хороших и разных!
А статью обязательно напишите. Почему я должен быть против? Больше статей, хороших и разных!
не, не. ГОСТ не взломали, а всего лишь скомпроментировали. т.е. это все равно что Вы бы нашли уязвимость в 4 раундовом DES`e а не в полноценном 16ти.
Гост претендует на замену AES и 3DES. за 20 лет как-то не густо в области анализа, на мой взгляд. Но, повторюсь, меня смущат блоки подстановки)
кстати вот статья по анализу криптостойкости ГОСТа(на англицком) eprint.iacr.org/2011/211.pdf
Гост претендует на замену AES и 3DES. за 20 лет как-то не густо в области анализа, на мой взгляд. Но, повторюсь, меня смущат блоки подстановки)
кстати вот статья по анализу криптостойкости ГОСТа(на англицком) eprint.iacr.org/2011/211.pdf
За недельку не получится :) Давайте считать. Предположим, что алгоритм шифрования выполняется за один такт процессора (например, у нас специализированный процессор). И процессор работает на частоте 2^28 Гц (приблизительно 248 ГГц). Тогда время полного перебора ГОСТ 28 147 ключа (256 бит) займет 2^256 / 2^28 = 2^228 секунд. Очень длинная будет неделька :)
Ключи шифрования в серьезных криптосистемах действительно периодически меняют, однако срок действия ключа обычно исчисляется годами. Дело в том, что при переборе работает теория вероятностей, есть шанс, что мы «угадаем» секретный ключ с первой попытки. Правда, вероятность такого везения 1 / 2^256
Ключи шифрования в серьезных криптосистемах действительно периодически меняют, однако срок действия ключа обычно исчисляется годами. Дело в том, что при переборе работает теория вероятностей, есть шанс, что мы «угадаем» секретный ключ с первой попытки. Правда, вероятность такого везения 1 / 2^256
В хороших сигналках используют диалоговый код — forum.ugona.net/topic6957.html, пример алгоритма — алгоритм Фиата-Шамира.
Если система сделана нормально — то это ассиметричные ключи.
В базе записан открытый ключ брелка. Посылается случайное число. Оно шифруется закрытым ключом брелка и посылается обратно. Открытым ключом его можно дешифровать. Если дешифровка совпадет, то значит это свой брелок. Это принцип цифровой подписи. Надежность его очень высока. Никакие там 20-1000-1000000 записанных ответов не подойдут, только если база не пошлет точно такое же число с ранее посланным (но это бред). Подбор ключа по открытому и закрытому числу можно сделать математически, т.е. дома. Но если ключ 256 бит, то это тысячи лет компа с учетом роста производительности по экспоненте.
Если система сделана нормально — то это ассиметричные ключи.
В базе записан открытый ключ брелка. Посылается случайное число. Оно шифруется закрытым ключом брелка и посылается обратно. Открытым ключом его можно дешифровать. Если дешифровка совпадет, то значит это свой брелок. Это принцип цифровой подписи. Надежность его очень высока. Никакие там 20-1000-1000000 записанных ответов не подойдут, только если база не пошлет точно такое же число с ранее посланным (но это бред). Подбор ключа по открытому и закрытому числу можно сделать математически, т.е. дома. Но если ключ 256 бит, то это тысячи лет компа с учетом роста производительности по экспоненте.

- tzirulnicov
- 24 ноября 2011, 20:37
- ↑
- ↓
Используют ещё KeeLoq («прыгающий код»), но это вчерашний день. Математика у Килога абсолютно достаточна для того, чтобы его нальзя было расшифровать и в самой простой конфигурации. По крайней мере раскрутить Киложный код пока еще никто не смог и упоминаний об этом я нигде не встречал.
Вопрос же в том, что при ОДНОСТОРОННЕМ канале никто и не собирается раскручивать килог, его просто подменяют методом подстановки.(портят хорошую посылку, запоминают ее и передают в следующий раз). Суть перехвата в данном случае главным образом зависит не от крутости математики, а от физических свойств канала.
Поэтому нет никакой разницы, будь там 100 или 1000 битные ключи. Не в них дело.
Принципиально решается вопрос в двустороннем диалоговом протоколе авторизации, описанном в предыдущем комменте.
Вопрос же в том, что при ОДНОСТОРОННЕМ канале никто и не собирается раскручивать килог, его просто подменяют методом подстановки.(портят хорошую посылку, запоминают ее и передают в следующий раз). Суть перехвата в данном случае главным образом зависит не от крутости математики, а от физических свойств канала.
Поэтому нет никакой разницы, будь там 100 или 1000 битные ключи. Не в них дело.
Принципиально решается вопрос в двустороннем диалоговом протоколе авторизации, описанном в предыдущем комменте.

- tzirulnicov
- 24 ноября 2011, 20:40
- ↑
- ↓
Сигналка <--запрос-- Брелок
Сигналка --случайное число--> Брелок
… брелок шифрует случайное число закрытым ключом…
Сигналка <--Шифрованное закрытым ключом случ.число-- Брелок
… Открытым ключом сигналка дешифрует шифр-е число с брелка,
если числа совпадают — значит этой свой брелок
При привязке брелка передаётся закрытый ключ, потому лучше привязку делать по проводам или оптическому каналу (led-фотодатчик).
Сигналка --случайное число--> Брелок
… брелок шифрует случайное число закрытым ключом…
Сигналка <--Шифрованное закрытым ключом случ.число-- Брелок
… Открытым ключом сигналка дешифрует шифр-е число с брелка,
если числа совпадают — значит этой свой брелок
При привязке брелка передаётся закрытый ключ, потому лучше привязку делать по проводам или оптическому каналу (led-фотодатчик).

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

- tzirulnicov
- 24 ноября 2011, 20:49
- ↑
- ↓
Недавно обнаружил нордиковские чипы www.nordicsemi.com/eng/Products/2.4GHz-RF/nRF24L01 где-то видел, что удавалось наладить связь на расстоянии 800 метров

- khloponin_v
- 25 ноября 2011, 00:04
- ↑
- ↓
Старый-добрый HC-04 на BlueCore. Подумать только — не прошло и 15 лет, как Bluetooth революция свершилась, модуль теперь действительно стоит менее $10. А XBee еще махать десяток строго режима, пока он станет интересен.
Еще nRF24LE1 станет интересным, когда будет стоить по 20 копеек штучка, по баксу пучок (модуль). Правда, китайцы не ждут 10 лет, и собирают революционных матросов уже сегодня.
Еще nRF24LE1 станет интересным, когда будет стоить по 20 копеек штучка, по баксу пучок (модуль). Правда, китайцы не ждут 10 лет, и собирают революционных матросов уже сегодня.
И сколько вы таких систем видели — с привязкой по оптическому каналу? ;-) Тут варианта два: либо не заморачиваться и ставить классегу на ASK с «железным» декодером на 128 значений, либо уже делать нормально, где можно и привязку делать по RF. Но нормально делать сложно, поэтому я думаю, в большинстве «сигналок» стоит ASKашка.
А хэш-функции какие используются. пробежаться по самым известным, да «присолить» их номером брелка, команды и т.д. Возможно и можно будет вычислить алгоритм, если он не самопальный конечно)
В подробности не вникал, у меня до сих пор лишь поверхностный интерес к этому был. Надеюсь, более знающие люди подскажут.

- tzirulnicov
- 24 ноября 2011, 20:56
- ↑
- ↓
Не совсем понял что вы имеете виду под подписыванием. По сслыке, которую предоставил tzirulnicov forum.ugona.net/topic6957.html — про ассиметричную криптографию не пишут. Пишут что схема такая:
сигнашка посылает брелку случайное число. Брелок хэширует и отправляет обратно. Поправьте, мож я че не увидел в ссылке. Опять же про протокол Фиата-Шамира ни слова. интересно аж стало с сигнашками)
сигнашка посылает брелку случайное число. Брелок хэширует и отправляет обратно. Поправьте, мож я че не увидел в ссылке. Опять же про протокол Фиата-Шамира ни слова. интересно аж стало с сигнашками)
Хорошая статья, спасибо. Хотелось бы далее услышать про скремблеры, так как их алгоритмы относительно просты, и заточены как раз на постоянный обмен информацией в реальном времени.
Вы имеет в виду скремблеры аналоговые? или цифровые варианты? По сути это генератор гаммы известный обеим сторонам, учавствующих в обмене информацией. В качестве скрэмблирования можно сжать исходные данные)
Ну коль речь о МК, то цифровые. Но и про аналоговые, тоже было бы интересно, так раньше их описания не встречал. Просто для МК типа авр и тп, главная проблема с шифрами и это тормознутость и громоздкость либ. Скремблер насколько я помню в теории, хоть и менее криптоустойчив, но значительно проще в реализации. Хотя и менее надежен для разовых посылок, типа автосигнализаций.
ЗЫ(мысли в слух) Помнится что методы криптографии не возбраняется комбинировать между собой (даже самые простые), и хотя правильность такой махинации, это уже матан. Возможно это и есть выход для слабеньких МК.
ЗЫ(мысли в слух) Помнится что методы криптографии не возбраняется комбинировать между собой (даже самые простые), и хотя правильность такой махинации, это уже матан. Возможно это и есть выход для слабеньких МК.
Для МК самым удобным вариантом, на мой взгляд, я вляется RC4 — довольно гибкий, надежный шифр, ну и шустрый конечно.
Почитал описание RC4, действительно простой, надо будет проверить его насколько он загружает МК (как понял из статьи на вики, самая сложная операция (по времени) это инициализация).
нагружать будет не сильно. но вот памяти расходует прилично. 256 байт на «Sbox» (при размере слова в 8 бит) + 2 счетчика по 2 байта. итого 258 байт. Сейчас допиливаю алгоритм генератора гаммы (RC4 — тоже генератор гаммы) конечно число состояний меньше чем у RC4: ~2^142 против 2^256. Но у моего алгоритма есть класс слабых ключей, ну и гамма не всем тестам удовлетворяет. Фишка моег алгоритма в том что памяти расходует мало, как ОЗУ так и ПЗУ, но плата за это — медленне чем RC4, но побыстрее блочных, и существование слабых ключей. Если Вам интересно то после сессии могу опубликовать здесь свои наработки.
ну, аналоговые скремблеры обычно юзали простой сдвиг(замену) частот. это даже не прошлый, а позапрошлый век.
для цифровых применяются потоковые шифры, хотя при небольшом размере блока и достаточной скорости канала вполне применимы и блочные шифры.
для цифровых применяются потоковые шифры, хотя при небольшом размере блока и достаточной скорости канала вполне применимы и блочные шифры.
обычно юзали простой сдвиг(замену) частот
А та смена частот, в те «века», была предсказуема или происходила по алгоритму известному только приёмнику и передатчику? А сейчас при наличии широкополосного сканера, менять частоты по определённому алгоритму уже нет смысла, получается? Или есть смысл? А если по известному только паре передатчик-приёмник менять параметры модуляции?
Статья полезная! Но вот вопрос, где реализация самого алгоритма, а не библиотечной функции?
Кстати, вот реализация
Вот, например, реализация алгоритма xtea:
используется в разработанной мной проивоугонке, которая работает по следующему принципу:
1. Базовый блок генерирует 2 32-х битных случайных числа, из двух последних бит помехи на АЦП.
2. Передаем на электронный ключ.
3. Электронный ключ их шифрует своим ключом и пересылает на базовый блок.
4. Базовый блок тоже шифрует исходный случайный текст тем же ключом что и электронный ключ.
5. Сравниваем зашифрованное в базовом блоке с полученным от ключа…
Короче все банально просто…
Кстати, вот реализация
Вот, например, реализация алгоритма 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. Сравниваем зашифрованное в базовом блоке с полученным от ключа…
Короче все банально просто…

- mr_freeman
- 24 ноября 2011, 22:45
- ↓
Пример реализации ГОСТ 28 147 прикреплен отдельным файлом к статье, вместе с примером использования.
По части криптографии позволю себе немного критики.
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. DES — гадость! Люди! Забудьте о нем и никогда не вспоминайте. Считайте что его никогда не существовало. Он медленный и нестойкий. Одновременно! Для чисто практических целей, несколько машин считающих на GPU при современном уровне развития технологий совершенно без проблем переберут 56 бит ключа брутфорсом за какие-то дни. Если планка настолько низко — а может вам и не нужно шифрование вообще? Иллюзия защиты — хуже чем полное отсутствие оной.
2. Лично я ГОСТу не доверяю. Там используются S-BOX'ы заполненные по никому не известному алгоритму. Разным конторам выдают разные s-box, что является плохим признаком. У криптографов есть подозрения что некие сочетания s-box'ов могут сильно просаживать стойкость алгоритма. Я бы такому алгоритму доверять секреты не стал бы.
3. Из простеньких но не идеально защищенных от всего и вся алгоритмов имхо заслуживают внимание штуки типа XTEA (но ни в коем разе не TEA и не XXTEA!) и (при грамотном использовании!) ARCfour (aka RC4). Хороши тем что просто реализуются, даже на голом асме. Любители экспериментов на свой зад могут рискнуть и глянуть на VMPC но он малоизучен криптографами, по сути — видоизменение ARC4 с похожими свойствами.
4. Из кондовых — внушают доверие blowfish, twofish. Есть еще AES, но опять же, может так выйти что американцы выбрали стандартом шифр которые кому надо умеют более просто вскрывать чем все остальные. Хотя общеизвестных методов его более-менее практически осуществимого вскрытия вроде как не нашлось пока.
ARCfour (aka RC4). Хороши тем что просто реализуются, даже на голом асме.О да. Я был впечатлен, заглянув в плагин iscrypt от Inno Setup. 3 строчки на С.
А в чем заключается грамотное использование?
Алсо, чем именно плохи TEA и XTEA? Для остальных (ГОСТ, DES, etc) ты хотя бы кратко указал причины.
Грамотное использование любого потокового шифра заключается в том, что никогда и не при каких условиях нельзя использовать один и тот же ключ. RC4 не имеет вектора инициализации, поэтому необходимо в качестве его ключа использовать, скажем, хэш от склейки сессионного и «постоянного» ключа. Но никак не их простую склейку.
Упс, комент убежал досрочно :(
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 строчек, увы.
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).
1) Во первых, у ARCFOUR надо пропустить первые 512...1024 байта вывода этого PRNG, в них содержится достаточно сильная утечка сведений о ключе. Лучше 1024, если можно позволить себе это.Т.е. перед основными данными зашифровать килобайт чего попало, отправив результат кодирования в null, а на приемном конце сперва расшифровать килобайт же чего попало?
Т.к. шифрование сводится к XOR входных данных с выводом PRNG, а состояние PRNG не зависит от подаваемых данных, а только от ключа и числа итераций, логично что на подачу данных и их ксорку можно честно забить. PRNG и без этого поток псевдослучайных чисел генерит. Т.е. прокрутить только саму тасовку значений PRNG в цикле вполне хватит, на XOR с входом и передачу-забить. На приемнике сделать то же самое. Поскольку PRNG при одинаковом ключе синхронны, скипание 1024 значений PRNG на приемнике приведет его в то же состояние как было в этот же момент на передатчике. И передавать ничего не надо, и битики ключа не утекут.
Спасибо за критику.
На самом деле я не пропагандирую какой либо конкретный алгоритм, хотелось просто рассказать о блочном симметричном шифровании и его применении. ГОСТ я привел для примера.
Если говорить о серьезной защите и криптоанализе, то хочу добавить, что лучше не использовать алгоритмы работающие в режиме «электронной кодовой книги» (ECB) так как после шифрования могут сохранится статистические особенности открытого текста.
На самом деле я не пропагандирую какой либо конкретный алгоритм, хотелось просто рассказать о блочном симметричном шифровании и его применении. ГОСТ я привел для примера.
Если говорить о серьезной защите и криптоанализе, то хочу добавить, что лучше не использовать алгоритмы работающие в режиме «электронной кодовой книги» (ECB) так как после шифрования могут сохранится статистические особенности открытого текста.
я так понял, чтобы взломать например брелок автосигнализации нужно:
1) поймать текст который нужно зашифровать
2) поймать зашифрованый текст
3) унать тип шифрования (например по модели сигнализации и формату посылки брелка)
4) брутфорсом шифровать открытый текст пока результат не совпадет с зашифрованным
5) ПРОФИТ!
хотябы частично верно?
а если так то не проще придумать свой алгоритм, который легко решается обычными системами уравнений, но требующий что бы твой сигнал засекли столько раз сколько неизвестных в алгоритме.(И на каждый байт передаваемой информации свой чуть чуть другой алгоритм)
да еще использовать массив ключей, столько, сколько памяти осталось в контроллере… и что бы они псевдорандомно(зависит только от предыдущего номера ключа) синхронно переключались???
Я конечно не рассматриваю случаи когда этим хранят секретные документы государтва, а например открывалку ворот на дачу на 8 битной тиньке. А как на счет такой системы в самодельной сигнализации?
О_о
1) поймать текст который нужно зашифровать
2) поймать зашифрованый текст
3) унать тип шифрования (например по модели сигнализации и формату посылки брелка)
4) брутфорсом шифровать открытый текст пока результат не совпадет с зашифрованным
5) ПРОФИТ!
хотябы частично верно?
а если так то не проще придумать свой алгоритм, который легко решается обычными системами уравнений, но требующий что бы твой сигнал засекли столько раз сколько неизвестных в алгоритме.
да еще использовать массив ключей, столько, сколько памяти осталось в контроллере… и что бы они псевдорандомно(зависит только от предыдущего номера ключа) синхронно переключались???
Я конечно не рассматриваю случаи когда этим хранят секретные документы государтва, а например открывалку ворот на дачу на 8 битной тиньке. А как на счет такой системы в самодельной сигнализации?
О_о
Да, вы все правильно поняли. Ключевой момент
Попробуйте методом грубой силы сломать тот-же DES (хотя от данного стандарта уже отказались), оцените временные и денежные затраты на взлом.
Изобретать свой алгоритм не эффективно – он Вам может казаться супер надежным, но быть уязвимым пред современными методами криптоанализа.
брутфорсом шифровать открытый текст пока результат не совпадет с зашифрованным
Попробуйте методом грубой силы сломать тот-же DES (хотя от данного стандарта уже отказались), оцените временные и денежные затраты на взлом.
Изобретать свой алгоритм не эффективно – он Вам может казаться супер надежным, но быть уязвимым пред современными методами криптоанализа.
Грамотно сделанная сигналка не позволит «брутфосить» и через пару-тройку неправильных «ответов» от якобы брелка уйдет в игнор на некоторое время.
Кстати, плюсом самописного алгоритма шифрования является то, что никто о нем не знает, т.е. вероятность взлома становится крайне мала, хотя это и не принято в криптографии, т.к. обычно исходят из того, что злоумышленнику известен алгоритм, а не известен только ключ и, как правило, исходное сообщение.
Кстати, плюсом самописного алгоритма шифрования является то, что никто о нем не знает, т.е. вероятность взлома становится крайне мала, хотя это и не принято в криптографии, т.к. обычно исходят из того, что злоумышленнику известен алгоритм, а не известен только ключ и, как правило, исходное сообщение.
Для брутфорса не нужно постоянно контактировать с «брелком». Достаточно перехватить «запрос» и «ответ» и можно дома, не спеша, брутфорсить. Здесь только одна проблема – когда программа методом грубой силы подберет ключ, не будет уже ни Вас, ни машины, которую вы хотели открыть, да и существование человечества может быть под вопросом :)
Касательно «самописных алгоритмов» — помимо проблем, которые я уже описывал, есть еще одна – как гарантированно обеспечить «секретность» алгоритма? Например, в компании, в которой несколько человек работают над кодом и еще куча человек имеет доступ к скомпилированной прошивке. С секретным ключом все просто, он может гарнироваться самостоятельно, внутри устройства или, например, генерироваться по инициативе конечного пользователя.
Касательно «самописных алгоритмов» — помимо проблем, которые я уже описывал, есть еще одна – как гарантированно обеспечить «секретность» алгоритма? Например, в компании, в которой несколько человек работают над кодом и еще куча человек имеет доступ к скомпилированной прошивке. С секретным ключом все просто, он может гарнироваться самостоятельно, внутри устройства или, например, генерироваться по инициативе конечного пользователя.
Да интересная статья. Слышал что у спецслужб есть универсальный взломщик любых защит и паролей. Называется ректально-термальный криптоанализатор.

- Papandopala
- 11 июля 2013, 10:40
- ↓
Комментарии (96)
RSS свернуть / развернуть