login timing attacks...

[jens]

Ich möchte gern das Thema ganz allgemein nochmal aufgreifen...

Hab gerade entdeckt, das django einiges an Aufwand betreibt um timing attacks beim Login möglichst zu verhindern: https://code.djangoproject.com/ticket/20760

Das Prinzip ist einfach: Es wird versucht den selben Code-Pfad zu nehmen, egal. oder der Benutzername/Passwort richtig/falsch sind.
Somit sollte am Ende jeder Request ähnlich gleich lange dauern...

Im Ticket wird auch über eine Künstliche-Zufalls-Verzögerung gesprochen. Langsame wird mir auch klar, warum das nicht funktionieren kann:
Man müßte im Prinzip doch möglichst genau die Zeit eines normalen Logins treffen, damit der Unterschied nicht sichtbar ist.

Aber das bringt mich auf eine Idee: Warum nicht die Zeit messen, wie lange ein erfolgreicher Login benötigt und dann einen delay basierend darauf erzeugen?!?
Natürlich Live Messen und nicht einen Messwert Hardcoden
Evtl. die letzten x-erfolgreichen Logins mitteln...

Das muss ich mal testen



Aber zum eigentlichen Problem: Was versucht man da eigentlich zu verhindern?!? Bzw. was kann man durch einen "timing attack" überhaupt erreichen?
Doch letztlich nur prüfen, ob ein Benutzername existiert oder nicht... Oder? Das ist bei einigen Webseiten außerdem kein großes Geheimnis. z.B. die meisten Foren haben Benutzerlisten.

...und das ganze ist nur Praktikabel, wenn es keine DOS-Abwehrmaßnamen gibt. Denn man benötigt ja eine große Messbasis...

Würde also nicht ein "Login-Versuch-Zeit-Limit" nicht generell mehr Schützen?
Außerdem ist diese "Gleichezeit für Loginversuche" irgendwie eine Sinnlose CPU Verschwendung...

[jens]

Aber das bringt mich auf eine Idee: Warum nicht die Zeit messen, wie lange ein erfolgreicher Login benötigt und dann einen delay basierend darauf erzeugen?!?
Natürlich Live Messen und nicht einen Messwert Hardcoden
Evtl. die letzten x-erfolgreichen Logins mitteln...

Ich hab eben mal schnell nachgemessen, bei meinem django-secure-js-login projekt:
https://github.com/jedie/django-secure- ... 53e5e9e728

Im Testbetrieb dauert ein Login im Schnitt:
0.00707 Sek <- erfolgreicher Login
0.00045 Sek <- falscher Benutzername

Also deutlicher Unterschied, aber ich habe es ja absichtlich so ausgelegt!
Als nächstes werde ich mal versuchen die Idee von oben zu realisieren... Mal sehen, was dann bei rauskommt

[BlackJack]

@jens: Bezüglich der DOS-Abwehrmassnahmen: Je nach dem über welche Mittel der Angreifer verfügt (Bot-Netz) oder wieviel Zeit er hat, kann er die unterlaufen.

[Kebap]

Was versucht man da eigentlich zu verhindern?!? Bzw. was kann man durch einen "timing attack" überhaupt erreichen?

Du erhältst (Indizien zu) Informationen, die du eigentlich nicht erhalten solltest.

Dass es hier um Login und Benutzernamen und Passwort geht, ist eher nebensächlich.

Das Prinzip lässt sich auf viele ähnliche Fälle übertragen. Aber dies ist ein sehr anschauliches.

Ein Computerprogramm hat gewisse vorgeplante Möglichkeiten für Ausgaben, die dir erstmal nicht so viele Infos verraten sollten. Nun gibt es aber Seitenkanäle, über die man trotzdem an "innere" Informationen herankommt, die gar nicht für Öffentlichkeit gedacht oder überhaupt je bedacht wurden. So kann man das Programm vielleicht trotzdem "aushorchen"

Muss auch nicht nur über Timing gehen, aber gut, so heißt der Thread hier.

[DasIch]

Nehmen wir mal an du hättest irgendwo folgende Funktion:

Code: Alles auswählen

def verify_password(password):
    return password == 'secret'

Der Angreifer kann beliebige Passwörter wählen um auf das geheime Passwort zu kommen. Ohne einen timing side channel müsste er jetzt irgendwelche Passwörter beliebig ausprobieren bis er irgendwann auf "secret" kommt.

Der timing side channel informiert allerdings den Angreifer ob der gegebene String einen Prefix hat der mit dem geheimen Passwort übereinstimmt, da bei einer Übereinstimmung die Verifikation länger dauert. Probiert der Angreifer also Strings aus und stößt auf einen bei dem die Verifikation länger dauert, kann er alle Strings ignorieren die nicht denselben Prefix haben. Die Anzahl der Möglichkeiten schrumpft dadurch massiv.

Dies funktioniert natürlich auch noch bei anderen Geheimnissen als Passwörtern und auch über andere side channels wie Geräusche der Hardware, Stromverbrauch oder den CPU Cache.

[jens]

Interessante Aspekte, danke!

Ich hab nun eine erste Implementierung, meiner time.sleep() Variante...

Diese hab ich mal gegen den normalen Django Login antreten lassen:

Measuring successful django login (100 loops)...
min: 0.064989 - average: 0.088680 - max: 0.098348 (takes 9.47 sec.)

Measuring failed django login (100 loops)...
min: 0.072198 - average: 0.096935 - max: 0.139168 (takes 9.70 sec.)
average django diff: -0.008255 sec


Measuring successful secure_js_login (100 loops)...
min: 0.011619 - average: 0.012313 - max: 0.035892 (takes 5.47 sec.)

Measuring failed secure_js_login (100 loops)...
min: 0.011200 - average: 0.011860 - max: 0.012650 (takes 1.19 sec.)
average secure_js_login diff: 0.000453 sec

Interessant finde ich, das der Django Login im Fehlerfall ein wenig länger dauert

Meine secure_js_login time.sleep() Lösung ist doch nach diesen Werten ganz Akzeptabel.
Nicht verwirren lassen darf man sich über die Unterschiedlichen "takes" Zeigen. Also 5,47 Sek. zu 1,19 Sek. Die Zeit wird quasi beim "setUp" und "tearDown" gebraucht

EDIT: Der dazugehörige branch: https://github.com/jedie/django-secure- ... ng_attacks

Das Prinzip ist einfach:

* timings = collections.deque(maxlen=10)
* Ein timings.append(duration) wird nur beim erfolgreichen Login gemacht.
* Bei nicht Erfolg: time.sleep(random.uniform(min(self.timings), max(self.timings)) - duration)

[jens]

So, ich wollte es nochmal genauer wissen...

Hab ein eigenständige "test.py" gemacht -> https://gist.github.com/jedie/ac7a0be713fb9d41a1d2

Kann man recht einfach, schnell selbst ausprobieren:

Code: Alles auswählen

~ $ virtualenv django_env
~ $ cd django_env/
~/django_env $ source bin/activate
(django_env)~/django_env $ pip install django
(django_env)~/django_env $ mkdir src
(django_env)~/django_env $ cd src
(django_env)~/django_env/src $ django-admin startproject timing-attack
(django_env)~/django_env/src $ cd timingattack/timingattack/
(django_env)~/django_env/src/timingattack/timingattack $ touch tests.py # <<<-- https://gist.github.com/jedie/ac7a0be713fb9d41a1d2
(django_env)~/django_env/src/timingattack/timingattack $ cd ..
(django_env)~/django_env/src/timingattack $ ./manage.py test
Creating test database for alias 'default'...

Measuring successful django login (200 loops)...
    Min/max avg with 30 items.
    avg.min: 45.7ms (-6%) - average: 48.8ms - avg.max: 54.5ms (10%) (takes 10.11 sec.)
Measuring 'wrong password' django login (200 loops)...
    Min/max avg with 30 items.
    avg.min: 49.0ms (-6%) - average: 52.1ms - avg.max: 57.0ms (8%) (takes 10.52 sec.)
Measuring 'wrong username' django login (200 loops)...
    Min/max avg with 30 items.
    avg.min: 48.5ms (-6%) - average: 51.6ms - avg.max: 58.0ms (11%) (takes 10.42 sec.)
 *** max.average django diff: 3.33ms (6.4%)
.
----------------------------------------------------------------------
Ran 1 test in 31.100s

In diesem Fall wird das aktuelle django 1.8.1 installiert.

Zu den Zahlen:
* (200 loops) -> Es wird 200mal der Request durchgeführt und jeder einzelne gemessen
* Min/max avg with 30 items. -> Durchschnitt der schnellten 30 und langsamsten 30 Requests werden zu avg.min und avg.max
* max.average django diff: 3.33ms -> Differenz in diesem Fall aus 48.8ms zu 52.1ms

Bin kein Statistiker, aber würden die Gemessenen Werte darauf hindeuten, das eine Timing-Attacke grundsätzlich möglich ist?
Gut die Durchschnittliche Abweichung von 3,33ms ist nicht gerade viel.

Auf der anderen Seite sind die Abweichungen zwischen avg.min zu average bzw. avg.max zu average auch 6% bzw. 10% und damit mehr, als zwischen 'successful' und 'wrong password'

[jens]

Hat hier noch jemand eine Idee zur Verbesserung?!?

Code: Alles auswählen

from __future__ import absolute_import, division, print_function


import time
import collections
import random


DEQUE_LENGTH = 50

class TimingAttackPreventer(object):
    succsessful_timings = collections.deque(maxlen=DEQUE_LENGTH)
    failed_timings = collections.deque(maxlen=DEQUE_LENGTH)

    def avg(self, deque):
        if deque:
            return sum(deque) / len(deque)
        else:
            return 0

    def __call__(self, func):
        def wrapped_func(*args, **kwargs):
            # log.debug("\ncall view %r with args: %r kwargs: %r",
            #     func.__name__, args, kwargs
            # )
            start_time=time.time()
            response = func(*args, **kwargs)

            succsessful_length = self.avg(self.succsessful_timings)
            failed_length = self.avg(self.failed_timings)

            diff_compensation = succsessful_length - failed_length
            no_compensation = 0

            if getattr(response, "add_duration", False):
                # successful request -> collect duration value
                timing_deque = self.succsessful_timings
                sleep_length = no_compensation
            else:
                # failed request -> 'fill' time with collect durations
                timing_deque = self.failed_timings
                sleep_length = diff_compensation

            if sleep_length<0:
                sleep_length=0

            timing_deque.append(time.time()-start_time)

            time.sleep(sleep_length)

            # log.debug("Response: %s", response)
            return response
        return wrapped_func


class NoAddDurationResponseMock(object):
    add_duration=False

class AddDurationResponseMock(object):
    add_duration=True


@TimingAttackPreventer()
def test(t, add_duration):
    time.sleep(t)
    if add_duration:
        return AddDurationResponseMock
    else:
        return NoAddDurationResponseMock


##############################################################################


count=200000

start_time = time.time()
for _ in range(count):
    test(t=0, add_duration=True)
duration1 = time.time()-start_time

start_time = time.time()
for _ in range(count):
    test(t=0, add_duration=False)
duration2 = time.time()-start_time

print("\n%f vs %f" % (duration1, duration2))
print("succsessful_timings", list(TimingAttackPreventer.succsessful_timings)[-3:])
print("failed_timings.....", list(TimingAttackPreventer.failed_timings)[-3:])


##############################################################################


count=500

start_time = time.time()
for _ in range(count):
    test(t=0.002, add_duration=True)
duration1 = time.time()-start_time


start_time = time.time()
for _ in range(count):
    test(t=0.001, add_duration=False)
duration2 = time.time()-start_time

print("\n%f vs %f" % (duration1, duration2))
print("succsessful_timings", list(TimingAttackPreventer.succsessful_timings)[-3:])
print("failed_timings.....", list(TimingAttackPreventer.failed_timings)[-3:])

Kann man so starten und raus kommt das:

Code: Alles auswählen

0.488604 vs 0.581449
succsessful_timings [0.0, 0.0, 0.0]
failed_timings..... [0.0, 0.0, 0.0]

1.322487 vs 1.062003
succsessful_timings [0.0029649734497070312, 0.0029020309448242188, 0.0029370784759521484]
failed_timings..... [0.0019538402557373047, 0.0019919872283935547, 0.0010120868682861328]

EDIT: Überarbeitete Version: https://github.com/jedie/django-secure- ... ors.py#L48

[nomnom]

Hat hier noch jemand eine Idee zur Verbesserung?!?

Tatsächlich „constant time“-Algorithmen zum Überprüfen von Benutzername/Passwort benutzen? Außerdem kommt es ja nicht darauf an, dass falsche Daten und richtige Daten genauso lange brauchen müssen, sondern dass aus der Zeitverzögerung nicht auf das Passwort geschlossen werden kann.

[jens]

Schon klar. Hatten wir ja weiter oben schon

...
Das Prinzip ist einfach: Es wird versucht den selben Code-Pfad zu nehmen, egal. oder der Benutzername/Passwort richtig/falsch sind.
...
Aber das bringt mich auf eine Idee: Warum nicht die Zeit messen, wie lange ein erfolgreicher Login benötigt und dann einen delay basierend darauf erzeugen?!?

Ich untersuche gerade die zweite Möglichkeit...

Denn die erste hat trotzdem nicht den 100% Erfolg.
Zweitens gibt die time.sleep() Variante CPU Ressourcen frei...
Drittens, benötigt man eh einen DOS Schutz, egal, welche Variante...

[jens]

Hab ein eigenständige "test.py" gemacht -> https://gist.github.com/jedie/ac7a0be713fb9d41a1d2

Hab noch mal weiter gespielt und matplotlib ein Plott erzeugt:

mit @override_settings(PASSWORD_HASHERS = ('django.contrib.auth.hashers.MD5PasswordHasher',)):


Mit dem "default" Hasher:

[jens]

Hab die sourcen auf platte wieder entdeckt und mal alles auf github gepackt: https://github.com/jedie/django-timingattack-test/

...sonst kommt da ja noch weg...