RSA_check_key

[public]

We probably don't want to have our own primality testing coding and other complex maths in cryptography, but this is still a useful feature.

Being able to check the validity (and perhaps "strength"?) of an RSA key is useful though. We should probably add an API like RSAPrivateKey.check(backend) (better name suggestions please?) that hooks intro the backends key checking stuff.

In OpenSSL this is called RSA_check_key and it checks the primality of the p and q and that the coefficients have the right values and so on.

[alex]

I'm not wild about this, it seems like a really classic case of "There's this API you were supposed to call, but it wasn't obvious, so everyone misses it" -- it also seems like it makes it really easy to have the correctness of an RSAKey be backend specific.

Maybe we should do some amount of checking in __init__ and then do more checking when you actually try to use a key or something?

[reaperhulk]

The biggest problem is performance. We can do all the checks quite easily, but if you pay a 1/4+ second penalty every time we build an RSAPrivateKey object that gets painful quickly.

Of course, we don't know that it's going to be painful so maybe we should do all the expensive checks all the time at first and see how it works. If it turns out it's a genuine issue we can come up with alternate solutions (like having a private constructor that bypasses the checks for known good situations).

[public]

We could use the backend specific checks when we convert them to backend specific context type. If we make it implicit during __init__ we are pretty much forced to implement them all ourselves. I am pretty hesitant to implement primality tests and so on due to their complexity and this being a practice that is apparently not that common in the field. AFAICT not a single crypto API does these checks automatically.

Does signing and verification even work reliably if your key parameters are broken in the ways these checks will detect? If you load a private key from a file, should we run those (expensive) tests then? Presumably you used an algorithm you trust to actually generate them in the first place?

It might be useful to have a CPython implementation of some of the tests so we can get a feel for just how slow they are. I think someone posted one in IRC earlier?

Can we add these tests and remove them later (or the other way around) without an API break?

[alex]

Yes, I'm sure the algorithms break, I've been able to coax pycrypto into all sorts of crashes by providing weird values for things.

On Thu, Feb 6, 2014 at 9:58 AM, Alex Stapleton notifications@github.comwrote:

We could use the backend specific checks when we convert them to backend specific context type. If we make it implicit during init we are pretty much forced to implement them all ourselves. I am pretty hesitant to implement primality tests and so on due to their complexity and this being a practice that is apparently not that common in the field. AFAICT not a single crypto API does these checks automatically.

Does signing and verification even work reliably if your key parameters are broken in the ways these checks will detect? If you load a private key from a file, should we run those (expensive) tests then? Presumably you used an algorithm you trust to actually generate them in the first place?

It might be useful to have a CPython implementation of some of the tests so we can get a feel for just how slow they are. I think someone posted one in IRC earlier?

Can we add these tests and remove them later (or the other way around) without an API break?

— Reply to this email directly or view it on GitHubhttps://github.com/pyca/cryptography/issues/569#issuecomment-34351012 .

"I disapprove of what you say, but I will defend to the death your right to say it." -- Evelyn Beatrice Hall (summarizing Voltaire) "The people's good is the highest law." -- Cicero GPG Key fingerprint: 125F 5C67 DFE9 4084

[public]

Obviously crashes are bad but loading private keys you don't trust is probably worse.

[public]

Are there any cheaper checks we can do on p, q and d? Presumably they should at least be < modulus but is there an easy upper limit we can compute easily?

Sent with AquaMail for Android http://www.aqua-mail.com

On 6 February 2014 17:59:25 Alex Gaynor notifications@github.com wrote:

Yes, I'm sure the algorithms break, I've been able to coax pycrypto into all sorts of crashes by providing weird values for things.

On Thu, Feb 6, 2014 at 9:58 AM, Alex Stapleton notifications@github.comwrote:

We could use the backend specific checks when we convert them to backend specific context type. If we make it implicit during init we are pretty much forced to implement them all ourselves. I am pretty hesitant to implement primality tests and so on due to their complexity and this being a practice that is apparently not that common in the field. AFAICT not a single crypto API does these checks automatically.

Does signing and verification even work reliably if your key parameters are broken in the ways these checks will detect? If you load a private key from a file, should we run those (expensive) tests then? Presumably you used an algorithm you trust to actually generate them in the first place?

It might be useful to have a CPython implementation of some of the tests so we can get a feel for just how slow they are. I think someone posted one in IRC earlier?

Can we add these tests and remove them later (or the other way around) without an API break?

— Reply to this email directly or view it on GitHubhttps://github.com/pyca/cryptography/issues/569#issuecomment-34351012 .

"I disapprove of what you say, but I will defend to the death your right to say it." -- Evelyn Beatrice Hall (summarizing Voltaire) "The people's good is the highest law." -- Cicero GPG Key fingerprint: 125F 5C67 DFE9 4084

---

Reply to this email directly or view it on GitHub: https://github.com/pyca/cryptography/issues/569#issuecomment-34351125

[reaperhulk]

Since we're making a performance argument we need to quantify the expense of fully validating the integrity of e, d, n, p, q.

To properly validate them you would hypothetically want to do the following:

• e must be >=3 and odd (and probably fits in 32-bits, Windows CryptoAPI can't handle more).
• p and q must be prime.
• n must be p * q
• d must be equal to its computation using p, q, and e (using extended euclidean?)

Any other requirements? I suppose if we include CRT coefficients then validating those becomes a requirement as well.

Of the requirements above, primality testing is likely the most expensive. Years ago I did a naïve Miller-Rabin primality tester in Python (be kind I didn't know Python then!) and it is slow. Validation of p & q on a 4096-bit key takes ~4 seconds. It'll need to be faster than that (although I'm guessing we can speed that up quite a bit) :)

[reaperhulk]

Might also need to add that e must be relatively prime to n.

[public]

At that point can't we remove everything except p and q from init and regenerate the rest of the key?

On 6 February 2014 18:52:46 Paul Kehrer notifications@github.com wrote:

Since we're making a performance argument we need to quantify the expense of fully validating the integrity of e, d, n, p, q.

To properly validate them you would hypothetically want to do the following:

• e must be >=3 and odd (and probably fits in 32-bits, Windows CryptoAPI can't handle more).
• p and q must be prime.
• n must be p * q
• d must be equal to its computation using p, q, and e (using extended euclidean?)

Any other requirements? I suppose if we include CRT coefficients then validating those becomes a requirement as well.

Of the requirements above, primality testing is likely the most expensive. Years ago I did a naïve Miller-Rabin primality tester in Python (be kind I didn't know Python then!) and it is slow. Validation of p & q on a 4096-bit key takes ~4 seconds. It'll need to be faster than that (although I'm guessing we can speed that up quite a bit) :)

---

Reply to this email directly or view it on GitHub: https://github.com/pyca/cryptography/issues/569#issuecomment-34356622

[reaperhulk]

p, q, and e would be required but that’s technically all if we choose to go that far.

On Thursday, February 6, 2014 at 1:18 PM, Alex Stapleton wrote:

At that point can't we remove everything except p and q from init and
regenerate the rest of the key?

On 6 February 2014 18:52:46 Paul Kehrer <notifications@github.com (mailto:notifications@github.com)> wrote:

Since we're making a performance argument we need to quantify the expense
of fully validating the integrity of e, d, n, p, q.

To properly validate them you would hypothetically want to do the following:

• e must be >=3 and odd (and probably fits in 32-bits, Windows CryptoAPI
  can't handle more).
• p and q must be prime.
• n must be p * q
• d must be equal to its computation using p, q, and e (using extended
  euclidean?)

Any other requirements? I suppose if we include CRT coefficients then
validating those becomes a requirement as well.

Of the requirements above, primality testing is likely the most expensive.
Years ago I did a naïve Miller-Rabin primality
tester in
Python (be kind I didn't know Python then!) and it is slow. Validation of p
& q on a 4096-bit key takes ~4 seconds. It'll need to be faster than that
(although I'm guessing we can speed that up quite a bit) :)

---

Reply to this email directly or view it on GitHub: https://github.com/pyca/cryptography/issues/569#issuecomment-34356622

— Reply to this email directly or view it on GitHub (https://github.com/pyca/cryptography/issues/569#issuecomment-34359472).

[public]

Would making the direct argument constructor private mean we don't have to do all this? It's not intended for normal usage at all anyway, mostly to support constructing keys via serialisation formats not supported by your backend.

We could have init create unusable keys or raise an exception.

Of course if we intend to also verify the content of serialised keys too then it doesn't save us anything.

[reaperhulk]

If we make this way of building a key private then I'd be willing to remove most of the checks. I think basic checks like p * q = n and e >= 3 and e&1 != 0 should still be there since they are relatively cheap, but people shouldn't be using private APIs inside hazmat unless they're willing to accept the consequences?

[alex]

Eh, you kind of need an API like this if you want to do interesting things like implement SSH; I don't think Hazmat is an excuse to be more unsafe than necessary.

On Thu, Feb 6, 2014 at 12:41 PM, Paul Kehrer notifications@github.comwrote:

If we make this way of building a key private then I'd be willing to remove most of the checks. I think basic checks like p * q = n and e >= 3 and e&1 != 0 should still be there since they are relatively cheap, but people shouldn't be using private APIs inside hazmat unless they're willing to accept the consequences?

— Reply to this email directly or view it on GitHubhttps://github.com/pyca/cryptography/issues/569#issuecomment-34368346 .

"I disapprove of what you say, but I will defend to the death your right to say it." -- Evelyn Beatrice Hall (summarizing Voltaire) "The people's good is the highest law." -- Cicero GPG Key fingerprint: 125F 5C67 DFE9 4084

[reaperhulk]

We've pretty much resolved this at this point (#580, #582, #605 all related to this). Additionally, it turns out the backends we've looked at have checks that are inferior to the ones we're doing at this point so I'm going to go ahead and close this issue. If anyone disagrees speak up!