Hacker News Reader

Comment by tptacek | Hacker News Reader

This is one of the all-time cryptography footguns, an absolutely perfect example of how systems development intuition fails in cryptography engineering.

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

View on HN

What's really interesting to me is that there was a known solution to the DSA/ECDSA nonce generation problem, RFC 6979, which was published 4 years before the vulnerability was introduced into PuTTY. And it sounds like the developer knew about this RFC at the time but didn't implement it because the much earlier version of deterministic nonce generation that PuTTY already had seemed similar enough and the differences were assessed to not be security critical.

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.

I think 6979 is a bit of a red herring here. 6979 is about deterministic nonce generation, which is what you do to dodge the problem of having an insecure RNG. But the problem here isn't that the RNG is secure; it's more fundamentally a problem of not understanding what the rules of the nonce are.

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

I was going based off the commit link posted further down the thread (https://git.tartarus.org/?p=simon/putty.git;a=commitdiff;h=c...). You're right that the PuTTY deterministic nonce generating code does appear to significantly predate the RFC, but it sounds like the developer made a conscious decision when 6979 came out not to switch from what PuTTY already had because they looked similar enough. The PuTTY release that introduced support for elliptic curve cryptography (and introduced this vulnerability) was 0.68, which came out in 2017, 4 years after the RFC.

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.

Right, the reason I'm splitting hairs is that in my intuition, the whole rationale for 6979 is to eliminate the possibility of fully repeated nonces, for instance because your RNG is "unseeded". You can still end up with a biased nonce even if you're using a perfectly seeded random bit generator (as you can see here). But yeah I think we understand each other.

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

RFC6979 attempts to guarantee that the nonce is unbiased (under the assumption that HMAC's output is indistinguishable from random). It's definitely attempting to give a stronger property than simply preventing a repeated nonce.

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.

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

And then you find out about special soundness and that this is not only expected behaviour, but crucial to the security definitions and you realise that signatures are absolutely cursed.

The article addresses this: they wrote this code path in 2001. RFC 6979 was authored in 2013.

But elliptic curve support and this vulnerability weren't introduced until 2017, and the commit log (https://git.tartarus.org/?p=simon/putty.git;a=commitdiff;h=c...) makes it clear the developer was aware of the RFC but chose not to upgrade the 2001 code. Doing so prior to the elliptic curve support being added would have completely avoided this vulnerability.

In a parallel universe, they switched to RFC6979 in 2013, but the implementation had a bug that wasn't detected for years, allowing compromise of lots of keys. In that parallel universe, HN is criticizing them for following fashion instead of just leaving an already-proven piece of crypto code in place.

It's an unfortunate bug, an unfortunate oversight, but I think they made a perfectly reasonable choice at the time.

I don't think anybody consciously looked at 9 zero bits and thought this is fine, but it rather looks like unfortunate effect of plugging old code into new algorithms without proper verification.

You could be right. If you look at the old code, dsa_gen_k(), that was removed during the commit (https://git.tartarus.org/?p=simon/putty.git;a=commitdiff;h=c...), it does basically no bounds checking, presumably because at the time it was written it was assumed that all modulus values would be many fewer bits than the size of a SHA-512 output.

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.

I mean, bounds checking should really be caught by complete test coverage, shouldn't it? Or fuzzing? It doesn't address the more fundamental problem of cryptanalysis attacks, but it would definitely help mitigate the simple mistakes which can lead to exploitable implementations.

The very existence of 521-bit ECDSA is a footgun just waiting to go off.

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!

There are many footguns in ECDSA, it's an old algorithm created to exist, instead use an algorithm designed to be safe, like ed25519.

The size is unexpected, but I believe this would have been an issue even if it really was 512-bit ECDSA rather than 521. Taking a random 512-bit number, which is what the PuTTY nonce function produced, and taking it modulo another 512-bit number, would also bias the output. Not as severely as having 9 bits that are always zero, but enough to be potentially exploitable anyways.

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

The number in question is actually:

  $ bc
  bc 1.07.1
  Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free 
  Software Foundation, Inc.
  This is free software with ABSOLUTELY NO WARRANTY.
  For details type `warranty'.
  2^521-1
  68647976601306097149819007990813932172694353001433054093944634591855\
  43183397656052122559640661454554977296311391480858037121987999716643\
  812574028291115057151

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

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 not the difference between an n-bit random number and an n-bit modulus. It's the difference between a 512-bit random number and a 521-bit random number. It's very simple, but wording it as number vs. modulus is needlessly confusing, just adding to the problem you are bemoaning.

The issue with cryptography is that you have to be precise, that means the communication needs to involve far more detail, even if it can initially be confusing.

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.

Agreed; my problem was that the parent comment was imprecise, and hence confusing. "n bit random number vs. n bit modulus" implied n was the same in each case, whereas 521 is not the same as 512.

I feel like there should be some intuition like a cable rated for 100kg is not suitable for holding 110kg, therefore 512 bits of entropy is not rated to be 521 bits of entropy?

Oh well, there’s this very popular library which generates 256-bit keys setting the last 128 bits to a value derived from the first 128 bits. So I guess in agreement with your post: actually achieving full entropy is not obvious.

https://chilkatforum.com/questions/622/algorithm-for-generat...

No, it’s actually far worse than that. This is like if you bought prestressed concrete rated for 100kg and you loaded it with 50kg. This is less than the limit, so it’s good right? Nope, the way it works is that you have to give it exactly 100kg of load or else it’s weak to tension and your building falls over in the wind. The problem here is that not that they needed 521 bits of entropy and 512 was too little but that 521 bits of entropy of which 512 are legit and the top 9 bits are all zeroes breaks the algorithm completely and makes it not secure at all. In fact I think copying 9 bits from the other 512, while not great, would have probably made this basically not a problem. I am not a cryptographer though, so don’t quote me on that ;)

The article has a good writeup. Clear, actionable, concise.

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

Tf is a zero bit and how is it distinct from a zero bit?

I'm not quite sure what you're asking here but note that 521 != 512, and the former is not a typo.

Plot twist: The choice of 521 is adversarial specifically to exploit PuTTY without being easily noticed. (Ok I get that 2^521-1 is a mersenne prime).

maybe 2^521-1 being a mersenne prime is adversarial

only in base 10 :)

I considered making that joke, that the established common base was picked adversarially to have 521 and 512 be confusingly similar but couldn't find a non convoluted way of expressing that without implying primes change with base

A zero bit is not a cryptographically random bit.

Here it is the difference between a bit that is part of a cryptographically-safe random number and just happens to be zero, but had equal chance of being one, and a bit that is zero every time because of the way the numbers are being generated.

Reply on news.ycombinator.com