{"action":"created","issue":{"url":"https://api.github.com/repos/briansmith/ring/issues/362","repository_url":"https://api.github.com/repos/briansmith/ring","labels_url":"https://api.github.com/repos/briansmith/ring/issues/362/labels{/name}","comments_url":"https://api.github.com/repos/briansmith/ring/issues/362/comments","events_url":"https://api.github.com/repos/briansmith/ring/issues/362/events","html_url":"https://github.com/briansmith/ring/issues/362","id":192163502,"number":362,"title":"implement NIST SP-800-56B-rev1-compliant RSA private key validation.","user":{"login":"briansmith","id":16816,"avatar_url":"https://avatars.githubusercontent.com/u/16816?v=3","gravatar_id":"","url":"https://api.github.com/users/briansmith","html_url":"https://github.com/briansmith","followers_url":"https://api.github.com/users/briansmith/followers","following_url":"https://api.github.com/users/briansmith/following{/other_user}","gists_url":"https://api.github.com/users/briansmith/gists{/gist_id}","starred_url":"https://api.github.com/users/briansmith/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/briansmith/subscriptions","organizations_url":"https://api.github.com/users/briansmith/orgs","repos_url":"https://api.github.com/users/briansmith/repos","events_url":"https://api.github.com/users/briansmith/events{/privacy}","received_events_url":"https://api.github.com/users/briansmith/received_events","type":"User","site_admin":false},"labels":[{"id":306920625,"url":"https://api.github.com/repos/briansmith/ring/labels/good-first-bug","name":"good-first-bug","color":"fbca04","default":false},{"id":402054654,"url":"https://api.github.com/repos/briansmith/ring/labels/rsa","name":"rsa","color":"e99695","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2016-11-29T01:24:35Z","updated_at":"2016-11-30T22:30:48Z","closed_at":null,"body":"See #360, where we've done some work on private key validation in Rust, replacing some similar code written in C.\r\n\r\nWe need to extend that work to comply with [NIST SP-800-56B-rev1](http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br1.pdf). Specifically, since we don't know how the exponent is determined, we need to implement the crt_pkv validation mechanism for the RSA Key-Pair Validation (Intended Exponent-Creation Method Unknown) case. That is in section 6.4.1.4.3.\r\n\r\n\r\nAt a minimum, we need to:\r\n\r\n* Annotate the code that does the private key validation with references to the steps given in the NIST document.\r\n* Restrict RSA private keys (but not public keys), to having *e* >= 65536. Note that the document allows for *e* to be up to 256 bits, but we're only going to maintain our 33 bit limit for now. (This is assuming the NIST document allows us to be more strict than what it specifies.)\r\n* Verify that (k<sup>e</sup>)<sup>d</sup>) == 1 for some 1 < *k* < `n` of our choosing.\r\n* Document the proof that our check p * q == 0 (mod n) is equivalent mathematically to p * q == n, or if it isn't, then replace it with a compliant check.\r\n* Add the checks on the consistency of *e* and *dmp1* and *dmq1* that we've skipped.\r\n* Add the public key as a parameter to the validation. (I suggest doing this step last.) I haven't read the document carefully but presumably the point of this check is to make sure that the public key in the certificate is the same as the public key in the private key bundle; i.e. it is a check that the application is using a private key consistent with the public key it sends its peers.\r\n"},"comment":{"url":"https://api.github.com/repos/briansmith/ring/issues/comments/264017476","html_url":"https://github.com/briansmith/ring/issues/362#issuecomment-264017476","issue_url":"https://api.github.com/repos/briansmith/ring/issues/362","id":264017476,"user":{"login":"ranweiler","id":515835,"avatar_url":"https://avatars.githubusercontent.com/u/515835?v=3","gravatar_id":"","url":"https://api.github.com/users/ranweiler","html_url":"https://github.com/ranweiler","followers_url":"https://api.github.com/users/ranweiler/followers","following_url":"https://api.github.com/users/ranweiler/following{/other_user}","gists_url":"https://api.github.com/users/ranweiler/gists{/gist_id}","starred_url":"https://api.github.com/users/ranweiler/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ranweiler/subscriptions","organizations_url":"https://api.github.com/users/ranweiler/orgs","repos_url":"https://api.github.com/users/ranweiler/repos","events_url":"https://api.github.com/users/ranweiler/events{/privacy}","received_events_url":"https://api.github.com/users/ranweiler/received_events","type":"User","site_admin":false},"created_at":"2016-11-30T22:30:48Z","updated_at":"2016-11-30T22:30:48Z","body":"@samscott89, nice catch re my proof! You are right: I made the log-ceiling bounding hypothesis too strong, and so the result only applies to equal `p`, `q` (which are _excluded_ by the choice of `p`, `q`), so the result is trivial.\r\n\r\nUnless I'm mistaken, the line of argument is otherwise _valid_, though, so we can salvage something from it. If, in that earlier proof, we instead assume `m := max(⌈lg(q)⌉, ⌈lg(p)⌉) ≤ ⌈lg(n)⌉/2`, we can get a non-trivial result like so:\r\n\r\n**Proof.** In the context of the [earlier proof](https://github.com/briansmith/ring/pull/360#issuecomment-263434916), suppose the log-ceiling bound is weakened to `m ≤ ⌈lg n⌉ / 2`. Then the 2nd chain of inequalities yields `lg n + lg k ≤ ⌈lg n⌉`. But for any `x`, we have `⌈x⌉ < x + 1`, so we can derive:\r\n```\r\nlg n + lg k ≤ ⌈lg n⌉\r\n            < 1 + lg n \r\n```\r\nWhence `lg k < 1`. But `k` is a positive integer, and since `lg 2 = 1` and `lg` is an increasing function, we must have `k < 2`, and so `k = 1`, as required.\r\n\r\n**Comment.** @samscott89, how's that modified argument look to you? I also wrote a little Python script and checked that there _are_ interesting solutions (where `p != q`)."}}
{"actor":{"display_login":"ranweiler"}}