Schneier on Security

Mark Wooding • January 7, 2011 12:31 PM

@Clive Robinson

I’m sorry, but your claims about DSA are so full of mistaken premises and misinformation that I can hardly believe it. Let’s deal with them one at a time, shall we?

“They basicaly optomised out a critical and difficult to achive part of the DSA protocol and in the process opened up a big fat, wide open, side channel that got exploited. Importantly this optomisation did not break the actual functioning of the software and would have past any regression tests…”

Three errors here.

Firstly, using a fresh random value for each signature is not especially difficult, particularly when you consider the context, which is signing code as part of Sony’s release process. The console itself has no need to sign this stuff: it’s done in-house, internally, beforehand. Optimization is almost completely unnecessary; even so, there are several possibilities for improving performance. (An obvious one is to associate a symmetric key with the signing key, and use it to generate the per-message randomizer, e.g., by computing a pseudorandom function of a counter, the date or the input message. Note also that the randomizers, and the computationally intensive parts of DSA signature computation, can be done in advance, before the message is known, and without knowledge of the private key.)

Secondly, this is not a side-channel. This is a well-known property of signature schemes based on the Fiat–Shamir heuristic applied to a three-pass proof-of-knowledge, and, indeed, is an essential part of the security proof for such schemes: the ability to extract the prover’s (signer’s) private key if it responds to distinct challenges (messages) when rewound (reusing a randomizer) demonstrates that a prover (signer) who can generate convincing responses (signatures) with significant probability must actually know the private key. Such schemes go back to Taher ElGamal’s signature scheme of 1984; DSA shows the influence of Claus Schnorr’s scheme of 1989. (DSA doesn’t quite fit into this framework, because it doesn’t seem to have the necessary zero-knowledge property. This was pointed out in public comments at the time.) In the event that you implement such a signature scheme incorrectly by reusing randomizers, you have a plain old cryptanalytic vulnerability. It’s not a side-channel: the private key falls straight out of the front door.

Thirdly, this is exactly the sort of thing that a half-decent regression test ought to catch. Detecting reuse of a randomizer in DSA is very easy, since half of the signature depends only on the randomizer (and the domain parameters) — and not at all on the message nor on the key (either public or private).

“The fact that meeting all the “k value” requirments is difficult especialy in a high bandwidth communication system should ring bells in peoples heads about using it.”

It’s not at all difficult, as I described above.

“The fact that the DSA “k value” is so very easy to get wrong in practical implementations, must have been well known to the NSA prior to it being made available to NIST. You therefore realy have to ask why they did not make it clear…”

Mistaken premise. It was indeed made clear: FIPS 186 (1994; the document in which DSA was originally standardized) says, quite clearly, in section 4: `Parameter k must be regenerated for each signature.’

It’s true that later NIST standards contain much more implementation guidance than older ones. FIPS 186-3 (2009 — so after Sony had already made the mistake) has a section (4.5) entitled `DSA Per-Message Secret Number’ which explains the security properties needed for by the randomizer.

“The mistake the Sony software engineers made is an understandable one, when you don’t have a domain expert sitting at the design table, and during the review processes.”

No. It’s very hard to understand this error: it’d be in the You Fail Cryptography Forever page of tvtropes if they had one.

Any self-respecting hardware security module will use a distinct randomizer for each DSA signature since it can’t reuse randomizers and simultaneously make any pretence at holding signing keys securely. Standard HSM programming interfaces, e.g., PKCS #11, don’t provide any way to pass a randomizer into the signing algorithm from outside the module: it must generate it itself.

In turn, this indicates that Sony aren’t holding their signing keys in a hardware security module. Which is worthy of a facepalm all by itself.

This is a simple case of hubris — `We can implement the crypto ourselves just fine’ — properly punished by Nemesis.

“The problem with the designed by NSA employee and certified by NIST DSA and it’s “k value” has been known by domain experts for a while but not widely otherwise.”

You’ll have to explain to me why a non-domain expert will be writing a DSA implementation in the first place, and even then where he’d find out what it’s meant to do without tripping over the requirement that each signature use a distinct randomizer. Bruce’s book certainly makes this clear, as does Menezes, van Oorschott and Vanstone’s Handbook of Applied Cryptography, available online, not to mention the official standard.

“NIST with the help of the NSA have a number of protocols / standards that are overly brittle in use one way or another and if not used correctly each and every time will open up a side channel that leaks confidential information.”

Many (most?) cryptographic schemes impose requirements on higher-level protocols and applications which must be fulfilled for security. This is often described in terms of a security warranty': using the crypto widget wronglyvoids the warranty’.

Blaming the tendency towards `brittleness’ in cryptographic widgets on the NSA is very bizarre. If anything, it comes from the academic trend towards provably secure schemes and protocols. The proof tells you that, if you use the thing properly, and satisfy its conditions, and the explicitly stated intractability assumptions hold, the theorem gives you well-defined and (ideally) well quantified security properties. If one of these hypotheses fails, the theorem obviously doesn’t apply any more, and you might get nothing at all. (Consider GCM, where tag reuse leads to a catastrophic authentication failure.)

“I keep saying it but the three attack areas the likes of the NSA, GCHQ et al are going to be working in for their bread and butter code breaking are,
1, Protocol weaknesses (especialy their edge effects in practical implementations).
2, Side channels (of all kinds).
3, Known plaintext (in standard file headers etc).”

Known plaintext is irrelevant in modern cryptography. Any encryption scheme worthy of consideration resists /chosen/ plaintext attacks — and, in practice, security against chosen /ciphertext/ attack is also necessary. Worrying about known plaintext is infinitely more likely to cause errors due to ambiguous data formats than it is to defend against cryptanalysis.

Mark Wooding • January 10, 2011 7:20 AM

@ Clive Robinson

“Even more so if you have to ensure no reuse which is why despite the fact it is technicaly a ‘no no’ determanistic methods such as CTR are used. Even then people still easily get it wrong (Debian) and Richard Clayton over at Cambridge Labs went on an Internet hunt to find there were a very significant number of broken certs etc due to this.”

The Debian OpenSSL fiasco is a bit different. Debian botched the way that OpenSSL gathers external entropy, to the extent that it only used the process’s PID. While that did indeed cause key leakage as a result of reusing signature randomizers (I had to replace my own SSH keys), it’s not a a result of attempting to use a deterministic method — quite the contrary, in fact! It’s a result of botching the /true/ random number generator.

“The simple fact is a phrase such as`Parameter k must be regenerated for each signature’ has specific meaning to a domain expert, but is at best opaque to a code cutting software person.”

Really? It seems pretty plain to me (though I probably do count as a domain expert). It says that I must somehow concoct k afresh each time I make a signature. Elsewhere it describes k as `a randomly or pseudorandomly generated integer with 0 < k < q’. So I have to generate a new random (or pseudorandom) k each time. Where’s the difficulty?

I agree that some programmers aren’t particularly good at reading plain English, but describing those that can read a straightforward specification as `domain experts’ seems like a stretch. Besides, getting the rest of ECDSA to work involves implementing rather complicated things like arbitrary-precision (or at least rather high-precision) integer arithmetic and elliptic curve arithmetic (a somewhat rarefied area of mathematics); the sort of person who can manage this
is unlikely to have much trouble with FIPS 186. (Once you have the elliptic curve and finite field arithmetic implemented, ECDSA signatures are more or less trivial.)

“As for if the issue is a side channel or not it depends on your view point of what a side channel is. I tend to use it in a lose sense as a high level “class” of problem where by an apparently correctly functioning system convays unknown to the system user information that can be used to an adversaries advantage.”

I think this is incorrect. A cryptographic widget has certain inputs and outputs which are part of its syntactic structure. For example, an encryption scheme takes as input a key and a message (and maybe a nonce), and outputs a ciphertext; a signature takes as input a private key and a message, and outputs a signature. A side-channel is an additional output of the widget which doesn’t exist in an ideal' black-box instantiation but does in some practical implementation, such as power consumption, timing, cache effects, electromagnetic radiation, and so on. Side-channel attacks are interesting because the usual models used for analysing cryptographic widgets deal only with theideal’ version of the widgets: a practical instantiation might therefore be given a clean bill of health by this sort of idealized analysis, while leaking vital secrets through side-channels.

Reuse of a DSA randomizer is clearly visible in the signatures themselves. Since the signatures are a signature scheme’s `official’ output, this is therefore not a side-channel.

“In this particular case not regenerating parameter k did not stop the signing software working as advertised. It was only on multiple uses with the same value that it was possible using statistical methods to determine what the key was.”

No `statistical methods’ are necessary. Two signatures with the same randomizer are sufficient: you end up with two linear equations with two unknowns (the randomizer and the key), and very simple arithmetic yields the private key in its entirety.

Some more detail. DSA works with a group G of q elements (for some prime q), and the field K = GF(q) with q elements; it makes use of a mapping, which I’ll write using square brackets, from G to K. (In plain DSA, G is the q order subgroup of GF(hq + 1)* and […] is simply reduction modulo q; in ECDSA, G is an elliptic curve over a field of about q elements, and […] takes the x-coordinate of a point on the curve, converts it to an integer if necessary, and reduces it mod q.) Let P be a generator of G; Alice’s private key is a random element of K, which I’ll denote a, and her public key is A = a P. One signs a message hash m by choosing a random k, computing R = k P, u = [R], and v = (m + a u)/k; the signature is the pair (u, v). To verify the signature, check that [(m/v) P + (u/v) A] = u.

Now, suppose that m’ is a second message hash, and let v’ = (m’ + a u)/k be the second half of a signature on m’ using the same randomizer. Then v/v’ = (m + a u)/(m’ + a u); rearranging that gives a = (m v’ – m’ v)/(u (v – v’)) and it’s all over for Alice.

“The simple fact is when it comes to product engineering on what is effectivly an embbeded fast moving consumer electronics (FMCE) product in a highly cost sensitive market place, every byte of ROM or RAM counts. As wasting a byte “robs features”, that could help sell the product (have a look at legacy boot code and BIOS code in PCs to see this).”

This is irrelevant here. As I mentioned earlier, the console doesn’t make these signatures, so nobody ought to be counting bytes or cycles. The part which /verifies/ the signatures needs to be on the console (in the boot loader, indeed), but it seems that (unlike Nintendo!) the verification code is fine. It’ll be part of Sony’s release process, done on some server somewhere; it ought to have been an HSM, but wasn’t.