Komoly biztonság: A Blackjacknél nem tudod legyőzni a házat – vagy igen?

Cryptoguru Bruce Schneier (hol crypto eszközök kriptográfia, nem a másik dolog!) most egy érdekfeszítő megjegyzést tett közzé blogján címmel Az automatikus kártyakeverők véletlenszerűségéről.

Ha járt már kaszinóban, legalább egy nevadai kaszinóban, tudni fogja, hogy a blackjack asztalok nem kockáztatnak olyan ügyfelekkel, akik a kereskedelemben kártyaszámlálók.

Ezt a kifejezést azokra a játékosokra használják, akik annyira edzettek emlékeiket, hogy közelről nyomon tudják követni a leosztásban eddig kijátszott kártyákat, ami elméleti előnyt jelent számukra a házzal szemben, amikor megjósolják, hogy álljanak vagy ütjenek játékként. halad előre.

A kártyaszámlálók még akkor is előnyre tehetnek szert, ha csak nyomon követik a 10 lapok (tíz, bubi, dáma és király) és a nem 10 lapok arányát az osztó cipőjében.

Például, ha az osztó egy ászral ül, de az átlag feletti számú 10 értékű kártyát már elhasználták, akkor az osztónak átlag alatti esélye van blackjack-re (két lappal 21 pont, pl. Ász és egy 10-JQK) és nyersz egyszerre, és átlagon felüli esély van a csődre, mielőtt elérné a 17-es vagy afeletti megállópontot.

Ha valós időben ki tudja egyensúlyozni a valószínűségeket, akkor ennek megfelelően módosíthatja tétjeit, és hosszú távon előrébb kerülhet.

Valójában ne próbálja ki ezt, legalábbis Nevadában: a kaszinó valószínűleg elég gyorsan elkapja Önt, mert ha nem számolja a kártyákat, a játékmintája jelentősen el fog térni a rendelkezésre álló legtájékozottabb nyerési lehetőségektől. Lehet, hogy nem kerül a bíróság elé, de szinte biztos, hogy kikísérik a helyszínről, és soha többé nem engedik vissza.

Az esélyek kiegyenlítése

A kártyaszámlálók (legalábbis azok, akiket még nem kaptak el) a valószínűségek ellensúlyozása érdekében a kaszinók jellemzően:

• Osszon le kezeket egy hat 52 kártyás csomaggal (paklival) megrakott cipőből. Ez azt jelenti, hogy minden kiosztott leosztás kevésbé torzítja el a fennmaradó kártyaelosztást, mintha egyetlen csomagot használnának.
• Keverje meg a 312 lapból álló teljes cipőt (hat csomag) minden leosztás előtt. Az időmegtakarítás és az osztó gyanújának eltüntetése érdekében egy pszeudovéletlen elektromechanikus gép közvetlenül az asztalon keveri meg a kártyákat, az összes játékos előtt.

Ez azonnal felveti a Schneier által feltett kérdést: mennyire keverik össze a kártyákat, amikor kikerülnek a gépből?

Figyelemre méltó, hogy hat új kártyacsomaggal, amelyek kiszámítható sorrendben érkeznek (pl. ász a szívkirályhoz, ász a klubkirályhoz, király a gyémánt ászhoz, király a pikk ász), mennyi részleges rendezés van hátra a a gép elvégezte a dolgát?

Jobban „kitalálnád” a következő lapot a cipőből, mint azt a véletlen sugallja?

A teljesen elektronikus randomizáló összetettségét elsősorban az általa használt CPU sebessége korlátozza, amelyet általában másodpercenként százmillió vagy milliárd aritmetikai műveletben mérnek.

De egy elektromechanikus kártyakeverőnek szó szerint mozgatnia kell a kártyákat a való életben.

Nyilván van határa annak, hogy milyen gyorsan tud csomagfelosztást, kártyacserét és interleaving műveleteket végrehajtani, mielőtt a mechanizmus sebessége elkezdené károsítani a kártyákat, ami azt jelenti, hogy van határ a véletlenszerűségnek (vagy pontosabban: álvéletlenség) a gép be tudja vezetni, mielőtt elérkezne a következő leosztás ideje.

Túl rövid ideig keverjük össze, és a kaszinó valóban megkönnyítheti a kártyaszámlálók dolgát, ha a kártyák elosztásában már a kezdetektől fogva ismert torzítás tapasztalható.

Túl sokáig keverje össze, és a játék túl lassú lesz, így a játékosok unatkozni fognak és elkóborolnak, amit a kaszinók kétségbeesetten próbálnak elkerülni.

Schneier blogbejegyzései a lenyűgöző darab A BBC leírja, hogy a Stanford Egyetem Persi Diaconis nevű matematikusa/mágusa Jason Fulmannel és Susan Holmesszal együtt formális vizsgálatot folytatott ebben a kérdésben a század elején, egy cikkben, melynek címe egyszerűen: A KASZINÓI POLCKEVERŐ GÉPEK ELEMZÉSE.

A komplexitás szintjei

Nyilvánvaló, hogy vannak olyan keverési technikák, amelyek egyáltalán nem keverik össze a kártyákat, például egyszerűen vágás a csomagot két részre osztjuk, és az alsó részt felfelé mozgatjuk.

Más technikák jobb keverést eredményeznek (vagy úgy érzik, hogy ennek kellene eredményezniük), például a riffle shuffle, ahol nagyjából kettéosztod a csomagot, mindkét kezedben tartod az egyik felét, és a két felét "összefordítod", álvéletlen módon egymásba rakva, felváltva úgy, hogy az egyik oldalról veszel néhány lapot, majd a másikról néhány lapot. .

Az ötlet az, hogy ha többször megkevered a csomagot, akkor pszeudovéletlen vágási sorozatot hajtasz végre minden alkalommal, amikor felosztod a csomagot minden riffle előtt, és összekevered a pszeudovéletlenszerű interleaving műveletek álvéletlenszerűen változó sorozatával, amely magában foglal egy N-ből származó balra-majd-M-jobbról-folyamat.

Érdekes módon azonban, ha képzett emberi keverőkről van szó, a kiszámíthatatlanság feltételezései egyike sem biztonságos.

Az ügyes bűvészek és az elferdült kereskedők (maga Diaconis az előbbi, de nem az utóbbi) végrehajthatják az ún. faro csoszogvagy tökéletes keverés, ahol a következő mindkét dolgot megteszik minden alkalommal, amikor feldobják a csomagot:

• Osszuk ketté pontosan a kártyákat, így minden kézben pontosan 26 kártya kerül.
• Tökéletesen beilleszti őket, pontosan egy kártyát forgatva le felváltva minden leosztásból, minden egyes alkalommal.

Diaconis maga is tökéletes keverést tud végezni (beleértve azt a ritka mesterséget is, hogy egy kézzel meg tudja tartani a csomag mindkét felét!), és a BBC szerint:

[Ő] szereti bemutatni a tökéletes keverést úgy, hogy vesz egy új kártyapaklit, és az egyik oldalára vastag fekete jelölővel írja a VÉLETLEN szót. Ahogy a kártyákkal végrehajtja a kézügyeskedést, a betűk összekeverednek, és olykor-olykor kísérteties formában jelennek meg, mint egy tökéletlenül behangolt kép egy régi tévékészüléken. Aztán, miután elvégzi a nyolcadik és egyben utolsó keverést, a szó újra materializálódik a pakli oldalán. A lapok az eredeti sorrendben vannak, a pikk ásztól a szív ászáig.

A tökéletesség két típusa

Valójában kétféle tökéletes keverés létezik, attól függően, hogy melyik kézből kezdesz riffelni, miután a kártyákat két 26 lapos pakliba vágod.

A kártyákat beillesztheti, hogy az 1-27-2-28-3-29-…-25-51-26-52 sorrendbe kerüljenek, ha az első lefelé fordított kártya abból a leosztásból származik, amelyben éppen tart. ő a csomag alsó felét.

De ha az első kártya, amit lefordítasz, az alsó lapja annak, ami korábban a csomag felső fele volt, akkor 27-1-28-2-29-3-…-51-25-52-26 lesz a végeredmény, tehát a a félúton túli kártya utána a tetejére kerül.

Az előbbi típust an out-shuffle, és nyolcszor ismételgeti újra a csomagot, ahogy itt is látható (a képen 52 pixelsor van, minden sor egy kártya szélének felel meg, amelyre jelölőtollal a VÉLETLENSZERŰ szó van ráírva):

Ez utóbbi típus egy keverés közben, és ez elképesztő módon 52 újrakeverésig tart, mielőtt megismétlődik, bár itt jól látható, hogy a csomag soha nem mutat igazi véletlenszerűséget, sőt a felénél tökéletes megfordításon megy keresztül:

Mit mondtak a matematikusok?

Tehát még 2013-ban, amikor Diaconis el al. tanulmányozta a polcos keverőgépet a gyártó meghívására, mit találtak?

Ahogy a cikk kifejti, a polckeverő egy elektromechanikus kísérlet egy automatizált, véletlenszerű „többvágott több riffle keverés” kidolgozására, ideális esetben úgy, hogy a kártyákat csak egyszer kell végigdolgozni, hogy a keverési idő rövid legyen.

A polckeverőben lévő kártyák gyorsan, pszeudovéletlenszerűen, egyenként „kiosztásra” kerülnek az eszköz belsejében lévő N fémpolc egyikére (innen ered a név), és minden alkalommal, amikor egy kártyát a polcra helyeznek, vagy becsúsztatják alulra, vagy az előző kártyák tetejére ejtve. (Feltételezzük, hogy ha a kártyát két, már a pakliban lévő véletlenszerű kártya közé próbáljuk beledugni, az lassabb és hajlamos a kártyák sérülésére.)

Miután az összes kártyát hozzárendelte egy polchoz, így mindegyik polcon a kártyák körülbelül 1/N-a van rajta, a kártyákat álvéletlen sorrendben egyetlen kupacba állítják össze.

Intuitív módon, tekintettel az álvéletlenségre, azt várhatnánk, hogy a további újrakeverések javítani fogják az általános véletlenszerűséget, egy bizonyos pontig…

…de ebben az esetben, ahol a gépnek 10 polca volt, a kutatókat külön megkérdezték, "Elegendő lesz-e a gép egy menete a megfelelő véletlenszerűség létrehozásához?"

A cég vélhetően elkerülni akarta a gép több cikluson keresztüli futtatását, hogy a játékosok elégedettek legyenek és a játék jól menjen, az eszközt tervező mérnökök pedig a saját tesztjeik során nem észleltek nyilvánvalóan kihasználható statisztikai anomáliákat.

A cég azonban meg akart győződni arról nem ment át a saját tesztjein, egyszerűen azért, mert a tesztek megfeleltek a gépnek, ami hamis biztonságérzetet adna számukra.

Végül a kutatók nem csak azt találták, hogy a véletlenszerűség meglehetősen gyenge, hanem azt is, hogy pontosan meg tudták mérni, hogy mennyire rossz, és így alternatív teszteket tudtak kidolgozni, amelyek meggyőzően kimutatták a véletlenszerűség hiányát.

Konkrétan azt mutatták ki, hogy az eszköz egyetlen passzusa elegendően sok rövid kártyasorozatot hagyott a megkevert kimenetben ahhoz, hogy megbízhatóan megjósolhassák átlagosan 9 és 10 közötti kártyát, amikor egy 52 megkevert kártyát tartalmazó csomagot utólag kiosztanak.

Ahogy a kutatók írták:

[Az elméletünk eléneklésével meg tudtuk mutatni, hogy egy hozzáértõ játékos körülbelül 9 és fél kártyát tud helyesen kitalálni egyetlen 52 lapos pakli átfutása során. Egy jól megkevert pakli esetén az optimális stratégia körülbelül 4 és fél kártyát kap helyesen. Ezek az adatok meggyőzték a céget. Az elmélet egy hasznos gyógymódot is javasolt.

[...]

A cég elnöke így válaszolt: "Nem vagyunk elégedettek a következtetéseivel, de hiszünk bennük, és ezért vettük fel." Egyszerű alternatívát javasoltunk: használja kétszer a gépet. Ez egy 200 polcos gépnek megfelelő keverést eredményez. Az itt nem közölt matematikai elemzésünk és további teszteink azt mutatják, hogy ez kellően véletlenszerű.

Mit kell tenni?

Ez a mese több „tanítható pillanatot” tartalmaz, és jó lenne tanulni belőlük, legyen szó programozóról vagy termékmenedzserről, aki kifejezetten a véletlenszerűséggel küszködik, vagy egy SecOps/DevOps/IT/kiberbiztonsági szakember, aki a kiberbiztonsági biztosításban vesz részt. Tábornok:

• A saját tesztek sikeres teljesítése nem elég. A saját tesztek sikertelensége határozottan rossz, de könnyen előfordulhat, hogy olyan teszteket kapunk, amelyeknek az algoritmusától, termékétől vagy szolgáltatásától elvárható, hogy sikeres legyen, különösen, ha a javításokat vagy a „hibajavításokat” aszerint mérjük, hogy átjutnak-e a teszteken. Néha szükség van egy második véleményre, amely objektív, független forrásból származik. Ez a független áttekintés származhat egy kaliforniai matematikai statisztikusok kiváló csapatától, mint itt; a behatolást vizsgálók külső „vörös csapatától”; vagy egy MDR (managed detection and reponse) csapattól, akik saját szemükkel és fülükkel rávilágítanak az Ön kiberbiztonsági helyzetére.
• A rossz hírek meghallgatása fontos. A keverőgépeket gyártó cég elnöke ebben az esetben tökéletesen válaszolt, amikor bevallotta, hogy nem elégedett az eredménnyel, de azért fizetett, hogy feltárja az igazságot, nem csak azért, hogy meghallja, amit remél.
• A kriptográfia különösen, és általában a kiberbiztonság nehéz. A segítségkérés nem a kudarc beismerése, hanem annak elismerése, hogy mi kell a sikerhez.
• A véletlenszerűség túl fontos ahhoz, hogy a véletlenre bízzuk. A rendellenesség mérése nem könnyű (olvassa el az újságot megérteni, miért), de meg lehet és meg kell tenni.

---

Kevés idő vagy szakértelem a kiberbiztonsági fenyegetésekre való reagáláshoz? Aggódik, hogy a kiberbiztonság végül elvonja a figyelmét az összes többi tennivalóról?

Tudjon meg többet Sophos felügyelt észlelés és válasz:
24 órás fenyegetésvadászat, észlelés és reagálás  ▶

---