秘密密码散列

Question

本着黑手C竞赛的精神，我开始了一场暗地里的代码竞赛。这场竞赛的目的是直接实现一些代码，同时巧妙地将一个邪恶的bug隐藏在其中。

，竞赛，

你是一名在美国间谍机构IT部门工作的秘密俄罗斯间谍。您的美国老板刚刚要求您实现一个密码哈希算法用于加密秘密信息。

您的老板希望您实现以下功能：

f: String -> byte[16]

它将密码转换为适合用作AES密钥的16字节数量。你的老板想要一个安全的函数，在这种情况下，这意味着不同的密码字符串应该以极大的概率产生不同的结果。例如，返回输入的md5哈希将是f的一个简单实现。

当然，你在俄罗斯间谍机构的真正老板会希望你颠覆这一过程。您的任务是实现f，以便俄国人能够解密使用f返回的密钥加密的所有秘密消息。

为此，您必须实现f，以便它只返回2^128可能的输出中的一小部分。特别是，您的f必须返回最多2^16不同的结果，这样俄国人就可以对他们希望解密的每一条加密信息进行简单的蛮力搜索。

然而，请记住，间谍活动将被判处死刑。为了不被捕捉到，函数f必须生成至少2^8不同的结果，这样粗略地检查几个f的输出就不太可能发现重复的结果。最重要的是，您引入的限制f范围的代码必须看起来是无意的，而不是故意的。如果你被拖进法庭，你是否故意或偶然地引入了窃听器，肯定会有一些合理的怀疑。

判断

我和另外两个我招募的人将对参赛作品进行评判(如果你愿意的话，请给我发邮件)。我为获奖作品提供200个名誉赏金。意见书必须在五月一日前上载。

评审将考虑到以下标准：

• f是否遵守规范，即它是否生成2^8和2^16之间的可能输出。不要觉得这些都是很难的限制，但是如果你太远的话，我们会扣分。
• 这个错误是否有可能是无意中的错误造成的？
• f的输出看起来是随机的吗？
• f的实现时间越短，效果越好。
• f的实现越清晰，效果越好。

Notes

您可以使用任何语言来实现代码。您正试图将一个bug隐藏在显而易见的范围内，因此不建议使用模糊代码。

您可能需要查看一下以前的一些黑手C竞赛获奖者，以了解什么是好的提交。

输入字符串将是可打印的ascii (32到126，包括在内)。如果你愿意的话，你可以假定一个合理的最大长度。

Answer 1

C

2^16可能的输出(或使用字符数的2^8倍)。

使用Linux的MD5实现，也就是AFAIK，很好。但这给出了相同的散列，例如，对于"40“和"42”。

编辑:将bcopy重命名为memcpy (当然是交换参数)。

编辑:从程序转换到功能，以更好地满足需求。

#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

这可能不是最华丽的竞赛条目，但我认为以下是任何一个编码器都可能做得太聪明的哈希函数，对您在散列函数中看到的操作有一个模糊的概念：

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

事实上，散列函数返回的结果不超过L*2048不同的结果，L是不同输入字符串长度可以发生的数目。在实践中，我在笔记本电脑上从手工页面和html文档中测试了185万行唯一输入行的代码，只有85428种不同的散列。

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

测试，如果结果与类似的输入不一样：

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

错误是只使用素数进行编码。而不是

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

价值，我们以

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

因为在256下面有54个素数。