1. 27
  1. 3

    I like the further ideas at the end of the article (and the idea itself).

    One simple way to get around the problem of avoiding checkmate could be to just play multiple rounds and consider it a best-of-k. Something like this: Reserve a not-so-good move for “message complete” marker, consider all the good moves for real message data and when one game is over just continue with the message where you stopped last. When a message is finished, perform one bad move (“by accident”) to set the “message complete” marker and then just continue playing until best-of-k is over.

    Not sure if it will work, just an idea. I never did any cryptography or steganography stuff.

    1. 4

      Thanks! (I made this).

      As it happens I’ve already done the ideas about making a “one-sided mode” and an “avoid blunders” mode, they’re available on here: https://incoherency.co.uk/chess-steg/

      Best-of-k would definitely work! You don’t even need to reserve a bad move to indicate end-of-message, you can just resign at the end. A checkmate or stalemate would mean “continue to the next game”, and resignation would mean “end of message”. This comes with the extra obligation to encode some information about where the next game is, or what order the games are to be consumed in, but it’s definitely possible.

    2. 2

      This post is great thank you.

      I wonder, since legal moves are always sorted in the same canonical order, whether this makes it too easy to spot messages. Moreover if you’re trying the one-sided approach and playing multiple games trying to reach a desired game length you’d always play the same starting moves, making it easier to spot on Lichess someone using this steganographic method.

      I wonder - if a symmetric key is used to created some key-and-move-number-dependent permutation of legal moves, is this good enough to hide and prevent being spotted in the one-sides scenario?

      Just an idle thought! I think an interesting next step is to pretend to be an attacker and ask “Hey is this PGN hiding a message?”.

      1. 2

        you’d always play the same starting moves, making it easier to spot on Lichess someone using this steganographic method.

        This wouldn’t be as easy to find as you might think, because almost everyone tries to play the same opening every time anyway. Furthermore, the games would diverge as soon as your opponent plays a different move.

        I don’t think I quite follow your idea about the symmetric key. If you use the same key each time wouldn’t that still result in the same moves generated in the same positions? And if you don’t use the same key each time how are you going to communicate the key?

        You could potentially encrypt your message with a short key and include the bytes for the key at the start of the bytes for your ciphertext, and then encode that with chess-steg, and you could do that with the current system with no changes (modulo difficulties copy-pasting binary data into the browser).

        To answer “Hey is this PGN hiding a message?”, I would do this:

        1. You can start by looking at how the game ended. If it is anything other than a resignation then the game was not generated with chess-steg.
        2. Next, try to decode the PGN using chess-steg for each combination of (one-sided, two-sided) and (with-blunders, without-blunders). (For one-sided mode you know that the message will be from the side that resigned).
        3. If bignum2data() bails at the decode_utf8() step[1] then it means the original message was not encoded with utf8, which means it wasn’t created with chess-steg.
        4. Augment bignum2data() with something that checks what the value of “n” is after the while loop ends: if it’s anything other than 1 then it wasn’t created with chess-steg.
        5. If you passed all the previous checks, meaning you have successfully used chess-steg to decode the chess game into bytes (pretty unlikely for arbitrary inputs, I would guess!) then you can do some simple automated checks like check to see if they’re all ASCII characters.
        6. Failing that, pass it on for manual classification. If manual classification identifies a new type of encoding being used, add it to the automated checks.

        If people are using the same kind of idea, but not directly using chess-steg (e.g. they sort the moves differently, or more complex changes) then you have more work to do :).

        [1] https://github.com/jes/chess-steg/blob/master/js/chess-steg.js#L22

        1. 1

          This wouldn’t be as easy to find as you might think, because almost everyone tries to play the same opening every time anyway. Furthermore, the games would diverge as soon as your opponent plays a different move.

          I tried “Attack at dawn” as the input and get the first move as “a4”, which is not a common opening move. But I understand why this is happening.

          I don’t think I quite follow your idea about the symmetric key. If you use the same key each time wouldn’t that still result in the same moves generated in the same positions? And if you don’t use the same key each time how are you going to communicate the key?

          You are right, using a symmetric key does not help make the resulting game look different for a given message, and you have the additional problem of communicating it to the other person.

          Also I understand how you would reverse this process. I think it’s great that I keep asking myself more and more questions, like “How frequent are false-positives, i.e. for a given message if you search the last year of Lichess games how many other games match the message. And I wonder what the tradecraft would look like for two people to communicate to each other.

          Great post, thanks for replying!

      2. 2

        Ooooh I like this idea! Wonder how many layers of chess-pgn you can place on top of each other

        1. 1

          Very cool, noticed the hello world example does not reflect human play however. I wonder about strategies that would include both a realistic game play plus a hidden message.