Securitate serioasă: Nu poți învinge casa la Blackjack – sau poți?

Cryptoguru Bruce Schneier (unde cripto mijloace criptografie, nu cealaltă chestie!) tocmai a publicat o notă intrigantă pe blogul său intitulată Despre caracterul aleatoriu al amestecarilor automate de carduri.

Dacă ați fost vreodată la un cazinou, cel puțin unul din Nevada, veți ști că mesele de blackjack nu riscă cu clienții cunoscuți în comerț ca contoare de carduri.

Acest termen este folosit pentru a se referi la jucătorii care și-au antrenat amintirile până la punctul în care pot urmări îndeaproape cărțile jucate până acum într-o mână, ceea ce le oferă un avantaj teoretic față de casă atunci când prezic dacă să stea în picioare sau să lovească în joc. progresează.

Contoarele de cărți pot obține un avantaj chiar dacă tot ceea ce fac este să țină evidența raportului dintre 10 cărți (Zece, Jack, Queen și King) și non-10 rămase în pantoful dealer-ului.

De exemplu, dacă dealer-ul stă cu un As, dar un număr peste medie de cărți de 10 cărți a fost deja consumat, atunci dealer-ul are o șansă sub medie de a face un blackjack (21 de puncte cu două cărți, adică As și unul de 10-JQK) și câștig deodată, și o șansă peste medie de a se epuiza înainte de a ajunge la punctul de oprire de 17 și mai sus.

Dacă poți echilibra probabilitățile din capul tău în timp real, atunci s-ar putea să-ți modifici pariurile în consecință și să ieși înainte pe termen lung.

Nu încercați asta, cel puțin în Nevada: este posibil ca cazinoul să vă surprindă destul de repede, deoarece modelul dvs. de joc se va abate în mod semnificativ de la cele mai informate opțiuni câștigătoare disponibile dacă nu numărați cărțile. S-ar putea să nu ajungi în instanță, dar aproape sigur vei fi escortat în afara sediului și nu vei mai lăsa niciodată să intri.

Nivelarea cotelor

Pentru a reduce contrabalansarea probabilităților de care se bucură contoarele de cărți (cel puțin cei care nu au fost prinși încă), cazinourile de obicei:

• Împărțiți mâini dintr-un pantof încărcat cu șase pachete (pachete) de 52 de cărți. Aceasta înseamnă că fiecare mână împărțită deformează distribuția rămasă de cărți mai puțin decât dacă ar fi folosit un singur pachet.
• Amestecă întregul pantof de 312 cărți (șase pachete) înainte de fiecare mână. Pentru a economisi timp și pentru a înlătura suspiciunea dealerului, o mașină electromecanică pseudoaleatorie amestecă cărțile chiar pe masă, în fața tuturor jucătorilor.

Asta ridică imediat întrebarea pusă de Schneier: cât de bine amestecate sunt cărțile când ies din mașină?

În special, cu șase pachete noi de cărți, care sosesc într-o ordine previzibilă (de ex. As la Regele Inimii, As la Regele Tresoare, Rege la Asul Diamantelor, Rege la Asul de pică), câtă ordine parțială rămâne după mașina și-a făcut treaba?

Ai putea „ghici” următoarea carte din pantof mai bine decât sugerează întâmplarea?

Un randomiser complet electronic este limitat în complexitatea sa în principal de viteza procesorului pe care îl folosește, care este de obicei măsurată în sute de milioane sau miliarde de operații aritmetice pe secundă.

Dar un amestecător de cărți electromecanic trebuie să mute cărțile în viața reală.

În mod evident, există o limită a cât de repede poate efectua împărțirea pachetelor, schimburile de cărți și operațiunile de intercalare înainte ca viteza mecanismului să înceapă să deterioreze cărțile, ceea ce înseamnă că există o limită a gradului de aleatorie (sau, mai precis, pseudoaleatorie) aparatul poate introduce înainte de a ajunge timpul să joace următoarea mână.

Amestecați pentru o perioadă prea scurtă de timp, iar cazinoul ar putea face lucrurile mai ușor pentru contoarele de cărți, dacă există o părtinire cunoscută în distribuirea cărților chiar de la început.

Amestecă prea mult timp, iar jocul va fi prea lent, astfel încât jucătorii se vor plictisi și se vor rătăci, lucru pe care cazinourile încearcă cu disperare să-l evite.

Blogul lui Schneier postează link-uri către a piesa fascinanta de BBC, care descrie modul în care un matematician/magist numit Persi Diaconis de la Universitatea Stanford, împreună cu Jason Fulman și Susan Holmes, au condus o investigație oficială asupra acestei probleme la începutul acestui secol, într-o lucrare intitulată simplu: ANALIZA MAȘINILOR DE MALATĂ PE RAFTURI DE CASINO.

Nivele de complexitate

În mod clar, există câteva tehnici de amestecare care nu amestecă deloc cărțile, cum ar fi pur și simplu tăiere pachetul în două părți și mutând partea de jos în sus.

Alte tehnici au ca rezultat (sau simt ca ar trebui să rezulte) o amestecare mai bună, de exemplu riffle shuffle, unde împărțiți pachetul aproximativ în jumătate, țineți câte o jumătate în fiecare mână și „întoarceți” cele două jumătăți împreună, intercalându-le într-un mod pseudoaleator, care alternează între luarea câtorva cărți dintr-o parte, apoi câteva cărți din cealaltă .

Ideea este că, dacă amestecați pachetul de mai multe ori, efectuați o secvență pseudoaleatoare de tăieturi de fiecare dată când împărțiți pachetul înainte de fiecare pușcă, amestecată împreună cu o secvență variabilă pseudoaleatoare de operații de intercalare pseudoaleatoare care implică un N-din-la- proces stânga-apoi-M-din-dreapta.

În mod intrigant, totuși, atunci când sunt implicați oameni pricepuți, niciuna dintre aceste presupuneri de imprevizibilitate nu este sigură.

Magicieni abili și dealerii strâmbi (Diaconis însuși este primul, dar nu cel din urmă) pot realiza ceea ce sunt cunoscuti ca faro amestecă, Sau amestecuri perfecte, în care fac ambele lucruri de mai jos de fiecare dată când pun în joc pachetul:

• Împărțiți cărțile exact în două, obtinand astfel exact 26 de carti in fiecare mana.
• Intercalează-le perfect, răsturnând în jos exact o carte la un moment dat alternativ din fiecare mână, de fiecare dată.

Diaconis însuși poate face amestecuri perfecte (inclusiv abilitatea rară de a face acest lucru cu o singură mână pentru a ține ambele jumătăți ale pachetului!), și conform BBC:

[El] îi place să demonstreze amestecul perfect luând un nou pachet de cărți și scriind cuvântul RANDOM cu un marker gros negru pe o parte. În timp ce își îndeplinește jocul de joc cu cărțile, literele se amestecă, apărând din când în când sub formă fantomatică, ca o imagine reglată imperfect pe un televizor vechi. Apoi, după ce face a opta și ultima amestecare, cuvântul se rematerializează pe partea laterală a punții. Cărțile sunt în ordinea lor originală exactă, de la Asul de pică la Asul de inimă.

Două tipuri de perfecțiune

De fapt, există două feluri de amestecare perfectă, în funcție de mâna din care începeți să riffleți după ce ați tăiat cărțile în două grămezi de 26 de cărți.

Puteți intercala cărțile astfel încât acestea să ajungă în secvența 1-27-2-28-3-29-…-25-51-26-52, dacă prima carte pe care o întoarceți în jos provine din mâna în care o țineți jumătatea de jos a pachetului.

Dar dacă prima carte pe care o întoarceți în jos este cartea de jos a ceea ce era anterior jumătatea superioară a pachetului, ajungeți cu 27-1-28-2-29-3-…-51-25-52-26, deci cartea care a trecut de jumătatea drumului ajunge pe partea de sus după aceea.

Primul tip se numește an out-shuffle, și reordonează pachetul la fiecare opt ori când îl repeți, după cum puteți vedea aici (imaginea are 52 de linii de pixeli, fiecare linie corespunzând marginii unei cărți cu cuvântul RANDOM scris pe ea cu un creion):

Ultimul tip este un în amestecare, și acest lucru, uimitor, necesită 52 de re-amestecări înainte de a se repeta, deși puteți vedea clar aici că pachetul nu arată niciodată vreo aleatorie adevărată și chiar trece printr-o inversare perfectă la jumătatea drumului:

Ce au spus matematicienii?

Deci, în 2013, când Diaconis el al. au studiat mașina de amestecat rafturi la invitația producătorului, ce au găsit?

După cum explică lucrarea, un amestecător de raft este o încercare electromecanică de a concepe o „amestecare cu mai multe tăieturi cu mai multe puști”, automată, randomizată, în mod ideal, astfel încât cărțile să fie prelucrate o singură dată, pentru a reduce timpul de amestecare.

Cărțile dintr-un amestecător de raft sunt rapid „împărțite” pseudoaleatoriu, una câte una, pe unul dintre cele N rafturi metalice din interiorul dispozitivului (de unde și numele), și de fiecare dată când o carte este adăugată la un raft, este fie introdusă în jos, sau aruncat pe partea de sus a cărților anterioare. (Presumăm că încercarea de a pune cartea între două cărți aleatorii aflate deja în stivă ar fi mai lentă și predispusă la deteriorarea cărților.)

După ce toate cărțile au fost alocate unui raft, astfel încât fiecare raft să aibă aproximativ 1/Nth din cărți pe el, cărțile sunt reasamblate într-o singură grămadă într-o ordine pseudoaleatorie.

Intuitiv, având în vedere caracterul pseudoaleatoriu implicat, te-ai aștepta ca reamesteri suplimentare să îmbunătățească aleatoritatea generală, până la un punct...

… dar în acest caz, în care mașina avea 10 rafturi, cercetătorii au fost întrebați în mod specific: „O singură trecere a mașinii va fi suficientă pentru a produce o aleatorie adecvată?”

Probabil, compania a vrut să evite rularea mașinii prin mai multe cicluri pentru a menține jucătorii fericiți și jocul să curgă bine, iar inginerii care au proiectat dispozitivul nu detectaseră nicio anomalie statistică evident expotable în timpul propriilor teste.

Dar compania a vrut să se asigure că asta nu trecuse propriile teste pur și simplu pentru că testele se potriveau mașinii, ceea ce le-ar da un fals sentiment de securitate.

În cele din urmă, cercetătorii au descoperit nu numai că aleatorietatea era destul de slabă, ci și că au putut cuantifica exact cât de slabă era și, astfel, să conceapă teste alternative care să dezvăluie în mod convingător lipsa aleatoriei.

În special, ei au arătat că doar o singură trecere a dispozitivului a lăsat suficient de multe secvențe scurte de cărți în ieșirea amestecată încât să poată prezice în mod fiabil între 9 și 10 cărți în medie atunci când un pachet de 52 de cărți amestecate a fost împărțit ulterior.

După cum au scris cercetătorii:

Folosind teoria noastră, am reușit să arătăm că un jucător informat ar putea ghici corect despre 9 cărți și jumătate într-o singură trecere printr-un pachet de 52 de cărți. Pentru un pachet bine amestecat, strategia optimă obține aproximativ 4 cărți și jumătate corecte. Aceste date au convins compania. Teoria a sugerat și un remediu util.

[...]

Președintele companiei a răspuns: „Nu suntem mulțumiți de concluziile tale, dar le credem și pentru asta te-am angajat”. V-am sugerat o alternativă simplă: folosiți mașina de două ori. Acest lucru are ca rezultat o amestecare echivalentă cu o mașină cu 200 de rafturi. Analiza noastră matematică și testele ulterioare, care nu sunt raportate aici, arată că acest lucru este în mod adecvat aleatoriu.

Ce să fac?

Această poveste conține mai multe „momente care pot fi învățate” și ai fi înțelept să înveți din ele, fie că ești programator sau manager de produs care luptă în mod special cu randomss, sau un profesionist SecOps/DevOps/IT/securitate cibernetică care este implicat în asigurarea securității cibernetice în general:

• Trecerea propriilor teste nu este suficient. Eșuarea propriilor teste este cu siguranță rău, dar este ușor să ajungi cu teste pe care te aștepți să le treacă algoritmul, produsul sau serviciul tău, mai ales dacă corecțiile sau „remedierea erorilor” sunt măsurate în funcție de faptul că trec prin teste. Uneori, ai nevoie de o a doua opinie, apoi vine de la o sursă obiectivă, independentă. Această privire de ansamblu independentă ar putea veni de la o echipă de statisticieni matematici din California, ca aici; dintr-o „echipă roșie” externă de testeri de penetrare; sau de la un echipaj MDR (detecție și răspuns gestionat) care își aduc propriile ochi și urechi la situația ta de securitate cibernetică.
• Ascultarea veștilor proaste este importantă. Președintele companiei de mașini de amestecat în acest caz a răspuns perfect când a recunoscut că este nemulțumit de rezultat, dar că a plătit pentru a descoperi adevărul, nu doar pentru a auzi ce spera.
• Criptografia în special, și securitatea cibernetică în general, este dificilă. A cere ajutor nu este o recunoaștere a eșecului, ci o recunoaștere a ceea ce este nevoie pentru a reuși.
• Aleatoriu este prea important pentru a fi lăsat la voia întâmplării. Măsurarea tulburării nu este ușor (Citește ziarul pentru a înțelege de ce), dar se poate și trebuie făcut.

---

Nu aveți timp sau experiență pentru a vă ocupa de răspunsul la amenințările de securitate cibernetică? Vă faceți griji că securitatea cibernetică vă va distrage atenția de la toate celelalte lucruri pe care trebuie să le faceți?

Aflați mai multe despre Sophos Managed Detection and Response:
Vânătoarea, detectarea și răspunsul amenințărilor 24/7  ▶

---