Cryptopals zestaw 3 ćwiczenie 23

przez | 9 października 2020

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:

X15X14X13X12X11X10X9X8X7X6X5X4X3X2X1X0
X

XOR

X10X9X8X7X6X5X4X3X2X1X000000
X<<n

=

Y
15
Y
14
Y
13
Y
12
Y
11
Y
10
Y
9
Y
8
Y
7
Y
6
Y
5
X4X3X2X1X0
Y

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)).

X15X14X13X12X11X10X9X8X7X6X5X4X3X2X1X0
X

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
(X<<n)&MASKA

=

Y
15
Y
14
Y
13
Y
12
Y
11
Y
10
Y
9
Y
8
Y
7
Y
6
Y
5
X4X3X2X1X0
Y

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.

Dodaj komentarz

Twój adres email nie zostanie opublikowany.