The problem here is the distinction between an n-bit random number and n-bit modulus. In DSA, if you're working with a 521-bit modulus, and you need a random k value for it, k needs to be random across all 521-bits.

Systems programming intuition tells you that a 512-bit random number is, to within mind-boggling tolerances, as unguessable as a 521-bit random number. But that's not the point. A 512 bit modulus leaves 9 zero bits, which are legible to cryptanalysis as bias. In the DSA/ECDSA equation, this reduces through linear algebra to the Hidden Number Problem, solvable over some number of sample signatures for the private key using CVP.

Later

Here you go, from Sean Devlin's Cryptopals Set 8:

https://cryptopals.com/sets/8/challenges/62.txt

So I think the other lesson here is that deviating from a cryptographic right answer is a major footgun unless you understand exactly why the recommendation works the way it does and exactly what the implications are of you doing it differently.

But I may be hair-splitting. Like, yeah, they freelanced their own deterministic nonce generation. Either way, I think this code long predates 6979.

You're right that this was not an RNG security problem and instead was a problem with not understanding ECDSA nonce rules. However the notable fact for me was that the developer was apparently aware of the recommended way to deterministically generate nonces prior to the vulnerability being introduced and made a choice not to implement the RFC because what PuTTY was already doing seemed close enough, without fully understanding the implications of doing so. To put it another way, understanding ECDSA nonce rules would have avoided this vulnerability, but so too would implementing the RFC recommended way even if the developer did not fully understand why it was better than the existing implementation.

As you can probably see, I just love this bug class, is all.

I agree! DSA nonce issues are a great class of cryptographic bug in that they're sort of weirdly unexpected failure properties when you first hear about it.

See step (h) in Section 3.2. The nonce is selected by rejection sampling. Thus, under the above assumption about HMAC, the result is indistinguishable from uniformly random in the [1, q-1] range.

So it would have been pretty easy to just reuse the function for a modulus value that was too big without encountering any errors. And the old code was written 15+ years before it was used for P-521, so it's entirely possible the developer forgot the limitations of the dsa_gen_k() function. So maybe there's another lesson here about bounds checking inputs and outputs even if they don't apply to anything you're currently doing.

If you have a bit of instinct for this, it feels obvious that 'reducing' a smaller number by a larger one is not going to obscure the smaller 1 in any meaningful way, and instead it will leave it completely unchanged.

I don't think this is so much what you make it out to be, but a poor understanding of basic discrete maths (also I think you mean the 521 bit modulus leaves 9 zero bits, the modulus normally refers to the divisor not the remainder)

https://mathworld.wolfram.com/Modulus.html

This is one of the major reasons that crypto is hard and if you try to get around the "hard" bit your "shortcut" will probably come back to bite you. When it comes to crypto and accuracy (and hence security), more communication, and detailed communication are probably the solution not the problem.

To any programmer who is accustomed to thinking in binary but hasn't heard the full story about why it ended up being such an odd number, 521 is virtually indistinguishable at a glance from the nice round number that is 512. Heck, when I first read about it, I thought it was a typo!

To avoid this issue, you either want your random value to be significantly larger than the modulus (which is what EDDSA does) or you want to generate random values of the right number of bits until one happens to be smaller than the modulus (which is what RFC 6979 does).

Sure, but the other half of systems programming intuition tells you "the end user is going to truncate this value to 8 bits and still expect it to be random".

It's reassuring to see a solid disclosure after a security issue, and we too often see half-truths and deceptive downplaying, e.g. LastPass.

Many people I know, with less than 1% of his contributions to OSS, have inflated egos and are just full of themselves, so it is refreshing to have people such as Simon in the OSS community.

Public keys are enough of a pain in the ass with PuTTY / KiTTY that I stick with password auth for my windows SSH'ing needs.

KiTTY even let's you save the passwords so you don't have to type it in, a horrible security practice no doubt, but so convenient... Perhaps more secure than the putty-gen'd ECDSA P521 keys? A tad bit ironic.

This particular bug basically fell into our hands while staring at the source code during our investigation of the security of SSH client signatures.

(Rant: All these years later, we're all still doing penance for the fact that Schnorr signatures were patented and so everyone used ECDSA instead. It's an absolute garbage fire of a signature scheme and should be abandoned yesterday for many reasons, e.g., no real proof of security, terrible footguns like this.)

EdDSA, which is essentially deterministic Schnorr, does solve the problem.

Also, the use of P-521 didn't specifically cause the vulnerability, but the bad interaction between SHA512 and P-521 did play a role. It is unfortunate that nature conspired against us to make 2^511 - 1 a composite number. The fact that you have to go up to 521 bits to get a Mersenne prime whereas the natural target length for a hash output is 512 bits is the fatal interaction here.

(And indeed, nature could have been kinder to us and given us a Mersenne between 127 and 521...)

Never heard of (which probably demonstrates that I know pretty much nothing about cryptography?), so seeing a name spelled like "Schn...r" in this context makes at least me think of an entirely different luminary in the area. Thought it was a typo at first.

Ssh agent will manage your ssh keys through windows registry windows login process.

Also if you use wsl, you can access your ssh keys in wsl from the windows ssh-agent via npiperelay

For me, the stakes are very low. It's my windows "gaming" machine, and has access to a few low-value hosts.

Otherwise I'd invest the time to learn wtf is pageant ;D

PuTTY was a great tool for many years and a lot of people have good reasons to not want to let it go. As with most software it accretes habits and processes built on top of it that are hard to leave. But also useful to sometimes remind about the new options because you never know who wants to be in the Lucky 10K to learn that Windows Terminal now has deeper, "true" terminal emulation or that Windows has ssh "built-in".

  C:\Users\luser>ssh-agent
  unable to start ssh-agent service, error :1058

PuTTY has a workaround, allowing PAGENT.EXE to be used in place of the forbidden/inaccessible Microsoft agent:

https://tartarus.org/~simon/putty-snapshots/htmldoc/Chapter9...

So PuTTY remains quite relevant because of the mechanisms that Microsoft has chosen.

If you need ammunition to encourage your corporate IT to allow you to run the proper ssh-agent service to do your job instead of increasing your attack surface by installing PuTTY/Pageant, you could collect a list of vulnerabilities such as the one posted here (look at the huge count of affected versions on just this one!). There should be plenty of vulnerability maintenance evidence on the Microsoft-shipped version of an open source tool with a lot of eyeballs because it is "the standard" for almost all platforms over the "single developer" tool that took at least a decade off from active development (and it shows).

This made me laugh :-) Grandparent is probably happy to just fly under the radar. The suggested conversation would probably play out thusly:

> IT! You idiots! Your dumb policies are forcing me to use this insecure software! Look how many vulnerabilities it has had over the years!

>> Hold up. Rewind. What's this software that you've installed?

> It's called PuTTY. And if you just change this policy I could...

>> And how insecure is it?

> Just check out all these vulnerabilities! It's probably not worse than the average, but it's unnecessary extra attack surface area that...

>> I'm going to need you to uninstall that. Now. And I'll need confirmation via email that you have done so by EOB, with your boss and the CISO on CC.

> But if you just change this boneheaded policy...

>> Now, please. We have a security incident on our hands. We can discuss policy another time. Is there anything else installed on your laptop that I should be aware of?

We were directed to use our new corporate SFTP instead of direct communication with our vendors and customers.

I tried direct ssh on the second account they gave us, got a shell, pulled /etc/passed, and my manager mailed it to corporate security.

We had a long talk about configuring ssh. I don't know if it helped.

It’s also why web apps are so popular and why the blackberry failed.

I encountered this, too, but the fix is quite simple.

That service is set to “manual” by default, (or maybe “disabled”) and setting it to “automatic” then starting it will get you running.

It is unlikely that this is a corporate lockdown measure.

Install WSL2 - you get the Linux SSH of your choice.

As mentioned above, Windows now ships with OpenSSH and windows terminal is good.

My favourite, but now probably obsolete solution was to install MobaXTerm which shipped with an SSH client. It's still great and there is a usable "free" version of it, but WSL2 does everything for me now when I'm forced to use windows.

ssh command is absolutely fine, but I much prefer a list of saved presets versus ~/.ssh/config file fuckery

Anyone care to explain how exactly? How it it any different to the top 9 bits being zero by chance (which happens in 1 out of ~500 attempts anyway)

I suspect there must be something else at play here.

EDIT: the nonce is PRIVATE, so the scenario I described would not work because we wouldn't know for which of the 30k signatures the nonce starts with 9 zero bits. Makes sense now.

(For example, if an attacker has compromised server A and you connect to it, they can now use your key to connect to server B which you also use)

Any k generation and subsequent signature generation are going to be impacted.

    ssh-keygen -l -f 

I am still wondering what the exact steps are to show the key type.

And I think converted key pairs in Putty format (.ppk) will have PuTTY-User-Key-File-2: ecdsa-sha2-nistp521 in plaintext.

For Pageant you should be able to select view keys from the system tray icon context menu and it should show the key type in the list.

For ssh-agent I think ssh-add -L should list the public keys (with key type) in the same format as the authorized_keys file

I'm not an expert, so if anyone is please correct me where I'm wrong!

"has an id starting ecdsa-sha2-nistp521 in [...] the key file" He also mentions some other places the information shows up.

> PuTTY-User-Key-File-2: ssh-rsa..Encryption: aes256-cbc

Indeed I seem to have used Puttygen in the past.

For keys from Linux ssh-keygen, the private key starts with:

> -----BEGIN OPENSSH PRIVATE KEY-----

and the public key starts with

> ssh-ed25519

PuTTY… Windows… gosh I feel dumb. I’ve used putty for almost 25 years but didn’t put two and two together until I just remembered how the pheasants in my garden would peck out the window putty to get at the ladybirds hibernating underneath.

This is not exploitable by simply passively watching traffic, so even for client keys, if you're certain that they were used in a constrained way, you should be fine. The difficulty is knowing that for sure, so it's still prudent to rotate.

Sounds like your server keys are safe.

  (Incidentally, none of this affects Ed25519. The spec for that system includes its own idea of how you should do deterministic nonce generation - completely different again, naturally - and we did it that way rather than our way, so that we could use the existing test vectors.)

A more interesting question (while we are on the 20/20 hindsight express) is why the dsa_gen_k() function did not include an assert(digest_len <= 512).

PuTTY carries its own formats from this time.

"For this reason, since PuTTY was developed on Windows before it had any cryptographic random number generator at all, PuTTY has always generated its k using a deterministic method, avoiding the need for random numbers at all."

> In all of those cases except P521, the bias introduced by reducing a 512-bit number mod q is negligible. But in the case of P521, where q has 521 bits (i.e. more than 512), reducing a 512-bit number mod q has no effect at all – you get a value of k whose top 9 bits are always zero.

For P-521, the base field is 2^521 - 1, but the modulus used when computing the nonce is not that value, it's the order of the P-521 curve. By Hasse's theorem, that's roughly p +- sqrt(p), which is essentially p for such large numbers (the cofactor of P-521 is 1, so the order of the group is prime).

So: both are 521-bit numbers, but the group order is less than 2^521-1. Its hex representation is 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409.

This doesn't make 13 a power of two. I'm aware of rejection sampling; my point was if you have a N bit value X and want M bits, truncating X to M bits and X MOD 2*M is the same. Neither solve the problem where M > N, which is what TFA is about.

Where did I imply that it is?

> I'm aware of rejection sampling; my point was if you have a N bit value X and want M bits, truncating X to M bits and X MOD 2*M is the same.

Sure.

> Neither solve the problem where M > N, which is what TFA is about.

If you observe my other comments, you'll see I'm well aware of what the article is about.

You used 13 as an example in a response to my comment that was:

Isn't modulo the same as truncation when dealing with powers of two?

I don't see the number 13 in any of my comments on this thread (except this one, or where I quoted you). Perhaps you are confusing me with someone else?

  Truncate(
    SHA-512(0x01 || message || private_key)
      || SHA-512(0x02 || message || private_key),
    bitsNeeded
  )

Even better, though, is to just use RFC 6979 and not implement it yourself.

Edit: To clarify further, the key in that case is not even handled by putty. All crypto ops are done on the token and the private key never leaves it. It can't be exported even because that defeats the purpose of using a hardware token. So putty will just tell the token or smartcard what to sign and the token returns the output.

That's why it's safe against this attack. Putty never handles the private key material in this scenario. So I never imported the private key in putty or pageant and I couldn't even if I wanted to. The agent just declares the public keys on the token.

I see all the downvotes but I didn't explain it properly. I've been using smart cards so long that these things are kinda a given for me.

I can really recommend doing it this way or doing the more modern fido2 auth. Hardware authentication is amazing and it even works on Android over nfc these days.

The biggest vulnerability I see is the issue of malware connecting to the unlocked token via the SSH agent, but I'm only using tokens that have touch to sign for this reason. They require a touch on the token for every operation.

> (The problem is not with how the key was originally generated; it doesn't matter whether it came from PuTTYgen or somewhere else. What matters is whether it was ever used with PuTTY or Pageant.)

——

Unfortunately, about that:

“(The problem is not with how the key was originally generated; it doesn't matter whether it came from PuTTYgen or somewhere else. What matters is whether it was ever used with PuTTY or Pageant.)”

Roughly speaking, an RSA key has to be 8 times as large as an EC key for the same security level.

The main disadvantage of RSA is the structure of finite fields, which allows specialized solutions to factoring (number field sieve). We do not know similar structures for elliptic curves, so for those we only have general attacks, thus allowing shorter key lengths.

One of the on call engineers had copied some documentation to his clipboard which had like:

Dbfile 1 location > /u01/ora/whatever

And accidentally right clicked…

I absolutely blame that software for ruining my Christmas one year, and I can’t really forgive it.

Please use OpenSSH.