The present invention provides a communication channel establishment method that establishes a communication channel used particularly when a cipher communication is carried out. Where a packet indicative of an ISAKMP message transmitted from a second communication device to a first communication device is awaited when a communication channel between the first and second communication devices is established via an IP network, the time taken to wait for the packet is counted by a corresponding packet waiting timer at random intervals. When a packet other than the sequence of each packet expected to be transmitted from the second communication device is received, the packet is accepted to establish the communication channel.