Contest: Cory Doctorow's Cipher Wheel Rings

Cory Doctorow wanted a secret decoder wedding ring, and he asked me to help design it. I wanted something more than the standard secret decoder ring, so this is what I asked for: "I want each wheel to be the alphabet, with each letter having either a dot above, a dot below, or no dot at all. The first wheel should have alternating above, none, below. The second wheel should be the repeating sequence of above, above, none, none, below, below. The third wheel should be the repeating sequence of above, above, above, none, none, none, below, below, below." (I know it sounds confusing, but here's a chart.)

So that's what he asked for, and that's what he got. And now it's time to create some cryptographic applications for the rings. Cory and I are holding an open contest for the cleverest application.

I don't think we can invent any encryption algorithms that will survive computer analysis -- there's just not enough entropy in the system -- but we can come up with some clever pencil-and-paper ciphers that will serve them well if they're ever stuck back in time. And there are certainly other cryptographic uses for the rings.

Here's a way to use the rings as a password mnemonic: First, choose a two-letter key. Align the three wheels according to the key. For example, if the key is "EB" for eBay, align the three wheels AEB. Take the common password "PASSWORD" and encrypt it. For each letter, find it on the top wheel. Count one letter to the left if there is a dot over the letter, and one letter to the right if there is a dot under it. Take that new letter and look at the letter below it (in the middle wheel). Count two letters to the left if there is a dot over it, and two letters to the right if there is a dot under it. Take that new letter (in the middle wheel), and look at the letter below it (in the lower wheel). Count three letters to the left if there is a dot over it, and three letters to the right if there is a dot under it. That's your encrypted letter. Do that with every letter to get your password.

"PASSWORD" and the key "EB" becomes "NXPPVVOF."

It's not very good; can anyone see why? (Ignore for now whether or not publishing this on a blog makes it no longer secure.)

How can I do that better? What else can we do with the rings? Can we incorporate other elements -- a deck of playing cards as in Solitaire, different-sized coins to make the system more secure?

Post your contest entries as comments to Cory's blog post -- you can post them here, but they're not going to count as contest submissions -- or send them to cryptocontest@craphound.com. Deadline is October 1st.

Good luck, and have fun with this.

Posted on September 5, 2008 at 12:01 PM • 60 Comments

Comments

Angel oneSeptember 5, 2008 12:58 PM

Bruce - with your proposed system, how can you decrypt it? At any given initial setting, multiple letters can be encrypted to form the same resultant letter. Because of this, when given the encoded message, any given letter could have been several different plaintext letters.

If anyone wants an example, just look at E, F, and G on the second wheel. The E pushes you right to the F, and the G pushes you left to the F.

To clarify, does this ring have to do encryption and decryption, or just hash?

rplSeptember 5, 2008 1:03 PM

I'll take a stab at the question of why the password scheme is not very good, bearing in mind that my background in crypto is limited to what I've read on this blog.

If you're going to use common words "encrypted" with the method described as passwords, then it seems to me that in terms of resisting a dictionary attack, the system little better than just appending two letters onto the dictionary word. To wit, both variants turn each dictionary word into 26*26 = 676 words. It doesn't seem like this would be too much harder to crack than the un-"encrypted" dictionary words.

Am I close?

Et tu, Bruce?September 5, 2008 1:12 PM

Cory Doctorow?

Next on the list is Rachel Ray asking you to demonstrate making polenta.

QuercusSeptember 5, 2008 1:14 PM

A quick thought is that if, as Angel One says, different plaintext password letters can get mapped to the same ciphertext password, then you've just made brute force attacks much easier (assuming the algorithm is known to the attacker; this is not necessarily true for a lot of real-world attacks).
At some level of technology, it's probably worth giving up some brute-force defense to get dictionary attack defense. I think we're still at that level, aren't we?

dmcSeptember 5, 2008 1:15 PM

And I thought my wedding ring with its DNA intercalated with the logical or symbol (V) motif was geeky :-)

Dave AronsonSeptember 5, 2008 1:16 PM

At first glance, this looks like a simple substitution cypher, albeit with (as Angel One pointed out), possibly some many-to-one mappings, making decryption somewhat guessy. The action of the rings serves only to create the mapping.

Fred PSeptember 5, 2008 1:17 PM

Your question seems silly:

You're using a non-variant key, so later letters of the same type encrypt to the same letter. This makes this very weak towards frequency analysis. A solution is to move one or more rings.

Adam VSeptember 5, 2008 1:43 PM

Following Fred P's advice:

Why not, instead of a single two-letter key, use the first two letters from the first chapter of an accepted text (Lord of the Rings, for example), then the next two, etc.? That way, the key rotates and the same letters in the plaintext phrase map to a different encrypted phrase.

If that's not good enough (cops will confiscate your books and try the first few words of each chapter to see if it's the right book), then you could memorize a shared phrase of some variable length. When you get to the end, just loop back to the beginning. (Better if it's an odd number of letters, in that case.)

Marty LambSeptember 5, 2008 1:57 PM

Here's an approach using only the rings, in case you are sent to a time in the past that predates any external dependencies (books, cards, etc.):

Agree on an arrangement of the rings to serve as a key (your spouse's initials, some secret, whatever).

To encrypt your message:

1. Find the plaintext letter on ring 1 (L1).
2. Scan across to the corresponding letter on ring 2 (L2).
3. Find *that* letter on ring 1.
4. Scan across to the corresponding letter on ring 3 (L3). This is your ciphertext letter.
5. For each of the rings, if there is a dot above or below its corresponding letter (L1, L2, or L3), rotate the ring one letter in that direction.


To decrypt your message:

1. Find the ciphertext letter on ring 3 (L3).
2. Scan across to the corresponding letter on ring 1.
3. Find *that* letter on ring 2 (L2).
4. Scan across to the corresponding letter on ring 1 (L1). This is your plaintext letter.
5. Same as #5 above.

You could also play with different rotation rules, e.g., rotate the first ring by *one* position, the second ring by two, and the third ring by three each time you rotate them.

StevenSeptember 5, 2008 2:11 PM

It seems like the problem with the password mnemonic is that if they get your password for one site, plus a reasonable guess for the site key, then they can back it out to PASSWORD, and then with reasonable guesses for other site keys, they get your passwords for other sites.

And the site keys do need to be guessable, or else the whole system isn't very mnemonic.

The reason we need mnemonics in the first place is that we have lots of different passwords, and the reason we have lots of different passwords is so that a compromise on one account doesn't compromise other accounts.

Davi OttenheimerSeptember 5, 2008 2:21 PM

"What else can we do with the rings?"

lame. i think you're missing the point entirely of a wedding ring.

if you have to stretch your mind to figure out a purpose...then you probably should not pretend that it is a wedding ring to start with.

Clive RobinsonSeptember 5, 2008 2:33 PM

@ Nicholas Weaver,

"I wonder if its possible to make a full rotor-machine in a manual form?"

Easily you just need to either use a series of ring within a ring pairs, or be a reliable counter.

You can quite accuratly simulate an Enigma with a number of strips of paper. In fact the very early system (pre German manufacture) was attacked quite successfully with just this method. If I remember correctly it was called the "method of battons" or "method of cliques". An Internet search will no doubt bring it up.

Jed DavisSeptember 5, 2008 3:03 PM

This would work better if it were letters and numbers; then the period-18 pattern of dots would repeat exactly twice on the 36-symbol ring.

Angel oneSeptember 5, 2008 3:06 PM

In response to me previous post, I misread Bruce's instructions, and the problem is actually far smaller than I thought. I was only moving 1 space to the left or right on each ring - I didn't notice that he had said to jump 2 spaces on the second ring, and 3 on the third. If you look at any "cycle" of letters (like, say C-E on top, or D-L on the bottom), you'll see that each "cycle" is just a simple substitution.

The problem is, the alphabet has 26 letters, and 26 is not an even multiple of 3, 6 or 9 (the size of the "cycles" on the three rings). The first ring for example will never yield an A, but will map Z twice as often as any other letter (assuming perfect entropy coming in).

The problem occurs in the other rings too. Take the second ring - because A and B (with dots on top) are next to Y and Z (also dots on top), Y and Z are more likely to be results than any other letter, and A and B can never result. (Both W+X yield Y+Z, and A+B also yield Y+Z). The same problem happens with the third ring as well.

This yields several problems:
1 - The letter 'A' will not be in your final ciphertext no matter what the key and plaintext. This makes brute force easier. (Thanks Quercus for pointing out the obvious to me)
2 - depending on the key used, other letters will also not appear (because they were "lost" in the upper rings).
3 - the letter 'X' will appear twice as often as other letters (assuming perfect entropy coming in).
4 - Other letters (depending on the key) will also appear with twice the frequency because they were "doubled" by an upper ring.
5 - This is really just a convoluted substitution cipher. Without permutations, it is vulnerable to statistical analysis and all the other attacks we know exist against substitution ciphers.
6 - Because none of the rings have perfect entropy on their own, (and issues 1-4 above), given enough ciphertext you could possibly deduce the key used based on which letters appear too often and which never do.

AnonyMouseSeptember 5, 2008 3:27 PM

Here's a variation on Bruce's encryption scheme using the ring.

Initialize the ring according to Bruce's suggestion, the first three letters, or some mnemonic, of/for the site you want to hash a password (or anything else) for.

Follow the same procedure from here on out, except after encoding each letter, rotate one or more of the rings a certain number of positions (counter)clockwise. This could be a "shared secret" between two parties.

Also, no spaces between words.

I'm not a cryptographer, so I apologize if I'm missing something.

whelSeptember 5, 2008 3:34 PM

kenan: I get NXPPVOWY... first 5 matched, so I must be misunderstanding something! :-p

Let's see... the O on top row has a dot under, so move one to the right to P. Middle row has E under the A in top row (i.e. four to the right), so P from row 1 drops down to T in row 2. T has a dot over, so move two to the left to R. Bottom row has B under the E in middle row (three to the left) so R from row 2 drops down to O in row 3. No dot, so keep that. Bruce has a V. hmmmmm

Clive RobinsonSeptember 5, 2008 4:02 PM

@ Bruce,

Correct me if I am wrong but,

the last time you designed a "simple" crypto system ( Solitaire) for an author I vaguely remembered it showed some bias in it's output?

Onto the ring, why did you not make the ring size odd preferably prime with a simple nulls such as numbers or other ASCII symbols for instance.

Further your "dot sequences" are the first multiples of 3 of which only the first is prime (ANB,AANNBB,AAANNNBBB).

This just does not feel right for a whole bunch of reasons.

As for a way to use it you could use it like a Jefferson system.

First agree a private key of dot patterns (there are many ways to do this including using a book).

Set the first three letters of your plain text up and then look around the ring to find the set of letters that match your dot pattern and send that.

For this simple case the dot pattern acts as a sort of check sum.

Now to make it more fun and put a private channel into the system. A valid tripplet matches the private key a null tripplet (meaningless random fill does not). In this way you can pad the real cipher text with meaningless junk (and have a similar effect as having more entropy in the system.

And you could build the system up further. Let us assume that you select any triplet to send, and that only the dot pattern of the last char has meaning such as A=dot, N=space, B=dash, then you could use the tripplets to send morse code.

Obviously that simple corespondence on the last letter of the triplet would become obvious in a message of more than a couple of charecters so a more complex method would be needed (I'll leave that as an excersize for the for the reader).

Further using the same wheel position repeatedly would likewise become obvious, so how about using a book and starting at an agreed place use the text of the book to set the ground wheel setting of each tripplet in turn.

Further how about pre-encoding the plaintext to reduce it's chi. A simple to remember system is to first remember "EAT ON IRISH LID" (which is a close aproximation to the order of the most frequent used letters in English).

Then (using the book) order them as they occur in an agreed sentance. The first eight then corespond to the numbers 0,1,2,3,4,5,6,7. Then again from the agreed text order the other 18 letters of the alphabet from 81-89,91-99. Write the numbers down under the plaintext to cive the encodedtext. Then either send the numbers using an agreed code. Or if using morse code using a second agreed sentance write down the first occurance of each letter in "EAT ON IRISH LID" as they occure and assign them the numbers 0-9 and send the letters that coresponed to each number in the encodedtext. The result of this encoding is to make the resulting encoded text have a much flater frequency distrubution which for short messages might make an evesdroper think you are using a numeric one time pad.

I can think up a whole load more wrinkles but hey I'm not an author ;)

PaulSeptember 5, 2008 4:56 PM

As a couple others have pointed out, one of the more glaring faults is that the the alphabet does not divide evenly into the size of the cycles on the rings, so there is guaranteed to be bias. However, it's not as bad as some have stated.

@Angel one
"1 - The letter 'A' will not be in your final ciphertext no matter what the key and plaintext. This makes brute force easier. (Thanks Quercus for pointing out the obvious to me)"

That's actually not true. With a key "AB', the plaintext letter "Z" will become the ciphertext letter "A".

A quick simulator over the keyspace "AA" - "ZZ" and plaintext characters 'A'-'Z' found the following frequency distribution:

586: V
612: D,F
658: Y
668: B,C
676: G,H,I,J,K,L,M,N,O,P,Q,R,S,T,Z
684: A
694: X
740: E
748: W
766: U

The biases are actually a good bit smaller than I was expecting. Of course, it's only suitable for a hash, as information is always lost (no key pair results in a 1:1 mapping between plaintext and ciphertext, and since plaintext and ciphertext share alphabets exactly that means data is lost).

StevenSeptember 5, 2008 8:35 PM

With the key 'EB',

PASSWORD -> NXPPVOVY

and the preimages of NXPPVOVY are

P[AZ]SS[RW]O[RW]D

So it's definitely feasible to recover the plaintext from the ciphertext, given the key.

Bruce SchneierSeptember 6, 2008 2:43 AM

"To clarify, does this ring have to do encryption and decryption, or just hash?"

The ring has to sit on a finger and look pretty. The question here is: what else can it do?

Alice Bevan–McGregorSeptember 6, 2008 2:56 AM

My bad, mine can be implemented in two wheels: for each character in the passphrase and text to encode, rotate the top wheel so the current character of the passphrase lines up with A of the second wheel, find the character of the text to encode in the first wheel, and write down the character aligned to it from the second wheel. Increment the passphrase offset and continue.

Yes, I'm a programmer. ¬_¬

periSeptember 6, 2008 5:13 AM

I would have been much more excited about this if the alphabet had something like a dash added to it so it has 27, or 3 cubed, characters and the dot pattern was

R1: 1 x over, 1 x none, 1 x under,
R2: 3 x over, 3 x none, 3 x under and
R3: 9 x over, 9 x none, 9 x under;

with 9 each of over, none and under.

More interestingly, the dot pattern can be interpreted as a base 3 digit; with 3 rings we can read 3 base 3 digits which gives a number in [0,27]. So a bijection would exist between that number and letters in the alphabet.

SteveJSeptember 6, 2008 5:35 AM

The password-generating algorithm Bruce describes above can be strengthened by combining it with another of his recommended password-remembering techniques.

Short version: use this scheme to write obfuscated versions of strong passwords on a piece of paper.

Long version: for each site, generate a random "pre-password", write it down on a piece of paper and keep it in your wallet.

Memorise a two-letter key (again, different for each site), and use it to apply Bruce's original algorithm to the pre-password to get the real password.

To an attacker who somehow gets the pre-password, the real password is still as strong as the two-letter key (which isn't good, but on a site with lock-out might just be good enough as long as you choose keys which aren't trivial to guess). Without the pre-password he has no chance, unlike in the original scheme where the use of the same pre-password for all sites makes it potentially recoverable.

It's still a substitution cipher, but at least frequency analysis is useless when the plaintext is random.

As a further refinement: use longer keys by coding the first letter of the pre-password with the first two letters of the key, the second with the next two. When you run out of key, start again, perhaps having manipulated the key somehow.

@Paul:

Were there any particular keys which produced significantly worse output bias than average?

Actually, I guess the answer is probably "yes", so the real point is that users of this scheme should know what the worst-case is, so that if they think that's too bad they can avoid any spectacularly weak keys. Of course doing so reduces the size of the keyspace, so might actually make the scheme weaker.

periSeptember 6, 2008 5:52 AM

There are only 26 + 676 keys; if it takes less than a minute to decrypt a message then the computing power required to brute force all the keys can be done with 12 intern hours.

periSeptember 6, 2008 5:54 AM

As pointed out by others there is a bias in the dot pattern distribution (+- 1%):

R1: 35% over, 35% none, 30% under.
R2: 38% over, 31% none, 31% under.
R3: 35% over, 35% none, 30% under.

Peter E. RetepSeptember 6, 2008 9:42 AM

Basic Problems are very interesting as prompts to challenge - or at least locate - our assumptions.

Very enjoyable.

Clive RobinsonSeptember 6, 2008 11:08 AM

@ Bruce,

You say,

"You can't; it's simply a way to generate passwords"

When asked,

"how can you decrypt it?"

You sadly underestimate the ring you have designed as you describe it here (for some reason T-Mobile in the U.K. content block your flicker link).

From the words the ring is a very limited version of the jefferson Disk Cipher which I briefly mentioned in my post above in this page. Which means it can be used not just to encrypt but decrypt as well.

For those that don't know the Jefferson Disk Cipher was invented by Thomas Jefferson in the 1790's. Jefferson sadly is more often remembered as a lawyer, one of the Founding Fathers and the 3rd U.S. President not as an inventor (JFK joked about him to the nobel prize winners at the White House in 1963).

The cipher system was one of many inventions by this outstanding polymath due to a number of reasons it lay virtually unknown untill rediscovered be Commandant Etienne Bazeries around 1900. This simple mechanical cipher therefore became known more commanly as the "Bazeries cylinder".

To Jefferson's credit a version of his cipher called the M-94 was used as a field cipher by the United States Army from 1923 until 1942 and by other nations subsiquently. It will be interesting to see if more modern systems remain in service for a century and a half.

A word of warning the Jefferson disk cipher is suceptable to an attack known as the "de Viaris method" it works best if the alphabets on the wheels have been poorly selected. As yours is in alphabetical order...

There are also other attacks the M-138-A (a more advanced paper strip analogue of the Jefferson disk system) was succesfully broken by the Germans during WWII and also messages in depth will fail the kappa test.

All that aside your ring could also be used as a limited stream cipher generator, and without much effort it's hash ability could be used as part of a Horst Feistel round or network to make a block cipher (which would require a lot more effort and be very error prone by hand).

So not only can it hash up a password it can encrypt and decrypt as both a stream and block cipher, so it does the three basic cipher types. Which also means it is amenable for use as a primative in the more complex modes of the basic cipher types.

But further your inclusion of the dots gives rise to it being used with/as a covert or side channel (prisoners dilema etc) which I also mentioned in my post above.

So to be a little more informative,

Alice and Bob need the ring, and depending on what they are doing additionaly an agreed text to and a secret based on the dots.

The secret is an agreed method of using the dots that can be further used to communicate covert information. At it's simplest and only realy suitable for explination it can just be a pattern of Above None or Below (ANB) dots at coincident wheel positions (I shall assume for now that any pattern will always be present without the tedium of checking ;)

As I outlined in my above post this secret dot pattern can be used as a security or duress checksum, covert channel or a method of increasing the entropy of the system when in use, depending on Alice and Bob's ability.

I'm further assuming that Alice and Bob are a bright pair of cookies and also know Samual Morse's or Emile Baudot's codes as well.

1, Use as Jefferson with duress checksum.
Let us assume that the agreed secret is AAN.

When not under duress Alice sets the rings to the first three letters of the plaintext, then looks around the ring for a trigram that has the dot pattern AAN and sends this to Bob.

Bob sets the ring to the trigram he receives and checks it has AAN as the dot pattern he then figures out which of the trigrams are meaningful there are only likley to be a few (the more wheels there are the easier this part is three is a realy to few but is just workable with effort).

If Alice is under duress or the ciphertext gets garbled in transmission then Bob gets something other than AAN as the checksum. He can request a resend of the ciphertext to eliminate transmission garbales

For obvious reasons the dot checksum AAN cannot be used for every trigram if used as a duress indicator but only in prior agreed positions.

2, Jefferson with added entropy (nulls)
As above but agreed secret dot code AAN is used to signify valid trigrams. Alice simply encodes the message and then puts in as many random trigrams that do not match AAN as she feels will suffice at random points in the ciphertext.

3, Jefferson with covert channel (A)
This time the secret dot code allows a binary or trinary baud to be sent with each trigram sent. For real simplicity of explination only the private trinary codes could be for Morse Code AAA=Dot AAB=Dash AAN=space, and for Baudot/ASCII AAA=Mark/one AAB=Space/zero AAN=BRK.

Alice encodes a fake message as for normal Jefferson, however the trigram she selects is used as a single baud for the data in the secret / covert channel.

For obvious reasons the fake message has to be sufficiently real to pass viewing by a prison warden etc.

(My use of baud here is as a unit of transmission with multiple levels, to avoid confusion wit a bit which is normaly reserved as a unit of data usually of only two levels ie a binary bit of data).

4, Jefferson with covert channel (B)
Works in a similar way to method A but instead of using a fake message Alice uses an agread text (book cipher) with Bob.

So to use the system Alice and Bob need to have an agreed text for the day or message the method of selection is left to the reader.

Alice encodes the agread text as per method A but she needs only send one letter from the resulting trigram again for simplicity of explination from the middle ring !!!

This has the advantage of compressing the agread text thus making it much harder to find and also alows the addition of a second hidden channel to be used as a duress indicator.

!!! HEALTH WARNING In reality you need a more complex method of letter selection than given here.

5, Use as a stream cipher
This works the same way as generating letters with the agreed text of method B (same health warning). However instead of randomly selecting a secret dot code match you use the first say clockwise from the ground trigram of the agreed text the letter found is then either XORed or added Mod26 to the plain text.

6, Use as a block cipher
Sorry folks this is a bit long to describe here and would need pictures as well. Also it would be a little difficult to use in practice and very error prone. However if you want to do it have a look at the rounds in DES or FEAL and simplify them not just in the number of rounds but in how you make the round keys and mix them in in a nonlinear way. IMPORTANTLY remember to use "whitening" with an agreed stream.

7, Other modes
As I indicated the ring with some work on it could be used as a Jefferson with covert channels or as a primative for a stream or block cipher. Like all stream and block ciphers it should not be used in simple code book form but at a minimum use some form of cipher chaining with secret IV.

As noted above when used as a block cipher it realy should have either a continuously evolving set of round keys or contiuously changing pre-whitening as this enables a much reduced number of rounds for the same level of security. The obvious candidate for this is to use it as a stream cipher based on a book code. Which begs the age old question "why bother with a block cipher"...

Jakub NarebskiSeptember 6, 2008 12:56 PM

If there are three rings, why not try for tri-letter substitution code, i.e. given triple of letters is encrypted by other triple of letters. That is better than simple letter substitution cipher...

periSeptember 6, 2008 2:03 PM

@Clive Robinson

I really enjoy your posts; this time I was happy to learn of the Jefferson Disk, the M-84 and M-128a ciphers. It seemed to me that Schneier had in mind an Enigma style system. Marty Lamb's method seems Enigma influenced. I am curious to hear what you have to say about operating the rings under an Enigma influenced system.

I also wanted to suggest my reading of Schneier suggests he thinks the rings can be used for encryption and decryption but provided an example crypto hashing system and it was the system, not the rings, about which he said "You can't; it's simply a way to generate passwords."

periSeptember 6, 2008 2:13 PM

@Marty Lamb

I've got to say I like your proposal but step 5 is flawed. Consider what happens when using the key AAA and encrypting "SSSSSS..." The encrypted output is "SRSRSR..." because L1 and L3 never move and L2 oscillates back and forth.

I would suggest changing step 5 so L2 and L3 always consume one character and L3 further consumes characters until you scan across from the input on L1 to L3 and the dot pattern matches. The dots in L1 and L3 have the same distribution so they can safely be used as a checksum.

I would also suggest swapping L1 and L3 as input and output so step 5 only consumes 0, 1 or 2 characters at most.


Clive RobinsonSeptember 6, 2008 9:04 PM

@ peri,

"my reading of Schneier suggests... ...and it was the system, not the rings..."

On reading it again I see where you are coming from, so yes,

Sorry Bruce, a misunderstanding there.

With regard to using the rings like an Enigma system it could be done but the way the rings are described does not sugest it would be at all easy.

It is a little difficult to describe why in words and much easier with a simple picture. But I only have words so hang in there.

I will start of by assuming a simple version of the Enigma with no reflecting stator as this gives a definate single direction of signal flow through the rotors.

The rotors of the Enigma system act as maps or transforms from the input side to the output side. If you where writing it down you would have two vertical columns the input being in alphabetical order on the left the output column on the right, which would appear to be random. For example,

A->g
B->c
C->q
D->r
´ ´ ´
´ ´ ´
X->m
Y->a
Z->p

That is the signal going into the rotor A input would exit from the output that aligns with the G input on the rotor.

However electricaly you need to visualise each rotor as sitting in a cage with contacts to the input and output side of the rotor. And realise that although the cage A contacts do not move, each step of the rotor effectivly changes the mapping to the rotor. So with the input side the cage A contact would step around the rotor contacts A,B,C,D,E,... X,Y,Z,A,B... That is although the rotor map is inveriant at each step the cage input to output mapping changes. Effectivly it has 26 different mappings which are rotations of the rotor map.

In reality unlike other rotor machines there is not a cage round each rotor in the Enigma. But the concept still holds logicaly and helps you keep a referance datum. Therefor it is usual to refrence the imaginary cage contacts back to the input stator contacts from the keyboard and say the rotor contact X is aligned with keyboard contact Y.

In use for a three rotor Enigma you would have the three physical rotors as,

{R1}{R2}{R3}
Q->d,C->q,F->d
R->p,D->r,G->g
S->a,E->q,H->e

That is physicaly the first rotor R1 has it's Q input aligned with the A input from the keyboard. Likewise the second rotor R2 has it's C input aligned with the A input from the keyboard and R3 has it's F input aligned with the keyboards A input.

Therefor electricaly the signal from the A key input would go into R1's Q and exit from R1's D output. This would align with the keyboard N into R2 which is aligned to R2's P input.

That is you have to visualise the offset position of each rotor and apply it to both the input and output of the mapping.

As you can see it is quite difficult to do with the signal going just one way. Now try and visualise what you would have to do with signal coming back from the reflecting stator?

The first thing you would need is an inverse map of each rotor. So your three rotors actually need six maps and a seventh map for the reflecting stator. You would then need to know the correct offset for each rotor map.

In Bruces ring it's rotors have no maps and there are only three of them. Further from the discription it appears to not have a way of dealing with the offssets.

When put this way perhaps you can see why the fit between Enigma and Bruce's ring is a poor one and would need quite a bit of extra work with paper.

Where it would match is if you had the maps on a piece of paper as seven tables you could then use the ring to record the offsets and just trace through each table with a pointer and count off the offsets up and down the individual tables input and output columns by the coresponding offset value.

I don't know if the above "words" help you "see" the problem or not. It's three in the morning U.K. time so hopefully nit has no errors and as I said it is much simpler with a good picture of which there are several on the Internet.

periSeptember 7, 2008 10:56 AM

@Clive Robinson

I can't thank you enough for taking the time to write that. I think I get what you were saying. I also took some time and did a little reading up on Enigma and other rotor machines.

Schneir's hashing scheme says "count one letter to the left if there is a dot over the letter, and one letter to the right if there is a dot under it." Doesn't that make the dots function like rotor windings?

If we ignore the reflector we could create three rotors wired so:
a letter with a dot above it wires the current to exit via its predecessor,
a letter has no dot above it wires the current to exit via itself and
a letter has a dot above it wires the current to exit via its successor.


If we align the rings so from R1 to R3 we have QCF then this mapping is almost possible:

{R1}{R2}{R3}
Q->q,C->c,F->f
R->s,D->d,G->h
S->r,E->f,H->i

The first problem is we would need an additional ring, R0, without dots so we can align the Q in R1 to R0's A. The second problem is that this system {R1} maps both A->z and Z->z.

What do you think? Am I missing something? Is it obvious there is no way to interpret the dots so the mapping is a bijection?


ThomasSeptember 7, 2008 11:10 AM

If the wedding couple needs another "rotor", they could use their fingers...
To all 28 finger elements you can assign a letter (plus two special characters or a shift). To select a rotor position you move the ring to corresponding finger element.
But beware of saw mills!

Clive RobinsonSeptember 7, 2008 1:11 PM

@ peri,

The first problem is the spacing or intervals in the maping between a rotor input and output.

It is "commanly felt" that you need to have every interval space possible to maximise security (no I do not know of any proofs of this but it does not look unreasonable as a proposition).

This would indicate the bruce would need thirteen symbols to put above or below instead of just a dot.

Also if you have done a little reading you might consider the difference between a half rotor and a full rotor. The ring could more easily be used as three half rotors, but as I said it is difficult to use as a full rotor which the Enigma used.

I will have a further think on it to see if there is a "less than obvious" way to use the ring to get a simulation of a full rotor.

AlbatrossSeptember 8, 2008 7:57 AM

Wow, I thought I was dorky, and my wedding ring just has two albatrosses on it, flying around my wife's birthstone sapphire (which is her handle).

While Doctorow's ring may represent only a nod in the direction of truly robust encryption, for the purposes of ROMANCE to be adequately served the ring of Doctorow's spouse needs to be designed to securely store the encryption key of HIS ring. It makes me misty just thinking about it.

P.S. I just thought it was important to reiterate that the encryption mechanism of Doctorow's ring is an "Alberti Cypher".

Angel oneSeptember 8, 2008 8:39 AM

Paul: regarding trying to have a letter A in the ciphertext.

If you encrypt a Z with the key AB you get a 'B', not an 'A'.

In the final ring you land on Y and move 3 spaces to the right, which is a B. There is no letter on the final ring which you can land on which will result in an A.

PaulSeptember 8, 2008 11:42 AM

@Angel one

Yes, you're correct. That was my initial impression on eyeballing the problem, however I made an error in my simulation and wasn't properly skeptical of the results. Mea culpa.

Updated, correct values over keyspace/plaintext space:

A : never occurs
B : 678
X: 1355
Y,Z: 676
rest: 677

So the worst cases are worse, but average output cases are better than I initially thought. For every key, there are no more than 4 ciphertext characters unrepresented (A is always unrepresented, of course) and for no key is there more than 4 plaintext characters mapping to the same ciphertext character. The only keys where the worst case (4 plaintext mapping to one cipher) occurs are BD, CD, DB, XZ, YW, and ZA.

Now to think of a better system...

periSeptember 8, 2008 12:20 PM

@Fred

Glad you like it.


@Albatross "Alberti Cypher".

I don't think that would work because the permutations of all three rings are public knowledge.


@Clive Robinson

Sorry was going to post last night but I ended up discovering all kinds of interesting things are possible if you ignore certain dots.

I also realized the Jefferson Disk Cipher probably wouldn't work here because the key is partly the alphabet permutation on a disk and partly the permutation of the disks; in the wedding rings these are fixed and well known.

So I ended up looking, without success, for a mapping that would give the symmetrical nature of the Enigma machine. Following the dots was as close as I got:


*Follow the Dots

Ignore any dots on y and z.
Letters without dots count for 0, above counts for +1 and below counts for -1.
If your finger isn't over a dotted letter you are done.
If your finger is covering a dot then its count is your total.
Move in the direction of the dot: above means go up and below means go down.
You will stop following the dots when your total is 0.

{R1}, {R2}
A->x, A->x
B->b, B->w
C->d, C->c
D->c, D->d
E->e, E->h
F->g, F->g
G->f, G->f
H->h, H->e
I->j, I->i
J->i, J->j
K->k, K->n
L->m, L->m
M->l, M->l
N->n, N->k
O->p, O->o
P->o, P->p
Q->q, Q->t
R->s, R->s
S->r, S->r
T->t, T->q
U->v, U->u
V->u, V->v
W->w, W->w
X->a, X->a
Y->y, Y->y
Z->z, Z->z

Ignoring dots on y and z means you can only follow the dots on R1 and R2. If you ignore dots on s through z then you can follow the dots on all rings.

Every interval space isn't possible if you follow the dots just once per ring but it is possible to make multiple passes over the rings and changing their alignment each pass does mean any input can now map to any output.


You'll want to turn a ring at least once per letter a small fixed amount to ensure a state change at every letter.

You'll also want to turn a small fixed amount every 26 letters to increase the period. This can be done by picking some none input/output letter and turning the wheel on the condition it is some particular letter.

If you will be using the same key for multiple messages then you'll also want to turn the rings variably as much as possible each letter to protect against people attacking fixed rows in the messages as outlined here:

http://starbase.trincoll.edu/~crypto/historical/...

If you will be using the same key for multiple messages then you may also want to randomly choose a session key for each message by spinning the rings to get a random alignment, sending that key with the persistent key and then encoding the session key and prepending it to the message it keys.

diySeptember 9, 2008 8:30 AM

Has anyone thought about ways to build something like this with common tools & parts?
I'd like to toy around with one, but I'm no jeweller.
It wouldn't have to be fingerring size, but small enough for carrying it a wallet or one's pockets would be a treat.
I think the limiting factor for smallness is the tools you find commonly for engraving letters, if never seen one's where the letters are smallers than 3-4 mm, with only 1 mm space between letters that would give you an outer diameter of 33 mm - to large for a ring.

Any ideas for a flexible version, to put into your wallet or filofax or whatever physical palmtop you use?
One idea: To strips of transparent meterial, closed as a ring and glued together along their middle third. The middle set of letters is printed along that region, too. left and right of it, you enter to closed rings of strong paper, plastic or maybe even cloth with the other to sets of letters. every feww mm, you glue/sew/staple the transparent sheet together along their rim, so the outer to strips can't fall out. You leave spaces between that, maybe with notches, to allow acces to the paper strips.

Another way would be to print three concentric cirlces of letters onto paper, and pinning them to a piece of stronger cardboard. (acually, this easiest and most practical way came to me last . .. I'm not writing this comment chronological)
Do any of you speak ps?

I'm thinking of ways to integrate this into common office/household stuff. Pencils will be too thin, even markers are well below 30 mm in girth. But it should be no problem to make a walking cane, umbrella, or nightstick with a cipher function. Just highly inpractical. A tubular, refillable lighter could work.

Gift idea for nerds: A wristwatch, with 3 concentric code rings surrounding the face.

periSeptember 9, 2008 8:57 AM

@diy

Find instructions for printing circuit boards using a black and white laser printer and translate them to a copper pipe.

Clive RobinsonSeptember 9, 2008 12:51 PM

@ diy,

Don't think wheels or rings think strips.

You need three strips of paper with your alphabets on twice (pluss one char) and about an inch extra at either end. So for Bruce's unscrambled ring you would have three strips of,

[ABC... ...XYZABC... ...XYZA]

Most of the letters in black but the three alphabet start chars (in this cas A) in red.

You then need a small piece of card with two rows of four holes. The holes are spaced just slightly wider than the strips are wide. Throught the holes you need to put loops of cotton thread.

An easy way to do this is as follows,

Make a row of four holes ABCD, below them make another four holes abcd, thus,

| A B C D |
| a b c d |

Take a needle with thread in and place a knot in one end of the thread just like you would for sowing (ask your mum or granny if not sure ;)

Starting at A and from behind the card pull the needle to the front ensuring that the end with the knot stays against the back of the card. Then down through B, up through C, down through D, up through C again down through B and tie the two free ends together. Do the same for the lower case holes.

To use put the three strips of paper under the loops in the top of the card with their alphabets face up. Adjust their position so that your initial position tripplet is aligned between the ABCD and abcd loops. You know have the same as Bruce's ring but as an analog in paper.

As the loops are not closed this is what the red letters are for. Asuming you are pulling a strip downwards and a red letter at the appears between the loops, simply pull the strip up to the previous red letter and carry on.

The reason for two alphabets is so that you always have a section where there is a full set of alphapets against each other, it is also why you need the cotton loops to act as the index position.

Now unlike Bruce's ring you can have as many paper strips as you like, and the card can be as many strips wide as you think will give you the security you need not just the three of the ring.

If you want to see what an "official issue" system looks like and how to operate it securely look at the U.S. M-138-A in it's later forms.

As well as Alberti and Jefferson ciphers you can simulate all half rotor machines on this little gizzmo.

To do full rotor machines such as the Enigma (without the plug board) you need to have the mapping on the strip usuall as upper (in) and lower case letters (out). You need two strips per full rotor one ordered on the in side (upper case) to encode which is the normal mapping. And one orderd on the out side (lower case) to decode which is the inverse mapping.

Encode
ABCDEFGHIJKLMNOPRSTUVWXYZ
thequickbrownfxjmpdvrlazyg

Decode
abcdefghijklmnopqrstuvwxyz
WIGSCM...

As the Enigma had a reflector you will need an additional map for that.

You will also need a piece of paper to write down the "turnover letter" for each rotor as this could be adjusted.

Obviously if you want your system to be durable you would need to use something stronger than paper and card. If you look in a stationary catalog you will find "overhead projector" transparancies that can be put through a lazer printer to make the strips. To make the holder up you can staple to pieces of transparency together and but the stape in to replace the cotton loops just remember to losen it slightly

Oh and be carefull with the craft knife and steel rule, you can cut a lump of your finger all to easily (been there done that collected the sticking plasters 8)

Clive RobinsonSeptember 9, 2008 1:28 PM

@ peri,

" in the wedding rings these are fixed and well known."

Don't wory about it for two reasons. The first Bruce did say,

"Ignore for now whether or not publishing this on a blog makes it no longer secure."

The second and more important reason is that it makes it easier to analyse what you are doing. A real life version would have a mapping selected either at random or after analysis to strengthen the system.

I'm still thinking of a way to do a full rotor on bruce's ring that allows for a suitable mapping without having lots of extra symbols to replace the dots.

An offset number was my first thought. To encode you go top to bottom ring and add offsets to decode you go bottom to top and subtract offsets but there is a flaw with this idea ;)

So I'm still thinking upper and lower case letters on each ring and a fixed index wheel.

htomSeptember 11, 2008 3:52 PM

Perfect pangrams are the first thought of how to extend it. The question is whether to use them as an additional, invisible ring, or in some other fashion. Imperfect pangrams, with repletions ignored, might be useful, too. And I want to use the dots to key transpositions. After doing the letter substitution on four letters, the dots and non-dots above the current trio of "active" letters on the rings indicate swapping; dot on left, swap the first pair of letters currently being encrypted with each other, dot on right, swap the second pair letters, dot in middle, swap the first pair and second pair.

periSeptember 12, 2008 2:42 PM

@Clive Robinson

I am still at a loss for what you mean by "full rotor" and "half rotor." This page alone doubled the Google results for '"full rotor" "half rotor" enigma.' I've been through pretty much everything wikipedia has to say with an appropriate measure of salt. I have also been through a few other site and I have not yet seen anyone explicitly define the distinction between half and full. I can only guess a half rotor has current flowing in one direction while a full rotor has bidirectional current flow. Is this correct? If it is incorrect I would appreciate if you could define it for me and failing that provide a link to a page that does.

I have learned since my last post that it was the symmetrical nature of the enigma machine that meant a plaintext letter could never map to a ciphertext letter and this lead to it being very susceptible to known plaintext attacks.

The only way in which following the dots differs from the Enigma machine is that the simulated "current" can flow in both directions through a wire which allows for identity mappings that wouldn't have been possible with the Enigma. The identity mappings possible when following the dots is thus a feature in the sense that they protect against the known plaintext weakness of the actual Enigma machine. I am curious to hear what you have to say.

periSeptember 12, 2008 2:57 PM

@Clive Robinson "A real life version would have a mapping selected either at random or after analysis to strengthen the system."

I just wanted to make sure you know the rings have already been constructed:

http://www.flickr.com/photos/doctorow/2817314754/...

I am guessing you meant the key would be a few strips of paper mapping the ring letters to some permutation of the alphabet?

Clive RobinsonSeptember 12, 2008 8:07 PM

@ peri,

'I am still at a loss for what you mean by "full rotor" and "half rotor."'

It is only obvious when you know 8)

A "Full Rotor" kind of looks like a hocky puck with gear teeth or holes around it's circumfrance. And importantly has input and output contacts on oposit faces (as used in the German Enigma machine).

A "Half Rotor" looks very different on one side. Instead of having a set of contacts it has a shaft with slip rings on it (as used in some of the Japanese systems).

Assuming the Half Rotor has the shaft on the input side, then it's A contact will always stay conected with the A keyboard wire. Therefore it's rotor map only moves at the output.

This is unlike the Full Rotor where on each step of the rotor both input and output contacts move round.

So, for a rotor with a maping of,

Map (offset)
A->f (back 1, forward 5).
B->e (back 3, forward 3).
C->d (back 5, forward 1).
D->b (back 2, forward 4).
E->a (back 4, forward 2).
F->c (back 3, forward 3)*.

I have used the (simplest) interval offset wiring method which for a rotor with an even number of contacts means that one (*) of the intervals is used twice.

Forward map
In = ABCDEF
Out = fedbac
Off = 531423

Forward chains = (afcdbe)

Inverse map
abcdef
EDFCBA
423531

Inverse chains = (aebdcf)

At step 0 both types of rotor have the same IN to OUT map

At each step (assuming my mental arithmatic offsets are correct) you have,

Half Rotor
ABCDEF
fedbac (step 0)
edbacf (step 1)
dbacfe (step 2)
bacfed (step 3)
acfedb (step 4)
cfedba (step 5)

Full Rotor
ABCDEF
fedbac (step 0)
dcafbe (step 1)
bfeadc (step 2)
edfcba (step 3)
cebafd (step 4)
dafecb (step 5)

Superficialy the full rotor looks to have the more complicated output as the half rotor looks just like a simple alphabet shift.

However if you examine the full rotor as offsets you will see that they simply rotate round.

With regards to the rings yes you could use their alphabet as an index into another substitution table. And you would be wise to change them for each message. A simple way is to use a book code method.

That is both Alice and Bob have the same book and they have a way of selecting a page and start letter on it you then simply work your way through writing down each new letter as they appear, then apply a transform (such as EAT ON IRISH, even then odd).

So using the first sentance in the above paragraph starting at the sixth letter gives,

egardstohinyuclpbx

Apply the EAT ON IRISH rule to shift the most frequent English language letters to the end but maintaining their order,

gdyuclpbx earstohin

Then add the mising alphabet letters to the end,

gdyuclpbxearstohin fjkmqvwz

Then even and odd it,

dulberthnjmvz gycpxasoifkqw

To give you your substitution alphabet for say the first wheel.

Obviously you want to use a different sentance for each wheel and a different transform as well.

periSeptember 13, 2008 3:04 AM

@Clive Robinson

Thanks for taking the time again to detail the difference between full and half rotors. I am still pretty sure that following the dots is a full rotor
simulation.


One Ring Example

For every upper case letter in the alphabet:

Put your finger over the input on R1, move to the adjacent letter in R2, follow the dots and finally move your finger back to R1 and write the output as a lowercase letter.


Results

Following are the input and output for the "One Ring Example" outlined above with all rings aligned (key AAA) and with R2's B adjacent to R1's A (key ABA):

ABCDEFGHIJKLMNOPQRSTUVWXYZ
xwcdhgfdijnmlkoptsrquvbayz (key AAA)
vbcgfedhimlkjnosrqptuazxyw (key ABA)


Looks like a full rotor to me. What do you think?

StevenSeptember 15, 2008 4:55 PM

In languages that use pictograms (like Japanese), signatures aren't idiosyncratic, so people authenticate documents by stamping them with a seal, called a hanko.

Most hanko have a fixed image carved in the face, but I seem to recall that some are made like this decoder ring, with rotating wheels. The owner has to set the wheels properly to create the correct stamp.

It seems like this would be more secure, since possession of the hanko alone isn't sufficient to forge a stamp. However, many people customarily store their hanko with their checks, and neglect to scramble the wheels after using it. So if someone breaks into your house, they have everything then need to forge your stamp...

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..