Cryptopals zestaw 3 ćwiczenie 19

przez | 8 września 2020

To ćwiczenie będzie rozwiązane inaczej niż wszystkie z którymi musieliśmy się zmierzyć do tej pory. Początkowo nie do końca zrozumiałem intencje twórców, ale po dłuższym zastanowieniu się stwierdziłem, że moje pierwotne rozwiązanie pomimo, że odszyfrowało treść wiadomości to nie działało w sposób jaki mieli na myśli autorzy, ale zacznijmy od początku.

W tym zadaniu dostajemy czterdzieści krótkich wiadomości, które po zdekodowaniu z base64 mają zostać zaszyfrowane AES CTR i zwrócone do nas abyśmy je odszyfrowali. Pierwszy krok jest standardowy, ponieważ należy stworzyć wyrocznię która zwróci nam zaszyfrowane wiadomości. Ułomność tej wyroczni polega na tym, że każda z czterdziestu wiadomości, jest szyfrowana oddzielnie z użycie tej samej wartości NONCE, a to oznacza, że wszystkie wiadomości są XORowane z takim samym kluczem. Kod wyroczni poniżej:

class OracleCtrRepeatingNonce(object):
    
    M_SECRETS = [
        b'SSBoYXZlIG1ldCB0aGVtIGF0IGNsb3NlIG9mIGRheQ==',
        b'Q29taW5nIHdpdGggdml2aWQgZmFjZXM=',
        b'RnJvbSBjb3VudGVyIG9yIGRlc2sgYW1vbmcgZ3JleQ==',
        b'RWlnaHRlZW50aC1jZW50dXJ5IGhvdXNlcy4=',
        b'SSBoYXZlIHBhc3NlZCB3aXRoIGEgbm9kIG9mIHRoZSBoZWFk',
        b'T3IgcG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==',
        b'T3IgaGF2ZSBsaW5nZXJlZCBhd2hpbGUgYW5kIHNhaWQ=',
        b'UG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==',
        b'QW5kIHRob3VnaHQgYmVmb3JlIEkgaGFkIGRvbmU=',
        b'T2YgYSBtb2NraW5nIHRhbGUgb3IgYSBnaWJl',
        b'VG8gcGxlYXNlIGEgY29tcGFuaW9u',
        b'QXJvdW5kIHRoZSBmaXJlIGF0IHRoZSBjbHViLA==',
        b'QmVpbmcgY2VydGFpbiB0aGF0IHRoZXkgYW5kIEk=',
        b'QnV0IGxpdmVkIHdoZXJlIG1vdGxleSBpcyB3b3JuOg==',
        b'QWxsIGNoYW5nZWQsIGNoYW5nZWQgdXR0ZXJseTo=',
        b'QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=',
        b'VGhhdCB3b21hbidzIGRheXMgd2VyZSBzcGVudA==',
        b'SW4gaWdub3JhbnQgZ29vZCB3aWxsLA==',
        b'SGVyIG5pZ2h0cyBpbiBhcmd1bWVudA==',
        b'VW50aWwgaGVyIHZvaWNlIGdyZXcgc2hyaWxsLg==',
        b'V2hhdCB2b2ljZSBtb3JlIHN3ZWV0IHRoYW4gaGVycw==',
        b'V2hlbiB5b3VuZyBhbmQgYmVhdXRpZnVsLA==',
        b'U2hlIHJvZGUgdG8gaGFycmllcnM/',
        b'VGhpcyBtYW4gaGFkIGtlcHQgYSBzY2hvb2w=',
        b'QW5kIHJvZGUgb3VyIHdpbmdlZCBob3JzZS4=',
        b'VGhpcyBvdGhlciBoaXMgaGVscGVyIGFuZCBmcmllbmQ=',
        b'V2FzIGNvbWluZyBpbnRvIGhpcyBmb3JjZTs=',
        b'SGUgbWlnaHQgaGF2ZSB3b24gZmFtZSBpbiB0aGUgZW5kLA==',
        b'U28gc2Vuc2l0aXZlIGhpcyBuYXR1cmUgc2VlbWVkLA==',
        b'U28gZGFyaW5nIGFuZCBzd2VldCBoaXMgdGhvdWdodC4=',
        b'VGhpcyBvdGhlciBtYW4gSSBoYWQgZHJlYW1lZA==',
        b'QSBkcnVua2VuLCB2YWluLWdsb3Jpb3VzIGxvdXQu',
        b'SGUgaGFkIGRvbmUgbW9zdCBiaXR0ZXIgd3Jvbmc=',
        b'VG8gc29tZSB3aG8gYXJlIG5lYXIgbXkgaGVhcnQs',
        b'WWV0IEkgbnVtYmVyIGhpbSBpbiB0aGUgc29uZzs=',
        b'SGUsIHRvbywgaGFzIHJlc2lnbmVkIGhpcyBwYXJ0',
        b'SW4gdGhlIGNhc3VhbCBjb21lZHk7',
        b'SGUsIHRvbywgaGFzIGJlZW4gY2hhbmdlZCBpbiBoaXMgdHVybiw=',
        b'VHJhbnNmb3JtZWQgdXR0ZXJseTo=',
        b'QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4='
    ]
    
    M_ENCRYPTION_KEY = b''
    
    def __init__(self):
        self.M_SECRETS = [bytearray(bytes_from_base64(x)) for x in self.M_SECRETS]
        self.M_ENCRYPTION_KEY = generateRandomData(16)
        self.M_NONCE = c_uint64(0)
    
    def getSecrets(self):
        cipher = CustomAES()
        return [cipher.encode(secret, self.M_ENCRYPTION_KEY, CustomAES.Mode.CTR,
                              self.M_NONCE) for secret in self.M_SECRETS]

Pierwsza myśl, która przyszła mi do głowy to: hej, przecież już coś takiego robiłem w jednym pierwszych ćwiczeń, wtedy ciąg z którym była XORowana wiadomość miał inną długość, ale zasada była ta sama – wiemy, że wiadomość jest tekstowa w związku z tym tak dobieramy klucz, żeby uzyskać wiadomość, która będzei zawierała najwięcej znaków które najczęściej występują w języku angielskim.

Użyłem skryptu, który został napisany do rozwiązania zadania numer 6 z zestawu 1 (https://cryptopals.com/sets/1/challenges/6) i faktycznie wszystko zadziałało tak jak powinno. Zadanie zostało rozwiązane w rekordowo, krótkim czasie. Kiedy zobaczyłem treść kolejnego zadania, okazało się że znów trzeba będzie użyć tego samego skryptu. Nie dawało mi to spokoju, ponieważ uważałem, że twórcy musieli chcieć coś nam pokazać.

Po namyśle, doszedłem do wniosku, że może powinienem rozwiązać to zadanie ręcznie, bez użycia tamtego skryptu. Zadanie było proste: wszystkie kolejne znaki z zaszyfrowanej wiadomości XORuję z bajtami od 0 do 255 i sprawdzam dla którego bajtu będę miał najwięcej znaków które są używane w języku angielskim (założyłem, że powinny tam znaleźć się białe znaki, apostrofy, litery, cyfry itd.). Robienie tego znak po znkau było dośc uciążliwe, w związku z tym pomyślałem, że może stworzę narzędzie które będzie mi w locie wyświetlało wynik XORowania kolejnych znaków we wszystkich wiadomościach. Najłatwiej było by napisać to coś takiego w postaci strony WWW, bo dzięki temu mogłem to również udostępnić w postaci dema dostępnego pod tym adresem: https://koltys.info/ctrrepetnoncebreaker/. Moim zdaniem twórcy chcieli pokazać, dlaczego używanie wartości NONCE więcej niż jeden raz jest bardzo złym pomysłem. Jeżeli mamy kilka wiadomości zaszyfrowanych z tą samą wartością NONCE, odszyfrowanie ich może być znacznie prostsze, nawet jeżeli nie użyjemy do tego żadnych narzędzi.

Na potrzeby prezentacji, zostały wygenerowane dane testowy i na sztywno zaszyte w źródle strony, nic nie stoi na przeszkodzie, żeby dane były ładowane dynamicznie, więc jeżeli ktoś będzie miał na to czas i ochotę może to w ramach dodatkowego ćwiczenia. Kod Pythonowy dostępny jest tutaj: https://gitlab.com/akoltys/cryptopals . Kod dema można również pobrać z repozytorium: https://gitlab.com/akoltys/ctrbreakerdemo .

Dodaj komentarz

Twój adres email nie zostanie opublikowany.