Im Geiste des Underhanded-C-Wettbewerbs starte ich einen Underhanded-Code-Wettbewerb. Das Ziel dieses Wettbewerbs ist es, Code einfach zu implementieren und dabei einen schändlichen Fehler zu verbergen.

Der Wettbewerb

Sie sind ein geheimer russischer Maulwurf, der in der IT-Abteilung einer amerikanischen Spionageagentur arbeitet. Ihr amerikanischer Chef hat Sie gerade gebeten, einen Passwort-Hashing-Algorithmus für die Verschlüsselung geheimer Nachrichten zu implementieren.

Ihr Chef möchte, dass Sie die folgende Funktion implementieren:

f: String -> byte[16]

Das konvertiert ein Passwort in eine 16-Byte-Menge, die als AES-Schlüssel verwendet werden kann. Ihr Chef möchte eine sichere Funktion, was in diesem Zusammenhang bedeutet, dass unterschiedliche Kennwortzeichenfolgen mit überwältigender Wahrscheinlichkeit unterschiedliche Ergebnisse erzeugen sollten. Zum Beispiel wäre die Rückgabe des MD5- Hash der Eingabe eine einfache Implementierung von f.

Natürlich möchte Ihr echter Chef der russischen Spionageagentur, dass Sie diesen Prozess untergraben. Ihre Aufgabe ist es, fso zu implementieren , dass die Russen alle geheimen Nachrichten entschlüsseln können, die mit Schlüsseln verschlüsselt wurden, die von zurückgegeben wurden f.

Dazu müssen Sie implementieren f, dass nur eine kleine Teilmenge der 2 ^ 128 möglichen Ausgaben zurückgegeben wird. Insbesondere fmüssen Sie höchstens 2 ^ 16 unterschiedliche Ergebnisse zurückgeben, damit die Russen für jede verschlüsselte Nachricht, die sie entschlüsseln möchten, eine einfache Brute-Force-Suche nach dem richtigen Schlüssel durchführen können.

Denken Sie jedoch daran, dass Spionage mit der Todesstrafe verbunden ist. Um nicht erwischt zu werden, fmuss Ihre Funktion mindestens 2 ^ 8 verschiedene Ergebnisse generieren, sodass eine flüchtige Überprüfung einiger Ausgaben von fwahrscheinlich kein Duplikat ergibt . Und am wichtigsten ist, dass der Code, den Sie einführen, um den Bereich feinzuschränken, nicht absichtlich, sondern ungewollt aussieht. Wenn Sie jemals in einen Gerichtssaal gebracht werden, muss es begründete Zweifel geben, ob Sie den Fehler absichtlich oder versehentlich eingeschleppt haben.

Beurteilen

Ich und zwei andere, die ich rekrutiere, beurteilen die Einträge (senden Sie mir eine E-Mail, wenn Sie beurteilen möchten). Ich biete ein Reputationsguthaben von 200 für den siegreichen Beitrag. Einsendungen müssen bis zum 1. Mai hochgeladen sein.

Bei der Beurteilung werden folgende Kriterien berücksichtigt:

• Entspricht fder Spezifikation, erzeugt also zwischen 2 ^ 8 und 2 ^ 16 mögliche Ausgaben. Denken Sie nicht, dass dies harte Grenzen sind, aber wir ziehen Punkte ab, wenn Sie zu weit außerhalb der Reichweite sind.
• Ist der Fehler plausibel auf einen unbeabsichtigten Fehler zurückzuführen?
• Sehen die Ausgaben von fzufällig aus?
• Je kürzer Ihre Implementierung ist f, desto besser.
• Je klarer Ihre Implementierung f, desto besser.

Anmerkungen

Sie können eine beliebige Sprache verwenden, um Ihren Code zu implementieren. Sie versuchen, einen Fehler in der Öffentlichkeit zu verbergen, daher wird kein verschleierter Code empfohlen.

Vielleicht möchten Sie einen Blick auf einige der vorherigen Gewinner des Underhanded C-Wettbewerbs werfen , um ein Gefühl dafür zu bekommen, was eine gute Einreichung ausmacht.

Eingabezeichenfolgen können in ASCII-Form (32 bis einschließlich 126) gedruckt werden. Sie können eine angemessene maximale Länge annehmen, wenn Sie möchten.

C

2 ^ 16 mögliche Ausgaben (oder 2 ^ 8 mal die Anzahl der verwendeten Zeichen).
Verwendet die MD5-Implementierung von Linux (AFAIK). Dies ergibt jedoch den gleichen Hash, zum Beispiel für "40" und "42".
BEARBEITEN: Umbenannt bcopyin memcpy(natürlich vertauschte Parameter).
BEARBEITEN: Konvertiert von Programm zu Funktion, um die Anforderungen besser zu erfüllen.

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

C

Dies ist vielleicht nicht der auffälligste Wettbewerbsbeitrag, aber ich denke, das Folgende ist die Art von Hash-Funktion, die von jedem zu schlauen Programmierer für sich selbst hätte erstellt werden können, mit einer vagen Vorstellung der Art von Operationen, die Sie in Hash-Funktionen sehen:

#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");
     }
}

Tatsächlich kann die Hash-Funktion nicht mehr als L * 2048 verschiedene Ergebnisse zurückgeben, wobei L die Anzahl der möglichen unterschiedlichen Längen der Eingabezeichenfolgen ist. In der Praxis habe ich den Code an 1,85 Millionen eindeutigen Eingabezeilen aus Handbuchseiten und HTML-Dokumenten auf meinem Laptop getestet und nur 85428 verschiedene eindeutige Hashes erhalten.

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

Testen Sie, ob das Ergebnis bei ähnlichen Eingaben nicht ähnlich aussieht:

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))

Der Fehler besteht darin, nur Primzahlen für die Codierung zu verwenden. Anstatt

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

Werte, mit denen wir enden

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

da gibt es 54 Primzahlen unter 256.