Pull to refresh
  • by relevance
  • by date
  • by rating

Генерация случайных чисел на микроконтроллерах

Programming microcontrollers *


Про генераторы случайных чисел написано очень много, но почти всегда, когда дело доходит до реализации, подразумевается (или явно говорится), что речь идет об x86/x64 и других «взрослых» архитектурах. В то же время, форумы, посвященные разработке устройств на микроконтроллерах, пестрят вопросами «как мне сгенерировать случайное число на %controllername%?». Причем диапазон ответов простирается от «смотри гугл/википедию» до «используй стандартную функцию». Далеко не всегда эта «стандартная функция» есть и устраивает разработчика по всем параметрам, чаще наоборот: то числа получаются далеки от случайных, то скорость работы слишком мала, а то полученный код вообще не помещается в свободную память.
Попробуем разобраться, какие бывают алгоритмы генерации случайных чисел, как выбрать подходящий, а главное, в чем особенности реализации этих алгоритмов на контроллерах.
Читать дальше →
Total votes 81: ↑80 and ↓1 +79
Views 32K
Comments 39

Как работает новый генератор случайных чисел Intel

Cryptography *
Translation


Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

К сожалению, ваша первая покупка в интернете была скомпрометирована с самого начала: вскоре обнаружится, что якобы безопасный протокол, по которому браузер установил соединение, на самом деле не очень защищён.
Читать дальше →
Total votes 179: ↑170 and ↓9 +161
Views 53K
Comments 113

Подробно о генераторах случайных и псевдослучайных чисел

Information Security *Algorithms *Mathematics *
Sandbox
На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.
image
Читать дальше →
Total votes 75: ↑71 and ↓4 +67
Views 252K
Comments 21

В поисках криптостойкого ГПСЧ

Information Security *Cryptography *Algorithms *

Привет, %username%!

В сегодняшнем посте речь пойдет о криптостойкости генераторов псевдослучайных чисел (ГПСЧ).
Для начала определимся, что же такое криптостойкий ГПСЧ (КСГПСЧ).
КСГПСЧ должен удовлетворять «тесту на следующий бит». Смысл теста в следующем: не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 битов с вероятностью более 50 %.
Wikipedia

Возможно, кое-кто из читателей использовал такие ГПСЧ, как регистры сдвига с линейной обратной связью (РСЛОС) или любимый многими программистами Вихрь Мерсенна. Я постараюсь показать, что оба этих способа, несмотря на весьма хорошие статистические свойства и большие периоды, не соответствуют приведенному выше определению и их нельзя считать криптографически стойкими, а также предложу, в качестве альтернативы, два очень надежных ГПСЧ.
Читать дальше →
Total votes 40: ↑39 and ↓1 +38
Views 35K
Comments 14

Fortuna: генератор случайных чисел для параноиков

Information Security *Cryptography *Algorithms *

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

Если у вас такого устройства нет, то прошу под кат.
Читать дальше →
Total votes 62: ↑58 and ↓4 +54
Views 45K
Comments 43

Как АНБ внедрило закладку в генератор псевдослучайных чисел

Information Security *Cryptography *

По материалам этой статьи.

Генератор «от АНБ» основан на эллиптических кривых. Не надо их бояться, тем более что суть алгоритма и закладки можно описать более простыми словами. Будет не сложнее, чем понять как работает протокол Диффи — Хеллмана
Показать всё, что скрыто
Total votes 155: ↑116 and ↓39 +77
Views 75K
Comments 50

История однострочных багов

Information Security *Cryptography *Open source *
Компания Apple недавно допустила крупную ошибку, забыв удалить лишнюю строчку с оператором безусловного перехода goto посередине функции SSLVerifySignedServerKeyExchange для проверки серверной подписи при установке SSL-соединения. В результате, функция успешно завершала работу, независимо от результата проверки подписи.

Однако, это не первый случай в истории, когда критическая ошибка объясняется единственной строчкой кода. Вот ещё несколько таких примеров.

X Server


В 2006 году было обнаружено, что X Server проверяет рутовые права у пользователя, но при этом разработчики в реальности забыли вызвать соответствующую функцию.

--- hw/xfree86/common/xf86Init.c
+++ hw/xfree86/common/xf86Init.c
@@ -1677,7 +1677,7 @@
   }
   if (!strcmp(argv[i], "-configure"))
   {
-    if (getuid() != 0 && geteuid == 0) {
+    if (getuid() != 0 && geteuid() == 0) {
        ErrorF("The '-configure' option can only be used by root.\n");
        exit(1);
     }

Читать дальше →
Total votes 142: ↑118 and ↓24 +94
Views 43K
Comments 90

Случайные числа и детерминистичная симуляция

Intel corporate blog Cryptography *Programming *


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

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


Иногда самый надёжный способ получить случайное число — взять его из справочника. Источник изображения: www.flickr.com/photos/nothingpersonal/337684768
Читать дальше →
Total votes 38: ↑36 and ↓2 +34
Views 29K
Comments 22

Неслучайная случайность, или Атака на ГПСЧ в .NET

Контур corporate blog Information Security *Cryptography *.NET *C# *
Random numbers should not be generated with a method chosen at random.
— Donald Knuth

Копаясь как-то в исходниках одного сервиса в поисках уязвимостей, я наткнулся на генерацию одноразового кода для аутентификации через SMS. Обработчик запросов на отправку кода упрощённо выглядел так:


class AuthenticateByPhoneHandler
{
    /* ... */

    static string GenerateCode() => rnd.Next(100000, 1000000).ToString();

    readonly static Random rnd = new Random();
}

Проблема видна невооруженным глазом: для генерации 6-тизначного кода используется класс Random — простой некриптографический генератор псевдослучайных чисел (ГПСЧ). Займёмся им вплотную: научимся предсказывать последовательность случайных чисел и прикинем возможный сценарий атаки на сервис.


Потокобезопасность


Кстати, заметим, что в приведённом фрагменте кода доступ к статическому экземпляру rnd класса Random из нескольких потоков не синхронизирован. Это может привести к неприятному казусу, который можно часто встретить в вопросах и ответах на StackOverflow:


Читать дальше →
Total votes 72: ↑71 and ↓1 +70
Views 16K
Comments 31

Предсказание случайных чисел в умных контрактах Ethereum

Information Security *Website development *Cryptography *
Translation


Ethereum приобрёл огромную популярность как платформа для первичного размещения монет (ICO). Однако она используется не только для токенов ERC20. Рулетки, лотереи и карточные игры — всё это можно реализовать на блокчейне Ethereum. Как любая реализация, блокчейн Ethereum не поддаётся подделке, он децентрализован и прозрачен. Ethereum допускает выполнение тьюринг-полных программ, которые обычно пишут на языке программирования Solidity. По словам основателей платформы, это превращает систему во «всемирный суперкомпьютер». Перечисленные характеристики полезны в приложениях для азартных игр, где особенно важно доверие пользователей.

Блокчейн Ethereum является детерминированным и поэтому представляет определённые сложности при написании генератора псевдослучайных чисел (ГПСЧ) — неотъемлемой части любого приложения для азартных игр. Мы решили исследовать смарт-контракты, чтобы оценить безопасность ГПСЧ на Solidity и подчеркнуть характерные ошибки проектирования, которые ведут к появлению уязвимостей и возможности предсказания будущего состояния ГПСЧ.
Читать дальше →
Total votes 39: ↑36 and ↓3 +33
Views 12K
Comments 17

Канадский эксперт по ГПСЧ критикует власти за использование древних алгоритмов Excel для розыгрыша виз

Cryptography *


Программа воссоединения семей (Family Reunification Program или Family sponsorship) — одна из трёх основных канадских программ помощи мигрантам. Она позволяет как недавно прибывшим иммигрантам, так и давно устоявшимся канадцам воссоединиться с членами своих семей. В соответствии с положениями об иммиграции и защите беженцев (Immigration and Refugee Protection Regulations), проживающие за рубежом семьи получают финансовую помощь, также как проживающие в Канаде родственники мигранта. На финансовую помощь могут рассчитывать супруги, дети, родители, внуки, усыновлённые дети и т. д.

Проблема в том, что Канада не может сразу предоставить гражданство всем родственникам всех мигрантов. Раньше их ставили в очередь, а рассмотрения заявки приходилось ожидать годами. Чтобы ускорить процесс, либералы предложили проводить лотерею. Так что с 2017 года в Канаде разыгрывается лотерея по типу американской Green Card. Среди примерно 100 000 заявок случайным образом выбирают 10 000. Благодаря официальному ответу на запрос по Закону доступа к информации канадскому изданию The Globe an Mail стали известны некоторые технические детали, как проводится лотерея.
Читать дальше →
Total votes 26: ↑23 and ↓3 +20
Views 12K
Comments 25

Увеличиваем случайность того, что и так [наверно] [почти] случайно

Information Security *Cryptography *Python *

случайные числа вкуснее, если их немножко поперчить

Будем сочетать теорию с практикой — покажем, что улучшение энтропии случайных последовательностей возможно, после чего посмотрим исходные коды, которые это делают.

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

В погоне за качественными случайными числами люди изобретают весьма остроумные приспособления (см. например здесь и здесь). В принципе, весьма неплохие источники случайности встроены в API операционных систем, но дело серьёзное, и нас всегда немножко гложет червячок сомнения: а достаточно ли хорош тот ГСЧ, который я использую, и не подпорчен ли он… скажем так, третьими лицами?
Читать дальше →
Total votes 12: ↑11 and ↓1 +10
Views 4.6K
Comments 12

Эффективная генерация числа в заданном интервале

Programming *Perfect code *Algorithms *Mathematics *
Translation
image

В подавляющем большинстве моих постов о генерации случайных чисел рассматривались в основном свойства различных схем генерации. Это может оказаться неожиданным, но производительность алгоритма рандомизации может зависеть не от выбранной схемы генерации, а от других факторов. В этом посте (на который меня вдохновила превосходная статья Дэниела Лемира) мы исследуем основные причины снижения производительности генерации случайных чисел, которые часто перевешивают производительность движка ГПСЧ.

Представьте такую ситуацию:

В качестве домашнего задания Хуан и Саша реализуют одинаковый рандомизированный алгоритм на C++, который будет выполняться на одном университетском компьютере и с одним набором данных. Их код почти идентичен и отличается только в генерации случайных чисел. Хуан торопится на свои занятия по музыке, поэтому просто выбрал вихрь Мерсенна. Саша, с другой стороны, потратил несколько лишних часов на исследования. Саша провёл бенчмарки нескольких самых быстрых ГПСЧ, о которых недавно узнал из соцсетей, и выбрал наиболее быстрый. При встрече Саше не терпелось похвастаться, и он спросил Хуана: «Какой ГПСЧ ты использовал?»

«Лично я просто взял вихрь Мерсенна — он встроен в язык и вроде неплохо работает».

«Ха!», — ответил Саша. «Я использовал jsf32. Он намного быстрее, чем старый и медленный вихрь Мерсенна! Моя программа выполняется за 3 минуты 15 секунд!».

«Хм, неплохо, а моя справляется меньше, чем за минуту», — говорит Хуан и пожимает плечами. «Ну ладно, мне пора на концерт. Пойдёшь со мной?»

«Нет», — отвечает Саша. «Мне… эээ… нужно снова взглянуть на свой код».

Эта неловкая вымышленная ситуация не особо и вымышлена; она основана на реальных результатах. Если ваш рандомизированный алгоритм выполняется не так быстро, как хотелось бы, и узким местом похоже является генерация случайных чисел, то, как это ни странно, проблема может быть и не в генераторе случайных чисел!
Читать дальше →
Total votes 31: ↑31 and ↓0 +31
Views 22K
Comments 10

Исследование и преобразование сортировкой псевдослучайных последовательностей

Entertaining tasks Algorithms *C# *Big Data *Studying in IT
Recovery mode
Sandbox
Исследование и преобразование сортировкой псевдослучайных последовательностей

Созданы алгоритмы на языках C# и qbasic и таблица Excel совместимая, доказывающие возможность исследовать псевдослучайные последовательности на случайность и способные определять последовательности неслучайные или маломощные.

Графическая оболочка: таблица Excel совместимая для исследования свыше 50тыс. элементов 2-х видов:
1. Исследование последовательности чисел;
2. Исследование последовательности цифр 0 и 1.


Total votes 34: ↑8 and ↓26 -18
Views 3.2K
Comments 88

Фальсификация случайности и и преобразование сортировкой псевдослучайных последовательностей

Entertaining tasks Algorithms *C# *Big Data *Studying in IT
Recovery mode

Фальсификация случайности и и преобразование сортировкой псевдослучайных последовательностей


Цель: доказать возможность фальсификации случайности и реальность преодоления фальсификации случайности.

Случайность натуральная, разделённая на интегральные логарифмические спектры, предсказуемо показывает короткие дистанции повторов и дистанции повторов длинные массово отсутствуют, зато сортировка последовательности приводит спектры разделения в вид теоретический.

Пробел Просвещения России и СССР и СНГ: интеграл и логарифм в младших классах не изучают и впоследствии считают простейшее якобы сложным.
Total votes 35: ↑8 and ↓27 -19
Views 4.1K
Comments 150

Принцип работы РСЛОС

Cryptography *Electronics for beginners
Sandbox

Регистр сдвига с линейной обратной связью (РСЛОС, англ. Linear Feedback Shift Register, LFSR) — сдвиговый регистр битовых слов, у которого значение входного бита однозначно задается некоторой функцией, исходя из значений остальных битов регистра до сдвига. Регистр сдвига может представлять собой некоторую электрическую схему, составленную из дискретных компонентов: транзисторов, резисторов, также может быть интегрирован в микросхему или же реализован в программе. Добавление обратной связи превращает регистр сдвига в генератор псевдослучайных чисел, который находит широкое применение в криптографии. В статье мы разберем принцип работы РСЛОС от hardware до различных его применений.

Регистр, в общем случае – это схема, состоящая из связанных между собой однобитовых элементов памяти. Такие схемы умеют записывать, хранить, считывать n-разрядные двоичные данные. В статье рассматривается вид регистра, называемый регистром сдвига. Чаще всего регистр сдвига собирается на основе последовательно соединенных D-триггеров, притом количество этих триггеров равно числу разрядов n. С принципов работы D-триггера мы и начинаем статью.

Читать далее
Total votes 28: ↑26 and ↓2 +24
Views 6.1K
Comments 2

Одномерный генератор случайных действительных чисел

Algorithms *
Tutorial

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

Класс генераторов "True Random" использует физические явления и внешние связи, так например для генерации десятичного случайного числа вы можете найти рекомендацию использования "атмосферного датчика". Естественно как любителю программирования такое положение дел мне показалось несправедливым, и довольно долгое время "задача созревала". Вариант решения, как и следовало ожидать из постановки задачи, появился случайно, как дополнение к задаче компрессии для упаковки твердых сфер. Задача не нашла аналитического решения как и нет пока доказательств его отсутствия, соответственно источник по внешним признакам вполне подходящий. Однако без дополнительного источника случайности, более чем бесконечной сложности в обратном вычислении состояния генератора я не получил.

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

Читать далее
Total votes 12: ↑4 and ↓8 -4
Views 2.7K
Comments 27

Взлом ГПСЧ с помощью машинного обучения

Дата-центр «Миран» corporate blog Information Security *Cryptography *Algorithms *Machine learning *

Выдача XORShift кажется случайной

Исследователь Мостафа Хассан (Mostafa Hassan) сумел взломать два генератора псведослучайных чисел (ГПСЧ) с помощью машинного обучения. Обученная двуслойная нейросеть предсказала выдачу генератора xorshift128 с точностью 100%.

Во второй части своей работы Мостафа описал ещё одну нейросеть, которая взломала популярный генератор Mersenne Twister (вихрь Мерсенна, MT, MT19937) тоже с точностью 100%.
Читать дальше →
Total votes 32: ↑32 and ↓0 +32
Views 11K
Comments 13