Kyber-768: differing shared secrets after decapsulation between bc and liboqs

[Chratho]

Hi,

I currently try to perform a KEM key derivation using Kyber-768. The client is written in C with liboqs [1] and the server uses Java/Kotlin with bc. However, the derived shared secrets between both applications do not match.

I have used the Kyber reference implementation [2] to generate a set of hex-dumps (notably the sk and ct as required for the last decapsulation round plus the resulting secret). Based on these dumps, I was able to derive the same secret using liboqs, but not with bc.

The following code should make the issue clear. Am I doing something wrong when performing the decapsulation using bc?

import java.security.Security
import kotlin.test.assertContentEquals
import kotlin.test.assertEquals
import kotlin.test.assertFalse
import org.bouncycastle.asn1.ASN1ObjectIdentifier
import org.bouncycastle.asn1.DEROctetString
import org.bouncycastle.asn1.pkcs.PrivateKeyInfo
import org.bouncycastle.asn1.x509.AlgorithmIdentifier
import org.bouncycastle.jce.provider.BouncyCastleProvider
import org.bouncycastle.openssl.jcajce.JcaPEMKeyConverter
import org.bouncycastle.pqc.crypto.crystals.kyber.KyberKEMExtractor
import org.bouncycastle.pqc.crypto.crystals.kyber.KyberPrivateKeyParameters
import org.bouncycastle.pqc.crypto.util.PrivateKeyFactory
import org.bouncycastle.pqc.jcajce.interfaces.KyberPrivateKey
import org.bouncycastle.pqc.jcajce.provider.BouncyCastlePQCProvider
import org.bouncycastle.util.encoders.Hex
import org.junit.jupiter.api.Test
import org.openquantumsafe.KeyEncapsulation

class DecapsulateTest {
    private val KYBER_768_OID = "1.3.6.1.4.1.22554.5.6.2"

    init {
        Security.removeProvider("BC")
        Security.insertProviderAt(BouncyCastleProvider(), 1)
        if (Security.getProvider("BCPQC") == null) {
            Security.addProvider(BouncyCastlePQCProvider())
        }
    }

    @Test
    fun testDecapsulate() {
        // hex-dumps generated by https://github.com/pq-crystals/kyber.git
        val pk = Hex.decode("7e647dcfc4b4eea168d58ac2fda24e27a60b9993b4ce95062e211c9a71250c460ea7a34d46d97375a703a0428e413cc5de7a6d777507c2e6a08b543193d520556b52fd8a13bc12281128533c831d7d765f745796dc49bcb8f26077287517a4858f34a0a56195e7cc4d4e14bbb674c4b9d5b225e14d4dc43f6935132d973f633c0c22fc21544113b58122a9e3899871b8f2b4668099c69e23672136b263f721f786551c724568146cfb833d10f10baee49332757f0be0a1db96495fb32e04814e5b091c1fa5b0992765780c8e731356e2aa1ccd24a13a8895b8250c5260200a70800c3aca4297124125235f4869dcecb3f4f5bbf6197299a356fefcca65f443487b0fcd945033323362a9b13ecc06cf982a07a7bcb3a63dec500dccc361dafb5606144f7a5a8c5847ba7c86bba4c367ee088fd2d5595032cee8c655bc02b4cf64b817b54ec207a204a9069d6b21411858dc21a64aa83d91d58e8b0389b95196392865c8438db0671d669356a455569d92bda290ccbbf1c0c0cc1133c01085a96ebcd04d7dc3467aa278dda62df74458cea8510a092586f5cf462c4aa6425cc9e3cac62085d5d45dad2a4cc447abdef010c2b7b6a948a6ef760b11f067e91747ec6694173509f16c82625a7c118675acea7ee32503bce80f3c036ab1fa190071c80f3b13e676ab018b4c3ef0b7d03b1d8d719134b0c0ad978ccff8b854217e41567c80197dec765fb7a228f97b3587d4ad8302a34eb7020ac40f41cbb6ecc10dcf8221bc5c0f2ceba9a1d5768c4c45b18acfa9e22a652a85e019be3da5504f312452514d33f2764c9a90d4219e5746a2e3966868ba24c656125289ae4b8068d7a4c479f3a34d4b952f853bc8a5210e83672c061248792b518687d9fbc4c8c5ceb1db6ecee725969688d9e07a668481d288076d453aab87a37d6cc1e22771f2a6be7e48bd07103f4c9bb6b692181d406d74546fc8d89381c09c09e52f6360bf853481db187a9312058f448dc1265d45ac8c06c58e7147b18fd5593952178077051ac864b7db9bf356bb92bb9d67e36555ecb0876544bf068eab11cd8a3bc8fe30c6708b9c3a872425e488680a75152c8717e5bd3901a298e20491857b1bf09148d22571fcbf94d47089816126e82aa0b56b238ba09403450d01360e368ec651833f4b2653648a95e84bb038a0ac1b7da936c7ee901d81a5c8a29a2080fb6240ecc1c1983e70d757e7c71198f50fa5cabd6ff17592cb318000a11b22b167aabb5a7165d37a8c0126853a023d06ac3b1ea03542786668c7570a9cb9c821578cc235fc8249b0c476476429da4aa067c5bd629c432fc33514f67edaf31d5bc65b1958134dbcc98a44bf428146aeb7ac142849cb66576b896e0dcb5c25eb3f38d038d83261b2d826ab33bf0e652c84c013ccc9642cc47d5881be46a547666799b96b02f25abf896390147b9a5bd9643f3623c0dc5e4c4862452862a8762f5342a86c1c5af8f89c55cb177018737259cdf1a67c36343801f6b98da35f45a402a3d41fb9a43684096edacc8fcdcc0a93443fc94c594aa3aa6982622e4abba42a4fed41219134455c654e209c35c8729d82402f58b9523568a4fe871495b61b3dcb47f6684094a433424347ce4668fdcb7065efa8af8254f0516b0928c484115bb912d28dc6")
        assertEquals(1184, pk.size)
        val sk = Hex.decode("342034f3599f8e9c3abfe25dad40848f7c5c1c78cc282062e2a20450643ec390b2ab2b42459a25b169c5fc5bc70b727b4ea6cc3f11583120503a19a8d56b6f011a6b014c51152207b32b0ee3d652078a0197cb4556a4233c2900ff104018e8caf2699c6eac92169792d2c5b0323b258309c963357836c0957845580c556320ab2bc48a34810411599b74a17128e6f3cc9563004f109701cc8cdde59945529242174720d45a399c47f732bbe83cc5f4494b5b854db0e6824a7000ceaa48f713ad907c6f34b9c5c5f8ad5afa3dd898b8cfacbce5e64603a2cfda276f2606327223b1c259b30bdc9bdb2524078291059a45c7f71cbff80ab8472a36f84f469c358be336ff1c261d51a1c453afdc2c4e6783a839687702f2b105ab47b7a06172608e15584750021d1e898cb6e29c11b144a32c5974f27e1455a1e2e22fe4b64efec62ddb9c402c025eb4cbcbea215dec684fca5480308519b5c0758df125c9b0b46fec06e27c4c29b24f7d03229339c85a0126cc6b8d6e47cfebdc3ec81a53fa397b21c353836c8952e81e4423c3fa10a7a2b4335b4c2bc616c2b2e78ab3c5ac729cb369b13e5aea783bb3bfa14796fe3074d563626476479a246f677b84ce2798b584ca6a492c13d9b8558bc2361b591e4122befb8d1cf3a5cbdc9fb681194786c4b0362b831a139c8c1427d9c14b443cdbc52af1d2b0c1114960f04f6de276d49994e3347f85b78243a44e1faa83663411f388514ac4a7465b8d6d07a22789cfa1aa6e916a859d75b8f602511d3c6275134126a20707b0921f8878e67328b26c51a4b8c52304c9d4d90c88c33ccfba8147205b06db9d83b87f962b5e1ae9308d8b7029a87c17f3447f33c4a72aa69307c05e88bd51b2328d9c854c13a8aaf121bb075153723d0f4c9531d7c2732a9e9a021c0177542fd0637c1088be46a533561cbc7a37ec1b7c6495919b642f11820c207b0a93915a253a13d203740ad0cf0f74b8cf100ac13c6763034e6cd16fe5b334a97a0308291a1b0a84c383334fba7728623b3ccc9cf00c6c91f2563872365ad21a930a1a2aa8561e291674a2145b3662ce6725a08b2838bc58ef585622933b91d613beb16d7a5139fc4b3322c66c0498035be05ae3e83591fa79ba267b6443114ac61dd7ac698ce183728144e53bcf96a11df93129e075a87a4493bef27afcf6b1b144a6da6ab6e6f67005020d632b0bbcd1b6b52c214e890ac30845056370a10bb7b24c5ac4284ba6812dd0b49066d8088be6b3fd808ece40751d3a05503222d4d2a9d1c8bdcb27063115c715f0928e117b7b0476b2d9042ccc7098114694caa171313fb1e4c3d8c70ea91450c8d96f9c551668078a5b849335c26dc451a9a9d09e5c4c6e91d00494aa14f7875a39d13600f57d1bf407f8a6ac4f15a93b5a2a84893966f4c7382903e237390eb669aee720470bb8e2569ab7b70d0d23558f51a493965c5b397656667567620c901465f8d6acd2c64902f75c43b64cd18c516610bb24690b60a6341759293a51b6ff468b7dd5c05d0c801bc13e962396b43c63f9e2079f028b25420f70c2866d0b5036620deb8c8432773b98a8447075b07d4aa7b1642634aa0a78c14cb258391dd1797e647dcfc4b4eea168d58ac2fda24e27a60b9993b4ce95062e211c9a71250c460ea7a34d46d97375a703a0428e413cc5de7a6d777507c2e6a08b543193d520556b52fd8a13bc12281128533c831d7d765f745796dc49bcb8f26077287517a4858f34a0a56195e7cc4d4e14bbb674c4b9d5b225e14d4dc43f6935132d973f633c0c22fc21544113b58122a9e3899871b8f2b4668099c69e23672136b263f721f786551c724568146cfb833d10f10baee49332757f0be0a1db96495fb32e04814e5b091c1fa5b0992765780c8e731356e2aa1ccd24a13a8895b8250c5260200a70800c3aca4297124125235f4869dcecb3f4f5bbf6197299a356fefcca65f443487b0fcd945033323362a9b13ecc06cf982a07a7bcb3a63dec500dccc361dafb5606144f7a5a8c5847ba7c86bba4c367ee088fd2d5595032cee8c655bc02b4cf64b817b54ec207a204a9069d6b21411858dc21a64aa83d91d58e8b0389b95196392865c8438db0671d669356a455569d92bda290ccbbf1c0c0cc1133c01085a96ebcd04d7dc3467aa278dda62df74458cea8510a092586f5cf462c4aa6425cc9e3cac62085d5d45dad2a4cc447abdef010c2b7b6a948a6ef760b11f067e91747ec6694173509f16c82625a7c118675acea7ee32503bce80f3c036ab1fa190071c80f3b13e676ab018b4c3ef0b7d03b1d8d719134b0c0ad978ccff8b854217e41567c80197dec765fb7a228f97b3587d4ad8302a34eb7020ac40f41cbb6ecc10dcf8221bc5c0f2ceba9a1d5768c4c45b18acfa9e22a652a85e019be3da5504f312452514d33f2764c9a90d4219e5746a2e3966868ba24c656125289ae4b8068d7a4c479f3a34d4b952f853bc8a5210e83672c061248792b518687d9fbc4c8c5ceb1db6ecee725969688d9e07a668481d288076d453aab87a37d6cc1e22771f2a6be7e48bd07103f4c9bb6b692181d406d74546fc8d89381c09c09e52f6360bf853481db187a9312058f448dc1265d45ac8c06c58e7147b18fd5593952178077051ac864b7db9bf356bb92bb9d67e36555ecb0876544bf068eab11cd8a3bc8fe30c6708b9c3a872425e488680a75152c8717e5bd3901a298e20491857b1bf09148d22571fcbf94d47089816126e82aa0b56b238ba09403450d01360e368ec651833f4b2653648a95e84bb038a0ac1b7da936c7ee901d81a5c8a29a2080fb6240ecc1c1983e70d757e7c71198f50fa5cabd6ff17592cb318000a11b22b167aabb5a7165d37a8c0126853a023d06ac3b1ea03542786668c7570a9cb9c821578cc235fc8249b0c476476429da4aa067c5bd629c432fc33514f67edaf31d5bc65b1958134dbcc98a44bf428146aeb7ac142849cb66576b896e0dcb5c25eb3f38d038d83261b2d826ab33bf0e652c84c013ccc9642cc47d5881be46a547666799b96b02f25abf896390147b9a5bd9643f3623c0dc5e4c4862452862a8762f5342a86c1c5af8f89c55cb177018737259cdf1a67c36343801f6b98da35f45a402a3d41fb9a43684096edacc8fcdcc0a93443fc94c594aa3aa6982622e4abba42a4fed41219134455c654e209c35c8729d82402f58b9523568a4fe871495b61b3dcb47f6684094a433424347ce4668fdcb7065efa8af8254f0516b0928c484115bb912d28dc63bde3cccde88d7f12c0ae632569264d086b3be055395b448fe2168a2c25622e7431e078cb4d48ecb02c987677f081a3b306a2ea1fa92ceb985ddb247803018cd")
        assertEquals(2400, sk.size)
        val ct = Hex.decode("78b52bba56c4a63238cd787d88a74e9690363778ceb8001430d7b47209c4e225528a4632246a3b26e354d67df77b6b8f2bc1722e05eb5a9b0187c13b633e449b3cf38a3b33792a051ff4c12771699b5b3bffc6b72789bdd395628f56a33b3c16650edfcca50f4c9a2cf3c1e30d8f2b6a8c4c34b4cdc5dbb01b03f50671bc173fd650e9fb18c93050f66475386d4d3e2f0ceb7e9b6096115a8082b6825d280e40c3335fe38854be25b87556a37bf87e25715e504b099ebd03d121ea6f8ae1e0492f5b5a90e882e0a9facf9879b9e5e6b726a4b96790e5d5a161a62e434a127e4805c2a63e6f05fc80f2ab444f5373f508f338168c71123db04b6e70462fcaca558ab5bfedaea7f78c5127b5b68d06f22358aa2fb1daded5701abee1c799a7a62c1a7431a09357dfdd3ef144087161002d0ce6528afbbe5ff559ffc7a3a4e0a9c4d455841d3645f5756ea6f417cf970450a943030540402b27ce2a2998906116ad100c2069d7ae32e3208c91831f9d67dd16f084351718a0fc80254671f8f3c0a0e8c787b5b1991997868d73b313b7127da6f951d3d6f6c9ce2172787794816f68c62dca0d502a3aba19cf4fa340a16f7f6de7da8e9f4bf4d162281aaa0729b8a35cae0e17d5babeffc0a1db8713ee8a631429efcf7d353f6ec13beb4fd649b61bffb22c7755686407f85677b06b952f439c380ea1a471fd395222772ccad800883b9124a1673a4137b902a4f2d19dfb1798615815851942fb8263446244e2611dddb0e8c38d5dc87974cabea25a29ad4fec25177fece3aef6b528c90e8b94842d7cd54038a75f8a2dbeda7b1a6fe0424499b4fd358cd2adfd7534519c2f8de1cfcfac043ebf88927290b9db87370a01872988f78b408245af12edd346fe82924d14a1501e5681a232c993ccd1e1329784a22c39e3ccff9df706a6c7c44ed687493fb5b50591dec7bed40d405fec726b9de8fe9d9e344275ea440b18ead819e7e30322b86eb930c5240ec0eef4db95a00347e4ebacea337508287daa1fa3f1692cdd4dac0dd047377809d66cd78dbf0179c36940c549cc37f23f7c2564f94d33b857bdab6bf2ae28200c37d45af2f69c92bc082af97b128989307070ce18b6b51a832f676f95718482169ce30e4d38994ae6b777c5eb0bcfe1239d5c64856d43fe5e8f2f8743b9a3d25f5c62ac5b4f4fde828d1c1746f47c4c3fd611b829567ca4071fe85c3f7ab8cc3ac9761f457cc2599916686c4a6c29ebca7e5a0b59cfb23ce0abedb9366da583221d0b00a51660915a96956c7505e194b7ed1ae43b1e05406073fdf15d9547abd98e34a0a4bbced1b6f7ec7b7c859ca137bebfdfbe0ab5eee22a80ac1e040f7936f695efd7b8899f389863c5372c2b2047674ffcaafaff28d484155f1369d8ba5b8eed7ab6712b2e5010ed12b71d9025e5dc6362a0eb82b77858462ca3aed154e990aa7df76ff95b7836b1b7b27387353a0c4585886ea4f3691e5bae19e35d3d9d6c73923ac66a3e58f1617884aa4e09d67f59f862490cd8")
        assertEquals(1088, ct.size)
        val referenceKey = Hex.decode("f0e1c49c40b3b2b6c3a6e50c286ee441c22342fb2cb2ebbdb8789aa9bad1d922")
        assertEquals(32, referenceKey.size)

        // verify liboqs-java derives the same secret
        assertContentEquals(referenceKey, KeyEncapsulation("Kyber768", sk).decap_secret(ct))

        // show bc derives something else
        assertFalse {
            referenceKey contentEquals bcDecapsulate(sk, ct)
        }
    }

    private fun bcDecapsulate(
        sk: ByteArray,
        ct: ByteArray,
    ): ByteArray {
        return KyberKEMExtractor(
            PrivateKeyFactory.createKey(readPqcPrivateKey(sk).encoded) as KyberPrivateKeyParameters
        ).extractSecret(
            ct
        )
    }

    /**
     * expects the pure private key data with 2400 bytes
     */
    private fun readPqcPrivateKey(pqcPrivateKey: ByteArray): KyberPrivateKey {
        return JcaPEMKeyConverter().getPrivateKey(
            PrivateKeyInfo(
                AlgorithmIdentifier(ASN1ObjectIdentifier(KYBER_768_OID)),
                DEROctetString(pqcPrivateKey)
            )
        ) as KyberPrivateKey
    }
}

[1] https://github.com/open-quantum-safe/liboqs
[2] https://github.com/pq-crystals/kyber/

[cipherboy]

@Chratho Bouncy Castle currently implements Kyber as specified in the NIST FIPS 203 draft, whereas OQS implements Kyber as specified in the earlier round three submission to NIST. NIST has made some changes to Kyber which has resulted in changing the output of the algorithm before standardizing it (perhaps it is now best called ML-KEM), though note that FIPS 203 is still in draft stage.

Particularly:

If you open the FIPS 203 draft and go to Section 6.2 ML-KEM Encapsulation, Algorithm 16, on page 30, and compare this with Section 1.3 Specification of Kyber.CCAKEM, Algorithm 8, on page 10, from the file Kyber-Round3/NIST-PQ-Submission-Kyber-20201001/Supporting_Documentation/kyber.pdf in kyber-submission-nist-round3.zip, you see:

versus

Note that NIST has removed the additional hash ("Do not send output of system RNG" -- doesn't impact output) and the additional KDF invocation (which does impact the output and ability to interoperate with older specs). BouncyCastle has updated to match NIST's changes as of c8eb894, but no similar commit has been made to OQS or their upstream reference implementation (in pq-crystals/kyber).

Presumably when the ink is dry on the final version of FIPS 203, we might be in sync again. :-)

Ah, here we are: open-quantum-safe/liboqs#1521 -- looks like they're working on it! :-)

HTH!

[Chratho]

Wow, thank you very much for this detailed explanation - I wasn't aware of these differences.

Is there any known schedule of when FIPS 203 will become final? Or can you make an educated guess?

Can I somehome force bc to use the round 3 submission version of Kyber? At least I think I won't be able to simply downgrade bc to some specific version, right? Because I think I've seen shared secrets of unexpected length in 1.76.

[cipherboy]

This recent blog article by Filippo might be insightful: https://words.filippo.io/dispatches/mlkem768/#bonus-track-using-a-ml-kem-implementation-as-kyber-v3

I haven't verified the result myself, but you might get away with what's noted there, namely:

shared, ciphertext := ML-KEM-Encapsulate(...)
shared = SHAKE-256(shared || ciphertext)[:32]

(or the same on the decapsulate side -- decapsulate OQS's value here in BC and then re-apply this transform).

And maybe that will give you interop with OQS, without downgrading BC?

[Chratho]

Thanks for this hint. I was indeed able to reproduce the "original" hash by applying two additional hashes (one on the ciphertext alone, and the already mentioned SHAKE-256 hash).