[HN Gopher] Low Tech Crypto: Solitaire (2020)
___________________________________________________________________
Low Tech Crypto: Solitaire (2020)
Author : zer0tonin
Score : 64 points
Date : 2023-09-24 13:24 UTC (9 hours ago)
(HTM) web link (alicegg.tech)
(TXT) w3m dump (alicegg.tech)
| msm_ wrote:
| >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 :).
| zokier wrote:
| 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...
| shagie wrote:
| 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...
| news_to_me wrote:
| 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.
| vikingerik wrote:
| 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.
| vmilner wrote:
| 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).
| shagie wrote:
| 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.
| d-z-m wrote:
| 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
| shagie wrote:
| That's interesting - it looks to be a variation on the Vigenere
| 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."
| vmilner wrote:
| Weakness discussed here https://arxiv.org/abs/1909.06300
| nanolith wrote:
| 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.
| rig666 wrote:
| [dead]
| [deleted]
| pikminguy wrote:
| 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.
| msm_ wrote:
| 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
___________________________________________________________________
(page generated 2023-09-24 23:01 UTC)