Cryptopals zestaw 3 ćwiczenie 23

W tym ćwiczeniu naszym zadaniem jest sklonowanie generatora liczb losowych. Sklonowany generator umożliwi nam przewidywanie kolejnych wartości zwracanych przez oryginalny generator.

Zadanie na pierwszy rzut oka wydaje się niemożliwe, ale przyjżyjmy się jak wygląda funkcja generująca kolejne liczby pseudolosowe:

    def extractNumber(self):
        if self._gMTidx == 0:
            self._generateNumbers()
        
        tmp = self._gMT[self._gMTidx]
        tmp = (tmp ^ (tmp>>11))&0xffffffff
        tmp = (tmp ^ ((tmp<<7) & 0x9d2c5680))&0xffffffff
        tmp = (tmp ^ ((tmp<<15) & 0xefc60000))&0xffffffff
        tmp = (tmp ^ (tmp>>18))&0xffffffff
        self._gMTidx = (self._gMTidx+1)%len(self._gMT)
        return tmp

Stan generatora zapisany jest w tablicy 624 liczb 32-bitowych, sklonowanie go będzie polegało na odtworzeniu tych 624 wartości. Okazuje się, że na podstawie liczby pseudolosowej zwracanej przez generator jesteśmy w stanie odtworzyć wartość z której została wygenerowana, czyli jedną z 624 liczb które opisują stan tego generatora. Wszystko co musimy zrobić to wykonać 4 operacje, które będą odwrotne względem tych wykonanych podczas generowania liczby.

Na początku warto zauważyć, że operację X ^ (X << n) i X ^ (X >> n) można traktować tak samo, jeżeli odwrócimy kolejność bitów w zmiennej X. Warto o tym pamiętać bo dzięki temu będziemy mogli użyć tego samego algorytmu w obydwu wypadkach, jeżeli tylko na początku i na końcu odwrócimy kolejność bitów.

Na razie skupmy się na przypadku kiedy wartość (X<<n) nie jest dodatkowo maskowana, czy nie rozpatrujemy przypadku: ((X<<n)&MASKA). Na razie założymy, że liczby są 16-bitowe i chcemy wykonać operację: X ^ (X<<5). W przypadku takiego działania sytuacja wygląda następująco:

X15

X14

X13

X12

X11

X10

X9

X8

X7

X6

X5

X4

X3

X2

X1

X0

XOR

X10

X9

X8

X7

X6

X5

X4

X3

X2

X1

X0

0

0

0

0

0

=

Y 15

Y 14

Y 13

Y 12

Y 11

Y 10

Y 9

Y 8

Y 7

Y 6

Y 5

X4

X3

X2

X1

X0

O ile N będzie większe 0 da się odtworzyć wartość X. Bity od 0 do N-1 pozostają niezmienione, a kolejne bity można odtworzyć według wzoru:
Xi = Yi ^ X(i-n) dla i od n do 16. Czyli w naszym przykładzie:
X0 = Y0,
X1 = Y1,
X2 = Y2,
X3 = Y3,
X4 = Y4,
X5 = Y5 ^ X0,
X6 = Y6 ^ X1,
…
X15 = Y15 ^ X10.

Teraz możemy to dodać do naszego równania maskowanie: Y = X ^ ((X<<n) & MASKA)).

X15

X14

X13

X12

X11

X10

X9

X8

X7

X6

X5

X4

X3

X2

X1

X0

XOR

X10 &M15

X9 &M14

X8 &M13

X7 &M12

X6 &M11

X5 &M10

X4 &M9

X3 &M8

X2 &M7

X1 &M6

X0 &M5

0 & M4

0 &M3

0 &M2

0 &M1

0 ^M0

=

Y 15

Y 14

Y 13

Y 12

Y 11

Y 10

Y 9

Y 8

Y 7

Y 6

Y 5

X4

X3

X2

X1

X0

Tak na prawdę za dużo to nie zmienia, jedyne co musimy pamiętać, to to żeby dla bitów o indeksach >= n bit X(indeks-5) dodatkowo ANDować z bitem MASKAindeks. Czyli w naszym przykładzie: Y = X ^ ((X<<5)&MASKA):

X0 = Y0,
X1 = Y1,
X2 = Y2,
X3 = Y3,
X4 = Y4,
X5 = Y5 ^ (X0 & MASKA5),
…
X15 = Y15 ^ (X10 & MASKA15)

Mój kod kod wygląda następująco:

def _invertValue(value):
    result = 0;
    for _ in range(32):
        result = (result<<1) | (value&0x1)
        value = value>>1
    return result

def _revertXorShifMask(value, shift, mask):
    """shift > 0 - shl, shift < 0 shr"""
    result = 0
    shiftC = shift
    if shift < 0:
        value = _invertValue(value)
        shiftC = abs(shift)
    
    for idx in range(32):
        if idx < shiftC:
            result = result | (value & (0x1<<idx))
        else:
            tmp = (value & (0x1<<idx))
            xorBit = result&(0x1<<(idx-shiftC))
            xorBit = xorBit << shiftC
            maskBit = (mask&(0x1<<idx))
            tmp = tmp ^ (xorBit&maskBit)
            result = result | tmp

    if (shift < 0):
        result = _invertValue(result)
    return result

Dodatkowo odwracam kolejność bitów jeżeli operacja przesunięcia bitowego była wykonywana w prawą stronę, a po odtworzeniu oryginalnej wartości ponownie odwracam kolejność bitów. To wszystko zebrane w całość umożliwia odtworzenie wartości z tablicy stanów na podstawie wygenerowanej liczny za pomocą takiej oto funkcji:

def untemperNumber(value):
    tmp = value
    tmp = _revertXorShifMask(tmp, -18, 0xffffffff)
    tmp = _revertXorShifMask(tmp, 15, 0xefc60000)
    tmp = _revertXorShifMask(tmp, 7, 0x9d2c5680)
    tmp = _revertXorShifMask(tmp, -11, 0xffffffff)
    return tmp

Kiedy mamy już taką funkcję wystarczy wygenerować 624 liczby w celu odtworzenia całej tablicy stanów a wtedy możemy stworzyć klon danego generatora:

def s3challenge23():
    print("Challenge 23")
    orig_randgen = mtrng.MTRng(int(datetime.now().timestamp()))
    orig_states = [0] * 624
    for i in range(624):
        orig_states[i] = mtrng.untemperNumber(orig_randgen.extractNumber())
    
    clone_randgen = mtrng.MTRng(0)
    clone_randgen.updateState(orig_states)
    orig_val = orig_randgen.extractNumber()
    clone_val = clone_randgen.extractNumber()
    if (orig_val == clone_val):
        print("Successfully cloned random number generator")
    else:
        print("Failed to clone random number generator")

Całość dostępna na gitlabie: https://gitlab.com/akoltys/cryptopals.