Reverse engineering a base64 encoded number

Question

I am working on reverse engineering an encoding.

A number between -12 and 12, with 2 decimals is encoded using an unknown method, and the result is a pair of strings as follows:

value   string1     string2
  0     AAAAAAAAAA  AAAAAAAA
  0.01  AAAAB7FK5H  4XqEPwAA
  0.02  AAAAB7FK5H  4XqUPwAA
  0.03  AAAAC4HoXr  UbiePwAA
  1     EAAAAAAAAA  AADwPwAA
  2     IAAAAAAAAA  AAAAQAAA
  3     MAAAAAAAAA  AAAIQAAA
  4     QAAAAAAAAA  AAAQQAAA
  5     UAAAAAAAAA  AAAUQAAA
  6     YAAAAAAAAA  AAAYQAAA
  7     cAAAAAAAAA  AAAcQAAA
  8     gAAAAAAAAA  AAAgQAAA
  9     kAAAAAAAAA  AAAiQAAA
 10     oAAAAAAAAA  AAAkQAAA
 11     sAAAAAAAAA  AAAmQAAA
 12     wAAAAAAAAA  AAAoQAAA
-12     T///8AAAAA  AAAowAAA
- 1     ////8AAAAA  AADwvwAA
- 0.64  ////97FK5H  4XrkvwAA
  2.01  IAAAAUrkfh  ehQAQAAA

(any additional samples can be provided upon request)

Obviously, I would like to determine the algorithm used to do this conversion.

My research indicates it MIGHT have to do with base64 encoding, and the alphabet used is ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

A=0 B=1 ... /=63

For instance, the first column, translated to decimal, then divided by 4 (discarding the remainder), gives the "integer" part of the value, when the value is positive, or 16-value, when negative.

I had lass luck with the decimal part, I just don't have the knowledge.

If anyone can give me a hint or a solution, it would be immensely appreciated.

I am a photographer with basic math and programming knowledge, and this would be the central piece needed to complete a script that will optimize my workflow, that now requires for me to manually read, compute (excel) and write those values back (in decimal).

Thank you.

Answer 1

These are binary representation of double numbers encoded with base64. To understand the encoding lets see an example (I used to convert numbers to binary double representation with this page):

0.03 = 0x3F9EB851EB851EB8 (binary representation of the double number)

With little endian encoding it is stored in the memory in the following form:

B8 1E 85 EB  51 B8 9E 3F

You have to extend the first and second 4 bytes with 2 zeros and encoded it with base64:

base64(0000B81E85EB) = AAC4HoXr
base64(51B89E3F0000) = UbiePwAA

In your example the 0.03 was encoded to:

0.03 = AAAAC4HoXr  UbiePwAA

So, the difference is only the first 2 letters in the first string, but I don't see why the first string starts with these letters.

Answer 2

Building on @ebux's answer:

The first 4 bytes is the integral part of the number, encoded in a slightly weird way .. the UPPER nibble of the first byte is the number itself. The other 5 nibbles are 0 for positive, f for negative numbers in the "usual" way.

The rest of the strings are, like @ebux said, the float part of the value, in IEEE format, but when encoding/decoding them, you have to add/remove two \0 bytes to the binary string.

This perl program will decode a file containing your examples:

#!/usr/bin/perl

use MIME::Base64 qw(decode_base64 encode_base64);
while (<>) {
    chomp;
    y/\r//d;
    s/- /-/;
    s/^\s+//;
    ($a, $b, $c)=split();
    $a2=decode_base64(substr($b, 0, 4));
    $b2=substr(decode_base64(substr($b, 2)), 2);
    $c2=substr(decode_base64($c), 0, 4);
    printf("%10s", $a);
    print "\t"; printhex($a2); 
    print "\t"; printhex($b2); 
    print "\t"; printhex($c2);
    print "\t"; printint($a2);
    print "\t"; printdbl($b2.$c2);
    print "\n";
}

sub printhex {
    my $str=shift;
    for ($i=0; $i<length($str); $i++) {
        printf("%02x.", ord(substr($str, $i, 1)));
    }
}

sub printint {
    my $str=shift;
    my $val=ord(substr($str, 0, 1))>>4;
    $val-=16 if (substr($str, 1, 1) eq "\xff");
    printf("%5d", $val);
}

sub printdbl {
    my $str=shift;
    my $val=unpack("d", $str);
    printf("%10.4f", $val);
}

Output (column order is your column, 3 columns of hex bytes derived from the base64 strings, integer value derived from col1, float value from col2/3):

  2.01  20.00.00.   14.ae.47.e1.    7a.14.00.40.        2       2.0100
     0  00.00.00.   00.00.00.00.    00.00.00.00.        0       0.0000
  0.01  00.00.00.   7b.14.ae.47.    e1.7a.84.3f.        0       0.0100
  0.02  00.00.00.   7b.14.ae.47.    e1.7a.94.3f.        0       0.0200
  0.03  00.00.00.   b8.1e.85.eb.    51.b8.9e.3f.        0       0.0300
     1  10.00.00.   00.00.00.00.    00.00.f0.3f.        1       1.0000
     2  20.00.00.   00.00.00.00.    00.00.00.40.        2       2.0000
     3  30.00.00.   00.00.00.00.    00.00.08.40.        3       3.0000
     4  40.00.00.   00.00.00.00.    00.00.10.40.        4       4.0000
     5  50.00.00.   00.00.00.00.    00.00.14.40.        5       5.0000
     6  60.00.00.   00.00.00.00.    00.00.18.40.        6       6.0000
     7  70.00.00.   00.00.00.00.    00.00.1c.40.        7       7.0000
     8  80.00.00.   00.00.00.00.    00.00.20.40.        8       8.0000
     9  90.00.00.   00.00.00.00.    00.00.22.40.        9       9.0000
    10  a0.00.00.   00.00.00.00.    00.00.24.40.       10      10.0000
    11  b0.00.00.   00.00.00.00.    00.00.26.40.       11      11.0000
    12  c0.00.00.   00.00.00.00.    00.00.28.40.       12      12.0000
   -12  4f.ff.ff.   00.00.00.00.    00.00.28.c0.      -12     -12.0000
    -1  ff.ff.ff.   00.00.00.00.    00.00.f0.bf.       -1      -1.0000
 -0.64  ff.ff.ff.   7b.14.ae.47.    e1.7a.e4.bf.       -1      -0.6400
  2.01  20.00.00.   14.ae.47.e1.    7a.14.00.40.        2       2.0100

This program converts one or multiple numbers to your format:

#!/usr/bin/perl

use MIME::Base64 qw(decode_base64 encode_base64);

foreach $a (@ARGV) {
    print $a;
    my $intpart=($a & 0x0f) << 4;
    if ($a<0) {
        $intpart|=0xffffff0f;
    }
    my $part1=encode_base64(pack("l", $intpart)); chomp $part1;
    # print "\t", $part1;

    my $temp=encode_base64("\x00\x00".pack("d", $a)); chomp $temp;
    # print "\t", $temp;

    my $part2=substr($part1, 0, 4).substr($temp, 2, 6);
    print "\t", $part2;

    my $part3=substr($temp, 8, 6)."AA";
    print "\t", $part3;

    print "\n";
}

Example:

$ perl encode.pl 0.01 0.02 0.03  2.01 0 11 12 -12 -1 
0.01    AAAAB7FK5H  4XqEPwAA
0.02    AAAAB7FK5H  4XqUPwAA
0.03    AAAAC4HoXr  UbiePwAA
2.01    IAAAAUrkfh  ehQAQAAA
0       AAAAAAAAAA  AAAAAAAA
11      sAAAAAAAAA  AAAmQAAA
12      wAAAAAAAAA  AAAoQAAA
-12     T///AAAAAA  AAAowAAA
-1      ////AAAAAA  AADwvwAA

And here's a link to all numbers from -12 to 12:

https://mega.nz/#!BVpWgBiI!aPbtMmMYnLgUUn011Cl5qjA5OO6TpKG8CSTIhR7Re0E