How can a host determine what address mask is in use on a remote host without logging in?

Interestingly, icmp is so powerful , that it can get us this information.

RFC 792 does not mention about the Address Mask( or type 17/18). However RFC 950 has the inherent rationale(Section 2.3) for embedding this option in icmp.

Using nemesis the solution can be seen in action outright.



@SOURCE_MACHINE>/usr/local/bin/nemesis icmp -qM -i 17 -m 0 -S 129.158.224.205 -D 129.158.224.182 -H 0:3:ba:4e:40:44 -M 00:03:ba:5b:8f:5d

ICMP Packet Injected

@SOURCE_MACHINE>snoop icmp
Using device /dev/eri (promiscuous mode)
SOURCE_MACHINE -> DESTINATION_MACHINE ICMP Address mask request
DESTINATION_MACHINE -> SOURCE_MACHINE ICMP Address mask reply (Mask = 0xffffff00)
^C@SOURCE_MACHINE>

My failed experiment to detect nodes in Promiscious mode.

Basic Prerequisites: Promiscuous mode,ARP, ICMP and Packet Injection.


Problem:
========
The decision to accept/drop the network packets is controlled by the Network Interface Card(NIC). NIC filters out the desired packets which system is entitled to recieve. However by setting the NIC to promiscuous mode the sniffing application receives packets regardless of the system being the intended destination. Sniffing is a difficult problem to acertain as it does not interfere with the network traffic, leaving no digital traces to track.


My Approach in theory
=====================
A “dynamic” protocol like Address Resolution Protocol (ARP) can be leveraged to detect the sniffing host. This protocol works alongside the Internet Protocol(IP) in Layer 3. On account of this ARP's operation occurs automatically in the background, without concern to the application user.

ARP works by sending an address request and collecting the response to create its mapping of addresses. The hardware addresses are only needed for hosts on the local network. At the lowest level, the Ethernet driver needs the hardware address of the remote system to which it will send a packet. When it does not have that address, it “broadcasts” a request for the missing address. This request, called an “ARP request”, contains the IP address of the host in question and is sent to all systems on the local network. A system may respond with a reply, called an “ARP reply”, which contains the host IP address and hardware address. The response received is used to build a table of IP addresses and hardware addresses.

Another feature of the protocol is called “gratuitous ARP”. This occurs when a host broadcasts an ARP request for its own hardware address. A Solaris system does this at boot time. It is used to detect if another system is using its IP address, indicating a misconfigured system. The other use of gratuitous ARP is to send updated
hardware address information. Systems that receive requests like this will automatically update the hardware address information for that host.

ARP by default uses BROADCAST method to get the destination MAC address. The idea here is to craft an ARP packet with the destination address being a non-BROADCAST address with a specific target IP address. If the NIC is in non-promiscuous mode, the packet is ignored and after the specified TTL no response is got back. However if the node with the corresponding IP address is in promiscuous mode, a prompt response is given by the sniffing host as the packet is percolated to the higher layers.

Using a handcrafted packet like ICMP with appropriate fields can induce the same effect.

References
----------
-Defeating Sniffers and Intrusion Detection Systems
http://www.phrack.com/issues.html?issue=54&id=10#article

-Plummer, Dave. An Ethernet Address Resolution Protocol, RFC 826, Network
Information Center, SRI International, Menlo Park, CA., November 1982.

- Interetworking with TCP/IP VolumeII Design,Implementation and Internals. Douglas E. Comer/David L. Stevens

-Solaris Operating Environment Network Settings for Security , By Alex Noordergraaf and KeithWatson
http://www.sun.com/blueprints/1299/network.pdf


The Reality ( Getting the hands dirty )
=======================================
Destination Machine
===================
@SOURCE-MACHINE>ping DESTINATION-MACHINE
DESTINATION-MACHINE is alive
@ SOURCE-MACHINE>arp -a | grep DESTINATION-MACHINE
eri0 DESTINATION-MACHINE 255.255.255.255 00:03:ba:5b:8f:5d
@SOURCE-MACHINE>ping -s !$
ping -s DESTINATION-MACHINE
PING DESTINATION-MACHINE: 56 data bytes
64 bytes from DESTINATION-MACHINE (129.158.224.182): icmp_seq=0. time=1.26 ms
64 bytes from DESTINATION-MACHINE (129.158.224.182): icmp_seq=1. time=0.920 ms
^C
----DESTINATION-MACHINE PING Statistics----
2 packets transmitted, 2 packets received, 0% packet loss
round-trip (ms) min/avg/max/stddev = 0.920/1.09/1.26/0.24
@SOURCE-MACHINE>

Source Machine
===================


@SOURCE-MACHINE>hostname
SOURCE-MACHINE
@SOURCE-MACHINE>ifconfig -a
lo0: flags=2001000849 mtu 8232 index 1
inet 127.0.0.1 netmask ff000000
eri0: flags=1000843 mtu 1500 index 2
inet 129.158.224.205 netmask ffffff00 broadcast 129.158.224.255
ether 0:3:ba:4e:40:44


Packet Injection
=================

@SOURCE-MACHINE>/usr/local/bin/nemesis icmp -S 129.158.224.205 -D 129.158.224.182 -H 0:3:ba:4e:40:44 -M 00:03:ba:5b:8f:5d

ICMP Packet Injected
@SOURCE-MACHINE>

@SOURCE-MACHINE>snoop icmp

SOURCE-MACHINE -> DESTINATION-MACHINE ICMP Echo request (ID: 15815 Sequence number: 46167)
DESTINATION-MACHINE -> SOURCE-MACHINE ICMP Echo reply (ID: 15815 Sequence number: 46167)

Now sending a wrong MAC address to Destination ( last letter changed from d to e )

@SOURCE-MACHINE>/usr/local/bin/nemesis icmp -S 129.158.224.205 -D 129.158.224.182 -H 0:3:ba:4e:40:44 -M 00:03:ba:5b:8f:5e

ICMP Packet Injected

@SOURCE-MACHINE>snoop icmp
Using device /dev/eri (promiscuous mode)
SOURCE-MACHINE -> DESTINATION-MACHINE ICMP Echo request (ID: 12112 Sequence number: 10553)


Interesting thing to note was that the Packet was seen in the snoop output on DESTINATION-MACHINE but was not replied.


There goes the failed experiment. Reality turns out to be different than the assumed theory. Digging further as to how snoop manages to get a snapshot of the packet and not process the packet.

Getting the Kth smallest element in two Sorted Lists

Problem
--------
Let A and B be two sorted arrays. The intent is to find the kth smallest number in the union of the two lists.

Sounds Simple, but the catch is to get it done with a better time complexity than O(size(A) + size(B)).

I now have the solution which works with O(log(size(A) + size(B)), but i gave a crappy solution to my friend who gave me this puzzle. I used the intuitive, 2 pointer solution. Dont fall for it.

Implementing a queue with 2 Stacks

Interesting, but intuitive question.

My Solution:-

//QueueWith2Stacks.java

import java.util.Stack;

public class QueueWith2Stacks {

Stack< Object> insertStack=new Stack< Object>();
Stack< Object> popStack=new Stack< Object>();


void enqueue(Object element){
insertStack.push(element);
}
Object dequeue(){
if(popStack.empty()&& insertStack.empty())
return(null);
if(popStack.empty())//This is the only interesting part about it.
while(!insertStack.empty())
popStack.push(insertStack.pop());
return(popStack.pop());
}
void display(){
System.out.println(popStack.toString()+insertStack.toString());
}
}