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.

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; key: 1337

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ę!

Comments:

2016-08-11 01:07:46 = ethann
{
Może coś jak "odwrotny regex" do wygenerowania tych różnych możliwych wiadomości?
W poniższym skrypcie expander() znalazłem na stack'u i przerobiłem lekko. Są zewnętrzne biblioteki do generowania możliwych rozwiązań regexów (np. exrex), ale wolałem na szybko znaleźć coś krótkiego z użyciem domyślnych libek. Na tą sytuację zadziała ;>

http://wklej.org/id/2781217/
}
2016-08-11 01:15:22 = Gynvael Coldwind
{
@ethann
Niezłe! Coś mi świtało, że w itertools jest coś co mogłoby się przydać :)
}
2016-08-11 09:41:12 = skomak
{
Bardzo ciekawy wpis. Mimo, że deszyfrowanie tej pocztówki nie było raczej skomplikowane to sama kryptoanaliza przykuła moją uwagę. Więcej takich wpisów ;)
}
2016-08-11 20:12:58 = bl4de
{
Popieram to, co napisał @skomak i w sumie to może fajnie byłoby ten wpis rozwinął w taki mały poradnik, jak "podchodzić" do podobnych rzeczy np. na CTF-ach?
}

Add a comment:

Nick:
URL (optional):
Math captcha: 4 ∗ 5 + 1 =