Manually calculating MST digests

Switches sharing an MST region must agree on three things:

• The region name
• The region revision level
• The region's mapping of VLANs to STP instances

The first two are exchanged directly inside BPDUs, so they are easy to validate. The third item is about 6KB of data at a minimum. It doesn't fit in a BPDU.

Rather than exchange the table directly, MST switches calculate a 128-bit hash of the table and exchange that instead. If the hashes match, the VLAN-to-stp-instance mapping database is assumed to match.

Most platforms will show you the calculated digest.

Catalyst:

 lab-catalyst#show spanning-tree mst configuration  
 Name   [lab]  
 Revision 3   Instances configured 4  
 Instance Vlans mapped  
 -------- ---------------------------------------------------------------------  
 0     4-9,40-99,101-199,201-299,301-4094  
 1     1,10-19,100  
 2     2,20-29,200  
 3     3,30-39,300  
 -------------------------------------------------------------------------------  
 lab-catalyst#show spanning-tree mst configuration digest  
 Name   [lab]  
 Revision 3   Instances configured 4  
 Digest     0x37D94E0098E3418C046F217A71077FB1  
 Pre-std Digest 0xFC2190275BBB19CD9A6F1BB116DB10E7  
 lab-catalyst#  

Procurve:

 lab-procurve# show spanning-tree mst-config  
  MST Configuration Identifier Information  
  MST Configuration Name : different              
  MST Configuration Revision : 4    
  MST Configuration Digest : 0x37D94E0098E3418C046F217A71077FB1  
  IST Mapped VLANs : 4-9,40-99,101-199,201-299,301-4094  
  Instance ID Mapped VLANs  
  ----------- ---------------------------------------------------------  
  1      1,10-19,100  
  2      2,20-29,200  
  3      3,30-39,300  
 lab-procurve#  

Because their VLAN-to-instance mapping is the same, both switches arrived at the same digest value. Note that the region name and revision does not have to match for the digest to come out correctly. The digest considers the VLAN mappings only.

I was dealing recently with a switch I didn't altogether trust, and wanted to validate how the digest is created. The process is is outlined in IEEE 802.1Q-2011, and is pretty straightforward. First, an 8192-byte database is initialized. This database is 4096 individual 16-bit values with the high-order byte first. Each 16-bit record represents a VLAN (0 - 4095). The value of these records is the MST instance number that VLAN maps to (also 0 - 4095). They first and last values (VLAN0 and VLAN4095) will always be 0x0000.

Next, the 8192 bytes describing the mapping are MD5 hashed using 0x13AC06A62E47FD51F95D2BA243CD0346 as the HMAC key. If anyone knows the significance of this value, please let me know.

So, lets do this at a bash prompt.

First, I'll initialize an array describing my MST instances:

mst[1]=1,10-19,100
mst[2]=2,20-29,200
mst[3]=3,30-39,300  

Next, loop over that array, converting it from a list of hyphenated VLAN ranges to a simple list of VLANs. For example, "1,10-19,100" will become "1 10 11 12 13 14 15 16 17 18 19 100":

 # Convert mst array elements from ranges to list.
 # Begin by looping over MST instances
 for instance in ${!mst[@]}; do
   # split on comma: listed instance ranges into array 'range'
   IFS=',' read -a range <<< "${mst[$instance]}"
   mst[$instance]=''
   # Now loop over ranges
   for r in ${range[*]}; do
     # split on hyphen: range into array 'x'
     IFS='-' read -a x <<< "$r"
     mst[$instance]="${mst[$instance]} $(seq ${x[0]} ${x[@]:(-1)})"
   done
 done  

Now initialize an array to stand in for the VLAN table. All 4096 records will be mapped to the IST (instance 0) at first:

 declare -a table=( $(for i in {0..4095}; do echo 0; done) )  

Finally, we'll correct the table entries that should not be zeros. Loop over MST instances. Inside each instance loop, we'll loop over VLANs, assigning the correct MST instance number to each table entry.

 # Loop over MST instances
 for instance in ${!mst[@]}; do
   # Loop over VLANs assigned to the instance
   for vlan in ${mst[$instance]}; do
     # rewrite VLAN table entry from 0 (IST) to MST instance number
     table[$vlan]=$instance
   done
 done  

At this point, table is a 4096-element array where each item represents a VLAN and its value represents the MST instance to which it maps. All that's left is to calculate the digest.

First, we need that mysterious key. Here it is base64 encoded:

 # Key specified by 802.1Q-2011, table 13-1  
 key="E6wGpi5H/VH5XSuiQ80DRg=="  

Now I'll loop over the 4096 elements, spitting out the binary representation of each. That whole loop gets pipelined into openssl which will calculate the digest.

 # Print the 4096 element VLAN table in the format specified by 802.1Q-2011, then  
 # run it throuth openssl for digest calculation  
 digest=$(for i in $(seq 0 4095); do  
  echo -ne "$(printf '\\x%x\\x%x' $((${table[$i]}/256)) $((${table[$i]}%256)))"  
 done | openssl dgst -md5 -hmac $(base64 -D <<< $key) | awk '{print $2}')

That was on OSX. If you try it on Linux, the correct option to base64 is '-d' rather than '-D'.

Let's print out the result:

 poetaster:~ chris$ echo $digest  
 37d94e0098e3418c046f217a71077fb1  
 poetaster:~ chris$   

Great! It matches what the switches printed above.

There's no reason to ever do this, but it was a fun exercise to find out exactly how this process works. I don't understand why that particular HMAC key is used, as opposed to using an un-keyed MD5 hash, but that's what the 802.1Q-2011 calls for in table 13-1.