  Covert communication conceals the existence of the transmission from a
watchful adversary. We consider the fundamental limits for covert
communications via packet insertion over packet channels whose packet timings
are governed by a renewal process of rate $\lambda$. Authorized transmitter
Jack sends packets to authorized receiver Steve, and covert transmitter Alice
wishes to transmit packets to covert receiver Bob without being detected by
watchful adversary Willie. Willie cannot authenticate the source of the
packets. Hence, he looks for statistical anomalies in the packet stream from
Jack to Steve to attempt detection of unauthorized packet insertion. First, we
consider a special case where the packet timings are governed by a Poisson
process and we show that Alice can covertly insert $\mathcal{O}(\sqrt{\lambda
T})$ packets for Bob in a time interval of length $T$; conversely, if Alice
inserts $\omega(\sqrt{\lambda T})$, she will be detected by Willie with high
probability. Then, we extend our results to general renewal channels and show
that in a stream of $N$ packets transmitted by Jack, Alice can covertly insert
$\mathcal{O}(\sqrt{N})$ packets; if she inserts $\omega(\sqrt{N})$ packets, she
will be detected by Willie with high probability.
