How to perform frequency analysis of a substitution cipher using a Base64 alphabet Let's imagine a cipher that works like the following:


Plaintext is encoded to Base64.
The characters in the encoded plaintext are substituted with a randomly shuffled character set(A-z, 0-9, -, _, =).  The shuffled alphabet is, in essence, the key.


Not particularly complex or even secure.  But...

What if I wanted to do frequency analysis?

For example, "RUNFORYOURLIFE" when encoded in Base64 is:

UlVORk9SWU9VUkxJRkU=

When the character set is shuffled, the final cryptext can look something like this:

xv24DYG9qxG2xYg6DYxf

The key being: 

yhAc5bTOWeYvBXCpVuoMJLdg8P1jHN3ZIsi67SrK4E_D9-x2qRQmnlkwUaFt0G=zf

Which is a shuffled version of:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_=

Let's also assume that the character set in subsequent messages is in the same order(ie the key is re-used).

Since the bytes are basically split up resulting in different character units that may or may not correspond, is frequency analysis still feasible?  Does encoding plaintext this way before encryption add any form of security?

My question mostly pertains to longer messages, as my example may be too short for any sort of real analysis.
I'll assume that the plaintext consists entirely of capital ASCII letters as in the example. This implies the high 3 bits of each byte of plaintext are 010.

It is useful to visualize how 3 consecutive bytes of plaintext map to 4 consecutive Base64 characters.


1. Frequency analysis of the last character of 4-char blocks in ciphertext

We see there is a straight mapping from the last of every three characters in the plaintext to the last of every four characters in the Base64 encoding (notice that the characters in Base64 codes the 5 lower bits of the character in the plaintext, on the right of the above picture, which are characteristic of the letter). It follows that we can perform single-letter frequency analysis on the ciphertext restricted to the last character of every block of four characters. If among the characters kept the last one is different from all the others, it likely represents = in Base64; all the other characters kept should be among 26 characters (else the assumption made above is disproved). The mapping, ordered by decreasing expected letter frequency in English plaintext (according to this source) is:

Plaintext          Plaintext          Plaintext          Plaintext
 | Base64           | Base64           | Base64           | Base64
 |  | Frequency     |  | Frequency     |  | Frequency     |  | Frequency
 E  F  0.12702      H  I  0.06094      W  X  0.02360      K  L  0.00772
 T  U  0.09056      R  S  0.05987      F  G  0.02228      J  K  0.00153
 A  B  0.08167      D  E  0.04253      G  H  0.02015      X  Y  0.00150
 O  P  0.07507      L  M  0.04025      Y  Z  0.01974      Q  R  0.00095
 I  J  0.06966      C  D  0.02782      P  Q  0.01929      Z  a  0.00074
 N  O  0.06749      U  V  0.02758      B  C  0.01492
 S  T  0.06327      M  N  0.02406      V  W  0.00978


and with a kilobytes of ciphertext, it is likely that the most frequent character in the fraction of the ciphertext kept corresponds to E in the plaintext, thus F in the Base64.

2. Frequency analysis of the first character of 4-char blocks in ciphertext

There is a function from the first of every three characters in the plaintext to the first of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the first character of every block of four characters. The characters kept should be among 7. Expected frequency is

Plaintext  Base64  Frequency
  DEFG       R      0.21198 = 0.04253 + 0.12702 + 0.02228 + 0.02015
  LMNO       T      0.20687 = 0.04025 + 0.02406 + 0.06749 + 0.07507
  TUVW       V      0.15152 = 0.09056 + 0.02758 + 0.00978 + 0.02360
  PQRS       U      0.14338 = 0.01929 + 0.00095 + 0.05987 + 0.06327
  HIJK       S      0.13985 = 0.06094 + 0.06966 + 0.00153 + 0.00772
   ABC       Q      0.12441 =           0.08167 + 0.01492 + 0.02782
  XYZ        W      0.02198 = 0.00150 + 0.01974 + 0.00074


It happens that the set of Base64 characters in the second method is a subset of the set for the first; this allows cross-checking the guesses.

3. Frequency analysis of the third character of 4-char blocks in ciphertext

There is a function from the second of every three characters in the plaintext to the third of every four characters in the Base64 encoding; we can perform a variant of single-letter frequency analysis on the ciphertext restricted to the third character of every block of four characters. The characters kept should be among 16 (except perhaps the last, which may map to = in the Base64 character set). Expected frequency is

Plaintext                               Plaintext
 | Base64                                | Base64
 |  | Frequency                          |  | Frequency
EU  V  0.15460 = 0.12702 + 0.02758      HX  h  0.06244 = 0.06094 + 0.0015
DT  R  0.13309 = 0.04253 + 0.09056      GW  d  0.04375 = 0.02015 + 0.0236
CS  N  0.09109 = 0.02782 + 0.06327       L  x  0.04025
IY  l  0.08940 = 0.06966 + 0.01974      FV  Z  0.03206 = 0.02228 + 0.00978
AQ  F  0.08262 = 0.08167 + 0.00095       M  1  0.02406
 O  9  0.07507                           P  B  0.01929
BR  J  0.07479 = 0.01492 + 0.05987       K  t  0.00772
 N  5  0.06749                          JZ  p  0.00227 = 0.00153 + 0.00074


Several of the characters in the Base64 character set for this third method also occur in the first two methods; this allows cross-checking the guesses.

Frequency analysis of bigrams

We can also consider bigrams in plaintext occurring in the last character of a block of three, and the first character of the next block; and how they map to bigrams in Base64 occurring in the last character of a block of four, and the character following. We can compute the common bigrams obtained in the ciphertext by keeping (as first character of bigram) the last character of a block of four, and (as other character of bigram) the next character; and compare to common bigrams in English (adding frequencies of up to 4 bigrams as we did in the second method).

This also works for bigrams in plaintext occurring in the last two characters of a block of three, mapping to bigrams in Base64 occurring in the last two characters of a block of four; again well be comparing to the frequencies of common bigrams in English (adding frequencies of up to 2 bigrams as we did in the third method).

Common/guessable trigrams in plaintext to finish the analysis

The above will allows recovering the mapping to ciphertext of no more than 36 out of 65 characters used in Base64. For the others, we should guess some aligned blocks of three characters in the plaintext based on what we already know and common English words, transcode these blocks of three plaintext characters to four Base64 characters, see if there is a contradiction with the established mapping of Base64 to ciphertext, and if not cautiously apply the new guesses.

Automated cryptanalysis

As rightly pointed in that other answer, heuristic algorithms can handle the search automatically. Still, I guess that the first three techniques (which can be adapted to different plaintext alphabets, e.g. with space, lowercase..) will greatly simplify the heuristic.