Podstępne hashowanie hasła [zamknięte]

33

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 ftakie wdrożenie , aby Rosjanie mogli odszyfrować wszystkie tajne wiadomości zaszyfrowane za pomocą kluczy zwróconych przez f.

Aby to zrobić, musisz zaimplementować, faby zwracał tylko niewielki podzbiór 2 ^ 128 możliwych wyników. W szczególności fmusisz 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 fmusi wygenerować co najmniej 2 ^ 8 różnych wyników, więc pobieżna kontrola kilku wyników fnie ujawni duplikatu. A co najważniejsze, kod, który wprowadzasz w celu ograniczenia zakresu, fmusi 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 fzgodny 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 fwyglą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ść.

Keith Randall
źródło
1
czy są jakieś ograniczenia dotyczące ciągu wejściowego? jakby składa się tylko z alfabetu?
Ali1S232,
@Gajet: musisz obsłużyć wszystkie drukowane znaki ascii (od 32 do 126 włącznie).
Keith Randall
Czy zakres wyjściowy obejmuje wszystkie 16-bajtowe ciągi, czy tylko te do wydrukowania?
stoisko
@boothby: wszystkie możliwe 16-bajtowe wartości (2 ^ 128 możliwości)
Keith Randall
1
Głosuję za zamknięciem tego pytania jako nie na temat, ponieważ słabe wyzwania nie są już na ten temat na tej stronie. meta.codegolf.stackexchange.com/a/8326/20469
kot

Odpowiedzi:

15

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ę bcopyna memcpy(zamieniono parametry oczywiście).
EDYCJA: Przekształcony z programu do działania, aby lepiej spełniać wymagania.

#include <string.h>
#include <openssl/md5.h>

void f(const unsigned char *input, unsigned char output[16]) {

    /* Put the input in a 32-byte buffer, padded with zeros. */
    unsigned char workbuf[32] = {0};
    strncpy(workbuf, input, sizeof(workbuf));

    unsigned char res[MD5_DIGEST_LENGTH];
    MD5(workbuf, sizeof(workbuf), res);

    /* NOTE: MD5 has known weaknesses, so using it isn't 100% secure.
     * To compensate, prefix the input buffer with its own MD5, and hash again. */
    memcpy(workbuf+1, workbuf, sizeof(workbuf)-1);
    workbuf[0] = res[0];
    MD5(workbuf, sizeof(workbuf), res);

    /* Copy the result to the output buffer */
    memcpy(output, res, 16);
}

/* Some operating systems don't have memcpy(), so include a simple implementation */
void *
memcpy(void *_dest, const void *_src, size_t n)
{
    const unsigned char *src = _src;
    unsigned char *dest = _dest;
    while (n--) *dest++ = *src++;
    return _dest;
}
ugoren
źródło
czy to wada z MD5?
Ali1S232
@Gajet, Nie, użyłem Linuksa MD5, co jest całkowicie OK (AFAIK).
ugoren
dlaczego nie generuje więcej możliwych wyników?
Ali1S232
1
@Gajet: Zastanów się, co dzieje się na tym bcopyetapie ... jest to dość błędne ukierunkowanie, ponieważ właściwa bcopyfunkcja BSD działałaby tutaj poprawnie.
han
@han, właściwie teraz widzę, że mój bcopyjest wadliwy. Zmienię to na memcpy, a wtedy ta sama implementacja stanie się ważna.
ugoren
13

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:

#include <stdio.h>
#include <string.h>
#include <stdint.h>

void hash(const char* s, uint8_t* r, size_t n)
{
     uint32_t h = 123456789UL;
     for (size_t i = 0; i < n; i++) {
          for (const char* p = s; *p; p++) {
               h = h * 33 + *p;
          }
          *r++ = (h >> 3) & 0xff;
          h = h ^ 987654321UL;
     }
}

int main()
{
     size_t n = 1024;
     char s[n];
     size_t m = 16;
     uint8_t b[m];
     while (fgets(s, n, stdin)) {
          hash(s, b, m);
          for (size_t i = 0; i < m; ++i)
               printf("%02x", b[i]);
          printf("\n");
     }
}

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.

Han
źródło
0

Scala:

// smaller values for more easy tests:
val len = 16
// make a 16 bytes fingerprint
def to16Bytes (l: BigInt, pos: Int=len) : List[Byte] = 
  if (pos == 1) List (l.toByte) else (l % 256L).toByte :: to16Bytes (l / 256L, pos-1)
/** if number isn't prime, take next */
def nextProbPrime (l: BigInt) : BigInt = 
  if (l.isProbablePrime (9)) l else nextProbPrime (l + 1)
/** Take every input, shift and add, but take primes */
def codify (s: String): BigInt = 
  (BigInt (17) /: s) ((a, b) => nextProbPrime (a * BigInt (257) + b))
/** very, very short Strings - less than 14 bytes - have to be filled, to obscure them a bit: */
def f (s: String) : Array [Byte] = {
  val filled = (if (s.size < 14) s + "secret" + s else s)
  to16Bytes (codify (filled + filled.reverse)).toArray.map (l => nextProbPrime (l).toByte) 
}

Przetestuj, jeśli wynik nie wygląda podobnie dla podobnych danych wejściowych:

val samples = List ("a", "aa", "b", "", "longer example", "This is a foolish, fishy test") 

samples.map (f) 

 List[Array[Byte]] = List(
Array (-41, -113, -79, 127, 29, 127, 31, 67, -19, 83, -73, -31, -101, -113, 97, -113), 
Array (-19, 7, -43, 89, -97, -113, 47, -53, -113, -127, -31, -113, -67, -23, 127, 127), 
Array (-41, -113, -79, 127, 29, 127, 31, 67, -19, 83, -73, -31, -101, -113, 97, -113), 
Array (37, -19, -7, 67, -83, 89, 59, -11, -23, -47, 97, 83, 19, 2, 2, 2), 
Array (79, 101, -47, -103, 47, -13, 29, -37, -83, -3, -37, 59, 127, 97, -43, -43), 
Array (37, 53, -43, -73, -67, 5, 11, -89, -37, -103, 107, 97, 37, -71, 59, 67))

Błąd polega na użyciu tylko liczb pierwszych do kodowania. Zamiast

scala> math.pow (256, 16)
res5: Double = 3.4028236692093846E38

wartości, kończymy na

scala> math.pow (54, 16)
res6: Double = 5.227573613485917E27

ponieważ jest 54 liczb pierwszych poniżej 256.

nieznany użytkownik
źródło
2
5.22e27 >> 2^16. Tak wiele możliwości nie ma sposobu na brutalną siłę.
Keith Randall
zapomniałeś nazwy języka
ajax333221
@ ajax333221: Scala. Dodałem go na górę.
użytkownik nieznany
@KeithRandall: Mógłbym „przypadkowo” użyć tylko pozytywnych bajtów, co zmniejszyłoby możliwości math.pow (27, 16), ale to wciąż około 8e22.
użytkownik nieznany