Underhanded Password Hashing

Question

In the spirit of the Underhanded C Contest, I'm starting an Underhanded Code Contest. The objective of this contest is to straightforwardly implement some code, while subtly hiding a nefarious bug inside it.

The contest

You are a secret Russian mole working in the IT department of an American spy agency. Your American boss has just asked you to implement a password hashing algorithm to use for encrypting secret messages.

Your boss wants you to implement the following function:

f: String -> byte[16]

which converts a password to a 16-byte quantity suitable for use as an AES key. Your boss wants a secure function, which in this context means that different password strings should generate different results with overwhelming probability. For instance, returning the md5 hash of the input would be a simple implementation of f.

Of course, your real boss in the Russian spy agency would want you to subvert this process. Your task is to implement f such that the Russians can decrypt all the secret messages encrypted using keys returned by f.

To do so, you must implement f so that it returns only a small subset of the 2^128 possible outputs. In particular, your f must return at most 2^16 different results so that the Russians can do an easy brute-force search for the correct key for each encrypted message they wish to decrypt.

Keep in mind, however, that espionage carries the death penalty. In order not to get caught, your function f must generate at least 2^8 different results, so that a cursory inspection of a few outputs of f is unlikely to reveal a duplicate. And most importantly, the code you introduce to limit the range of f must look unintentional, not deliberate. If you ever get hauled into a courtroom, there must be some reasonable doubt as to whether you introduced the bug deliberately or by accident.

Judging

I and two others I recruit will judge the entries (email me if you'd like to judge). I'm offering a 200 reputation bounty for the winning entry. Submissions must be uploaded by May 1.

Judging will take into account the following criteria:

• Does f adhere to the spec, i.e. does it generate between 2^8 and 2^16 possible outputs. Don't feel that these are hard limits, but we'll deduct points if you're too far out of range.
• Is the bug plausibly the result of an unintentional mistake?
• Do the outputs of f look random?
• The shorter your implementation of f, the better.
• The clearer your implementation of f, the better.

Notes

You may use any language to implement your code. You're trying to hide a bug in plain sight, so obfuscated code is not suggested.

You might want to take a look at some of the previous Underhanded C contest winners to get a feel for what makes a good submission.

Input strings will be printable ascii (32 through 126, inclusive). You may assume a reasonable max length if you want.

Answer 1

C

2^16 possible outputs (or 2^8 times the number of used characters).
Uses Linux's MD5 implementation, which is, AFAIK, fine. But this gives the same hash, for example, for "40" and "42".
EDIT: Renamed bcopy to memcpy (swapped parameters of course).
EDIT: Converted from program to function, to meet requirements better.

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

Answer 2

C

This may not be the flashiest contest entry, but I think the following is the kind of hash function that could have been made by any coder too clever for their own good, with a vague idea of the kind of operations you see in hash functions:

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

In fact the hash function can return no more than L*2048 different results, where L is the number of different input string lengths that can occur. In practice, I tested the code on 1.85 million unique input lines from manual pages and html documents on my laptop, and got only 85428 different unique hashes.

Answer 3

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

Test, if the result doesn't look similar for similar input:

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

The error is using just primes for the encoding. Instead of

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

values, we end with

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

since there are 54 primes below 256.