Dec
26

Access-list address and wildcard pair calculations are based
around the AND and XOR logic gates.

AND: The output is high only when both inputs A and B are high.

A AND B
______________
| A | B | out |
| 0 | 0 |  0  |
| 0 | 1 |  0  |
| 1 | 0 |  0  |
| 1 | 1 |  1  |
--------------

XOR: The output is high when either of inputs A or B is high, but not if
both A and B are high.

A XOR B
______________
| A | B | out |
| 0 | 0 |  0  |
| 0 | 1 |  1  |
| 1 | 0 |  1  |
| 1 | 1 |  0  |
--------------

To find the most specific address and wildcard pair that will
match two addresses, A and B, we use the gates AND and XOR. The address
we will check in the access-list is A AND B. The wildcard used to check
in this list will be A XOR B.

access-list 1 permit [address_to_check] [wildcard_used_to_check]

Take the following example:

We have two IP addresses, 10.20.30.40, and 40.30.20.10. How do we
create an access-list that is the most specific match for these two
addresses? First, write both addresses out in binary:

10.20.30.40 = 00001010.00010100.00011110.00101000
40.30.20.10 = 00101000.00011110.00010100.00001010

To find the address_to_check, take the logical AND of these addresses.

   00001010.00010100.00011110.00101000
&& 00101000.00011110.00010100.00001010
--------------------------------------
   00001000.00010100.00010100.00001000

This is our address_to_check: 8.20.20.8

To find the matching wildcard_used_to_check, we take the logical XOR of
these addresses.

    00001010.00010100.00011110.00101000
XOR 00101000.00011110.00010100.00001010
---------------------------------------
    00100010.00001010.00001010.00100010

This is our wildcard_used_to_check: 34.10.10.34

Therefore, the most specific match for both 10.20.30.40 and 40.30.20.10
would be:

access-list 1 permit 8.20.20.8 34.10.10.34

Here’s one more:

A = 1.2.3.4
B = 5.6.7.8

1.2.3.4 = 00000001.00000010.00000011.00000100
5.6.7.8 = 00000101.00000110.00000111.00001000

A && B  = 00000001.00000010.00000011.00000000
A XOR B = 00000100.00000100.00000100.00001100

Therefore the access-list would read:

access-list 1 permit 1.2.3.0 4.4.4.12
About Brian McGahan, CCIE #8593, CCDE #2013::13:

Brian McGahan was one of the youngest engineers in the world to obtain the CCIE, having achieved his first CCIE in Routing & Switching at the age of 20 in 2002. Brian has been teaching and developing CCIE training courses for over 10 years, and has assisted thousands of engineers in obtaining their CCIE certification. When not teaching or developing new products Brian consults with large ISPs and enterprise customers in the midwest region of the United States.

Find all posts by Brian McGahan, CCIE #8593, CCDE #2013::13 | Visit Website


You can leave a response, or trackback from your own site.

32 Responses to “How do I compute complex wildcard masks for access-lists?”

 
  1. anthony esdaile says:

    This was so great, ive been searching for good explanations on this subject for weeks now.

    Is it possible to compute more than two examples say for example if i wanted 3 or 4 ranges.

    I would very much appreciate an example on complex summarisation too as i cannot find any examples anywhere

  2. Ted Schafer says:

    Great Blog!!
    Nice explanation of a difficult subject.
    This post caught my eye, because of the exclusive or gate.
    Good to know all that Boolean algebra wasn’t for not.
    Ted

  3. Andy Irving says:

    Great post, I have also seen wildcard masks used to block either all odd or even number subnets by looking for a 1 in bit 1 of the respective octet
    E.g
    192.168.1.0
    192.168.2.0
    192.168.3.0
    192.168.4.0
    192.168.5.0
    192.168.6.0

    To filter only odd subnets the ACE would be
    192.168.0.0 0.0.1.0

  4. An explanation on the why AND and XOR operations are used would be great. My own explanation is as follows:

    The AND operation will result in an address that has the “common” up bits in addresses A & B. The XOR operation will result in a wildcard that’ll have bits set to one for the parts of the addresses that are not equal.

    Therefore you’ll check an address with the bits that are common between A & B, with a wildcard that tells the router to ignore the bits that are not common (since the XOR operation will only give a 1 result when two bits are different).

  5. [...] quite tedious so NAT added a bit of interest to it.  Another item that gained my interest is a post by Brian McGahan on the Internetwork Experts blog detailing how to work out the most specific match [...]

  6. D says:

    Also you can use the calc in windows (scientific) AND/XOR function to compute the wild card masks.

  7. trilok says:

    I won’t agree with the solution provided as to combine a pair of ip address with wild card mask the mandatory thing is only 1 bit has to vary while we compare that pair of addresses or else no way we can combine those IP addresses if they are are having more than 1 bit varying in between them.

    The range of IP addresses that an accesslist applies is purely based on number of 1′s in the wild card mask. i.e range = 2^(number of 1′s in the wild card mask)

    If its failing then it will apply to some other addresses apart from the desired one’s

  8. George Roman says:

    One problem,

    As far as i now this “XOR” function is not the logical XOR when you try to compute more than 2 “inputs”(3 ips for example). In this last case the result of the XOR operation would be different (you would calculate xor between first 2 inputs and the result will come into play with the 3-rd input).
    So by the correct XOR logic the result of 3 IPs would not give you the correct wildcard mask.

  9. Ziv says:

    I’m working with Cisco and ACLs for nearly 10 years and I’d never needed to calculate so complex wildcards, so I don’t know, perhaps I’ve never met complex networks, but I think that if you’re in need for so comlex wildcards it must have something to do with bad network designing…

  10. Steve Raymond says:

    While this is interesting, what is a practical application of that broad an ACL? e.g., the example 8.20.20.8 34.10.10.34 covers any IP addresses starting with the 1st octet like:
    8
    9
    10
    11
    12
    13
    14
    15
    24
    25
    26
    27
    28
    29
    30
    31
    40
    41

    And the 2nd & 3rd octet:
    20
    21
    22
    23
    28
    29
    30
    31
    52
    53
    54
    55
    60
    61
    62
    63
    84
    85

    Don’t get me wrong, I like the xor description and explanation. But I don’t see where this would be useful in IOS ACLs?

    Thanks!

  11. The point is just to show the binary logic of how the wildcard is derived. The practical implementation of this would be to aggregate multiple access list lines into a single statement in order to save processing power. Remember that for a traffic filter the router has to check each entry in a top down fashion until a match occurs. For example if you are doing “bogon” filtering, the access-list is best implemented as an aggregated list. You can see more information about this here:

    http://www.cymru.com/Documents/bogon-dd.html

    Look at Cisco ACL Aggregated and Cisco ACL Non-Aggregated

  12. Harmik says:

    Hi All

    I am new to this configuring cisco router. the scenario is, I want to use access list.

    In ACL, I want to permit only ip range 192.168.0.0 – 192.168.0.255
    192.168.2.0 – 192.168.2.255

    and deny the following

    deny 192.168.1.0 – 192.168.1.255
    deny 192.168.3.0 – 192.168.255.255

  13. Harmik says:

    Thanks All

    I just figured out how to do all this

    deny ip 192.168.1.0 0.0.0.255 any
    deny ip 192.168.3.0 0.0.252.255 any
    deny ip any 192.168.1.0 0.0.0.255
    deny ip any 192.168.3.0 0.0.252.255
    permit ip 192.168.0.0 0.0.0.255 any
    permit ip 192.168.2.0 0.0.0.255 any

    ======its working for me now….

    good news….

  14. Phil says:

    Hi

    I read the article from Brian McGahan under http://www.internetworkexpert.com/resources/01700370.htm

    I can not follow his wildcard calculation (xor part) in the 2nd example. The calculation is

    xor of

    00001010 00000000 00000000 00000000
    00001010 00000100 00000000 00000000
    00001010 00100000 00000000 00000000
    00001010 00100100 00000000 00000000

    00000000 00100100 00000000 00000000 (his result)

    00000000 00000000 00000000 00000000 (my result)

    Why does 1 xor 1 become 1 in his calculation?

    Any help or insight highly appreciated.

    cheers

  15. charles says:

    i tried this and it does not work: please have a look:

    87.98.96.15 & 91.156.17.84

    First in binary:
    128 64 32 16 8 4 2 1
    0 1 0 1 0 1 1 1 = 87
    0 1 1 0 0 0 1 0 = 98
    0 1 1 0 0 0 0 0 = 96
    0 0 0 0 1 1 1 1 = 15

    0 1 0 1 1 0 1 1 = 91
    1 0 0 1 1 1 0 0 = 156
    0 0 0 1 0 0 0 1 = 17
    0 1 0 1 0 1 0 0 = 84
    LOGICAL AND:
    01010111.01100010.01100000.00001111
    01011011.10011100.00010001.01010100
    —————————————————–
    01010011.00000000.00000000.00000100 = 83.0.0.4 = IP

    LOGICAL XOR:
    01010111.01100010.01100000.00001111
    01011011.10011100.00010001.01010100
    —————————————————
    00001100.11111110.01110001.01011011
    =
    12.254.113.91 = wildcard mask
    83.0.0.4 12.254.113.91

    83.0.0.4 12.254.113.91
    Now to confirm:
    128 64 32 16 8 4 2 1
    0 1 0 1 0 0 1 1
    0 0 0 0 1 1 0 0
    0 means to match exact
    1 means ignore
    0 1 0 1 IGNORE IGNORE 1 1
    So what values do we get for the first octet?
    64+16+3 –these values are always present = 83
    The ignored values are either ON or OFF
    If OFF then the value = 8 OR 4 OR 12
    So the first octet is either
    83
    Or
    95
    Or
    87
    Or
    91

    therefore as you can see i am incorporating 2 ADDITIONAL subnets that i do not own: 83.x.x.x & 95.x.x.x.

    Where did I go wrong?

  16. charles says:

    Will the “great” Brian McGahan respond, please?

    Where did I go wrong with my calcuation?

    It seems that your logic–or whoever illustrated this method of reasoning–is faulty.

  17. Polleke says:

    That is caused by the difference in how Cisco is calculating XOR and how Electronic Logic Gates (or XOR function in programming languages) are calculating XOR.

    Cisco way of calculating XOR:
    =============================

    Binary input:
    IP1 00000001 00000010 00000011 00000100 (1.2.3.4)
    IP2 00000101 00000110 00000111 00001000 (5.6.7.8)
    IP3 00001001 00001010 00001011 00001100 (9.10.11.12)
    IP4 00001101 00001110 00001111 00010000 (13.14.15.16)

    Binary output:
    AND 00000001 00000010 00000011 00000000 (1.2.3.0)
    XOR 00001100 00001100 00001100 00011100 (12.12.12.28)

    ==> If there is a 1 in a column, but not all 1-’s –> result=1 otherwise result=0

    Electronic way of calculating XOR:
    ==================================

    Binary input:
    IP1 00000001 00000010 00000011 00000100 (1.2.3.4)
    IP2 00000101 00000110 00000111 00001000 (5.6.7.8)
    IP3 00001001 00001010 00001011 00001100 (9.10.11.12)
    IP4 00001101 00001110 00001111 00010000 (13.14.15.16)

    Binary output:
    AND 00000001 00000010 00000011 00000000 (1.2.3.0)
    XOR 00000000 00000000 00000000 00010000 (0.0.0.16)

    ==> If there is an odd amount of 1′s in a column –> result=1 otherwise result=0

    I wrote a proggie to calculate it… http://parmasoft.com/wildcard.zip

    Rgds Paul-:

  18. Charles says:

    Thanks Paul
    I will have a look at it shortly

  19. Cody says:

    I liked the posting about complex ACL’s. I have done many complex ACL’s in the past, or at least I thought so. Any way I liked the information so much I created a Config Builder for it. I posted the config builder on my blog at http://www.melcara.com. I have not tested all the possible outcomes, but the logic is sound.

    Thanks for a great posting.

  20. Ray says:

    Many other IP’s got match.

    The statement “access-list 1 permit 8.20.20.8 34.10.10.34″
    not only permit
    10.20.30.40 = 00001010.00010100.00011110.00101000
    40.30.20.10 = 00101000.00011110.00010100.00001010
    but also permit many others also.
    for example:
    8.20.30.40
    42.30.20.10

    Brian,
    Appreciate if a reference for the mathematical prove is provided.

    Thanks.

  21. Parasar Das says:

    Brian,

    In your example you showed access list with two ip address, what if there are four or five address ? Also could you tell us the reverse calculation from access list 8.20.20.8 34.10.10.34 back to original subnets ?

    Regards
    Parasar

  22. reyjoy says:

    that’s great…

    I analyzes this ACL usually used this wildcard mask.and until now i can’t understand how to get it. can you give me some example that easy to understand.

  23. stephen says:

    i undestand the logic, but does anyone have any good resources for achieving the same with an extended access-list or Prefix-list ?

  24. ouki says:

    It is crucial to note that “Cisco” way of implementing XOR is different from well-known binary logical operation of “XOR”, especially when there are more than two elements. It has confused me for a week until I saw post above.

  25. Ibrahim says:

    Dear all,

    I thought that the wild card mask have only specific numbers that should be used for it such as :

    0.0.0.1
    0.0.0.3
    0.0.0.7
    0.0.0.15
    .
    .
    .
    up to 127.255.255.255

    I just would like to understand when we use such a method to calculate the wild card mask?

    Thanks in advance :)

  26. indrapal says:

    Is it possible to compute more than two examples say for example if i wanted 3 or 4 ranges…

    Plz reply

  27. realdreams says:

    Is that a unique match in both ways? It would be great if someone can create a page to convert between ACL and network/host.
    The uniqueness matters. Unintended matches can create problems.

 

Leave a Reply

Categories

CCIE Bloggers