1
$\begingroup$

I am looking for an example of handling bit messages in SHA-3. I have looked at the example for 5-bit here but when I give complete padded msg

D300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

the digest I get is very different from one in the example.

Can any one please help me with bit message padding and its correct working digest. I have tried NIST short messages but none of them are working except at message lengths which are multiple of 8 and 0 lengths.

With my code (hidden by moderator, but still viewable) I get MD = 927f4c60c3b347f2e63a7ee0885c20bd226a00e6dcfd01ef7489e2e5 instead of FFBAD5DA96BAD71789330206DC6768ECAEB1B32DCA6B3301489674AB in the standard document. Please help.

$\endgroup$
3

2 Answers 2

2
$\begingroup$

The example linked in the question computes $\operatorname{SHA3-224}(M)$ for $M$ the 5-bit bitstring $\mathtt{11001}$.

FIPS 202 section 6.1 defines

$\operatorname{SHA3-224}(M)=\operatorname{KECCAK}[448](M\mathbin\|\mathtt{01},224)$

thus it's computed $\operatorname{KECCAK}[448](\mathtt{11001}\mathbin\|\mathtt{01},224)$ that is $\operatorname{KECCAK}[448](\mathtt{1100101},224)$

FIPS 202 section 5.2 defines

$\operatorname{KECCAK}[c]=\operatorname{SPONGE}[\operatorname{KECCAK-}p[1600,24],\operatorname{pad10*1},1600-c]$

thus it's computed $\operatorname{SPONGE}[\operatorname{KECCAK-}p[1600,24],\operatorname{pad10*1},1152](\mathtt{1100101},224)$

FIPS 202 section 4 algorithm 8 defines computing $\operatorname{SPONGE}[f,\operatorname{pad},r](N,d)$ to be (with parameter $b$ equal to the bit size of the input and output of $f$)

  1. Let $P=N\mathbin\|\operatorname{pad}(r,\operatorname{len}(N))$.
  2. Let $n=\operatorname{len}(P)/r$.
  3. Let $c=b-r$.
  4. Let $P_0,\ldots,P_{n-1}$ be the unique sequence of strings of length $r$ such that $P=P_0\mathbin\|\ldots\mathbin\|P_{n-1}$.
  5. Let $S=\mathtt0^b$.
  6. For $i$ from $0$ to $n-1$, let $S=f(S\oplus(P_i\mathbin\|\mathtt0^c))$.
  7. Let $Z$ be the empty string.
  8. Let $Z=Z\mathbin\|\operatorname{Trunc}_r(S)$
  9. If $d\le|Z|$, then return $\operatorname{Trunc}_d(Z)$; else continue.
  10. Let $S=f(S)$, and continue with Step 8.

thus step 1 computes $P=\mathtt{1100101}\mathbin\|\operatorname{pad10*1}(1152,7)$.

FIPS 202 section 5.1 algorithm 9 defines computing $\operatorname{pad10*1}(x,m)$ to be

  1. Let $j=(-m-2)\bmod x$
  2. Return $P=\mathtt{1}\mathbin\|\mathtt{0}^j\mathbin\|\mathtt{1}$

thus said $P=\mathtt{1100101}\mathbin\|\mathtt{1}\mathbin\|\mathtt{0}^j\mathbin\|\mathtt{1}$ with $j=1152-7-2$, that is $P=\mathtt{11001011\underbrace{000000\ldots000}_{1143\;\mathrm{ bits}}1}$.

Now if we keep on Algorithm 8, we have $n=1$, $c=1600-1152=448$, $P_0=P$, $S=\mathtt0^{1600}$ at step 5. So that at the first (and only) evaluation of $f$ at step 6, the input is $\mathtt{11001011\underbrace{000000\ldots000}_{1143\;\mathrm{ bits}}1\underbrace{000000\ldots000}_{448\;\mathrm{ bits}}}$ or, if we make byte boundaries explicit $$\mathtt{11001011\,\underbrace{00000000\,00000000\ldots00000000}_{142\;\mathrm{ bytes}}\,00000001\,\underbrace{00000000\,00000000\ldots00000000}_{56\;\mathrm{ bytes}}}$$ At the first (and only) execution of step 8, $Z$ is the first $1152$ bits of the output of $f$, and at step 9 the results is the first $224$ bits of that.


If we assemble the bits into bytes per the little-endian convention and express each byte in big-endian hexadecimal (per FIPS 202 appendix B.1 Algorithm 11), we get that $\operatorname{SHA3-224}(M)$ for $M$ the 5-bit bitstring $\mathtt{11001}$ is the first $28$ bytes of the ($200$-byte) output of $\operatorname{KECCAK-}p[1600,24]$ for input the ($200$-byte) bytestring $\mathtt{D3\,\underbrace{00\,00\ldots00}_{142\;\mathrm{ bytes}}\,80\,\underbrace{00\,00\ldots00}_{56\;\mathrm{ bytes}}}$. This input matches the "complete padded msg" in the question and it's reference.

Computing $\operatorname{KECCAK-}p[1600,24]$ is just as in standard $\operatorname{SHA3}$. However implementations of $\operatorname{SHA3}$ and $\operatorname{SHAKE}$ usually do not give access to this function, much less support bit-sized messages. Adding that capability requires messing up with the internals of a library. I don't see how that could be done cleanly on top of OpenSSL libraries, as attempted by the question's code.


I wrote code (source that can be run online) for SHA3-224, SHA3-256, SHA3-384 and SHA3-512, with bit-sized message support. Here is the interface:

// Compute SHA3-<ol>, return 0 iff OK, 1 iff parameter error
// Supports message size in bit (if il%8!=0, only the low il%8 bits of the last byte are hashed)
int sha3(
    uint8_t* op, int ol,            // output, and it's length in bits among 224, 256, 384, 512
    const uint8_t* ip, int64_t il   // input, and it's length in bits
)

The single function is ~90 lines of portable C code, half of which for the Keccak permutation. It's optimized for concision, except a permutation round is unrolled to keep it fast. There's test code for 7 example messages for each of the 4 hashes, including the messages linked in the question, similar messages by NIST, and the message in comment in the question's code. Results match the 25 Known Answer Tests in these NIST references and the question.

$\endgroup$
5
  • 1
    $\begingroup$ One reason to create a bit oriented implementation is to validate the algorithm. I did this for Skein (SkeinFromSpec) where I detected a mistake with regard to the endianness (somebody beat me to it by reporting it while I was validating my design, but I was able to send out the test vectors to the Skein team when they were double checking their updated code). Quite often the algorithms only supply an optimized version, which is pretty hard to understand and thus validate using the theoretical spec. $\endgroup$
    – Maarten Bodewes
    Jan 2 at 18:05
  • $\begingroup$ So, you went full answer, tough hard to read for all, however, kudos.. $\endgroup$
    – kelalaka
    Jan 2 at 23:04
  • $\begingroup$ Thank all for your valuable comments I have modified my question which includes my implementation test code. please review the question and help me to get the expected digest value. $\endgroup$ Jan 3 at 11:42
  • $\begingroup$ @Umadevi Palathur : Again, in my opinion, using OpenSSL libraries is a dead end for what you attempt, because OpenSSL neither gives access to the KECCAK function, nor has support for bit-sized message. It's much easier to write SHA3 from scratch, with bit-sized message support. See updated answer. $\endgroup$
    – fgrieu
    Jan 3 at 22:07
  • $\begingroup$ Further discussion best takes place in chat. $\endgroup$
    – fgrieu
    Jan 23 at 10:37
1
$\begingroup$

I'll give a treatment on the pitfalls of implementing bit-oriented mode cryptographic algorithms, the fix for your problem will be left as an exercise for you.

In today's world, we almost always work with 8-bit bytes (a.k.a. octets). The biggest reason for this in my opinion, is because almost all networking protocols have been defined in terms of octets historically, thus in order to achieve interoperability with each other, almost all systems are octet-oriented.

Being byte/octet-oriented means that, all data must be encoded as a sequence of bytes; then, when encoding bits into bytes, we must specify whether it's most-significant bit first, or least-significant bit first. OpenSSL, being a software for communicating in SSL/TLS protocol, it has no provision for bit-oriented systems in its crypto library.

SHA-3 and most algorithms specified by NIST are align on octet boundaries - they preferentially cater to needs of octet-oriented systems. The only reason they're specified in terms of bits, is to cater to the very few systems that're not octet oriented, such as 7-bit, 9-bit, and 12-bit systems that're increasingly rare.

Some other facts for you to consider:

  • There's an April fools' RFC specifying Unicode Transformation Format for 9-bit systems that's apparently a joke.

  • The current POSIX and Single Unix Specification specifies the CHAR_BIT limit for bits in a byte as exactly 8.

TL;DR

Bit-oriented implementation are only useful for systems where bytes are not exactly 8 bits and when bit order is defined (i.e. msb/lsb).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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