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?

Well, the answer says

> With this optimization, the values of n, e and d are not required

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.

It's a private key so sharing it kinda defeats the purpose. This also only works because the modified part isn't being used.

I mean,if you want compact just use ECC key instead of rsa. It will be much shorter (and arguably more secure)

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.)

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.

That's the difference between format and content. Web servers make sure the format is correct, they won't inspect the content

I'm pretty sure they mean a web server configured to use the content for TLS.

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.

A good example of the robustness of binary formats compared to text formats.

This has nothing to do with binary versus text.

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.

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.

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.

Is there a reason I should blame the OS specifically and not the C runtime?

I guess it depends on how specific you want to be. The Windows C runtime is a component of the OS.

Well you're not really supposed to use the OS copy of msvcrt.dll

Yes, library functions do what you ask them to do.

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.

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.

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.

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

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.

> 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.

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.

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.

Yes, I'd assumed people would have some basic knowledge before commenting to disprove the point and have functional synapse with basic correlation skills.

Is an obvious conclusion to me, otherwise why would I point it out in the first place?

Knowing when Fermat's little theorem gets used outside math is not basic knowledge!

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.

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.

Though there could've been different ways to ask rather than saying, arrogantly, "wheel is used everyday too"

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.

You took the wrong one

No, you just have a pet fact that doesn’t really matter to anyone but you

> 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.

> 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...

They also all use addition, which was invented so long ago, we don't know when it was.

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.

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.

Ceasar’s cipher is neither complex nor an OTP. What are you talking about?

What are you talking about. That was the first cipher.

RSA is OTP?

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.

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

Otp

Otp

> 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.

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.

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

I did that in university before you born

It can be done manually easily

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.

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.

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.

Expensive but spy agencies did it.

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.

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_π

People can get shockingly good at that kind of thing with enough practice.

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 "those types of systems" that can't upgrade.

[0]: https://nickjanetakis.com/blog/switching-from-an-rsa-ssh-key...

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.

> 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.

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.)

> 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.

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.

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.

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.

Euler was also the one to generalise the result to non-prime integers. He could have used the Chinese remainder theorem to do so but the first know use of it by western mathematicians was due to Gauss in 1801.

To be fair mathematics was really close for a really long time, but before that generalisation not all of the ingredients were there at the same place at the same time. It might well have been possible for the Chinese or Hindu-Arabic mathematicians to discover Fermat's theorem or perhaps even Lagrange's theorem (which is how I'd prove it from scratch if necessary), but as far as I can tell they did not.

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.

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.

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

> 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.

> 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...

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.

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.

What a beautifully formatted reply.

Nutshell: lack of an integrity check (such as CRC32) over an object that contains fluff fields that don't affect the crypto.

(comment withdrawn)

Why? it got the correct answer (guess #3 was arguably correct, albeit phrased a bit misleadingly)

Finally I understand why private RSA keys are so freaking long; storing redundant information explains it.

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?

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."

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.

Actually my question was poorly stated. I meant to ask what the parent comment understood, but the grandparent comment understood my question in a different way - on the ASN.1 level and not on the crypto level, like issues with different parsings of same weird XML documents.

It's important for the title to say (2016) because things have changed A LOT.

Care to elaborate?

OpenSSH private keys are now their own format, not ASN.1 encoded. There is still two 4 byte "checkint" values that can vary (but must match), but less redundant overall.

https://cvsweb.openbsd.org/src/usr.bin/ssh/PROTOCOL.key?anno...

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...

I actually use this as a form of a canary when ssh keys must be reside in multiple systems -- in the case where a key is found outside of is proper place it identifies the source during investigations.