Password Algorithms: bcrypt File Encryption

Introduction

lxd requested analysis of BFE files generated by the bcrypt file encryption utility which according to the home page, hasn’t been updated in 10 years. Judging by the mailing list, lots of people still use it.

I’ve come across this program in the past while searching for information about bcrypt password algorithm built into OpenBSD. Both are completely unrelated codes, just in case there’s any confusion.

bcrypt will by default compress a file using ZLib and encrypt with Blowfish.

Usage is straight forward enough; supply a list of files to encrypt and specify if you want them overwritten and removed once complete.

# bcrypt
Usage is: bcrypt -[orc][-sN] file1 file2..
  -o Write output to standard out
  -r Do NOT remove input files after processing
  -c Do NOT compress files before encryption
  -sN How many times to overwrite input files with random data

Initial observations

I created a text file with “hello” in it and encrypted with “password” as the key just to see what output was generated.

# echo hello > test.txt
# ./bcrypt -r test.txt
Encryption key:
Again:

# hexdump -C test.txt.bfe
00000000  54 01 7a 73 0e 2e 64 0a  fa 15 34 61 49 b3 be 33  |T.zs..d...4aI..3|
00000010  65 6f 17 d7 9b 60 91 77  10 27 49 e1 42 fc 8a b1  |eo...`.w.'I.B...|
00000020  43 fa 6a fa 13 ea 0e 5d  39 8a d7 7d 95 9a d1 e4  |C.j....]9..}....|
00000030  06 c3 be e8 9e 0c ec 4b  7d 67 ec 6a fc db 2f 95  |.......K}g.j../.|
00000040  81 58 b2 a5 f4 c7 8c 94  84 6e 06 00 00 00        |.X.......n....|

Hmmm…78 bytes for 6 bytes of plaintext, that’s odd!
The first 2 bytes are “tags”; options which indicate the endianess and whether compression is used.

#define BIG_ENDIAN    0x45
#define LITTLE_ENDIAN 0x54

The second byte can be either TRUE (Compressed) or FALSE (not compressed)
The remaining data is ciphertext although it looks slightly bloated for small string like “hello” so I’ve passed the same file again this time without compression.

00000000  54 00 f3 d9 e9 41 1c b4  0e 96 17 d7 9b 60 91 77  |T....A.......`.w|
00000010  10 27 49 e1 42 fc 8a b1  43 fa 6a fa 13 ea 0e 5d  |.'I.B...C.j....]|
00000020  39 8a d7 7d 95 9a d1 e4  06 c3 be e8 9e 0c ec 4b  |9..}...........K|
00000030  7d 67 ec 6a fc db 2f 95  81 58 b2 a5 f4 c7 8c 94  |}g.j../..X......|
00000040  84 6e                                             |.n|

It’s slightly smaller than before at 66 bytes but what’s really weird is the excess bytes are almost the exact same as when compression is used.

The utility calls compress() function in Zlib directly so I pass the file through this separately and dump the results.

# ./comp_test test.txt

Read size = 6
Compressed size = 14

# hexdump comp.bin -C
00000000  78 9c cb 48 cd c9 c9 e7  02 00 08 4b 02 1f        |x..H.......K..|

Only 14 bytes.
I then try an empty file without compression.

# touch test_file.txt
# ./bcrypt -r -c test_file.txt
Encryption key:
Again:

# hexdump -C test_file.txt.bfe
00000000  54 00 69 58 11 36 9e a7  69 1c c8 b8 62 6c 3d f0  |T.iX.6..i...bl=.|
00000010  6e 87 3c 3b c4 59 7e 77  12 88 c8 40 6b 31 98 36  |n.<;.Y~w...@k1.6|
00000020  41 61 85 c4 1f e2 9a 06  36 09 65 c9 63 c8 7a 37  |Aa......6.e.c.z7|
00000030  11 db 92 b5 6d 44 87 be  25 53                    |....mD..%S|

58 bytes for an empty file! :|
After looking in the source code files again, a 56-byte key is attached to plaintext/compressed data before being encrypted.

Generation (summary)

  1. mutateKey() in keys.c takes a password of 8 or more characters and produces 2 56-byte keys, 1 in little endian format, the other in big format.
  2. If compression is used, readfile() in rwfile.c will take the entire contents of input file and pass to compress() function (part of Zlib)
  3. A 56-byte key generated in step 1 is appended to compressed data using attachKey() Null bytes are used as padding if required.
  4. BFEncrypt() in wrapbf.c invokes blowfish functions to encrypt data + key.
  5. If compression is used, the original file size is appended and data is saved to file with BFE extension.

The first problem I see with this app is the storage of encrypted key, it is even stored when there is no data in the original file…

The author does this to verify successful decryption but what it also does is provide a reliable way to recover original password.

Integrity of data is important of course but a hashing algorithm like SHA-256 would be much more suitable for verification process.

There’s also the Zlib signature [ 0x78, 0x9c ] as a chosen plaintext attack but only if the file’s compressed.

Here is snippet of the code from BFDecrypt() that verifies successful decryption.

  sz -= MAXKEYBYTES;

  if (memcmp(*input+sz, mykey, MAXKEYBYTES) != 0)
    return(0);

In attachKey() part of rwfile.c copies the encryption key to the end of the file data.

  memcpy(*input+sz, key, MAXKEYBYTES);
  sz += MAXKEYBYTES;

Recovery

Using the authors own code and some hardcoded values, it’s possible to create a verification routine for demonstration purposes.

Please note this was tested only on x86 hardware. — feel free to donate one of these :)

    char password[] = "password";
    unsigned char ciphertext[] = { 0x69, 0x58, 0x11, 0x36,
                                   0x9e, 0xa7, 0x69, 0x1c };

    unsigned char newkey[MAXKEYBYTES];

    uInt32 L, R;
    BLOWFISH_CTX ctx;
    int i, j;

    j = sizeof(uInt32);

    // create initial key
    Blowfish_Init(&ctx, password, strlen(password));

    memcpy(&L, &password[0], 4);
    memcpy(&R, &password[4], 4);

    // create new 448-bit key
    for (i = 0; i < MAXKEYBYTES; i += sizeof(uInt32) * 2) {
      Blowfish_Encrypt(&ctx, &L, &R);

      memcpy(newkey + i,     &L, j);
      memcpy(newkey + i + j, &R, j);
    }

    // create the decryption/encryption key for file data
    Blowfish_Init(&ctx, newkey, MAXKEYBYTES);

    memcpy(&L, &newkey[0], 4);
    memcpy(&R, &newkey[4], 4);

    // encrypt 64-bits of newkey
    Blowfish_Encrypt(&ctx, &L, &R);

    // compare encrypted result with 64-bits of encrypted key
    if (!memcmp(&L, ciphertext, 4)) {
      printf("\nKey is correct\n");
    } else {
      printf("\nKey is incorrect\n");
    }

The ciphertext used here is from test_file.txt.bfe and works fine, displaying “Key is correct” :)

I wanted to test the same routine using OpenSSL in hopes of achieving performance boost, here’s the structure/defined tags.

typedef struct _BFE_HDR {
  u_int8_t arch;
  u_int8_t compressed;
} BFE_HDR, *PBFE_HDR;

#define BIG_ENDIAN    0x45
#define LITTLE_ENDIAN 0x54

#define MIN_PASS_LEN 8
#define MAX_PASS_LEN 56

A function to read the encrypted key from BFE file.

bool read_bfe_key(char bfe_file[], u_int8_t bfe_key[]) {
  bool valid = false;
  struct stat fs;

  if (stat(bfe_file, &fs) == 0) {
    // should be at least equal to or more than 58 bytes
    if (fs.st_size >= MAX_PASS_LEN + sizeof(BFE_HDR)) {
      // if it's exactly 58 bytes, there's no encrypted data
      // we continue with crack anyway since the encrypted
      // key is what we're attacking.
      if (fs.st_size == MAX_PASS_LEN + sizeof(BFE_HDR)) {
        printf("\n  WARNING: Size of file indicates no encrypted data.");
      }

      // open and read header
      FILE *fd = fopen(bfe_file, "rb");

      if (fd != NULL) {
        BFE_HDR hdr;
        size_t readSize = fread(&hdr, 1, sizeof(BFE_HDR), fd);

        if (readSize == sizeof(BFE_HDR)) {
          // big endian format unsupported
          // hdr.arch == BIG_ENDIAN ||
          if ((hdr.arch == LITTLE_ENDIAN) &&
              (hdr.compressed == 1 || hdr.compressed == 0)) {

            // allocate memory for read
            u_int8_t *bfe_data = (u_int8_t*)malloc(fs.st_size);

            if (bfe_data != NULL) {
              readSize = fread(bfe_data, 1, fs.st_size, fd);

              // if file was compressed before encryption
              // skip the original size value
              if (hdr.compressed == 1) {
                readSize -= sizeof(u_int32_t);
                u_int32_t origSize;

                memcpy(&origSize, &bfe_data[readSize], sizeof(u_int32_t));

                printf("\n  File is compressed."
                       "\n  Original size : %i bytes", origSize);
              } else {
                printf("\n  No compression used."
                       "\n  Original size : unknown");
              }

              // read encrypted key
              for (int i = MAX_PASS_LEN - 1;i >= 0;i--) {
                bfe_key[i] = bfe_data[--readSize];
              }

              valid = true;
              free(bfe_data);
            }
          } else {
            printf("\n  WARNING: Unrecognised BFE header"
                   " - Endian flag: %#02x", hdr.arch);
          }
        }
        fclose(fd);
      }
    }
  }
  return valid;
}

The OpenSSL based function to test if password is valid key.

bool is_valid_key(char password[], u_int8_t bfe_key[]) {
  char *p;
  size_t pass_len;
  u_int8_t newkey[MAX_PASS_LEN + 8] = {0};

  BF_LONG buf1[2], buf2[2];
  BF_KEY key;

  if ((p = strchr(password, 'n')) != 0) *p = 0;
  if ((p = strchr(password, 'r')) != 0) *p = 0;

  pass_len = strlen(password);

  if (pass_len >= MIN_PASS_LEN) {
    memcpy(&buf1[0], &password[0], sizeof(BF_LONG) * 2);
    memcpy(&buf2[0], &bfe_key[48], sizeof(BF_LONG) * 2);

    // 1. create blowfish key from password string
    BF_set_key(&key, pass_len, (u_int8_t*)password);

    // 2. create 56-byte key encrypting 64-bits of password string
    for (int i = 0; i < MAX_PASS_LEN; i += sizeof(BF_LONG) * 2) {
      BF_encrypt(buf1, &key);
      memcpy(&newkey[i], &buf1[0], sizeof(BF_LONG) * 2);
    }

    // 3. create blowfish key from 56-byte key
    BF_set_key(&key, MAX_PASS_LEN, newkey);

    for (int i = 0;i < 8;i++) {
      memcpy(&buf1, &newkey[48 + i], sizeof(BF_LONG) * 2);
      BF_encrypt(buf1, &key);

      // if buffers match, we've found key
      if (buf1[0] == buf2[0] && buf1[1] == buf2[1]) {
        return true;
      }
    }
  }
  return false;
}

The program basically reads encrypted key from *.BFE file, then sequentially reads from a list of words, each one processed with is_valid_key(). Since the keys are 8 characters or more, I didn’t think it was necessary to use some brute force algorithm.

Using example file provided on authors site.

# crack_bfe littleendian.bfe words.txt
  ...
  File is compressed.
  Original size : 1725 bytes

  found key: "eggheads"

  3 seconds elapsed - k/s: 19925

Even on an empty file described earlier, it finds the key..

# crack_bfe empty.txt.bfe words.txt
  ...
  WARNING: Size of file indicates no encrypted data.
  No compression used.
  Original size : unknown

  found key: "password"

The speed is a little disappointing but it does use BF_set_key() twice which internally uses BF_encrypt() a lot and so the key setup accounts for most of time testing key.

Due to the design of Blowfish, it’s unlikely you would achieve a huge performance boost on latest GPU.

For the average joe, a decent password generator should be enough to recover most passwords.

Conclusion

bcrypt is no longer maintained, has some bugs / design flaws and there are much better alternatives available.

Okay, the BFE files are relatively safe providing the initial password is strong but perhaps there are bigger weaknesses in blowfish not publicly known. (not always governments that know of secret weaknesses)

I’d recommend a more robust application like FileEncrypt or indeed 7Zip as alternatives. Both offer more security and functionality.

4 thoughts on “Password Algorithms: bcrypt File Encryption

    • Again, its dietrich who posts the crypto. I stick with my appsec and exploits, he does the awesome cryptanalysis.

      ~making sure credit given where due!!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>