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ść.

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;
}

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.

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.