You are right, Scott. I did not see the tricky knight move.
The only solution, as several has guessed, is 1 Ka3! avoiding any possible Knight forks and essentially leaving Black in zugzwang.
The immediate threat is 2 Nc7 Nf6 3 Nd5+ winning (which wouldn't have worked with the King still at b4 because Black takes with check). So then:
A) 1 ...Kc6 2 Ka2! (but not 2 Kb2? Ne5! 3 Nd6 Nc4+ or 3 Nf6 Nc4+ 4 Kc3 Nd6 followed by ...Ne8!) and again zugzwang since if 2...Kb6 3 Nc7 or 2 ...Kc5 3 Nd6 with the same threat if ...Nf6.
B) 1 ...Ka7 leaves Black stuck shuffling between a7 & b8 until White's King gets close enough for the Knight to reach, since ...Kb6 is always met by Ne8-c7. So White just heads across the 2nd rank to f2, then Kf2-g3-f4 when Black can play ...Kb6, but it is too late due to Kf5 Kc6 & finally Ne8-f6 winning.
The subtle intricacy of the plan with such scant material seems quite beautiful in its simplicity and Black's helplessness. Halberstadt won 1st prize in the 1938 competition for the magazine Gros, and well deserved!
Yeah, really nice position. Annoyingly, I think I may have got it with more time, I saw the deflection fork if only the white king wasn't checked at the end.