BestCrypt IV generation flaw

Created: 23 October 2003
Last Update: 7 November 2003

Vulnerable versions

Windows: all versions prior to 7.10 (released on 3 November 2003)
Linux: all versions prior to 1.3 (released on 5 November 2003)

Intro

Because I was not satisfied entirely with available hard disk encryption software, I started to work on my own. I've beginned to investigate in more detail their inner workings, so that I can see if I am good enough to do one.

Please don't believe that I want to discredit this software. In my opinion is the best hard disk encryption software around, I use it every day and I will continue to use it (maybe because I don't need hidden containers which are made vulnerable by this attack). The source code is partialy available, which made this discovery possible. Other encryption software could also be vulnerable to this attack, or some other one, but it is hard to find out without access to their source code.

The problem

When looking through BC encryption drivers, one thing puzzled me. They are free to implement whatever cipher algorithm or encryption mode they want. To make sure that 2 different sectors yield a different cipher text even if the plain texts are identical, the virtual disk driver passes to the encryption driver an IV (initialization vector) seed which is different for every sector on the disk. From this seed most encryption drivers derive with the help of a random pool (which depends on the encryption key) an IV which is used by CBC. The IV seed is nothing more than the sector number of the sector which is being encrypted. This algorithm is safe if all the IV seeds are different and the derivation method is one way (so that you can not find the key if you know the IV). I cannot comment on the derivation method, but the IV seed is definitively flawed.

The problem is that only the lower 16 bits of the sector number are used, which means that every two sectors which are 65536 sectors apart (32 MB) are encrypted with the same IV. Did they forget to change this when going from MS-DOS to Win32? Did they keep it for compatibility reasons? I don't know.

Even if this flaw does not give access to the encrypted data, it can reveal some interesting information about the data inside. In particular, it can aid an attacker to make a more or less informed guess about whether there is a hidden-container inside the normal one, and also to estimate it's size!!!!

I want to point out that not all containers are vulnerable to this attack, as this requires couples of sectors set at distances of a multiple of 32 MB to contain the same data (it is not required that all 512 bytes be identical, it is enough that N bytes coincide, where N is the block size in bytes of the cipher used). However, this happens quite often. If we consider the Rijndael cipher, with a 16 byte block size (as it is implemented in BC), it is enough for the two sectors to contain an PE file (Win32 EXE format) generated by the same compiler (so that the MS-DOS EXE stub coincide). But 90% of Win32 exe's are built by VC++. Or it's enough for two sectors to contain two BMP of the same size (like wallpapers). There are many file formats which have the first 16 bytes more or less constant.

BestCrypt container analyzer

You can download from this page a Win32 Console application which scans a BC container and prints out every "slice" which contains identical sectors. By slice starting at sector N I understand all the sectors starting at sector N, set 65536 sectors apart.

The slice starting at sector 2 contains the following sectors:

2 + 0 * 65536 = 2
2 + 1 * 65536 = 65538
 ...
2 + K * 65536 =
 ...

This program reads all the slices (there are 65536 slices, starting from sector 0 to sector 65535) from one BC container and looks for duplicate cipher texts, which implies that the plain texts are also identical.

If in one slice it finds duplicate sectors, it print's a line like the folowing:

 2892 .0..0....00..110.1..22
 2894 ....00................
                111111111122 - the slice sector index (read top-down)
      0123456789012345678901

This line gives us the folowing information:

Sectors (or the 'compare byte count' first bytes of these sectors)
2892 +  1 * 65536
2892 +  4 * 65536
2892 +  9 * 65536
2892 + 10 * 65536
2892 + 15 * 65536 are identical (these are the sectors marked with 0).

Sectors (or the 'compare byte count' first bytes of these sectors)
2892 + 13 * 65536
2892 + 14 * 65536
2892 + 17 * 65536 are identical (these are the sectors marked with 1).

Sectors (or the 'compare byte count' first bytes of these sectors)
2892 + 20 * 65536
2892 + 21 * 65536 are identical (these are the sectors marked with 2).

Sectors (or the 'compare byte count' first bytes of these sectors)
2894 + 14 * 65536
2894 + 15 * 65536 are identical (these are the sectors marked with 0).

Note that this not implies that the identical sectors from slice 2892 marked with 0 and the ones also marked with 0 from slice 2894 are identical together. They could be identical, and usually are, but this is not necessarly true. All we can prove for sure is that sectors from one slice are identical in between them or not.

Hidden containers

Create a big enough disk (200 MB should do). In special cases (both containers are zeroed), the minimum size for this demonstration to work is 65 MB (2 * 32 + some sectors).

Fill half of it, then delete some files (to create some fragmentation).

Wipe the free space with zeros (this is required because BC fills it initially with pseudo-random data which blocks this program; be warned that some wipe programs don't let you set the wipe value; Eraser is one that does). You may say that this proves that this attack is innefective against real world use, because it requires special conditions. But no matter what information is stored inside, it should be computationally infesible to gain information about it. Even if all the disk contains noting but zeroed sectors, we should not be able to find this out without the proper key.

Dismount the container, and run BCAnalyze on it (with a 512 compare byte count)

Here's some of the output I got:

BCAnalyze test.jbc 512

  768 0...000
  769 0.0.000
  770 0.0.000
  771 0.0.000
  772 0...000
  773 0.0.000
  774 0.0.000
  775 000.000
  776 0...000

  863 ..0.000
  864 ....000
  865 ....000

 1729 ....000
 1732 ....000
 1733 ....000

The last three 000 indicate the free space from the disk end (as you can see, they represent approximatively 3/7 = 42% of the disk space). The few 0's from the top are the places where the deleted files were.

Now create a hidden container of 70 MB.

Fill half of the hidden container and then wipe the free space with zeros (or any other constant), just like in the first case.

Run the analyzer again.

BCAnalyze test.jbc 512
    0 .....00
    1 .....00
    2 .....00
    3 0...011
    4 0...011
    5 0...011
    6 .....00
    7 .....00
    8 .....00
    9 0...011
   10 0...011
   11 0...011
   12 .....00
   13 0...011
   14 0...011

   93 .....00
   94 .....00
   95 .....00
   96 .....00
   97 0...011
   98 .....00
   99 .....00

  768 0...0..
  769 0.0.0..
  770 0.0.0..
  771 0.0.0..
  772 0...0..
  773 0.0.0..
  774 0.0.0..
  775 000.0..
  776 0...0..

  863 ..0.0..

 3971 ..0.0..
 3972 ..0.0..

 4018 .0..0..
 4019 .0..0..
 4049 .0..0..
 4050 .0..0..
 4051 .0..0..

IMPORTANT: This is where the shift happens.

As you can see, last two characters from the lines above seem to be in the same state much of the time. This is because they are encrypted with another set of keys (the hidden container ones). From now on, the last three characters will display this behavior. This happens because some slices in the container (starting from some sector) have a different number of sectors than others, because the hidden container size is usually not divisible by 32 MB. If it were, then this would not happen.

The split position allows us to aproximate the size of the hidden container

 4099 ....0.0
 4100 ....0.0
 4101 ....0.0
 4105 ....0.0
 4106 ....0.0

 4126 ....0.0
 4127 ....0.0
 4129 .00....
 4130 .00....
 4131 .00....
 4132 .00....
 4134 .00....
 4135 .00....
 4136 .00....
 4137 .00....
 4138 .00....
 4139 .00....

 4892 ....0.0
 4893 ....0.0
 4894 ....0.0
 4895 ..001.1
 4896 ....0.0
 4897 ....0.0
 4898 ....0.0
 4899 ..001.1
 4900 ....0.0
 4901 ....0.0
 4902 ....0.0
 4903 ....0.0

The formula to aproximate the hidden container size

HiddenContainerSize = ContainerSize - DataOffset - (ShiftSector - 1 + SliceIndex * 65536) * 512

ContainerSize is the size in bytes of the file which contains the normal and the hidden container.
DataOffset is displayed by the program at start (usually is 2048).
ShiftSector is the sector starting from where the pattern of the last charachters change. This sounds very weird, I don't know how to explain it. But when you'll look at the console spitting lines like the one above, it should be easy to see where this happens. This is very easy on XP, if you change the console buffer size to a bigger value (2000 lines) and then from time to time pause the program (Pause key) and then scroll through the output. You can unpause the program by pressing Enter. The accuracy of the determination of HiddenContainerSize depends on how accurate this value is determined.
SliceIndex is the index (character position starting from 0) of the first entry after the shift.

HiddenContainerSize = 209715200 - 2048 - (4099 - 1 + 4 * 65536) * 512 = 73397248 bytes = 69.997 MB

Quotes from BestCrypt help file

So what can we do? Let us imagine that we use steganography, but we hide the encrypted containers inside BestCrypt containers themselves rather than inside graphic files. Now we'll get two kinds of containers: original and hidden (which are stored inside the original containers). Using this kind of steganography, BestCrypt is far superior to the conventional sound or graphic method of steganography, because:
- performance of the hidden containers is the same as of the original ones;
- hiding containers in this way does not waste unnecessary space, so it will not require as much disk space;
- the potential intruder cannot prove whether or not an additional (hidden) container exists.

The hidden part is stored inside part 3 of the original container without its own Key Data Block, so it is impossible to define the borders of the hidden part inside the original container.

They are still right, it's impossible to prove, but in some cases (if the file has many identical sectors) you can compute a probability of how likely it is for a hidden container to be there, and when multiple files have the same probability, this looks good enough for me, and probably also for any judge living in UK.

Download

This software was only tested with containers encrypted with the Rijndael and SHA-1 modules, but it should work with all ciphers delivered with BC.

Download
BCAnalyze.zip - 31 KB (7 November 2003 - includes source code and this file)