AES-Encryption Experimente

Winfried Mueller, www.reintechnisch.de, Start: 21.03.2005

Unter Linux gibt es derzeit hauptsächlich 2 Möglichkeiten, starke Verschlüsselung ins System einzubauen. Eine davon ist loop-aes von Jari Ruusu. Es benutzt standardmäßig AES (Rijndael Algorithm) als Verschlüsselungs-Algorithmus, welcher noch recht jung (2001 Standard) ist und als sehr sicher gilt. Neben loop-aes gibt es auch noch ein Werkzeug namens aespipe, welches man z.B. wunderbar zum verschlüsseln von Backup-Archiven einsetzen kann:

Verschlüsseln 

 
# tar -cvzf myfile.tgz mydir
# aespipe -p3 <myfile.tgz >myfile.tgz.ap 3</etc/mypass

Entschlüsseln 

 
# aespipe -d -p3 <myfile.tgz.ap >myfile.tgz 3</etc/mypass

So verschlüsselte Backups sind eine feine Sache, denn die Daten darauf sind ziemlich sicher vor Missbrauch. In Sachen Datensicherung ist es jedoch immer eine gute Idee, wenn man mehrere Möglichkeiten hat, die Daten wieder herzustellen. So entstand die Idee, über ein Ruby Skript die Daten solcher Archive wieder zu entschlüsseln, völlig unabhängig von aespipe. Auch wollte ich mich damit überzeugen, ob aespipe wirklich ein standardisiertes AES benutzt.

Die Experimente der letzten Tage waren zuerst wenig fruchtbar. Ich musste tief in den Code von aespipe abtauchen, um mir Informationen über den Algorithmus zu holen. Ich hab einiges an Unterlagen zu sha, aes und Verschlüsselung gelesen. Nach 2 Tagen jedoch klappten erste Versuche, noch sah alles sehr kompliziert aus und ich hatte die Krypto-Bibliotheken überall gepatcht. In den nächsten Tagen wurde alles viel einfacher, bis zum Schluß ganz einfache Programme entstanden. So ist es oft, es hört sich leicht an, wird dann kompliziert, um dann, wenn man es verstanden hat, wieder leicht zu werden.

Details

Für AES-Unterstützung unter Ruby fand ich 3 Möglichkeiten ruby-aes, aes-rb und die openssl Bibliothek. Interessant fand ich ruby-aes, weil es reiner Rubycode ist. Das gefiel mir, weil ich so den Code besser verstehen konnte. Ruby liest sich einfach besser, als C. Andererseits bedeutet es völlige Plattform-Unabhängigkeit. Man muss nichts kompilieren oder ist auf Leute angewiesen, die einem die Binärpakete bauen. Man braucht nur den Ruby-Interpreter und kann loslegen. Gerade wenn es darum geht, eine immer funktionierende Möglichkeit zu haben, verschlüsselte Backuparchive zu entschlüsseln, ist das ein Argument.

Am einfachsten installiert man sich ruby-aes manuell. Das Installationsskript tat nämlich zu diesem Zeitpunkt nicht. Im Verzeichnis alg/optimized muss man hierzu zuerst aes_gencons.rb aufrufen, damit aes_cons erzeugt wird. Dann kopiert man die 3 Dateien aes_cons.rb, aes_alg.rb und api/aes.rb in ein Bibliotheksverzeichnis, z.B. unter ein neues Verzeichnis extern/aes. Weil wir so die Verzeichnisse verschoben haben, müssen wir noch die require-Zeilen in aes-alg.rb und aes.rb anpassen. Damit sollte dann ruby-aes verfügbar sein.

Zum aespipe Alogrithmus muss man wissen, dass er etwas vom Standard abweicht, was aber bedeutende Vorteile hat. AES ist so aufgebaut, dass immer Blöcke von 16 Byte verschlüsselt werden. Normal wird der erste Block mit einem Initialisierungs-Vektor (iv) XOR verknüpft und alle folgenden Blöcke XOR mit dem Ergebnis des vorher verschlüsselten Blockes. Das bedeutet, dass jeder Block vom vorherigen abhängt. Würde man so ein Archiv verschlüsseln, könnte man nichts nach einem Bitfehler/defekten Sektor wieder herstellen. Auch könnte man nicht wahlfrei auf einen Sektor zugreifen, wie es loop-aes ja braucht, man müsste immer erst alles entschlüsseln. Deshalb geht aespipe anders vor. Jeder 512 Byte Sektor bekommt einen neuen definierten Intialisierungsvektor. Dieser ist einfach die Sektornummer. Sektor 1 wird also mit 0x00001 ver-xort, Sektor 255 mit 0x000ff. Sicherheitstechnisch ist dieses Vorgehen wichtig. Würde man z.B. für iv immer 0x00 verwenden, würden alle Sektoren, die im entschlüsselten Zustand den gleichen Inhalt haben, auch verschlüsselt identisch sein. Damit könnte man Rückschlüsse auf den entschlüsselten Inhalt ziehen. Wenn aber nur ein Bit unterschiedlich ist, was durch iv passiert, ist der komplette Block völlig andersartig und man kann diese Rückschlüsse nicht mehr ziehen.

Die größte Verwirrung bei der Umsetzung stiftete bei mir immer wieder die unterschiedliche Sichtweise von Integer und Strings. Die Ruby Implementierung nutzt nämlich Strings, um Key, Startvektor und Datenblock aufzunehmen. Hierbei muss man sich klar machen, dass s[0] nicht das niedrigste Byte ist sondern das höchste Byte. 

 
s = "\xff\x00"  # >> ist nicht 0xf0 sondern 0x0f

Nachdem alle Probleme umschifft waren, stellte sich große Ernüchterung ein: Es gab ein konzeptionelles Problem, was Performance hieß. Skriptsprachen sind nunmal nicht geeignet, um sehr maschinennahe Algorithmen zu implementieren. Hier bezahlt man für den Komfort ganz krass mit Schneckentempo.

Wo aespipe auf einer 200 MHz Maschine ein 100 MB Archiv in 30 Sekunden erzeugt (ca. 3.4 MB/s), brauchte mein Ruby Programm 28 Stunden (!), also ungefähr 1KB/s. Das erinnerte mich an Download-Raten aus dem Internet vor 10 Jahren. Das Ruby Programm ist also etwa 3500 mal langsamer, als der recht optimierte C-Code.

Man muss dazu sagen, dass ruby-aes nicht sonderlich auf Geschwindigkeit optimiert ist, es war wohl eher ein experimenteller Versuch, AES in purem Ruby umzusetzen und den Code ordentlich strukturiert und leserlich zu halten. Ein Lehrbeispiel sozusagen.

Ein wenig optimieren konnte ich ihn mit recht einfachen Mitteln, was aber nur ca. 20-30 % Performance brachte. Ich vermute, dass man maximal nochmal Faktor 2-3 rausholen kann, was aber einfach viel zu wenig ist. Hier muss man wirklich sagen, dass pur Ruby dann nicht geht, wenn man größere Mengen zu verschlüsseln hat.

Gut nutzbar ist der Code jedoch, wenn es darum geht, kleinere Menge im KB-Bereich zu verschlüsseln.

Für meinen Zweck, ein Werkzeug zu haben, womit ich Backup-Archive entschlüsseln kann, ist es zumindest eine gute Notlösung, wenn mal nichts anderes verfügbar sein sollte.

Den folgenden Code habe ich sowohl unter Windows wie unter Linux getestet. Dabei habe ich mehrere Backuparchive mit aespipe verschlüsselt und mit den Rubyprogrammen entschlüsseln. Auch umgedreht. Die Archive hatten die Größe von 10 KB-100 MB.

Nochwas in Sachen Schlüssel: aespipe nutzt in der Standardeinstellung SHA-256 als Schlüssel, genau genommen nur die oberen 128 Bit. Aus dem Passwort wird also über die Hashfunktion der Schlüssel erzeugt.

Zu aespipe muss man noch wissen, dass konzeptbedingt die Dateien immer um Vielfache von 16 Byte lang sein müssen. Ein Inputfile wird mit Null-Bytes aufgefüllt, wenn es dem nicht entspricht. Beim entschlüsseln hat man dann ein um ein paar Bytes längeres File. Bei tgz-Archiven ist das kein Problem, weil gzip sowas verwirft. Bei anderen Anwendungen sollte man dies aber bedenken. Möchte man mehr Komfort, muss man sich ein Protokoll darüber basteln, was die raw-Daten nochmal verpackt. So etwas findet man schon fertig als Skript im aespipe-Paket.

Andere Wege

Ich denke, dass die openssl Bibliothek bald zum Standard in Ruby gehört. Openssl dürfte, soweit ich das verstanden habe, AES-Verschlüsselung können. Leider ist die Dokumentation von openssl unter Ruby derzeit sehr schlecht bzw. nahezu nicht vorhanden. Die Verwendung von openssl sollte aber eine gute Basis sein, weil einfach zu erwarten ist, dass dies eine langfristig stabil verfügbare Bibliothek sein wird, auf allen Plattformen.

Benutzung der Programme

 
Verschlüsseln:
# ruby encrypt_std.rb myfile

#
# -> erzeugt myfile.raes 
#

Entschlüsseln:
# ruby decrypt_std.rb myfile.raes

# -> erzeugt myfile.raes.d, welches identisch mit myfile sein sollte, 
#    mit Ausnahme einiger evtl. angehängter Null-Bytes

Quellcode

Encrypt

 
require 'digest/sha2'
require 'extern/aes_orig/aes'

# encrypt_std.rb              Version: 2005/03/21
#
# aespipe/loop-aes Encryption with ruby-aes source
#   - for aespipe defaults: SHA-256 Passwort->Key, 
#     AES-128 Encryption
#   - slow: 450 MHz Machine: 1.6 KB/s
#   - pure ruby Code, no external C-Lib
#   - tested on Ruby 1.8.2 Windows & Linux
#   - aespipe/loop-aes see: http://sourceforge.net/projects/loop-aes/
#   - ruby-aes see: http://raa.ruby-lang.org/project/ruby-aes/ 
#
#
# Winfried Mueller, www.reintechnisch.de, Public Domain


class AES_IV_Gen

  def initialize
    @iv = "\x00"*16
    @ivCounter = 0
    @devSect = 0
  end

  def set( value )
    raise if value.length != 16
    @iv = value
  end

  def get_next!
    @iv = int2str16r( @devSect )        
    @devSect += 1
    @iv
  end

  def int2str16r( value )
    r = ""
    16.times do 
      b = value & 0xFF
      r << b.chr
      value = value / 0x100
    end
    r
  end
  protected :int2str16r

end

class ProgressBar
  def initialize
    @count = 0
  end
  def trigger
    @count += 1
    print "."
    if @count % 16 == 0
      printf( " (%8.8d KB)\n", @count / 2 )
    end
    $stdout.flush
  end
  def sum
    puts
    printf( "Sum              (%8.8d KB)\n", @count / 2 )
  end
end

in_file = ARGV[0]

print "Passwort: "
pass = ""
pass = $stdin.gets
pass.chomp!

d = Digest::SHA256.new

d << pass
key = d.digest[0..15]

iv = AES_IV_Gen.new

out_file = in_file + ".raes"
f_out = File.open( out_file, "w+b" )

puts "Infile:  #{in_file}"
puts "Outfile: #{out_file}"

pb = ProgressBar.new

File.open( in_file, "rb" ) do |f|
  while (buf = f.read( 512 ))
    pdl = buf.length % 16
    if pdl != 0
      buf = buf << "\x00"*(16-pdl)
    end
    iv_next = iv.get_next!
    ctext = Aes.encrypt_buffer(128, 'CBC', key, iv_next, buf)
    ctext.chop!        #delete padding length trailer
    f_out.print ctext
    pb.trigger
  end
end

pb.sum
f_out.close

Decrypt

 
require 'digest/sha2'
require 'extern/aes_orig/aes'

# decrypt_std.rb              Version: 2005/03/21
#
# aespipe/loop-aes Decryption with ruby-aes source
#   - for aespipe defaults: SHA-256 Passwort->Key, 
#     AES-128 Encryption
#   - slow: 450 MHz Machine: 1.6 KB/s
#   - pure ruby Code, no external C-Lib
#   - tested on Ruby 1.8.2 Windows & Linux
#   - aespipe/loop-aes see: http://sourceforge.net/projects/loop-aes/
#   - ruby-aes see: http://raa.ruby-lang.org/project/ruby-aes/ 
#
#
# Winfried Mueller, www.reintechnisch.de, Public Domain

class AES_IV_Gen

  def initialize
    @iv = "\x00"*16
    @ivCounter = 0
    @devSect = 0
  end

  def set( value )
    raise if value.length != 16
    @iv = value
  end

  def get_next!
    @iv = int2str16r( @devSect )        
    @devSect += 1
    @iv
  end

  def int2str16r( value )
    r = ""
    16.times do 
      b = value & 0xFF
      r << b.chr
      value = value / 0x100
    end
    r
  end
  protected :int2str16r

end

class ProgressBar
  def initialize
    @count = 0
  end
  def trigger
    @count += 1
    print "."
    if @count % 16 == 0
      printf( " (%8.8d KB)\n", @count / 2 )
    end
    $stdout.flush
  end
  def sum
    puts
    printf( "Sum              (%8.8d KB)\n", @count / 2 )
  end
end


in_file = ARGV[0]

print "Passwort: "
pass = ""
pass = $stdin.gets
pass.chomp!

d = Digest::SHA256.new

d << pass
key = d.digest[0..15]

iv = AES_IV_Gen.new

out_file  = in_file + ".d"
f_out = File.open( out_file, "w+b" )

puts "Infile : #{in_file}"
puts "Outfile: #{out_file}"

pb = ProgressBar.new

File.open( in_file, "rb" ) do |f|
  while (buf = f.read( 512 ))
    pdl = buf.length % 16
    raise if pdl != 0
    iv_next = iv.get_next!
    buf <<= "\x00"  #add padding length trailer
    ctext = Aes.decrypt_buffer(128, 'CBC', key, iv_next, buf )
    f_out.print ctext
    pb.trigger
  end
end

pb.sum
f_out.close

Ruby-aes Paket

Weblinks

Openssl-Version (Ergänzung 16.05.2005)

Nun ist auch eine Openssl Version entstanden, die schnell genug ist, um sie produktiv zu nutzen. Auf einem 450 MHz Windows-Rechner erreicht sie einen Datendurchsatz von etwa 1MB/s.

In der openssl-Version habe ich decrypt und encrypt zu einem Programm namens rcrypto zusammengefasst. Ein Problem gibt es unter Debian woody. Die Ruby 1.8.2er Backports setzen auf eine alte openssl-Version auf, die noch kein AES kennt. Mit einer Debian Sarge sollte es dagegen funktionieren.

Im Code wurde eine Bibliothek für die Passworteingabe included, damit man diese nicht als externe Bibliothek nachladen muss. Damit ist es nun möglich, Passwörter verdeckt einzugeben.

Interessant an der openssl Bibliothek ist, dass einem damit auch andere Cipher zur Verfügung stehen, z.B. des, des3, blowfish (bf), rc4, cast, rc2. Durch minimale Anpassungen kann man mit dem Programm also auch diese Algorithmen verwenden, z.B. auch konfigurierbar über eine Kommandozeilenoption.

Wie optimiert man das Programm? Bei 10 MB gehen bei einem 450 MHz Rechner etwa 8 Sekunden zu Lasten des File-IO und nur 3 Sekunden braucht die Verschlüsselung und Neuberechnung des IV. Die Verschlüsselung selber schafft etwa 8,5 MB pro Sekunde, wenn man den IV nicht neu lädt. Man kann also einiges rausholen, wenn man das File-IO optimiert. Dafür müssen viel größere Blöcke eingelesen werden. Der Blockbuffer muss dann aber in 512Byte großen Stücken verschlüsselt werden, weil ja der IV immer wieder neu gesetzt werden muss. Rausgeschrieben werden sollte dann ebenfalls ein größerer Block. Auch die Berechnung des IV lässt sich noch gut optimieren und dürfte einiges bringen.

Nachtrag 18.11.2016: Getestet mit Ubuntu 16.04. Funktioniert noch ohne Änderung. 

 
#!/usr/bin/env ruby
#
# This file is automatically generated. DO NOT MODIFY!
#

# rcrypto.rb File AES-Encryption and Decryption
#            (same algo as aespipe)
# 
# Copyright (C) 2005, Winfried Mueller, www.reintechnisch.de
# License: GPL
# 
#

State   = "Experimental"
Version = "2007/01/01"
DEBUG = true

require 'optparse'
require 'ostruct'
require 'digest/sha2'
require 'openssl'


# ========== begin include wmclasslib/passwd ==========

case RUBY_PLATFORM.downcase
  when /mswin32/, /mingw32/, /cygwin/, /bccwin32/
    require 'Win32API'
    def get_passwd( char=nil, prompt=nil, char_range=0x20..0x7F )
      getch = Win32API.new("msvcrt", "_getch", [], 'L')
      prompt ||= "Password: "
      STDERR.print prompt
      passwd = ""

      loop do
        c = getch.Call
        case c
          when 0x0d
            break
          when char_range
            passwd << c.chr
            if char
              STDERR.print char
            end
          when 0x08
            if passwd.length != 0
              STDERR.print "\x8" # BS backspace
              STDERR.print " "
              STDERR.print "\x8"
              passwd.chop!
            else
              STDERR.print "\x7" # BEL
            end
          else
            STDERR.print "\x7" # BEL if not allowed char
        end
      end
      STDERR.print "\n"

      passwd
    end
  when /linux/, /freebsd/, /bsd/, /solaris/, /hpux/, /powerpc-darwin/
    def get_passwd( char=nil, prompt=nil, char_range=0x20..0x7F )
      #char output not supported
      prompt ||= "Password: "
      STDERR.print prompt
      passwd = ""
      begin
        system "stty -echo"
        passwd = $stdin.gets.chomp
      ensure
        system "stty echo"
      end
      STDERR.print "\n"
      passwd.each_byte do |c| 
        unless char_range === c
          raise "password character out of range"
        end
      end
      passwd
    end
  else
    raise "unsupported platform"
end
# ========== end include wmclasslib/passwd ==========



class AES_IV_Gen

  def initialize
    @iv = "\x00"*16
    @ivCounter = 0
    @devSect = 0
  end

  def set( value )
    raise if value.length != 16
    @iv = value
  end

  def get_next!
    @iv = int2str16r( @devSect )        
    @devSect += 1
    @iv
  end

  def int2str16r( value )
    r = ""
    16.times do 
      b = value & 0xFF
      r << b.chr
      value = value / 0x100
    end
    r
  end
  protected :int2str16r

end

class ProgressBar
  DIV_MAX = 64
  def initialize( out )
    @out = out
    @count = 0
    @divider = 0
    @line_count = 0
  end
  def trigger
    @count += 1
    @divider += 1
    if @divider < DIV_MAX
      return
    end
    @divider = 0

    @out.print "."
    @line_count += 1

    if @line_count >= 32
      @line_count = 0 
      @out.printf( " (%8.8d KB)\n", @count / 2 )
    end
    @out.flush
  end
  def sum
    @out.puts
    @out.printf( "Sum              (%8.8d KB)\n", @count / 2 )
  end
end

def passwd_to_key( passwd )
  d = Digest::SHA256.new

  d << passwd
  d.digest[0..15]
end


# ---------------------------------------------------------------------

ARGV.options do |o|
  o.banner = "Usage: rcrypto [options] input-file >output-file"
  o.separator( "rcrypto AES-File Encryption and Decryption" )
  o.separator( "" )

  o.on( "-d", "--decrypt", "decrypt input-file, default is encrypt" ) do
    $options.decrypt = true
  end
  o.on( "-v", "--verbose", "verbose mode" ) do
    $options.verbose = true
  end
  o.on_tail("-h", "--help", "Diese Hilfe." ) do
    puts o
    exit
  end
  o.on_tail("--version", "Show version") do
    puts o.ver
    puts "Written by Winfried Mueller, www.reintechnisch.de"
    puts ""
    puts "Copyright (C) 2005 Winfried Mueller"
    puts "This is free software; see the source for copying conditions."
    puts "There is NO warranty; not even for MERCHANTABILITY or" 
    puts "FITNESS FOR A PARTICULAR PURPOSE."
    exit
  end
end


# App ---------------------------------------------------------------

def encrypt( in_file, key, verbose )
  iv = AES_IV_Gen.new

  pb = ProgressBar.new( STDERR ) if verbose

  aes = OpenSSL::Cipher::Cipher.new("AES-128-CBC")

  aes.encrypt
  aes.key = key

  while (buf = in_file.read( 512 ))
    pdl = buf.length % 16
    if pdl != 0
      buf = buf << "\x00"*(16-pdl)
    end

    raise "assert" if (buf.length % 16) != 0
    aes.iv = iv.get_next!
    ctext = aes.update( buf )
    raise "assert" if ctext.length != buf.length
    STDOUT.print ctext
    pb.trigger if verbose
  end

  pb.sum if verbose
end

def decrypt( in_file, key, verbose )
  iv = AES_IV_Gen.new

  pb = ProgressBar.new( STDERR ) if verbose

  aes = OpenSSL::Cipher::Cipher.new("AES-128-CBC")
  aes.decrypt
  aes.key = key

  while (buf = in_file.read( 512 ))
    raise "assert" if (buf.length % 16) != 0

    aes.iv  = iv.get_next!
    buf << "x" # Dummy, um letzten Block freizugeben

    ctext = aes.update( buf )
    raise "assert" if (ctext.length+1) != buf.length

    STDOUT.print ctext
    pb.trigger if verbose
  end
  pb.sum if verbose
end

begin

  $options = OpenStruct.new  
  err_code = 0
  ARGV.parse!
  STDOUT.binmode
  in_file = ARGV[0] 
  if !in_file || !File.file?( in_file ) 
    raise( "Input file not found." )
  end

  key = passwd_to_key( get_passwd( "*" ) )

  File.open( in_file, "rb" ) do |f|
    if $options.decrypt
      decrypt( f, key, $options.verbose )
    else
      encrypt( f, key, $options.verbose )
    end
  end
rescue SystemExit
rescue Exception => exc
  err_code = -1 if err_code == 0
  STDERR.puts "E: #{exc.message}"
  raise if DEBUG
end
exit err_code

Changelog

16.05.2005 openssl Version hinzugefügt

13.05.2005 openssl Infos

08.04.2005 openssl Experimente

  • Leider ist openssl derzeit schlecht dokumentiert. Erste Versuche konnte ich jedoch schon machen. Mir kam es vor allem erstmal auf den Aspekt Geschwindigkeit an. Auf einer 450 MHz Maschine hatte ich einen Datendurchsatz von 600 KB/s. Ein 600MB Archiv kann man dann in ungefähr 17 Minuten verschlüsseln. Das sind Werte, die echt zufriedenstellend sind, das wäre für den Praxiseinsatz voll tauglich. Leider funktioniert derzeit das korrekte verschlüsseln noch nicht.