search

paulmillr / nip44

NIP44 spec and implementations of encrypted messages for nostr
https://nostr.com
26 stars 9 forks source link

NIP44 Implementations are broken #17

Closed prolic closed 2 weeks ago

prolic commented 2 weeks ago

Edit by @prolic: I leave the original ticket description, but before anyone gets shocked, TLRD: NIP44 is all good - The findings presented here stem from a misunderstanding of the original NIP44 document. Clarification has been tried to get appended here.

NIP-44 Implementations: Analyzing the Inconsistencies

NIP-44, which governs encrypted messaging in Nostr, mandates the use of Elliptic-curve Diffie–Hellman (ECDH) with the specific function secp256k1_ecdh. Extensive test vectors for NIP-44 are available here.

However, an examination of various NIP-44 implementations across multiple languages reveals significant inconsistencies:

C

F

Go

JavaScript

Kotlin

Rust

Swift

Summary of Findings

Only two implementations (C and Swift) are correct, while others mistakenly use secp256k1_ec_pubkey_tweak_mul instead of secp256k1_ecdh.

Since the JavaScript implementation is incorrect but passes the provided test vectors (verified locally), it's likely that the test vectors were generated using this flawed implementation. Interestingly, the Swift implementation, which is correct, still passes these test vectors — this discrepancy is worth investigating further, as it might indicate failing tests when run locally.

Why Does This Matter?

If these discrepancies persist, encrypted messaging under NIP-44 in Nostr will lack true standardization. Although the protocol may be officially standardized, clients will not be interoperable, depending on the libraries they use. Additionally, there could be other broken implementations in various Nostr clients that haven't been identified yet.

VnUgE commented 2 weeks ago

C (noscrypt) implementation tests against nip44 vectors using a c-sharp wrapper which will be released eventually. In the mean time it exists in it's own feature branch. Since nip44 is a much wider net than the encryption cipher itself and utilities derived from the encryption layer. The utility library added in v0.1.3, includes padding tests and correctness tests using some values pulled from the test-vector file.

Testing against the vector file is not something I intend to do directly in C at the moment because it's a massive pain handling JSON and a higher-level wrappers will be implementing tests against it, now and in the future.

Noscrypt is always tested against the nip44 test vector file on Windows (1904+) and Linux (Debian and Fedora) amd64 based systems before every release

mikedilger commented 2 weeks ago

The nip44 lib I wrote calls rust-secp256k1::ecdh::shared_secret_point which calls C secp256k1_ecdh(..) It does not call rust-secp256k1::mul_tweak which calls C secp256k1_ec_pubkey_tweak_mul.

It does however pass the test vectors. To be careful, I include the test vector JSON file verbatim.

So I think the rust version is OK, but please correct me if I'm wrong.

https://github.com/mikedilger/nip44

prolic commented 2 weeks ago

Your test vector file https://github.com/mikedilger/nip44/blob/master/src/nip44.vectors.json is different from https://github.com/paulmillr/nip44/blob/main/nip44.vectors.json

Semisol commented 2 weeks ago

This issue is bogus.

The specification defines secp256k1_ecdh(a, B) as a * B (scalar mult.), with the result being the x coordinate.

secp256k1_ec_pubkey_tweak_mul implements the requested function above.

secp256k1_ecdh in libsecp256k1 implement the requested function also, but introduces a hashing step. The implementations that use this function set this "hashing function" to output the x coordinate as is.

prolic commented 2 weeks ago

Used Test Vectors

{
  "v2": {
    "valid": {
      "get_conversation_key": [
        {
          "sec1": "315e59ff51cb9209768cf7da80791ddcaae56ac9775eb25b6dee1234bc5d2268",
          "pub2": "c2f9d9948dc8c7c38321e4b85c8558872eafa0641cd269db76848a6073e69133",
          "conversation_key": "3dfef0ce2a4d80a25e7a328accf73448ef67096f65f79588e358d9a0eb9013f1"
        },

taken from: https://github.com/paulmillr/nip44/blob/main/nip44.vectors.json

The Implementation

The getConversationKey function derives a conversation key from a secret key (SecKey) and a compressed public key (PubKeyXO). The function uses pubKeyTweakMul to perform the key derivation, which is different from the standard ECDH approach:

-- | Derives the conversation key using SecKey and PubKeyXO
getConversationKey :: SecKey -> PubKeyXO -> Maybe ByteString
getConversationKey secKey pk = do
    pubKeyXY <- convertToFullPubKey pk
    let tweak = fromJust $ S.importTweak $ S.exportSecKey (getSecKey secKey)
    sharedSecret <- S.pubKeyTweakMul pubKeyXY tweak     -- we use pubKeyTweakMul now !!!
    let sharedSecret' = BS.drop 1 $ S.exportPubKeyXY True sharedSecret
    let salt = C8.pack "nip44-v2"
    let prk = extract salt sharedSecret' :: PRK SHA256
    return $ BA.convert prk

The Test

We test the function using known inputs and compare the computed conversation key to an expected value:

let sk = read fromJust $ importSecKey $ hexToByteString (sec1 tv)
let pk = fromJust $ importPubKeyXO $ hexToByteString (pub2 tv)
let expectedKey = hexToByteString (fromJust $ conversationKey tv)

let result = getConversationKey sk pk
putStrLn $ show $ BC.unpack $ B16.encode $ expectedKey
putStrLn $ show $ BC.unpack $ B16.encode $ fromJust result

Expected Output

3dfef0ce2a4d80a25e7a328accf73448ef67096f65f79588e358d9a0eb9013f1 -- expected conversation key
3dfef0ce2a4d80a25e7a328accf73448ef67096f65f79588e358d9a0eb9013f1 -- result !!!

Alternate Implementation

If we use the standard ECDH method for deriving the conversation key:

getConversationKey :: SecKey -> PubKeyXO -> Maybe ByteString
getConversationKey secKey pk = do
    pubKeyXY <- convertToFullPubKey pk
    let sharedSecret = S.ecdh (getSecKey secKey) pubKeyXY
    let sharedSecret' = BA.convert sharedSecret :: ByteString
    let salt = C8.pack "nip44-v2"
    let prk = extract salt sharedSecret' :: PRK SHA256
    return $ BA.convert prk

Resulting Output

3dfef0ce2a4d80a25e7a328accf73448ef67096f65f79588e358d9a0eb9013f1 -- expected conversation key
9d4ce2dced70fd54894bd4e1e3509136bee1c5573b08ffd86c3dcc04f2cc99ca -- result !!!

Conclusion

As shown, using pubKeyTweakMul yields a different result than using ECDH. The test vectors appear to have been created with the flawed JavaScript implementation. If there is anything incorrect in this analysis, please let me know.

mikedilger commented 2 weeks ago

Your test vector file https://github.com/mikedilger/nip44/blob/master/src/nip44.vectors.json is different from https://github.com/paulmillr/nip44/blob/main/nip44.vectors.json

So it is. But my test vector commit is dated 2023-12-16 and matches a file in Paul's repo commited on 2023-12-20 (/rust/src/nip44.vectors.json). However IMHO different implementations should not use different test vectors. This repo (paulmillr/nip44) has different test vectors for rust versus for javascript. If I use the javascript test vectors on my nip44 repo, it fails:

test tests::test_invalid_decrypt ... FAILED
test tests::test_valid_calc_padded_len ... ok
test tests::test_valid_encrypt_decrypt ... FAILED
test tests::test_valid_get_conversation_key ... FAILED
test tests::test_invalid_get_conversation_key ... ok

Yet I have had NIP-17 private DM convos with a number of people and have not noticed any decryption errors. So I'm quite confused about this now.

paulmillr commented 2 weeks ago

Spec says:

Execute ECDH (scalar multiplication) of public key B by private key A Output shared_x must be unhashed, 32-byte encoded x coordinate of the shared point

It's unhashed.

with the specific function secp256k1_ecdh

ECDH is key agreement protocol. It has nothing to do with libsecp256k1 or its functions, which you're mentioning. Diffie Hellman is done with point-by-scalar multiplication. Should it be hashed? Different standards say different things. We've chosen unhashed one.

mikedilger commented 2 weeks ago

Nevermind my comments above, the tests failed on rust because it expected certain fields in the json. The crypto passed. Also shared_secret_point in rust-secp256k1 is unhashed and warns about this in the comment on the function.

So all is good.

prolic commented 2 weeks ago

Digging deeper into bitcoin-core/secp256k1:

int secp256k1_ecdh(const secp256k1_context* ctx, unsigned char *output, const secp256k1_pubkey *point, const unsigned char *scalar, secp256k1_ecdh_hash_function hashfp, void *data), see https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/ecdh/main_impl.h#L29

calls internally: secp256k1_ecmult_const (see https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/ecdh/main_impl.h#L53) and then applies hashfp (see https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/ecdh/main_impl.h#L62).

On the other hand:

int secp256k1_ec_pubkey_tweak_mul(const secp256k1_context* ctx, secp256k1_pubkey *pubkey, const unsigned char *tweak32), see https://github.com/bitcoin-core/secp256k1/blob/master/src/secp256k1.c#L745

calls internally: secp256k1_eckey_pubkey_tweak_mul (see https://github.com/bitcoin-core/secp256k1/blob/master/src/secp256k1.c#L745) and if you look there:

static int secp256k1_eckey_pubkey_tweak_mul(secp256k1_ge *key, const secp256k1_scalar *tweak) (see https://github.com/bitcoin-core/secp256k1/blob/master/src/eckey_impl.h#L80) it also calls secp256k1_ecmult (see https://github.com/bitcoin-core/secp256k1/blob/master/src/eckey_impl.h#L87) but doesn't apply the hash function.

So I stand corrected on most issues. My initial statement about mistakenly using secp256k1_ec_pubkey_tweak_mul instead of secp256k1_ecdh is wrong. You should always use secp256k1_ec_pubkey_tweak_mul to comply with the NIP44 specs. So where did I get this from? Looking at https://github.com/nostr-protocol/nips/blob/master/44.md and searching for "secp256k1_ecdh" gives me two results, with two function calls like that. Any mention of "secp256k1_ec_pubkey_tweak_mul" nowhere to be found.

By the way, I have a working Haskell implementation now, just took me a few extra days to work through this mess. Sorry for any confusion created, but the specs are really more unclear than you think, given that it mentions secp256k1_ecdh two times and you are not supposed to call a function with the exact name on the original bitcoin secp256k1 lib.

On a last note: All implementations should really use the very same test vectors.

paulmillr commented 2 weeks ago

See e2d6c80

paulmillr commented 2 weeks ago

@prolic consider adding your code to the repo once it's done

prolic commented 2 weeks ago

@prolic consider adding your code to the repo once it's done

Appreciate the offer, but I don't want to maintain this in two places at the moment and it's part of a nostr client implementation, not even a distinct lib to be installed stand-alone.

Feel free to however link the repository or file directly: Encryption.hs

paulmillr commented 2 weeks ago

There is no need to maintain two copies, just uploading everything once is ok. You can keep updating your repos, and the link would be there. Having everything in one repo is extremely useful for beginners.