Specification / Implementation mismatches?

[kevPretterhofer]

Hi,

I have implemented SABER by myself with the respective round3-specification and the reference implementation as some kind of guidance.
I have noticed one or two things which I want to share with you:
First and foremost I don't think that those discrepancies I have found affect the security in any way, however I think they can be a bit confusing when implementing the algorithm solely with the specification. I don't want to rule out that those mismatches aren't even any, and its just a lack of understanding on my side.

1. In algorithm 18 (Saber.PKE.Enc for IND-CPA encryption) in line 9, you are applying a SHIFTLEFT on the message m which is a 256-bit string. However the SHIFTLEFT is explicitly described to get a polynomial as input, and each coefficient is shifted. What I am missing is something like a BS2POLVEC_2 applied on the message m beforehand (and then probably some kind of notion that the coefficients should be interpreted as elements of Z_p I guess?). This conversion happens in the reference implementation, but is not mentioned in the specification.
2. Similar to this, in algorithm 19 (Saber.PKE.Dec for IND-CPA decryption) in line 3 respectively line 4, you are applying a SHIFTLEFT on the byte string C_m, which would need to be converted with BS2POLVEC_t I guess, however this conversion is not mentioned in the specification.
3. The last thing I have noticed is, that in general you sometimes interpret a byte string e.g. bs = (bs1 || bs0), as a concatenation of two byte strings, where bs0 relates to the LSBs and bs1 to the MSBs. Consequently, assuming that |bs1| = |bs0| = 32 bytes, that would mean that |bs| = 64 bytes, and therefore bs[i] with i in [0, 31] would index bytes in bs0, and bs[i] with i in [32, 63] would index bytes in bs1. This is done throughout the whole reference implementation except for one part: In algorithm 21 (S_aber.KEM.Decaps for recovering session key from ciphertext_), depending whether the re-encryption fails or not you are setting temp = (k || r') or temp = (z || r') in the specification. However in the reference implementation you are setting temp = (r' || k) or temp = (r' || z) instead (happening in the cmov function). The way it is done in the reference implementation obviously makes sense, since this way you get the same session key as in the Encaps algorithm, but it diverges from the specification (where the ordering of k and r is wrong I'd say).

Again, I don't think that those things have impact on the security itself, it was just somehow confusing when implementing the algorithms. Maybe my observations are wrong and I just have overseen something (or did not understand something right), but I just wanted to inform you about that.

Kind regards

Edit:
Also just found a typo as well: Algorithm 18 states INC-CCA instead of IND-CCA :)