Thinking About Encryption, Part 11


I admit that my primary go-to book is Simon Singh’s The Code Book, which came out in 1999. That makes it pretty out of date theory-wise, but the history side isn’t going to change much with age. One small section of the book concerns The Great Cipher. Developed by two of France’s most brilliant cryptographers of the time, father and son team Antoine and Bonaventure Rossignol, it was used from some time after 1643 up to the death of Bonaventure’s second son, Antoine-Bonaventure (unfortunately, no one seems to have an exact date of death for him.) More specifically, mathematician Antoine Rossignol came to the attention of Louis XIII’s chief minister, Cardinal Richelieu in 1628, after Antoine broke, in one day, an encrypted message sent by the Huguenots pleading for ammunition from their allies to prevent the city of Realmont from falling to a siege by the French. After Louis XIV ascended to the throne, both Antoine and his son ran France’s Black Chamber (their code bureau), and they developed the Great Cipher to encrypt all of Louis XIV’s more private letters and records. Since they never shared the algorithm with anyone else, it wouldn’t be until 200 years later that anyone would ever be able to crack it and read those letters.

Etienne Bazeries required 3 years of hard work to finally crack the cipher in the 1890’s. Singh doesn’t go into the details of the Great Cipher, and I can’t read French, so I’m going to be short on specifics as well. Before I go any farther, I need to introduce a bit of terminology that I’ve skimmed over previously.

Monoalphabetic: A substitution cipher is considered “mono-alphabetic” if the substitution remains fixed over the entire message. That is, if “A”= “B” and “B”=”H” from the first letter of the plaintext, and this substitution assignment doesn’t change, then the cipher is monoalphabetic (it uses one “alphabet”).

Polyalphabetic: Conversely, if the substitution assignments change depending on where you are in the message, then the cipher is said to be “poly-alphabetic” (it uses more than one “alphabet). Vigenere is an excellent example of a polyalphabetic cipher. If the keyword is  “keyword,” then as you go through the message, starting with the first letter, “A” is going to equal “K”, if “A” is the second letter of the plaintext message, it will equal “E”, and as you go through plaintext positions 3 through 7, it will be “Y,” “W,” “O,” “R,” and “D” before recycling.

Polygraphic: This is when you substitute more than 1 letter at a time. That is, if 5 = “th” and 29 = “ll,” the cipher is polygraphic. My blog entry Part 9 discussed in part the use of polygraphics with phoneme-, syllable- and word-level substitutions. (Monographic just means that the cipher is a single letter-for-letter type.)

Homophonic: I mentioned this term a long time ago. One of the biggest weaknesses of a language is its uneven usage of the letters in its character set, or its “alphabet” (ref. “ETOAIN SHRDCLU”) which is what allows us to tackle it through frequency analysis. To flatten out the symbol distribution, we can assign more than one value to the more common characters. This works best if you use numbers instead of the ASCII character set. Say 3, 27, 99, 104 and 200 all represent “E”; and 3, 30, 60, 81 and 199 are all the letter “T”. Then, a cipher that randomly selects from these assignments for the plaintext letters is said to be homophonic (“same sound”). The question should be what “random” means. If, for some reason we select 30, x, 27, 30, x, 27 twice in a row for the word “the” that shows up multiple times in the plaintext, then we’re defeating the point of using homophones. It may be better to scramble the order of the assignments so they’re not in ascending order (104, 27, 200, 3, 99), and then use them in sequence. Which of course introduces a new weakness, in that these cycles become detectable in long messages.

Nomenclator: This is essentially another name for a code book. A nomenclator lists the monoalphabetic, polygraphic and homophonic substitutions for a given cipher. The substitutions can be numeric, or they can use variations of upper, lower, and upside down characters, or all-new invented character sets.

Null: A character that translates to nonsense. Used for padding the end of a message to make it longer, or for confounding the codebreaker by introducing something that’s not actually used for recreating the plaintext.

Trap: Characters used in a substitution to mess up the codebreaker. Traps can be single values (i.e. – 23) or groups (23 64 104) that mean “ignore the previous value or group”).

Ok, so we go to to the Great Cipher. The main reason it fell was that Etienne had a large volume of letters to work with, and he eventually realized that some of the numbers referred to syllables, instead of whole words or individual letters. I’m very disappointed with the articles I’m finding on the Great Cipher in English on the net because they’re inconsistent, they repeat each other without adding anything new, and they offer few to no examples of deciphering longer blocks of text. As an example, the wiki article says that the heart of the Great Cipher was a set of 587 numbers that represented the syllables of the French language, plus other numbers representing person and place names and whole words. Some of the other sources state that the entire cipher was just the 587 value set for the syllables. What I can determine is that the Rossignols put together several nomenclators (code books) to be sent to French ambassadors and the military, and that these nomenclators were homophonic, monoalphabetic, polygraphic, and contained nulls and traps. In the wiki article, one bit of trivia that gets repeated by a lot of other web articles, is that one of the nomenclators was 711 code numbers long, 131 of which represented the letter “e”.


(Example of one page of one nomenclator (code book).)

In other words, the Rossignols’ Great Cipher as employed in the code books sent out to message recipients, as well as for the encryption of Louis XIV’s personal letters, used a large quantity of code numbers. Some of these code numbers represented person and place names, some were for regular words, others were for syllables, and the rest represented individual letters, nulls and traps (some of which could have multiple codes for one character, null or trap).

Etienne’s work pointed out one flaw of the Great Cipher – it was used more than once to encrypt Louis’ letters. Each nomenclator represented one algorithm plus key combination. Because it was considered secure, and few people had access to all of Louis’ letters, the Rossignols felt little need to change the nomenclator very frequently.

Now, I keep trying to make up correlations between ciphers and the various fields of math and physics that I don’t really understand all that well. And to me, the Great Cipher suggests a Turing Machine. The plaintext (or, conversely, the ciphertext) can be written to the input TM tape, and the algorithm is the Turing machine itself. In effect, we could pretend that if the tape contains an “e”, we write any one of the 131 values for “e” to the output tape, and advance the tape one position. Additionally, we could randomly decide to write a null code value and advance the output tape again. Along the way, we could randomly decide to write an entire group of nonsense values and follow that with the code number for “ignore the last “x” values.” Or, we could check the input tape for recognized syllables or words and write out the code numbers for those.

In this sense, the concept of a “cipher algorithm” literally becomes a computer algorithm. This leads me to an algorithmic pseudocode that could be implemented in any language you want. This algorithm would depend on the generation of a nomenclator that consists of code numbers for the letters, syllables and desired words, plus numbers for a handful of nulls, and traps that negate previous code strings of varying lengths (i.e. – “negate last code number”; “negate last 5 code numbers”; “negate previous code numbers up to code number 565”; “negate code numbers at positions -1, -3 and -5 from current position”). The trap class would then have “.length”, “.code” and possibly a way to interleave “nonsense” with plaintext when you’re deleting non-sequential codes as in the last example above. (Note that flipCoin() is a method that has an n% chance of returning Heads.)

For word in message begin;
coin := flipCoin(90%);
if word in nomenclator and coin = H then
write nomenclator(word).code(any);
else
for syllable in word begin;
coin := flipCoin(50%);
if syllable in nomenclator and coin = H then
write nomenclator(syllable).code(any);
else
for letter in syllable begin;
coin := flipCoin(5%);
if coin = H then
write nomenclator(NULL).code(any);
write nomenclator(letter).code(any);
end;
end;
coin := flipCoin(1%);
if coin = H then begin;
trap := nomenclator.trap(any);
write nomenclator(nonsense).length(trap.length);
write trap.code;
end;
end;

What makes this approach fun is that you can now generate hundreds and hundreds of nomenclators of differing sizes in a few seconds, distribute them ala a one-time pad, and then your key is just the file number for the nomenclator file you use for encryption. You can even use any given nomenclator more than once (within reason), because certain code numbers for specific syllables or letters may never appear in any one ciphertext, allowing for the illusion that you are indeed using a brand new look-up table (if you keep your messages short).

The next step after this would necessarily be writing the nomenclator generator, an exercise left up to the student.

Advertisements

Wiggles, part 8


Just a little ongoing story to give you something to play with until the next blog post.

DMIKBEG BI OHIS. SFM CMIL PFFK NFJ H IVFYYBEG UBILJBTL, FJ LJHBE ILHLBFE, YBTK H QMBOL DBL FN IBUOAHPK EOHJ LVO ZFIL TJFAUOU YHJL FN LVO YOUOILJBHE AHPKAHSI, HEU ILHJL YPHSBEG. HI PFEG HI SFM UFE’L BELOJNOJO ABLV DMIBEOII, LVO ILFJO FAEOJI AFE’L TFZYPHBE, HEU BN SFM’JO TPOHE HEU UJOIIOU FK LVO ZHAHJB-IHE (DOHL TFYI) POHWO SFM HPFEO. SFM UF GOL VHIIPOU FTTHIBFEHPPS, HEU HL LVFIO LBZOI SFM CMIL VHWO LF DFA, EFU SFMJ VOHU H PFL, HEU IFZOLBZOI HPPFA SFMJ LBYI LF DO “TFENBITHLOU”. FLVOJABIO, BL VOPYI LF VHWO H TFMYPO TUI LF IOPP, HEU H LABLLOJ HTTFMEL SFM THE YFBEL YOFYPO LF. ABLV H IMZHYVF (IZHJLYVFEO), SFM THE HTTOII LVO EOL AVOJOWOJ SFM HJO. LVBI BI GFFU NFJ GOLLBEG ZFJO AFJK, ZHSDO, NJFZ DHJ FAEOJI. FLVOJABIO, B IYOEU H PFL FN LBZO IMJNBEG LVO AOD NFJ FYOE ZBT EBGVLI, HEU LJS LF GOL GBGI LVHL AHS. HI IFFE HI SFM GOL H DBL FN H JOYMLHLBFE VOJO, SFMJ EHZO IYJOHUI DS AFJU FN ZFMLV, HEU H TFMYPO FN FNNOJI ABPP TFZO BE NJFZ IFZO FLVOJ LFAE, GBWBEG ZO H JOHIFE LF GOL DHTK FE LVO DBKO NFJ H TFMYPO VFMJI.

Thinking About Encryption, Part 10


Ok, so say you get a file with a .bin extension. There’s no obvious application attached to it, and the best we can assume is that it is a PC file, and that it’s in binary. The first step would be to use a hex editor and check whether there’s any kind of header to the file, or if there are any blocks of human-readable text. Nothing shows up in the editor, but we have reason to believe the file has been bit-level encrypted. What next?

Let’s assume that the only options are those mentioned in Part 9. They were: Pair swapping, bit flipping, Scytale, rail fence, X-ORing and 7-bit grouping. The final algorithm can be checked quickly just by looking at the file contents – if every hex pair is between 0 and 127 (00-7F), then do a frequency analysis on the file. If the character distribution is more-or-less flat, try reversing the grouping.

That is, if you have
24 1B 0D 46 7B 5D 5E 72 36 19 00 (hex)
List the binary values out in groups of 8.

00100100
00011011
00001101
01000110
01111011
01011101
01011110
01110010
00110110
00011001
00000000

Remove the leading 0’s from each byte, and form the lines into one long string. Add spaces every 4 characters.

0100 1000 0110 1100 0110 1100 0110 1111 0111 0111 0110 1111 0111 0010 0110 1100 0110 0100 0000 0

Convert the string to hex.

48 65 6C 6C 6F 77 6F 72 6C 64 0-

That last “0-” is shorter than 8 bits. We can assume it’s padding and discard it.
Right now, we can look at the hex bytes, and at a glance see that they’re mostly between 41 and 7F, so maybe this is an ASCII file. Otherwise, we could try reversing the string and repeating the above steps to see what that gives us. But, if we look the bytes up in the ASCII table, we get,

“Helloworld”

But, say that didn’t work. We already know how to do pair swapping, so try that.

The thing about pair swapping is that we really can’t assume that the encrypter flipped neighboring bits (7 and 6, 5 and 4, 3 and 2, 1 and 0). If the PC is 64-bit, then we may need to try every single combination here. But, for this example, let’s keep things simple with 3-bit swapping. If we number the bits 0-2, we get the following combinations:

210
201
120
102
021
012

That’s 6 combinations with just three bits. We go to 4 bits, that 24 combinations. For 8 bits, that’s 8! = 40,320 combinations. Woof. We can try to speed up the bruteforce approach by only sampling the first 200 bytes and then looking for readable text. Alternatively, we can use frequency analysis (FA). If the encrypter only swapped up to 8 bits each, then this is going to look just like any random substitution cipher, and it will fall to FA. If the file is long enough, and contains a lot of text, we may see some repeating character groupings, the same as we did with Vigenere. This is because the swap width is going to behave exactly the same as with the Vigenere key cycling. That is, if the word “the” occurs frequently in the plaintext, the bit-swapped ciphertext will show up with spacings that are a factor of the swap width. That can help narrow down possible swap combinations you have to test.

As an example,
12 A6 36 36 F6 EE F6 4D 36 46

You might already see the give-away here. Yes, the swap width is 8 bits, In binary we get,

0001 0010 1010 0110 0011 0110 0011 0110 1111 0110 1110 1110 1111 0110 0100 1110 0011 0110 0100 0110

A bruteforce test of the first few bytes will show that the swap pairs are 7-0, 6-1, 5-2, 4-3. And converting back to ASCII gives us “Helloworld” again.

Bit flipping is easy, because there’s only one “key” per se. That is, if the bit is 1, change it to 0, and vice versa. Just do a sample test on the first 100 bytes and see what comes out.

Now, this brings me to binary data files. Files with extensions like .doc, .xls, and .ppt are going to have header blocks with fixed bytes at fixed locations. E.g. – PDF files have “25 50 44 46 = %PDF” at the beginning. We could actually build up a database of header data for the most common file extensions, with the data bit-flipped and bit-swapped, and then just run through the database on the file header and hope for a match. If we do get one, then we apply the entire algorithm with the matching key on the rest of the file.

So, for 25 50 44 46
0010 0101 0101 0000 0100 0100 0100 0110
Bit-flipped:
1101 1010 1010 1111 1011 1011 1011 1001

Gives us a tag of DA AF BB B9 for PDFs, and this is what we’d have stored in our database.

I already talked about bit-wise Scytale. We can either do a simple brute force test and then a frequency analysis or a header match test. Or, we can try something a bit different, but kind of like the header match test.

Say we have a big file, and we don’t want to brute force the entire thing for every value of Scytale key width of 2 to length/2. One thing we can do is predict where certain bits would land in the encrypted file, and test those. Say we have:

FF 00 00 00

But, we number the target bits:

1234 5678 0000 0000 0000 0000 0000 0000

And we apply a Scytale cipher with width 8.

12345678
00000000
00000000
00000000

1000 2000 3000 4000 5000 6000 7000 8000

In fact, the numbers above represent 1’s, and the cipher text will be
88 88 88 88

The point is that the numbered bits above represent the bits we’d want to test to get a match. If the actual file contains:
1010 1100 0100 1111 0110 1101 1011 1000 Cipher
1000 1000 1000 1000 1000 1000 1000 1000 Test bit locations
1 1 0 1 0 1 1 1 (fails the match for “1 1 1 1 1 1 1 1” = FF)

Then only look at bits 7 and 3 of each byte and compare them to our prepared tag. If we get a match, then we know both the file type, and the Scytale width. If not, go through the rest of the file header database. If still no match, then increment the Scytale width and start over from the top of the header database.

This would work the same way for rail fence.

This leaves X-ORing. You may already be ahead of me at this point (or, you may 10-20 years ahead of me), but the algorithm for X-ORing is to apply a key bit-wise to the plain file, If you have 1+0 or 0+1, the result is 1. Otherwise 1+1 and 0+0 are 0. If the plain file is 6C and the key is 37:

0110 1100 6C
0011 0111 37
0101 1011 : cipher out = 5B

Now, in general, we could use the Vigenere cycle length test again to get the length of the key back out (look for repeating character groups and check the length of the spacing between these groups, which should be a factor of the key length). Then, brute force the X-OR with different key combinations to maximize the frequency counts of specific byte groups.

Alternatively, we can try to break the key. If the file is one of the common document types (.xls, .ppt, pdf, .doc, etc.), then we have the known header data for that file type. Going back to the PDF example, the first four characters are “%PDF” (25 50 44 46). If the cipher data is:

1010 1110 1101 1100 0110 1010 1111 0000 : Cipher
0010 0101 0101 0000 0100 0100 0100 0110 : %PDF
1000 1011 1000 1100 0010 1110 1011 0110 : Potential key

By itself, this proves nothing. We need to slide our potential key (8B 8C 2E B6) along the rest of the PDF file and see what, if anything comes out. If we do get additional matches on part of the header, or the rest of the file, then we can at least be somewhat confident that we are looking at an encrypted PDF file and not something else. Otherwise, try the next filetype in the database.

Naturally, everything revolves around knowing what algorithm is being applied. Or, having a strong suspicion. Otherwise, you’re going to waste a lot of time chasing down the wrong rabbit hole.

That’s my thoughts on this topic, for what it’s worth.

Wiggles, part 7


Just a little ongoing story to give you something to play with until the next blog post.

NES QPILP KOP NCPE IAA PEIP “VIRIX CQ NBCLH” QPOZZ IP PEB TBDCXXCXD? NBAA, CP’Q I AKP FEBIRBL PK QABBR CX I FIUB, I HCQOQBH PLICX POXXBA, KL IX BJRPS TOCAHCXD PEIX CP CQ IP I EKPBA. IXH SKO JBBP I JOFE JKLB CXPBLBQPCXD FAIQQ KZ RBKRAB PEIP NIS, PKK. IZPBL IAA, VIRIX CQ IX BMRBXQCUB RAIFB PK TB, IXH PEBLB ILB I AKP KZ EKJBABQQ EBLB. PEBS EIUB PK ACUB QKJBNEBLB, IXH QKJB KZ PEBJ FIX TB I AKP KZ ZOX PK PIAG PK. ACGB PEB ZKLJBL FBK KZ I FKJROPBL ZCLJ NEK NIQ KX PEB NLKXD BXH KZ I EKQPCAB JBLDBL, KL PEB JIXDI ILPCQP PEIP TBFIJB IAFKEKACF IXH QOZZBLBH QBUBLIA XBLUKOQ TLBIGHKNXQ TBFIOQB KZ PEB RLBQQOLBQ ECQ BHCPKLQ ROP ECJ OXHBL. XCFB ZKAGQ, VOQP XKP NBAA-QOCPBH ZKL FKRCXD NCPE JKHBLX QKFCBPS. GCXH KZ ACGB JB, C DOBQQ, TOP C HKX’P EIUB QK JIXS QPKLCBQ JSQBAZ. C VOQP OQB JS DOCPIL PK PIAG ZKL JB.

Thinking About Encryption, Part 9


There’s a concept in mathematics that revolves around changing domains, or changing systems. By this, I mean that you can have an equation that you map in a Cartesian coordinate system, which is essentially the x-y grid, and the equation can be in the form of y = a*x + b. Quite often, though, the problem you want to solve may not be that easy in a Cartesian system, but it could be trivial when using polar coordinates, which are represented by a radius and an angle. Or in vector space, with a magnitude and a direction. To go from one system to the other, you need a conversion formula. An alternative example could be using the Fourier transform to switch between the time and frequency domains.

The question then becomes, are there “systems” in cryptography? Is there a moral equivalent to Cartesian and polar coordinates? In a gross sense, I think we could say that are two types. The first is on the message level, and the other is on the media level.

For anyone new to ciphers, it would seem that enciphering is either a matter of moving the plaintext letters around (transposition), or changing them to something else (substitution). I’ve only really addressed rail fence, Scytale, Caesar and Vigenere, and if those were all the algorithms anyone had ever come up with, we could be forgiven in thinking that the point is to just manipulate individual letters.

But, look at the English language. We have phonemes, letters, syllables, words, sentences and paragraphs. And, on a meta level, we have nouns, verbs, adjectives, adverbs and everything else. On a message level, we could (and many other people already have) develop algorithms that encrypt plaintexts on a non-letter basis. It’s a bit tricky trying to define phonemes for individual words if the sender and the receiver have different accents. You’d need to go with the dictionary definitions or fixed 2- and 3-letter combinations, but it is still possible to develop a random substitution table for phonemes, either to other phonemes, or to numbers. As an example, “cram” would turn into “‘kram”, and “through” would become “thru” (where “u” has the umlauts). The Dyslexia Reading Well lists 44 phonemes in the English language, so we could either code them as upper or lower letters (the 26 upper plus 26 lower letters, which would allow for some duplications), or simply as the numbers 1-46 (if you don’t use delimiters, then 1-9 would need leading “0” padding). If you want to get nasty, use hexadecimal pairs (00-FF), which would give you 0-255 potential assignments.

Syllable substitutions would work pretty much the same way. The Quora page answering the question “How many syllables are there in English” gives two different answers: over 10,000, and exactly 15,831. Given that, to do the encryption, you’d need an agreed upon substitution table, you can simply pick the syllables, or letter groupings, you care about, and use those. In this case, it would probably  be easier to use number values. That is, “gi” = 1, “ven” = 2, “tt” = 3, “le” = 4, “ers” = 5. “Given letters” would then be 1 2 4 3 5. Any text not encrypted at the syllable level could be treated as individual letters and given numeric values like 100-200, if you like.

Ok, when we come to words, or word groupings, it might seem that we should give up. Merriam-Webster had 470,000 entries in their 1993 Addenda edition, and there’s the question of what’s an English word? Do we include “teriyaki,” “sushi,” and “cannoli”? But, what if we mix systems? Pick the 100 most common words and give them number values. (I.e. – “the” = 1, 6 and 9; “if” = 2, 10 and 20; “may not” = 7 and 8). Everything else can be represented as letters, phonemes and syllables.

Technically, there’s no point in trying to substitute entire sentences or paragraphs, but there’s no reason we can’t transpose them. We could resort to Scytale and rail fence on a sentence-by-sentence, or paragraph-by-paragrah basis. Alternatively, the substitution table we use above could change based on a key from one sentence or paragraph to the next (hello again, Vigenere).

For the second system, the “media,” we have the computer. As mentioned above, it can be easy for a beginner to get trapped in the idea that a plaintext message is simply whatever you have written down on paper, or typed with a typewriter, as a string of letters, digits and symbols. Even if we make the transition to a computer, we see these characters as represented by the ASCII table. “A” = decimal 65, hex 41; “Z” = 90 decimal, hex 5A. In fact we are performing a random substitution all the time when we type messages up on a computer, because 54 68 65 = “The”. Applying a simple Caesar cipher with a shift of one gives use 55 69 66, or “Uif”. Cracking a random substitution cipher can be done as easily for “Uif” as it is for 55 69 66, through the application of frequency analysis.

The mistake is to not change number systems. ASCII is based on 8-bit binary. 00000000 = 0, and 11111111 = 255 (if we use hex, then 00-FF). General ASCII just uses 0-127 (00-7F), while the upper half of the range (80-FF) can be any graphics characters you like.  This is fine for the English alphabet, but languages like Chinese and Japanese use non-phonetic pictogram systems that can easily require 2,000-5,000 characters for high school-level literacy. Which is where Unicode comes in. One of the most commonly-used Unicode versions is UTF-16, which is a 16-bit variable-width encoding system. Unicode is important to understand if you’re dealing with “letter level” substitutions as described above. Otherwise, at the bit level, we don’t care.

This next part is a bit off-topic, but the second we go binary, we can start talking about filename extensions. .doc indicates that the file is a Word document; .jpg is a JPEG image file, and .mov is a video file that includes audio. Up to this point, I’ve only been concerned with .txt, or ASCII textfiles. But these extensions just represent format conventions for data files used by specific applications. Ignore the application that created the file and now you just have an arbitrarily long string of 1’s and 0’s in sequence. Who cares what the “plaintext” file was? Just move the bits around and the application (or the person trying to access the data in the encrypted file through that application) can’t read it.

To do this, we still have substitution and transposition. The most obvious choices would be Scytale or rail fence, but we can also use swapped pairs.

“The” was 65 41 90, which is also
0110 0101 0100 0001 1001 0000

Swapping pairs of bits, we get
1001 1010 1000 0010 0110 0000 (9A 82 60)

Both 9A and 82 are outside the regular ASCII character range, and will appear as strange graphics shapes. Unfortunately, this is no different than a regular random substitution, and will fall to frequency analysis.

Scytale with a width of 5 gives us,
01100
10101
00000
11001
00000 (and adding 0 for padding)

Or,
01010 10010 11000 00000 01010

Going back to hex pairs, with more 0 padding:
01010100 54
10110000 B0
00000101 03
00000000 00

But, this is where things get a tricky. By adding padding, we’re kind of giving away the width value. Because computers use widths of 2, 4, 8, 16, 32, 64, etc., if the ciphertext is not a multiple of one of those numbers, we can assume padding was added to bring the number of bits up to a multiple of the cipher width. The ciphertext is 25 bits long, and that’s kind of an obvious clue. Next, though, we need to put our ciphertext back into a format the computer can recognize, and that means padding up to 32 bits. We can do that easily by appending 0’s at the beginning or end of the string, but how is our recipient going to know how much padding we’ve added?

Actually, having the key width will help. If the ciphertext is 32 bits long, but the key width is 5, then our recipient can argue as follows: The plaintext length is going to be a multiple of 8 bits, giving me 8, 16, 24 and 32 bits as options. If the plaintext was 8 bits long, then the Scytale portion needs to be padded to 10 bits. For 16, padded to 20. For 24, padded to 25, and for 32, padded to 35. 35 bits is right out, and the closest number to the current 32 bits of the ciphertext is 25. Obviously, there’s 7 bits of padding, either at the front or the back, and then 1 more bit for the Scytale portion. Now, anyone trying to crack this cipher can use the same logic, but they have to apply a bruteforce approach to the ciphertext for every value from 2 to length/2. And, naturally we can choose to reverse some of the columns of the Scytale following whatever rules we want, as well as doing that old “keyword” -> “dekorwy” column shuffling I’ve talked about before for Scytale.

That was transposition. For substitution, we can flip bits:

“The” was 65 41 90, which is also
0110 0101 0100 0001 1001 0000

Flipping 1 to 0, and 0 to 1:

1001 1010 1011 1110 0110 1111 (9A BE 6F)

Again, two of the characters will look like random graphics. And again, this will fall to frequency analysis because it still looks like a random substitution.

Instead, we can exclusive or (XOR) the plaintext against a key. If the key is the same length as the text, say CAT (43 41 54), and we know that the rule for XOR is that 0+1 and 1+0 = 1, otherwise 0+0 and 1+1 = 0, then

0110 0101 0100 0001 1001 0000 (The)
0100 0011 0100 0001 0101 0100 (CAT)
0010 0110 0000 0000 1100 0100 (36 00 B4)

A weakness here is that if we use only human-readable keywords (anything using A-Z, a-z, 0-9 and punctuation), then our keys won’t change the high bit (bit 8), and won’t include values 0-31, which are “non-printable” characters. We can overcome this by using simple hex values for the keys (00-FF) and not worry about trying to make words out of the keys.

And of course, we can combine Scytale with XOR as we like. This brings me back to the idea of making the length of the XOR keyword into the width of the Scytale or rail fence transposition, and reversing the order of the transposition columns if the length is even or odd.

One more complication can be the decision to make the ciphertext human readable. In other words, we can pretend that the resulting output is either ASCII or Unicode. It’s easier to pretend we’re dealing with ASCII. To do this we group the bits in bunches of 7 and prepend a 0 at the front to make 8-bit groupings. For the example, let’s go back to the bit flip,

1001 1010 1011 1110 0110 1111 (9A BE 6F)

We need groups of 7 bits,
1001101 0101111 1001101 1110000

Then we prepend the 0’s to get
01001101 00101111 01001101 01110000
4D 2F 4D 70 = “M/Mp”

The real drawback to this type of algorithm of making 7-bit groupings and prepending the 0 is just that we’re making the file roughly 12.5% larger, which is going to affect file transfer times. But, if the time for sending the file is not an issue, then we’re still good to go. The real reason for doing any of this is that it makes the bruteforce approach to cracking the cipher that much more time consuming. If our opponent has no idea exactly which algorithm we’re using, they have to test every single one, in all conceivable combinations.

Theoretically speaking, of course.

I’m not really sure how well my original point holds up that encryption/decryption has an analogue to coordinate switching in math. But it serves as an introduction to this blog entry well enough.

Wiggles, part 6


Just a little ongoing story to give you something to play with until the next blog post.

E VTX T NOD OP PWYY DERY EZ DVY KZTMB ATW, DVOJFV, TK GYNN TK OZ-ATKY. T MOJCNY OP RH XTX’K PWEYZXK VTX T ATZX, TZX DVYH DTJFVD RY DO CNTH FJEDTW. TZX, RH ROR GTZDYX RY DO NYTWZ YZFNEKV, KO KVY KYZD RY DO T MOJCNY MWTR KMVOONK. DVY POWYEFZ DYTMVYWK TD DVOKY KMVOONK JKJTNNH UJKD KDTHYX EZ UTCTZ POW 6 ROZDVK DO T HYTW TZX T VTNP, TZX DVYH MOJNXZ’D AY AODVYWYX DO AWEZF TNN DVYEW AYNOZFK GEDV DVYR GVYZ DVYH GYZD ATMB VORY TD DVY YZXK OP DVYEW KDTHK VYWY. DVTD RYTZD DVTD DVYH’X UJKD XJRC GVTDYQYW DVYH XEXZ’D GTZD DO BYYC, GVEMV EK VOG E FOD T CTEW OP PWYY TMOJKDEM FJEDTWK PWOR DVYR. E’X BYYC OZY OZ ATKY, TZX DVY ODVYW TD DVY KZTMB ATW, TZX E’X CNTH EP ZODVEZF YNKY GTK FOEZF OZ. GVYZ E PEZEKVYX KMVOON, E MOJNX VTQY FOZY OZ DO JZEQYWKEDH, OW E MOJNX VTQY PONNOGYX RH XTX DO DVY J.K. EZKDYTX, E JKYX RH MOZZYMDEOZK GEDV DVY ODVYW ATWK EZ DVY ZYEFVAOWVOOX DO CEMB JC AOJZMYW GOWB. GEDV DVTD, E’X DTNB DVY OGZYWK EZDO NYDDEZF RY CNTH RJKEM T NEDDNY, TZX RTBY KORY ROWY ROZYH DVTD GTH. YQYZDJTNNH, E FOD FOOX YZOJFV DO KJWQEQY OZ AJKBEZF, AOJFVD RHKYNP T RODOWMHMNY, TZX AYFTZ GTZXYWEZF DVY MOJZDWH TK T PONB KEZFYW.

Thinking About Encryption, Part 8


Building on the algorithm from the last post, because I still haven’t had time to add more ciphers to En/De yet, say we just want to use Vigenere, Scytale and Rail Fence. For the moment, let’s just stick with upper case letters in the plaintext, because that’s what Vigenere was designed around. But, there’s nothing that says we have to. It’s trivial to treat the source file as binary, and build up a Vigenere table for the entire 256-character ASCII set. Our key could then be converted to 2-byte hex, and each number (0-255) would point to a row of the table where the ASCII table is shifted left that many positions. Then, for enciphering, we could use straight code instead of a look-up table, as in:

(pseudocode)

for i :=0 to plainText.length – 1 do
chPlain := plainText[i];
chKey := keyText[mod(i, length(keyText))];
chCipher[i] := mod(chPlain + chKey, 255);
next;

Instead, I’ll just use the normal Vigenere table, which is the upper case alphabet Caesar-shifted one position to the left for each row.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
BCDEFGHIJKLMNOPQRSTUVWXYZA
CDEFGHIJKLMNOPQRSTUVWXYZAB
DEFGHIJKLMNOPQRSTUVWXYZABC
… etc.

As a reminder, if the keyword is JACK, then we use the row that starts with “J” to look up the first letter of the plaintext, the row that starts with “A” for the second letter, the “C” row for the third letter, the “K” row for the fourth letter, then cycle back to “J” for the 5th letter, and so on.

To build on this, let’s allow for a key phrase, which can be as many words long as we like. If the word is “A”, or when we hit a space, we just skip it. Otherwise, we can apply the following rules:

1) If the length of the phrase is even, apply the Vigenere cipher before applying transposition; otherwise, apply Vigenere after transposition.
2) Strip out the spaces from the phrase and use the resulting string as the Vigenere key.
3) Step through the key phrase one word at a time.
4) If the word length is even, use the Scytale cipher to transpose the working text; otherwise, use rail fence.
5) Strip out any recurring letters from the current word, and use the resulting length as the transposition key.
6) Apply the transposition to the working text, but only for making the rows/columns.
7) Stepping through the stripped keyword, if the letter is even (b, d, f…) reverse the column; otherwise, leave the order alone (columns for Scytale, rows for rail fence).
8) After step 7 is done, rearrange the stripped keyword so the columns are in alphabetic order.
9) Complete the transposition algorithm now, pulling the columns out and putting the working text into one long string.
10) Go back to step 3 as long as there are words left the key phrase.

This looks kind of wordy and unwieldy. So, we need an example.
Say the plaintext is:
“This is a plaintext message.”
-> “THISISAPLAINTEXTESSAGE”

And the key phrase is “Wish you were here.”
The length is 19 characters, which is odd, so step one says the order will be Vigenere then transpose.

The stripped key is:
“WISHYOUWEREHERE”
which becomes the Vigenere key.

Applying the Vigenere to the plaintext, we get for the working text:
PPAZGGUTCWQFACLNQVOASNC

The first keyphrase word is “WISH”, which is four letters long (even), so we use the Scytale transposition. Let’s use padding (x’s) on the last row for simplicity, only.

WISH
—-
PPAZ
GGUT
CWQF
ACLN
QVOA
SNCX

W: PGCAQS
I: PGWCVN
S: AUQLOC
H: ZTFNAX

Even letters: BDFHJLNPRTVXZ
“H” gets reversed

H: XANFTZ

Sorting the letter order,

HISW: XANFTZPGWCVNAUQLOCPGCAQS
—-

Apply the Vigenere again with the “WISHYOUWEREHERE” key:

TIFMRNJKNYDFHSEFSTLOUHOG

“YOU” is an odd length, so we use rail fence. Again, padding the end of the string isn’t really necessary, but I’ll do it for simplicity.

T—R—N—H—S—U—X
-I-M-N-K-Y-F-S-F-T-O-H-G
–F—J—D—E—L—O

Y:TRNHSUX
O:IMNKYFSFTOHG
U:FJDELO

“YOU” -> “OUY”, and all the letters are odd, so none of the rows are reversed.

OUY: IMNKYFSFTOHGFJDELOTRNHSUX

Apply Vigenere again,

EUFRWTMJKKPYMHRYPFPZFOQIR

Rinse and repeat. “were” and “here” turn into “WER” and “HER”, for two more rail fences. “R” and “H” are both even letters, so those rows get reversed in both cases.

This post is getting long enough, so I’ll stop here. The point is that someone who has the key phrase can just reverse the process and get the plaintext back out (minus spaces and punctuation). Anyone else can never be sure that what they’ve obtained was really the same message.

That is, when you attack this cipher, you have to brute force test everything against the following possible cases:
Vigenere is applied before the transposition.
Vigenere is applied after the transposition.
The key length is unknown and there are no reliable repetitions.
The transposition can be either Scytale or Rail Fence.
The transposition keys can be anything between 2 and cipher length/2.
Any given row of the transposition can be reversed, or not.
Any of the above combinations for the Vigenere and transposition ciphers could be applied anywhere between 1 and 1 million times, depending on the length of the key phrase. (More practically, the phrase might be between 2 and 30 words, the longer the better.)

In a way, this situation calls up the “many worlds interpretation” from quantum mechanics, in that not knowing my original key phrase, someone trying to break my message could get back:

“THISISAPLAINTEXTESSAGE”
“THEEYEOFTHETIGERISBLUE”
“INAREDGALAXYFARFARAWAY”

And any other of an infinite combination of readable English words of the same length, even if they get the number of padding characters right. And in at least one of the many worlds, every single possible output would be correct.

This also relates to one strength of the Vigenere – for very long keys, it’s pretty much unbreakable. If you use a one-time pad with keys made of 1000-2000 randomly selected letters, you only use any given key once before throwing it away, and you keep your plaintext shorter than the key length.

That is, say your key is 13 characters long, and the plaintext is “I like cheese”.
If the key is “BDFHJLNPRTVXZ”, you get:

JONRNNUTVLZ

The key doesn’t cycle, and there’s no combination of cipher characters that repeat. Someone not knowing the key could obtain “theoretical” (also 11 letters), because they can’t be sure that the key WASN’T “QHJDWJBLTLO” (because, maybe you didn’t strip out the duplicated letters from the key – and you wouldn’t if you required a 1,000 character-long key).

Speaking strictly theoretically, of course. As always, the weakness in the above algorithm is in how you get the key phrase to the recipient of your message, and in how you ensure the same key is never used twice.

Wiggles, part 5


JI OMJB PY CPJUCVI IMJMFWGVP. P FQBZ WK UO MPQ SUQGBY XMYBY MQUWOA NMKMO WOCPD P CWQOBA 17. JI AMA ZMY M JBGVMOPG, MOA JI JUJ YCPDD QWOY M YJMDD XMQ OBMQ CVB XMYB PO IURUYWRM. P YKBMR BOFDPYV XBCCBQ CVMO P AU NMKMOBYB, XWC P GMO JMRB JIYBDS WOABQYCUUA PO BPCVBQ DMOFWMFB. P’J 6 SUUC, MOA 220 KUWOAY, MOA P YKBOA M GUWKDB VUWQY M ZBBR PO CVB XUEPOF FIJY US ZVMCBLBQ GPCI P’J PO. ZVBO P CBDD YUJBUOB CU KPYY USS, CVBI WYWMDDI FBC JI AQPSC. CVPY VMKKBOY JUQB USCBO CVMO P’A DPRB, XBGMWYB P ZUQR KMQC CPJB MY M XUWOGBQ. JI JUJ’Y KDMGB ZMY M YOMGR XMQ, ZVBQB YMDMQIJBO ZUWDA GUJB PO MC OPFVC MSCBQ ZUQR, MOA CVBO FBC AQWOR CU XDUZ USS YCBMJ. YVB VMA CZU “VUYCBYYBY” ZUQRPOF SUQ VBQ, MOA YUJB US CVB GDPBOCBDB ZUWDA YUJBCPJBY FBCCPOF M DPCCDB CUU CUWGVI-SBBDI. ZVBO P ZMY LPYPCPOF VBQ UO CVB ZBBRBOAY, P’A UGGMYPUOMDDI FBC GMWFVC WK PO CVB POBLPCMXDB YRPQJPYVBY, MOA P DBMQOBA SMYC CVMC NWYC YMIPOF “KPYY USS” ZMYO’C BOUWFV. IUW VMLB CU XB ZPDDPOF CU CMRB M KWOGV UQ CZU CU CVB SMGB XBSUQB IUWQ YOBBQ, KQBSBQMXDI M XDUUAPBA UOB, QBMDDI FBCY CVQUWFV CU CVB UCVBQ FWI. PS PC AUBYO’C, ZBDD… CVMC’Y ZVI P XUE.

Dreaming – papercraft


In the land of Godzilla and giant robots…
Dreaming mechanical monster dreams.

Thinking About Encryption, Part 7


I want to build on the point made at the end of the last blog entry.
There are two separate processes for creating new ciphers, and for attacking them. For developing a new cipher, traditionally the factors have been: ease of use, ease of getting the key to the recipient, ease of reversing the cipher without making mistakes, and the difficulty in breaking it. The Caesar and Scytale ciphers were fine for their times because the “enemy” often didn’t know the language being used all that well, and writing out all of the different possible combinations on parchment or animal skin brute-force was too much work. Additionally, it would be hundreds of years before the idea of frequency analysis would occur to anyone.

When Caesar and Scytale were no longer viable sources of security, the idea became one of identifying weaknesses in existing ciphers and then eliminating them. With simple substitution ciphers, we can check letter frequencies, so one obvious change is to flatten the letter counts out, either by adding more choices for the more common letters, or by using polyalphabetic tables as with Vigenere. Now, though, with Vigenere, and anything that uses repeating keywords, we get recognizable cycles, leading to cycle counting. The Enigma machine was a brilliant invention in that it essentially acted like a never-ending Vigenere table generator.

The Enigma machine might have remained a worthy cipher option, except that banks and companies started sending messages back and forth at the rate of hundreds a day, with even greater sums expected in the future. Private keys were no longer feasible. That led to the development of RSA and public keys in the late 70’s.

Conversely, when attacking a cipher, you want to look for weaknesses, repetitions, the appearances of certain words in the plaintext that you can rely on (such as “submarine,” “troops,” and “commander”), and even quirks introduced by the operators sending the messages. If it’s a brand new cipher, you need to amass a mountain of ciphertext that hopefully uses the same key. If the message uses an existing, known cipher, you can sometimes just apply brute force, trying all possible combinations of the key with the known algorithm until the plaintext comes back out.

One of the most common analogies used when discussing physics and ciphers is that of mixing paint. If you have a can of red, and a can of green paint and you pour them together, you can still tell at the least that you have red and green in the same tray. But then, you start stirring, and you keep stirring for an hour. When you’re done, the “enemy” is not going to know exactly what proportions of red and green you started with, and they definitely aren’t going to be able to pull all the red paint back out of the tray, leaving only the green behind. But, the recipient of a cipher message that has the key is doing exactly that, which is possible specifically because they know the algorithm that was used to do the “stirring” and can then “unstir it.”

With private key ciphers, a lot of the initial security came by keeping the algorithm secret. Even the Engima machine would have been impregnable, were it not for the fact that Polish agents were able to get their hands on a working machine, with user instructions.

So, if the algorithm is known, what next? The answer is to make the brute force approach too time consuming to be practical. In the case of the Engima machine, there were 4-5 wiring wheels that acted like hardwired random substitution ciphers, and the first wheel would advance one position as the operator pressed a key. When the first wheel made one full rotation, the second wheel would advance one position; same for the third wheel. Three wheels were used of the 5, and they could be in any order, and start on any letter. That is, you could use wheels starting at 3=Z, 1=K, 5=M for one message, and 3=B, 1=Y, 5=B for the next message, and so on. Later, there were up to 8 wheels to choose from. That’s like 26!*26!*26!*26!*26!*26!*26!*26! combinations to work through, even if you do know the wiring of the individual wheels and the machine itself. The hope is that the universe would end before the enemy landed on the right combination of wheels for one message.

But, by knowing the algorithm, you can find weaknesses that the designers may have missed. Such as the rule that the wheels can not code a letter to itself (A!=A), and that wheels give 1-to-1 correspondence to the wiring (if A=R on wheel 1, then R=A on the same wheel). Or, you look at the people sending the messages. People get lazy. They don’t change their keys regularly, so that multiple messages have the same key, making them more vulnerable to frequency analysis. At the beginning of the use of Engima, the operators would send the key twice (e.g. – “KLAKLA”) to avoid mistakes in receiving the key. The cipher text could then start with JMYUVT, and we’d now know that J and U are the same letter three letters apart, even if you don’t know what J is. And, that would point a finger at which wheel was in the first slot.

We’re very slowly working backwards on that paint tray, getting closer to our original values for the red and green paints. The recipient of the message is doing this exact unmixing process which is easy for them because they do have the key. Knowing the algorithm lets you attack it. For private key ciphers, this is bad,

Enter public keys. It doesn’t matter if the enemy knows the algorithm for mixing the paints, or even that they know the recipient’s public key. The idea here is the recipient is given two very large prime numbers, which they use as their keys for deciphering whatever message they are sent. They then multiply these two primes together and make that public to anyone that wants to send them messages. The sender uses a different algorithm to encipher their plaintext message using that public key. An “enemy” intercepting the message now needs to factor the public key to get the recipient’s original two prime numbers back out. And this step just takes a REALLY, REALLY long time if the key is 1024 bits long or more. So, you’re not attacking the algorithm now, you’re attacking the key. If you have a server farm, you can do this, but maybe not for more than one or two keys at a time.

One idea I’ve been playing with is applying a multi-word key phrase on a Scytale cipher. Say you use the phrase “July August”, on the plain text “This is a plaintext message”. In the first pass, using “July” as the key, you get (adding padding for simplicity):

This
isap
lain
text
mess
agex

Then, sorting “july” to get “jluy”

Tihs
iasp
lian
txet
mses
aegx

For the string
Tiltmaiaixmsehsaeegspntsx

Now, for “augst” (removing the duplicated “u”):
Tiltm
aiaix
msehs
aeegs
pntsx

“agstu”:

Tltmi
aaixi
mehss
aegse
ptsxn

We get,
Tamaplaeettihgsmxssxiisen

If we allow for key phrases of any length, then the first paragraph of a Dan Brown novel would stir that paint can pretty well. Someone intercepting the ciphertext would never know when to stop unmixing. Was the key phrase something like words of 5, 7, 3, and 4 letters, or of 24 and 17 letters? What orders were the columns each time? And were any of the columns reversed? We could apply reversing rules based on even and odd word lengths plus whether the letter in the key word was a vowel or consonant. Finally, we could use the key phrase, minus spaces, to apply a Vigenere substitution either to the plaintext before transposition, or after the transposition is finished, again based on whether the number of key words in the phrase is even or odd.

This is one way to remove obvious letter or word repetitions, cycle counts, etc., while mixing the paints up really good. Knowing the algorithm won’t make a brute force approach any faster. This just leaves the question of how to distribute the key, and that’s an exercise left to the student.