The Sum-of-Squares (SoS) hierarchy is a semi-definite programming\nmeta-algorithm that captures state-of-the-art polynomial time guarantees for\nmany optimization problems such as Max-$k$-CSPs and Tensor PCA. On the flip\nside, a SoS lower bound provides evidence of hardness, which is particularly\nrelevant to average-case problems for which NP-hardness may not be available.\n In this paper, we consider the following average case problem, which we call\nthe \\emph{Planted Affine Planes} (PAP) problem: Given $m$ random vectors\n$d_1,\\ldots,d_m$ in $\\mathbb{R}^n$, can we prove that there is no vector $v \\in\n\\mathbb{R}^n$ such that for all $u \\in [m]$, $\\langle v, d_u\\rangle^2 = 1$? In\nother words, can we prove that $m$ random vectors are not all contained in two\nparallel hyperplanes at equal distance from the origin? We prove that for $m\n\\leq n^{3/2-\\epsilon}$, with high probability, degree-$n^{\\Omega(\\epsilon)}$\nSoS fails to refute the existence of such a vector $v$.\n When the vectors $d_1,\\ldots,d_m$ are chosen from the multivariate normal\ndistribution, the PAP problem is equivalent to the problem of proving that a\nrandom $n$-dimensional subspace of $\\mathbb{R}^m$ does not contain a boolean\nvector. As shown by Mohanty--Raghavendra--Xu [STOC 2020], a lower bound for\nthis problem implies a lower bound for the problem of certifying energy upper\nbounds on the Sherrington-Kirkpatrick Hamiltonian, and so our lower bound\nimplies a degree-$n^{\\Omega(\\epsilon)}$ SoS lower bound for the certification\nversion of the Sherrington-Kirkpatrick problem.\n