Which integers are the areas of squares with vertices in the 3d integer lattice? For which integers $n$ does there exist a square of area $n$ with vertices in the 3d integer lattice $\mathbb{Z}^3$? 
A sufficient condition is that $n$ is a square or the sum of two squares, and I have verified that the condition is also necessary when $n < 10^5$.
Edit: This question was posed by James Tanton on Twitter. I thought it was very interesting, so I took the liberty of posting it here.
Edit 2: I have extended the search to $n < 10^6$ without finding any counterexamples.
 A: Translate one of the vertices to the origin, then the two adjacent vertices of the square are $(x,y,z)$ and $(u,v,w)$ where $x^2 + y^2 + z^2 = u^2 + v^2 + w^2 = s$ and $xu + yv + zw = 0$, and the area of the square is $s$.  Now consider
$$
\begin{align}
(xw-uz)^2 + (yw-vz)^2
&=x^2w^2 - 2xwuz + u^2z^2 + y^2w^2 - 2ywvz + v^2z^2\\
&=(x^2 + y^2)w^2 + (u^2 +v^2)z^2 - 2(xu+yv)wz\\
&=(x^2 + y^2)w^2 + (u^2 +v^2)z^2 + 2(zw)wz\\
&=(x^2 + y^2 + z^2)w^2 + (u^2 +v^2+w^2)z^2\\
&=s(w^2+z^2)
\end{align}
$$
Since a number is a sum of two squares if and only if each prime factor of that number that is equal to $3\pmod{4}$ occurs with even exponent, all prime factors of $(xw-uz)^2 + (yw-vz)^2$ and $w^2+z^2$ equal to $3\pmod{4}$ occur with even exponent, thus each prime factor of $s$ equal to $3\pmod{4}$ must also occur with even exponent. Therefore, $s$ is a sum of two squares.
A: This is equivalent to integers $\{x_i, y_i, z_i\}$ for $i = 0, 1, 2, 3$ satisfying:
$(x_i - x_{i+1})^2 + (y_i - y_{i+1})^2 + (z_i - z_{i+1})^2 = A$ (the area)
$(x_i - x_{i+1})(x_{i+1} - x_{i+2}) + (y_i - y_{i+1})(y_{i+1} - y_{i+2}) + (z_i - z_{i+1})(z_{i+1} - z_{i+2}) = 0$
(taking $i+1$ and $i+2$ mod 4)
So because a non-negative integer is the sum of three squares of integers if and only if it is not of the form $4^m(8 n + 7)$, a necessary condition is that the area A is not of that form. Your conditions satisfy this, as they require odd primes of odd multiplicity to be $\equiv 1 \bmod 4$, so that the area (according to your conditions) must be of the form $4^m(4 n + 1)$.
But the three squares condition doesn't in itself rule out primes $\equiv 3 \bmod 4$ occuring to odd multiplicity, and if you try larger values perhaps some examples of this will turn up.
Edit: I just had another thought - The area would be of the form $4^m(8 n + 3)$ if and only if all the differences $x_i - x_{i+1}$, $y_i - y_{i+1}$, etc were odd. But in that case, the "orthogonality" conditions would not be satisfied, because the LHS would be the sum of three odd integers and hence odd and non-zero. So in summary, the area must be of the form $4^m(8 n + 1)$
However, that still leaves a loophole to evade your conditions: A non-negative integer is the sum of the squares of two integers if and only if it contains no prime $\equiv 3 \bmod 4$ to odd multiplicity. (Of course a square is a special case of this, with one of the two integers zero.) But the $8 n + 1$ area condition above doesn't exclude an even number of primes $\equiv 3 \bmod 4$ each occurring to odd multiplicity, which would preclude a sum of two squares form.
A: With Qiaochu's observation, one can find a general parametric solution to this problem, starting from:
$a^2 + b^2 + c^2 = d^2 + e^2 + F^2$
$a d + b e + c F = 0$
Start by forgetting about integers for now, and dividing both equations by $c^2$, and considering $a, b, d, e, F$ as rational. In other words, in effect take $c = 1$.
Then plugging $- F = a d + b e$ into the first gives a result equivalent to:
$(a^2 + 1) d^2 + 2 a b d e + (b^2 + 1) e^2 = a^2 + b^2 + 1$
Multiplying throughout by $a^2 + 1$, this can be expressed in the form:
$((a^2 + 1) d + a b e)^2 = (a^2 + 1 - e^2) (a^2 + b^2 + 1)$
Letting:
$(a^2 + 1) d + a b e = (a^2 + b^2 + 1) f$
this becomes:
$a^2 + 1 - e^2 = (a^2 + b^2 + 1) f^2$
or equivalently:
$(a^2 + 1) (1 - f^2) = e^2 + (b f)^2$
It isn't hard to prove that this implies the existence of rational $g, h$ with:
$1 - f^2 = g^2 + h^2$
whence by composition:
$e^2 + (b f)^2 = (a g + h)^2 + (a h - g)^2$
This in turn implies the existence of rational $u, v$ with:
$u^2 + v^2 = 1$
such that again by composition:
$e = u (a g + h) + v (a h - g)$
$b f = v (a g + h) - u (a h - g)$
Now $f^2 + g^2 + h^2 = 1$ has general solution:
$f = \frac{p^2 + q^2 - 1}{p^2 + q^2 + 1}$
$g = \frac{2 p}{p^2 + q^2 + 1}$
$h = \frac{2 q}{p^2 + q^2 + 1}$
and $u^2 + v^2 = 1$ of course has general solution:
$u = \frac{r^2 - 1}{r^2 + 1}$
$v = \frac{2 r}{r^2 + 1}$
So plugging these two solutions into the preceding equations for $e$ and $b f$ expresses $b$ and $e$ in terms of $a, p, q, r$.
Also plugging these two solutions, and $b$ and $e$ just obtained, into the equation (near 
the start) where $f$ was introduced, expresses $d$ in terms of $a, p, q, r$.
Finally, $F$ follows from $- F = a d + b e$.
Then simply homogenize to obtain equations giving all integer solutions.

I later realized that the above, although correct, is suboptimal.
Solving $a^2 _+ b^2 + 1 = d^2 + e^2 + (a d - b e)^2$, as we did, by expressing $b, d, e$ in terms of $a$ and parameters should require only 2 parameters instead of our 3.
This mystery can be resolved by observing that $u^2 + v^2 (= 1)$ can be absorbed by composition into $g^2 + h^2$. So with a pair of new parameters $G, H$, with $1 - f^2 = G^2 + H^2$ we can conclude:
$e = a G + H$
$b f = a H - G$
and $b, d, e, F$ can each now be expressed in terms of $a, G, H$
