Серйозна безпека: ви не можете перемогти вдома в блекджек – чи можете?

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

Якщо ви коли-небудь були в казино, принаймні в одному з Невади, ви знаєте, що за столами для блекджеку не ризикують клієнти, відомі в торгівлі як карткові лічильники.

Цей термін використовується для позначення гравців, які навчили свою пам’ять настільки, що вони можуть уважно стежити за зіграними на даний момент картами в роздачі, що дає їм теоретичну перевагу перед домом, коли прогнозують, чи стояти, чи бити як грати. прогресує.

Лічильники карт можуть отримати перевагу, навіть якщо все, що вони роблять, це стежити за співвідношенням 10 карт (десятка, валет, дама і король) і не 10, що залишилися в дилері.

Наприклад, якщо у дилера є туз, але вже використано більше середньої кількості карт номіналом 10, тоді дилер має нижчий за середній шанс зробити блекджек (21 очко з двома картами, тобто Туз і один із 10-JQK) і відразу виграти, а шанси програти вище середнього, перш ніж досягти кінцевої точки 17 і вище.

Якщо ви можете збалансувати ймовірності у своїй голові в реальному часі, тоді ви зможете відповідним чином змінити свої ставки та вийти вперед у довгостроковій перспективі.

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

Вирівнювання шансів

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

• Роздайте руки з шістьма колодами по 52 карти. Це означає, що кожна роздана рука спотворює розподіл карт, що залишився, менше, ніж якби використовувалася одна колода.
• Перед кожною роздачею перетасуйте всю колодку з 312 карт (шість пачок). Щоб заощадити час і зняти підозру з дилера, псевдовипадковий електромеханічний автомат тасує карти прямо на столі, на очах у всіх гравців.

Це негайно викликає запитання, поставлене Шнайєром: наскільки добре перетасовані карти, коли вони виходять із машини?

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

Чи могли б ви «вгадати» наступну картку краще, ніж підказує випадок?

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

Але електромеханічний пристрій для тасування карт буквально повинен рухати карти в реальному житті.

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

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

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

У блозі Шнайєра є посилання на a захоплюючий твір BBC описує, як математик/маг Персі Діаконіс зі Стенфордського університету разом із Джейсоном Фулманом і Сьюзен Холмс провели формальне розслідування саме цього питання на початку цього століття, у статті під простою назвою: АНАЛІЗ МАШИН ДЛЯ ТАСУВАННЯ ПОЛИЦЬ КАЗИНО.

Рівні складності

Зрозуміло, що існують деякі методи тасування, які зовсім не змішують карти, наприклад просто різання розділіть пакет на дві частини та перемістіть нижню частину до верхньої.

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

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

Цікаво, однак, що коли задіяні досвідчені люди-тасовники, жодне з цих припущень про непередбачуваність не є безпечним.

Спритні маги та підступні торговці (сам Діаконіс є першим, але не другим) можуть виконувати те, що відомо як фаро перемішуєабо ідеальні перемішування, де вони виконують обидві наведені нижче дії кожного разу, коли розбирають зграю:

• Розділіть карти точно на дві частини, отримуючи рівно 26 карток у кожній руці.
• Переплітайте їх ідеально, перевертаючи рівно по одній карті за раз по черзі з кожної руки, кожен раз.

Сам Діаконіс може робити ідеальні перетасування (включно з рідкісним умінням робити це лише однією рукою, щоб тримати обидві половинки зграї!), і, за словами BBC:

[Він] любить демонструвати ідеальне тасування, беручи нову колоду карт і пишучи слово ВИПАДКОВИЙ товстим чорним маркером з одного боку. Коли він виконує свою спритність з картками, літери змішуються, час від часу з’являючись у примарній формі, як неідеально налаштоване зображення на старому телевізорі. Потім, після того, як він зробить восьме й останнє перемішування, слово знову матеріалізується збоку колоди. Карти розташовані в оригінальній послідовності від туза пік до туза черв.

Два види досконалості

Насправді існує два види ідеального тасування, залежно від того, з якої руки ви починаєте грати після розрізання карт на дві стопки по 26 карт.

Ви можете чергувати карти так, щоб вони опинилися в послідовності 1-27-2-28-3-29-…-25-51-26-52, якщо перша карта, яку ви перегортаєте, походить від руки, яку ви тримаєте. нижня половина пачки.

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

Перший тип називається an поза-тасувати, і змінює порядок набору кожні вісім разів, коли ви його повторюєте, як ви можете бачити тут (зображення містить 52 рядки пікселів, кожен рядок відповідає краю однієї картки зі словом ВИПАДКОВИЙ, написаним на ньому маркером):

Останній тип є an в-тасування, і це, на диво, потребує 52 повторних перемішувань, перш ніж повторюється, хоча тут ви можете чітко побачити, що зграя насправді ніколи не демонструє жодної справжньої випадковості, і навіть проходить ідеальне розворот на півдорозі:

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

Так, ще в 2013 році, коли Diaconis el al. вивчили машину для перемішування полиць на запрошення виробника, що вони знайшли?

У документі пояснюється, що тасування на полицях — це електромеханічна спроба розробити автоматизоване рандомізоване «тасування з кількома розрізами й декількома рифлями», в ідеалі, щоб карти потрібно було пропрацювати лише один раз, щоб перетасування було коротшим.

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

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

Інтуїтивно зрозуміло, враховуючи пов’язану псевдовипадковість, можна очікувати, що додаткові повторні перетасування покращать загальну випадковість, до певної точки…

…але в цьому випадку, коли машина мала 10 полиць, дослідників конкретно запитали, «Чи буде достатньо одного проходу машини, щоб створити адекватну випадковість?»

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

Але компанія хотіла переконатися в цьому не пройшла власні випробування просто тому, що випробування підходили машині, що дало б їм помилкове відчуття безпеки.

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

Зокрема, вони показали, що лише один прохід пристрою залишає достатньо коротких послідовностей карт у перемішаному виході, щоб вони могли достовірно передбачити в середньому від 9 до 10 карт, коли потім роздають колоду з 52 перемішаних карт.

Як писали дослідники:

Використовуючи нашу теорію, ми змогли показати, що досвідчений гравець може правильно вгадати приблизно 9 з половиною карт за один раз по колоді з 52 карт. Для добре перемішаної колоди оптимальна стратегія передбачає приблизно 4 з половиною правильні карти. Ці дані переконали компанію. Теорія також запропонувала корисний засіб.

[...]

Президент компанії відповів: «Ми не задоволені вашими висновками, але ми їм віримо, і саме для цього ми найняли вас». Ми запропонували просту альтернативу: використовувати машину двічі. Це призводить до перемішування, еквівалентного машині з 200 полицями. Наш математичний аналіз і подальші тести, про які тут не повідомляється, показують, що це достатньо випадковий характер.

Що ж робити?

Ця історія містить кілька «навчальних моментів», і вам було б доцільно повчитися на них, незалежно від того, чи ви програміст чи менеджер із продуктів, що боретеся саме з випадковістю, чи спеціаліст із SecOps/DevOps/IT/кібербезпеки, який займається забезпеченням кібербезпеки в загальні:

• Пройти власні тести недостатньо. Провалити власні тести – це, безперечно, погано, але легко отримати тести, які, як ви очікуєте, пройде ваш алгоритм, продукт чи послуга, особливо якщо ваші виправлення чи «виправлення помилок» вимірюються тим, чи вони допоможуть вам пройти тести. Іноді вам потрібна друга думка, яка надходить з об’єктивного незалежного джерела. Такий незалежний огляд може бути зроблено командою фахових математиків-статистиків з Каліфорнії, як тут; від зовнішньої «червоної команди» тестувальників проникнення; або від команди MDR (кероване виявлення та реагування), які своїми очима та вухами вивчають вашу ситуацію з кібербезпекою.
• Слухати погані новини важливо. У цьому випадку президент компанії, що займається перемішуванням, відповів ідеально, коли визнав, що був незадоволений результатом, але заплатив, щоб відкрити правду, а не просто почути те, на що сподівався.
• Криптографія зокрема та кібербезпека загалом — це важко. Прохання про допомогу — це не визнання невдачі, а визнання того, що потрібно для досягнення успіху.
• Випадковість надто важлива, щоб залишити її на волю випадку. Виміряти розлад нелегко (читати газету зрозуміти чому), але це можна і потрібно робити.

---

Не вистачає часу чи досвіду для реагування на загрози кібербезпеці? Хвилюєтеся, що кібербезпека зрештою відволікатиме вас від усіх інших справ, які вам потрібно зробити?

Дізнатися більше про Кероване виявлення та реагування Sophos:
Цілодобове полювання на загрози, виявлення та реагування  ▶

---