search

cryspen / hpke-rs

Pure Rust implementation of HPKE (https://www.rfc-editor.org/rfc/rfc9180.html)
31 stars 16 forks source link

Add support for P-521 #21

Closed mefsantos closed 3 years ago

mefsantos commented 3 years ago

the KAT from test_vectors.json is failing for P-521 (for every configuration). I implemented P-521 support (on swift) and the unit test (which is passing) with the following configuration (from the draft 08): Mode: Base DHKEM(P-521, HKDF-SHA512), HKDF-SHA512, AES-256-GCM.

Every other configuration is passing except the ones for P-521.

Any chance P-521 being implemented soon so you can validate this issue?

mefsantos commented 3 years ago

I was port'ing v0.0.8 and firstly used the respective json file. However, I also tried the updated test vectors from the last commit and it is still failing

mefsantos commented 3 years ago

Im not sure if this is relevant but the error I'm having is authentication failure. Unfortunately, CryptoKit lacks documentation but this error is yield if any of the components is wrong (ciphertext, aad, key, nonce, or authentication tag) which is roughly how it is specified in the NISTP GCM paper

franziskuskiefer commented 3 years ago

Thanks for taking a look at this. The issue is that hacl*/evercrypt doesn't support P521 right now. I'm looking at adding other primitives to make the implementation more complete. But this requires some thought and then actually implementing it.

mefsantos commented 3 years ago

Alright. I'll implement the remaining tests from the draft to make sure it's not just an edge case passing

mefsantos commented 3 years ago

issue update: (tag: v0.0.8, commit: f740af9)

So it turns out I forgot to implement the HpkeContext::open() operation in the tests to the draft's test vectors. So, after implementing, at least there's a more consistent result: P521 always fails wheras the remaining configs are passing.

By tracking down the issue, I believe the problem is in the diffie-hellman, namely in ecdh_derive.

To ease the explanation of what I have done, here is the code for the actual test for the context setup (The syntax differs from rust but its easy to infer from context)

Note that every variable that is not being set in this sample is obtained from the draft's test vector.

Configuration: 

let mode = HpkeMode.base
let kemId = KemMode.dhKemP521
let kdfId = KdfMode.hkdfSha512
let aeadId = AeadMode.aesGcm256

hpke = Hpke.new(mode: mode, kemId: kemId, kdfId: kdfId, aeadId: aeadId)

The key schedule test:

// setup a sender with KAT's randomness
var senderHpke = hpke!
senderHpke.setKemRandom(bytes: ikmE)

let (_enc, senderCtx) = try senderHpke.setupSender(
    pkR: HpkePublicKey(value: pkRm),
    info: info,
    psk: .none,
    pskId: .none,
    skS: HpkePrivateKey(value: skEm)
).get()

// setup the computed context given the KAT's shared secret
let computedContext = try hpke.keySchedule(sharedSecret: sharedSecret, info: info, psk: [], pskId: []).get()

// setup the expected context (KAT)
let expectedContext = HpkeContext(
    key: key,
    nonce: baseNonce,
    exporterSecret: exporterSecret,
    sequenceNumber: 0,
    hpke: hpke
)

XCTAssertEqual(computedContext, expectedContext)     // check OK
XCTAssertEqual(computedContext.computeNonce(), expectedContext.computeNonce())     // check OK

XCTAssertEqual(_enc, enc)     // check OK
XCTAssertEqual(senderCtx.nonce, baseNonce) // check fails <----

A. As marked in the code, the _enc produced is the same as KAT's but the base nonce differs.

Tracing inside DhKEM::encap(), we can start with these assumptions, considering serialize and deserialize are, yet, identity functions: A1. derive_key_pair(suiteId, random()) is OK since it produces the same key pair (pkE, skE) with the given ikmE because enc = serialize(pkE). A2. both suiteId and random() are OK for the same reason (_enc = enc) A3. kemContext is OK since enc is OK and pkRm is the serialized pkR received as parameter (and ultimately received from KAT's)

This means that:

  1. from the pair (zz, enc) generated with encap(), zz is not being properly derived;
  2. from the aforementioned assumptions, the only "bad" parameter from extract_and_expand is dh_pk

which brings us to the ecdh_derive implementation. Sadly, I cannot dig deeper since, from this point onwards, I am using CryptoKit's sharedSecretFromKeyAgreement() which derives the shared secret as such:

// public keys are handled in "x963" (prepend 0x04)
let pubKey = try P521.KeyAgreement.PublicKey(x963Representation: pk)
let privKey = try P521.KeyAgreement.PrivateKey(rawRepresentation: sk)
let derivedSecret = try privKey.sharedSecretFromKeyAgreement(with: pubKey)

and the result of ecdh_derive is also validated and stripped:

...
let ssLen = sharedSecretLen(dhMode: Self.dhId)
sharedSecret.prefix(ssLen) // take the first ssLen bytes of SharedSecret

Note that ssLen is 66 for P521 as specified in HPKE-08, Section 4.1 DH-Based KEM

To ensure Apple's DH implementation is OK I generated a test vector on python with the package criptography for ecdh over P521, for 20 random generations. The test vector contained the sender's public key, the receiver's private and public keys (to also assess public key derivation) and the diffie-hellman's shared secret between the receiver and the sender.

The test is passing for that test vector so apple's DH is working as expected.

Considering all this info, I'm inclined to say the issue might be related with the KAT generation, specifically the shared_secret field on P521 configurations.

Hopefully I exposed it correctly and not overlooking any detail on my implementation that may be causing the issue.

test vector info:

franziskuskiefer commented 3 years ago

@mefsantos thanks for the detailed explanation. But I'm not sure exactly sure what the issue is or what you are trying to do. Did you add P521 support and have issues with it?

mefsantos commented 3 years ago

I'd say the issue is the KAT for P521, they are all failing - enc matches but sharedSecret doesn't. I implemented P521 support and wanted to make sure it was correct by running your KAT, but they fail for P521. That's why I tried to trace the issue, leading to the ecdh_derive and the python-generated test vector to assess apple's Diffie-Hellman implementation

franziskuskiefer commented 3 years ago

The test vectors I'm using are the official ones generated by the go implementation. Since this implementation doesn't support P521 it also can't create the test vectors.

But if you have any code for me to look at, I might be able to help you figure out the issue 🙂

mefsantos commented 3 years ago

Thanks for helping out. This will (again) be a long one... stay with me :)

I'd say the issue should not be the code (in general) since the remaining configurations are passing. However, it might be related to the constants defining the sizes which is the only "code" specific for each curve, aside from deriveKeyPair which applies the "bitmask" 0xFF or 0x01 on P256 and P521, respectively. Anyway, as referred in the detailed explanation, the issue "starts" in encap which I implemented as follows:

func encap(pkR: [UInt8], suiteId: [UInt8]) -> Result<([UInt8], [UInt8]), KemError> {
    switch self.deriveKeyPair(suiteId: suiteId, ikm: self.random()) {
    case .failure(let kemError)     : return .failure(kemError)
    case .success(let (pkE, skE))   :
        var dhPk: [UInt8]
        switch self.dh(sk: skE, pk: pkR) {
        case .success(let key)      : dhPk = key
        case .failure(let kemError) : return .failure(kemError)
        }
        let enc = self.serialize(pk: pkE)
        let pkRm = self.serialize(pk: pkR)
        let kemContext = enc + pkRm

        let zz = self.extractAndExpand(pk: dhPk, kemContext: kemContext, suiteId: suiteId)
        return .success((zz, enc))
    }
}

For context, here is the setupSender implementation (I'll remove the remaining modes to avoid code clutter): 

public func setupSender(
        pkR: HpkePublicKey,
        info: [UInt8],
        psk: [UInt8]?,
        pskId: [UInt8]?,
        skS: HpkePrivateKey?
    ) -> Result<(EncapsulatedSecret, HpkeContext), HpkeError> {
        var zz = [UInt8]()
        var enc = [UInt8]()
        switch self.mode {
        case .base:
            switch self.kem.encap(pkR: pkR.bytes) {
            case .success(let pair)     : (zz, enc) = pair
            case .failure(let kemError) : return .failure(.from(kemError: kemError))
            }
        (...)
        }

        switch self.keySchedule(sharedSecret: zz, info: info, psk: psk ?? [], pskId: pskId ?? []) {
        case .success(let context)      : return .success((enc, context))
        case .failure(let error)        : return .failure(error)
        }
    }

So, analyzing encap: From the resulting pair (zz, enc), zz is the issue, since enc is equal to KAT's. Above, I reasoned about what variables could be different than expected throughout this function. To recap:

Lets dig into it: 

func dh(sk: [UInt8], pk: [UInt8]) -> Result<[UInt8], KemError> {
    switch EcdhHelper.ecdhDerive(ecdhId: self.dhId, pk: pk, sk: sk) {
    case .success(let sharedSecret):
        let ssLen = DhKemConstants.sharedSecretLen(dhMode: self.dhId)
        guard sharedSecret.count >= ssLen else {
            HSLogger.log(.kem).error("DH shared secret is shorter than the minimum required: \(sharedSecret.count) < \(ssLen)")
            return .failure(.cryptoError)
        }
        HSLogger.logCrypto("Shared Secret Derived: \(sharedSecret.toHex). Size: \(sharedSecret.count)")
        return .success([UInt8](sharedSecret.prefix(ssLen)))
    case .failure(let e): return .failure(e)
    }
}

Since no errors were caught here, we can focus on EcdhHelper.ecdhDerive(ecdhId: self.dhId, pk: pk, sk: sk)

This is where I delegate the Diffie-hellman to CryptoKit:

static func ecdhDerive(ecdhId: EcdhMode, pk: [UInt8], sk: [UInt8]) -> Result<[UInt8], KemError> {
    do {
        switch ecdhId {
        (...)
        case .p521:
            // x963Representation => prepend 0x04
            let pubKey = try P521.KeyAgreement.PublicKey(x963Representation: pk)
            let privKey = try P521.KeyAgreement.PrivateKey(rawRepresentation: sk)
            // actual Diffie-Hellman between sk & pk
            let derivedSecret = try privKey.sharedSecretFromKeyAgreement(with: pubKey)
            return .success(derivedSecret.withUnsafeBytes{Data($0)}.bytes) // extract the bytes from `SharedSecret` struct
        }
    } catch {
        (...)
    }
}

This is the function that I validated using the python-generated test vector. The Diffie-hellman is correct.

So, since there were no errors until here, we can jump back to dh() with a valid byte array containing the sharedSecret. since we return [UInt8](sharedSecret.prefix(ssLen)), and ssLen = DhKemConstants.sharedSecretLen(dhMode: self.dhId) lets take a look at that.

This is the entire struct containing the getter for key sizes:

struct DhKemConstants {
    /// `Nsk`
    /// \- [Hpke-08 Section 7.1](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hpke-08#section-7.1)
    static func skLen(dhMode: EcdhMode) -> Int {
        switch dhMode {
        case .x25519    : return 32
        case .p256      : return 32
        case .p521      : return 66
        }
    }
    /// `Npk`
    /// \- [Hpke-08 Section 7.1](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hpke-08#section-7.1)
    static func pkLen(dhMode: EcdhMode) -> Int {
        switch dhMode {
        case .x25519    : return 32
        case .p256      : return 65
        case .p521      : return 133
        }
    }
    /// `Nsecret`
    /// \- [Hpke-08 Section 7.1](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hpke-08#section-7.1)
    static func sharedSecretLen(dhMode: EcdhMode) -> Int {
        switch dhMode {
        case .x25519    : return 32
        case .p256      : return 32
        case .p521      : return 64
        }
    }
}

since sharedSecretLen(dhMode: .p521) is 64, sharedSecret.prefix(ssLen) will return the first 64 bytes of the sharedSecret (which was originally 66 bytes long, as referred in hpke-08, section 4.1)

This is the 64-byte array used to perform the extractAndExpand in encap, and from my tests, this is the only byte array that differs from KAT's.

to make sure the issue is the dhPk and not the extractAndExpand I debugged the execution of one test with a couple of breakpoints to extract these values BEFORE the end of encap: test configuration: base, dhKemP521, hkdf521, aesGCM256

enc:
0401f1f6d9583bcdaf771212a996542e370a73e9e36a207eed1168f4142a139832f9ef2f8fc87664f3d9074dedca1b01c2d46b5095e3f0d561ca9d364dff041ca6f3b400f782800038ea8e52a752f5ffaad25df0e971c53803199c7f0ec96283d874d9184c6d6f74d5bc9533b91d6b7183a073ffb8d0d1d2006deba12e10529fc64ee025bf

zz(sharedSecret): 4f4a880c6341a2331d555186eef1e48ec4ff7c6c5f23ff5345597bb44644b34119010d0ad644f3fa294e0da0d60a895937a4bd056356241fe5de77bde0b087c21328

skE: 01a33bedb85d1993389a3e524477411c8c088572e2b3e160eea59b1a074626262d0409e48ce9fc7ed4af8e298669e20646895a6460666b23867135c549ac8ef45c96
pkE: 0401f1f6d9583bcdaf771212a996542e370a73e9e36a207eed1168f4142a139832f9ef2f8fc87664f3d9074dedca1b01c2d46b5095e3f0d561ca9d364dff041ca6f3b400f782800038ea8e52a752f5ffaad25df0e971c53803199c7f0ec96283d874d9184c6d6f74d5bc9533b91d6b7183a073ffb8d0d1d2006deba12e10529fc64ee025bf

pkR: 0401cf0f6149f3c205096fb29d415a38a3a10c5e882822b582220ae74230f78d183b92824fb2b1d9b005b8af49c43fe2341f210d5262da9b97bb3ae750292656f63d39001b4b39296e906399e82a2b4413a3b2ff2b2657a166c1b85926d33190ad79f7bcc8b0a80092e93c6998088c87bb5bb372e596b902fbf100f2fb0a24f6392b4a444c

keyScheduleContext: 0083a27c5b2358ab4dae1b2f5d8f57f10ccccc822a473326f543f239a70aee46347324e84e02d7651a10d08fb3dda739d22d50c53fbfa8122baacd0f9ae5913072ef45baa1f3a4b169e141feb957e48d03f28c837d8904c3d6775308c3d3faa75dd64adfa44e1a1141edf9349959b8f8e5291cbdc56f62b0ed6527d692e85b09a4

which means that the only value differing from KAT's is the zz/sharedSecret

I'm not tackling the KDF labels since the KDF tests are passing, and the remaining configs are working as well.

To recap, I believe the issue is related to the Diffie-hellman between the ephemeral secret key (skE - generated the same as KAT's) and the pkR (loaded from the KAT).

I was using this p521Base.json.txt test (a subset from the original KAT) for this issue