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

Новый алгоритм ГСЧ на замену /dev/random

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

Немецкие исследователи Бернард Фечнер (университет Хагена) и Андре Остерлох (BTC AG) заявили о прорыве в методах генерации случайных чисел. Они разработали алгоритм, который обеспечивает дискретное равномерное распределение до 20 раз лучше существующих методов. К работе прилагаются результаты тестов по сравнению качества случайных чисел, генерируемых разными методами.
Читать дальше →
Total votes 57: ↑52 and ↓5 +47
Views 3.9K
Comments 64

Правда о ГСЧ покер румов

Покерофф corporate blog

Введение


В этой статье вы узнаете об одной из важнейших составляющих онлайн покера — генераторе случайных чисел (ГСЧ). «Честность» ГСЧ различных покер-румов регулярно подвергается сомнению и обязательно обсуждается на любом ресурсе посвященном покеру. Пользователи постоянно жалуются на «подкрученный» генератор, который позволяет комнате сдерживать более сильных игроков для того чтобы большинство представляющее категорию «более слабых игроков» осталось лояльным комнате. Давайте разберемся действительно ли все так плохо со случайностью на покерных сайтах.
Читать дальше →
Total votes 76: ↑40 and ↓36 +4
Views 67K
Comments 35

Генератор паролей, который всегда под рукой

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

Итак, знакомьтесь: RANDOMOUSE — генератор случайных символов, встроенный в обычную компьютерную мышку.


Читать дальше →
Total votes 105: ↑87 and ↓18 +69
Views 5.2K
Comments 52

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

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

Быстрый генератор случайных чисел из вакуумного «шума»

Cryptography *
Канадский физик Бен Сассмэн (Ben Sussman) с коллегами сконструировали исключительно быстрый и конструктивно простой генератор случайных чисел на базе вакуумных флуктуаций поля.

Вселенная устроена таким образом, что в каждой точке пространства постоянно возникают виртуальные частицы со значительной энергией. В квантовом масштабе вакуум представляет собой бешено активный, «живой» субстрат, где частицы рождаются и аннигилируют, в сумме давая ноль. Хотя эти частицы являются абстрактными объектами квантовой теории поля, но они проявляют себя в конкретных физических процессах, например, эффекте Казимира — взаимном притяжении проводящих незаряженных тел. И вот найдено ещё одно полезное применение вакуумного «шума» — генерация случайных чисел.
Читать дальше →
Total votes 57: ↑46 and ↓11 +35
Views 6.4K
Comments 40

Генератор энтропии Seeder 1.1 существенно уменьшает лаги на Android-устройствах

Interfaces *
В старых версиях Android некоторые системные компоненты и JVM активно считывали большие объёмы случайных чисел из псевдоустройства /dev/random. Это устройство предоставляет интерфейс к системному генератору случайных чисел (ГСЧ), который выводит шумы из драйверов устройств и других источников в «хаотичный» пул. На старых версиях Android иногда возникали проблемы с наполнением пула случайных чисел. В случае опустошения пула возникали лаги UI, пока пул не наполнялся. В новых версиях Android проблему с лагами UI решили, но не до конца: всё-таки иногда возникают характерные задержки.

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

Один из разработчиков с форума XDA-Developers перекомпилировал rngd, так что пул случайных чисел каждую 1 секунду пополняется из пула псевдослучайных чисел /dev/urandom. Результат — потрясающее ускорение интерфейса Android с почти полным исчезновением лагов! Chrome, карты и другие тяжеловесные приложения теперь мгновенно переключаются между задачами.
Читать дальше →
Total votes 116: ↑95 and ↓21 +74
Views 137K
Comments 216

«Человеческая» энтропия для генератора случайных чисел

Cryptography *.NET *Algorithms *
Sandbox
Лишь вследствие нашей слабости, вследствие нашего невежества случайность для нас существует

А. Пуанкаре

Чем больше люди постигали тайны Вселенной, тем ближе они приближались к той точке незнания, в которой их предки все приписывали богам. Теперь это называется – случайность. И хотя Эйнштейн не верил в случайность – он говорил «Бог не играет в кости», – он в числе первых из списка: Эйнштейн, Шредингер, Лаплас…

В наш век цифровых технологий и огромной роли информации в развитии человечества защита информации – актуальнейшая задача. Технологическое решение этой задачи предполагает привлечение «случайности», а именно – генерацию случайных чисел. При этом от качества используемых генераторов напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».
Читать дальше →
Total votes 19: ↑10 and ↓9 +1
Views 16K
Comments 28

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

Intel corporate blog Cryptography *Programming *


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

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


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

Правильные ответы по криптографии: 2018 год

GlobalSign corporate blog Information Security *Website development *Cryptography *
Перевод статьи, автор – Latacora

В литературе и самых сложных современных системах есть «лучшие» ответы на многие вопросы. Если вы разрабатываете встроенные приложения, то предлагают использовать STROBE и модный современный криптографический стек для аутентификации полностью из одиночных SHA-3-подобных функций губки. Советуют использовать NOISE для разработки безопасного транспортного протокола с формированием общего ключа аутентификации (AKE). Говоря об AKE, есть около 30 различных парольных AKE на выбор.

Но если вы разработчик, а не криптограф, то не должны делать ничего такого. Следует придерживаться простых и обычных решений, которые легко поддаются анализу — «скучных», как говорят люди из Google TLS.
Читать дальше →
Total votes 24: ↑24 and ↓0 +24
Views 18K
Comments 7

Random.org — история длиной в 20 лет

RUVDS.com corporate blog History of IT
Уже совсем скоро в рамках проекта «Сервер в облаках» у нас полетит воздушный шар, чьи координаты места приземления — настоящий генератор истинно случайных чисел, у которого источником энтропии является движение воздушных масс. На момент написания этого поста более 100 хабражителей принимают участие в этой интеллектуальной гонке – угадать/рассчитать место приземления сервера и выиграть сертификат на участие в регате. Присоединяйся!



А пока идет гонка и подготовка к полету, мы вспомнили, что у Random.org, одного из самых популярных онлайн-генераторов, предоставляющего истинно случайные числа, источником энтропии тоже является атмосфера, точнее, атмосферные шумы. К тому же сайт скоро будет справлять 20-летие. И история развития Random.org оказалась настолько феерична, и в духе нашего проекта, что в честь «энтропийного совпадения» и скорого юбилея мы решили перевести её для вас.
Читать дальше →
Total votes 29: ↑27 and ↓2 +25
Views 9.5K
Comments 3

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

Information Security *Cryptography *Python *

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

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

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

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

Уязвимость генератора псевдослучайных чисел в Bitcoin

Cryptocurrencies
Sandbox
Приватные Биткоин-ключи — это целочисленное значение от 1 до 115792089237316195423570985008687907852837564279074904382605163141518161494337 или в HEX 1 до 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. В главной сети Биткоина существуют адреса начинающиеся на 1: compressed, uncompressed; адреса на 3: SigScript и обратно совместимые с SegWit, а так же нативные SegWit адреса начинающиеся на bc1. К тому же есть уже порядка семидесяти форков, имеющие другие префиксы, но те же корни что и основного Биткоина.

Биткоин-адреса рассчитываются криптографической функцией подписи ECDSA ( ) основанной на эллиптической кривой.
Total votes 31: ↑29 and ↓2 +27
Views 34K
Comments 12

CPU-функции RDRAND и RDSEED стали доступнее

Cryptography *Assembler *Delphi *
Всем привет!

Сам я криптографией не занимаюсь, но кому то вполне может пригодится мое небольшое исследование. Решил разобраться со встроенными в процессор функциями RDRAND и RDSEED. Компилятор Delphi сказал Undeclared identifier. Хмм. Уже давно существует BMI, BMI2, AVX, AVX2 и даже AVX-512, а дельфийцы остановились на SSE4.2. Не беда. Скомпилируем код сами.

Сначала сделал проверку на поддержку данных функций процессором. Конечно же CPUID. Использовать CPUID можно начиная с первых Pentium процессоров. Надеюсь никто не додумается запустить CPUID на 486 машине, ибо ее там еще не было. Кстати RDRAND и RDSEED до процессоров IvyBridge также не существует.

function CPU_support_RDRAND: Boolean;
asm
  mov rax, $01
  cpuid
  test ecx, 40000000h //тестируем 30-й бит
  setne al
end;

function CPU_support_RDSEED: Boolean;
asm
  mov rcx, 0
  mov rax, $07 //страница №7
  cpuid
  test ebx, 40000h //тестируем 18-й бит
  setne al
end;

Оказалось, что мой Core i7 G6950X Extreme поддерживает данные функции. Поэтому дальше решил скомпилировать байт-код вручную. Для опытных приведу код REX и REX.W префиксов. Возможно вы захотите записать результат в другой регистр:

const
  REX_RDRAND32: Byte = $F0; //(11b:REG, 110b:OPCODE, 000b:EAX) 
  REX_RDSEED32: Byte = $F8; //(11b:REG, 111b:OPCODE, 000b:EAX)
  REX_W_RDRAND64: Byte = $48; //(11b:REG, 110b:OPCODE, 000b:RAX)
  REX_W_RDSEED64: Byte = $48; //(11b:REG, 111b:OPCODE, 000b:RAX)
Читать дальше →
Total votes 21: ↑19 and ↓2 +17
Views 5.4K
Comments 15

Идёт массовый отзыв TLS-сертификатов от множества УЦ, по ошибке сгенерированных на 63-битном ГСЧ вместо 64-битного

GlobalSign corporate blog Information Security *Cryptography *Browsers
Три дня назад в списке рассылки mozilla.dev.security.policy опубликовано сообщение о массовом нарушении в генерации TLS-сертификатов. Как показало расследование, пострадало несколько удостоверяющих центров, в том числе GoDaddy, Apple и Google. Общее количество неправильных сертификатов превышает 1 миллион, а может быть намного больше. GoDaddy первоначально назвала цифру в 1,8 млн сертификатов, а потом уменьшила оценку на два порядка, до 12 000. Представитель Apple назвал цифру 558 000 сертификатов.

Суть в том, что все пострадавцие УЦ использовали open source PKI-решение EJBCA с неправильными настройками, в результате чего для последовательных номеров сертификатов использовались случайные числа из 63-битного пространства, что нарушает требования CA/B Forum по минимальной энтропии (64 бита).

Разница между 263 и 264 превышает 9 квинтиллионов, то есть 9×1018, это очень существенное число (хотя разница всего в два раза). Все сертификаты должны быть отозваны. У SSL.com и GoDaddy процедура займёт 30 дней, у других могут быть примерно такие же сроки, хотя по стандарту RFC5280 они обязаны отозвать некорректные сертификаты в пятидневный срок. Но они очевидно не успевают уложиться в норматив.
Читать дальше →
Total votes 26: ↑24 and ↓2 +22
Views 15K
Comments 14

Как выбрать случайное число от 1 до 10

Algorithms *Mathematics *R *
Translation
Представьте, что вам нужно сгенерировать равномерно распределённое случайное число от 1 до 10. То есть целое число от 1 до 10 включительно, с равной вероятностью (10%) появления каждого. Но, скажем, без доступа к монетам, компьютерам, радиоактивному материалу или другим подобным источникам (псевдо) случайных чисел. У вас есть только комната с людьми.

Предположим, что в этой комнате чуть более 8500 студентов.

Самое простое — попросить кого-нибудь: «Эй, выбери случайное число от одного до десяти!». Человек отвечает: «Семь!». Отлично! Теперь у вас есть число. Однако вы начинаете задаваться вопросом, является ли оно равномерно распределённым?
Читать дальше →
Total votes 43: ↑41 and ↓2 +39
Views 28K
Comments 77

BlessRNG или проверяем ГСЧ на честность

Playgendary corporate blog Game development *Unity3D *Reading room


В геймдеве часто нужно что-нибудь завязать на рандоме: у Unity для этого есть свой Random, а параллельно с ним существует System.Random. Когда-то давно на одном из проектов сложилось впечатление, что оба могут работать по-разному (хотя должны иметь равномерное распределение).

Тогда в детали углубляться не стали — хватило того, что переход на System.Random исправил все проблемы. Сейчас решили разобраться подробнее и провести небольшое исследование: насколько «предвзяты» или предсказуемы ГСЧ, и какой выбрать. Тем более, я не раз слышал противоречивые мнения об их «честности» — попробуем разобраться, как реальные результаты соотносятся с заявленными.
Читать дальше →
Total votes 21: ↑19 and ↓2 +17
Views 9K
Comments 20

Генерация случайных чисел с помощью ДНК

ua-hosting.company corporate blog Information Security *Cryptography *Popular science Biotechnologies


Случайности. Для кого-то все, что происходит вокруг, это одна сплошная случайность. А кто-то утверждает, что случайностей не бывает. Философствовать и спорить на эту тему можно много часов, а выводов все равно будет множество. Перейдя от метафизических размышлений к более реальным, можно увидеть, что случайные числа нашли свое применение во многих аспектах нашей жизни: от игровых автоматов до систем кодирования информации. Процесс, во время которого создается последовательность случайных чисел/символов, которую нельзя предугадать, именуется генерацией случайных чисел (ГСЧ). За долгую историю человечества было создано немало методов ГСЧ. Одни достаточно просты и понятны: игральные кости, монеты (орел/решка), колода карт и т.д.

Другие же применяют куда более сложные физические процессы: к примеру, за счет высокочастотных движений электронов электрическое сопротивление провода не является постоянным, т.е. варьируется случайным образом. Измерив этот фоновый шум, можно получить последовательность случайных чисел. Но методики ГСЧ не ограничиваются исключительно физикой. Группа ученых из Швейцарской высшей технической школы Цюриха (или сокращенно ETHZ) создали новый метод генерации случайных чисел, основанный на синтезе ДНК. Как именно это было достигнуто, насколько случайны полученные число, и можно ли их предугадать? Ответы на эти вопросы ждут нас в докладе ученых. Поехали.
Читать дальше →
Total votes 19: ↑19 and ↓0 +19
Views 2.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 10K
Comments 13