Re: SHA3 implementation problem

[Taylor R Campbell <campbell+netbsd-tech-userlevel%mumble.net@localhost>]

tl;dr: I think we're in the clear with no further effort in src.


> Date: Tue, 7 Mar 2023 09:55:33 +0100
> From: Thomas Klausner <wiz%NetBSD.org@localhost>
> 
> "This paper describes a vulnerability in several implementations of
> the Secure Hash Algorithm 3 (SHA-3) that have been released by its
> designers. [...]"

https://github.com/XKCP/XKCP/issues/105
https://github.com/XKCP/XKCP/commit/fdc6fef075f4e81d6b1bc38364248975e08e340a

The flaw arises from a 32-bit integer overflow in a bounds test:

             /* normal lane: using the message queue */
             partialBlock = (unsigned int)(dataByteLen - i);
             if (partialBlock+instance->byteIOIndex > rateInBytes)
                 partialBlock = rateInBytes-instance->byteIOIndex;
             i += partialBlock;

(Certainly it's not surprising that it's the variable-input-processing
part that was exploitable; that's the most annoying part to get
right.)

> I looked for SHA 3 and keccak and found at least the following hits in
> our tree:
> 
> common/lib/libc/hash/sha3/sha3.c

I wrote this independently.  The variable-input-processing logic I
used is different and unlikely to be affected by this mistake.
Verified that it prints the correct SHA3-224 hash for 4294967296
zeroes split into a one-byte chunk and a 4294967295-byte chunk:

c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe

I confirmed this with a version of Python released since they switched
from KCP to tiny_sha3, using the fragment in the paper to reproduce a
crash for older vulnerable Python versions:

   >>> import hashlib
   >>> h = hashlib.sha3_224()
   >>> h.update(b"\x00" * 1)
   >>> h.update(b"\x00" * 4294967295)
   >>> print(h.hexdigest())
   c5bcc3bc73b5ef45e91d2d7c70b64f196fac08eee4e4acf6e6571ebe

> crypto/external/bsd/openssl/dist/crypto/evp/m_sha3.c
> crypto/external/bsd/openssl/dist/crypto/sha/asm/
> crypto/external/bsd/openssl/dist/crypto/sha/keccak1600.c
> crypto/external/bsd/openssl/dist/crypto/evp/m_sha3.c
> crypto/external/bsd/openssl.old/...

These were also written independently.  The paper notes that the
OpenSSL implementation is not vulnerable to this attack.  I did not
independently verify that it produces the correct hash for an input
split that way, mainly because reminding myself how to use the EVP API
is a pain in the arse.

> external/public-domain/sqlite/dist/shell.c

This appears to have been written independently, and kept considerably
simpler, likely at some cost in performance.  It is also impossible
for this particular bug to happen because the SHA3Update function is
limited to sizes representable in unsigned int.