Ishikawa Oku Laboratory robot version 2 cheating at rock, player, scissors at University of Tokyo. Video runs at 0.25 speed.

Cheating

The classic game between human players uses a style of play where both players present their choice at the same time to reduce the possibility of cheating by reacting to the other player's choice. Human reaction times make this a reasonable approach.

If there is not an agreed time to exchange choices then this allows a nefarious player to observe/receive an opponent's choice and then react to it. The video above shows a crafty, custom robot which carefully watches the opponent's hand and rapidly reacts with a winning choice within the human hand's movement time.

The game can be written to avoid immediately revealing the opponent's choice. This would prevent a player waiting and then reacting to that opponent. Unfortunately, a modified game could still reveal this and facilitate cheating. This could be solved with:

  1. some method for preventing modification of the code or robustly verifying its integrity;
  2. a truly simultaneous exchange;
  3. a trusted third party, an arbitrator, collecting and then distributing the choices or wins together;
  4. an approach where the choices are exchanged in some form but cannot be read until all are received.

The first option isn't feasible as CircuitPython and the associated hardware don't support this feature and code modification is intentionally trivial. The second option seems tempting but it is difficult to synchronise the devices to exchange data precisely enough. The exchange could only be near simultaneous with more than two devices and even two devices would struggle to achieve this with the busy radio spectrum used by Bluetooth.

The fourth option is desirable and practical as it removes the need in the third option for a referee or asymmetric roles for the players. It also doesn't place any constraints on the timing of communication between devices.

Simultaneous Exchange of Player Choices

The players could send an encrypted version of their choice and then send the key only when they have received the choices from all of the opponents. Since the key is revealed it cannot be reused making it a per-message key.

First Idea

An encryption algorithm E might produce the following with a certain key k:

  • Ek(rock) = chey
  • Ek(paper) = ennem
  • Ek(scissors) = roncttla

It only takes a few seconds to see the flaw in this approach. The length of the output ciphertext gives away the choice because the input plainttext has a known format with a well-known, small set of possible values with unique lengths. This is a very simple form of traffic analysis.

Second Idea

Adding some characters to the messages to make them the same length removes the ability to deduce the choice in this case. This is referred to as padding.

The one-time pad (also known as Vernam cipher) is a cipher which has the useful property of being unbreakable when used correctly. It should not be confused with padding mentioned in the previous paragraph. Given the short plaintext it is a very tempting choice here. An example of this is shown below.

Download: file
>>> random.seed(0)
>>> plaintext = "rock....".encode("ascii")
>>> key = bytes([random.randrange(256) for _ in range(len(plaintext))])
>>> ciphertext = bytes([pt ^ k for pt, k in zip(plaintext, key)])
>>> ciphertext
b'\x9e\x1c4\x8b\x93~w\xb0'

There are two issues here. The first is hinted at by the inclusion of a superfluous looking execution of random.seed(), the second is a bit more subtle and discussed later.

Any one who considers arithmetical methods of producting random digits is, of course, in a state of sin.

John Von Neumann (1951)

The seed sets where a random library starts its random number sequence and that sequence will be predictable from a seed value. CircuitPython running on nRF52840-based boards like the CLUE and Circuit Playground Bluefruit initialise the seed with a number from the os.random() function. os.random() provides true random numbers from a hardware generator.

Third Idea

The one-time pad seems suitable if the seed is initialised with a true random number. Unfortunately for cryptography, the pseudo-random number generator (PRNG) commonly found in libraries produces a predictable stream of values. This is clearly noted in both the Python and CircuitPython documentation.

Numbers from this module are not cryptographically strong! Use bytes from os.urandom directly for true randomness.

The values from a standard PRNG must not be used for proper cryptography. In this case the key is intentionally revealed to everyone by the design of the protocol including any eavesdroppers. Over time, this provides an attacker with a sequence of consecutive numbers from the PRNG which is a very useful aid to determine the seed.

Fourth Idea

The solution looks robust in terms of the key if a true random number generator is used to generate that key.

Download: file
>>> plaintext = "rock....".encode("ascii")
>>> key = os.urandom(len(plaintext))
>>> ciphertext = bytes([pt ^ k for pt, k in zip(plaintext, key)])
>>> ciphertext
b'\x82\x0e\xe7\xf4\xe3y]\x9c'

The CircuitPython ^ (xor) operator applies the key to the plaintext and is a classic final step for stream ciphers to create the ciphertext. This creates the more subtle problem raised previously as it makes discovering a new alternative key for a different plaintext trivial and very fast. This alternative key can be given to an opponent who will decrypt the message producing a plaintext which is different to the original one.

An example is shown below where the player has chosen rock and sent the encrypted rock but the player can then send an alternative key to convince an opponent that paper was their choice.

Download: file
>>> desiredpt = "paper...".encode("ascii")
>>> newkey = bytes([dpt ^ ct for dpt, ct in zip(desiredpt, ciphertext)])
>>> newkey
b'\xf2o\x97\x91\x91Ws\xb2'
>>> bytes([ct ^ k for ct, k in zip(ciphertext, key)])
b'rock....'
>>> bytes([ct ^ nk for ct, nk in zip(ciphertext, newkey)])
b'paper...'
circuitpython_The_Triumph_of_Death_by_Pieter_Bruegel_the_Elder-43whitelb.jpg
“We Rolled Our Own Crypto” from Classic Programmer Paintings. Also known as The Triumph of Death (1562-1563) by Pieter Bruegel the Elder.

Fifth Idea

The one-time pad cannot be used with this simple protocol for the aforementioned reason. An essential property for all other encryption algorithms is the key cannot be selected or found easily to provide a chosen output for encryption or decryption. Hence, one of the common algorithms is likely to solve this issue.

AES (Rijndael) is a modern, widely-used block cipher but it is not currently offered by the standard CircuitPython libraries. Its block size is 128bit (16 bytes) which is a little coarse for direct use with short messages. The Chacha20 stream cipher is easy to implement in Python and was selected for this program. Its key length was shortened as this is just for fun. A short key makes a system vulnerable to brute-force attacks.

The number of flaws quickly found here shows how mistakes can easily be made with cryptography. A slightly more complex and more robust protocol for doing this can be found in the Simultaneous Exchange of Secrets section of Bruce Schneier's Applied Cryptography.

Applications using encryption need to use well-known, mature protocols, high-quality libraries, have a thorough implementation review by experts and be operated as prescribed to achieve good security.

Identity and Authentication

For a game over Bluetooth, the players can be identified by the network (MAC) hardware address if the address privacy feature is not in use or by a Bluetooth name. The issue of player and message authentication has not been covered. For a rock, paper, scissors game outside of a formal competition this seems reasonable!

Bluetooth Low Energy (BLE) typically has limited range, often around 5-10m (16-33ft) which can be perceived as a privacy feature. The range can be far higher with sensitive receivers or powerful transmitters. Exploring Bluetooth 5 - Going the Distance cites an example of 350m (1150ft) range for BLE!

This guide was first published on Sep 02, 2020. It was last updated on Sep 02, 2020.

This page (Exchanging Choices) was last updated on Sep 02, 2020.