Practical Cryptography Corrected

The coding challenge implicitly asks for a brute-force search based solution?

It also seems to assume that it's a straight line or at least a one-dimensional space - a curve is certainly a line. If it's not a straight line, then there isn't sufficient information to solve the problem in two dimensions.

Overall, this problem sounds an awful lot like a variant of the 8 Queens puzzle.

For an RSA modulus, you should always use 2.

I don't think you mean modulus here.

You should always do encryption as a layer outside of authentication.

Strongly disagree.

Authenticate-then-encrypt (AtE) is subject to attacks that encrypt-then-authenticate (EtA) is not. How practical those attacks are depend on exactly what you're using for your encryption, but they can occur surprisingly often, and you don't want to have to worry about them.

The most prevalent class of such attack (in my opinion) is when you've got a (possibly public-key) encryption system that isn't reaction resistant. The encryption might be somewhat homomorphic, in that the adversary can modify the ciphertext in such a way as to make it come out to the same plaintext some of the time, and a different plaintext (or \bottom) some of the time. Then the inner authentication will fail, and the adversary will know which happened. Lattice-based crypto often has this problem, as does McElice (see our 1999 paper on this). Other encryption systems may have this or similar problems, as protecting against this isn't generally something that's a design goal of semantically secure encryption. (If your encryption is IND-CCA2, you're safe, but then you've basically got the authentication built in, anyway.)

Authenticating the ciphertext avoids the whole issue.

Of course, it may have its own issues, if you're using signatures (and not MACs) for authentication, and you want, say, to hide the information of who's signing the message. If you have complex requirements like that, though, you might think twice about designing the crypto protocol yourself.

I certainly agree that Practical Cryptography feels outdated, and readers should be warned about the problematic parts. Here are a few thoughts and questions from a theoretical crypto POV:

For an encryption mode, you should always use CTR, and always use a nonce of zero, and never reuse keys.

I'm interested to hear more about why this is true. Certainly there are times when you want to reuse keys and use modes that provide more security than that :-).

You should always do encryption as a layer outside of authentication.

It sounds like you are suggesting the opposite of what you should do, which is encrypt first, and then authenticate the ciphertext. Authenticating the plaintext before encrypting is not safe.

For an RSA exponent, you should always use 2. Technically that's Rabin-Williams, and requires slightly different implementation, but that actually works in its favor. Rabin-Williams has a reduction to factoring, RSA does not.

I think suggesting that practitioners dig into implementations of the number-theoretic algorithms (as would be necessary here) is likely to lead to exploitable bugs. Moreover, even a proper implementation of Rabin-Williams would not increase security in practice, unless the sky falls and we find algorithms for inverting the RSA trapdoor function that do something other than factoring. And what's worse is that in practice you'll be using a padding scheme like PKCS#1v1.5, which means the reduction no longer applies. Even if you used OAEP instead, the reduction would be in the random oracle model, further clouding the significance of a reduction to factoring vs RSA inversion.

This is all ignoring the fact that low-exponent (e=3) RSA has lead to vulnerabilities in the past...

You should never use the same key for both encryption and authentication. If you need both encryption and authentication, you should use two keys. One for encryption, and one for authentication.

This is good advice, unless you're using an authenticated encryption mode like GCM. It would be good to be more complete on when it applies.

Interestingly, I just came across this article from 2 years ago --

http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html

Seems somewhat similar at times to what you wrote. Interesting how the recommendations then are still pretty much the same you made above, now.

I would directly recommend an AEAD mode like GCM rather than even mentioning CTR mode.

The CTR nonce MUST be random. It cannot be the same value, or zero as you have suggested. Doing so leads to chosen-plaintext attacks.

Authentication should be done after encryption because this is the way that can be proved to work for any encryption and authentication schemes.