Post by m***@heinerkuecker.dePost by Lothar Kimmeringerhabe mir gerade den Vortrag zum Thema Hashflooding reloaded
Gibt es eine Moeglichkeit fuer Java 1.6 und groesser, ohne
Anpassung der verwendeten VM (JDK bzw. JRE) java.lang.String
durch eine eigene Klasse zu ersetzen?
Da würde ich die Finger von lassen,
String und HashMap sind in Java so fundamental,
dass es hier eigentlich nur knallen kann.
Darauf wird's wohl hinauslaufen (hab mir freigenommen, ich werde
mich damit erst wieder naechste Woche in praktischer Form be-
schaeftigen). Da aber so oder so ein Lerneffekt da sein wird,
werde ich es trotzdem mal versuchen.
Post by m***@heinerkuecker.deDie App kann ganz einfach durch eine eigene Map-Implementierung,
welche eine beim Start zufällig erzeugten(und natürlich nicht
veröffentlichten) String vorn oder hinten an den Key-String anhängt.
Das Argument kam oefter, ist aber meiner Ansicht nach ein
Herumgepfriemel um das eigentliche Problem. So muss jeder,
der mit HashMap arbeitet, dieses Sicherheitsloch im Kopf
haben, waehrend es mit der Aenderung einer einzigen Methode
fuer alle bestehenden und zukuenftigen Applikationen
gefixed waere.
HTTP Parameter Parsing ist ja nur eine Teilanwendung von Maps
und Hashcode.
Post by m***@heinerkuecker.deDann ist der Hashcode nicht mehr durch einen Hacker nachvollziehbar.
Das Ergebnis sollte nicht voraussagbar sein oder am besten
so kollisionsfrei, dass ein Versuch, Kollisionen zu berechnen
zu viel Aufwand bedeutet, um zweckmaessig zu sein. Das Anhaengen
von zufaelligem Text kann funktionieren, muss aber nicht
(siehe MD5).
Post by m***@heinerkuecker.deIch verstehe auch nicht, wieso die Java-Web-Server Post-Data cachen sollten
(steht so in dem Foliensatz), für Post-Data gibt es einen Stream, welcher
nur im Request-Scope lebt.
Der Begriff caching duerfte verwirrend eingesetzt sein. Es geht
um das Hinterlegen von Key-Value-Paaren in einer Map, um im
Anschluss schneller darauf zuzugreifen. Im Prinzip ist das
ein Caching, da es ja technisch nicht notwendig ist, sondern nur
die Performance erhoeht.
Post by m***@heinerkuecker.deDamit das Problem auftritt, muss der Angreifer erst mal überhaupt
2 hoch was weiss ich Requests an den Server bringen, was
wahrscheinlich auch schon in ein Sicherheitsnetz laufen würde.
Wo ist da also das Problem.
Es werden nicht 2 hoch x Anfragen reingestellt, sondern ein Request
mit 2 hoch x Key-Value-Paaren, deren Key immer den gleichen
Hashcode produzieren.
HashMap und Hashtable arbeiten beide nach dem gleichen Prinzip
(bei Hashtable war das frueher anders, aber ich schau jetzt
nicht nach, ob das immer noch so ist), dass sie ein internes
Array mit LinkedList haben. Beim put wird
key.hashcode modulo arraygroesse
errechnet und der LinkedList an der Stelle der Value hinzugefuegt
(ist nicht vollstaendg, siehe spaeter).
Beim get wird dann auf die gleiche Weise die LinkedList ermittelt
und ueber die Elemente iteriert, bis currentkey.equals(key) ist
und der entsprechende Wert zurueckgegeben.
Best case: O(1)
Worst Case: O(n^2)
Der Hack realisiert den Worst Case. Da beim put oben ja schon
geschaut werden muss, ob der Key nicht schon in der Map drin ist,
hast du den Worst Case bereits beim Aufbau der Map, d.h. ob die
angefragte Seite die Parameter ueberhaupt verwendet ist nicht
relevant.
Der simpelste Workaround ist die Nutzung von TreeMap, allerdings
erkauft man sich das mit einem O(log n) im Best Case. Der einfachste
Fix waere die Anpassung von String.hashcode. SUN/Oracle geht aber
wohl (nicht zu unrecht) davon aus, dass es Schlaumeier gibt, die
von einer auf ewig gueltigen Hashimplementierung von String
ausgehen und diese als Konstanten irgendwo im Code verwenden.
Praktisch duerfte das sogar vom Compiler so jetzt selbst bei den
String-cases der Fall sein (siehe
<news:5ng8ph6nu1sw$***@kimmeringer.de>
wie sowas implementiert sein duerfte). Da koennte man aber den
Compiler relativ einfach anpassen, indem man im switch nicht
einfach mystring.hashCode() aufruft, sondern (das derzeit nicht
existente) System.stringHashCode(), aehnlich wie es dort ja schon
den identitiyHash gibt.
Hoffe, das Problem damit verstaendlich gemacht zu haben. Man steht
also derzeit vor der Wahl, alle seine Verwendungen von HashMap
zu aendern und darauf zu hoffen, dass Drittanbieter von Software
wie Jetty, Glassfish etc. ebenfalls schnell etwas liefern (und
dabei nichts uebersehen haben, wie das bei Ruby mit dem Hack von
letztem Jahr passiert ist). Oder man hofft darauf, dass Oracle
einen von einem Big Player eins auf den Deckel bekommt und dazu
"ueberredet" wird, das ganze prinzipiell zu fixen (also in etwa
aequivalent zu den "freiwilligen" Backports beim Bug
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6346658 mit
dem Backport auf Java 6 unter
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8003275)
Ich persoenlich hoffe auf letzteres. Da einem sowieso nur
das Warten bleibt, kann ich mich (theoretisch, mit eventuell
praktischem Einsatz bei Bedarf) mit der Frage beschaeftigen,
ob ich das nicht selbst hintenrum gefixed bekomme. ;-)
Gruesse, Lothar
--
Lothar Kimmeringer E-Mail: ***@kimmeringer.de
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)
Always remember: The answer is forty-two, there can only be wrong
questions!