Encryption for the Lich Queen's spys?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Ciber
Posts: 123
Joined: Fri Mar 15, 2013 1:33 pm UTC

Encryption for the Lich Queen's spys?

Say you are advising this evil lich queen one day and she requests an improved system of encryption as part of her overarching plan to stop all opposition. Now obviously the method you suggest must be possible to compute by hand, but luckily anyone trying to break your code would be similarly limited.

So what would be a good algorithm to use here?

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3549
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Encryption for the Lich Queen's spys?

Something based upon a hand-calculable stream cipher of sufficient robustness, undoubtedly.

(I'm wary to suggest that two disimilar stream ciphers methods run in parallel(/one at a time), and a trivial but additional scheme determining when and when not to jump between the two, might be adding less encrypting complexity than it does in the cracking.. but it does sound like it could be usable with only the same possibility of GIGO errors but obfuscate the methods greatly against hand-analysis...)

Exact algorithm(s) would depend on various factors. Which would obviously also be an issue when those tasked to crack it are trying to get their grip on the configuration they are trying to pull back apart.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Encryption for the Lich Queen's spys?

What does computable by hand mean? AES is computable by hand but requires significant effort. How much ciphertext does one individual have to output per hour? If its just a few bytes then AES will be manageable after some practice and by building a few lookup tables to speed up the process.

Breaking a cipher however will become significantly more difficult. We consider ciphers like DES broken even though actually inverting them requires something like 2^43 known plaintexts. Processing that much data is possible using a cluster of computers (or better ASICs) but even if all humans that ever lived spent their entire lives on decrypting DES manually (using today's best known methods) they would not have produced more than a few kilobytes of data.

Flumble
Yes Man
Posts: 2044
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Encryption for the Lich Queen's spys?

Ciber wrote:Say you are advising this evil lich queen one day and she requests an improved system of encryption as part of her overarching plan to stop all opposition.

In what scenario would spies need better encryption rather than steganography? I thought spying was all about passing information unbeknownst to the target, not unreadable.

Anyway, I'll link this topic has some discussion on securing two-party communication under heavy surveillance.

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Encryption for the Lich Queen's spys?

The question itself seems legit though. What if I send love-letters to my boy, but am afraid of anyone else reading them? What kind of encryption method that he can do by hand would be advisable?
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3549
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Encryption for the Lich Queen's spys?

Encoding:
Let Plaintext be "I love you".
Let Codetext be getRandomNumber(Plaintext).

Decoding:
sub Decode(Codetext) {
If Code == 4 then return "I love you." // should be sufficient...
}

ucim
Posts: 6476
Joined: Fri Sep 28, 2012 3:23 pm UTC

Re: Encryption for the Lich Queen's spys?

Soupspoon wrote:Encoding:
Let Plaintext be "I love you".
Let Codetext be getRandomNumber(Plaintext).

Decoding:
sub Decode(Codetext) {
If Code == 4 then return "I love you." // should be sufficient...
}
Alas, Code is undefined. Is this the true source of computerized emo poetry?

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

cphite
Posts: 1275
Joined: Wed Mar 30, 2011 5:27 pm UTC

Re: Encryption for the Lich Queen's spys?

Xanthir
My HERO!!!
Posts: 5319
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Re: Encryption for the Lich Queen's spys?

I'll leave it to you to look up the details, but Cryptonomicon describes a pretty decent encryption algorithm implemented with modular addition and a pack of cards. It does require some form of coordination to allow the sender and receiver to agree on the deck setup before starting; in the book, it's suggested you use something like information from a newspaper.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

mok-kong shen
Posts: 15
Joined: Mon Oct 31, 2016 10:19 am UTC

Re: Encryption for the Lich Queen's spys?

Applications of classical crypto schemes IMHO could be rendered arbitrarily strong, if one suitably employs multiple encryption ("super-encryption"), i.e. appropriately combining diverse classical schemes as constituents (including their multiple usages, in general with different keys, advantageously alternating between substitution and transposition) of a big scheme and if there is enough entropy in the entire key materials. However, due to the increased complexity there is more work to be done in encryption/decryption processing and one has to be more vigilant to avoid eventually possible operator errors. (This is in conformity to the Principle of No Free Lunch.) I would suggest to use the following constituents: (1) Disrupted columnar transposition (cf. Ratschluessel 44), (2) Playfair, (3) Polyalphabetical substitution with pseudo-random ("mixed") alphabets, (4) Fractionation (cf. Polybius Square) and (5) homophonic encryption schemes. See Wiki articles and other literatures on the Internet.

duodecimus
Posts: 36
Joined: Tue May 19, 2015 12:25 pm UTC

Re: Encryption for the Lich Queen's spys?

I may be reading too far into the setting, but:
The lich queen probably exists in a realm of fantasy. We should consider magical means of foiling encryption.

Whatever system probably has to be memorize-able as any code book would be possible to scry and be far more prone to being stolen than in mundane lands.

In addition you'd have to consider other, more esoteric angles. Magic systems often have a 'like calls to like' or a 'part is the whole' system, ex: tracking someone with a bit of their blood or voodoo effigies. If you were using some basic letter replacement code that allows certain quick ins (such as identifying A and I from words like I, a, at, It) do you run the risk of the message spontaneously arising from a partial break?

Also, I haven't seen very many magic systems that don't simply have a comprehend languages spell. Should this exist in your setting you may have better success with a Thieves Cant style code, where you weave a message into an apparently normal conversation. Perhaps your people have a 'weird accent' that is actually a tonal language separate from the words being spoken.

Ciber
Posts: 123
Joined: Fri Mar 15, 2013 1:33 pm UTC

Re: Encryption for the Lich Queen's spys?

Sadly quest was ended bc too much work for author. Search for "What can sb teach an evil queen" on spacebattles. Author really put some work into it.

duodecimus
Posts: 36
Joined: Tue May 19, 2015 12:25 pm UTC

Re: Encryption for the Lich Queen's spys?

Internetmeme
Posts: 1405
Joined: Fri Jul 25, 2008 3:16 pm UTC
Location: South Carolina, USA

Re: Encryption for the Lich Queen's spys?

With the assumption that our spies are pretty loyal and that any rebels don't have access to any significant computational power, the Enigma Machine is actually probably a great solution here. Plus, because it's ultimately just a series of changing substitution cyphers with rules on how to use the output from one as the input of another, it's relatively easy to implement by hand compared to modern methods of encryption. Encryption is also easily reversible for the spies; running a decrypted message through the machine will encrypt it, and running the same encrypted message through the machine will decrypt it (so long as you use the same initial settings).

The main ways that you can crack an enigma machine are either:
1) Brute force. Which can potentially take a long time to decrypt. The final uncracked Enigma messages weren't solved until 2013.
2) Guessing what strings the message is likely to contain. This is how the allies managed to crack most of the Enigma messages. A large number of enigma messages began with the same phrase, which allowed them to figure out what the encryption scheme for the day was.

So, as long as our spies are loyal, and we prevent ourselves from making it easy for the rebels to guess, the machine would be more than adequate. Plus, depending on how high-fantasy our setting is, this is something that we could potentially have a machinist produce. Alternatively, you can make a simpler one out of a paper tube
Spoiler:

wumpus
Posts: 532
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: Encryption for the Lich Queen's spys?

Flumble wrote:
Ciber wrote:Say you are advising this evil lich queen one day and she requests an improved system of encryption as part of her overarching plan to stop all opposition.

In what scenario would spies need better encryption rather than steganography? I thought spying was all about passing information unbeknownst to the target, not unreadable.

Anyway, I'll link this topic has some discussion on securing two-party communication under heavy surveillance.

I'm fairly sure that such a system exists entirely for steganography. In Dungeons & Dragons for example, a [arcane casting] lich can simply cast a spell [magic mouth] that transmits a 25 word message when given a specific code word. Presumably such a spell makes an ideal cipher (it can't be broken), but fails as steganography (it can easily be detected by a "detect magic" spell). While the spell can be destroyed/dispelled (note that this is profoundly difficult if the lich queen cast it herself, and expensive even if an apprentice managed to cast it), I doubt that breaking the spell is possible.

While there don't appear to be means of direct breaking of ciphers in standard D&D spell lists, contacting devils or modrons for assistance is certainly possible. Also use of golems for computation is unexplored, but any player/DM of an engineering bent should see multiple ways to use golems for computation (and thus encryption and cryptanalysis).

Don't forget the use of divination, scrying, and using modern technology tricks via magic. While it is essentially impossible to break a well encrypted message with a truly random key, it is often quite trivial to compromise the computer used to encrypt or decrypt it. An obvious good way to find the message is to scry/bug (possibly literally with a polymorphed minion) the message when it is sent/received. [Note: assume reasonable permanent spells for preventing scrying/teleportation is strictly necessary to allow the existence of nearly any 'traditional' fantasy society. Don't assume that any spell not needed to slay dragons in dungeons isn't available to court wizards, these spells are crucial]. Divination is a huge danger to steganographic messages, and the use of such tricks largely depends on how available such spells are. I'd have to assume that magically hiding such messages (so divination wouldn't find them) wouldn't be much different then masking the aura of a magic mouth, but that's just me. If the world "works better" with a "hide from divination" spell, add it).

There is an old story about a king that wrote a message on a slaves shaved head, waited for the hair to regrow, then sent him as a message. When he got to the right kingdom, the other king shaved his head and read the message. Presumably a lich queen could cast two magical disguises on a minion: one with the message written on them and a second one to cover it up. It brute force dispelling the disguise was used, it would remove the "message disguise" as well. Minions used wouldn't be literate, so there is no way to get the message out of them once the spells were removed.

duodecimus
Posts: 36
Joined: Tue May 19, 2015 12:25 pm UTC

Re: Encryption for the Lich Queen's spys?

DnD rules don't have any spells for it because Decipher Scriptis just a skill check.

So basically it's unsupported by magic, beyond stacking Int bonuses. As a DM I'd probably have the creator take 20 on making it to set the DC, then give a cracker one check per workday or something, with reductions based on the crafting rules.

wumpus
Posts: 532
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: Encryption for the Lich Queen's spys?

duodecimus wrote:DnD rules don't have any spells for it because Decipher Scriptis just a skill check.

So basically it's unsupported by magic, beyond stacking Int bonuses. As a DM I'd probably have the creator take 20 on making it to set the DC, then give a cracker one check per workday or something, with reductions based on the crafting rules.

If you can use "contact other plane" to hit anything like the "Traveller Universe" (or better yet, Shadowrun), you have pretty much cracked any encryption scheme. If not, a summoned/gated modron would probably be your best bet (let it do the crafting rules with some huge bonuses for int, math, and concentration abilities).

I think the failure of D&D (possibly just 3e) to attach any real meaning (at least none that I've seen) to the "impossibly" high levels of intelligence that both the Lich Queen (assuming once a wizard, all bets are off for any other caster) and any wizard attempting to attack the encryption will be a problem.

duodecimus
Posts: 36
Joined: Tue May 19, 2015 12:25 pm UTC

Re: Encryption for the Lich Queen's spys?

Yup. Encryption gets difficult when anybody can just buy some time with a super computer.

Do you suppose kingdoms just keep an abyssal on retainer for this sort of thing?

Ciber
Posts: 123
Joined: Fri Mar 15, 2013 1:33 pm UTC

Re: Encryption for the Lich Queen's spys?

The setting in question had magic, but not DnD style. And entire nation was brought low by a manufactured plague of zombie badgers delivered by catapult though if I recall correctly...