In this paper we prove that the set $\{|x^1-x^2|,\dots,|x^k-x^{k+1}|\,{:}\,x^i\in E\}$ has non-empty interior in $\mathbb{R}^k$ when $E\subset \mathbb{R}^2$ is a Cartesian product of thick Cantor sets $K_1,K_2\subset\mathbb{R}$. We also prove more general results where the distance map $|x-y|$ is replaced by a function $\phi(x,y)$ satisfying mild assumptions on its partial derivatives. In the process, we establish a nonlinear version of the classic Newhouse Gap Lemma, and show that if $K_1,K_2, \phi$ are as above then there exists an open set S so that $\bigcap_{x \in S} \phi(x,K_1\times K_2)$ has non-empty interior.