Low Tech Crypto: Solitaire (2020) | Hacker News Reader

Low Tech Crypto: Solitaire (2020)

alicegg.tech

77 pointszer0tonin15 comments

>Solitaire (...) was featured in Neal Stephenson’s book Cryptonomicon under the name “Pontifex”.

It was introduced under the name "Solitaire", "Pontifex" was used initially as a temporary code-word when characters couldn't speak freely.

I've always wondered if just using plain RC4 (adapted to a card deck) would be simpler (and probably more secure). Adding two-digit (0..52) numbers by hand is easy for almost everyone, and RC4's swap step is no more involved than the `cut` operation of Solitaire. The only downside is that it requires user to keep track of `i` and `j` - two additional two-digit numbers (in memory, because writing anything down is against the threat model of characters in the story). I agree it's error-prone. But, assuming temporarily writing things down with pen and paper is OK according to my threat model, I think RC4 would work nicely.

Of course Bruce is the world-class expert in cryptography and I'm not, so you should probably ignore my grumbling here :).

There is variant of rc4 called lc4/elsiefour that is intended for computing by hand: https://news.ycombinator.com/item?id=16586257

Found a further variant using deck of cards: https://gitea.blesmrt.net/exa/ls47#alternative-board-with-pl...

This article notes that the algorithm "leaks information at a rate of 0.0005 bits per character" and as such it's fine for encrypting a tweet but not a novel. Can someone with a better understanding of cryptography put 0.0005 bits per character in context? Maybe suggest a practical upper limit to its usefulness that's more specific? More than 140 characters but less than a whole book leaves a lot of wiggle room.

edit: To be clear I mean someone with a better understanding of cryptography than me. I don't doubt the author's expertise.

Leaking 0.0005 bits/character means that you leak a full bit after 2000 characters. This may already be a problem - for example if you know the (2000 characters long) message starts with either "Victory" or "We lost", you can use the information leak to make an educated guess which one it is (with significant, but not 100%, certainty).

A better motivated and more precise example comes from the linked paper itself:

>As another example, suppose a suspected dissident is accused of leaking a government document using Solitaire and that the document is 10,000 characters. In their defence the suspect produces an innocuous document of the same length. A cryptographic expert witness could derive the key stream under each claim and count the repeats. The causal case would be expected to have about 444 repeats in the key stream and the non-causal around 385. The difference of 60 would represent more than 2 standard deviations, which may constitute reasonable doubt dependent on the legal system and the member of the judiciary

One of the interesting parts of this is the key exchange. Handing off a deck of cards works - but that's not always practical.

Fortunately, many major newspapers distribute keys each day.

https://www.mercurynews.com/2023/09/24/bridge-sept-24-2023/

                 NORTH
                 S A 6 3
                 H Q 2
                 D Q 10 8 7 4 2
                 C K 5

    WEST                        EAST

    S 7                         S J 10 9 2
    H J 10 9 8 5                H K 7 6 4 3
    D A J 6 3                   D K 9
    C J 10 8                    C A 9

                 SOUTH

                S K Q 8 5 4
                H A
                D 5
                C Q 7 6 4 3 2

And there are so many to chose from https://vineyardgazette.com/news/2021/09/20/bridge-column-se...

These bridge hand examples always format the hands by grouping suits and sorting the values. Would this impact the security of the key? I assume you’d need a randomly shuffled key to prevent leaking anything.

Correct. This is to solve a different problem associated with Solitaire - keeping our keys in sync.

With Solitaire, if I miss a message that you sent, my decipher deck is now out of sync until we resynchronize somehow.

With bridge columns as the approach, each day the message has a different key that is kept in sync through the bridge columns. Missing a message doesn't result in desync.

Yes, this has low entropy compared to a shuffled deck of cards... and if someone can find out what the system used to generate the key is, it's all decrypted (I'm sure that various Three Letter Agencies are saving every bridge column that's been written).

This solves a problem that two people (or more! because that gets complicated too) may have in using Solitaire. If I were to use Solitaire with this means of key exchange, this would be something that would be low importance and temporal in nature where it doesn't matter if it is decrypted next week.

For example, during WWII Four Square was used ( https://en.wikipedia.org/wiki/Four-square_cipher ) and remains part of basic cryptanalysis in the US Military - https://archive.org/details/Fm3440.2BasicCryptAnalysis - even though stronger cryptography was available. It was usable by in the field to send encoded messages that needed to be sent now (without lengthy encrypt / decrypt processes) for information that had little to no value in the future.

It does remove a lot of entropy. The number of distinct bridge deals is 5 x 10^28 (source https://jlmartin.ku.edu/~jlmartin/bridge/basics.pdf ). log2 of that is under 96 bits, which does seem small by today's standards of cryptography.

As an aside modern bridge dealing machines/algorithms generate a 96 bit random number and do a one-to-one map to a particular deal (ie not doing lots of random calls and moving cards with a Fisher Yates shuffle, say).

My favorite low-tech cipher(e.g. if I ever have to encrypt something by hand) is Quagmire III[0], notably used to encrypt sections K1 and K2 of Kryptos[1].

[0]: https://www.cryptogram.org/downloads/aca.info/ciphers/Quagmi... [1]: https://en.wikipedia.org/wiki/Kryptos

That's interesting - it looks to be a variation on the Vigenère square and the tabula recta... though instead of one key that is repeated (HIGHWAYHIGHWAY...) it also shuffles the alphabet used with another key... and has the possibility of shifting the position of that within the shuffled alphabet... though I'm not sure if that gains anything significant (instead of HIGHWAYHIGHWAY it becomes JLHJXUZJLHJXUZ which is a shift of one column and most letters are a shift of one except A -> U because that's the key shuffled alphabet).

https://sites.google.com/site/cryptocrackprogram/user-guide/...

https://crypto.stackexchange.com/questions/35232/how-to-brea...

https://eprint.iacr.org/2022/1475.pdf

It's gonna be added to my "things to play with when nothing else is pending."

Weakness discussed here https://arxiv.org/abs/1909.06300

Shiu's paper is a nice improvement over Crowley's findings (here: http://www.ciphergoth.org/crypto/solitaire/).

I've taught folks to use this cipher, then showed them Crowley's analysis. It's a good exercise that provides a taste of the sort of cryptanalysis found in real-world ciphers and other cryptographic primitives. It's much more difficult for folks without the background to understand reduced round attacks in AES -- since that does require some understanding of key scheduling in the cipher -- but after physically manipulating those cards, then doing some statistical reasoning to reproduce the results of this paper, it's relatively easy to visualize some of these weaknesses.

That's definitely a good primer for getting folks to think carefully when choosing and using cryptographic primitives when designing protocols. That can be a subtly difficult challenge.

As a budding crypto hobbyist, any good books or daily/weekly challenges that would hit the same spot as everything you posted?

In the age of mobile devices littered with sensors, randomness is far more achievable.

I made a random number generator in Automate that takes takes the end digits that are really just noise and put that into a random seed.

Reply on news.ycombinator.com