Skip to main content

Appendix A. Example 20-Bit Hash Function

This appendix provides an example of a hash function that can be used to generate Flow Label values. This is not a mandatory algorithm; implementations are free to use any method that produces a suitable distribution of Flow Label values.

Purpose​

The purpose of this hash function is to generate Flow Label values that:

  1. Approximate a discrete uniform distribution
  2. Are difficult for third parties to predict
  3. Are consistent for packets belonging to the same flow
  4. Can be computed efficiently

Algorithm Description​

The hash function takes as input:

  • Source Address (128 bits)
  • Destination Address (128 bits)
  • Source Port (16 bits)
  • Destination Port (16 bits)
  • Protocol Number (8 bits)
  • A secret key unique to the source node (128 bits)

The output is a 20-bit Flow Label value.

Implementation Approach​

One possible implementation approach is:

  1. Concatenate Inputs: Concatenate all input values into a single bit string.

  2. Apply Cryptographic Hash: Apply a cryptographic hash function (e.g., MD5, SHA-1, or SHA-256) to the concatenated input.

  3. Extract 20 Bits: Extract 20 bits from the hash output to form the Flow Label value.

Example Using MD5​

Input:
  - Source Address: 128 bits
  - Destination Address: 128 bits
  - Source Port: 16 bits
  - Destination Port: 16 bits
  - Protocol: 8 bits
  - Secret Key: 128 bits

Process:
  1. Concatenate all inputs: 424 bits total
  2. Compute MD5 hash: 128-bit output
  3. Take the first 20 bits of the MD5 output as the Flow Label

Output:
  - Flow Label: 20 bits

Security Considerations​

The secret key is essential for preventing attackers from predicting Flow Label values. The secret key should:

  • Be at least 128 bits in length
  • Be generated using a cryptographically secure random number generator
  • Be unique per source node
  • Be kept secret and not transmitted over the network
  • Be changed periodically (e.g., once per day or week)

Performance Considerations​

Computing a cryptographic hash for every packet may be computationally expensive. Implementations may optimize performance by:

  1. Caching: Cache the Flow Label value for active flows and reuse it for subsequent packets in the same flow.

  2. Lightweight Hash: Use a lightweight hash function instead of a full cryptographic hash, as long as it provides sufficient unpredictability.

  3. Hardware Acceleration: Use hardware acceleration for hash computation where available.

Alternative Approaches​

Other approaches that may be used include:

  • Linear Congruential Generator (LCG): A simple pseudo-random number generator seeded with the flow 5-tuple and secret key.

  • SipHash: A fast, cryptographically strong hash function designed for hash table lookups.

  • AES-based PRF: Using AES in counter mode or CMAC mode as a pseudo-random function.

The choice of hash function depends on the specific requirements and constraints of the implementation. The key requirements are that the output should be unpredictable to attackers and should approximate a uniform distribution.

Example Code (Pseudocode)​

function compute_flow_label(src_addr, dst_addr, src_port, dst_port, protocol, secret_key):
    // Concatenate inputs
    input = concatenate(src_addr, dst_addr, src_port, dst_port, protocol, secret_key)
    
    // Compute hash
    hash_output = MD5(input)
    
    // Extract 20 bits
    flow_label = hash_output[0:20]  // First 20 bits
    
    // Ensure non-zero (optional, depending on requirements)
    if flow_label == 0:
        flow_label = 1
    
    return flow_label

Notes​

  • The Flow Label value of 0 has special meaning (unlabeled packets). Implementations may choose to avoid generating a Flow Label of 0, or they may allow it.

  • The hash function should be applied consistently for all packets in a flow to ensure that they all receive the same Flow Label value.

  • The secret key should be protected and not exposed to potential attackers.

Last updated on