33
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by cat, Martin Ender Apr 18 '16 at 14:49

  • This question does not appear to be about programming puzzles or code golf within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ is there any limitations on input string? like it's only consist of alphabet? \$\endgroup\$ – Ali1S232 Mar 29 '12 at 15:49
  • \$\begingroup\$ @Gajet: you must handle all of the printable ascii characters (32 through 126, inclusive). \$\endgroup\$ – Keith Randall Mar 29 '12 at 18:42
  • \$\begingroup\$ Is the output range all 16-byte strings, or just printable ones? \$\endgroup\$ – boothby Mar 29 '12 at 20:01
  • \$\begingroup\$ @boothby: all possible 16-byte values (2^128 possibilities) \$\endgroup\$ – Keith Randall Mar 29 '12 at 20:10
  • 1
    \$\begingroup\$ I'm voting to close this question as off-topic because underhanded challenges are no longer on-topic on this site. meta.codegolf.stackexchange.com/a/8326/20469 \$\endgroup\$ – cat Apr 18 '16 at 12:41
15
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ is this a flaw with MD5? \$\endgroup\$ – Ali1S232 Apr 1 '12 at 11:56
  • \$\begingroup\$ @Gajet, No, I used Linux's MD5, which is perfectly OK (AFAIK). \$\endgroup\$ – ugoren Apr 1 '12 at 11:58
  • \$\begingroup\$ they why it doesn't generate more possible output? \$\endgroup\$ – Ali1S232 Apr 1 '12 at 12:01
  • 1
    \$\begingroup\$ @Gajet: Consider what happens in the bcopy step... it is a nice bit of misdirection, since the actual BSD bcopy function would work properly here. \$\endgroup\$ – han Apr 1 '12 at 14:34
  • \$\begingroup\$ @han, Actually, I now see that my bcopy is buggy. I'll change it to memcpy, and then the same implementation will become valid. \$\endgroup\$ – ugoren Apr 1 '12 at 14:41
13
+200
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 5.22e27 >> 2^16. There's no way to brute force that many possibilities. \$\endgroup\$ – Keith Randall Apr 4 '12 at 19:40
  • \$\begingroup\$ you forgot the name of the language \$\endgroup\$ – ajax333221 Apr 5 '12 at 1:57
  • \$\begingroup\$ @ajax333221: Scala. I added it to the top. \$\endgroup\$ – user unknown Apr 5 '12 at 3:23
  • \$\begingroup\$ @KeithRandall: I could 'accidentally' only use positive Bytes, which would reduce the possibilities to math.pow (27, 16), but that is still about 8e22. \$\endgroup\$ – user unknown Apr 5 '12 at 3:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.