nice cat watch screen

Binary Maelstrom

Matasano cryptopals challenge - part one - Converting to base64

This post is the first one of a serie about the matasano cryptopals challenge. This serie is not intended to cover all excercises of this challenge. I’m just going to write about some of them I find interesting. Moreover, I don’t want to give all solutions of the challenge, it could be more rewarding to do it by yourself.

So, I’m going to talk about the very first exercice: base64 encoding. You have an ascii (or hex encoded, whatever…) input buffer, you must return a base64 encoded of the input. As you could guess by yourself, a good entry point is this page. In this exercice, it is not asked to handle the padding but anyways, I put the padding as part of the solution.

So here is a quick example on how things work with base64 encoding:

We define the following index table: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=

  1. We have the sequence “Fo” as input.
  2. We convert the sequence using ascii decimal value for each character: 70 111 (and add 0 to have a ascii sequence multiple of 3).
  3. We convert every ascii decimal value in binary (8-bit sequence).
  4. Now we cut the all sequence of bits into 6-bits long values.
  5. Every 6-bits long value is converted into an integer. (17 38 60 0)
  6. For every integers i, i is the index of the base64 symbol of our output in our index table, the last sequence will be the padding .

This algorithm is illustrated in the following table:

Source input F o
ASCII Dec 70 (0x46) 111 (0x6F) 0
Bit pattern 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0
Index 17 38 60 0
Base64 enc. R M 8 =

In practise, the implementation of the below algorithm is slightly different because:

  1. Each input character is already in its integer representation when stored
  2. We get the result from the index table directly from the 6-bit integer representation (we shift the bits from the decimal input representation)
  3. By comparing where we are in the input, to the input size, we apply the right shifting and set the right padding if needed (if clauses)

This results in the following C implementation:

 1 typedef unsigned char byte;
 2 char index_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
 3 
 4 byte * 
 5 ascii_to_64(byte * input) { 
 6 
 7     byte * str64;
 8     unsigned int input_length = strlen(input); 
 9     unsigned int str64_length = input_length * 4 / 3; 
10     unsigned int i, j = 0;
11 
12     if((str64 = (byte *) malloc(str64_length * sizeof(byte))) == NULL)
13         return NULL;
14 
15     for(i = 0; i < input_length; i+=3) {
16 
17         str64[j++] = index_table[(input[i] >> 2)];
18 
19         if(input_length >= i+2) {
20             str64[j++] = index_table[(((input[i] << 4) & 0x30) | ((input[i+1] >> 4) & 0x0F))];
21         } else {
22             str64[j++] = index_table[(((input[i] << 4) & 0x30) | (0x00))];
23             str64[j++] = index_table[64];
24             str64[j++] = index_table[64];
25             break;
26         }
27 
28         if(input_length > i+2) {
29             str64[j++] = index_table[(((input[i+1] << 2) & 0x3C) | ((input[i+2] >> 6) & 0x03))];
30         } else {
31             str64[j++] = index_table[(((input[i+1] << 2) & 0x3C) | (0x00))];
32         }
33 
34         if(input_length >= i+3) {
35             str64[j++] = index_table[((input[i+2]) & 0x3F)];
36         } else {
37             str64[j++] = index_table[64];
38         }
39     }
40 
41     return str64;
42 }

That’s it for today. As usual, any feedbacks are always welcome using my email address (“about” page).

Happy crypto!

comments powered by Disqus
Newer >>