Διάβαζα το καταπληκτικό βιβλίο του Goodrich για τις δομές δεδομένων & αλγόριθμους στην Python και βρήκα αυτό το ενδιαφέρον διάβασμα για όσους από εσάς έχετε χρησιμοποιήσει πίνακες κατακερματισμού (και γνωρίζετε την εσωτερική υλοποίηση χρησιμοποιώντας το σχήμα ανοιχτής διεύθυνσης) αλλά αγνοούσαν αυτή τη δυνατότητα.
Ακολουθεί το απόσπασμα από αυτό το βιβλίο:
Σε μια ακαδημαϊκή εργασία του 2003, οι ερευνητές συζητούν τη δυνατότητα εκμετάλλευσης της απόδοσης ενός πίνακα κατακερματισμού στη χειρότερη περίπτωση για να προκληθεί επίθεση DoS. Για πολλούς δημοσιευμένους αλγόριθμους που υπολογίζουν κωδικούς κατακερματισμού, σημειώνουν ότι ένας εισβολέας θα μπορούσε να υπολογίσει εκ των προτέρων έναν πολύ μεγάλο αριθμό συμβολοσειρών μέτριου μήκους που όλες κατακερματίζονται με τον ίδιο κωδικό κατακερματισμού 32-bit.
Στα τέλη του 2011, μια άλλη ομάδα ερευνητών παρουσίασε την εφαρμογή μιας τέτοιας επίθεσης. Οι διακομιστές Ιστού επιτρέπουν την ενσωμάτωση μιας σειράς παραμέτρων κλειδιού-τιμής σε μια διεύθυνση URL χρησιμοποιώντας μια σύνταξη όπως ?key1=val1&key2=val2&key3=val3. Συνήθως, αυτά τα ζεύγη τιμών κλειδιών αποθηκεύονται αμέσως σε έναν χάρτη από τον διακομιστή και τίθεται ένα όριο στο μήκος και τον αριθμό τέτοιων παραμέτρων υποθέτοντας ότι ο χρόνος αποθήκευσης στον χάρτη θα είναι γραμμικός στον αριθμό των καταχωρήσεις. Εάν όλα τα κλειδιά συγκρούονταν, αυτή η αποθήκευση απαιτεί τετραγωνικό χρόνο (αναγκάζοντας τον διακομιστή να εκτελέσει υπερβολική ποσότητα εργασίας).
Την άνοιξη του 2012, οι προγραμματιστές της Python διένειμαν μια ενημερωμένη έκδοση κώδικα ασφαλείας που εισάγει την τυχαιοποίηση στον υπολογισμό των κωδικών κατακερματισμού για συμβολοσειρές, καθιστώντας λιγότερο εφικτή την αντίστροφη μηχανική ενός συνόλου συμβολοσειρών που συγκρούονται.
Και τώρα, συνάντησα ένα άλλο blog που επισημαίνει πώς τέτοιες τυχαιοποιημένες λειτουργίες παρέμειναν επίσης επιρρεπείς σε επιθέσεις DoS. Φοβερο!
