6

MurmurHash3のC＃実装をVB.Netに移植しようとしています。

実行されます...しかし、誰かが私にいくつかの既知のテストベクトルを提供して、正確さを検証できますか？

  • 既知の文字列テキスト
  • シード値
  • MurmurHash3の結果

前もって感謝します。

編集：実装を32ビットのMurmurHash3のみに制限していますが、64ビットの実装用のベクトルも提供できる場合はそれも良いでしょう。

4

3 に答える 3

16

私はついにMurMur3実装の作成に取り掛かり、SMHasherテストコードを変換することができました。私の実装では、SMHasherテストと同じ結果が得られます。つまり、私は最終的にいくつかの有用な、そして正しいと仮定されたテストベクトルを与えることができるということです。

これはMurmur3_x86_32専用です

| Input        | Seed       | Expected   |
|--------------|------------|------------|
| (no bytes)   | 0          | 0          | with zero data and zero seed, everything becomes zero
| (no bytes)   | 1          | 0x514E28B7 | ignores nearly all the math
| (no bytes)   | 0xffffffff | 0x81F16F39 | make sure your seed uses unsigned 32-bit math
| FF FF FF FF  | 0          | 0x76293B50 | make sure 4-byte chunks use unsigned math
| 21 43 65 87  | 0          | 0xF55B516B | Endian order. UInt32 should end up as 0x87654321
| 21 43 65 87  | 0x5082EDEE | 0x2362F9DE | Special seed value eliminates initial key with xor
| 21 43 65     | 0          | 0x7E4A8634 | Only three bytes. Should end up as 0x654321
| 21 43        | 0          | 0xA0F7B07A | Only two bytes. Should end up as 0x4321
| 21           | 0          | 0x72661CF4 | Only one byte. Should end up as 0x21
| 00 00 00 00  | 0          | 0x2362F9DE | Make sure compiler doesn't see zero and convert to null
| 00 00 00     | 0          | 0x85F0B427 | 
| 00 00        | 0          | 0x30F4C306 |
| 00           | 0          | 0x514E28B7 |

実際の配列を持たない言語に移植する人のために、文字列ベースのテストもいくつかあります。これらのテストの場合：

  • すべての文字列はUTF-8でエンコードされていると見なされます
  • ヌルターミネータを含めないでください

これらはコード形式のままにしておきます。

TestString("", 0, 0); //empty string with zero seed should give zero
TestString("", 1, 0x514E28B7);
TestString("", 0xffffffff, 0x81F16F39); //make sure seed value is handled unsigned
TestString("\0\0\0\0", 0, 0x2362F9DE); //make sure we handle embedded nulls


TestString("aaaa", 0x9747b28c, 0x5A97808A); //one full chunk
TestString("aaa", 0x9747b28c, 0x283E0130); //three characters
TestString("aa", 0x9747b28c, 0x5D211726); //two characters
TestString("a", 0x9747b28c, 0x7FA09EA6); //one character

//Endian order within the chunks
TestString("abcd", 0x9747b28c, 0xF0478627); //one full chunk
TestString("abc", 0x9747b28c, 0xC84A62DD);
TestString("ab", 0x9747b28c, 0x74875592);
TestString("a", 0x9747b28c, 0x7FA09EA6);

TestString("Hello, world!", 0x9747b28c, 0x24884CBA);

//Make sure you handle UTF-8 high characters. A bcrypt implementation messed this up
TestString("ππππππππ", 0x9747b28c, 0xD58063C1); //U+03C0: Greek Small Letter Pi

//String of 256 characters.
//Make sure you don't store string lengths in a char, and overflow at 255 bytes (as OpenBSD's canonical BCrypt implementation did)
TestString(StringOfChar("a", 256), 0x9747b28c, 0x37405BDC);

Murmur3に変換した11個のSHA-2テストベクトルのうち2つだけを投稿します。

TestString("abc", 0, 0xB3DD93FA);
TestString("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 0, 0xEE925B90);

そして最後に、大きなもの：

  • 鍵： "The quick brown fox jumps over the lazy dog"
  • シード： 0x9747b28c
  • ハッシュ：0x2FA826CD

他の誰かがそれらの実装からこれらのベクトルのいずれか/すべてを確認できる場合。

また、これらのテストベクトルは、からのSMHasher256反復ループテストに合格する実装に由来しKeySetTest.cpp - VerificationTest(...)ます。

これらのテストは、Delphiでの私の実装から来ました。また、Luaで実装を作成しました（これは、配列のサポートではそれほど大きくありません）。

注：パブリックドメインにリリースされたコード。アトリビューションは必要ありません。

于 2015-08-10T21:31:00.083 に答える
6

SMHasherは、ハッシュが機能していることを確認するために小さなルーチンを使用します。基本的には、それぞれのシード値を（256から）減少させて、次の値のハッシュを計算します。

' The comment in the SMHasher code is a little wrong -
' it's missing the first case.
{}, {0}, {0, 1}, {0, 1, 2} ... {0, 1, 2, ... 254}

HASHLENGTH * 256そして、それを長さ配列に追加します。つまり、次のようになります。

' Where & is a byte array concatenation.
HashOf({}, 256) &
HashOf({0}, 255) &
HashOf({0, 1}, 254) &
...
HashOf({0, 1, ... 254), 1)

次に、その大きな配列のハッシュを取得します。最終ハッシュの最初の4バイトは、符号なし32ビット整数として解釈され、検証コードと照合されます。

  • MurmurHash3 x86 32 0xB0F57EE3
  • MurmurHash3 x86 128 0xB3ECE62A
  • MurmurHash3 x64 128 0x6384BA69

残念ながら、それは私が見つけた唯一の公開テストです。他のオプションは、簡単なCアプリを作成し、いくつかの値をハッシュすることだと思います。

これがベリファイアのC＃実装です。

static void VerificationTest(uint expected)
{
    using (var hash = new Murmur3())
    // Also test that Merkle incremental hashing works.
    using (var cs = new CryptoStream(Stream.Null, hash, CryptoStreamMode.Write))
    {
        var key = new byte[256];

        for (var i = 0; i < 256; i++)
        {
            key[i] = (byte)i;
            using (var m = new Murmur3(256 - i))
            {
                var computed = m.ComputeHash(key, 0, i);
                // Also check that your implementation deals with incomplete
                // blocks.
                cs.Write(computed, 0, 5);
                cs.Write(computed, 5, computed.Length - 5);
            }
        }

        cs.FlushFinalBlock();
        var final = hash.Hash;
        var verification = ((uint)final[0]) | ((uint)final[1] << 8) | ((uint)final[2] << 16) | ((uint)final[3] << 24);
        if (verification == expected)
            Console.WriteLine("Verification passed.");
        else
            Console.WriteLine("Verification failed, got {0:x8}, expected {1:x8}", verification, expected);
    }
}
于 2013-05-28T15:39:56.577 に答える
0

Jonathanの救命コードを改善しました。ICryptoTransformこのメソッドが機能するには、Murmur3を実装する必要があります。 このインターフェースを実装しているのはgithubにあります。

public static  void VerificationTest(uint expected)
{
    using (var hash = new Murmur32ManagedX86())
    {
        using (var cs = new CryptoStream(Stream.Null, hash, CryptoStreamMode.Write))
        {
            var key = new byte[256];

            for (var i = 0; i < 256; i++)
            {
                key[i] = (byte)i;
                using (var mur = new Murmur32ManagedX86((uint)(256 - i)))
                {
                    var computed = mur.ComputeHash(key, 0,i);
                    cs.Write(computed, 0, 4);
                }
            }
            cs.FlushFinalBlock();
            var testBoy = hash.Seed;

            var final = hash.Hash;
            var verification = ((uint)final[0]) | ((uint)final[1] << 8) | ((uint)final[2] << 16) | ((uint)final[3] << 24);
            if (verification == expected)
                Console.WriteLine("Verification passed.");
            else
                Console.WriteLine("Verification failed, got {0:x8}, expected {1:x8}", verification, expected);
        }
    }
}

インターフェイスを持たずICryptoTransform、バイトを処理して返すだけの実装を使用する場合int（簡単に変更して動作するようにすることもできbyte[]ます）。そのためのテスト関数は次のとおりです。

public static void VerificationTest(uint expected)
{
    using (var stream = new MemoryStream())
    {
        var key = new byte[256];

        for (var i = 0; i < 256; i++)
        {
            key[i] = (byte)i;
            var hasher = new MurMurHash3((uint)(256 - i));

            int computed = hasher.ComputeBytesFast(key.Take(i).ToArray());
            stream.Write(BitConverter.GetBytes(computed), 0, 4);
        }
        var finalHasher = new MurMurHash3(0); //initial seed = 0
        int result = finalHasher.ComputeBytesFast2(stream.GetBuffer());
        if (result == (int)expected)
            Console.WriteLine("Verification passed.");
        else
            Console.WriteLine("Verification failed, got {0:x8}, expected {1:x8}", verification, expected);
    }
}
于 2016-03-18T23:04:46.240 に答える