[HN Gopher] Why does my SSH private key still work after changin...
___________________________________________________________________
Why does my SSH private key still work after changing some bytes?
(2016)
Author : curling_grad
Score : 492 points
Date : 2022-12-31 05:30 UTC (17 hours ago)
(HTM) web link (crypto.stackexchange.com)
(TXT) w3m dump (crypto.stackexchange.com)
| jesprenj wrote:
| I'm a newbie regarding computers and mathematics, but would it be
| possible to construct an ASN.1 privkey structure that would be
| interpreted by different libraries as different privkeys?
|
| Could this be abused in any way?
|
| What implementations use the legacy approach of using $d$?
|
| Do TLS keys/x509 express the same phenomenon?
| ondhbcjg wrote:
| It shouldn't be possible to manipulate the ASN.1. The answer to
| your first question _should_ be no, to the second yes.
|
| See this brand-new paper which briefly discusses the desired
| property of "non-malleability": https://www.fstar-
| lang.org/papers/asn1star.pdf
|
| "DER are designed to ensure that every value of a given ASN.1
| type has a distinct, canonical wire format representation. That
| is, DER formats are intended to be unambiguous and non-
| malleable, in the sense that given a bit string b that encodes
| a value v, every parser will yield back o, whereas changing any
| bit in b either produces an invalid representation or yields a
| distinct value o' + v. These properties are particularly
| important in security applications, inasmuch as they depend on
| values u but apply cryptographic protection only on binary
| formats b."
| layer8 wrote:
| This is incorrect. The properties of DER you cite do not
| prevent changing parts of an RSAPrivateKey structure (i.e.
| replacing o by an arbitrary o' is perfectly possible). The
| properties only prevent two different DER structures from
| representing the same value.
|
| It is possible to have an RSAPrivateKey structure where the
| privateExponent field is inconsistent with the
| exponent1/exponent2 fields, effectively representing two
| different private keys, and where one library uses the one
| and another uses the other. However, that just means that
| only one of the two would work with the given public key.
|
| That can be exploited only insofar as it will break
| interoperability depending on which library is used. In
| addition, an attacker would need access to the private key in
| order to create the inconsistent values, or would need to
| install a key creation software producing such inconsistent
| values, in which case the attacker probably can already do
| much worse.
| perlgeek wrote:
| Finally I understand why private RSA keys are so freaking long;
| storing redundant information explains it.
| g0xA52A2A wrote:
| What a beautifully formatted reply.
| kazinator wrote:
| Nutshell: lack of an integrity check (such as CRC32) over an
| object that contains fluff fields that don't affect the crypto.
| logicallee wrote:
| (comment withdrawn)
| bawolff wrote:
| Why? it got the correct answer (guess #3 was arguably correct,
| albeit phrased a bit misleadingly)
| [deleted]
| ksaj wrote:
| This is pretty interesting. I wonder how much of the key you can
| gore out without affecting its functionality. Enough to pass
| compact messages to a modified service?
| lucakiebel wrote:
| Well, the answer says
|
| > With this optimization, the values of n, e and d are not
| required
| dataflow wrote:
| The thing is, that depends on if the client wants to use the
| other bits instead. The key is broken if the parts are out of
| sync, even if some clients ignore some parts.
| bawolff wrote:
| I mean,if you want compact just use ECC key instead of rsa. It
| will be much shorter (and arguably more secure)
| drewtato wrote:
| It's a private key so sharing it kinda defeats the purpose.
| This also only works because the modified part isn't being
| used.
| vasqw wrote:
| It's important for the title to say (2016) because things have
| changed A LOT.
| muhehe wrote:
| Care to elaborate?
| egberts1 wrote:
| Off topic: audit tool for OpenSSH config files.
|
| Posted here because SSH algorithms are a moving target.
|
| https://github.com/jtesta/ssh-audit/tree/e50ac5c84d46e902e02...
| [deleted]
| userbinator wrote:
| I think this is an example of how, unless you're specifically
| designing a file format to be redundant for error
| detection/correction or similar reasons, having "this field must
| always be related to that field in this manner" types of
| constraints introduces redundancy, and with it, the associated
| ambiguities of inconsistency (and opportunities for code handling
| the format to behave erroneously.)
| locusofself wrote:
| I think it's funny that removing what looks like actual key
| material doesn't break a key, but having the wrong kind of
| newline, or trailing newline in a .pem file can cause certain
| programs (webservers etc) to not be able to load a cert or key.
| IshKebab wrote:
| A good example of the robustness of binary formats compared to
| text formats.
| metafunctor wrote:
| This has nothing to do with binary versus text.
| myself248 wrote:
| I think it does, insofaras OSs feel free to just fuck with
| the contents of files they think are text, replacing
| newlines willy-nilly. Files not identified as text are safe
| from such automatic tampering.
| MayeulC wrote:
| I've never seen this behaviour at an OS level. This seems
| like an editor issue, and binary files are not exempt
| from being messed up by a slightly incompatible editor,
| far from it.
| nemetroid wrote:
| Perhaps you have been spared from writing code for
| Windows:
|
| https://learn.microsoft.com/en-us/cpp/c-runtime-
| library/refe...
|
| > In text mode, carriage return-line feed (CRLF)
| combinations are translated into single line feed (LF)
| characters on input, and LF characters are translated to
| CRLF combinations on output.
| tedunangst wrote:
| Yes, library functions do what you ask them to do.
| Dylan16807 wrote:
| Is there a reason I should blame the OS specifically and
| not the C runtime?
| nemetroid wrote:
| I guess it depends on how specific you want to be. The
| Windows C runtime is a component of the OS.
| Dylan16807 wrote:
| Well you're not really _supposed_ to use the OS copy of
| msvcrt.dll
| woodruffw wrote:
| I don't think this is a good example of robustness: if the
| change had happened to affect the DER encoding instead of
| just a field within the DER encoding, this could just have
| easily been an example of the fragility of binary formats.
|
| Rather, what's happening here is that the _interpretation_ of
| the parsed format is malleable in an arguably incorrect way.
| There aren 't any great solutions that I'm aware of to that,
| since the "fix" is to validate the correctness of fields that
| ultimately don't matter to the operation at hand.
| MayeulC wrote:
| IMO that distinction doesn't make much sense. Text is (as
| soon as it's stored on a computer) a binary format: you have
| to specify encoding, etc.
|
| Inserting or removing a control character in a binary file
| would break stuff too. Maybe even more so.
|
| You may think of the ability to add CRCs (or at least
| checksums/parity bits) in a binary file? That's extra work,
| and can be provided by other mechanisms, like par files or at
| the filesystem level.
|
| The advantage of text formats is that binary decoders for
| text are ubiquitous. That said, it's usually simple to filter
| input data through a decoder like gzip.
| IshKebab wrote:
| You're not thinking about the human element. Parsers are
| implemented by real people, and they make mistakes.
|
| If a format is human-readable and text based it's both far
| more likely that a) the spec isn't actually complete
| (because there's an implicit "sensible" option), and b)
| people don't read the spec anyway and guess the "sensible"
| option.
|
| There are countless examples of bugs and security flaws in
| HTTP that wouldn't have been a problem with e.g. Protobuf.
| ausudhz wrote:
| That's the difference between format and content. Web servers
| make sure the format is correct, they won't inspect the content
| Dylan16807 wrote:
| I'm pretty sure they mean a web server configured to use the
| content for TLS.
| marcosdumay wrote:
| Isn't the whitespace in pem files just recommended? AFAIK,
| it's there just for interoperability with old transport
| protocols and not a part of the data at all.
| ausudhz wrote:
| What I find interesting about RSA is how it became so popular and
| important in our daily life, yet it uses basic math from hundred
| or thousands of years back.
|
| It uses the Fermat's little theorem of prime numbers, which was
| defined in 1640 then proved by Euler almost 100 years after that.
|
| Plus uses the Chinese reminder theorem that was discovered in the
| 300 CE
|
| What is more crazy is that RSA (or something comparable to that)
| was discovered in parallel also by another mathematician working
| for a government agency 4 years prior to the RSA algo
| aflag wrote:
| To be fair, most of popular and important algorithms and tools
| in our daily lives are likely even older than that. Arithmetic
| takes you a very long way. RSA is quite mathematically
| sophisticated (and recent) next to most of the algorithms we
| use. Also, look around your kitchen and you'll see a lot of
| tools that haven't changed much in millenia.
| kybernetikos wrote:
| > What is more crazy is that RSA (or something comparable to
| that) was discovered in parallel also by another mathematician
| working for a government agency 4 years prior to the RSA algo
|
| That story is great - he was a new grad and given it as an
| exercise by his mentor. He wasn't allowed to write anything
| down at home so he worked it out entirely in his head that
| evening.
| contravariant wrote:
| You'll want Euler's theorem (one of the many) for RSA, it won't
| be much use to have a prime number as a key since it's not
| exactly hard to guess its factorisation. That moves your date
| by a hundred years, into the later half of the 18th century.
|
| So not exactly thousands of years back.
| ausudhz wrote:
| Chinese reminder theorem is from 300 CE. 1700 years ago.
|
| That's actively used in some libraries to validate the key
| (as stated in the link)
|
| Euler just proved what Fermat theorized.
| timthorn wrote:
| > What is more crazy is that RSA (or something comparable to
| that) was discovered in parallel also by another mathematician
| working for a government agency 4 years prior to the RSA algo
|
| Cocks, Ellis and Williamson at GCHQ:
| https://www.nsa.gov/History/Cryptologic-History/Historical-F...
|
| An interview with Cocks and Ralph Benjamin:
| https://www.zdnet.com/article/gchq-pioneers-on-birth-of-publ...
| anothernewdude wrote:
| They also all use addition, which was invented so long ago, we
| don't know when it was.
| oraetlabora wrote:
| > yet it uses basic math from hundred or thousands of years
| back
|
| as if that was an argument. We use the wheel for a gazillion o
| "important and f daily life" applications.
| ausudhz wrote:
| Great, you totally missed the point.
|
| While the wheel has been used from the next day of its
| invention till today, the Fermat's little theorem had no
| application outside of pure math for roughly 400 years.
| trompetenaccoun wrote:
| To be fair there was no obvious point, so how could it be
| missed? You simply wrote it's interesting without
| explaining what you find interesting about it.
| ausudhz wrote:
| [flagged]
| Dylan16807 wrote:
| Knowing when Fermat's little theorem gets used outside
| math is not basic knowledge!
| ausudhz wrote:
| It's if you studied computer science, is in the first
| year's program in many universities.
|
| This board is predominantly for IT and engineers and this
| post is about cryptography.
|
| If someone doesn't have an idea of what they're talking
| about, they should at the very least avoid commenting
| without having the knowledge of what's discussed.
|
| Is not that every opinion matters, it doesn't. Especially
| if you don't have any knowledge of the topic.
|
| Internet has given the illusion that anybody is one
| search away from being an expert on anything.
| imwillofficial wrote:
| I've taken many a crypto class and never picked up that
| nugget.
|
| You made a social misstep.
|
| Accept the correction with grace, try to be better, and
| move on.
| ausudhz wrote:
| You took the wrong one
| [deleted]
| Dylan16807 wrote:
| Those classes might mention this use. They're unlikely to
| teach students that it _wasn 't used elsewhere (outside
| math) until then_, which is a crucial part of the point
| you were making.
|
| Seriously, that specific aspect is trivia, not basic
| knowledge, even in the realm of cryptography.
| ausudhz wrote:
| Though there could've been different ways to ask rather
| than saying, arrogantly, "wheel is used everyday too"
| [deleted]
| [deleted]
| newpavlov wrote:
| Try to run a non-toy RSA by hand using pen and paper, it will
| be quite painful and impractical. Practicality of RSA largely
| depends on existence of computers. Even in the presence of all
| required theoretical knowledge, an application may not be
| practical, thus it does not get "invented" until the
| practicality issue gets resolved.
|
| I would say it's more interesting that one-time pad encryption
| was not invented and used much earlier than 19th century. It
| has obvious military and intelligence uses and is simple enough
| to be executed by hand.
| ausudhz wrote:
| For centuries people have been encrypting things "by hand"
| and "inconveniently" (Cesar's cipher is an example, I can
| make many more).
|
| RSA doesn't largely depends on the existence of computer, it
| could've been used "by hand" using the math behind it. The
| reason why was not is because, prior to computer, there was
| not a problem of "sharing" the key (and btw Nazi knew that a
| single key was weak, that's why they'd change it everyday to
| encrypt the communication with enigma)
|
| > I would say it's more interesting that one-time pad
| encryption was not invented and used much earlier than 19th
| century
|
| That's not true, as I mentioned Cesar's cipher is an example
| of that, though of course uses a simple key. Radio
| communications (and of course internet later) is the reason
| why encryption started to boom on the early 19th century
| onwards.
| Hendrikto wrote:
| Ceasar's cipher is neither complex nor an OTP. What are you
| talking about?
| ausudhz wrote:
| What are you talking about. That was the first cipher.
|
| RSA is OTP?
| nvrspyx wrote:
| The point originally made was that RSA couldn't
| _practically_ be used because of how complex the math is
| to do by hand. So, the parent is pointing out that the
| Caesar cipher isn 't a counterargument.
|
| In other words, the "inconvenience" of doing a Caesar
| cipher by hand is nowhere near comparable as doing an RSA
| cipher by hand.
| ausudhz wrote:
| Is not complex at all, if you can't multiply two prime
| number and do subtraction probably you should reconsider
| your skills.
|
| If people were able to do that in 15th century by hand I
| don't see how who really needs it couldn't.
|
| Is just the needs were different, but is not complicated
| krisoft wrote:
| > The reason why was not is because, prior to computer,
| there was not a problem of "sharing" the key
|
| Lol. There is a new dude sitting in a castle one sea over.
| You want to communicate with them. Let's say you want to
| agree to attack a third neighbour at the same time. If your
| message gets intercepted you will be in trouble.
|
| How do you share your secret keys with them? Mind you, you
| don't really trust any of your man, and the sea route is
| treacherous so you don't fancy risking going in person.
|
| Sharing keys is a problem old as time.
| ausudhz wrote:
| That's the point. Still though is very old is not a 19th
| century problem. Yet RSA was used 400 years after the
| theory behind
|
| Why didn't people came up with a manual "RSA" before.
| Since the math is 400 years old.
| codeflo wrote:
| I recommend you try to do it -- it's a fun exercise, and
| will very quickly answer any remaining doubt why it can't
| be done manually.
|
| We actually did that in university; the public key we
| used was something like 91 (not hard to factor).
| Wikipedia has an example with 3233, and that's already
| very cumbersome:
| https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example
| ausudhz wrote:
| I did that in university before you born
|
| It can be done manually easily
| zeven7 wrote:
| I tried generating an Ethereum address by hand starting
| by creating a random private key. It quickly got away
| from me.
|
| I wish there was some way to simplify the math to allow
| doing it by hand. It would be a nice way to check for
| correctness while computing it offline, and while
| ensuring dependencies hadn't been compromised to produce
| a fake public address.
| rocqua wrote:
| I feel like making your own circuits that could do this
| would be a more feasible approach. Or at least a circuit
| that uses small purpose build ICs that are easy to
| verify.
| im3w1l wrote:
| Well book ciphers go some ways back and they are almost OTP
| (in the sense of how they are performed, not in the sense of
| security properties). It may have been prohibitively
| expensive to print a custom pad used for encryption.
| ElevenLathe wrote:
| Expensive but spy agencies did it.
| jrochkind1 wrote:
| A one-time pad seems totally feasible to me without a
| computer, and sufficient motivation. RSA does not. They're
| different algorithms of course! OTP is a very simple one,
| as you point out.
| [deleted]
| Retric wrote:
| RSA on pen and paper isn't that bad compared to some other
| calculations people used to do by hand. By comparison in 1800
| multiple people had already calculated the first 100 digits
| of pie.
| https://en.wikipedia.org/wiki/Chronology_of_computation_of_p
|
| People can get shockingly good at that kind of thing with
| enough practice.
| eric__cartman wrote:
| I really enjoyed a piece of coursework that I was given on a
| discrete mathematics course that consisted of implementing RSA
| using the math theory taught in class. It's a very clever
| algorithm.
| [deleted]
| nickjj wrote:
| RSA SSH keys are starting to become phased out.
|
| Ubuntu 22.04 for example won't let you SSH into another server
| using an RSA key unless you configure your OpenSSH client to
| continue supporting RSA. I noticed this even with an RSA
| SHA-256 key[0]. GitHub and other git hosting providers are also
| pushing Ed25519 over RSA for generating new keys.
|
| I would say it's had a good run, and will likely still be in
| use for decades because there's always going to be systems that
| can't updated for whatever reasons.
|
| [0]: https://nickjanetakis.com/blog/switching-from-an-rsa-ssh-
| key...
| ryukafalz wrote:
| This is not correct. The ssh-rsa _signature algorithm_ is
| being phased out, but that 's not the same thing as RSA
| keypairs for authentication. This page has a good explanation
| of what's going on:
|
| https://levelup.gitconnected.com/demystifying-ssh-rsa-in-
| ope...
|
| It's unfortunate that there's a signature algorithm and a key
| format with the same name, because that definitely leads to
| confusion in cases like this. But RSA keypairs are fine for
| now.
| nickjj wrote:
| > It's unfortunate that there's a signature algorithm and a
| key format with the same name, because that definitely
| leads to confusion in cases like this.
|
| Thanks for the clarification, but from the end user's
| perspective it's all the same in the end?
|
| It translates to "I have an SSH keypair that was generated
| using RSA as the algorithm and I was able to SSH into my
| servers when using OpenSSH vX.X.X and now after updating
| OpenSSH to a newer version I can no longer SSH into the
| same servers.". In the end it used to work and now it
| doesn't and the solution is to pick a different algorithm
| such as Ed25519 or re-configure your OpenSSH client to
| continue allowing RSA even though the creators of OpenSSH
| have deprecated it by default.
| ryukafalz wrote:
| It's not quite the same in the end from the end user's
| perspective, no. If you were logging into servers running
| a recent-ish version of OpenSSH (i.e. newer than 2016),
| you would continue to be able to log in with your RSA
| keypairs with no changes, because the client and server
| would still be able to negotiate a signature algorithm
| that both support. It just so happens that very old
| versions of OpenSSH don't support any of the signature
| algorithms used with RSA keys that new clients prefer to
| use. In other words:
|
| > or re-configure your OpenSSH client to continue
| allowing RSA even though the creators of OpenSSH have
| deprecated it by default
|
| ^ this is not correct. RSA is not deprecated by default.
| A specific signature algorithm used with RSA keys is
| deprecated. But yes, if your server is running a very old
| version of OpenSSH, that may be the only signature
| algorithm it supports.
|
| I'm not sure there are any distro releases running
| versions of OpenSSH this old that aren't EOL though, so
| really you should probably update your servers, which
| would also take care of this. (I suppose if you're
| running CentOS 7 or RHEL 7 you still get security updates
| for the next 1.5 years at least, but it's no longer
| actively supported.)
| layer8 wrote:
| RSA keys aren't deprecated (apart from those with shorter
| key lengths, e.g. 1024 bits). What's deprecated is the
| use of SHA-1, and in consequence the signature algorithms
| that combine SHA-1 with RSA. Instead you have to use
| signature algorithms that combine other hash algorithms
| (like SHA-2) with RSA. RSA itself, and RSA keys, remain
| unaffected.
|
| Another thing that may get deprecated in the coming years
| is RSA 1.5 padding, requiring to use PSS padding instead.
| Again, that doesn't impact RSA keys, but only the
| algorithm parameters used with RSA.
|
| In the context of TLS/SSH, it just means that client and
| server have to negotiate the RSA-based algorithm variant
| they both support and both deem to be safe, using the
| existing RSA keys.
| InvaderFizz wrote:
| > Thanks for the clarification, but from the end user's
| perspective it's all the same in the end?
|
| The vast majority of users will not experience this
| unless their client is old. I literally dealt with this
| issue yesterday with one of our lead Developers.
|
| He was using JSch in an older version of dbeaver,
| couldn't SSH into the new test environments we're
| validating on Ubuntu 22.04. Turns out to be this exact
| issue. The solution was to update dbeaver and switch to
| the new default SSHJ client within it.
|
| Same private key, new client. Problem solved.
|
| I will be using this as leverage to force a company
| standard change from RSA4096 keys to ed25519. So I am not
| going to clarify the difference to the Security teams.
| ulrikrasmussen wrote:
| I'm a bit uncomfortable with the fact that the ASN.1 encoding is
| actually inconsistent but that the implementation happily ignores
| that and just uses the derived values. Since these values are
| entirely redundant, it feels like a bad design to include them in
| the key file. I guess the point of them is to make operations
| faster, and therefore they have to be cached to make any sense.
| ausudhz wrote:
| If you read the response you'd realize that it depends on how
| the key is generated.
|
| Is not a "bad design", is a feature that allows to include or
| exclude derived values, if you do so then the original values
| are used and the encoded private key would be smaller.
|
| The reason why they'd keep the original values when the derived
| are available might have to do with backwards compatibility
| and/or legacy constraint
| Dylan16807 wrote:
| > If you read the response you'd realize that it depends on
| how the key is generated.
|
| Where does it say or imply that? When I read the answer it
| sounds like using them is optional but generating them is
| mandatory.
| ausudhz wrote:
| > With this optimization, the values of n, e and d are not
| required, hence are ignored by typical implementations
| whenever p, q, dp, dq and qinv are available*
|
| > *at least for OpenSSH, they do not have to be present:
| setting p=q=1 and dp=dq=qinv=0 makes the implementation use
| n and d.
|
| https://crypto.stackexchange.com/questions/31807/why-does-
| my...
| layer8 wrote:
| This is a particularity of OpenSSH though and not
| supported by RFC 8017. The fields are mandatory and
| required by the spec to contained the correct values.
| [deleted]
| Dylan16807 wrote:
| I misread the second quote. I suppose that is evidence,
| but setting them to an incorrect value suggests that this
| might not be a _valid_ file even if it works.
___________________________________________________________________
(page generated 2022-12-31 23:01 UTC)