Perl anfällig für DoS bei Webanwendungen die Hashing verwenden? (Allgemeines zu Perl)

[thread]17029[/thread]

Perl anfällig für DoS bei Webanwendungen die Hashing verwenden?

Tags: perl5 Ähnliche Threads

Leser: 22

Articles: hide open all | hide show old branches

+14 replies
GwenDragon

2011-12-29 12:10

User since
2005-01-17
14748 Artikel
Admin1

Heise berichtet vom 28C3, dass diverse Webanwendungen schnell die CPU eines Servers auslasten können, wenn hashing verwendet wird - ein DoS einfach möglich.

Heise schreibt aber auch:
Quote
Die beste Abhilfe gegen das Problem liefert den Forschern zufolge die Verwendung zufälliger Hashfunktionen, wie dies bei Perl bereits seit 2003 nach einer konkreten Sicherheitswarnung der Fall sei.

http://www.heise.de/security/meldung/28C3-Denial-o...

Was meint ihr dazu?
die Drachin Gwen

Meine Perl-Artikel · perldev – verschiedene Perl-Versionen unter Windows starten
- torsten
  
  2011-12-29 14:30
  
  User since
  2010-08-16
  45 Artikel
  BenutzerIn
  
  Wie schon gesagt. Perl hat das, mit 5.8.1 gefixt. In perlrun kannst Du nach der Beschreibung zu HASH_SEED suchen, bzw. auch in perlsec nach "Algorithmic Complexity Attacks". Als ich den Artikel gelesen habe, habe ich mich gewundert, dass derart alte News immer noch für Vorträge gut sind. Offensichtlich ist aber Perl die einzige Sprache, die das Thema vernünftig behandelt.
- GwenDragon
  
  2011-12-29 15:33
  
  User since
  2005-01-17
  14748 Artikel
  Admin1
  
  Schon 2003 wurde sowas untersucht
  Denial of Service via Algorithmic Complexity Attacks
  die Drachin Gwen
  
  Meine Perl-Artikel · perldev – verschiedene Perl-Versionen unter Windows starten
- +11 replies
- rosti
  
  2011-12-30 06:21
  
  User since
  2011-03-19
  3472 Artikel
  BenutzerIn
  
  Wie groß sind denn solche Tabellen um die es hierzu geht und zu welchem Zweck werden die eingesetzt?
  - GwenDragon
    
    2011-12-30 10:46
    
    User since
    2005-01-17
    14748 Artikel
    Admin1
    
    Du meinst diese Rainbowtables, die für das Bruteforce verwendet werden?
    die Drachin Gwen
    
    Meine Perl-Artikel · perldev – verschiedene Perl-Versionen unter Windows starten
  - +9 replies
  - topeg
    
    2011-12-30 12:25
    
    User since
    2006-07-10
    2611 Artikel
    BenutzerIn
    
    Es geht um Hash-Tables. Das sind Datenstrukturen, die z.B intern bei Perl vorkommen um Hashes zu implementieren. Auch PHP nutzt sie für ihre Arrays. Wann immer Daten ungeordnet aber strukturiert abgelegt werden sollen, kommen Hash-Tables in irgendeiner Form vor.
    Die Idee ist den zu speichernden Wert zu hashen, also für diesen Wert eine eindeutige Nummer zu erzeugen und diese zu benutzen um den Speicherort für den Wert fest zu legen. Da kein Hash-Algorithmus perfekt ist, kann es vorkommen, das zwei Werte den selben Hash erzeugen und damit den selben Speicherort beanspruchen. Um das Problem zu lösen werden Die Werte als verlinkte Liste an diesem Speicherort hinterlegt.
    
    Der Angriff hat das Ziel die verlinkte Liste für einen Hashwert immer länger werden zu lassen und immer wieder darauf zuzugreifen. Das abarbeiten der verlinkten Liste dauert immer länger und zieht immer mehr Prozessorleistung an sich. Da das auflösen einer solchen Liste meist ununterbrechbar implementiert ist, kann das Programm auf keine weiteren Aktionen reagieren. Ist die verlinkte Liste also lang genug, kann es das System aus bremsen und das angegriffene Programm zum stehen bringen.
    
    Es gibt ein paar Möglichkeiten einem solchen Angriff entgegenzuwirken. Eine ist es für jedes gestartete Programm ein Wert zu generieren, der dem Hash-Algorithmus mitgegeben wird und die erzeugten Ids für diese Instanz einzigartig zu machen.
    
    Um das für ältere Perl Versionen (oder PHP etc.) zu simulieren, erzeuge ein Zufallszahl und wende sie mit XOR auf den hash-key an, oder füge ihn vor den Wert, oder hänge ihn an den Wert an.
    
    Aber einen solchen Angriff zu führen ist nicht einfach. Dazu muss man sich mit den Interna des anzugreifenden Programms und seinen Libs auskennen. Nur selten werden die einkommenden Daten unverändert in einem Hash-Table hinterlegt, auch wird nicht immer der selbe Hash-Algorithmus verwendet.
    Wenn man die Struktur kennt muss man Daten generieren, die eine Kollision im Hash-Table auslösen. So was lohnt sich nur wenn genügend Ziele vorhanden sind.
    Last edited: 2011-12-30 12:27:50 +0100 (CET)
    - rosti
      
      2011-12-30 16:27
      
      User since
      2011-03-19
      3472 Artikel
      BenutzerIn
      
      Danke für die Info!
      
      --Rosti
    - +5 replies
    - murphy
      
      2011-12-30 17:05
      
      User since
      2004-07-19
      1776 Artikel
      HausmeisterIn
      
      2011-12-30T11:25:42 topeg
      [...]
      Da kein Hash-Algorithmus perfekt ist, kann es vorkommen, das zwei Werte den selben Hash erzeugen und damit den selben Speicherort beanspruchen. Um das Problem zu lösen werden Die Werte als verlinkte Liste an diesem Speicherort hinterlegt.
      [...]
      
      Anmerkungen am Rande:
      
      In genau den Spezialfällen wo man alle möglichen Schlüssel im Vorfeld kennt kann man das Problem durchaus dadurch verhindern, dass man eine perfekte Hashfunktion erzeugt.
      Man kann das Problem auch dadurch umgehen, dass man zum Speichern aller Schlüssel-Wert-Paare mit gleichem Schlüsselhash eben keine einfache sequentielle Datenstruktur verwendet, sondern zum Beispiel einen Binärbaum.
      
      When C++ is your hammer, every problem looks like your thumb.
      - +4 replies
      - topeg
        
        2011-12-30 17:40
        
        User since
        2006-07-10
        2611 Artikel
        BenutzerIn
        
        2011-12-30T16:05:16 murphy
        In genau den Spezialfällen wo man alle möglichen Schlüssel im Vorfeld kennt kann man das Problem durchaus dadurch verhindern, dass man eine perfekte Hashfunktion erzeugt.
        
        IP-Adressen sind ein Beispiel für Eindeutige und Begrenzte Anzahl von Werten. Das Problem ist dann, dass man sehr viel Speicher für reservieren muss (rechne mal nach wieviel TByte man bräuchte nur um eine IP -> DomainName Zuweisung zu ermöglichen). Weshalb auch hier eine einfache Form von Hashing genutzt und eine Kollision riskiert wird.
        
        2011-12-30T16:05:16 murphy
        Man kann das Problem auch dadurch umgehen, dass man zum Speichern aller Schlüssel-Wert-Paare mit gleichem Schlüsselhash eben keine einfache sequentielle Datenstruktur verwendet, sondern zum Beispiel einen Binärbaum.
        
        Sicher das reduziert das Problem, schafft es aber nicht aus der Welt. Denn auch das Abarbeiten und Erweitern eines Baumes braucht Zeit. Man kann einen immer tiefer verschachtelten Baum konstruieren, dessen bearbeiten immer länger dauert. Der Extremfall wäre äquivalent zu einer verketteten Liste.
        
        +3 replies
        
        murphy
        
        2011-12-30 20:00
        
        User since
        2004-07-19
        1776 Artikel
        HausmeisterIn
        
        2011-12-30T16:40:41 topeg
        2011-12-30T16:05:16 murphy
        Man kann das Problem auch dadurch umgehen, dass man zum Speichern aller Schlüssel-Wert-Paare mit gleichem Schlüsselhash eben keine einfache sequentielle Datenstruktur verwendet, sondern zum Beispiel einen Binärbaum.
        
        Sicher das reduziert das Problem, schafft es aber nicht aus der Welt. Denn auch das Abarbeiten und Erweitern eines Baumes braucht Zeit. Man kann einen immer tiefer verschachtelten Baum konstruieren, dessen bearbeiten immer länger dauert. Der Extremfall wäre äquivalent zu einer verketteten Liste.
        
        Das ist so nicht korrekt: Auf einem Red-Black Tree lassen sich zum Beispiel alle Operationen eines assoziativen Arrays mit einer Laufzeitordnung von O(log n) für n Einträge durchführen, während die sequentielle Suche in einer Liste oder einem Array immer O(n) braucht.
        
        Man verringert durch die Verwendung eines Baums als Bucketdatenstruktur also deutlich die schlechtestmögliche Laufzeit einer hashtabellenbasierten Implementation assoziativer Arrays ohne die bestmögliche Laufzeit zu beeinflussen.
        When C++ is your hammer, every problem looks like your thumb.
        
        +2 replies
        
        topeg
        
        2011-12-30 22:26
        
        User since
        2006-07-10
        2611 Artikel
        BenutzerIn
        
        Du hast Recht, man kann die Ablage der Daten Optimieren. Was einen Angriff erschwert aber nicht unmöglich macht. Vergrößere den Datenpool und du kannst den Angriff immer noch machen.
        Die wirksamste Lösung, meiner Meinung nach, mit dem geringsten Aufwand ist wirklich den Wert vor dem Hashen für jede laufende Instanz einzigartig zu Salzen.
        
        murphy
        
        2011-12-30 22:39
        
        User since
        2004-07-19
        1776 Artikel
        HausmeisterIn
        
        Am besten ist es, man macht beides -- nicht nur, weil doppelt besser hält, sondern auch weil die Strategien an unterschiedlichen Punkten ansetzen und sich gut ergänzen: Das Salzen der Hashes reduziert die Kollisionswahrscheinlichkeit bei böswillig gewählten Schlüsseln und intelligente Bucketstrukturen dämpfen den Geschwindigkeitsabfall falls doch Kollisionen auftreten.
        
        Eine weitere mögliche Strategie ist auch, schlichtweg die maximale Anzahl von Einträgen in Hashes zu beschränken, in denen Schlüssel aus externen Datenquellen verwendet werden.
        When C++ is your hammer, every problem looks like your thumb.
    - +2 replies
    - clms
      
      2011-12-30 21:52
      
      User since
      2010-08-29
      373 Artikel
      BenutzerIn
      
      2011-12-30T11:25:42 topeg
      Um das für ältere Perl Versionen (oder PHP etc.) zu simulieren, erzeuge ein Zufallszahl und wende sie mit XOR auf den hash-key an, oder füge ihn vor den Wert, oder hänge ihn an den Wert an.
      
      Ein XOR des Hash-Keys mit einer Zufallszahl bringt bei dem Problem nichts.
      Die Zufallszahl muss ja für den Lauf des Programms (oder zumindest für den den jeweiligen Hash während des Programmlaufs) konstant sein, sonst kann man ja nicht mehr auf den Hash zugreifen. Wenn man N Werte hat, die den gleichen Hash-Key erzeugen, und dann die Hash-Keys mit jeweils der gleichen Zahl verXORed, bekommt man zwar einen anderen Hash-Key - aber wieder N mal den gleichen. Das Problem besteht also fort.
      
      Was hilft, ist entweder die Funktion zur Bildung des Hash-Keys zufällig auswählen (kann der Anwender aber i.d.R. nicht, da das Interna der Programmiersprache ist) oder die Ausgangswerte, für die die Hash-Keys gebildet werden, so modifizieren, dass zwei verschiedene Werte, die vorher den gleichen Hash-Key hatten, nun unterschiedliche Hash-Keys bilden
      - und dann die Modifikation mit jedem Programmlauf ändern.
      - topeg
        
        2011-12-30 22:14
        
        User since
        2006-07-10
        2611 Artikel
        BenutzerIn
        
        Von mir ungenügend formuliert.
        Zur Startzeit des Programms wird das Salt einmalig generiert und dann solange das Programm läuft verwendet. Damit bekommt man eine konstante "Verschiebung" im Hash-Algorithmus.
        
        Sicher das Salt erschwert den Angriff verhindert ihn aber nicht unbedingt. Es kommt auf die Implementation des Algorithmus an. In vielen Fällen führen gleichartige Änderungen an den Ausgangswerten zu völlig anderen Verteilungsmustern. Viele Hash-Algorithmen sind gerade darauf hin ausgelegt, da sonst zu leicht Rückschlüsse vom Hash auf den Ursprungswert möglich sind. MD5 hat z.b dahingehend ein paar schwächen.

View all threads created 2011-12-29 12:10.