Confusion regarding SABER specification
244 views
Skip to first unread message
Kevin Pretterhofer
Jul 23, 2021, 5:18:12 AM7/23/21
to pqc-forum
Hi everyone,
I hope this is the right place to post this.
I am an IT-sec student, and I was implementing the SABER-KEM. I have used the respective specification, as well as the reference implementation as some sort of guidance. Throughout the process I came across several things which I think made the process of implementing SABER a bit confusing (or at some parts hard to understand). I already opened an issue at the SABER repo, but I think that its probably not maintained, so I will try it here:
---
-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.
-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.
-In general you 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 (Saber.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).
-Furthermore I have noticed, that in the specification, also in algorithm 21 (Saber.KEM.Decaps for recovering session key from ciphertext) in line 8 you are computing the r' as the hash of ciphertext' (which is the recomputed ciphertext). In the reference implementation however, you are using the original ciphertext for that hash. Of course if the recomputed ciphertext is the same as the initial one, there is no difference in this but if someone tampered with the initial ciphertext the results are different.
---
The first two points are probably trivial since obviously one has to do the conversions in order to perform the respective operations, but I think point 3 is probably a mistake in the
specification, and regarding point 4 I am not sure whether the way it is in the ref implementation or the way it is in the specification is correct.
I hope someone of the SABER team can shine some light on this.
Thanks in advance and
all the best,
Kevin
I hope this is the right place to post this.
I am an IT-sec student, and I was implementing the SABER-KEM. I have used the respective specification, as well as the reference implementation as some sort of guidance. Throughout the process I came across several things which I think made the process of implementing SABER a bit confusing (or at some parts hard to understand). I already opened an issue at the SABER repo, but I think that its probably not maintained, so I will try it here:
---
-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.
-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.
-In general you 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 (Saber.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).
-Furthermore I have noticed, that in the specification, also in algorithm 21 (Saber.KEM.Decaps for recovering session key from ciphertext) in line 8 you are computing the r' as the hash of ciphertext' (which is the recomputed ciphertext). In the reference implementation however, you are using the original ciphertext for that hash. Of course if the recomputed ciphertext is the same as the initial one, there is no difference in this but if someone tampered with the initial ciphertext the results are different.
---
The first two points are probably trivial since obviously one has to do the conversions in order to perform the respective operations, but I think point 3 is probably a mistake in the
specification, and regarding point 4 I am not sure whether the way it is in the ref implementation or the way it is in the specification is correct.
I hope someone of the SABER team can shine some light on this.
Thanks in advance and
all the best,
Kevin
Fre
Oct 13, 2021, 11:02:12 AM10/13/21
to Kevin Pretterhofer, pqc-forum
Dear Kevin
Thank you for pointing out the differences between the pseudo-code in the submission document and the reference code. The reference code acts as the definite specification of Saber, but as you indicate, there were some data type conversions. e.g from bit strings to polynomials, missing.
We have now updated the specification document to include these fixes. You can find it on our website: https://www.esat.kuleuven.be/cosic/pqcrypto/saber/
Thanks again for your contributions to making the specification clearer.
Best regards
Saber team
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/8aed5b08-c114-4ece-a903-3f8e53c58e42n%40list.nist.gov.
Reply all
Reply to author
Forward
0 new messages