Pamiętacie mój crypto-challenge "Pocztówka z Doliny Krzemowej" (#1, #2)? Przyszła kolej i na mnie - dzisiaj w poranno-popołudniowej poczcie znalazłem pocztówkę od KrzaQ, która zdecydowanie wymagała rozszyfrowania przed przeczytaniem. Poniżej zdjęcie samej pocztówki, jak i rozwiązanie zagadki w kilku krokach.


Jak widać powyżej dostępny był zarówno szyfrogram, jak i klucz - pozostało więc wymyślić algorytm (nie będzie to więc trudna zagadka). Zacząłem od dokładnego przyjrzenia się danym informacjom - zazwyczaj pozwala to zawęzić grupę możliwych algorytmów poprzez eliminację szyfrów, które raczej nie są prawdopodobne w tym wypadku, lub zwiększeniu "wagi" innych szyfrów, które będzie warto spróbować w pierwszej kolejności. Kilka rzeczy, które zauważyłem:

• Klucz to heksadecymalnie 0539h - tj. nie ma w nim zapalonych najstarszych bitów danych bajtów (binarnie: 00000101 00111001). W szyfrogramie są bajty z zapalonymi najstarszymi bitami, i to całkiem sporo. W ASCII bajty nigdy nie mają zapalonego najstarszego bitu, więc z dużym prawdopodobieństwem nie będzie to XOR. Można by kontrargumentować, że w UTF-8 już się zdarzają zapalone najstarsze bity w bajtach, natomiast spodziewałem się wiadomości raczej po polsku lub angielsku, a tam najstarsze bity się pojawiają raczej rzadko (tylko w przypadku znaków diakrytyzowanych typu: ążśźęćńół), i jak już to występują w parach (np. ą to C4 85) - ten warunek nie zawsze jest spełniony w szyfrogramie, więc można ten kontrargument odrzucić. Podobnie UTF-16/UCS-2 odpadają, ponieważ parzyste/nieparzyste (LE/BE) bajty byłyby prawie zawsze równe jednemu z bajtów klucza (tj. w wiadomości byłyby równe zero, a XOR bajtu klucza z zerem da oczywiście dany bajt klucza w wyniku). UTF-32 ani innych kodowań się nie spodziewałem (tj. prawdopodobieństwo ich użycia było zaniedbywalne na tym etapie).
• Szyfrogram składa się z 74 bajtów. Liczba ta nie jest podzielna ani przez 4, ani przez 5, ani przez 8, ani tym bardziej przez 16 czy 32 - to pozwala w zasadzie odrzucić większość szyfrów blokowych.
• Klucz jest zapisany jako liczba (a nie np. jako ciąg bajtów) - to w niewielkim stopniu (ale jednak) zwiększa prawdopodobieństwo szyfru, w którym trzeba szyfrogram potraktować jako jedną długą liczbę (jak np. w RSA).
• Pierwszy nibble (cyfra szesnastkowa) to 0 - to również w niewielkim stopniu zwiększa prawdopodobieństwo użycia szyfru tego typu.
• Bardzo mało wartości bajtów się powtarza, tj. entropia jest dość wysoka. To w zasadzie eliminuje proste szyfry podstawieniowe.

Powyższa dedukcja nie pozwoliła mi jednoznacznie wskazać szyfru, ale pozwoliła wybrać rodzinę szyfrów od której zacznę próbować, tj. szyfry "matematyczne", w których wiadomość jest liczbą.

W tym momencie stwierdziłem, że dane trzeba przepisać - pewnym (spodziewanym) problemem okazało się rozróżnienie cyfry "3" od "9" w kilku przypadkach. Ostatecznie byłem prawie przekonany, że są to dziewiątki, ale uznałem, że lepiej zagrać bezpiecznie i dane przepisać z obiema możliwościami. Do pliku tekstowego trafiło więc coś takiego:

0F F7 DA 29 D1 29 D5 31 48 C8
BF 8E 8C 3B D3 47 51 43 79 7A
0C 22 AE 55 17 00 47 2F 33 34
ED E2 C7 6A 5[93] AF 78 14 00 AA
4E 65 [39]2 4F 53 [93]0 D7 0C A5 0E
CC C5 4F 26 BC FD E6 C9 1B FF
A4 2D 42 B5 35 7F FC A1 6F A7
2E 2B 4C 0A
W nawiasach kwadratowych odnotowałem różne możliwości wystąpienia znaków w danym miejscu. Pozostało napisać skrypt w Pythonie, który z owych "możliwości" wygeneruje mi wszystkie możliwe ciągi. To sprowadziło się do następującego kodu (btw, ma ktoś pomysł jak to krócej zapisać? w rozumieniu: wykorzystać jakieś Pythonowe funkcje biblioteczne lub idiomy, które to skrócą, a nie krótszego zapisu tego co jest):

def GetDataSetsWorker(dataset, s, idx, current=""):
 i = idx
 l = len(s)
 while i < l:
   if s[i] == '[':
     break
   current += s[i]
   i += 1

 if i == l:
   dataset.append(current)
   return

 i += 1  # Skip opening [
 chars = []
 while s[i] != ']':
   chars.append(s[i])
   i += 1

 i += 1  # Skip closing ]
 for ch in chars:
   GetDataSetsWorker(dataset, s, i, current + ch)


def GetDataSets():
 with open("data") as f:
   d = f.read().replace(" ", "").replace("\n", "")

 data = []
 GetDataSetsWorker(data, d, 0)

 return data
Po przetestowaniu powyższego kodu i poprawieniu literówek, dostałem 8 różnych ciągów. Dotarłem więc do pytania, jakiego przekształcenia matematycznego użyć w tym wypadku. Postanowiłem zacząć od potęgowania i pierwiastka (stopnia key), ale to okazało się zupełnie nietrafione z oczywistych powodów (liczba w wiadomości jest zdecydowanie za mała na pierwiastek stopnia 1337; potęga też za bardzo by tu nie miała sensu, choć z nią by można trochę popracować już).

Dwie kolejne, prostsze, operacje, które postanowiłem wypróbować to mnożenie i później dzielenie:

sets = GetDataSets()
key = 1337

for s in sets:
 print len(s)/2
 k = int(s, 16)
 k = k * 1337
 print hex(k)[2:-1].decode("hex")
Po uruchomieniu okazało się, że trafiłem w algorytm:

Serdeczne pozdrowienia ze słonecznej wyspy Kos!

KrzaQ

PS: padding      :
I tak oto mogłem w końcu odczytać wiadomość na pocztówce :)
Całość na oko zajęła mi jakieś 15 minut + przepisanie kodu z pocztówki.

I tyle :)

P.S. KrzaQ - dzięki za pocztówkę!