| 검색 | ?

ToeplitzHash (토플리츠 해시)



1.1. 개요

토플리츠 해시(Toeplitz Hash)는 키(key)와 토플리츠 행렬(Toeplitz matrix)의 행렬 곱셈을 통해 해시 값을 계산하는 해시(Hash) 함수 알고리즘입니다

입력 데이터와 비밀 키(Secret Key)로 구성된 토플리츠 행렬(Toeplitz matrix) 간의 연산을 통해 고정된 길이의 해시 값을 생성하여 hash충돌 확률이 낮은 특성을 가지고 있어 네트워킹 분야에서는 주로 RSS(Receive Side Scaling) 분산에 많이 사용하고 있습니다.

RSS(Receive Side Scaling) 분산에 토플리츠 해시(Toeplitz Hash)를 사용할 때 주요 고려 사항은 정방향과 역방향 tuple을 동일한 hash 계산 값이 나오게 맞출지 여부에 따라서 Asymmetric Key vs Symmetric Key 중 어떤 Key를 사용할지 결정하는 것과 Tuple 을 어떤 방식으로 구성하여 입력 데이터로 사용할지 결정해야 합니다.

간단히 요약하면 hash 값은 입력(input)에 대한 행렬과 키(Secret Key)에 해당하는 행렬의 비트열([http]Modulo-2[])의 곱을 계산하는 구현이라고 할 수 있습니다.

1.2. Pseudo code

대략 다음과 같은 형태의 구현이 플리츠 해시(Toeplitz Hash) 구현입니다. 
K[Secret Key 320bits (40Bytes) (For Asymmetric)] = {
      0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
      0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
      0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
      0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
      0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa
}

result = 0
For each bit b in input[] from left to right
{
    if (b == 1) result ^= (left-most 32 bits of K)
    shift K left 1 bit position
}

return result
입력(input) 또는 Key(K)의 byte/bit 열이 input[0], input[1], input[2], ..., input[n-1] 또는 K[0], K[1], K[2], ..., K[n-1] 과 같을 때 left는 lest-most byte/bit를 의미하는 input[0] 또는 K[0]의 MSB(Most-Significant Bit, 부호를 다루는 최상위 비트 쪽) 가 됩니다.

이를 C언어로 구현한다면 다음과 같은 구현입니다. 
static const uint8_t g_toeplitz_hash_asymmetric_key[] = { /* 320bits (40Bytes) */
        0x6d, 0x5a, 0x56, 0xda, 0x25, 0x5b, 0x0e, 0xc2,
        0x41, 0x67, 0x25, 0x3d, 0x43, 0xa3, 0x8f, 0xb0,
        0xd0, 0xca, 0x2b, 0xcb, 0xae, 0x7b, 0x30, 0xb4,
        0x77, 0xcb, 0x2d, 0xa3, 0x80, 0x30, 0xf2, 0x0c,
        0x6a, 0x42, 0xb7, 0x3b, 0xbe, 0xac, 0x01, 0xfa
};
static const uint8_t g_toeplitz_hash_symmetric_key[] = { /* 320bits (40Bytes) */
        0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a,
        0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a,
        0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a,
        0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a,
        0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a, 0x6d, 0x5a
}

uint32_t toeplitz_hash(const void *s_key_ptr, size_t s_key_size, const void *s_data_ptr, size_t s_size)
{
        const uint8_t *s_key8 = (const uint8_t *)s_key_ptr;
        const uint8_t *s_data8 = (const uint8_t *)s_data_ptr;

        /* initial hash */
        uint32_t s_hash32 = (uint32_t)0u;

        /* initial (left-most 32 bits of K) */
        uint32_t s_key32 = (((uint32_t)s_key8[0]) << 24) | (((uint32_t)s_key8[1]) << 16) | (((uint32_t)s_key8[2]) << 8) | ((uint32_t)s_key8[3]);

        unsigned int s_byte_offset, s_bit_offset;

        for(s_byte_offset = 0u;s_byte_offset < ((unsigned int)s_size);s_byte_offset++) {
                for(s_bit_offset = 0u;s_bit_offset < 8u;s_bit_offset++) {
                        /* if (b == 1) result ^= (left-most 32 bits of K) */
                        if(s_data8[s_byte_offset] & (1u << (7u - s_bit_offset))) {
                                s_hash32 ^= s_key32;
                        }

                        /* shift K left 1 bit position */
                        s_key32 <<= 1u;
                        if(((s_byte_offset + 4u) < ((unsigned int)s_key_size)) && (s_key8[s_byte_offset + 4u] & (1u << (7u - s_bit_offset)))) {
                                s_key32 |= (uint32_t)1u;
                        }
                }
        }

        return(s_hash32);
}

1.3. RSS(Receive Side Scaling) 분산에 사용하는 Tuple 구성(입력 데이터) 예시

토플리츠 해시(Toeplitz Hash)를 사용하여 RSS(Receive Side Scaling) 분산 값을 계산할 때 입력되는 데이터를 2tuple, 4tuple, 5tuple 로 사용합니다. L3(IPv4/IPv6)가 확보되는 경우 기본적으로 2tuple을 사용하고 L4(TCP/UDP/SCTP/...) 등 port 값 또는 그에 대응하는 값이 확보되는 경우 4tuple을 사용하게 되며 경우에 따라서 Outer header를 식별 가능한 경우 5tuple을 사용하기도 합니다. 정해져 있는 규칙이 있는 것은 아니고 tuple을 어떻게 입력 데이터로 사용하는지에 따라서 계산 결과에 특성이 달라질 수 있습니다.

비밀 키(Secret Key)는 원하는 분산 방법에 따라서 임의의 값을 사용할 수 있으며 Asymmetric Key와 Symmetric Key가 사용 목적에 따라 구분될 수 있습니다.

Tuple의 정방향/역방향에 대한 동일한 계산 값이 나오도록 하는 것을 Symmetric 방식이라고 하며 그렇지 않은 경우를 Asymmetric 방식이라고 합니다.

또한 추가적인 고른 분산을 통제하는 방법으로 RSS RETA (RSS Redirection Table) 을 통해서 계산된 결과 값의 하위 특정 bits 를 table index로 하여 맵핑하는 방법도 추가적으로 사용하기도 합니다.

  • Toeplitz Original Tuple (For Asymmetric)
    • 2tuple : SourceAddress, DestinationAddress
    • 4tuple : SourceAddress, DestinationAddress, SourcePort, DestinationPort
    • 5tuple : SourceAddress, DestinationAddress, SourcePort, DestinationPort, Protocol
  • Toeplitz XOR Tuple (For Symmetric)
    • 2tuple : (SourceAddress ^ DestinationAddress), (SourceAddress ^ DestinationAddress)
    • 4tuple : (SourceAddress ^ DestinationAddress), (SourceAddress ^ DestinationAddress), (SourcePort ^ DestinationPort), (SourcePort ^ DestinationPort)
    • 5tuple : (SourceAddress ^ DestinationAddress), (SourceAddress ^ DestinationAddress), (SourcePort ^ DestinationPort), (SourcePort ^ DestinationPort), Protocol
  • Toeplitz OR-XOR Tuple (For Symmetric)
    • 2tuple : (SourceAddress | DestinationAddress), (SourceAddress ^ DestinationAddress)
    • 4tuple : (SourceAddress | DestinationAddress), (SourceAddress ^ DestinationAddress), (SourcePort | DestinationPort), (SourcePort ^ DestinationPort)
    • 5tuple : (SourceAddress | DestinationAddress), (SourceAddress ^ DestinationAddress), (SourcePort | DestinationPort), (SourcePort ^ DestinationPort), Protocol

1.4. 예제 소스

전체 toeplitz hash 에 대한 예제 구현은 다음의 링크를 통해서 받아보실 수 있습니다.
  • [https]https://www.minzkn.com/public/release/rss_hash/rss_hash_20251124-0.tar.gz[]
    • 예제 소스 실행 결과 
            [<운영방식>] <입력 tuple 수> : <계산 값> [/ <Test-Vector 값> (<검증 유효>)] & invert : <역방향 tuple 계산 값> (<정방향/역방향 계산 값의 동일 유무>)
* Toeplitz test vectors...
  - IPv4/udp(17) [66.9.149.187]:2794 to [161.142.100.80]:1766
      [Asymmetric] 2tuple : 0x323e8fc2 / 0x323e8fc2 (PASSED) & invert : 0xba45587e (Asymmetric)
      [ Symmetric] 2tuple : 0x0a590a59 & invert : 0x0a590a59 (Symmetric)
      [       XOR] 2tuple : 0x887bd7bc & invert : 0x887bd7bc (Symmetric)
      [    OR_XOR] 2tuple : 0x277806fe & invert : 0x277806fe (Symmetric)
      [Asymmetric] 4tuple : 0x51ccc178 / 0x51ccc178 (PASSED) & invert : 0xfde799b2 (Asymmetric)
      [ Symmetric] 4tuple : 0x9fcc9fcc & invert : 0x9fcc9fcc (Symmetric)
      [       XOR] 4tuple : 0xac2b58ca & invert : 0xac2b58ca (Symmetric)
      [    OR_XOR] 4tuple : 0xa65524fa & invert : 0xa65524fa (Symmetric)
      [Asymmetric] 5tuple : 0x9d176496 / 0x9d176496 (PASSED) & invert : 0x313c3c5c (Asymmetric)
      [ Symmetric] 5tuple : 0x58295829 & invert : 0x58295829 (Symmetric)
      [       XOR] 5tuple : 0x60f0fd24 & invert : 0x60f0fd24 (Symmetric)
      [    OR_XOR] 5tuple : 0x6a8e8114 & invert : 0x6a8e8114 (Symmetric)
  - IPv4/udp(17) [199.92.111.2]:14230 to [65.69.140.83]:4739
      [Asymmetric] 2tuple : 0xd718262a / 0xd718262a (PASSED) & invert : 0x6fbcad07 (Asymmetric)
      [ Symmetric] 2tuple : 0x7ba97ba9 & invert : 0x7ba97ba9 (Symmetric)
      [       XOR] 2tuple : 0xb8a48b2d & invert : 0xb8a48b2d (Symmetric)
      [    OR_XOR] 2tuple : 0x0efd860b & invert : 0x0efd860b (Symmetric)
      [Asymmetric] 4tuple : 0xc626b0ea / 0xc626b0ea (PASSED) & invert : 0xe53c74e8 (Asymmetric)
      [ Symmetric] 4tuple : 0x60d760d7 & invert : 0x60d760d7 (Symmetric)
      [       XOR] 4tuple : 0x231ac402 & invert : 0x231ac402 (Symmetric)
      [    OR_XOR] 4tuple : 0x69d9c235 & invert : 0x69d9c235 (Symmetric)
      [Asymmetric] 5tuple : 0x0afd1504 / 0x0afd1504 (PASSED) & invert : 0x29e7d106 (Asymmetric)
      [ Symmetric] 5tuple : 0xa732a732 & invert : 0xa732a732 (Symmetric)
      [       XOR] 5tuple : 0xefc161ec & invert : 0xefc161ec (Symmetric)
      [    OR_XOR] 5tuple : 0xa50267db & invert : 0xa50267db (Symmetric)
  - IPv4/udp(17) [24.19.198.95]:12898 to [12.22.207.184]:38024
      [Asymmetric] 2tuple : 0xd2d0a5de / 0xd2d0a5de (PASSED) & invert : 0xf6e02bf3 (Asymmetric)
      [ Symmetric] 2tuple : 0xa55aa55a & invert : 0xa55aa55a (Symmetric)
      [       XOR] 2tuple : 0x24308e2d & invert : 0x24308e2d (Symmetric)
      [    OR_XOR] 2tuple : 0x53494126 & invert : 0x53494126 (Symmetric)
      [Asymmetric] 4tuple : 0x5c2b394a / 0x5c2b394a (PASSED) & invert : 0xa802b849 (Asymmetric)
      [ Symmetric] 4tuple : 0x3a3e3a3e & invert : 0x3a3e3a3e (Symmetric)
      [       XOR] 4tuple : 0xf4298103 & invert : 0xf4298103 (Symmetric)
      [    OR_XOR] 4tuple : 0x886967e2 & invert : 0x886967e2 (Symmetric)
      [Asymmetric] 5tuple : 0x90f09ca4 / 0x90f09ca4 (PASSED) & invert : 0x64d91da7 (Asymmetric)
      [ Symmetric] 5tuple : 0xfddbfddb & invert : 0xfddbfddb (Symmetric)
      [       XOR] 5tuple : 0x38f224ed & invert : 0x38f224ed (Symmetric)
      [    OR_XOR] 5tuple : 0x44b2c20c & invert : 0x44b2c20c (Symmetric)
  - IPv4/udp(17) [38.27.205.30]:48228 to [209.142.163.6]:2217
      [Asymmetric] 2tuple : 0x82989176 / 0x82989176 (PASSED) & invert : 0xa7728522 (Asymmetric)
      [ Symmetric] 2tuple : 0xf8a7f8a7 & invert : 0xf8a7f8a7 (Symmetric)
      [       XOR] 2tuple : 0x25ea1454 & invert : 0x25ea1454 (Symmetric)
      [    OR_XOR] 2tuple : 0xe30415e3 & invert : 0xe30415e3 (Symmetric)
      [Asymmetric] 4tuple : 0xafc7327f / 0xafc7327f (PASSED) & invert : 0xe1dfcdff (Asymmetric)
      [ Symmetric] 4tuple : 0xd26ed26e & invert : 0xd26ed26e (Symmetric)
      [       XOR] 4tuple : 0x4e18ff80 & invert : 0x4e18ff80 (Symmetric)
      [    OR_XOR] 4tuple : 0x021058ed & invert : 0x021058ed (Symmetric)
      [Asymmetric] 5tuple : 0x631c9791 / 0x631c9791 (PASSED) & invert : 0x2d046811 (Asymmetric)
      [ Symmetric] 5tuple : 0x158b158b & invert : 0x158b158b (Symmetric)
      [       XOR] 5tuple : 0x82c35a6e & invert : 0x82c35a6e (Symmetric)
      [    OR_XOR] 5tuple : 0xcecbfd03 & invert : 0xcecbfd03 (Symmetric)
  - IPv4/udp(17) [153.39.163.191]:44251 to [202.188.127.2]:1303
      [Asymmetric] 2tuple : 0x5d1809c5 / 0x5d1809c5 (PASSED) & invert : 0xc197330c (Asymmetric)
      [ Symmetric] 2tuple : 0x57545754 & invert : 0x57545754 (Symmetric)
      [       XOR] 2tuple : 0x9c8f3ac9 & invert : 0x9c8f3ac9 (Symmetric)
      [    OR_XOR] 2tuple : 0x0e558017 & invert : 0x0e558017 (Symmetric)
      [Asymmetric] 4tuple : 0x10e828a2 / 0x10e828a2 (PASSED) & invert : 0x15d05e13 (Asymmetric)
      [ Symmetric] 4tuple : 0xf23ef23e & invert : 0xf23ef23e (Symmetric)
      [       XOR] 4tuple : 0x053876b1 & invert : 0x053876b1 (Symmetric)
      [    OR_XOR] 4tuple : 0xd9fe70e3 & invert : 0xd9fe70e3 (Symmetric)
      [Asymmetric] 5tuple : 0xdc338d4c / 0xdc338d4c (PASSED) & invert : 0xd90bfbfd (Asymmetric)
      [ Symmetric] 5tuple : 0x35db35db & invert : 0x35db35db (Symmetric)
      [       XOR] 5tuple : 0xc9e3d35f & invert : 0xc9e3d35f (Symmetric)
      [    OR_XOR] 5tuple : 0x1525d50d & invert : 0x1525d50d (Symmetric)
  - IPv6/udp(17) [3ffe:2501:200:1fff::7]:2794 to [3ffe:2501:200:3::1]:1766
      [Asymmetric] 2tuple : 0x2cc18cd5 / 0x2cc18cd5 (PASSED) & invert : 0xbf3b2ab5 (Asymmetric)
      [ Symmetric] 2tuple : 0x867e867e & invert : 0x867e867e (Symmetric)
      [       XOR] 2tuple : 0x93faa660 & invert : 0x93faa660 (Symmetric)
      [    OR_XOR] 2tuple : 0x97d97493 & invert : 0x97d97493 (Symmetric)
      [Asymmetric] 4tuple : 0x40207d3d / 0x40207d3d (PASSED) & invert : 0x1ac0fcce (Asymmetric)
      [ Symmetric] 4tuple : 0x13eb13eb & invert : 0x13eb13eb (Symmetric)
      [       XOR] 4tuple : 0x5ae081f3 & invert : 0x5ae081f3 (Symmetric)
      [    OR_XOR] 4tuple : 0xaea5d07d & invert : 0xaea5d07d (Symmetric)
      [Asymmetric] 5tuple : 0xe3408fed / 0xe3408fed (PASSED) & invert : 0xb9a00e1e (Asymmetric)
      [ Symmetric] 5tuple : 0xd40ed43b & invert : 0xd40ed43b (Symmetric)
      [       XOR] 5tuple : 0xf9807323 & invert : 0xf9807323 (Symmetric)
      [    OR_XOR] 5tuple : 0x0dc522ad & invert : 0x0dc522ad (Symmetric)
  - IPv6/udp(17) [3ffe:501:8::260:97ff:fe40:efab]:14230 to [ff02::1]:4739
      [Asymmetric] 2tuple : 0x0f0c461c / 0x0f0c461c (PASSED) & invert : 0x39eafaa7 (Asymmetric)
      [ Symmetric] 2tuple : 0x2def2def & invert : 0x2def2def (Symmetric)
      [       XOR] 2tuple : 0x36e6bcbb & invert : 0x36e6bcbb (Symmetric)
      [    OR_XOR] 2tuple : 0x91dfa0cc & invert : 0x91dfa0cc (Symmetric)
      [Asymmetric] 4tuple : 0xdde51bbf / 0xdde51bbf (PASSED) & invert : 0xe0f7edc9 (Asymmetric)
      [ Symmetric] 4tuple : 0x36913691 & invert : 0x36913691 (Symmetric)
      [       XOR] 4tuple : 0x3d12f676 & invert : 0x3d12f676 (Symmetric)
      [    OR_XOR] 4tuple : 0xb7ea4926 & invert : 0xb7ea4926 (Symmetric)
      [Asymmetric] 5tuple : 0x7e85e96f / 0x7e85e96f (PASSED) & invert : 0x43971f19 (Asymmetric)
      [ Symmetric] 5tuple : 0xf174f141 & invert : 0xf174f141 (Symmetric)
      [       XOR] 5tuple : 0x9e7204a6 & invert : 0x9e7204a6 (Symmetric)
      [    OR_XOR] 5tuple : 0x148abbf6 & invert : 0x148abbf6 (Symmetric)
  - IPv6/udp(17) [3ffe:1900:4545:3:200:f8ff:fe21:67cf]:44251 to [fe80::200:f8ff:fe21:67cf]:38024
      [Asymmetric] 2tuple : 0x4b61e985 / 0x4b61e985 (PASSED) & invert : 0x2d4381a5 (Asymmetric)
      [ Symmetric] 2tuple : 0xc85ec85e & invert : 0xc85ec85e (Symmetric)
      [       XOR] 2tuple : 0x66226820 & invert : 0x66226820 (Symmetric)
      [    OR_XOR] 2tuple : 0x87bdf57e & invert : 0x87bdf57e (Symmetric)
      [Asymmetric] 4tuple : 0x02d1feef / 0x02d1feef (PASSED) & invert : 0xd1bec7ad (Asymmetric)
      [ Symmetric] 4tuple : 0x08090809 & invert : 0x08090809 (Symmetric)
      [       XOR] 4tuple : 0xd36f3942 & invert : 0xd36f3942 (Symmetric)
      [    OR_XOR] 4tuple : 0x79207404 & invert : 0x79207404 (Symmetric)
      [Asymmetric] 5tuple : 0xa1b10c3f / 0xa1b10c3f (PASSED) & invert : 0x72de357d (Asymmetric)
      [ Symmetric] 5tuple : 0xcfeccfd9 & invert : 0xcfeccfd9 (Symmetric)
      [       XOR] 5tuple : 0x700fcb92 & invert : 0x700fcb92 (Symmetric)
      [    OR_XOR] 5tuple : 0xda4086d4 & invert : 0xda4086d4 (Symmetric)

1.5. 참고자료

  • [https]RSS 해시 계산 확인 - Microsoft[]
    • Toeplitz Original Tuple Vectors table 
            Destination                      Source                                      2tuple     4tuple     5tuple
      161.142.100.80:1766              66.9.149.187:2794                           0x323e8fc2 0x51ccc178 0x9d176496
      65.69.140.83:4739                199.92.111.2:14230                          0xd718262a 0xc626b0ea 0x0afd1504
      12.22.207.184:38024              24.19.198.95:12898                          0xd2d0a5de 0x5c2b394a 0x90f09ca4
      209.142.163.6:2217               38.27.205.30:48228                          0x82989176 0xafc7327f 0x631c9791
      202.188.127.2:1303               153.39.163.191:44251                        0x5d1809c5 0x10e828a2 0xdc338d4c
      [3ffe:2501:200:3::1]:1766        [3ffe:2501:200:1fff::7]:2794                0x2cc18cd5 0x40207d3d 0xe3408fed
      [ff02::1]:4739                   [3ffe:501:8::260:97ff:fe40:efab]:14230      0x0f0c461c 0xdde51bbf 0x7e85e96f
      [fe80::200:f8ff:fe21:67cf]:38024 [3ffe:1900:4545:3:200:f8ff:fe21:67cf]:44251 0x4b61e985 0x02d1feef 0xa1b10c3f
  • [https]RSS 해시 함수 - Microsoft[] 
    result = 0
For each bit b in input[] from left to right
{
    if (b == 1) result ^= (left-most 32 bits of K)
    shift K left 1 bit position
}

return result

Copyright ⓒ MINZKN.COM
All Rights Reserved.