The case when $a=b$ is easy. WLOG $\nu_2 (a^2-1)\geqslant \nu_2 (b^2-1)$. Let $t=\nu_2 (b^2-1)$. We'll prove by induction on $n\geqslant t$ that there exists positive integer $k_n$ that $2^n\mid b^{k_n}-a^2.$ Base case is easy. Take $k_t=2\implies b^{k_t}-a^2=(b^2-1)-(a^2-1).$ For inductive step. Suppose there exists $k_m$ for some $m\geqslant t$. If $2^{m+1}\mid b^{k_m}-a^2,$ simply take $k_{m+1}=k_m$. If not, we get $\nu_2 (b^{k_m}-a^2)=m$. Consider $k=k_m+2^{\ell}$. We have $b^{k}-a^2=b^{k_m}( b^{2^{\ell}}-1) +(b^{k_m}-a^2).$ Since $\nu_2 (b^{2^{\ell}}-1)=t+\ell -1,$ choosing suitable $\ell$ gives $\nu_2 (b^{2^{\ell}}-1)=m\implies \nu_2 (b^{k}-a^2)\geqslant m+1$.