Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Correlation Between Key Length and Execution Time #1080

Closed
CindyZhouYH opened this issue Oct 28, 2021 · 14 comments
Closed

Correlation Between Key Length and Execution Time #1080

CindyZhouYH opened this issue Oct 28, 2021 · 14 comments

Comments

@CindyZhouYH
Copy link

CindyZhouYH commented Oct 28, 2021

I'm using Crypto++ built by the latest version of source code in this repository on Ubuntu 18.04.

The function is as follows:

void ECC_PrivatetoPublic(string priv){
    using namespace CryptoPP;
    clock_t start, finish;
    ECDSA<ECP, SHA256>::PrivateKey privateKey;
    ECDSA<ECP, SHA256>::PublicKey publicKey;
    const Integer privStr(priv.c_str());
    const DL_GroupParameters_EC<ECP>& curve = ASN1::secp521r1();
    privateKey.Initialize(curve, privStr);
    privateKey.MakePublicKey(publicKey);
    std::string x = IntToString<>(publicKey.GetPublicElement().x, 10);
    std::string y = IntToString<>(publicKey.GetPublicElement().y, 10);
    printf("%s\n%s\n", x.c_str(), y.c_str());
    return;
}

It seems that the execution time of privateKey.MakePublicKey(publicKey) is positively correlated with the length of the private key instead of a constant value. I did a simple experiment and heres the result. But I haven't studied the reason yet.

Wizard data (2)

I suppose this may leak the length information of the input private key and facilitate malicious attacks on key decryption.

Besides, the execution time becomes abnormally long when the private key reaches hundreds of bytes long, which causes a little inconvenience to me.

Hope you can check this case.

@carnil
Copy link

carnil commented Nov 5, 2021

This issue seems to have assigned CVE-2021-43398.

@geoffbeier
Copy link
Collaborator

I think I'm missing something... if you have the private key already, you know its length.

You can only call MakePublicKey() if you have the private key already.

How can a correlation between key length and a function's runtime be dangerous if you have to possess the private key already in order to call the function in the first place?

In the absence of further explanation, the CVE entry is misleading and should be withdrawn.

@noloader
Copy link
Collaborator

noloader commented Nov 28, 2021

Thanks @CindyZhouYH.

Please provide your test program and some data points. I would like to see how you generate your private keys for a particular curve, and how you can correlate a private key length to execution time beyond the field size.

Naively, it seems to me there's nothing interesting about determining how many bytes are in the private key. I think that leaks one bit of information (the MSB position), and I don't think that's an interesting problem.

Also, Crypto++ multiplies words and not bytes. A word is 8 bytes. The chances of all 8 bytes being 0 so the 65th-bit is leaked is 1 / 2^64. That's a really small probability, and I don't think the MSB position is leaked in practice.


... the execution time becomes abnormally long when the private key reaches hundreds of bytes long,

Something sounds a bit off here. A 256-bit curve will have a private key that is 64 bytes long; and a 521-bit curve will have a private key that is 132 bytes long. How do you have a private key that is hundreds of bytes long? They key should be rejected during loading or during validation.

@noloader
Copy link
Collaborator

noloader commented Dec 3, 2021

@CindyZhouYH,

Would you provide your test program and data points, please.

Thanks in advance.

@mouse07410
Copy link
Collaborator

mouse07410 commented Dec 6, 2021

Isn't it obvious that the longer the key is - the longer the operations with it would take?

Did somebody really assigned a CVE on this?!

Update: yes, as you increase the size of the curve generator to whatever, you're likely to reach a point when your computer takes forever (literally!) to operate on that key. It's called math...

@noloader
Copy link
Collaborator

Hi Everyone,

We are going to close this a "not a bug". We believe it is expected behavior. We don't believe the CVE is valid.

@CindyZhouYH, if you can provide a test program and test data we would be happy to revisit it.

@noloader noloader changed the title Dangerous Correlation Between Key Length and Execution Time Correlation Between Key Length and Execution Time Dec 17, 2021
@carnil
Copy link

carnil commented Dec 17, 2021

@noloader are you (as upstream) going to ask MITRE (via cveform.mitre.org ideally) for a REJECT of the CVE? (or at least being marked disputed if there is not consensus with the reporter that the CVE is not valid)

@noloader
Copy link
Collaborator

noloader commented Dec 17, 2021

@carnil,

I'm not sure who acquired the CVE, so I am not sure who to contact about withdrawaling it.

Mitre's CVE webform is unusable. I tired to use it to obtain a CVE but I could not submit the form. I lost my taste for the webform. Mitre should re-enable the email address.

@carnil
Copy link

carnil commented Dec 17, 2021

@noloader the assigning CNA was MITRE, but the metadata does not disclose who requested it. I just have asked MITRE if they can reject the CVE.

@noloader
Copy link
Collaborator

Thanks @carnil.

@CindyZhouYH
Copy link
Author

Sorry for the delayed reply. @geoffbeier @noloader @carnil @mouse07410
I think you may misunderstood what I meant.
Of course, for normal user, they know the private key. But this vulnerability could allow an attacker who can detect runtime without knowing the key private key information to obtain information of the key length, which provides great convenience for cracking the private key.

On the contrary, the execution time of OpenSSL on the same function remains unchanged, which is a correct performance because it will not disclose the information of the privacy data participating in the algorithm. You can check it through the following testfile.

void openssl_ECC_PrivatetoPublic(string priv){
    int curveNID;
    clock_t start, finish;
    curveNID = NID_secp384r1;
    EC_KEY * ctx = EC_KEY_new();
    EC_GROUP * group = EC_GROUP_new_by_curve_name(curveNID);
    BIGNUM* bn = nullptr;
    BIGNUM* pub_x = nullptr;
    BIGNUM* pub_y = nullptr;
    EC_POINT* pub = nullptr;
    EC_KEY_set_group(ctx, group);
    BN_dec2bn(&bn, priv.c_str());
    EC_KEY_set_private_key(ctx, bn);
    pub = EC_POINT_new(group);
    start = clock();
    EC_POINT_mul(group, pub, bn, nullptr, nullptr, nullptr);
    pub_x=BN_new();
    pub_y=BN_new();
    EC_POINT_get_affine_coordinates(group, pub, pub_x, pub_y, nullptr);
    char* pub_x_str = nullptr;
    char* pub_y_str = nullptr;
    pub_x_str = BN_bn2dec(pub_x);
    pub_y_str = BN_bn2dec(pub_y);
    finish = clock();
    printf("openssl: %ld\n", finish - start);
    EC_KEY_free(ctx);
    EC_GROUP_free(group);
    BN_free(pub_x);
    BN_free(pub_y);
    EC_POINT_free(pub);
    BN_free(bn);
    free(pub_x_str);
    free(pub_y_str);
}

void cryptopp_ECC_PrivatetoPublic(string priv){
    clock_t start, finish;
    ::CryptoPP::ECDSA<::CryptoPP::ECP, ::CryptoPP::SHA256>::PrivateKey privateKey;
    ::CryptoPP::ECDSA<::CryptoPP::ECP, ::CryptoPP::SHA256>::PublicKey publicKey;
    const ::CryptoPP::Integer privStr(priv.c_str());
    string ini = ::CryptoPP::IntToString<>(privStr, 10);
    const ::CryptoPP::DL_GroupParameters_EC<::CryptoPP::ECP>& curve = ::CryptoPP::ASN1::secp521r1();
    privateKey.Initialize(curve, privStr);
    start = clock();
    privateKey.MakePublicKey(publicKey);
    finish = clock();
    printf("cryptopp: %ld   ", finish - start);
    string x = ::CryptoPP::IntToString<>(publicKey.GetPublicElement().x, 10);
    string y = ::CryptoPP::IntToString<>(publicKey.GetPublicElement().y, 10);
    return;
}

void checkTime_ECC(){
    string base = "94494124494959990410";
    string priv = "";
    for(int i=0;i<30;i++){
        priv = priv + base;
        cryptopp_ECC_PrivatetoPublic(priv);
        openssl_ECC_PrivatetoPublic(priv);
    }
    return;
}

int main(){
    checkTime_ECC();
    return 0;
}

image

@mouse07410
Copy link
Collaborator

mouse07410 commented Dec 31, 2021

My RSA private key is 4096 bits. My ECDSA key is 380 bits. Feel free to use this info to crack them.

@tomlemmon
Copy link

@mouse07410 You are really the wisest man I ever met. I even didn't know what math was until you explained it! Thank you for your great help. It is a great shame pleasure (sorry, my English is also poor, maybe you can teach me to speak English as well) to have people like you in the community. If ignorance means happiness, then you must be the happiest person in the world!

@noloader @CindyZhouYH
Sorry, I couldn't resist expressing my compliments to mouse07410. Let's get back to the point and ignore him.
My question here is why OpenSSL try to implement this function with unchanged time consumption? Is this issue related to timing attack? It would be nice if a more accurate explanation could be given.

@acipm
Copy link

acipm commented Aug 17, 2022

@CindyZhouYH Could you please give some theoretical background on why OpenSSL does implement this in constant time as @tomlemmon asked?

Is there any known attack that chains the keysize with something else? Because I agree with @mouse07410 that in itself this should not be an issue?

I am not from the cryptography community, so a detailed explanation would be very helpful, thanks!

LeSuisse added a commit to LeSuisse/nixpkgs that referenced this issue Nov 27, 2022
https://github.com/weidai11/cryptopp/releases/tag/CRYPTOPP_8_7_0

Note there is a bogus CVE ID assigned to versions <= 8.6.0 (CVE-2021-43398).
See upstream discussion for more information weidai11/cryptopp#1080
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

7 participants