Серьезная безопасность: Вы не можете победить в блэкджеке — или можете?

Криптогуру Брюс Шнайер (где крипто- означает криптография, не иначе!) только что опубликовал в своем блоге интригующую заметку под названием О случайности автоматических тасовщиков карт.

Если вы когда-либо были в казино, по крайней мере, в одном из Невады, вы знаете, что за столами для блэкджека нельзя рисковать с клиентами, известными в торговле как счетчик карт.

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

Счетчики карт могут получить преимущество, даже если все, что они делают, это отслеживают соотношение 10-карт (десятка, валет, дама и король) к не-10-кам, оставшимся в башмаке дилера.

Например, если дилер сидит с тузом, но количество карт номиналом 10 выше среднего уже израсходовано, то шансы дилера собрать блэкджек ниже среднего (21 очко с двумя картами, т.е. туз и один из 10-JQK) и выигрыш сразу, а также выше среднего шанс проиграть до достижения точки остановки 17 и выше.

Если вы сможете сбалансировать вероятности в своей голове в режиме реального времени, вы сможете соответствующим образом изменить свои ставки и выйти вперед в долгосрочной перспективе.

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

Выравнивание шансов

Чтобы уменьшить противовес вероятностей, которым пользуются счетчики карт (по крайней мере, те, кого еще не поймали), казино обычно:

• Сдавайте руки из башмака, загруженного шестью колодами (колодами) по 52 карты. Это означает, что каждая сданная рука искажает оставшееся распределение карт меньше, чем если бы использовалась одна колода.
• Перетасовывайте весь башмак из 312 карт (шесть колод) перед каждой раздачей. Чтобы сэкономить время и снять подозрения с дилера, псевдослучайная электромеханическая машина тасует карты прямо на столе, на глазах у всех игроков.

Это сразу же поднимает вопрос, поставленный Шнайером: насколько хорошо тасуются карты, когда они выходят из машины?

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

Могли бы вы «угадать» следующую карту из колоды лучше, чем подсказывает случай?

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

Но электромеханический тасовщик карт буквально должен перемещать карты в реальной жизни.

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

Перетасовывайте в течение слишком короткого времени, и казино может действительно облегчить работу счетчиков карт, если с самого начала существует известная предвзятость в распределении карт.

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

Блог Шнайера публикует ссылки на захватывающая часть Би-би-си, в котором описывается, как математик/маг по имени Перси Диаконис из Стэнфордского университета вместе с Джейсоном Фулманом и Сьюзан Холмс провели формальное расследование этого самого вопроса в начале этого века в статье, озаглавленной просто: АНАЛИЗ МАШИН ДЛЯ ПЕРЕТАСОВКИ ПОЛОК В КАЗИНО.

Уровни сложности

Ясно, что есть некоторые методы тасования, которые совсем не смешивают карты, например, просто резки пакет на две части и перемещая нижнюю часть вверх.

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

Идея состоит в том, что если вы перетасовываете колоду несколько раз, вы выполняете псевдослучайную последовательность разрезов каждый раз, когда делите колоду перед каждым перелистыванием, смешивая ее с псевдослучайной переменной последовательностью псевдослучайных операций перемежения, включающих N-из- левый, затем М-справа процесс.

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

Ловкие фокусники и мошенники (сам Диаконис первый, но не последний) могут совершать то, что известно как фаро перетасовываетили идеальное перемешивание, где они делают обе следующие вещи каждый раз, когда переворачивают колоду:

• Раздели карты ровно пополам, таким образом получая ровно 26 карт в каждой руке.
• Чередуйте их идеально, переворачивая ровно по одной карте за раз поочередно из каждой руки, каждый раз.

Сам Диаконис может идеально тасовать (в том числе редкое умение делать это одной рукой, чтобы держать обе половины колоды!), И, согласно BBC:

[Он] любит демонстрировать идеальное тасование, беря новую колоду карт и записывая слово RANDOM толстым черным маркером на одной стороне. Пока он ловко работает с картами, буквы смешиваются, время от времени появляясь в призрачной форме, как плохо настроенное изображение на старом телевизоре. Затем, после восьмой и последней тасовки, слово снова материализуется на краю колоды. Карты находятся в своей точной исходной последовательности, от Туза Пик до Туза Червей.

Два вида совершенства

На самом деле существует два вида идеального тасования, в зависимости от того, с какой руки вы начинаете перетасовку после того, как разделите карты на две стопки по 26 карт.

Вы можете чередовать карты, чтобы они оказались в последовательности 1-27-2-28-3-29-…-25-51-26-52, если первая карта, которую вы переворачиваете вниз, принадлежит руке, в которой вы держите нижняя половина пачки.

Но если первая карта, которую вы переворачиваете вниз, является нижней картой того, что раньше было верхней половиной колоды, вы получите 27-1-28-2-29-3-…-51-25-52-26, поэтому карта, прошедшая наполовину, впоследствии оказывается сверху.

Первый тип называется перетасовывать, и переупорядочивает колоду каждые восемь раз, когда вы ее повторяете, как вы можете видеть здесь (изображение имеет 52 строки пикселей, каждая строка соответствует краю одной карты со словом RANDOM, написанным на ней маркером):

Последний тип представляет собой в случайном порядке, и это, что удивительно, требует 52 перетасовок, прежде чем оно повторится, хотя здесь вы можете ясно видеть, что колода никогда не показывает истинной случайности и даже проходит через идеальное переворачивание на полпути:

Что сказали математики?

Итак, еще в 2013 году, когда Diaconis el al. изучили машину для перемешивания полки по приглашению производителя, что они нашли?

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

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

После того, как все карты были размещены на полке, так что на каждой полке находится около 1/N карт, карты снова собираются в одну стопку в псевдослучайном порядке.

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

…но в этом случае, когда в машине было 10 полок, исследователей специально спросили, «Будет ли достаточно одного прохода машины для получения адекватной случайности?»

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

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

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

В частности, они показали, что только один проход устройства оставил достаточно много коротких последовательностей карт в перетасованных выходных данных, чтобы они могли надежно предсказать в среднем от 9 до 10 карт, когда впоследствии была роздана колода из 52 перетасованных карт.

Как писали исследователи:

[Используя] нашу теорию, мы смогли показать, что знающий игрок может правильно угадать около 9 с половиной карт за один проход через колоду из 52 карт. Для хорошо перетасованной колоды оптимальная стратегия дает правильное использование примерно 4 с половиной карт. Эти данные убедили компанию. Теория также предложила полезное средство.

[...]

Президент компании ответил: «Нам не нравятся ваши выводы, но мы им верим, и именно для этого мы вас наняли». Мы предложили простую альтернативу: использовать машину дважды. Это приводит к перетасовке, эквивалентной машине с 200 полками. Наш математический анализ и дальнейшие тесты, о которых здесь не сообщается, показывают, что это достаточно случайно.

Что делать?

В этой истории есть несколько «поучительных моментов», и вам было бы разумно извлечь из них уроки, независимо от того, являетесь ли вы программистом или менеджером по продукту, которые сами борются с случайностью, или специалистом по безопасности, DevOps, ИТ или кибербезопасности, который занимается обеспечением кибербезопасности в Генеральная:

• Пройти собственные тесты недостаточно. Неудачные собственные тесты, безусловно, плохо, но легко получить тесты, которые, как вы ожидаете, ваш алгоритм, продукт или услуга должны пройти, особенно если ваши исправления или «исправления ошибок» измеряются тем, помогли ли они вам пройти тесты. Иногда вам нужно второе мнение, полученное из объективного независимого источника. Этот независимый обзор мог бы исходить от первоклассной команды математических статистиков из Калифорнии, как здесь; от внешней «красной команды» пентестеров; или от команды MDR (управляемое обнаружение и реагирование), которые своими глазами и ушами смотрят на вашу ситуацию с кибербезопасностью.
• Слушать плохие новости очень важно. Президент компании по производству тасующих машин в данном случае ответил идеально, когда признал, что недоволен результатом, но что он заплатил за раскрытие правды, а не просто за то, чтобы услышать то, на что он надеялся.
• Криптография в частности и кибербезопасность в целом сложны. Просьба о помощи — это не признание неудачи, а признание того, что нужно для успеха.
• Случайность слишком важна, чтобы оставлять ее на волю случая. Измерить беспорядок непросто (читать газету понять почему), но это можно и нужно сделать.

---

Не хватает времени или опыта, чтобы позаботиться о реагировании на угрозы кибербезопасности? Беспокоитесь, что кибербезопасность в конечном итоге отвлечет вас от всех других вещей, которые вам нужно сделать?

Узнать больше о Управляемое обнаружение и реагирование Sophos:
Круглосуточный поиск угроз, обнаружение и реагирование  ▶

---