W duchu zawodów Underhanded C zaczynam zawody Underhanded Code. Celem tego konkursu jest proste wdrożenie kodu, a jednocześnie subtelne ukrywanie w nim nikczemnego błędu.
Zawody
Jesteś tajnym rosyjskim pieprzem pracującym w dziale IT amerykańskiej agencji szpiegowskiej. Twój amerykański szef właśnie poprosił cię o zaimplementowanie algorytmu haszującego hasło do szyfrowania tajnych wiadomości.
Twój szef chce, abyś zaimplementował następującą funkcję:
f: String -> byte[16]
która konwertuje hasło na 16-bajtową liczbę odpowiednią do użycia jako klucz AES. Twój szef chce bezpiecznej funkcji, co w tym kontekście oznacza, że różne ciągi hasła powinny generować różne wyniki z ogromnym prawdopodobieństwem. Na przykład, zwracanie skrótu md5 danych wejściowych byłoby prostą implementacją f
.
Oczywiście twój prawdziwy szef rosyjskiej agencji szpiegowskiej chciałby, abyś obalił ten proces. Twoim zadaniem jest f
takie wdrożenie , aby Rosjanie mogli odszyfrować wszystkie tajne wiadomości zaszyfrowane za pomocą kluczy zwróconych przez f
.
Aby to zrobić, musisz zaimplementować, f
aby zwracał tylko niewielki podzbiór 2 ^ 128 możliwych wyników. W szczególności f
musisz zwrócić co najwyżej 2 ^ 16 różnych wyników, aby Rosjanie mogli z łatwością wyszukać właściwy klucz dla każdej zaszyfrowanej wiadomości, którą chcą odszyfrować.
Pamiętaj jednak, że szpiegostwo niesie ze sobą karę śmierci. Aby nie zostać złapanym, twoja funkcja f
musi wygenerować co najmniej 2 ^ 8 różnych wyników, więc pobieżna kontrola kilku wyników f
nie ujawni duplikatu. A co najważniejsze, kod, który wprowadzasz w celu ograniczenia zakresu, f
musi wyglądać niezamierzenie, a nie celowo. Jeśli kiedykolwiek zostaniesz wciągnięty do sali sądowej, muszą pojawić się uzasadnione wątpliwości, czy błąd został wprowadzony umyślnie, czy przypadkowo.
Osądzać
Ja i dwie osoby, które rekrutuję, ocenię wpisy (napisz do mnie, jeśli chcesz oceniać). Oferuję 200 nagród za wygraną. Zgłoszenia należy przesłać do 1 maja.
Sędziowanie weźmie pod uwagę następujące kryteria:
- Jest
f
zgodny ze specyfikacją, tj. Generuje od 2 ^ 8 do 2 ^ 16 możliwych wyników. Nie uważaj, że są to twarde limity, ale odejmiemy punkty, jeśli będziesz zbyt daleko poza zasięgiem. - Czy błąd jest prawdopodobnie wynikiem niezamierzonego błędu?
- Czy wyjścia
f
wyglądają losowo? - Im krótsza implementacja
f
, tym lepiej. - Im jaśniejsze wdrożenie
f
, tym lepiej.
Notatki
Możesz użyć dowolnego języka do implementacji swojego kodu. Próbujesz ukryć błąd na widoku, więc zaciemniony kod nie jest sugerowany.
Możesz rzucić okiem na niektórych poprzednich zwycięzców konkursu Underhanded C, aby przekonać się, co składa się na dobre zgłoszenie.
Ciągi wejściowe będą drukowane ascii (32 do 126 włącznie). Jeśli chcesz, możesz założyć rozsądną maksymalną długość.
źródło
Odpowiedzi:
do
2 ^ 16 możliwych wyników (lub 2 ^ 8-krotność liczby użytych znaków).
Wykorzystuje implementację MD5 Linuksa, co jest, AFAIK, w porządku. Ale daje to ten sam skrót, na przykład dla „40” i „42”.
EDYCJA: zmieniono nazwę
bcopy
namemcpy
(zamieniono parametry oczywiście).EDYCJA: Przekształcony z programu do działania, aby lepiej spełniać wymagania.
źródło
bcopy
etapie ... jest to dość błędne ukierunkowanie, ponieważ właściwabcopy
funkcja BSD działałaby tutaj poprawnie.bcopy
jest wadliwy. Zmienię to namemcpy
, a wtedy ta sama implementacja stanie się ważna.do
Być może nie jest to najbardziej błyskotliwy wpis w konkursie, ale myślę, że następująca funkcja haszująca mogłaby być wykonana przez dowolnego programistę zbyt sprytnego dla własnego dobra, z niejasnym wyobrażeniem o rodzajach operacji widocznych w funkcjach skrótu:
W rzeczywistości funkcja skrótu może zwrócić nie więcej niż L * 2048 różnych wyników, gdzie L jest liczbą różnych długości łańcucha wejściowego, które mogą wystąpić. W praktyce przetestowałem kod na 1,85 miliona unikatowych wierszy wejściowych ze stron podręcznika i dokumentów HTML na moim laptopie i uzyskałem tylko 85428 różnych unikatowych skrótów.
źródło
Scala:
Przetestuj, jeśli wynik nie wygląda podobnie dla podobnych danych wejściowych:
Błąd polega na użyciu tylko liczb pierwszych do kodowania. Zamiast
wartości, kończymy na
ponieważ jest 54 liczb pierwszych poniżej 256.
źródło
5.22e27 >> 2^16
. Tak wiele możliwości nie ma sposobu na brutalną siłę.