An ninh nghiêm túc: Bạn không thể đánh bại nhà ở Blackjack - hay bạn có thể?

Cryptoguru Bruce Schneier (nơi Crypto có nghĩa mật mã, không phải thứ khác!) vừa đăng một ghi chú hấp dẫn trên blog của mình có tựa đề Về tính ngẫu nhiên của máy xáo trộn thẻ tự động.

Nếu bạn đã từng đến một sòng bạc, ít nhất là một sòng bạc ở Nevada, bạn sẽ biết rằng các bàn blackjack không có cơ hội với những khách hàng được biết đến trong ngành như quầy thẻ.

Thuật ngữ đó được dùng để chỉ những người chơi đã rèn luyện trí nhớ của mình đến mức họ có thể theo dõi chặt chẽ các quân bài đã chơi cho đến nay trong ván bài, điều này mang lại cho họ lợi thế về mặt lý thuyết so với nhà cái khi dự đoán nên đứng hay đánh khi chơi. tiến triển.

Người đếm bài có thể giành được lợi thế ngay cả khi tất cả những gì họ làm là theo dõi tỷ lệ của các quân bài 10 (Mười, Jack, Hậu và Vua) so với các quân không phải 10 còn lại trong giày của người chia bài.

Ví dụ: nếu người chia bài đang có quân Át, nhưng số quân bài 10 giá trị trên mức trung bình đã được sử dụng hết, thì người chia bài có cơ hội kiếm được blackjack dưới mức trung bình (21 điểm với hai quân bài, tức là Ace và một trong 10-JQK) và giành chiến thắng ngay lập tức, đồng thời có cơ hội phá sản trên mức trung bình trước khi đạt đến điểm dừng từ 17 trở lên.

Nếu bạn có thể cân bằng các xác suất trong đầu theo thời gian thực, thì bạn có thể sửa đổi mức đặt cược của mình cho phù hợp và đạt được kết quả tốt hơn về lâu dài.

Đừng thực sự thử điều này, ít nhất là ở Nevada: sòng bạc có thể sẽ loại bạn khá nhanh, bởi vì kiểu chơi của bạn sẽ khác biệt đáng kể so với những lựa chọn chiến thắng sáng suốt nhất hiện có nếu bạn không đếm bài. Bạn có thể không phải ra tòa, nhưng gần như chắc chắn bạn sẽ bị áp giải ra khỏi cơ sở và không bao giờ được phép quay lại nữa.

Cân bằng tỷ lệ cược

Để giảm sự cân bằng về xác suất mà những người đếm bài được hưởng (ít nhất là những người chưa bị bắt), các sòng bạc thường:

• Chia bài từ một chiếc giày chứa sáu gói (bộ bài) gồm 52 lá bài. Điều này có nghĩa là mỗi ván bài được chia sẽ làm lệch số lượng bài còn lại ít hơn so với khi sử dụng một gói duy nhất.
• Xáo toàn bộ hộp gồm 312 lá bài (sáu gói) trước mỗi ván bài. Để tiết kiệm thời gian và loại bỏ sự nghi ngờ của người chia bài, một máy cơ điện giả ngẫu nhiên sẽ xáo bài ngay trên bàn, trước mặt tất cả người chơi.

Điều đó ngay lập tức đặt ra câu hỏi mà Schneier đặt ra: các lá bài được xáo trộn tốt đến mức nào khi chúng xuất hiện từ máy?

Đáng chú ý, với sáu bộ bài mới, sắp xếp theo thứ tự có thể dự đoán được (ví dụ: Ace đến King of Hearts, Ace đến King of Clubs, King đến Ace of Diamonds, King đến Ace of Spades), số lượng phần đặt hàng còn lại sau khi máy đã hoàn thành công việc của nó chưa?

Bạn có thể “đoán” lá bài tiếp theo tốt hơn cơ hội gợi ý không?

Bộ tạo ngẫu nhiên hoàn toàn bằng điện tử bị giới hạn về độ phức tạp chủ yếu bởi tốc độ của CPU mà nó sử dụng, thường được đo bằng hàng trăm triệu hoặc hàng tỷ phép tính số học một giây.

Nhưng một bộ xáo trộn thẻ cơ điện theo đúng nghĩa đen phải di chuyển các thẻ xung quanh trong cuộc sống thực.

Rõ ràng là có giới hạn về tốc độ nó có thể thực hiện chia gói, hoán đổi thẻ và các hoạt động xen kẽ trước khi tốc độ của cơ chế bắt đầu làm hỏng thẻ, điều đó có nghĩa là có giới hạn về mức độ ngẫu nhiên (hay chính xác hơn là sự giả tạo) máy có thể giới thiệu trước khi đến lượt chơi ván tiếp theo.

Xào bài trong thời gian quá ngắn và sòng bạc thực sự có thể làm mọi việc dễ dàng hơn cho người đếm bài, nếu có sự thiên vị đã biết trong việc phân phối bài ngay từ đầu.

Xáo trộn quá lâu và chơi sẽ quá chậm, khiến người chơi cảm thấy nhàm chán và bỏ đi, điều mà các sòng bạc cố gắng hết sức tránh.

Các bài đăng trên blog của Schneier liên kết tới một mảnh hấp dẫn của BBC mô tả cách một nhà toán học/ảo thuật gia tên là Persi Diaconis của Đại học Stanford, cùng với Jason Fulman và Susan Holmes, tiến hành một cuộc điều tra chính thức về chính vấn đề này vào đầu thế kỷ này, trong một bài báo có tựa đề đơn giản: PHÂN TÍCH MÁY XÓA KỆ CASINO.

Mức độ phức tạp

Rõ ràng, có một số kỹ thuật xáo trộn không trộn lẫn các quân bài nhiều chút nào, chẳng hạn như đơn giản là cắt gói thành hai phần và di chuyển phần dưới lên trên.

Các kỹ thuật khác mang lại (hoặc cảm thấy như thể chúng sẽ mang lại) sự trộn tốt hơn, ví dụ như xáo trộn ngẫu nhiên, trong đó bạn chia đôi gói, giữ một nửa trong mỗi tay và “lật” hai nửa lại với nhau, xen kẽ chúng theo cách giả ngẫu nhiên xen kẽ giữa việc lấy một vài lá bài từ một bên, sau đó lấy một vài lá bài từ bên kia .

Ý tưởng là nếu bạn xáo trộn gói nhiều lần, bạn sẽ thực hiện một chuỗi các lần cắt giả ngẫu nhiên mỗi lần bạn chia gói trước mỗi lần xáo trộn, trộn lẫn với một chuỗi biến đổi giả ngẫu nhiên của các thao tác xen kẽ giả ngẫu nhiên liên quan đến N-từ-the- quá trình trái-rồi-M-từ-phải.

Tuy nhiên, điều thú vị là khi có sự tham gia của những người xáo trộn lành nghề, không có giả định nào về tính không thể đoán trước là an toàn.

Những pháp sư khéo léo và những kẻ buôn bán quanh co (bản thân Diaconis là người đầu tiên, nhưng không phải người sau) có thể thực hiện những gì được gọi là xáo trộn faro, hoặc là xáo trộn hoàn hảo, nơi họ thực hiện cả hai điều sau đây mỗi lần họ lục gói:

• Chia các thẻ chính xác thành hai, do đó nhận được chính xác 26 lá bài trong mỗi ván bài.
• Xen kẽ chúng một cách hoàn hảo, lần lượt lật xuống chính xác một lá bài từ mỗi tay.

Bản thân Diaconis có thể thực hiện những pha xáo trộn hoàn hảo (bao gồm cả kỹ năng hiếm có khi làm điều đó chỉ bằng một tay để giữ cả hai nửa đàn!), và theo BBC:

[Anh ấy] thích thể hiện khả năng xáo trộn hoàn hảo bằng cách lấy một bộ bài mới và viết từ RANDOM bằng bút dạ màu đen dày ở một mặt. Khi anh ấy thực hiện trò chơi khéo léo của mình với các lá bài, các chữ cái bị trộn lẫn, thỉnh thoảng xuất hiện dưới dạng ma quái, giống như một hình ảnh được điều chỉnh không hoàn hảo trên một chiếc TV cũ. Sau đó, sau khi anh ta thực hiện lần xáo bài thứ tám và cũng là lần xáo trộn cuối cùng, từ đó xuất hiện trở lại bên cạnh bộ bài. Các quân bài được sắp xếp theo thứ tự chính xác ban đầu, từ Át bích đến Át tim.

Hai loại hoàn hảo

Trên thực tế, có hai kiểu xáo bài hoàn hảo, tùy thuộc vào tay bạn bắt đầu riff sau khi chia bài thành hai chồng 26 lá.

Bạn có thể xen kẽ các lá bài để chúng có kết quả theo trình tự 1-27-2-28-3-29-…-25-51-26-52, nếu lá bài đầu tiên bạn lật xuống đến từ tay bạn đang cầm anh ấy ở nửa dưới của gói.

Nhưng nếu lá bài đầu tiên bạn lật xuống là lá bài dưới cùng của nửa trên của bộ trước đó, bạn sẽ có 27-1-28-2-29-3-…-51-25-52-26, vì vậy thẻ vừa đi được nửa đường sẽ ở trên cùng sau đó.

Loại trước đây được gọi là xáo trộnvà sắp xếp lại gói sau mỗi tám lần bạn lặp lại, như bạn có thể thấy ở đây (hình ảnh có 52 dòng pixel, mỗi dòng tương ứng với cạnh của một thẻ có chữ RANDOM được viết trên đó bằng bút đánh dấu):

Loại sau là một ngẫu nhiên, và điều này, thật đáng kinh ngạc, phải mất 52 lần xáo trộn lại trước khi nó lặp lại, mặc dù bạn có thể thấy rõ ở đây rằng gói này không bao giờ thực sự thể hiện bất kỳ sự ngẫu nhiên thực sự nào và thậm chí còn trải qua một sự đảo ngược hoàn hảo ở nửa chặng đường:

Các nhà toán học đã nói gì?

Vì vậy, trở lại năm 2013, khi Diaconis el al. nghiên cứu máy xáo trộn kệ theo lời mời của nhà sản xuất, họ tìm thấy điều gì?

Như bài báo giải thích, máy xáo bài trên kệ là một nỗ lực cơ điện nhằm tạo ra một “xáo bài nhiều đoạn nhiều đoạn” tự động, ngẫu nhiên, lý tưởng là các lá bài chỉ cần được xử lý một lần, để rút ngắn thời gian xáo bài.

Các thẻ trong bộ xáo trộn trên kệ nhanh chóng được “xử lý” một cách giả ngẫu nhiên, lần lượt từng thẻ một, trên một trong N kệ kim loại bên trong thiết bị (vì thế mà có tên) và mỗi lần một thẻ được thêm vào kệ, nó sẽ được trượt vào dưới cùng hoặc thả lên trên cùng của thẻ trước đó. (Chúng tôi cho rằng việc cố gắng chọc thẻ vào giữa hai thẻ ngẫu nhiên đã có trong ngăn xếp sẽ vừa chậm hơn vừa dễ làm hỏng thẻ.)

Sau khi tất cả các thẻ đã được xếp vào một giá, sao cho mỗi giá có khoảng 1/N số thẻ trên đó, các thẻ sẽ được tập hợp lại thành một chồng theo thứ tự giả ngẫu nhiên.

Theo trực giác, với tính chất giả ngẫu nhiên có liên quan, bạn có thể mong đợi rằng những lần xáo trộn lại bổ sung sẽ cải thiện tính ngẫu nhiên tổng thể, đến một mức độ nào đó…

…nhưng trong trường hợp này, khi chiếc máy có 10 kệ, các nhà nghiên cứu được yêu cầu cụ thể, “Liệu một lần chạy máy có đủ để tạo ra sự ngẫu nhiên đầy đủ không?”

Có lẽ, công ty muốn tránh chạy máy qua nhiều chu kỳ để giữ cho người chơi hài lòng và trò chơi diễn ra tốt đẹp, đồng thời các kỹ sư thiết kế thiết bị đã không phát hiện bất kỳ sự bất thường thống kê rõ ràng nào có thể bị lợi dụng trong quá trình thử nghiệm của chính họ.

Nhưng công ty muốn đảm bảo rằng đã không vượt qua được các bài kiểm tra của chính nó chỉ vì các bài kiểm tra phù hợp với máy, điều này sẽ mang lại cho họ cảm giác an toàn giả tạo.

Cuối cùng, các nhà nghiên cứu không chỉ nhận thấy rằng tính ngẫu nhiên khá kém mà họ còn có thể định lượng chính xác mức độ kém của nó và do đó đưa ra các thử nghiệm thay thế tiết lộ một cách thuyết phục sự thiếu ngẫu nhiên.

Đặc biệt, họ đã chỉ ra rằng chỉ cần một lượt thiết bị để lại đủ nhiều chuỗi quân bài ngắn trong đầu ra được xáo trộn mà họ có thể dự đoán một cách đáng tin cậy trung bình từ 9 đến 10 quân bài khi một gói 52 quân bài được xáo trộn được chia sau đó.

Như các nhà nghiên cứu đã viết:

[U]hát lý thuyết của chúng tôi, chúng tôi đã có thể chứng minh rằng một người chơi hiểu biết có thể đoán chính xác khoảng 9 lá bài rưỡi chỉ trong một lần chạy qua bộ bài 52 lá. Đối với một bộ bài được xáo trộn tốt, chiến lược tối ưu là lấy đúng khoảng 4 quân rưỡi. Dữ liệu này đã thuyết phục được công ty. Lý thuyết này cũng đề xuất một phương pháp chữa trị hữu ích.

[...]

Chủ tịch công ty trả lời: “Chúng tôi không hài lòng với kết luận của bạn, nhưng chúng tôi tin chúng và đó là lý do chúng tôi thuê bạn”. Chúng tôi đã đề xuất một giải pháp thay thế đơn giản: sử dụng máy hai lần. Điều này dẫn đến việc xáo trộn tương đương với một chiếc máy 200 kệ. Phân tích toán học của chúng tôi và các thử nghiệm sâu hơn, không được báo cáo ở đây, cho thấy đây là kết quả ngẫu nhiên đầy đủ.

Phải làm gì?

Câu chuyện này chứa đựng một số “khoảnh khắc có thể dạy được” và bạn nên học hỏi từ chúng, cho dù bạn là lập trình viên hay người quản lý sản phẩm đang vật lộn với vấn đề ngẫu nhiên hay một chuyên gia SecOps/DevOps/IT/an ninh mạng tham gia vào việc đảm bảo an ninh mạng trong tổng quan:

• Vượt qua bài kiểm tra của riêng bạn là không đủ. Việc thất bại trong các thử nghiệm của chính bạn chắc chắn là điều tồi tệ, nhưng bạn rất dễ kết thúc với các thử nghiệm mà bạn mong đợi thuật toán, sản phẩm hoặc dịch vụ của mình vượt qua, đặc biệt nếu các sửa chữa hoặc “sửa lỗi” của bạn được đo lường bằng việc liệu chúng có giúp bạn vượt qua các thử nghiệm hay không. Đôi khi, bạn cần có ý kiến ​​thứ hai đến từ một nguồn khách quan, độc lập. Cái nhìn tổng quan độc lập đó có thể đến từ một nhóm các nhà thống kê toán học xuất sắc từ California, như ở đây; từ “đội đỏ” bên ngoài gồm những người thử nghiệm thâm nhập; hoặc từ đội ngũ MDR (phát hiện và phản hồi được quản lý), những người tận mắt chứng kiến ​​tình huống an ninh mạng của bạn.
• Nghe tin xấu là quan trọng. Chủ tịch công ty máy xáo trộn trong trường hợp này đã trả lời một cách hoàn hảo khi ông thừa nhận rằng ông không hài lòng với kết quả này, nhưng ông đã trả tiền để khám phá ra sự thật chứ không chỉ đơn giản là nghe những gì ông hy vọng.
• Mật mã nói riêng và an ninh mạng nói chung rất khó. Yêu cầu giúp đỡ không phải là sự thừa nhận thất bại mà là sự thừa nhận những gì cần thiết để thành công.
• Sự ngẫu nhiên là quá quan trọng để có thể phó mặc cho sự may rủi. Đo lường rối loạn không dễ dàng (đọc tờ giấy để hiểu tại sao), nhưng nó có thể và nên được thực hiện.

---

Thiếu thời gian hoặc chuyên môn để xử lý các mối đe dọa an ninh mạng? Bạn lo lắng rằng an ninh mạng sẽ khiến bạn mất tập trung khỏi tất cả những việc khác mà bạn cần làm?

Tìm hiểu thêm về Phản hồi và phát hiện được quản lý của Sophos:
Tìm kiếm, phát hiện và phản ứng mối đe dọa 24/7  ▶

---