61
$\begingroup$

I (for a test) just randomly altered a private RSA key by opening it up in Vim and changing a few bytes. It is the private part of an SSH key pair used for logging in on a remote system. Puzzlingly, it still allows me to login.

I did some research and found that it is a base64 encoded ASN.1 container, so I pulled all the relevant integers out with OpenSSL and it seems only $d$, the private exponent, has changed (and only slightly at that). Is it possible the additional cached values are therefore being used to decrypt the value sent from the server, in order to still allow me to be logging in? The public key can (as expected) still be derived due to the other integers in the ASN.1 still being the same.

As I'm an encryption dufus I'd appreciate some guidance on how the above is possible. I've found when I modify the key in Vim by larger amounts it rejects me as expected. Thanks.

$\endgroup$
  • $\begingroup$ Changing the d , private exponent without changing other parameters, you will lose the original properties of the whole key pair. Check how is the d argument generated. Anyway quite interesting topic. Can you share the keys (or create similar) to reproduce the case? $\endgroup$ – Jakuje Jan 9 '16 at 19:33
  • $\begingroup$ Are you sure that this key was used? Check with ssh -v host. Isn't there a DSA-key too by chance? $\endgroup$ – ott-- Jan 10 '16 at 7:20
  • $\begingroup$ It was definitely the RSA key. $\endgroup$ – PhilPotter1987 Jan 10 '16 at 20:11
85
$\begingroup$

An ASN.1-encoded SSH private key contains the following integers in order:

  • The public modulus $n$ and exponent $e$;
  • The private exponent $d$;
  • The prime factors $p$ and $q$ of $n$;
  • The "reduced" private exponents $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$;
  • The "CRT coefficient" $q_{\text{inv}}=q^{-1}\bmod p$.

The observation that the value of $d$ in such a key may be irrelevant is due to the following: To speed up exponentiation modulo $n$ by a factor of about $4$, the Chinese Remainder Theorem can be utilized to compute the result modulo $p$ and $q$ separately and subsequently combine them to obtain the "real" result modulo $n$. With this optimization, the values of $n$, $e$ and $d$ are not required, hence are ignored by typical implementations whenever $p$, $q$, $d_p$, $d_q$ and $q_{\text{inv}}$ are available*. This is why changing some characters in the middle of the key need not necessarily destroy it, depending on which of the components you change.

*) at least for OpenSSH, they do not have to be present: setting $p=q=1$ and $d_p=d_q=q_{\text{inv}}=0$ makes the implementation use $n$ and $d$.

To visualize the arrangement of the individual components, I created the following graphic from a typical 4096-bit RSA private key file:

RSA private key with highlightning of the encoded numbers

The grey part right in the beginning is ASN.1 header data (encoding the fact that a sequence is about to follow, etc), followed by the integers forming the key as described above. The ASN.1 header data associated to each component (mostly a length field) is colored slightly brighter than the data representing the integer itself. Note that the pictured subdivision is not 100% accurate as one Base64 character encodes roughly $3/4$ raw bytes, hence some boundaries should actually run strictly within a single character.

$\endgroup$
  • 2
    $\begingroup$ Related question: crypto.stackexchange.com/questions/6593/… (formerly linked from my answer, which I deleted as otherwise redundant to this one). $\endgroup$ – Ilmari Karonen Jan 9 '16 at 21:24
  • 4
    $\begingroup$ @yyyyyyy: Meta question: I like your colorization. What programs did you use? $\endgroup$ – StackzOfZtuff Jan 11 '16 at 8:37
  • 2
    $\begingroup$ @StackzOfZtuff Thank you! Unfortunately I am not aware of any convenient program for things like this: My "toolchain" consisted of a horrible mixture of OpenSSL, Python, LaTeX, and GIMP, along with a non-negligible amount of manual work. $\endgroup$ – yyyyyyy Jan 11 '16 at 12:12
  • $\begingroup$ Blimey! I've upvoted the answer for the colorization alone :) [needless to say it is a very helpful answer for all RSA newbies, I've saved a link to it in my favourites]. $\endgroup$ – tum_ Jun 24 '16 at 7:39
  • $\begingroup$ Re: "at least for OpenSSH, they do not have to be present: setting $p=q=1$ and $d_p=d_q=q_{\text{inv}}=0$ makes the implementation use $n$ and $d$." The same appears to hold true for OpenSSL as well: I just tested a certificate constructed with these parameters against Node.js's crypto.privateDecrypt and it worked without errors. $\endgroup$ – Stuart P. Bentley May 10 '17 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.