We investigate one-way and two-way quantum key distribution (QKD) protocols. Our analysis is based on a simple precondition for secure QKD in each case. In particular, the legitimate users need to prove that there exists no quantum state having a symmetric extension (in the case of one-way QKD), or that there exists no separable state (two-way QKD) that is compatible with the available measurements results. We show that both criteria can be formulated as a convex optimization problem known as a semidefinite program, which can be efficiently solved. Moreover, we prove that the solution to the dual optimization corresponds to the evaluation of an optimal witness operator that belongs to the minimal verification set of them for the given one-way (or two-way) QKD protocol. A positive expectation value of this optimal witness operator states that no secret key can be distilled from the available measurements results. We apply such analysis to several well-known QKD protocols and obtain ultimate upper bounds on the maximal rate and distance that can be achieved with these schemes.