2
$\begingroup$

I'm attempting to decrypt a body of ciphertext which has been encrypted using a monoalphabetic cipher. The trouble I'm having is that the plaintext was base64 encoded before being encrypted. In this puzzle the encryption scheme uses an array containing a permutation of 0-63 as the key. It takes the plaintext and encrypts each char by taking its index in the base64 alphabet and using that as the index in the key. Then that key value is used as an index to take the ciphertext character from the base 64 alphabet.

I understand the typical way to solve a cipher like this is through frequency analysis of the letters (knowing that e is the most common letter and so on). My confusion comes from how to do this given the plaintext is base64 encoded.

I have read though this post but am having trouble understanding how to actually apply it. I have been able to write some python to count the frequency of every 4th char in the ciphertext but I'm not sure what the next step is to get the plaintext/key.

One of the things I did attempt was mapping the results of the frequency analysis back to plaintext. For example e in binary yields 01100101. Then if you have an e as the 3rd char in the plaintext then the 4th char of the base64 encoded plaintext would be l (100101). From there I would look at the analysis of the ciphertext and see the most common letter was V meaning that V mapped to l. Then calculating the different in indexes in the base 64 alphabet of those to letters I get $$64 - 37 = 27$$ (37 = the index of l, to get to the end of the alphabet)

$$27 + 21 = 48$$ (adding 21, the index of V). This leaves me with the $key[30] = 48$, 30 being the index of e in the base64 alphabet. I repeated this for multiple letters but it didn't yield any readable text when attempting to decrypt with that key then unencoding the returned text.

Additionally I attempted to map the capital and lower case letter to the same result since I believe this will just yield a case insensitive plaintext. Continuing the example above, I would also set $key[4] = 48$ as well, 4 being the index of E in the base64 alphabet.

I'm not sure if this is signifigant but all the indexes in they key array that I did not map (some of the less common letters, 0-9, and '+' '/' I initialized to 0.

Any tips on where to go from here or how to approach this problem would be greatly appreciated.

$\endgroup$
3
$\begingroup$

You will probably not get any (even partially) readable text out until you've figured out the decryption of the most common characters in at least two adjacent base64 positions (1 and 2, 2 and 3, or 3 and 4).

That's because the eight bits of each plaintext byte get spread across two adjacent six-bit base64 characters during the encoding process. Thus, even if you manage to correctly decrypt one of these two characters, you've still only recovered at most six of the eight bits. That leaves at least two bits whose value you'll just have to guess.

That said, the difficulty of guessing those two missing bits depends a lot on which bits happen to be missing. In particular, the ASCII codes for all letters (A-Z, a-z) have their highest two bits out of eight set to 01. (The third-highest bit is 0 if the letter is uppercase, and 1 if it's lowercase.) So, if your plaintext is actually ASCII text, you may be able to get some partially readable output just by trying to decrypt the last base64 character in each group of four, and just assuming that the previous character decodes into something that ends in the bits 01.

(However, do note that the most common plaintext byte, if your plaintext is indeed ASCII text, is most likely not a letter at all, but the space character, whose ASCII code 32 = 00100000 in binary begins with 00, not 01. The same is true of numbers, line feeds and most but not all punctuation.)


More generally, you will likely want to exploit the structure of the ASCII code, which makes the highest two or three bits of each plaintext byte quite predictable. In particular, if you take any group of three eight-bit plaintext bytes (representing three ASCII characters) and split them into four groups of six bits (as base64 encoding does), you'll end up with something like this:

ABC??? ??DEF? ????GH I?????

where the bits ABC, DEF and GHI (corresponding to the highest three bits of each plaintext byte) can be:

  • 000 only if the byte represents a control character (of which the only ones likely to appear in plain ASCII text are the line feed = 00001010, the carriage return = 00001101, which is usually always followed by a line feed, and possibly the tabulator = 00001001);
  • 001 for spaces (00100000), numbers (for which the next bit is always 1) and most punctuation characters;
  • 010 for uppercase letters (and the characters @, [, \, ], ^ and _); or
  • 011 for lowercase letters (and the characters `, {, |, } and ~).

Note that, in plain ASCII text, the highest bits of each eight-bit byte (i.e. bits A, D and G above) are always 0. (That said, they could be 1 if your plaintext was actually written in some "extended ASCII" encoding like ISO Latin 1, or perhaps Unicode in the UTF-8 encoding, and contained some non-ASCII characters.)


For example, let's say that you guess that the most common byte in your plaintext is probably an ASCII space (binary 00100000), and therefore that the most common base64 character (let's arbitrarily say it's X) at the end of each 4-character group probably encodes the bits 100000.

This means that this base64 character X should basically never appear as the first character of a 4-character group (since that would make bit A above 1), and should only rarely appear as the second character (since that would make bits DEF be 000, which should be pretty rare unless the plaintext is full of line breaks). If that's indeed the case, you can be pretty confident that you've guessed correctly.

Also, you can then look at the base64 characters that precede X in the ciphertext, and be pretty sure that they all represent six-bit base64 codes that end in 00 (since bit G must be 0 in ASCII text anyway, and if bit H was 1, that would decode to the rather uncommon plaintext byte 01100000 = `), which (together with their frequencies in the four different positions) should help narrow down their possible values.

Similarly, you can guess that the most common base64 character in the first position of a four-character group probably encodes the bits 001000, and that the two most common characters following it in the second position probably encode 000100 and 000101 (assuming that a space is most often followed by a lowercase letter; of course, the bit sequences 000110 and 000111 are also likely to be fairly common, since they arise from a space followed by an uppercase letter).

And the most common base64 character in the third position most likely represents the bits 000001 (i.e. a space followed by a letter), especially if it does not usually precede the most common fourth-group character (i.e. X above), as that would again yield a rather unlikely plaintext sequence involving the backtick character ` = 01100000.*


Also, assuming that your plaintext is indeed English ASCII text, another approach you can use to get started is to look for common repetitive sequences of base64 characters in the ciphertext, and assume that they likely correspond to common sequences of characters in English text.

For example, probably the most common five-byte sequence in English ASCII text is  the  (i.e. "the" surrounded by spaces on both sides). When broken up into three-byte groups for base64 encoding, depending on where the group boundary happens to fall, you can end up with either:

  •  th and e ?;
  • ? t and he ; or
  • ?? , the and  ??,

where ? stands for some variable byte (most likely a letter). Thus, the 4-character base64 groups encoding  th, the and he  should all be pretty common, and appear with roughly the same frequency (although note that the frequencies can be skewed not only by random chance, but also by the presence of other common English words sharing the same beginning or end, such as "that", "this", "those", "these", "they", "there" and "then", as well as "he" and "she", and of course the capitalized form "The").

Furthermore, you can distinguish the base64 groups encoding these different 3-byte sequences by looking at the surrounding encrypted base64 characters. For example, the group that encodes the should very frequently be preceded by the base64 character that encodes the lowest six bits of an ASCII space (i.e. 100000) and followed by the base64 character that encodes the highest six bits of an ASCII space (i.e. 001000). Furthermore, since they encode spaces, which are common in general, these two base64 characters should usually each be the most common ones in that position of a 4-character group.

(Of course, the group the won't always be preceded or followed by a space, since it can also appear as part of a longer word, or possibly at the beginning or the end of a line. But the most common plaintext bytes before and after it should still be spaces.)

Similarly, the four-character group encoding  th should begin with the base64 character that encodes the first six bits of an ASCII space (and is thus rather common in the first position of a group), and should be commonly followed by a specific sequence of three base64 characters that encodes followed by a letter. And, correspondingly, the group that encodes he  should end in the common character that encodes the last six bits of a space, and should typically be preceded by the two base64 characters that correspond to  t at the end of the previous group.

Some other fairly common byte sequences in English text that you may want to look for include  a  and  I  (i.e. "a" and "I" surrounded by spaces), both of which can be quite easy to recognize if you've already determined which base64 characters corresponding to spaces at the beginning and the end of a group, as well as  and  (another fairly common three-letter word surrounded by spaces, occurring in a similar pattern as  the  above, but typically sufficiently less common to be fairly easily distinguishable) and the four-byte sequences  to ,  of ,  in ,  at , etc. You'll probably want to mostly ignore the latter until you've managed to decode at least some common letters, though, since there are rather many common two-letter words in English, and their relative frequency can vary a lot based on the topic and style of writing.


*) That said, everything always depends on what the plaintext actually it. For example, the Markdown source code of this very answer is full of backticks, most often following or followed by a space, since that's the Markdown syntax for inline code.

$\endgroup$
0
$\begingroup$

Ilmari's answer above is very thorough, and it is well worth considering how base64 works. In particular, the placement of symbols in the 4 character sequence needs considering.

I would suggest an alternative approach to the frequency baseline calculation. Download a large corpus of English text, or something that represents the frequencies of the plaintext. Then measure the histograms.

$\endgroup$
  • $\begingroup$ Just "then measure the histograms" is too short for an answer. Please extend it so that the answer doesn't rely on an internet search of the term. Or if you don't feel up to it, convert it to a comment below the question - I prefer upvoting a good answer though :) $\endgroup$ – Maarten Bodewes Sep 19 '18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.