0
$\begingroup$

tl;dr What does "d <= |Z|" mean in the context of bit array manipulations?

As a learning exercise I'm working on an implementation of SHA-3. I am not a cryptography specialist in any way but I have implemented similar algorithms in the past such as MD5 and SHA1, so I am roughly conversant with the kinds of operations that happen in such algorithms.

I have been working through the document "FIPS PUB 202" (freely available as a PDF here: http://dx.doi.org/10.6028/NIST.FIPS.202).

I am finding this a hard document to understand but I'm getting near to completing the program and I'm unsure about the meaning of the following line of text in section 4, algorithm 8 (page 19) the SPONGE function...

enter image description here My problem is with step 9. I do not understand what "|Z|" means in this context.

This algorithm deals with truncating and concatenating an array Z of bits (which could be several hundred bits long) until this condition is met at which point the first "d" bits of Z is returned to the calling function.

  • My first thought was that |Z| means "the length of Z in bits", but that would be inconsistent -- they are using "len(...)" for that purpose in steps 1 and 2 (and elsewhere in the document). This is the only place in the document where this "|...|" notation is used.
  • I don't think it would mean "Abs(Z)" in the mathematical sense of converting Z to a positive value because the resulting number would be extremely large in almost all cases. Converting Z (effectively a list of random bits) into an integer seems pointless and arbitrary.
  • The "|...|" syntax is not mentioned in the glossary section. ("a || b" is mentioned but that's for array concatenation, which this is definitely not).
  • I was also a bit puzzled by the use of "<=" in this condition. Why bother to truncate if the length is equal, just return it as it is? Further suggestion that it doesn't mean "length of Z".

So, how should I understand this slightly weird bit of text? I doubt it's a mistake in the document because it's such an important algorithm and will have been stringently vetted by thousands of people much smarter than me.

|improve this question
$\endgroup$
  • $\begingroup$ I think it does mean the string length. It’s a common notation for it. If we’d have $=$ the Trunc function does nothing. $\endgroup$ – Henno Brandsma Oct 2 at 17:33
2
$\begingroup$

It means the length of $Z$ in bits; in other words, squeeze out consecutive $r$-bit blocks from the sponge until you have a $d$-bit string, truncating the last block if necessary.

I expect you may overestimate the number of people who proofread this document with an eye for details like that. Most cryptographers studying it will have read the Keccak reference, which uses slightly different notation meaning the same thing; most implementors will likely correctly guess that $|Z|$ and $\operatorname{len}(Z)$ mean the same thing when $Z$ is a bit string, or compare to another reference to confirm.

|improve this answer
$\endgroup$
  • $\begingroup$ I see, thank you. I'm glad I don't have to do this kind of implementation for a living. It would be interesting to know how much scrutiny such a document undergoes before it's publication. I only spotted this because my program doesn't work properly and I'm trying to iron out the bugs :) Cheers. $\endgroup$ – Wossname Oct 2 at 17:47
  • $\begingroup$ What I hear on the grapevine is that the technology NIST uses for collaborative editing of their standards is emailing Word documents around. I would love to hear a less miserable story than that, but I haven't yet. The only other story I vaguely recall hearing—but I can't dig up a reference now, so it may have been apocryphal and/or a joke and/or something I hallucinated on my own—is that they have a LaTeX template to imitate the bad typographical style of those Word documents. $\endgroup$ – Squeamish Ossifrage Oct 2 at 17:54
  • $\begingroup$ That is quite depressing, although I like the idea of LaTeX as a tool for creating documents with clarity and conciseness, it is rather esoteric and probably not in the metier of your average civil servant. I won't bother submitting a document change request because my days of shouting into hurricanes are behind me :) $\endgroup$ – Wossname Oct 2 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.