[Question]
  [
**Closed.** This question is [off-topic](/help/closed-questions). It is not currently accepting answers.
 
 
---
 This question does not appear to be about code golf or coding challenges within the scope defined in the [help center](https://codegolf.stackexchange.com/help/on-topic).
Closed 7 years ago.
[Improve this question](/posts/5334/edit) 
In the spirit of the [Underhanded C Contest](http://underhanded.xcott.com/?m=200912), 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](http://en.wikipedia.org/wiki/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](http://underhanded.xcott.com/?page_id=4) 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]
## 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]
# 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]
## 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.
]