I was as skeptical as you are. But then I read the original article. The attackers here specify the ciphertext, and they craft a specific one for every bit they want to extract from the private key.

The ability to craft a ciphertext of ~1 second per bit makes it plausible they are able to force the difference between a 0 and a 1 to be large enough to be heard. Still surprising, but plausible.