אבטחה רצינית: אתה לא יכול לנצח את הבית בבלאק ג'ק - או שאתה יכול?

קריפטוגורו ברוס שנייר (איפה קריפטו אומר קריפטוגרפיה, לא הדבר השני!) זה עתה פרסם הערה מסקרנת בבלוג שלו בשם על האקראיות של מערבבי כרטיסים אוטומטיים.

אם אי פעם היית בקזינו, לפחות אחד בנבאדה, תדע ששולחנות הבלאק ג'ק לא לוקחים סיכונים עם לקוחות הידועים במסחר בתור מוני כרטיסים.

המונח הזה משמש להתייחסות לשחקנים שאימנו את הזיכרונות שלהם עד כדי כך שהם יכולים לעקוב מקרוב אחר הקלפים ששיחקו עד כה ביד, מה שנותן להם יתרון תיאורטי על הבית בעת חיזוי אם לעמוד או להכות כמשחק. מתקדם.

מונים קלפים יכולים לרכוש יתרון גם אם כל מה שהם עושים זה לעקוב אחר היחס בין 10 קלפים (עשרה, ג'ק, מלכה ומלך) לא-10 שנותרו בנעל של הדילר.

לדוגמה, אם הדילר יושב עם אס, אבל מספר מעל הממוצע של קלפים בעלי ערך 10 כבר נוצל, אז לדילר יש סיכוי נמוך מהממוצע לעשות בלאק ג'ק (21 נקודות עם שני קלפים, כלומר. אס ואחד של 10-J-Q-K) וזכייה בבת אחת, וסיכוי מעל הממוצע להתפרץ לפני הגעה לנקודת העצירה של 17 ומעלה.

אם אתה יכול לאזן את ההסתברויות בראש שלך בזמן אמת, אז אולי תוכל לשנות את ההימורים שלך בהתאם ולצאת קדימה בטווח הארוך.

אל תנסה זאת, לפחות בנבאדה: הקזינו צפוי לתפוס אותך די מהר, מכיוון שדפוס המשחק שלך יחרוג במיוחד מהאפשרויות המנצחות המושכלות ביותר הזמינות אם אינך סופר קלפים. אולי לא תגיעו לבית המשפט, אבל כמעט בוודאות ילוו אתכם מהמקום, ולעולם לא תיכנסו שוב.

ליישר את הסיכויים

כדי לצמצם את מאזן ההסתברויות שממנה נהנים מוני הקלפים (אלו שעדיין לא נתפסו, לפחות), בתי הקזינו בדרך כלל:

• חלק ידיים מנעל עמוסה בשש חבילות (חבילות) של 52 קלפים. המשמעות היא שכל יד שחולקה מטה את חלוקת הקלפים שנותרה פחות מאשר אם נעשה שימוש בחבילה בודדת.
• ערבבו את כל הנעל של 312 קלפים (שש חבילות) לפני כל יד. כדי לחסוך זמן ולהסיר חשד מהדילר, מכונה אלקטרו-מכאנית פסאודורנדומלית מערבבת את הקלפים ממש על השולחן, מול כל השחקנים.

זה מעלה מיד את השאלה שהציג שנייר: עד כמה קלפים מערבבים היטב כשהם יוצאים מהמכונה?

יש לציין, עם שש חבילות קלפים חדשות, שמגיעות בסדר צפוי (למשל אס למלך הלבבות, אס למלך האלפים, מלך לאס היהלומים, מלך לאס ספייס), כמה הזמנה חלקית נותרה לאחר המכונה עשתה את עבודתה?

האם תוכל "לנחש" את הקלף הבא שיצא מהנעל טוב יותר ממה שהמקרה מציע?

אקראי אלקטרוני מלא מוגבל במורכבותו בעיקר על ידי מהירות המעבד שבו הוא משתמש, הנמדדת בדרך כלל במאות מיליונים או מיליארדי פעולות אריתמטיות בשנייה.

אבל מערבב קלפים אלקטרומכני ממש צריך להזיז את הקלפים בחיים האמיתיים.

ברור שיש גבול לכמה מהר הוא יכול לבצע פיצולי חבילה, החלפת קלפים ופעולות שזירה לפני שמהירות המנגנון מתחילה לפגוע בקלפים, מה שאומר שיש גבול לכמה אקראיות (או ליתר דיוק, פסאודורנדומליות) המכונה יכולה להציג לפני שהגיע הזמן לשחק ביד הבאה.

ערבבו לזמן קצר מדי, והקזינו עשוי למעשה להקל על מונים הקלפים, אם יש הטיה ידועה בהפצת הקלפים כבר מההתחלה.

ערבבו במשך זמן רב מדי, והמשחק יהיה איטי מדי, כך שהשחקנים ישתעממו ויסתובבו, משהו שבתי הקזינו מנסים להימנע ממנו נואשות.

הפוסטים בבלוג של שנייר מקשרים ל-a יצירה מרתקת מאת ה-BBC שמתאר כיצד מתמטיקאי/קוסם בשם פרסי דיאקוניס מאוניברסיטת סטנפורד, יחד עם ג'ייסון פולמן וסוזן הולמס, ערכו חקירה רשמית בנושא זה ממש מוקדם יותר המאה, במאמר שכותרתו פשוט: ניתוח של מכונות דשדוש מדפי קזינו.

רמות מורכבות

ברור שיש כמה טכניקות ערבוב שלא מערבבות את הקלפים בכלל, כמו פשוט גזירה החבילה לשני חלקים והזזת החלק התחתון למעלה.

טכניקות אחרות מביאות (או מרגישות כאילו הן אמורות לגרום) לערבוב טוב יותר, למשל דשדוש רובה, שבו אתה מחלק את החבילה בערך לשניים, מחזיק חצי אחד בכל יד, ו"העיף" את שני החצאים יחד, תוך שילובם בצורה פסאודורנדומלית שמתחלפת בין לקיחת כמה קלפים מצד אחד, ואז כמה קלפים מהצד השני. .

הרעיון הוא שאם אתה מערבב את החבילה מספר פעמים, אתה מבצע רצף פסאודו-אקראי של חיתוכים בכל פעם שאתה מחלק את החבילה לפני כל רובה, מעורבב יחד עם רצף משתנה פסאודו-אקראי של פעולות שזירה פסאודור-אקראי הכוללות N-מה- תהליך שמאלה-ואז-M-מן-הימין.

עם זאת, באופן מסקרן, כאשר מעורבים מערבבים אנושיים מיומנים, אף אחת מההנחות הללו של אי-חיזוי אינה בטוחה.

קוסמים מיומנים וסוחרים מטומטמים (דיאקוניס עצמו הוא הראשון, אבל לא האחרון) יכולים לבצע את מה שמכונה פארו מדשדש, או דשדוש מושלם, שם הם עושים את שני הדברים הבאים בכל פעם שהם מתעסקים עם החפיסה:

• לפצל את הקלפים בדיוק לשניים, ובכך מקבלים בדיוק 26 קלפים בכל יד.
• שלב אותם בצורה מושלמת, הפיכת קלף אחד בדיוק בכל פעם לסירוגין מכל יד, בכל פעם.

דיאקוניס עצמו יכול לעשות דשדוש מושלם (כולל המיומנות הנדירה לעשות זאת ביד אחת בלבד כדי להחזיק את שני חצאי החפיסה!), ולפי ה-BBC:

[הוא] אוהב להדגים את הערבוב המושלם על ידי נטילת חפיסת קלפים חדשה וכתיבת המילה RANDOM בטוש שחור עבה בצד אחד. כשהוא מבצע את מעשי ידיו עם הקלפים, האותיות מתערבבות, ומופיעות מדי פעם בצורה רפאים, כמו תמונה מכווננת בצורה לא מושלמת על מכשיר טלוויזיה ישן. ואז, לאחר שהוא מבצע את הדשדוש השמיני והאחרון, המילה מתחדשת בצד החפיסה. הקלפים נמצאים ברצף המקורי המדויק שלהם, מהאס של ספידים ועד אס הלבבות.

שני סוגים של שלמות

למעשה, ישנם שני סוגים של דשדוש מושלם, תלוי מאיזו יד אתה מתחיל לרפרף לאחר חיתוך הקלפים לשתי ערימות של 26 קלפים.

אתה יכול לשזור את הקלפים כך שהם יסתיימו ברצף 1-27-2-28-3-29-...-25-51-26-52, אם הקלף הראשון שאתה מפנה כלפי מטה מגיע מהיד שבה אתה מחזיק החצי התחתון של החפיסה.

אבל אם הקלף הראשון שהופכים למטה הוא הקלף התחתון של מה שהיה בעבר החצי העליון של החבילה, בסופו של דבר אתה מקבל 27-1-28-2-29-3-…-51-25-52-26, אז כרטיס רק אחרי מחצית הדרך מגיע למעלה לאחר מכן.

הסוג הקודם נקרא an לערבב החוצה, ומסדר מחדש את החבילה כל שמונה פעמים שאתה חוזר עליה, כפי שאתה יכול לראות כאן (בתמונה יש 52 שורות של פיקסלים, כל שורה מתאימה לקצה של כרטיס אחד עם המילה RANDOM כתובה עליו בעט סימון):

הסוג האחרון הוא an ערבוב, וזה, למרבה הפלא, לוקח 52 ערבובים מחדש לפני שהוא חוזר על עצמו, אם כי אתה יכול לראות כאן בבירור שהחבילה אף פעם לא באמת מראה שום אקראיות אמיתית, ואפילו עוברת היפוך מושלם באמצע הדרך:

מה אמרו המתמטיקאים?

אז, עוד ב-2013, כשדיאקוניס אל על. למדו את מכונת הדשדוש המדפים בהזמנת היצרן, מה הם מצאו?

כפי שמסביר זאת העיתון, דשדש מדף הוא ניסיון אלקטרומכני לתכנן "ערבוב רב-שכיבים רב-חתכים" אוטומטי ואקראי, באופן אידיאלי כך שצריך לעבור על הכרטיסים רק פעם אחת, כדי לשמור על זמן הערבוב קצר.

הקלפים במערבל מדף "מחולקים" במהירות פסאודו אקראית, אחד בכל פעם, על אחד מ-N מדפי מתכת בתוך המכשיר (מכאן השם), ובכל פעם שכרטיס נוסף למדף הוא מחליק פנימה ב- תחתית, או נפלה בחלק העליון של כרטיסים קודמים. (אנו מניחים שניסיון לתקוע את הקלף בין שני קלפים אקראיים שכבר נמצאים בערימה יהיה איטי יותר וגם נוטה לפגוע בקלפים.)

לאחר שכל הקלפים הוקצו למדף, כך שבכל מדף יש בערך 1/Nth מהקלפים, הקלפים מורכבים מחדש לערימה אחת בסדר פסאודו אקראי.

באופן אינטואיטיבי, בהינתן הפסאודורנדומליות הכרוכה בכך, היית מצפה שערבובים מחדש נוספים ישפרו את האקראיות הכוללת, עד לנקודה מסוימת...

...אבל במקרה הזה, שבו למכונה היו 10 מדפים, החוקרים נשאלו במפורש, "האם מעבר אחד של המכונה יספיק כדי לייצר אקראיות נאותה?"

יש להניח שהחברה רצתה להימנע מלהפעיל את המכונה במחזורים מרובים כדי לשמור על השחקנים מרוצים והמשחק יזרום היטב, והמהנדסים שתכננו את המכשיר לא זיהו חריגות סטטיסטיות ברורות שניתן לנצל במהלך הבדיקות שלהם.

אבל החברה רצתה לוודא שזה לא עבר את המבחנים שלו פשוט כי המבחנים התאימו למכונה, מה שייתן להם תחושת ביטחון מזויפת.

בסופו של דבר, החוקרים גילו לא רק שהאקראיות הייתה גרועה למדי, אלא גם שהם הצליחו לכמת בדיוק עד כמה היא גרועה, וכך לתכנן בדיקות חלופיות שחשפו בצורה משכנעת את היעדר האקראיות.

בפרט, הם הראו שמעבר אחד בלבד של המכשיר השאיר מספיק רצפים קצרים של קלפים בפלט המעורב, כך שהם יכולים לחזות בצורה מהימנה בין 9 ל-10 קלפים בממוצע, כאשר חבילה של 52 קלפים ערבבו חולקה לאחר מכן.

כפי שכתבו החוקרים:

[לשמר את התיאוריה שלנו, הצלחנו להראות ששחקן בעל ידע יכול לנחש נכון לגבי 9 וחצי קלפים בריצה אחת בחפיסה של 52 קלפים. עבור חפיסה מעורבת היטב, האסטרטגיה האופטימלית מקבלת כ-4 וחצי קלפים נכונים. הנתונים הללו אכן שכנעו את החברה. התיאוריה הציעה גם תרופה שימושית.

[...]

נשיא החברה הגיב: "אנחנו לא מרוצים מהמסקנות שלך, אבל אנחנו מאמינים להן ובשבילו שכרנו אותך". הצענו חלופה פשוטה: השתמשו במכונה פעמיים. זה גורם לדשדוש שווה ערך למכונה של 200 מדפים. הניתוח המתמטי שלנו ומבחנים נוספים, שלא דווחו כאן, מראים שזה אקראי במידה מספקת.

מה לעשות?

סיפור זה מכיל מספר "רגעים ניתנים ללמד", והיה חכם ללמוד מהם, בין אם אתה מתכנת או מנהל מוצר שמתאבק ספציפית באקראיות בעצמך, או איש מקצוע של SecOps/DevOps/IT/אבטחת סייבר שעוסק באבטחת סייבר ב- כללי:

• לעבור את המבחנים שלך זה לא מספיק. כישלון במבחנים שלך זה בהחלט רע, אבל קל להגיע לבדיקות שאתה מצפה שהאלגוריתם, המוצר או השירות שלך יעברו, במיוחד אם התיקונים או "תיקוני הבאגים" שלך נמדדים לפי האם הם יעבירו אותך דרך הבדיקות. לפעמים, אתה צריך חוות דעת שנייה ואז מגיעה ממקור אובייקטיבי ובלתי תלוי. סקירה עצמאית זו יכולה להגיע מצוות קראק של סטטיסטיקאים מתמטיים מקליפורניה, כמו כאן; מ"צוות אדום" חיצוני של בודקי חדירה; או מצוות MDR (מנוהל זיהוי ותגובה) שמביא את העיניים והאוזניים שלהם למצב אבטחת הסייבר שלך.
• חשוב להקשיב לחדשות רעות. נשיא חברת מכונות הדשדוש במקרה הזה ענה בצורה מושלמת כשהודה שהוא לא מרוצה מהתוצאה, אבל הוא שילם כדי לחשוף את האמת, לא רק כדי לשמוע את מה שהוא מקווה.
• קריפטוגרפיה בפרט, ואבטחת סייבר בכלל, היא קשה. בקשת עזרה אינה הודאה בכישלון אלא הכרה במה שנדרש כדי להצליח.
• האקראיות חשובה מכדי להיות מותירה למקרה. מדידת הפרעה אינה קלה (לקרוא את העיתון להבין למה), אבל אפשר וצריך לעשות זאת.

---

חסר לך זמן או מומחיות לטפל בתגובה לאיומי אבטחת סייבר? חוששים שאבטחת סייבר תסיח את דעתך מכל שאר הדברים שאתה צריך לעשות?

למידע נוסף בנושא Sophos Managed Detection and Response:
ציד, איתור ותגובה של איומים 24/7  ▶

---