JavaScript: Zufallsgenerator für Diffie-Hellman rückrechnen

[nufan]

Hallo
Mal ein Web-Problem der etwas anderen Art ^^ Vorweg, hier geht es um eine Situation in einer Test-Umgebung. Ich mache hier nichts Illegales ^^

Die Lage sieht folgendermaßen aus:
Ich habe ein Kontakt-Formular, über das eine Nachricht abgeschickt wird. Diese Nachricht wird lokal über JavaScript mit AES (OFB) verschlüsselt. Nun habe ich einen HTTP-Trace (http://pastebin.com/HpGMNn9w), dessen Text ich entschlüsseln soll. Verschlüsselt wird über folgenden Script: http://pastebin.com/7r3mtTAv
Beim Abschicken des Formulars wird die "send()"-Methode ausgeführt.
Weiters habe ich den Hinweis, dass der Bug etwas mit dem Zufallsgenerator zu tun hat.
Ich hab Zugang zum Formular und kann selbst Daten eingeben, die danach verschickt werden. Ich kann den Ablauf also komplett nachvollziehen.

Soweit zur Angabe, jetzt mal meine Erkenntnisse:
Der Script implementiert einen Diffie-Hellman-Schlüsselaustausch (http://de.wikipedia.org/wiki/Diffie-Hel ... laustausch), mit dem dann der AES-Schlüssel erstellt wird. Was mir nun fehlt um den Text im Trace wieder herzustellen, ist die Zufallszahl des Clients ("randomValue" im Script). Diese über Bruteforce auszurechnen ist unpraktisch. Der Schlüssel hat 16 Byte, also hab ich 256^16 Möglichkeiten, was laut Python 340282366920938463463374607431768211456 sind... etwas zu viel für meinen Laptop ^^
Was nun? Sehen wir uns folgenden Code an:

Code: Alles auswählen

for (i=0; i<c ; i++) {
        randomValue.appendByte(getRandom(0, 255));
        iv.appendByte(getRandom(0, 255));
}

"iv" (Initialization Vector des AES-Hashs: http://de.wikipedia.org/wiki/Initialisierungsvektor) wird unverschlüsselt übertragen und ist dadurch auch im HTTP-Trace vorhanden. Ich kenne also jedes Byte, das zwischen den Bytes der Zufallszahlen erzeugt wird. Da alle üblichen Browser Predictable Random Number Generators (PRNG, http://en.wikipedia.org/wiki/Random_num ... tor_attack) verwenden, könnte man den Status des Zufallsgenerators rekonstruieren und dadurch auf vorherige bwz. nachfolgende Zahlen schließen (http://landing2.trusteer.com/sites/defa ... -3.6.8.pdf). Was ist das Problem dabei? Dass ich die Zufallszahlen nicht vollständig kenne:

Code: Alles auswählen

function getRandom( min, max ) {
        if( min > max ) {
                return( -1 );
        }
        if( min == max ) {
                return( min );
        }
  
    return( min + parseInt( Math.random() * ( max-min+1 ) ) );
}

Ich multipliziere sie mit 256 und verwende anschließend den Integer-Anteil. Dadurch verliere ich die Informationen über die Nachkommastellen.

Blöde Frage... Welchen Typ hat Math.random() überhaupt? Entspricht das einem double in C/++? long double? Hängt das vom Browser/Betriebssystem ab? Da ich das Problem (spätestens beim Rekonstruieren) auf Bit-Ebene vermute, wäre das sehr wichtig zu wissen.

Ich hab schon einen Ansatz gehabt ein Ergebnis-Byte durch 256 zu dividieren und das Ergebnis so lange zu erhöhen, bis der Status auch für alle nachfolgenden stimmte (Wobei zwischendurch natürlich immer eine Stelle übersprungen wird, die für "iv" verwendet wird). Das ist einerseits schlecht, weil ich dabei eine Fließkommazahl erhöhe, andererseits habe ich noch keinen Code gefunden, der mir nachfolgende/vorhergehende Zahlen berechnet, da muss ich schlimmstenfalls selbst ran.

So... ich bin inzwischen recht ratlos, hat irgendjemand auch nur den Ansatz einer Idee? ^^
Besten Dank im Voraus

[cloidnerux]

Ich multipliziere sie mit 256 und verwende anschließend den Integer-Anteil. Dadurch verliere ich die Informationen über die Nachkommastellen.

Eine Multiplikation mit 256 = 2^8 ist doch ein binärer shift um 8 stellen, zumindest bei int. Dürfte sich da bei Float nicht ähnliches ergeben?
http://de.selfhtml.org/javascript/objek ... htm#random
Sagt bruch, also float. Aber ist es den so wichtig, wie groß Mantisse oder Exponent sind, oder kann man nicht auch mit weniger Information das lösen?
Wenn ich richtig gehe, ist doch jedes Byte aus dem rv-vector das um 8 nach links geshiftete Bitmuster der Mantisse des zugehörigen floats.
Andererseits könntest du auch versuchen, selber den Zufallsgenerator so lange laufen zu lassen, bis du zu dem Bytes des rv-vectors kommst, was davon abhängt, wie der Zufallsgenerator im Browser gestartet wird.
Wenn der über die Urzeit initialisiert wird und dann random erst mit dem Schlüsselalgorithmus aufgerufen wird, musst du nur herausfinden, wann das script gestartet wurde.

[nufan]

Ich multipliziere sie mit 256 und verwende anschließend den Integer-Anteil. Dadurch verliere ich die Informationen über die Nachkommastellen.

Eine Multiplikation mit 256 = 2^8 ist doch ein binärer shift um 8 stellen, zumindest bei int. Dürfte sich da bei Float nicht ähnliches ergeben?

Das war auch einer meiner ersten Gedanken, aber es wird nur die Mantisse um 8 erhöht.

Aber ist es den so wichtig, wie groß Mantisse oder Exponent sind, oder kann man nicht auch mit weniger Information das lösen?

Joa, das ist eine gute Frage ^^

Andererseits könntest du auch versuchen, selber den Zufallsgenerator so lange laufen zu lassen, bis du zu dem Bytes des rv-vectors kommst, was davon abhängt, wie der Zufallsgenerator im Browser gestartet wird.
Wenn der über die Urzeit initialisiert wird und dann random erst mit dem Schlüsselalgorithmus aufgerufen wird, musst du nur herausfinden, wann das script gestartet wurde.

Brauche ich die Zeit wirklich?

The state can be easily extracted from a single Math.random() value as following:
the floating point value is first multiplied by 253 to form the original 53 bit integer.
Then the higher 26 bits are extracted from it, and are shifted to the right by 22
positions. The lower 22 bits are enumerated over, and each 48 bit value is
considered a candidate for the state (from which the first sample is taken),
advanced once and then compared (only higher 27 bits) to the remaining 27 bits
in the 53 bit integer. A match is unlikely unless the real state is found.

From the extracted state, it’s easy to roll back iteratively until a state value (XOR
a) is found which matches a date in the last few days (assuming 227-228 such
possible values, out of the 248 possible state values, it is very reliable way of
finding the seeding time – since the PRNG is used only for Math.random(), and
thus is not frequently invoked).

Quelle: http://landing2.trusteer.com/sites/defa ... owsers.pdf

Damit bin ich wieder bei einem meiner alten Ansätze. Ich dividiere einfach mein erstes bekanntes Ergebnis durch 256. Danach berechne ich mir meinen Status und prüfe, ob der Status ein möglicher Ausgangswert für die anderen bekannten Werte ist. Ist er das, hab ich mit sehr großer Wahrscheinlichkeit den korrekten Status und kann die anderen Werte berechnen.
Ist er das nicht, erhöhe ich einfach das Ergebnis meiner Division um die kleinste mögliche Zahl und versuche es erneut. Nur haben die Zufallszahlen teilweise 17-18 Nachkommastellen (ich muss das mit der Größe unbedingt genau prüfen...), wodurch das viele Additionsschritte werden könnten.

Ich muss es schaffen den zu überprüfenden Bereich einzugrenzen. Ich kann aufhören zu überprüfen, wenn bei der Rundung vom Ergebnis der Multiplikations meines Divisionsergebnisses dann mein bekannter Wert + 1 rauskommt. Denn dann hätte mir parseInt() den nächsten Integer-Wert geliefert.
1 / 256 = 0,00390625
Ich kann mir also die ersten 2 Kommastellen komplett sparen, da ich bei einer Multiplikation mit einem an diesen Stellen erhöhten Wert mit 256 ganz sicher auf die nächste Zahl komme. Ich muss also praktisch nur mein Divisionsergebnis (maximal) um 0,00390625 inkrementieren. Das Problem sind die Stellen dahinter... 390625 Iterationen sind kein Problem, wenn noch paar Stellen dazukommen, hab ich ein Problem.

Wie findet ihr den Ansatz? Theoretisch denke ich ist das Problem so auf jeden Fall zu lösen, ob sich das praktisch auch machen lässt ist eine andere Frage.

[cloidnerux]

Brauche ich die Zeit wirklich?

Das ist ein Ansatz. hast du die Zeit und der Zufallsgenerator wird wie üblich mit der Zeit initialisiert, dann kennst du den Startzustand und kannst dann auf die Zustände beim Generieren des Keys schließen. Selbst wenn du das nur auf die Sekunde genau hast, kannst du +-500ms rechnen, bist also irgendwo in einem Sinnvollen bereich. Dafür ist es aber notwendig, die Zeit auf der Lokalen Maschine zu kennen.

Aber man kann es auch mit dem entgegengesetzten Ansatz verknüpfen. Du Rechnest deine Bytes aus dem rv-vector Zurück, da kommst du auf einen Wert zwischen 1 und 0 mit x/256. Ich gehe mal von 23 Bit Mantisse aus, von denen wir die obersten 8 schon kennen(wenn ich das jetzt richtig gedacht habe). Damit hast du noch 23-8 = 15 Bit Entropie, macht 2^15 = 32768 Möglichkeiten, auch noch tolerabel. Sind also 2 Ansatzpunkte, meiner Meinung nach.
Wenn es aber Doubles sind, dann wird es mit 44Bit Entropie und 17.592.186.044.416 Möglichkeiten sind dann nicht so schön, wobei dann hier deine Möglichkeit mit der Rückbildung funktionieren kann.

[nufan]

Brauche ich die Zeit wirklich?

Das ist ein Ansatz. hast du die Zeit und der Zufallsgenerator wird wie üblich mit der Zeit initialisiert, dann kennst du den Startzustand und kannst dann auf die Zustände beim Generieren des Keys schließen. Selbst wenn du das nur auf die Sekunde genau hast, kannst du +-500ms rechnen, bist also irgendwo in einem Sinnvollen bereich. Dafür ist es aber notwendig, die Zeit auf der Lokalen Maschine zu kennen.

Die kenn ich leider nicht...

Aber man kann es auch mit dem entgegengesetzten Ansatz verknüpfen. Du Rechnest deine Bytes aus dem rv-vector Zurück, da kommst du auf einen Wert zwischen 1 und 0 mit x/256. Ich gehe mal von 23 Bit Mantisse aus, von denen wir die obersten 8 schon kennen(wenn ich das jetzt richtig gedacht habe). Damit hast du noch 23-8 = 15 Bit Entropie, macht 2^15 = 32768 Möglichkeiten, auch noch tolerabel. Sind also 2 Ansatzpunkte, meiner Meinung nach.
Wenn es aber Doubles sind, dann wird es mit 44Bit Entropie und 17.592.186.044.416 Möglichkeiten sind dann nicht so schön, wobei dann hier deine Möglichkeit mit der Rückbildung funktionieren kann.

Dass ich mir einen gewissen Anteil aus der Hexadezimalzahl herleiten kann hab ich mir auch schon gedacht. Auf meinen Rechnern sieht das stark nach double aus, aber die sind alle 64-Bit. Hat das was damit zu tun oder liegt das nur am Browser?

[cloidnerux]

Dass ich mir einen gewissen Anteil aus der Hexadezimalzahl herleiten kann hab ich mir auch schon gedacht. Auf meinen Rechnern sieht das stark nach double aus, aber die sind alle 64-Bit. Hat das was damit zu tun oder liegt das nur am Browser?

Du hast 52 Bit Mantisse, 1 Bit Vorzeichen und 11 Bit Exponent. Da kommt das auf 64-Bit, dann ist das alles double.

Die kenn ich leider nicht...

Du kannst hoffen, dass es sich per NTP synchronisiert mit M$ oder so, dann hätte man nen Ansatz. Gibt es im HTTP_header oder im user Agent keine Zeitangabe?

[nufan]

Dass ich mir einen gewissen Anteil aus der Hexadezimalzahl herleiten kann hab ich mir auch schon gedacht. Auf meinen Rechnern sieht das stark nach double aus, aber die sind alle 64-Bit. Hat das was damit zu tun oder liegt das nur am Browser?

Du hast 52 Bit Mantisse, 1 Bit Vorzeichen und 11 Bit Exponent. Da kommt das auf 64-Bit, dann ist das alles double.

Ja, aber ich weiß nicht, was im Trace für ein System verwendet wurde. Ich kann nur 32-Bit versuchen und hoffen ^^

Die kenn ich leider nicht...

Du kannst hoffen, dass es sich per NTP synchronisiert mit M$ oder so, dann hätte man nen Ansatz. Gibt es im HTTP_header oder im user Agent keine Zeitangabe?

Nein, ich hab nur den oben verlinkten HTTP-Trace.
http://pastebin.com/HpGMNn9w
Ich kann das zwar alles selbst vom Ablauf her nachvollziehen, aber ich hab dann ja trotzdem eine andere Zeit und somit andere Zufallszahlen.

[nufan]

*Update* ^^
Ich bin inzwischen auf ein paar Sachen draufgekommen. "randomValue" und "iv" sind eher ungeeignet um die Folge zu rekonstruieren, da ich ja nur jede 2. Zahl kenne. Viel besser dafür eignet sich "ctr", das komischerweise bis auf den Request nirgends verwendet wird. Sieht ganz danach aus, als würde der Fehler daran liegen, dass "ctr" unverschlüsselt übertragen wird. "ctr" ist ein String aus den ASCII-Codes von Dezimalzahlen. Nun bin ich dabei die folge per Bruteforce zu ermitteln, über ein Zeitspanne der letzten Jahre... in Java...

Code: Alles auswählen

// Prng.java
package prng;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;

public class Prng {

    static BufferedWriter out;
    // Expected values from calculted from "ctr"
    static char[] results = {0x05, 0x08, 0x09, 0x05, 0x07, 0x07, 0x09, 0x01};
    static long a = 0x5DEECE66DL;
    static long b = 0xBL;

    public static void main(String[] args) throws CloneNotSupportedException, IOException {
        out = new BufferedWriter(new FileWriter("out_40.txt"));
        // 1. 1. 2007
        long startTime = 1167609600L;
        // 1. 10. 2012
        long endTime = 1349049600L;
        long i;
        MyRandom random = new MyRandom();

        // Try every ms as seed
        for (i = startTime; i <= endTime; i++) {
            random.setSeed(i);
            if (tryState(0, 0, random) == 1) {
                out.write("SUCCESS: " + i + "\n\n");
            }
        }
        out.flush();
        out.close();
    }

    private static int tryState(int totalIndex, int resultIndex, MyRandom random) 
            throws CloneNotSupportedException, IOException {
        // All results were found in the sequence
        if (resultIndex == results.length) {
            // enough forerunners for "randomValue" and "iv" -> quit and report success
            if (totalIndex >= 32 + results.length ) {
                return 1;
            }
            // Not enough forerunners -> report failure
            return 0;
        }
        // Get next random number
        double r = random.nextDouble();
        // Random number fits in the sequence
        if ((int) (r * 10) == results[resultIndex]) {
            // Try for next number in the sequence
            if (tryState(totalIndex + 1, resultIndex + 1, random.cloneRandom()) == 1) {
                out.write(" " + resultIndex + ": " + r + "\n");
                return 1;
            }
        }
        // Random number does not fit at the current position of the sequence, but at the first one -> restart
        else if ((int) (r * 10) == results[0]) {
            if (tryState(totalIndex + 1, 1, random.cloneRandom()) == 1) {
                out.write(" " + 0 + ": " + r + "\n");
                return 1;
            }
        }
        // Random number does not fit in the sequence, but the maximum number of tries is not reached yet 
        else if (totalIndex <= 100) {
            if (tryState(totalIndex + 1, 0, random.cloneRandom()) == 1) {
                out.write(" " + "-: " + r + "\n");
                return 1;
            }
        }
        // Wrong random number and out of tries -> quit
        return 0;
    }
}

"MyRandom" fügt nur das "Cloneable"-Interface zu "Random" hinzu und bietet eine entsprechende öffentliche Methode an:

Code: Alles auswählen

// MyRandom.java
package prng;

import java.util.Random;

public class MyRandom extends Random implements Cloneable {
    
    MyRandom cloneRandom() throws CloneNotSupportedException {
        return (MyRandom) this.clone();
    }
    
}

Läuft so auch ganz gut... bis auf das Ergebnis. Ich bekomme einige Ergebnisse, sie sind aber überschaubar. Das Problem ist, dass die vorhergehenden Zufallszahlen nicht mit "iv" zusammenpassen. Sieht jemand einen Fehler im Code? Hab ich einen falschen Ansatz?

Noch eine Quelle: http://landing2.trusteer.com/sites/defa ... owsers.pdf