A method is described in a network element for supporting flexible lookup keys in a software-defined network. The method includes receiving a packet to be forwarded and determining a next hop for the packet, which includes parsing the packet to identify a superkey comprising a plurality of header field values of the packet; identifying a superkey mask value and a superkey offset value for a first lookup table of a set of one or more lookup tables; generating a table key for the first lookup table based upon the superkey mask value, the superkey offset value, and the superkey; and performing a lookup in the first lookup table using the table key. The lookup identifies an entry of the first lookup table indicating the next hop for the packet. The packet may then be forwarded to the next hop.