Paweł Goleń, blog

Pierwsze pytanie, na ile sposobów można ułożyć poszczególne hasła jednorazowe w maski? Długość sekretu to 6 znaków, przyjmijmy więc, że zadanie to sprowadza się do wyboru k numerów z zakresu 1-6 (n elementów), które będą określały pozycje znaków w masce. Oczywiście wybierać można bez powtórzeń. Są to kombinacje bez powtórzeń, tak więc ilość generowanych masek określamy ze wzoru:

n!/k!(n-k)!

Ilość możliwych kombinacji wynosi więc (w zależności od ilości wybieranych elementów, która w tym wypadku odpowiada długości hasła jednorazowego):

1	6
2	15
3	20
4	15
5	6
6	1

Ponieważ chodzi mi tutaj o ograniczenie ilości obliczeń, chcę ograniczyć ilość "możliwych" masek. Ilość ta jest najmniejsza dla najkrótszych i najdłuższych przypadków. W tym wypadku najdłuższe hasło jednorazowe ma 4 znaki, daje to więc 15 możliwych masek. Na początek.

Pozostałe hasła jednorazowe mają długość 3 znaków, tak więc każde z nich można ułożyć na 20 sposobów. Maksymalna ilość możliwych sekretów uzyskana po kroku drugim wynosi 15 * 20 = 300. Oczywiście w rzeczywistości jest ich dużo mniej, bo nie każda para pozwala na wygenerowanie "sensownej" maski.

Czy w tej chwili warto wybrać hasło jednorazowe bardziej, czy mniej podobne do hasła początkowego? Wydaje mi się, że w tym przypadku dobrze jest wybrać hasła odległe, zawierające jak najmniej wspólnych znaków. Dlaczego?

Porównajmy hasła jednorazowe 125, 356 i 234 dla przykładowej maski:

_2_346

Dla hasła 125 istnieje tylko jeden możliwy produkt:

125346

Dla hasła 356 też istnieje tylko jeden możliwy produkt:

324346

Dla hasła 234 możliwości jest więcej:

223346
_23346
_2_346

"Skrzyżowanie" ze sobą hasła 2346 oraz 234 w żaden sposób nie ogranicza ilości możliwych sekretów, zwiększa tylko ilość pracy, który w kolejnym kroku trzeba wykonać.

Można tu posłużyć się następującym rozumowaniem (szacowanie bardzo z góry). Dla maski _2_346 pozostają dwie "wolne" pozycje. Znak z kolejnego hasła jednorazowego (np. 234) możemy wstawić, jeśli pozycja jest "wolna" lub na określonej pozycji znajduje się już taki znak. Im mniej pozycji, na które można wstawić znaki, tym mniej możliwości ich ustawienia.

Pomińmy w tej chwili na moment wymaganie, by znaki były wstawiane w (odpowiedniej) kolejności. Dla maski _2_346 oraz hasła 234 zbiór dopuszczalnych pozycji zawiera:

• 1 - bo pozycja jest "wolna",
• 2 - bo występuje tu znak 2, który występuje również w haśle jednorazowym,
• 3 - bo pozycja jest "wolna",
• 4 - bo występuje tu znak 3, który występuje również w haśle jednorazowym,
• 5 - bo występuje tu znak 4, który występuje również w haśle jednorazowym,

Analogiczny zbiór dla hasła jednorazowego 356 zbiór tych pozycji jest mniejszy:

• 1 - bo pozycja jest wolna,
• 3 - bo pozycja jest wolna,
• 6 - bo występuje tu znak 6, który występuje również w haśle jednorazowym,

W pierwszym przypadku mamy więc 5 możliwych pozycji, w drugim - 3. W obu przypadkach ilość wybieranych elementów to 3 (długość hasła jednorazowego). W pierwszym przypadku daje to 10 możliwości, w drugim tylko jedną możliwość. W obu przypadkach ilość ta może być dalej redukowana przez dodatkowe wymagania, choćby kolejność występowania znaków.

Swoje "eksperymenty myślowe" wspieram eksperymentami praktycznymi. Nie pozostaje mi w takim razie nic innego, niż dopisać w moim skrypcie testowym funkcję sortowania haseł jednorazowych, która:

• wybiera hasło startowe h1 (najdłuższe z haseł jednorazowych),
• wybiera najdłuższe hasło kolejne hN takie, dla którego część wspólna (występujące znaki) w h1 do h(N-1), jest najmniejsza,

Ciekawe jak teoria sprawdzi się w praktyce ;)

Całość sprawdzam na sekrecie długości 15 znaków, maski pochodzą z pewnego, prawdziwego źródła. Eksperyment (jego wyniki) w praktyce wygląda tak... Posortowana już lista haseł jednorazowych (na wejściu 10 losowych masek):

['OgeOkmosk', 'Ogdykausk', 'Odyeamok', 'OgOkmusk', 'gdykaou', '6OAeOks', 'OAdekos', 'gdyOao', 'gAyOk', 'OAeO']

Na wyjściu otrzymuję listę możliwych haseł:

6OgAdyeOkamousk

A wszystko to w czasie:

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 20:33:59 2012
TimeThis :      End Time :  Mon Jan 09 20:36:14 2012
TimeThis :  Elapsed Time :  00:02:15.501

Ten sam przypadek z nieco inną listą danych na wejściu:

['gAdeOkmouk', 'gdyOkmusk', 'OgdyOmou', 'OAdeOaok', 'OyOamsk', '6OAeOks', 'yekamu', '6yeOmo', 'Oyauk', 'Aeao']

Wynik (a to niespodzianka):

6OgAdyeOkamousk

Wszystko to w (lepszym) czasie:

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 20:37:38 2012
TimeThis :      End Time :  Mon Jan 09 20:38:37 2012
TimeThis :  Elapsed Time :  00:00:59.085

Teraz przykład dla innego sekretu (pozostałe warunki takie same):

['aSyfipDyji', 'vyfiaDbji', 'Jvyfipybj', 'avfiybi', 'JffaDji', 'avyiybi', 'vSfipy', 'avyaj', 'yiybi', 'ypDy']

JavSfyfipaDybji
JavSfyfiapDybji
JavSyfifapDybji
JavSyffipaDybji
JavSyfifpaDybji
JavSyffiapDybji
JavSyfipfaDybji
JavfSyfipaDybji
JavfSyfiapDybji
JafvSyfipaDybji
JafvSyfiapDybji
JfavSyfipaDybji
JfavSyfiapDybji
aJfvSyfipaDybji
aJfvSyfiapDybji
aJvSyfifpaDybji
aJvSyfifapDybji
aJvSyffiapDybji
aJvSfyfipaDybji
aJvSfyfiapDybji
aJvSyfipfaDybji
aJvSyffipaDybji
aJvfSyfipaDybji
aJvfSyfiapDybji

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 20:39:59 2012
TimeThis :      End Time :  Mon Jan 09 20:40:35 2012
TimeThis :  Elapsed Time :  00:00:35.891

Jak widać w tym przypadku nie udało się ustalić jednoznacznie sekretu na podstawie dostępnych danych. A ten przypadek jest jeszcze bardziej pechowy:

['vSyfiybi', 'JSffiDyb', 'avSfpDbi', 'JffiDy', 'Jvfbji', 'vSayi', 'aSaji', 'JaSfy', 'JSaj', 'Sfpy']

JavSayfpfiDybji
JavSyfpafiDybji
(... w sumie 49 możliwych haseł ...)

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 20:41:13 2012
TimeThis :      End Time :  Mon Jan 09 20:51:56 2012
TimeThis :  Elapsed Time :  00:10:42.430

...choć i dla niego czasami świeci słońce (bardziej):

['avSffipDyj', 'JaSyfapyb', 'aSyfipyi', 'avSfapDb', 'avSfpDy', 'ayfpji', 'JyffDb', 'vSfiyb', 'vaybj', 'ffpDb']

JavSyffiapDybji
JavSyffaipDybji
JavSyfafipDybji

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 20:54:08 2012
TimeThis :      End Time :  Mon Jan 09 20:54:31 2012
TimeThis :  Elapsed Time :  00:00:22.687

W tym wypadku udało się bardzo szybko ustalić trzy możliwe sekrety.

Ten sam przypadek, gdy mogę wybierać spośród wszystkich istniejących w systemie masek dla tego sekretu:

['vSyfiaDybi', 'JvSyfiaDbj', 'Javyfiapji', 'JaSfiaDbji', (...) ]

JavSyffiapDybji

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 20:56:27 2012
TimeThis :      End Time :  Mon Jan 09 20:56:55 2012
TimeThis :  Elapsed Time :  00:00:27.844

Jak na razie moja ciekawość odnośnie tego, jak bardzo skomplikowane jest odtworzenie całości sekretu z jego poszczególnych kawałków, została zaspokojona. Być może do tematu powrócę by poszukać takich parametrów "masek", by odzyskanie sekretu w opisany tutaj (i wcześniej) sposób, kosztowało jak najwięcej. Inna sprawa, że jednocześnie można poprawić algorytm poszukiwania rozwiązania na taki, który jest mniej naiwny. Komuś się nudzi? :)

P.S. Jak się można było spodziewać, w moim PoC (funkcja sortowania haseł) były błędy. Konkretnie dwa, przez co hasła jednorazowe były sortowane nie do końca zgodnie z moimi zamierzeniami. Jaka różnica? Cóż, powiedzmy, że czas wykonania ostatniego przykładu teraz wygląda tak:

['vSyfiaDybi', 'JaSffipybj', 'vSaj', 'JSaj', 'ypDy', (...)

JavSyffiapDybji

TimeThis :  Command Line :  masked2.py
TimeThis :    Start Time :  Mon Jan 09 21:37:06 2012
TimeThis :      End Time :  Mon Jan 09 21:37:14 2012
TimeThis :  Elapsed Time :  00:00:08.218

Najlepszy dowód na to, że kolejność MA znaczenie :)