Tuesday, October 26, 2010

Fun with Raw Sockets in Erlang: Bridging

Hosts connecting to another system on the same network map the protocol address (e.g., IPv4 address) of the destination host to a hardware address (e.g., ethernet MAC address) using the ARP protocol. Clients on different networks can communicate by having a device forward the packets between networks. These devices, usually multi-homed and spanning networks, forward packets by re-writing the packet headers: for example, the ethernet header (a bridge), the IP header (a router) or the IP and TCP headers (a NAT).

An ethernet II header:

  • Preamble:42
  • Start of Field Delimeter:8
  • Destination Host:48
  • Source Host:48
  • Type:16
  • Protocol Payload:N
  • CRC:16

Not all of these fields will be visible to processes running on the operating system.

  • The Preamble starts the Ethernet frame (not available to the OS)
  • The SOF Delimiter marks the start of the destination host address field (not available to the OS)
  • The Destination Host is the 6 byte MAC address of the target host
  • The Source Host is the 6 byte MAC address of the sending host
  • The Type represents the protocol held in the payload. Common types are IPv4 (ETH_P_IP (16#0800)), ARP (ETH_P_ARP (16#0806)) and IPv6 (ETH_P_IPV6 (16#86DD)).
  • A trailing CRC checksum of the packet (frame check sequence) (usually not available to the OS)

    Ethernet frames can apparently include other trailing data, leading to trailing junk when doing packet captures.

    When capturing data off the network, it's important to properly calculate the size of the packet. For example, for an IPv4 TCP packet:

    IP length - (IP header length * 4) - (TCP offset * 4)

The ethernet header has fixed size fields and so does not explicitly include a field for length. Interestingly, Ethernet 802.3 frames use the Type field for the length (according to Wikipedia 802.3 packets can be distinguished from Ethernet II packets by:

  1. if the value of the Type field is equal to or less than 1500 bytes (maximum frame length), the frame is Ethernet 802.3 and the value represents the length of the frame
  2. if the value of the Type field is equal to or greather than 1536, the frame is Ethernet II and the value represents the protocol type of the encapsulated packet

    The protocol of 802.3 frames is always IPX.

  3. if the value of the Type field is between 1500 and 1536, the behaviour is undefined)

An Erlang binary representation of an Ethernet II frame:

Dhost:6/bytes,        % destination MAC address
Shost:6/bytes,        % source MAC address
Type:16               % protocol type, usually ETH_P_IP

Using Erlang to Bridge Packets

To go along with the ARP poisoning, we need a sort of "one armed bridging" to forward packets from our spoofing host to the real destinations. Once we have the raw ethernet frames, doing the bridging is quite simple. For the complete code, see herp on GitHub (yes, the herp is what you get when you've been promiscuous. I hear like 80% of adults have it).

I won't include much of the code here because it's so trivial. The bridging process captures packets off the network and pattern matches on the headers:

filter(#ether{shost = MAC}, _, #state{mac = MAC}) ->
filter(#ether{type = ?ETH_P_IP}, Packet, State) ->
    {#ipv4{daddr = DA}, _} = epcap_net:ipv4(Packet),
    filter1(DA, Packet, State);
filter(_, _, _) ->

filter1(IP, _, #state{ip = IP}) ->
filter1(IP, Packet, #state{gw = GW}) ->
    MAC = case packet:arplookup(IP) of
        false -> GW;
        {M1,M2,M3,M4,M5,M6} -> <<M1,M2,M3,M4,M5,M6>>
    bridge(MAC, Packet).
  1. Check if the frame has our MAC address
  2. Retrieve the IP address from the frame and check the system ARP cache. A real bridge would monitor the network for ARP packets and cache the results.
  3. If the IP exists in our ARP cache, use the MAC address, otherwise, send it to the gateway (it's possible the IP address does not exist in the system ARP cache and will be wrongly forwarded to the gateway)
If the frame should be bridged, we create a new frame with the source hardware address set to our host's MAC address. The IP header and payload are not touched.
handle_call({packet, DstMAC, Packet}, _From, #state{
        mac = MAC,
        s = Socket,
        i = Ifindex} = State) ->

    Ether = epcap_net:ether(#ether{
            dhost = DstMAC,
            shost = MAC,
            type = ?ETH_P_IP

    packet:send(Socket, Ifindex, list_to_binary([Ether, Packet])),
    {reply, ok, State};

It'd be interesting to experiment with making herp into a traditional network bridge: quite likely very slow, but also redundant, distributed and fault tolerant.

Monday, October 25, 2010

Fun with Raw Sockets in Erlang: ARP Poisoning

On IP ethernet networks, hosts use a peer to peer method called ARP (address resolution protocol) to discover the hardware address of the peer with which they intend to communicate.

IPv4 ethernet ARP packets are specified as:
  • Hardware Type:16
  • Protocol Type:16
  • Hardware Length:8
  • Protocol Length:8
  • Operation:16
  • Sending Hardware Address:48
  • Sending IP Address:32
  • Target Hardware Address:48
  • Target IP Address:32

The numbers after the colon represent the size in bits of the field.

  • The Hardware Type of the network is ethernet, so the value is set to ARPHRD_ETHER (1)
  • The Protocol Type of the network is IPv4, so the value is set to ETH_P_IP (0x0800)
  • The Hardware Length of an ethernet MAC address is 6 bytes
  • The Protocol Length of an IPv4 address is 4 bytes
  • Operation is usually an ARP request (ARPOP_REQUEST (1)) or reply (ARPOP_REPLY (2))
  • The Sending Hardware Address is the MAC address of the host sending the ARP packet
  • The Sending IP Address is the IPv4 address of the host sending the ARP packet
  • The Target Hardware Address is the MAC address of the host receiving the ARP packet

    The target address may be the ethernet broadcast address (FF:FF:FF:FF:FF:FF or 00:00:00:00:00:00) which results in all hosts receiving the ARP packet.

  • The Target IP Address is the IPv4 address of the host sending the ARP packet
The corresponding Erlang representation of an IPv4 ethernet ARP packet is:
<<Hrd:16, Pro:16,
Hln:8, Pln:8, Op:16,
Sha:48, Sip:32,
Tha:48, Tip:48>>

Behaviour of the ARP Cache

ARP caches are key/value stores holding a mapping of the protocol address to the hardware address. To prevent caching of stale data, entries eventually expire. The expiry timeout varies; for example, on MS Windows, arp entries are kept for 2 minutes if another session to the remote host is not initiated. If a session is initiated within the 2 minute period, the ARP cache expiry time is extended to 10 minutes.

ARP is opportunistic and trust-based. If a host sees an ARP request or reply for which it is not the target, the host may cache the information. However, caching all requests would be pointless, since arp lookup would be slow on a network with a large number of peers with which the host might never communicate.

Gratuitous ARPs

ARPs are gratuitous when no request was made for the information. Gratuitous ARPs are useful for:
  • discovering IP conflict
  • IP take over: in a high availability cluster of servers, one of the hosts is active (holding the service IP address). In the event of a failure of the active node, one of the slave nodes can assume the service IP address, sending a gratuitous ARP to inform the other nodes and the gateway that the IP address is associated with a new MAC address
An Erlang binary representing a gratuitous ARP looks like:
1:16,                                 % hardware type
16#0800:16,                           % protocol type
6:8,                                  % hardware length
4:8,                                  % protocol length
2:16,                                 % operation: ARPOP_REPLY
0,1,2,3,4,5,                          % sending MAC address
192,168,1,100,                        % sending IPv4 address
16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,  % target MAC address: ethernet broadcast
192,168,1,100                         % target IPv4 address: set to sending address
Behaving badly by gratuitously arp'ing for all the IP addresses on the network will DoS the other hosts, eventually forcing them to report a network error condition and go offline.

Sending an ARP Reply

To send an ARP packet from Erlang, we'll use the procket module on GitHub. The functions in procket used for these examples are unfortunately Linux-only. For this example, the binaries are manually specified. The epcap_net module on GitHub has convenience functions for creating and decomposing ARP packets into a record structure. If the network was set up like:
  • arping Erlang node:
  • source host:
  • target host (doesn't exist):
Login to another host on your network (the source node) and run tcpdump:
tcpdump -n -e arp
In another window, run the code:
$ erl -pa /path/to/procket/ebin
Erlang R14B01 (erts-5.8.2) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.8.2  (abort with ^G)
1> carp:send({10,11,11,11}). % Use an address on your network
If the MAC address of the Erlang node is 00:aa:bb:cc:dd:ee, then on the other host you should see something like:
00:59:35.051302 00:aa:bb:cc:dd:ee > ff:ff:ff:ff:ff:ff, ethertype ARP (0x0806), length 60: arp reply is-at 00:aa:bb:cc:dd:ee
Check the ARP cache on the source node:
arp -an
The ARP entry may not exist. Since ARP caching is opportunistic, it is up to a host to decide whether it will optimize future connections by caching an unsolicited entry. To force an ARP cache entry on the remote host, ping the fake IP address:
Then, in the Erlang shell, run carp:send/1. Run "arp -an" again on the remote host. The ARP cache entry for should now be there.
? ( at 00:aa:bb:cc:dd:ee [ether] on eth0
If you run tcpdump on the host doing the ARP'ing, you should see ICMP traffic for
01:13:36.075040 IP > ICMP echo request, id 35604, seq 17, length 64
01:13:36.088794 IP > ICMP echo request, id 35604, seq 18, length 64
01:13:36.106572 IP > ICMP echo request, id 35604, seq 19, length 64
Since this IP address is not bound to any interface on your host, there will, of course, be no reply.

Poisoning the ARPs

On old networks using hubs or open networks using 802.11 access points, data is broadcasted to all the hosts. Running a packet sniffer displays the network activity for everyone, not just yourself.

Switched networks learn the MAC address of the host connected to the port of the switch and send data only to the recipient. ARP poisoning or spoofing fools other hosts on the network to send data to the host under your control. If your host spoofs the gateway, you'll also see the internet traffic. Obviously, if your host is not somehow routing, the packets will go nowhere, performing a denial of service on your network. But you will be able to see the data other hosts are sending.

Using the code we ran earlier, we can test ARP spoofing. You'll need 3 hosts: one doing the poisoning and two victims, a source and a target. The process is the same as above. For example, if were a real host, we would have convinced to send its data through our host.

I've put my experiment in progress with ARP poisoning, farp, on GitHub. farp works by replying to ARP requests with our host's MAC address. It can also optionally send out gratuitous arps as the gateway to speed up the process.

Sunday, October 17, 2010

Setting Parity on DES Keys

DES keys are 8 bytes, of which only 7 bits of each byte are used for the key. The least significant bit is used for parity and is thrown away for the actual encryption/decryption (resulting in a 56-bit key for single DES). Mostly, it seems, the parity is ignored by DES implementations, but occasionally a system using DES will check the parity and reject the key if the parity is not odd (or so Google tells me, I've never actually seen this happen). The parity bit was intended to prevent corruption or tampering with the key.

The DES parity calculation works as follows:
00001001 = 9
  • for each byte, count the number of bits that are set. For the example byte above, 2 bits are set
  • if the number of bits set is odd, do nothing
  • if the number of bits is even, set or unset the least significant bit to make the count odd
In the example, the new value for the byte would be
00001000 = 8
Reading through Erlang's crypto support for DES and DES3, it's up to the caller to use a valid key. For example, the NIF making up crypto:des_cbc_crypt/3 is defined as:
DES_set_key((const_DES_cblock*), &schedule);
DES_ncbc_encrypt(, enif_make_new_binary(env, text.size, &ret),
    text.size, &schedule, &ivec_clone, (argv[3] == atom_true));
DES_set_key() is an OpenSSL compatibility function that, in this case, is identical to DES_set_key_unchecked(). The corresponding checking function, DES_set_key_checked(), returns some information about the key: -1 (if the parity is even) and -2 (if the key is weak).

So I was curious how to go about setting the parity in a functional language. It turns out to be quite easy:

-export([set_parity/1, check_parity/1, odd_parity/1]).

set_parity(Key) ->
    << <<(check_parity(N))>> || <<N>> <= Key >>.

check_parity(N) ->
    case odd_parity(N) of
        true -> N;
        false -> N bxor 1

odd_parity(N) ->
    Set = length([ 1 || <<1:1>> <= <<N>> ]),
    Set rem 2 == 1.

set_parity/1 uses a binary comprehension to read 1 byte at a time from the 8 byte key.

check_parity/1 checks whether an integer has an odd or even parity and returns the integer XOR'ed with 1 if the parity is even.

odd_parity/1 counts the bit set by using a bit comprehension to return the list of bits that are set. The modulus of the length of this list returns oddness/evenness.

To test if this is correct, we can check if a few cases (all even bits or all odd bits in a key) work and then test that a key with corrected parity produces the same cipher text as the uncorrected key:

test() ->
    <<1,1,1,1,1,1,1,1>> = set_parity(<<0:(8*8)>>),
    <<1,1,1,1,1,1,1,1>> = set_parity(<<1,1,1,1,1,1,1,1>>),
    K1 = <<"Pa5Sw0rd">>,
    K2 = set_parity(K1),
    Enc = crypto:des_cbc_encrypt(K1, <<0:64>>, "12345678"),
    Enc = crypto:des_cbc_encrypt(K2, <<0:64>>, "12345678"),
    <<"12345678">> = crypto:des_cbc_decrypt(K2, <<0:64>>, Enc),