Consider fuzzy matching of SNI domain names ?

[Shonke]

.example.me can represent all subdomains, such as abc.example.me . Just like this:

[protocols."tls_2"]
protocol = "tls"
target = ["192.168.122.5:443"]
load_balance = "source_ip"

server_names = ["example.com", "example.org", ".example.me"]

[Shonke]

Of course, ECH is an exception and all situations must be listed

[junkurihara]

Hi! @Shonke

I understand that you mean the list-based matcher with longest-suffix matching (LSM) rule for SNI.

It is 'technically' possible, but it linearly increases the matching cost with the number of protocol entries.

[Current implementation] Recall that by using a hash-map or similar data structure, the cost to find a matched protocol entry with exact-matching is O(1) for a given server_name in TLS ClientHello. For instance, given example.com, we search for it in a table like:

<key>      : <value>
example.com: ...
example.org: ...
example.net: ...

Then, the average cost to find a matched entry (value = protocol spec) can be estimated as O(1).

[List-based matching with LSM] On the other hand, by allowing this matching strategy, we first check for each list whether the given name is contained under the rule of longest-suffix matching. Specifically, for each protocol spec entry, we need to execute a search operation using a certain algorithm, much like domain-based filtering for DNS.

Using a trie-based data structure (like Patricia-trie/QP-trie/etc.), it is O(1) on average to check whether the given name is contained in a list under the LSM rule. However, we have n entries, so the cost simply increases with the number of protocol spec entries, i.e., O(n). I think it could be a cause for DoS attacks. This is why we currently adopt the simplest strategy.

However, I agree that it would be useful to allow a list for matched server_names. I am considering whether it is feasible, e.g., by restricting the number of protocol specs specifying SNI-based routing.

[Shonke]

@junkurihara
I think this is unnecessary. If we consider performance, we can do it this way. Only supports subdomains at one level, for example:

match sub.example.org:
server_names.has(".example.org")

match sub.abc.example.org:
server_names.has(".abc.example.org")

[junkurihara]

It is still O(n) for n entries with server_names since it must require a for-loop. It is not a reduction of computational cost.

[Shonke]

This is a very obvious fallacy. If I were to add 100 domains (assuming they are all subdomains of the same level under the same domain name, which should not be encountered in reality) to the "server names" in the configuration file, then you would have to loop 100 times. Obviously, this situation actually fits your description of O(n).

If I simplify these domain names to ". example. com", then I only need one loop to handle situations such as "a.example. com", "b.example. com" (excluding "a.b.example. com"), and so on, and its complexity is not O(n) but O(2).

[junkurihara]

No, it is completely wrong. the first case is O(1) with a hash table. This can be done with a single hash map lookup, and no loop of size n is required. the average cost is always constant. That’s why I adopt this strategy.

For the latter case, O(2) is a wrong expression in the complexity theory. The cost is linearly increasing with the list size in the case. So, it is O(n) for the list size n. Consider two domain suffix are specified (two entries in a list). Then you need two (= n) operations for checking if a given name matches with the suffix pattern, in the worst case, right? That would be worse than the exact match using a hash map when two or more suffix patterns are given. This would be a DoS attack surface in a large scale scenario.

I actually agree that the simplification of the configuration in your idea would be nice for many cases. But I prioritize the security and performances from the viewpoint of fundamentals of computer science. So, we should explore the way to balance the flexibility and security/performance. (For instance, we should consider if other data structures like tries (e.g., QP trie, patricia trie) works in this situation with O(1).)

[junkurihara]

Ah i might misunderstand for the first case. You mean you add n domains in a single sever_names field of an entry, right? And you also mean the list is replaced with a pattern, like

[a.example. com, b.example.com] -> .example.com

If my understanding is correct, the cost for both case is O(1). Using the hash-set, you can check the existence of a given name in a list with O(1). For suffix matching, it is O(1).

Apart from this, I might misunderstood my current implementation. Will inspect later. But actually, multiple incompatible suffix patterns must be simultaneously allowed (like .example.com and .example.org) since only single suffix pattern cannot cover my use case. Then, it still increases the search complexity.

[junkurihara]

@Shonke

Based on the insights you provided in this issue, I've updated another crate match_domain. Using a double-array trie, this crate rapidly finds matching prefixes/suffixes for a given domain and can output the longest-matched-prefix/suffix.

For instance, consider a case where a pattern

[*.google.com, api.google.com, *.example.com, api.example.com]

is stored. Then for a given domain sample.api.google.com, it rapidly outputs the longest-suffix-matched domain, i.e., api.google.com. Note that we do not need a for-loop to check every pattern. It just executes a single trie look-up operation with complexity O(m), where m is the length of the given domain, independently of the size of the pattern list. Note that this is sometimes faster than a hash map in a real-world use case. Also, using a trie, we can handle inconsistent suffix/prefix patterns (like google.com and example.com) in a single data structure.

Anyways, I believe that by using this updated crate, we can consider implementation of a longest-prefix/suffix based SNI matching. To this end, we have to design a data structure connecting a pattern (like *.google.com) and each TLS protocol entry. I think this can be done by a simple hash map, which involves a look-up cost O(1). The following code is my initial idea for that.

let hashmap_pattern_to_proto: HashMap<String, pointer_to_proto_entry> = ...;

// O(1)
let proto_pointer = connection_pattern_proto.get(found_matched_longest_suffix);

// If found, serve it
if let Some(pointer) = proto_pointer {
  let proto = tls_proto_list[pointer];
  ...
}

However, to implement this update, we need a lot of modifications, e.g.,

• updating internal TLS proto management data structure
• updating configuration handler
• etc...

So I cannot promise this idea will be adopted soon.

There is also room for discussion. We need to consider a priority for the case where both prefix and suffix are matched with different protocol entries. For instance, consider the following case:

[protocols."tls_1"]
protocol = "tls"
target = [ ... ]
server_names = ["*.internal.local", "*.example.com", "*.example.org" ] # exapmle.com and *.example.com are the same.

[protocols."tls_2"]
protocol = "tls"
target = [ ... ]
server_names = ["api.internal.*", "api.test.*", "api.*" ]

Then, for a given SNI api.internal.local, both of tls_1 and tls_2 are matched respectively with longest-suffix and longest-prefix matching. In my opinion, suffix matching should be prioritized.

[Shonke]

It looks good. For priority selection, I also believe that suffix matching takes priority.